> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-safeprime.md). # \[DreamHack] safeprime #### 문제 링크 {% embed url="" %} #### 문제
#### Writeup ``` 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 = }") ``` 문제코드 -> RSA를 두 번 나누고 있음 첫 번째 RSA 키 -> p1은 고정되어 있음 -> p2 = 2\*p1 + 1 -> 즉, p2는 safe prime 구조 -> q1은 랜덤한 1024 bit 소수 -> N1 = p1 \* q1 두 번재 RSA 키 -> p2는 2\*p1 + 1 -> q2는 또 다른 랜덤한 1024 소수 -> N2 = p2 \* q2 출력값이 주어짐(output.txt) ``` N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221 e = 65537 FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798 N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043 e = 65537 FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402 ``` 복호화 코드는 다음과 같다. 각 변수에 출력값을 넣어준다. ``` from Crypto.Util.number import long_to_bytes, inverse # 이미 알고 있는 값 p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653 # 코드에서 하드코딩된 값 p2 = 2*p1 + 1 # 받은 값들 N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221 N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043 FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798 FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402 e = 65537 # RSA 키 복구 q1 = N1 // p1 phi1 = (p1 - 1)*(q1 - 1) d1 = inverse(e, phi1) FLAG1 = pow(FLAG1_enc, d1, N1) q2 = N2 // p2 phi2 = (p2 - 1)*(q2 - 1) d2 = inverse(e, phi2) FLAG2 = pow(FLAG2_enc, d2, N2) # 최종 FLAG 복원 flag = long_to_bytes(FLAG1) + long_to_bytes(FLAG2) print(flag) ```

--- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-safeprime.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.