CTF 문제에 RSA가 나와서 복습 겸 간단히 정리한다.

---

RSA

특징

• 공개키 알고리즘으로 사설키, 공개키로 구분하여 사용
• 공개키로 암호화할 경우 사설키로 복호화, 사설키로 암호화할 경우 공개키로 복호화가 가능
• 소수의 곱으로 이루어진 숫자를 소인수분해하는 것이 어렵다는 점에서 착안

키 생성

공개키

1.소수 p,q에 대한 곱 N이 필요하다.
2.Φ(N)이 필요하다. 오일러 파이함수로, (p-1)(q-1)로 구한다.
3.Φ(N)보다 작으면서 서로소인 e를 선택한다.

개인키

1.1 = ed * Mod(Φ(N))인 d를 선택한다.(ed를 Φ(N)로 나눴을 때 나머지가 1인 숫자)

예시

소수 13, 17이 있다. N은 13*17 = 221이다.
Φ(N)는 12*16 = 192 이다.
e는 5로 정한다.
d는 77로 정한다.((77*5) = 385, 385%192 = 1)

암호화

메시지를 m이라고 하자. m은 N보다 작아야 한다.

1.Hello World!를 숫자 m으로 변환한다.
2.m^e Mod N인 암호화된 숫자 c를 구한다. (m을 e제곱한 값을 N으로 나눴을 때 나머지 값을 구하는 것이다.)

c가 암호화된 값이다.

예시

m = 8이라고 가정한다.

8^5 % 221 = 60

c는 60이 되는 것이다.

복호화

1.c^d Mod N을 계산해 m을 구한다.
2.m을 변환법을 통해 Hello World!로 변환한다.

한 마디로, 암호화와 같은 과정을 복호화 키 d로 하는 것이다.

예시

다음을 계산하면

60^77 % 221

m의 값인 8이 나온다.

---

부록

RsaCtfTool

작은 수의 N, e, c가 있을 때 이것을 크랙하는 도구이다.
다음 링크에서 확인할 수 있다.

https://github.com/Ganapati/RsaCtfTool

CTF에 종종 nec를 제공하는 형태의 문제가 출제되는데 그 때 활용할 수 있다.

주의할 점은 python3로 실행해야 한다.

python3 RsaCtfTool.py -n 57772961349879658023983283615621490728299498090674385733830087914838280699121 -e 65537 --uncipher 36913885366666102438288732953977798352561146298725524881805840497762448828130

[*] Testing key /tmp/tmpc2m7ehf6.
Can't load smallfraction because sage is not installed
Can't load boneh_durfee because sage is not installed
Can't load ecm2 because sage is not installed
Can't load qicheng because sage is not installed
Can't load ecm because sage is not installed
Can't load roca because sage is not installed
[*] Performing pollard_p_1 attack on /tmp/tmpc2m7ehf6.
[*] Performing partial_q attack on /tmp/tmpc2m7ehf6.
[*] Performing primefac attack on /tmp/tmpc2m7ehf6.
[*] Performing cube_root attack on /tmp/tmpc2m7ehf6.
[*] Performing noveltyprimes attack on /tmp/tmpc2m7ehf6.
[*] Performing fermat attack on /tmp/tmpc2m7ehf6.
[*] Performing comfact_cn attack on /tmp/tmpc2m7ehf6.
[*] Performing mersenne_primes attack on /tmp/tmpc2m7ehf6.
[*] Performing siqs attack on /tmp/tmpc2m7ehf6.
[!] Yafu SIQS is not working.
[*] Performing pastctfprimes attack on /tmp/tmpc2m7ehf6.
[*] Performing smallq attack on /tmp/tmpc2m7ehf6.
[*] Performing factordb attack on /tmp/tmpc2m7ehf6.

Results for /tmp/tmpc2m7ehf6:

Unciphered data :
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00tjctf{BOLm1QMWi3c}'