[Dreamhack] safeprime

문제 설명

안전 소수는 2p+1 꼴의 소수로, 아모처럼 사용하지만 않는다면 암호학에서 정말 유용하게 사용할 수 있답니다.

 

소스코드

#prob.py

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG

def getSafePrime(n):
    while True:
        p1 = getPrime(n)
        p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
        p2 = 2*p1 + 1
        if isPrime(p2):
            return p1, p2

while True:
    p1, p2 = getSafePrime(1024)
    q1 = getPrime(1024)
    q2 = getPrime(1024)
    e = 0x10001
    if (p1 - 1) * (q1 - 1) % e == 0:
        continue
    if (p2 - 1) * (q2 - 1) % e == 0:
        continue
    N1 = p1 * q1
    N2 = p2 * q2
    break

FLAG1 = bytes_to_long(FLAG[ : len(FLAG)//2])
FLAG2 = bytes_to_long(FLAG[len(FLAG)//2 : ])

# RSA encryption 1
FLAG1_enc = pow(FLAG1, e, N1)
print(f"{N1 = }")
print(f"{e = }")
print(f"{FLAG1_enc = }")

#RSA encryption 2
FLAG2_enc = pow(FLAG2, e, N2)
print(f"{N2 = }")
print(f"{e = }")
print(f"{FLAG2_enc = }")

 

 

소스코드 분석

1. 라이브러리 임포트 및 초기 설정

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG

 

• Crypto.Util.number: CTF에서 가장 많이 쓰이는 pycryptodome 라이브러리의 모듈
  • getPrime(n): n비트의 랜덤한 소수를 생성.
  • isPrime(n): 숫자가 소수인지 판별 (Miller-Rabin 판정법 등을 사용).
  • bytes_to_long(b): 바이트 문자열을 RSA 연산이 가능한 큰 정수(Integer)로 변환.
• from flag import FLAG: 외부 파일(flag.py)에 저장된 정답 문자열(FLAG)을 가져온다.

 

2. getSafePrime(n) 함수 정의 (핵심 부분)

def getSafePrime(n):
    while True:
        p1 = getPrime(n)
        p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
        
        p2 = 2*p1 + 1
        if isPrime(p2):
            return p1, p2

 

• p1 = getPrime(n) : n비트의 랜덤 소수를 뽑는다.
• p1 = 1229... : 이 문제의 의도된 취약점. 위에서 랜덤하게 뽑은 값을 무시하고, 코드에 하드코딩된 거대한 상수로 p1을 강제 할당한다. 즉, 이 함수는 항상 똑같은 p1과 p2를 반환하게 된다.
• p2 = 2*p1 + 1 : Sophie Germain Prime 관계식. p1이 소수이고 2 x p1 + 1도 소수라면 p2는 Safe Prime이라고 부른다. RSA에서 p-1의 소인수분해 구조를 어렵게 만들어 공격을 막기 위해서 사용되는 개념이다.
• if isPrime(p2): return p1, p2: p2가 소수일 때만 두 값을 반환합니다.

Sophie Germain Prime
어떤 소수 $p$가 있을 때, $2p+1$도 소수가 된다면, 원래의 $p$를 Sophie Germain Prime이라고 한다.
이때 만들어진 큰 소수 $2p + 1$을 암호학에서는 Safe Prime라고 부른다.

RSA와 Diffie-Hellman 알고리즘을 공격하는 특정 수학적 기법들을 무력화시킨다.
대표적인 예시로, $p-1$이 작은 소인수들로만 구성되어있으면 아주 쉽게 뚫리는 공격법인 Pollard's $p-1$ 알고리즘을 방어할 수 있다.

우리가 RSA 소수 $q$를 고를 때, Safe Prime $2p+1$을 골랐다고 가정해보자. ($q = 2p+1$)
그럼 공격자는 $q-1$을 계산해볼 것이다.
$q-1 = (2p+1) -1 = 2p$

- 공격자는 $q-1$을 소인수분해 한다.
- 결과는 $2$와 $p$가 나온다.
- 그런데 여기서 $p$도 Sophie Germain Prime이다. 게다가 $q$의 절반에 가까운 매우 큰 수이다.
- 결론적으로 $q-1$이 작은 소인수들의 곱이 아니라 거대한 소수 $p$를 포함하고 있으므로 Pollard's p-1 공격이 통하지 않게 된다. 

 

 

3. RSA 키 생성 루프

while True:
    p1, p2 = getSafePrime(1024)
    q1 = getPrime(1024)
    q2 = getPrime(1024)
    e = 0x10001
    
    if (p1 - 1) * (q1 - 1) % e == 0:
        continue
    if (p2 - 1) * (q2 - 1) % e == 0:
        continue
        
    N1 = p1 * q1
    N2 = p2 * q2
    break

• p1, p2 = getSafePrime(1024) : 위에서 설명한 고정된 p1, p2를 가져온다. 이 값은 공격자에게 이미 노출된 값이다.
• q1, q2 = getPrime(1024): q1과 q2는 랜덤하게 생성되는 1024비트 소수. 이것들은 Unknown 값이다.
• e = 0x10001: RSA Public Exponent로 가장 흔히 쓰이는 65537을 사용한다.
• if (p-1) * (q-1) % e == 0: RSA 키 생성 조건 검사.  $\phi(N) = (p-1)(q-1)$이 $e$와 서로소여야 역원 $d$를 구할 수 있다. 만약 서로소가 아니라면(최대공약수가 1이 아님), 키 생성을 다시 한다.
• N1, N2 계산: RSA의 모듈러(Modulus) $N = p \times q$를 계산한다.
  • $N1$은 첫 번째 암호문에 사용될 모듈러.
  • $N2$는 두 번째 암호문에 사용될 모듈러.

 

4. Flag 처리 및 변환

FLAG1 = bytes_to_long(FLAG[ : len(FLAG)//2])
FLAG2 = bytes_to_long(FLAG[len(FLAG)//2 : ])

• FLAG 문자열을 절반으로 나눈다.
• 그리고 쪼개진 텍스트를 RSA 수학 연산을 하기 위해서 Integer로 변환한다. 이것이 평문 메시지 $M$이 된다.

 

5. RSA 암호화 및 출력

# RSA encryption 1
FLAG1_enc = pow(FLAG1, e, N1)
print(f"{N1 = }")
print(f"{e = }")
print(f"{FLAG1_enc = }")

# RSA encryption 2
FLAG2_enc = pow(FLAG2, e, N2)
print(f"{N2 = }")
print(f"{e = }")
print(f"{FLAG2_enc = }")

• pow(base, exp, mod) : 모듈러 거듭제곱 연산 함수
  • $C \equiv M^e \pmod{N}$
  • 즉, FLAG1_enc는 FLAG1을 $e$제곱하고 N1으로 나눈 나머지이다.

 

6. 정리

• 이 코드는 플래그를 두 조각 내어서 각각 다른 모듈러스 $N_1, N_2$로 RSA 암호화한다.

 

취약점 분석

1. 하드코딩된 소수 $p$

• RSA의 안전성은 $N =pq$에서 $p$와 $q$를 모른다는 가정(소인수분해 난제)에 기반한다.

p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653

• getPrime(n)을 호출하여 난수를 생성하는 척 했지만, 그 직후에 p1을 상수로 덮어썼다.
• 공격자는 Brute Force나 복잡한 수학적 공격을 할 필요 없이, 소스 코드를 보는 것만으로 $p1$ 값을 획득할 수 있다.
• 이 시점에서 $N1$에 대한 소인수분해 난이도는 $O(1)$로 떨어진다.

 

2. 파생 키 p2

• 두 번째 소수 p2 역시 안전하지 않다.

p2 = 2*p1 + 1

• p2는 p1의 종속된 값이다.
• 암호학에서 키들은 서로 independent해야 안전한데, 여기서는 p1을 알면 p2가 자동적으로 결정된다.
• p1이 하드코딩되어 있으므로, p2 역시 사실상 하드코딩된 상수나 다름없다.

 

공격 시나리오

1. q 값 복구

• RSA 모듈러의 정의에 따라 다음이 성립합니다.

$N1 = p1 \times q1 \quad \Rightarrow \quad q1 = \frac{N1}{p1}$

 

$N2 = p2 \times q2 \quad \Rightarrow \quad q2 = \frac{N2}{p2}$

 

2. 오일러 피 함수 및 개인키 $d$ 도출

$$\phi(N1) = (p1 - 1)(q1 - 1)$$

$$d1 \equiv e^{-1} \pmod{\phi(N1)}$$

 

$$\phi(N2) = (p2 - 1)(q2 - 1)$$

$$d2 \equiv e^{-1} \pmod{\phi(N2)}$$

 

3. 복호화

$$FLAG1 \equiv (FLAG1\_enc)^{d1} \pmod{N1}$$

$$FLAG2 \equiv (FLAG2\_enc)^{d2} \pmod{N2}$$

 

 

공격 코드

# [1] prob.py에서 추출한 하드코딩된 소수
p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
p2 = 2 * p1 + 1

# [2] output.txt 데이터
N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221
FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798
N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043
FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402
e = 65537

# [3] 복호화 로직
def long_to_bytes(val):
    byte_len = (val.bit_length() + 7) // 8
    return val.to_bytes(byte_len, "big")

# p1, p2가 소인수인지 확인
if N1 % p1 == 0 and N2 % p2 == 0:
    q1 = N1 // p1
    q2 = N2 // p2
    
    # 개인키 계산
    phi1 = (p1 - 1) * (q1 - 1)
    phi2 = (p2 - 1) * (q2 - 1)
    
    d1 = pow(e, -1, phi1)
    d2 = pow(e, -1, phi2)
    
    # RSA 복호화
    m1 = pow(FLAG1_enc, d1, N1)
    m2 = pow(FLAG2_enc, d2, N2)
    
    # 결과 합치기
    full_flag = long_to_bytes(m1) + long_to_bytes(m2)
    print("\n[+] Found Flag:")
    print(full_flag.decode())
else:
    print("[-] Error: Hardcoded primes are NOT correct factors.")