[Dreamhack] Textbook-RSA 문제풀이

Description

RSA 요약

1. 적당한 소수 p, q를 찾습니다.
2. N = pq
3. 오일러 피함수 phi에 대해 phi(N) = (p-1)(q-1)입니다.
4. 1 < e < phi(N) 를 만족하는 phi(N)와 서로소 e 찾습니다. (코드에서는 소수 0x10001로 강제지정)
5. e * d mod phi(N) ≡ 1을 만족하는 d를 찾습니다. 코드에서는 인버스함수를 사용합니다.
6. 평문 m의 암호화는 c≡m^e%N으로 합니다.
7. 암호문 c의 해독은 m≡c^d%N으로 합니다.

https://m.blog.naver.com/errorsoft666/221557573037

[보안/암호] RSA 암호화 복호화 (공개키 암호 시스템)

문제에 주어진 코드는 다음과 같습니다.

#!/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")

 

self.p = getStrongPrime(512)

self.q = getStrongPrime(512) 에서는 512bit짜리 랜덤한 강한 소수를 생성합니다.

https://pythonhosted.org/pycrypto/Crypto.Util.number-module.html

Crypto.Util.number

self.n은 Modulus, self.e는 공개 지수(public exponent), self.d는 비밀 지수(private exponent)를 나타냅니다.

self.e는 공개키 값으로 65537을 사용합니다.

