[Dreamhack][CryptoPS] Textbook-RSA

1.문제 분석

• RSA 암호를 이해하는 문제
• 선택 암호문 공격을 사용하는 문제

---

2. 기본 아이디어

1. 주어진 n, e, flag를 통해 decrypt하는 방법을 찾는다.
2. FLAG가 아닌 임의의 암호문에 대해 평문으로 바꿔주는 점을 이용해본다.

---

3.문제 풀이

 

이 문제는 파이썬 코드를 제공한다.

 

#!/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="")
        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":
        print(f"N: {rsa.N}")
        print(f"e: {rsa.e}")
        print(f"FLAG: {FLAG_enc}")

    else:
        print("Nope")

 

코드를 간단하게 설명하면 1번은 Encrypt 2번은 Decrypt 3번은 n, e, flag를 보여준다.

 

입력은 hex로 받는 것을 볼 수 있다.

 

우선 flag를 decrypt하는 것은 금지된 것을 볼 수 있으니 flag에 다른 값을 첨가하거나 flag의 길이를

 

늘리는 방법이 있겠다. 하지만 RSA의 경우 AES와 같이 padding을 사용하는 개념이 아니므로

 

값의 첨가는 적절하지 않다. 따라서 flag를 2배 해준 값을 decrypt하고 다시 반으로 나눠주자.

 

위 생각을 정리해보면 다음과 같다.

[1]. 2를 암호화 -> 2^e mod n을 얻기
[2]. flag_enc 와 2_enc를 곱셈 -> (2 * flag_enc)^e mod n을 얻기
[3]. [2]에서 구한 값을 복호화 -> (2 * flag_enc)^e^d mod n -> 2 * flag

 

이제 익스플로잇 코드를 짜보면

 

from pwn import *
from Crypto.Util.number import getStrongPrime, long_to_bytes, inverse


r = remote("host3.dreamhack.games", 9479)

#Get Data
r.recvuntil("[3] Get info")
r.sendline("3")
r.recvuntil("N: ")
n = int(r.recvline())
r.recvuntil("e: ")
e = int(r.recvline())
r.recvuntil("FLAG: ")
flag_enc = int(r.recvline())

#Decrypt
#Choosen Ciphertext Attack (2^e * flag_enc)^d = 2^ed * flag = 2 * flag mod n

cca_flag = (pow(2, e) * flag_enc) % n

r.recvuntil("[3] Get info")
r.sendline("2")
r.sendlineafter("Input ciphertext (hex): ", hex(cca_flag)[2:])
flag = int(r.recvline())

flag = flag // 2

print(str(long_to_bytes(flag)))

r.interactive()

 

cca_flag를 보면 2^e 값과 flag_enc값을 곱해 mod n을 해준 것을 볼 수 있고

 

hex값으로 보낸 cca_flag를 디코딩해 2로 나눠준 것을 볼 수 있다.

 

문제 코드에서는 bytes를 long으로 바꿨으니 이번엔 반대로해서 flag를 문자열로 출력해준다.