[Dreamhack] uncommon e

문제 설명

아모가 무슨 일이 있었던 건지, RSA에서 절대 평범한 e를 쓰지 않겠다고 하네요. 도대체 무슨 일이 있었던 걸까요?

 

소스코드

from Crypto.Util.number import getPrime, GCD, bytes_to_long

FLAG = b"DH{????????????????????????}"
FLAG = bytes_to_long(FLAG)

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q

    # e = 0x10001 
    # assert GCD((p - 1)*(q - 1), e) == 1... Oh, COME ON.. Stop generating that stupid COMMON e.
    for e1 in range(0x100, 0x10001):
        if GCD(p - 1, e1) >= 0x100: # much better!
            break

    for e2 in range(0x100, 0x10001):
        if GCD(q - 1, e2) >= 0x100: # This is nice!!
            break

    if GCD(e1, e2) == 1: # UN-UN common == common :P
        break

print(f"{N = }")
print(f"{e1 = }")
print(f"{e2 = }")

FLAG_enc1 = pow(FLAG, e1, N)
FLAG_enc2 = pow(FLAG, e2, N)

print(f"{FLAG_enc1 = }")
print(f"{FLAG_enc2 = }")

 

소스코드 분석

1.  Modulus 생성

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q

• $p, q$: 1024비트의 큰 소수 두 개를 무작위로 생성
• $N$: 두 소수의 곱. 이것이 공개키의 모듈러스(Modulus)가 된다.

 

2. 첫 번째 공개 지수 ($e_1$) 탐색

for e1 in range(0x100, 0x10001):
    if GCD(p - 1, e1) >= 0x100: # much better!
       break

• 256(0x100)부터 65537(0x10001)까지 순회한다.
• GCD(p - 1, e1) >= 0x100
  • 일반적인 RSA에서는 개인키 $d$를 구하기 위해서 $\text{gcd}(e, \phi(N)) = 1$이어야한다. ($e$의 곱셉의 역원이 존재하기 위해서는 $\phi(n)$과 $e$가 서로소여야함.)
  • 하지만 이 코드는 $e_1$과 $p-1$이 256 이상의 큰 공약수를 가지는 경우를 찾는다.
  • 즉, $e_1$은 정상적인 RSA 키로서 기능하지 못하는(단독으로는 복호화가 매우 어려운/불가능한) 고장난 키이다.

 

3. 두 번째 공개 지수 ($e_2$) 탐색

for e2 in range(0x100, 0x10001):
    if GCD(q - 1, e2) >= 0x100: # This is nice!!
       break

• $e_1$과 비슷하게 동작
• GCD(q - 1, e2) >= 0x100
  
  • $e_2$는 $q-1$과 256 이상의 큰 공약수를 가지는 경우를 찾는다.
  • $e_2$ 역시 단독으로는 정상적인 RSA 복호화가 불가능한 키이다.

 

4. 최종 탈출 조건 (취약점의 핵심)

if GCD(e1, e2) == 1: 
   break

• GCD(e1, e2) == 1
  • $e_1$과 $e_2$는 각각 $p-1$, $q-1$과는 공약수를 가지지만, 두 수끼리는 서로소여야 한다는 조건이다.
  • 이 조건이 만족되면 루프를 멈추고 암호화를 진행한다.

 

5. 결과 출력 및 암호화

print(f"{N = }")
print(f"{e1 = }")
print(f"{e2 = }")

FLAG_enc1 = pow(FLAG, e1, N)
FLAG_enc2 = pow(FLAG, e2, N)

print(f"{FLAG_enc1 = }")
print(f"{FLAG_enc2 = }")

• $N, e_1, e_2$ 값을 제공한다.
• 이중 암호화:
  1. $C_1 = M^{e_1} \pmod N$
  2. $C_2 = M^{e_2} \pmod N$
• 동일한 평문 메시지($M$, FLAG)를 동일한 모듈러스($N$)를 사용해, 서로 다른 두 지수($e_1, e_2$)로 암호화한 두 개의 암호문($C_1, C_2$)을 제공한다.

 

취약점 분석

 

이 문제의 핵심적인 취약점

1. 동일한 평문 $M$과 동일한 $N$이 사용되었다.
2. 두 개의 공개 지수 $e1, e2$가 사용되었다
3. 비록 $e_1, e_2$가 각각 $\phi(N)$과 서로소가 아니어서 개별적인 복호화 키($d$)를 구하기는 어렵지만, $e_1$과 $e_2$는 서로소($GCD(e_1, e_2)=1$)이다.

이 구조는 전형적인 Common Modulus Attack 시나리오이다.

