[picoCTF 2022] Very Smooth

1. Investigation

Hint#1 : Don't look at me... Go ask Mr. Pollard if you need a hint!

 

문제 설명을 살펴보니 안전한 소수를 까먹었다며 인생을 위험하게 사는게 좋다고 합니다...

힌트#1 에서는 날 보지 말고 Mr. Pollard 에게 힌트를 물어보라네요.

---

2. Solution

먼저 문제에서 제공된 파일들을 각각 확인해봅니다.

>> gen.py

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
    math.gcd = gcd
    math.lcm = lcm

_DEBUG = False

FLAG  = open('flag.txt').read().strip()
FLAG  = mpz(hexlify(FLAG.encode()), 16)
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

e = 0x10001

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) != len(set(q_factors)):
        continue
    factors = p_factors + q_factors
    if e not in factors:
        break

if _DEBUG:
    import sys
    sys.stderr.write(f'p = {p.digits(16)}\\n\\n')
    sys.stderr.write(f'p_factors = [\\n')
    for factor in p_factors:
        sys.stderr.write(f'    {factor.digits(16)},\\n')
    sys.stderr.write(f']\\n\\n')

    sys.stderr.write(f'q = {q.digits(16)}\\n\\n')
    sys.stderr.write(f'q_factors = [\\n')
    for factor in q_factors:
        sys.stderr.write(f'    {factor.digits(16)},\\n')
    sys.stderr.write(f']\\n\\n')

n = p * q

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')

대략적으로 살펴보면 소수 p, 소수 q 를 생성하는데 소수를 계속 곱해서 만든 tmpp(= p1 * p2 * ... * pn) 에 1 을 더해서(tmpp + 1) 해당 수가 소수인지 확인(is_prime)하고 소수이면 p 에 저장하여 소인수 목록(p_factors)과 함께 반환하고 있다는 것을 알 수 있습니다.

 

또한 그렇게 생성된 p, q 값으로 n = p * q 를 계산하는 등 RSA 암호화 기법을 사용하고 있음을 알 수 있습니다.

 

>> output.txt

n = e77c4035292375af4c45536b3b35c201daa5db099f90af0e87fedc480450873715cffd53fc8fe5db9ac9960867bd9881e2f0931ffe0cea4399b26107cc6d8d36ab1564c8b95775487100310f11c13c85234709644a1d8616768abe46a8909c932bc548e23c70ffc0091e2ed9a120fe549583b74d7263d94629346051154dad56f2693ad6e101be0e9644a84467121dab1b204dbf21fa39c9bd8583af4e5b7ebd9e02c862c43a426e0750242c30547be70115337ce86990f891f2ad3228feea9e3dcd1266950fa8861411981ce2eebb2901e428cfe81e87e415758bf245f66002c61060b2e1860382b2e6b5d7af0b4a350f0920e6d514eb9eac7f24a933c64a89
c = 671028df2e2d255962dd8685d711e815cbea334115c30ea2005cf193a1b972e275c163de8cfb3d0145a453fec0b837802244ccde0faf832dc3422f56d6a384fbcb3bfd969188d6cd4e1ca5b8bc48beca966f309f52ff3fc3153cccaec90d8477fd24dfedc3d4ae492769a6afefbbf50108594f18963ab06ba82e955cafc54a978dd08971c6bf735b347ac92e50fe8e209c65f946f96bd0f0c909f34e90d67a4d12ebe61743b438ccdbcfdf3a566071ea495daf77e7650f73a7f4509b64b9af2dd8a9e33b6bd863b889a69f903ffef425ea52ba1a293645cbac48875c42220ec0b37051ecc91daaf492abe0aaaf561ffb0c2b093dcdabd7863b1929f0411891f5

output.txt 에서는 Public Modulus 인 n 값과 암호문인 c 를 제공해주고 있습니다.

 

문제의 제목과 소스코드를 보고 딱 알 수 있었던 것은 Public Modulus 인 n 의 소인수인 p, q 가 각각 p - 1, q - 1 에 대하여 Smooth Integer 이라는 것 이었습니다.

 

Smooth Integer 란?

Smooth Integer 라고 하는 개념이 있습니다. B-smooth integer는 그 수를 소인수분해 했을 때, 소인수 중에 B 보다 큰 소인수가 없다는 의미입니다. 예를 들어, 1620 은 2^2 × 3^4 × 5 로 가장 큰 소인수가 5 이므로, 5-smooth integer 입니다.

http://www.secmem.org/blog/2019/10/20/Smooth-number-and-Factorization/

 

쉽게 말해 어떠한 정수 N 이 Smooth 하다고 하면 N 의 소인수가 매우 많고 작은 소수들의 곱으로 이루어져 있다는 말입니다.

 

특이하게도 이러한 수에 적용되는 소인수분해 알고리즘이 있는데 그것이 바로 Pollard’s p-1 method 입니다.

