[42CTF] Very Short Crypto 풀이

Background

---

공개 키 관련 문제이다.

 

download시

1811ca69474cf7dce163acd43dc99520d94c98de9fab1da5285c53795bcc77451af202566bb90aad9921448ce1eec7b26e1b67d0c6b89a26ccc87f925d19db825f36d4cbc9077eaa2b17219ed24260d02f6af94a56f7c14980e27cfa38e3710dcfcbd1944ed7370032432504347c82ce9e9d

ciphertext와

 

pub.pem파일이 주어진다. 이를 가지고 ciphertext를 복호화한다.

 

풀이

---

이 문제를 올리는 이유로는 RSA를 거의 풀어보지 않기도 했고 이런 방식을 사용할 수 있다는 점에서 올린다.

 

https://xerxes-break.tistory.com/341

RSA 공격법

RSA 공격법에 대해서는 해당 게시물이 잘 정리되어있었는데 여기서 하나를 보고 그거에 대해서 더 자세히 찾아보면 좋다.

 

우선 pub.pem에서 공개키 e와 N값을 알아내야한다. 여기서는 저번 https://neutrinox4b1.github.io/blog/2023/crack_the_key/

Crack-the-key | Neutrinox4b1 ⚛

 

DAMCTF에서 .pem파일에서 e와 N을 얻어내는 법을 배웠다.

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.backends import default_backend
from base64 import b64decode, b64encode
from sympy.ntheory.factor_ import totient
from Crypto.Util.number import *
from gmpy2 import *

pub_file = './pub.pem'
flag_file = './ciphertext'

with open(pub_file, 'rb') as pubf:
	pub_key = serialization.load_pem_public_key(pubf.read(), backend=default_backend())
with open(flag_file, 'r') as ff:
	ciphertext = ff.read()
n = pub_key.public_numbers().n
e = pub_key.public_numbers().e
c = bytes_to_long(bytes.fromhex(ciphertext))

 

위에 필요없는 모듈들도 있기는 하지만 cryptography.hazmat.~ 에서 이것저것 필요한 모습이다.

키를 읽어들이고 n, e, c를 구한다.

이를 출력해보면

 

 

e가 3인 상황을 볼 수 있다.

e가 3인 경우에, 그리고 평문의 길이가 매우 짧을 경우 일반적으로 낮은 지수 공격이 사용된다.

 

낮은 지수 공격의 핵심은 e가 매우 작아서(보통 3) 제곱을 하더라도 의미가 없다는 것이다. 따라서 암호문에 세제곱근을 씌우면 평문을 얻을 수 있다.

 

 

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.backends import default_backend
from sympy.ntheory.factor_ import totient
from Crypto.Util.number import *
from gmpy2 import *

pub_file = './pub.pem'
flag_file = './ciphertext'

with open(pub_file, 'rb') as pubf:
	pub_key = serialization.load_pem_public_key(pubf.read(), backend=default_backend())
with open(flag_file, 'r') as ff:
	ciphertext = ff.read()
n = pub_key.public_numbers().n
e = pub_key.public_numbers().e
c = bytes_to_long(bytes.fromhex(ciphertext))

print(long_to_bytes(int(pow(c, 1/3))))

 

처응에는 단순히 1/3을 pow를 사용하여 씌웠는데 일부만 출력되었다.

 

제곱근을 계산하는 과정에서 오차가 있으리라 생각하고 이를 개선하기 위한 방법을 알아보다가.

 

gmpy에서 percision을 크게 하면 정밀도를 높일 수 있다고 한다.

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.backends import default_backend
from sympy.ntheory.factor_ import totient
from Crypto.Util.number import *
from gmpy2 import *

pub_file = './pub.pem'
flag_file = './ciphertext'

with open(pub_file, 'rb') as pubf:
	pub_key = serialization.load_pem_public_key(pubf.read(), backend=default_backend())
with open(flag_file, 'r') as ff:
	ciphertext = ff.read()
n = pub_key.public_numbers().n
e = pub_key.public_numbers().e
c = bytes_to_long(bytes.fromhex(ciphertext))

with local_context() as lcx:
    lcx.precision = 500
    print(long_to_bytes(int(cbrt(c))))

 

정밀도를 약 500정도로 크게 하여 cbrt(세제곱근)을 씌웠다.

완벽하게 잘 나온다.