$GCD(e_1, e_2) = 1$이므로, 확장 유클리드 알고리즘(Extended Euclidean Algorithm)을 통해 다음을 만족하는 정수 $r, s$를 찾을 수 있다.

$r \cdot e_1 + s \cdot e_2 = 1$

 

이를 이용하면 개인키($d$)를 모르고, 소인수분해($p, q$)를 하지 않아도 암호문 $C_1, C_2$를 조합하여 평문 $M$을 복구할 수 있다.

 

$C_1^r \cdot C_2^s \equiv (M^{e_1})^r \cdot (M^{e_2})^s \equiv M^{r e_1 + s e_2} \equiv M^1 \equiv M \pmod N$

 

 

공격

우리의 목표는 $r \cdot e_1 + s \cdot e_2 = 1$이 되는 정수 $r, s$를 찾는 것이다. 이 식을 $e_2$에 대한 모듈러 연산으로 바꾸면 다음과 같다.

 

$r \cdot e_1 + s \cdot e_2 \equiv 1 \pmod{e_2}$

 

$s \cdot e_2$는 $e_2$의 배수이므로 나머지가 0이 되어 사라진다.

 

$r \cdot e_1 \equiv 1 \pmod{e_2}$

 

즉 $r$은 $e_2$ modulus 하에서 $e_1$의 Modular Inverse와 같다. 

 

$r$을 구했으니 이제 원래 식 $r \cdot e_1 \equiv 1 \pmod{e_2}$에 대입해서 $s$를 구한다. 

 

$s \cdot e_2 = 1 - r \cdot e_1$

$s = \frac{1 - r \cdot e_1}{e_2}$

 

여기서 $r \cdot e_1$은 1보다 훨씬 큰 양수이므로, 분자 $(1 - r \cdot e_1)$은 음수가 된다. 따라서 $s$는 자연스럽게 음수 값을 갖게 된다.

 

수학적으로 $C_2^{s} \pmod N$ (음수 지수)은 $C_2$의 모듈러 역원을 양수 $|s|$만큼 제곱한 것과 같다.

 

$C_2^{-k} \equiv (C_2^{-1})^k \pmod N$

 

from Crypto.Util.number import long_to_bytes

# 1. 문제 데이터 설정
N = 18564839028340970630632687927085732690660216946716888067188954046812800985732372062460700863888002343155902759133649880101140768419725781550847529242612574780286876355781415545270149267924318930484262298628091098398893193544538272524290190578306149953368594658823348775434109820836311754081667945186523509419274141640792179302149121645060758381445210342226062749581257840649008843072969882069745488933714383742625035916351887508696280553528500528993974650390749489910938646668966427281419193682964555099697539229141704274820381967489671915008271272572784624353477273387243166242973237904102218303978989538340075110803
e1 = 26107
e2 = 416
c1 = 7527079488835824550176589432384780921138078216741164078317178088512020484637815911814449926944662371885728405467621509470317993615175662631245614263206465411761405248665475018014955011387536383732578999002193581953127201730485926821982569309896641811322758517611730555795173063573946211306084429097792646498732335587337634527626172754334153175582669944053431474970826408358022316126279869698898223075336790046723458233152991869045783807109865365096509043487724858636091575421769914060998644878330883643511254289263960487281213979614256506109469224245020612145584918823245558025971100167133602718304130194072814312710
c2 = 5553467916392779302319650321161682360291392077019602231908379041584499902773710723619110301005008094731504431902945888409491392723061165695579512443486392024940348967751410819758344508288749930005375895909393752897849038447778016747963886132791102187462287312608282729773341145901349954559564077909026595969034706754208713806020071917600988186991043342705750598606533751031166628502148837344385933277599437539183985932955644653119376571815604213229278422645273875273059325957488817516922134037588666169092554553063254879269416996367056713107865228810125004163068707218820011235988174311427569510212386257879728088984

# 2. 베주 항등식 계수(r, s) 구하기: r*e1 + s*e2 = 1
r = pow(e1, -1, e2)      
s = (1 - r * e1) // e2   

# 3. 평문 복구 (Common Modulus Attack) : m = (c1^r * c2^s) mod N
m = (pow(c1, r, N) * pow(c2, s, N)) % N

print(long_to_bytes(m).decode())

• 파이썬의 pow(a, -1, b) 문법은 역원을 구해준다.
• 파이썬의 pow(base, exp, mod) 함수는 지수(exp) 자리에 음수가 들어오면, 내부적으로 알아서 base의 모듈러 역원을 구한 뒤 연산을 수행한다.