[DreamHack - Crypto] uncommon_e

Common modulus attack

Common Modulus Attack RSA 암호에서 같은 N과 GCD(e1, e2)=1 를 사용하여 같은 평문 m을 암호화해서 두 암호문 c1, c2을 만들었을 때, 이를 공격하는 기법이다.

공격자는 e1, e2가 서로소라는 점을 활용해 r*e1 + s*e2=1이고, (r, s) 쌍을 확장 유클리드 알고리즘을 통해 구할 수 있다.

 

유클리드 알고리즘

유클리드 알고리즘을 사용하여 GCD 를 구하는 방법을 알아보자. 106과 16의 GCD를 찾기 위해서 목과 나머지를 활용하면 다음과 같이 나타낼 수 있다.

우변이 0이 될 때 그전 식의 우변 2가 106, 16의 GCD가 된다.

 

풀이 방법

FLAG_enc1 = FLAG^e1 mod N

FLAG_enc2 = FLAG^e2 mod N

GCD(e1, e2) = 1 이므로 유클리드 알고리즘을 사용해서 FLAG 값을 구할 수 있다.

from Crypto.Util.number import inverse, long_to_bytes

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

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

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

 

실행 결과

b'DH{7e532757ebddde149f45c32156e58421e95b5c691b668f1681677af9495f7e36}'