(https://ko.wikipedia.org/wiki/폴라드의_P-1_알고리즘)

(Pollard 교수에게 물어보라는 힌트#1 과도 일맥상통합니다)

 

Pollard’s p-1 method 는 요약하자면 어떠한 합성수 N 이 Smooth Integer 로 이루어져 있을 때 합리적인 시간 내에 소인수분해(Factorization)가 가능한 기법이라 할 수 있습니다.

(RSA 의 강점은 Public Modulus 이자 합성수인 N 이 소인수분해가 거의 불가능하다는 것에 있음.)

(하지만 위처럼 개발자가 잘못된 방법으로 소수 p, q 를 선택한다면 소인수분해가 가능해져 큰 문제를 야기할 수 있음.)

 

위 문제의 소스코드에서도 보았듯이 소수 p 자체는 굉장히 크고 is_prime 함수로 소수임을 확인했기 때문에 약수가 1 과 자기자신인 p 밖에 존재하지 않습니다.

 

하지만 소수 p 는 p = tmpp + 1 로 이루어져 있고 tmpp 는 tmpp = (p1 * p2 * ... * pn) 과 같이 작은 소수들의 곱으로 이루어져 있기 때문에 (Smooth 하다는 뜻) p = tmpp + 1 에서 1 을 좌항으로 옮겨 p - 1 = tmpp 와 같은 식이 만들어지고 p - 1 = (p1 * p2 * ... * pn) 와 같이 소인수들의 곱으로 표현이 가능해집니다.

(쉽게 말해 소인수분해 가능해진다는 뜻)

 

이것은 소수 q 의 경우도 마찬가지이고 여기에 Pollard’s p-1 method 를 적용하여 주어진 n 값을 소인수분해한 뒤 개인키 d 값을 계산해 암호문 c 를 복호화하면 Flag 를 획득할 수 있게 됩니다.

 

>> Very-Smooth-sol.py

# <http://www.secmem.org/blog/2019/10/20/Smooth-number-and-Factorization/>

import math

N = 0xe77c4035292375af4c45536b3b35c201daa5db099f90af0e87fedc480450873715cffd53fc8fe5db9ac9960867bd9881e2f0931ffe0cea4399b26107cc6d8d36ab1564c8b95775487100310f11c13c85234709644a1d8616768abe46a8909c932bc548e23c70ffc0091e2ed9a120fe549583b74d7263d94629346051154dad56f2693ad6e101be0e9644a84467121dab1b204dbf21fa39c9bd8583af4e5b7ebd9e02c862c43a426e0750242c30547be70115337ce86990f891f2ad3228feea9e3dcd1266950fa8861411981ce2eebb2901e428cfe81e87e415758bf245f66002c61060b2e1860382b2e6b5d7af0b4a350f0920e6d514eb9eac7f24a933c64a89
B = 70000   # This value should be modified.

# Prime
primes = []
for i in range(2, B + 1):
    flag = True
    for j in primes:
        if j * j > i:
            break
        if i % j == 0:
            flag = False
            break
    if flag:
        primes.append(i)

# Pollard's p-1 algorithm
a = 2
for p in primes:
    wow = pow(p, math.floor(math.log(B, p)))
    a = pow(a, wow, N)

print(math.gcd(a - 1, N))
# 177529604771775811447794627528898905563608127308618713400260159684003628121897638346581772088147960905570447556763891720452738611287634839201158386379116429397697859892035253074680507674006763427672353958542251411700851999453703543179036524728177137039687762641769500501195739670681098180171316381127270595227
# Modulus N is factorized!!!

p = 177529604771775811447794627528898905563608127308618713400260159684003628121897638346581772088147960905570447556763891720452738611287634839201158386379116429397697859892035253074680507674006763427672353958542251411700851999453703543179036524728177137039687762641769500501195739670681098180171316381127270595227
q = N // p
assert p*q == N

e = 0x10001

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

ct = 0x671028df2e2d255962dd8685d711e815cbea334115c30ea2005cf193a1b972e275c163de8cfb3d0145a453fec0b837802244ccde0faf832dc3422f56d6a384fbcb3bfd969188d6cd4e1ca5b8bc48beca966f309f52ff3fc3153cccaec90d8477fd24dfedc3d4ae492769a6afefbbf50108594f18963ab06ba82e955cafc54a978dd08971c6bf735b347ac92e50fe8e209c65f946f96bd0f0c909f34e90d67a4d12ebe61743b438ccdbcfdf3a566071ea495daf77e7650f73a7f4509b64b9af2dd8a9e33b6bd863b889a69f903ffef425ea52ba1a293645cbac48875c42220ec0b37051ecc91daaf492abe0aaaf561ffb0c2b093dcdabd7863b1929f0411891f5

flag = pow(ct, d, N)
flag = bytes.fromhex(format(flag, 'x'))
print(flag)
# b'picoCTF{94****17}'

 

🚩 FLAG : picoCTF{94****17}

---