[Dreamhack] Textbook-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")

문제에서 제공된 코드이다.

뭐가 뭔지 하나도 모르겠어서 댓글을 힌트로 CCA에 대해 검색했다.

 

* CCA (Chosen-Ciphertext Attack)

- 암호문(ciphertext)을 선택하는 공격자가 선택한 암호문을 이용하여 평문(plaintext)을 알아내려는 공격 기법

- 암호화된 데이터와 대응되는 평문을 구하거나 암호 시스템의 보안을 약화시키는 데 사용

- 공격자가 암호문을 선택하는 데 제한이 없는 경우에 발생

 

그래서 뭐 어쩌라는거지 싶었는데 다른 블로그에서 adaptive chosen ciphertext attack에 대한 것을 알아냈다.

https://rkm0959.tistory.com/131

 

그러면 이 수식대로 코드를 작성해보자.

서버 출력

e = 65537 
c = 58655659458875025082496462903223362294675135539071575341750661255034321036818812471781452408287863821546096669177908767367440837452175377873107417918305142883378332228935408585029908716934969329454908584430834014183928674334860289787325210389945334058962722058414383046022275491168880439049825046484980839813
N = 108736520004014246713743498956901630403380236057802708074735824499463938902600870863572624893653029702254512478466859300571383788185525668386099816785971289732626760568147370410229625890277846896340056637391749317589226814009648373899548418961740001045700763482451569298808376126727273288700030737729479509081
print(hex((c<<e)%N))

서버에서 출력된 값을 토대로 (2^e)*c (mod N)을 계산했다. 여기서 decrypt 할때  hex 값을 입력받기 때문에 변환을 해줘야한다.

출력된 값을 서버에서 decrypt하면 이렇게 결과값이 나온다. 이 때 우리가 얻은 값은 ((2^e)*c)^d 이다. 

 

from Crypto.Util.number import *

N = 108736520004014246713743498956901630403380236057802708074735824499463938902600870863572624893653029702254512478466859300571383788185525668386099816785971289732626760568147370410229625890277846896340056637391749317589226814009648373899548418961740001045700763482451569298808376126727273288700030737729479509081

dec = 265303025271760754782762668660255715813910508769429152493707039977108929146371416679674

flag= dec>>1
 
print(long_to_bytes(flag))

결과값을 dec에 입력했다. 아까 공식에 따르면 우리가 얻은 값은  ((2^e)*c)^d = 2M =dec 이기 때문에 dec/2을 통해 flag를 얻고 이를 byte로 변환해줬다. (dec를 2로 막 나눠도 되는건지 잘 모르겠다.. 모듈러스 개념이 잘 안 잡혔다..)

그리고 출력해주면 flag를 얻을 수 있다.

 

 

 

* 공부할 것 

https://rkm0959.tistory.com/131 - 해당하는 논문도 읽어보면 좋을 것 같다.

암호론 논문 리딩 #3: Twenty Years of Attacks on the RSA Cryptosystem