Alexctf / poor rsa (공개키를 이용한 rsa 개인키 복호화)

date : `17.02

This time Fady decided to go for modern cryptography implementations, He is fascinated with choosing his own prime numbers, so he picked up RSA once more. Yet he was unlucky again!

이전과 같은 rsa 암호 문제이지만 제공되는 p, q값이 없으며, 공개키 e만 주어졌다. 문제는 숫자값으로 주어진 것이 아닌 키 형태로 주어졌기 때문에 이를 다시 숫자화 시켜야 한다.

이는 다음 명령으로 할 수 있다.

openssl rsa -text -inform PEM -in key.pub -pubin -modulus

text : key의 modulos, exponent 값을 text 형태로 출력한다.

inform PEM : 인코딩 형태가 PEM임을 의미한다. (der도 존재)

in key.pub -pubin : key 파일을 넣어 주는데 public key임을 명시해준다.

modulus : modulus값을 보기 편하게 출력.

이와 같이 하면 다음 값을 얻을 수 있다.

Public-Key: (399 bit)

Modulus:

    52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:

    77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:

    89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:

    ba:5c:32:42:43

Exponent: 65537 (0x10001)

Modulus=52A99E249EE7CF3C0CBF963A009661772BC9CDF6E1E3FBFC6E44A07A5E0F894457A9F81C3AE132AC5683D35B28BA5C324243

modulos n값, exponent값을 얻을 수 있다. 이제 이 값을 이용해서 값을 구하면 된다. 단, 문제는 아직 p, q값을 모른다.

p,q값은 factordbㅇ서 조회를 하면 된다고 한다.

http://www.factordb.com/index.php?query=833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019

p =  863653476616376575308866344984576466644942572246900013156919

q =  965445304326998194798282228842484732438457170595999523426901값을 주고 복호화를 해주면 된다.

public key를 만들었으므로 이번에는 이 값들을 사용하여 private key를 만들어 주면 된다.

key생성은 rsatool.py를 사용한다.

https://github.com/ius/rsatool

python rsatool.py -p 863653476616376575308866344984576466644942572246900013156919 -q 965445304326998194798282228842484732438457170595999523426901 -f PEM -o privatekey.pem

위 명령을 주면 p, q값을 가지고 private key가 생성이 된다. 이제 key를 이용해서 풀어주면 된다.

private key가 생성되었으므로 이 키를 가지고 본래의 암호문을 해독하면 된다. 사용된 key소스는 다음과 같다.

1 2 3 4 5 6 7 8

def rsa_k(key, c):     from Crypto.PublicKey import RSA     tmp = open(key,'r').read()     rsakey = RSA.importKey(tmp)     m  = rsakey.decrypt(c)     return m   rsa_k.__doc__="return m\nrefer : https://isitdtu.blogspot.kr/2017/02/alexctf-cr4poor-rsa.html"

cs

1 2 3 4 5 6 7

import base64 from my import rsa_k   data = base64.b64decode(open('flag.b64','r').read()) rsa_k('privatekey.pem',data)   ## '\x02\x9e&\xded\xa0\x96#H\x8au6L\xdb\xae\x84\x89:\x00ALEXCTF{SMALL_PRIMES_ARE_BAD}\n'

cs

Flag : ALEXCTF{SMALL_PRIMES_ARE_BAD}

privatekey.pem

 

rsatool.py