uncommon e 풀이

문제 제목

문제 정보

prob.py

N = 18564839028340970630632687927085732690660216946716888067188954046812800985732372062460700863888002343155902759133649880101140768419725781550847529242612574780286876355781415545270149267924318930484262298628091098398893193544538272524290190578306149953368594658823348775434109820836311754081667945186523509419274141640792179302149121645060758381445210342226062749581257840649008843072969882069745488933714383742625035916351887508696280553528500528993974650390749489910938646668966427281419193682964555099697539229141704274820381967489671915008271272572784624353477273387243166242973237904102218303978989538340075110803
e1 = 26107
e2 = 416
FLAG_enc1 = 7527079488835824550176589432384780921138078216741164078317178088512020484637815911814449926944662371885728405467621509470317993615175662631245614263206465411761405248665475018014955011387536383732578999002193581953127201730485926821982569309896641811322758517611730555795173063573946211306084429097792646498732335587337634527626172754334153175582669944053431474970826408358022316126279869698898223075336790046723458233152991869045783807109865365096509043487724858636091575421769914060998644878330883643511254289263960487281213979614256506109469224245020612145584918823245558025971100167133602718304130194072814312710
FLAG_enc2 = 5553467916392779302319650321161682360291392077019602231908379041584499902773710723619110301005008094731504431902945888409491392723061165695579512443486392024940348967751410819758344508288749930005375895909393752897849038447778016747963886132791102187462287312608282729773341145901349954559564077909026595969034706754208713806020071917600988186991043342705750598606533751031166628502148837344385933277599437539183985932955644653119376571815604213229278422645273875273059325957488817516922134037588666169092554553063254879269416996367056713107865228810125004163068707218820011235988174311427569510212386257879728088984

 

지수와 암호문이 2개씩 주어졌습니다.

Common Moduls Attack으로 해결할 수 있을 것 같네요.

https://velog.io/@hunji/Common-Modulus-Attack

Common Modulus Attack

 

블로그에 나온 선행 조건

다행히 선행 조건도 만족합니다.

해결 방법을 알았으니, 바로 코드 작성!

 

from Crypto.Util.number import inverse, long_to_bytes

N = 18564839028340970630632687927085732690660216946716888067188954046812800985732372062460700863888002343155902759133649880101140768419725781550847529242612574780286876355781415545270149267924318930484262298628091098398893193544538272524290190578306149953368594658823348775434109820836311754081667945186523509419274141640792179302149121645060758381445210342226062749581257840649008843072969882069745488933714383742625035916351887508696280553528500528993974650390749489910938646668966427281419193682964555099697539229141704274820381967489671915008271272572784624353477273387243166242973237904102218303978989538340075110803
e1 = 26107
e2 = 416
FLAG_enc1 = 7527079488835824550176589432384780921138078216741164078317178088512020484637815911814449926944662371885728405467621509470317993615175662631245614263206465411761405248665475018014955011387536383732578999002193581953127201730485926821982569309896641811322758517611730555795173063573946211306084429097792646498732335587337634527626172754334153175582669944053431474970826408358022316126279869698898223075336790046723458233152991869045783807109865365096509043487724858636091575421769914060998644878330883643511254289263960487281213979614256506109469224245020612145584918823245558025971100167133602718304130194072814312710
FLAG_enc2 = 5553467916392779302319650321161682360291392077019602231908379041584499902773710723619110301005008094731504431902945888409491392723061165695579512443486392024940348967751410819758344508288749930005375895909393752897849038447778016747963886132791102187462287312608282729773341145901349954559564077909026595969034706754208713806020071917600988186991043342705750598606533751031166628502148837344385933277599437539183985932955644653119376571815604213229278422645273875273059325957488817516922134037588666169092554553063254879269416996367056713107865228810125004163068707218820011235988174311427569510212386257879728088984

def f (enc1, enc2, a, b) : # Euclidean algorithm
    q = a // b
    r = a % b
    if(r == 1 ) :
        return enc1 * inverse(pow(enc2, q, N), N) % N
    else : 
        return f(enc2, enc1 * inverse(pow(enc2, q, N), N) % N, b, r)

print(f(FLAG_enc1, FLAG_enc2, e1, e2).to_bytes(68, 'big'))

문제 풀이 성공