[138] IT 비전공자 [dreamhack]safeprime문제 풀기

 

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 = }")

 

output.txt

N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221
e = 65537
FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798
N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043
e = 65537
FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402

 

 

 

이 문제는 RSA 암호화와 관련된 문제로, 특히 안전 소수(safe prime)를 사용하여 암호화를 수행하고 있습니다. 주어진 코드를 분석하고 문제를 해결하기 위한 전략을 세워 보겠습니다.

---

코드 분석

1. getSafePrime(n) 함수:
   • 안전 소수 pp는 2p+12p + 1 꼴의 수가 소수일 때 pp를 의미합니다.
   • 주어진 코드에서는 이미 특정 소수 p1p1을 설정하고 있으며, p2=2p1+1p2 = 2p1 + 1가 소수인지 확인합니다.
   • 조건을 만족하면 p1p1과 p2p2를 반환합니다.
2. RSA 키 생성:
   • 두 세트의 RSA 모듈러스 N1N1과 N2N2가 생성됩니다.
   • N1=p1⋅q1N1 = p1 \cdot q1, N2=p2⋅q2N2 = p2 \cdot q2.
   • q1q1과 q2q2는 임의의 소수입니다.
   • 공개 지수 e=65537e = 65537 (일반적으로 사용하는 값).
3. 조건 확인:
   • ee와 (p1−1)(q1−1)(p1-1)(q1-1), ee와 (p2−1)(q2−1)(p2-1)(q2-1)는 서로소 관계여야 합니다.
   • 만약 조건이 만족되지 않으면 새로운 소수를 선택합니다.
4. FLAG 암호화:
   • FLAG를 두 부분으로 나누어 각각 RSA 암호화를 수행합니다.
   • 첫 번째 절반은 N1N1, 두 번째 절반은 N2N2로 암호화됩니다.
   • 결과로 FLAG1encFLAG1_enc와 FLAG2encFLAG2_enc를 출력합니다.

---

공격 전략

문제점:

• p1p1이 하드코딩되어 있으므로 p2p2도 쉽게 계산 가능합니다.
• N1=p1⋅q1N1 = p1 \cdot q1이므로 q1=N1/p1q1 = N1 / p1을 통해 q1q1을 구할 수 있습니다.
• 마찬가지로 q2=N2/p2q2 = N2 / p2로 q2q2를 구할 수 있습니다.
• q1q1, q2q2, p1p1, p2p2를 이용하면 RSA 비밀 키 dd를 계산하여 FLAG를 복호화할 수 있습니다.

단계:

1. p1, p2 계산:
   • p1p1은 하드코딩된 값.
   • p2=2p1+1p2 = 2p1 + 1.
2. 소인수 분해:
   • N1N1에서 q1=N1/p1q1 = N1 / p1.
   • N2N2에서 q2=N2/p2q2 = N2 / p2.
3. RSA 비밀 키 dd 계산:
   • ϕ(N1)=(p1−1)(q1−1)\phi(N1) = (p1 - 1)(q1 - 1).
   • d1=e−1mod  ϕ(N1)d1 = e^{-1} \mod \phi(N1).
   • d2=e−1mod  ϕ(N2)d2 = e^{-1} \mod \phi(N2).
4. FLAG 복호화:
   • FLAG1=FLAG1encd1mod  N1FLAG1 = FLAG1_enc^d1 \mod N1.
   • FLAG2=FLAG2encd2mod  N2FLAG2 = FLAG2_enc^d2 \mod N2.
   • FLAG를 두 부분을 합쳐 원문을 얻습니다.

---

우리가 해야 할 일은 다음과 같습니다:

1. N1과 N2를 사용해 q1q1과 q2q2를 계산합니다.
   • q1=N1/p1q1 = N1 / p1, q2=N2/p2q2 = N2 / p2.
2. ϕ(N1)\phi(N1)와 ϕ(N2)\phi(N2)를 계산합니다.
   • ϕ(N)=(p−1)(q−1)\phi(N) = (p - 1)(q - 1)로 계산.
3. RSA 비밀키 d1d1과 d2d2를 계산합니다.
   • d=e−1mod  ϕ(N)d = e^{-1} \mod \phi(N).
4. 암호화된 FLAG를 복호화합니다.
   • FLAG=FLAGencdmod  NFLAG = FLAG_{\text{enc}}^d \mod N.
5. 복호화된 FLAG를 출력합니다.

아래에 이를 수행하는 코드를 작성하겠습니다:

from Crypto.Util.number import inverse, long_to_bytes

# 주어진 값
p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
p2 = 2 * p1 + 1

N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221
FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798

N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043
FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402

e = 65537

# 소인수 분해
q1 = N1 // p1
q2 = N2 // p2

# φ(N) 계산
phi_N1 = (p1 - 1) * (q1 - 1)
phi_N2 = (p2 - 1) * (q2 - 1)

# 비밀키 d 계산
d1 = inverse(e, phi_N1)
d2 = inverse(e, phi_N2)

# FLAG 복호화
FLAG1 = pow(FLAG1_enc, d1, N1)
FLAG2 = pow(FLAG2_enc, d2, N2)

# 결과 출력
FLAG = long_to_bytes(FLAG1) + long_to_bytes(FLAG2)
print(f"FLAG: {FLAG.decode()}")

---

이 코드는 주어진 암호문과 N1,N2,eN1, N2, e를 기반으로 FLAG를 복호화합니다. 이 코드를 실행하면 문제의 FLAG를 얻을 수 있습니다.