정수 모듈로 n으로 이루어진 집합은 덧셈과 곱셈의 연산을 포함하여 링(Ring)이 됩니다.
이는 집합 내의 두 요소를 더하거나 곱하는 경우에도 집합 내의 다른 요소가 반환된다는 것을 의미합니다.
모듈러스가 소수일 때: n = p인 경우, 우리는 집합 내의 모든 요소에 대한 역원을 보장받으며, 이로 인해 링은 필드(Field)로 승격됩니다. 이 필드를 유한체 Fp라고 합니다.Diffie-Hellman 프로토콜은 일반적으로 큰 소수인 유한체 Fp의 요소들로 작동합니다.
소수 p = 991과 요소 g = 209가 주어진 경우, g * d mod 991 = 1을 만족하는 역원 d를 찾아보겠습니다.
역원으로 d를 구하면 되는 문제이다 역원은 RSA에서도 했듯이 pycrypto 안에있는 inverse함수로 구할 수 있다.
from Crypto.Util.number import inverse
print(inverse(209, 991))
키를 직접 추가 하고 싶다면 키를 가지고 오는 코드를 삭제후 본인이 입력하면 제대로 동작한다.
from Crypto.Util.number import*
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5 as Cipher_PKCS1_v1_5
from base64 import b64encode
# Get public key from a file
pubkey_file = open("public_key.pem", 'r')
pubkey = pubkey_file.read()
pubkey_file.close()
flag_file = open("flag.txt", 'r')
flag = int(flag_file.read(), 16)
flag_file.close()
msg = "plain text"
# Create key using public key
keyPub = RSA.importKey(pubkey)
cipher = Cipher_PKCS1_v1_5.new(keyPub)
cipher_text = cipher.encrypt(msg.encode())
emsg = b64encode(cipher_text)
encryptedText = emsg.decode('utf-8')
n = keyPub.n
e = keyPub.e
def convergents_from_contfrac(frac):
convs = [];
for i in range(len(frac)):
convs.append(contfrac_to_rational(frac[0:i]))
return convs
def contfrac_to_rational (frac):
if len(frac) == 0:
return (0,1)
num = frac[-1]
denom = 1
for _ in range(-2,-len(frac)-1,-1):
num, denom = frac[_]*num+denom, num
return (num,denom)
def is_perfect_square(n):
h = n & 0xF;
if h > 9:
return -1
if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
# take square root if you must
t = isqrt(n)
if t*t == n:
return t
else:
return -1
return -1
def test_is_perfect_square():
print("Testing is_perfect_square")
testsuit = [4, 0, 15, 25, 18, 901, 1000, 1024]
for n in testsuit:
print("Is ", n, " a perfect square?")
if is_perfect_square(n)!= -1:
print("Yes!")
else:
print("Nope")
def isqrt(n):
if n < 0:
raise ValueError('square root not defined for negative numbers')
if n == 0:
return 0
a, b = divmod(bitlength(n), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def bitlength(x):
assert x >= 0
n = 0
while x > 0:
n = n+1
x = x>>1
return n
def hack_RSA(e,n):
# rational_to_contfrac ref
x, y = e, n
a = x//y
pquotients = [a]
while a * y != x:
x,y = y,x-a*y
a = x//y
pquotients.append(a)
frac = pquotients
# rational_to_contfrac ref end
convergents = convergents_from_contfrac(frac)
for (k,d) in convergents:
#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
discr = s*s - 4*n
if(discr>=0):
t = is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d
d = hack_RSA(e,n)
pt = pow(flag,d,n)
print(long_to_bytes(pt))
#!/usr/bin/python3
from Crypto.Util.number import getStrongPrime, bytes_to_long, inverse
class RSA(object):
def __init__(self):
self.p = getStrongPrime(512)
self.q = getStrongPrime(512)
self.N = self.p * self.q
self.e = 0x10001
self.d = inverse(self.e, self.N - self.p - self.q + 1)
def encrypt(self, pt):
return pow(pt, self.e, self.N)
def decrypt(self, ct):
return pow(ct, self.d, self.N)
rsa = RSA()
FLAG = bytes_to_long(open("flag", "rb").read())
FLAG_enc = rsa.encrypt(FLAG)
print("Welcome to dream's RSA server")
while True:
print("[1] Encrypt")
print("[2] Decrypt")
print("[3] Get info")
choice = input()
if choice == "1":
print("Input plaintext (hex): ", end="")
pt = bytes_to_long(bytes.fromhex(input()))
print(rsa.encrypt(pt))
elif choice == "2":
print("Input ciphertext (hex): ", end="") #2번을 누르고 플래그 값이나 암호문보다 값이 작은 N을 입력하면 치트를 쓰지말라고 한다
ct = bytes_to_long(bytes.fromhex(input()))
if ct == FLAG_enc or ct > rsa.N:
print("Do not cheat !")
else:
print(rsa.decrypt(ct))
elif choice == "3": #3번을 누르면 공개키 (E,n)과 암호문을 준다.
print(f"N: {rsa.N}")
print(f"e: {rsa.e}")
print(f"FLAG: {FLAG_enc}")
else:
print("Nope")
이런식으로 운영되는 방식이였다
근데 공개키로 평문을 암호문으로 만들지 않나? 그럼 어떻게 공격하지.. 싶었는데 찾아보니 선택 암호문 공격 (CCA) 를 알아야한다
선택 암호문 공격은 임의로 선택된 암호문과 일치하는 평문으로부터 암호키를 알아내기 위해 시도하는 공격이다. 즉 원하는 암호문을 복호화해주는 경우 사용할 수 있는 공격 방법이다. RSA에서 쓰이는 경우는 "곱셈에 대한 준동형사상(Homomorphism)의 성질"이라고 한다
곱셈에 대한 준동형사상은 다음 식으로 정리될 수 있으며, 이를 이용하면 다음과 같은 공격이 가능해진다.
암호화된 flag가 있고, 암/복호화 기능이 존재한다고 가정하면
1. 숫자 2를 암호화 한다.
2. 숫자 2를 암호화 한 값 * flag를 암호화 한 값을 곱한다.
3. 결과 값을 숫자 2로 나누면 flag가 된다.
덧붙여, 이 방법을 막기 위해서 고안된 방법은 RSA-OAEP를 제안하였다.
RSA-OAEP는 암호화 단계에서 평문 해시값과 정해진 개수의 '0' 등으로 만들어진 "인증 정보"를 평문의 앞에 추가하고 RSA로 암호화한다.
이후 복호화단계에서 이 "인증 정보"가 보이지 않을 경우 평문을 알고 있는 사람이 만든 암호문이 아니라고 판단하여 복호화를 진행하지 않는다.
실제로 RSA-OAEP에서는 난수를 이용하는 등 암호문이 매번 다른 패턴이 되도록 하여 안전성을 높였다
즉, 이 문제에서는
2^e * flag_enc 를 [2] Decrypt에 넣어 1/2 해주면 된다.
내가 참고한 blog에서는 pwn 툴을 사용했는데 처음 써봐서 베끼는 수준 이였지만..
이 문제를 통해 pwn툴의 이해와 CCA의 개념을 이해했다
from pwn import *
from Crypto.Util.number import *
p = remote('host3.dreamhack.games', 21275) # 서버랑 연결
p.sendlineafter('info\n', '3') #기다렸다가, 3번째 메뉴 선택
p.recvuntil('N: ') # N값 받아오기(개행문자 제거해 정수로 변환한 값을 n에 저장)
n = int(p.recvline()[:-1])
p.recvuntil('e: ') # e값 받아오기 (개행문자 제거해 정수로 변환한 값을 e에 저장)
e = int(p.recvline()[:-1])
p.recvuntil('FLAG: ') # FLAG값 받아오기(개행문자 제거해 정수로 변환한 값을 flag_enc에 저장)
flag_enc = int(p.recvline()[:-1])
exploit_flag = (pow(2,e) * flag_enc) % n # exploit_flag에 2^e * flag_enc % n 값을 저장
p.sendlineafter('info\n', '2') # 2번째 메뉴 선택
p.sendlineafter('hex): ', hex(exploit_flag)[2:])# exploit_flag값을 16진수로 변환해 전송 16진수 변환시 0x가 붙으므로 [2:]로 0x를 제거
verflag = int(p.recvline()[:-1]) # verflag에 받아온 값을 정수로 변환해 저장
flag = verflag // 2 # verflag값을 2로 나눈 몫을 flag에 저장
log.info("REAL FLAG: " + str(long_to_bytes(flag))) # flag값을 바이트로 변환해 출력