이는 RSA의 키 생성 과정에서의 변수들입니다.(RSA에서 d ≡ e^-1(mod(phi(n))이고 phi(n)는 p x q - p - q + 1 = (p-1)(q-1)이기 때문에 self.d = inverse(self.e, self.N - self.p - self.q + 1)입니다. 또한 n = p x q이므로 self.N이 사용된 것입니다.)

 

encrypt함수는 pt^self.e % self.N을 수행하여 값을 반환합니다.(암호화)

decrypt함수는 ct^self.d % self.N을 수행하여 값을 반환합니다.(복호화)

https://www.programiz.com/python-programming/methods/built-in/pow

Python pow() (With Examples)

rsa = RSA()

RSA() 클래스 함수를 실행합니다.

 

FLAG = bytes_to_long(open("flag", "rb").read())

FLAG_enc = rsa.encrypt(FLAG)

flag파일을 읽어들어서 rsa.encrypt를 통해 flag를 암호화합니다.

 

[1] Encrypt에서는 16진수 값을 입력받고 이를 rsa의 encrypt를 통해 암호화합니다.

[2] Decrypt에서는 16진수 값을 입력받고 이를 rsa의 decrypt를 통해 복호화합니다. 입력값으로 Flag를 암호화한 값을 넣거나 n보다 더 큰 값이면 복호화되지않습니다.

[3]현재 N, e, 암호화된 flag값을 보여줍니다.

 

이 코드를 실행하는 서버를 열어보면 다음과 같습니다.

실행결과

이 문제를 풀기 위해서는 CCA(Chosen Ciphertext Attack, 선택 암호문 공격)를 알아야 합니다.

공격자가 많은 수의 암호문에 대해 평문으로 가지고 상태에서 공격하는 유형입니다. 가장 이상적인 상황은 위와 같이 복호화 프로그램 혹은 도구에 접근할 수 있는 상황입니다. 물론 공격자가 암호키에 대한 정보를 모르는 상태이며 이 공격유형은 가장 강력한 암호 공격 방법이며 암호키를 알아내는 것이 최종 목표입니다. 주로 공개키 암호 알고리즘을 공격할 때 사용합니다.

CCA

2번 옵션에서 flag_enc * 2^e mod N 의 값을 암호문으로 입력해주면 이는 flag_enc의 값과 다를 것이므로 문제없이 이에 대한 평문인 2 * flag를 낼 것입니다. 그 값에 2를 나누면 flag값을 얻을 수 있을 것 입니다. 즉 여기서는 flag_enc에 2^65537을 곱한 값을 복호화하면 flag * 2의 값을 얻을 수 있다는 것 입니다.

위에 연산을 따라간다면 2M ≡ ((2M)^e mod n)^d mod n이므로 M에다가 2^e를 곱해주는 것입니다.

원리는 m을 암호화한 m^e와 2를 암호화한 2^e가 있을 때 둘을 곱하면 (2m)^e이다. 이것을 복호화하면 2m이 되서 2m을 2로 나누면 m을 구할 수 있습니다.

 

Solution 1

from Crypto.Util.number import bytes_to_long, inverse, long_to_bytes

N = int(input('N:') # 옵션 3을 통해 얻은 N값을 복사해서 입력합니다.
e = int(input('e:') # 옵션 3을 통해 얻은 e값을 복사해서 입력합니다.
flag_enc = int(input('flag_enc:')) # 옵션 3을 통해 얻은 암호화된 flag를 입력합니다.

flag_enc_pow = flag_enc * enc(2, e, N) % N # flag_enc * 2^e의 값을 구합니다. 0 ~ N의 범위에 속해야하므로 % N을 합니다.

print('new encrypt: ', long_to_bytes(flag_enc_pow).hex()) # flag_enc_powf를 바이트형식으로 바꾸어 16진수로 변환합니다. 이 값을 복사하여 옵션 2를 통해 복호화합니다.
print('flag: ', long_to_bytes(int(input('give decrypt:'))*inverse(2,N)%N)) # 복호화를 통해 얻은 값(flag *2)를 2로 나눕니다. 2로 나누는 것은 2의 역원을 곱하는 것과 같습니다. 나누기를 사용하면 int가 아닌 float형식이 나올 수 있기에 2의 역원을 곱하는 방식으로 구합니다.

 

Solution 2

Pwntools를 사용해서 문제를 해결할 수 있습니다.

https://hg2lee.tistory.com/entry/Pwntools-사용법

Pwntools 사용법

import os
os.environ['PWNLIB_NOTERM'] = '1' # https://github.com/Gallopsled/pwntools/issues/1671
from pwn import * # Pwntools를 import합니다.

p = remote("host3.dreamhack.games",15675) # 서버에 원격으로 접속합니다.

#get info
p.sendline('3') # 문자열 3을 서버에 전송합니다. 즉 옵션 3을 실행시킵니다.
p.recvuntil("N: ") # "N: "까지 문자열을 읽어드립니다. 
n = int(p.recvline()[:-1]) # 위에서 "N: "까지 읽어들었으니 1480~ 숫자를 쭉 읽어드립니다. [:-1]을 통해 마지막 한 character를 빼고 읽어들이는데 여기서는 개행문자 \n을 빼고 숫자형식의 문자열만 읽어드리게됩니다. 
log.info("N: "+str(n)) # N값을 Log로 출력합니다.
p.recvuntil("e: ") # "e: "까지 문자열을 읽어드립니다.
e = int(p.recvline()[:-1]) # 마찬가지로 개행문자를 제외한 숫자형 문자열만 읽어드리게 됩니다.
log.info("e: "+str(e)) # e값을 Log로 출력합니다.
p.recvuntil("FLAG: ") # "Flag: "까지 문자열을 읽어드립니다.
flag_encrypt = int(p.recvline()[:-1])   # "Flag: " 뒤의 숫자형 문자열을 int형으로 변환하여 대입합니다.


#get 2^d * flag mod n
p.sendline('2') # 문자열 2를 서버에 전송합니다. 즉 옵션 2를 실행시킵니다.(복호화)
p.sendlineafter("(hex): ",hex((2*flag)%n)[2:]) # "(hex): "문자열까지 받은 후 데이터를 전송합니다. 2^d * flag mod n 값을 서버에 보냅니다. 즉 이 값을 복호화합니다. [2:]를 하는 이유는 hex를 통해 16진수 문자열로 변환하게 되면 "0x..."형식으로 앞에 0x가 붙는데 이것을 제외하기 위해서입니다.
pow_2_flag = int(p.recvline()[:-1])#복호화된 값을 읽어들여 int형식으로 저장합니다.

#get 2^d mod n
p.sendline('2')
p.sendlineafter("(hex): ",'02') # "02"를 복호화합니다/
test = int(p.recvline()[:-1]) # 복호화한 결과값을 Int로 저장합니다.

inverse = pow(test,-1,n) # text^(-1)%n
flag = inverse * pow_2_flag %n # ((2^d mod n)^-1) * (2^d * flag mod n) % n => flag

print(bytes.fromhex(hex(flag)[2:]))
p.close()
p.interactive() # 프로그램을 평소대로 실행했던 때 처럼 입출력할 수 있게 유저에게 입출력을 돌려줍니다.