[Cryptography] Textbook-RSA

문제 : https://dreamhack.io/wargame/challenges/131

Textbook-RSA

Code Analysis

RSA : RSA 암호화 및 복호화 처리

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)

 

init 

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)

• getStrongPrime(512) : 512비트의 강력한 소수를 얻는 함수
• p, q를 512비트의 강력한 소수로 설정
• N = p * q > 공개키
• e = 0x10001(65537) > 공개키
• d = 1/e > 개인키

def encrypt(self, pt):
        return pow(pt, self.e, self.N)

• return \(pt^e (mod\ N)\)

def decrypt(self, ct):
        return pow(ct, self.d, self.N)

• return \(ct^d (mod\ N)\)

rsa = RSA()
FLAG = bytes_to_long(open("flag", "rb").read())
FLAG_enc = rsa.encrypt(FLAG)

• RSA 인스턴트를 생성
• FLAG : 이진 데이터
• FlAG_enc에 RSA로 FLAG를 암호화하여 저장

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. 사용자에게 평문을 입력받음 → 암호화하여 출력
2. 사용자에게 암호문을 입력받음 → RSA로 복호화하여 출력 (*FLAG_enc와 같거나 N보다 큰 경우 안됨)
3. RSA키 및 FLAG_enc 값을 출력함 

Exploit

CCA(Chosn Ciphertext Attack) 선택 암호문 공격

곱셈에 대한 준동형사상의 성질 : \((r\times m)^e = (r)^e \times (m)^e\)

 

$$ (2^e \times {flag})^d = 2^{ed} \times {flag}^d $$

* \(d = 1/e\) 이므로 \(2^{ed} = 2\)

이 식을 복호화 한 후 /2 하면 flag를 얻을 수 있음

Exploit Code

from pwn import remote
from Crypto.Util.number import long_to_bytes
import logging

# Set up logging
logging.basicConfig(level=logging.INFO)
log = logging.getLogger(__name__)

# Connect to the remote host
p = remote("host3.dreamhack.games", 21969)

# Send the request for information
p.sendlineafter('info\n', "3")

# Receive and parse N, e, and FLAG_enc
p.recvuntil("N:")
n = int(p.recvline()[:-1]) #N 얻기

p.recvuntil("e:")
e = int(p.recvline()[:-1]) #e 얻기

p.recvuntil("FLAG:")
flag_enc = int(p.recvline()[:-1]) #flag_enc 얻기

# Calculate the exploit flag
exploit_flag = (pow(2, e) * flag_enc) % n #암호화된 값에 2^e를 곱한 후 mod 2
log.info("Exploit flag: " + str(exploit_flag))

# Send the request to decrypt the exploit flag
p.sendlineafter("info\n", "2")
p.sendlineafter("(hex): ", hex(exploit_flag)[2:]) #exploit flag를 복호화

# Receive and parse the decrypted flag
double_flag = int(p.recvline()[:-1]) 
flag = double_flag//2 #2로 나누어줌
flag_bytes = long_to_bytes(flag)
flag_str = flag_bytes.decode('utf-8')

# Print the decrypted flag
print("Decrypted flag: ", flag_str)

# Close the connection
p.close()