sexy소수를 활용한 RSA 문제

#sexy소수 #sexyRSA #SECCON2021

---

SECCON 2021 SPEEDRUN 챌린지에 출제된 sexyRSA 문제이다.

n = 0xe72988e811f04091c3291ac28f1e8332193187f3dc5af01579c36badb06671aa9a9543aa07eba8cdab36d787f1ff98a06db995c43cd5c63581ce050e0b9ba856634dabfaf8c7f271fbd026edd6ea1257b16013a526e0581a688cc6a335e7ee4c1b0633f0532d3d0824824195b6b249c70cf0e458609efc01a6575f084e6de53b
e = 0x10001
c = 0x6fadd5d7095bd6f45de69bb4e76080e0ea5f8c5a159de10663133e585b71ae580b99b3e0a8e047a9c51c8091a6b33b01c9ab95668794c3acfb084e939a04cb151757c3b2522da99e03f83e205c7c701066d69b120ca17fcf59061c078d9099e5f4bf6dd6dab206418527035f2c1096861c2896327977ac88c2728faa7504d879

위에 제시 된 c 값을 복호화 하여 플래그를 인증하는게 목표이다.

# chall.py
from Crypto.Util.number import getPrime, isPrime
import os

def getSexyPrime(n=512):
    # Sexy prime: https://en.wikipedia.org/wiki/Sexy_prime
    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p, q = getSexyPrime()
    n = p * q
    e = 65537

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"c = 0x{c:x}")

처음에 제시된 n, e, c 값은 위 소스에 의해 생성이 되었다.

이 때 주어진 힌트가 sexyPrime 에 대한 위키 링크가 주어졌다.

요약하자면, 소수 중에 (7,13) 과 같이 두 수 간의 6 차이가 나는 소수 쌍을 sexyPrime 이라고 말한다.

이 sexyPrime 이 쓰인 부분은

def getSexyPrime(n=512):
    # Sexy prime: https://en.wikipedia.org/wiki/Sexy_prime
    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6

p, q 값을 리턴하는 getSexyPrime 함수이다.

결론적으로 딱봐도 512 비트 소수안에서 주어진 n 값을 형성하는 sexyPrime p, q 값은 그리 많지 않을 것이다.

단순히 브루트포싱으로 풀어보았는데, 시간이 의외로 오래걸려서 이진탐색 방식으로 해보았다.

# dec.py
from Crypto.Util.number import getPrime, isPrime, inverse, long_to_bytes
n=0xe72988e811f04091c3291ac28f1e8332193187f3dc5af01579c36badb06671aa9a9543aa07eba8cdab36d787f1ff98a06db995c43cd5c63581ce050e0b9ba856634dabfaf8c7f271fbd026edd6ea1257b16013a526e0581a688cc6a335e7ee4c1b0633f0532d3d0824824195b6b249c70cf0e458609efc01a6575f084e6de53b
c=0x6fadd5d7095bd6f45de69bb4e76080e0ea5f8c5a159de10663133e585b71ae580b99b3e0a8e047a9c51c8091a6b33b01c9ab95668794c3acfb084e939a04cb151757c3b2522da99e03f83e205c7c701066d69b120ca17fcf59061c078d9099e5f4bf6dd6dab206418527035f2c1096861c2896327977ac88c2728faa7504d879
# binary search
low=0
high=n
while(high - low > 1):
    mid = (high + low) // 2
    if(mid*(mid+6) >= n):
        # 범위 줄임
        high = mid
    else:
        low = mid

p = high
q = high + 6
e=65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag=pow(c,d,n)
print(long_to_bytes(flag))

플래그가 나온다.