0 まず

高校1年のもちもちです。セキュリティキャンプ全国大会2021やCODE BLUE2022に参加してました。CTFをやってる最中にこれを使う問題が出てきたので備忘録もかねて書くことにしました

1 Common Modulus Attackとは

RSA公開鍵 {$ n,e_2$}と{$n,e_2$}と平文$m$を暗号化した暗号文${c_1,c_2}$が与えられたときに$GCD(e_1,e_2)=1$である時に平文$m$を復元できるという攻撃です(GCDが1であることは後々重要になってきます)。

2 原理

そもそもRSA暗号の定義について振り返ると$c=m^e$ $mod$ $n$でした。ここで$e_1s_1+e_2s_2=1$となるような$s_1,s_2$が存在した場合

c_1^{s_1}c_2^{s_2}=m^{e_1s_1}m^{e_2s_2}=m^{e_1s_1+e_2s_2}=m^1=m \ (mod \ n)

と平文$m$が復元できる。$e_1s_1+e_2s_2=1$となるような$s_1,s_2$の求め方であるが、これは拡張ユークリッドの互除法により簡単に求めることができる。もし$GCD(e_1,e_2)\neq1$であった時、$d>1$であるような整数$d$を用いて$e_1=dE_1,e_2=dE_2$といったように書けるため$e_1s_1+e_2s_2=d(E_1s_1+E_2s_2)\neq1$となる。そのための$GCD(e_1,e_2)=1$である。

3　実装

例題を持ってきた。

from typing import Tuple, Iterator, Iterable, Optional
def excGCD(a:int,b:int)->Tuple[int,int,int]:
    if(b!=0):
        d,y,x=excGCD(b,a%b)
        y-=(a//b)*x
        return d,x,y
    return a,1,0

def Common_Modulus_Attack(N,e_1,c_1,e_2,c_2):
    d,s_1,s_2=excGCD(e_1,e_2)
    return (pow(c_1,s_1,N)*pow(c_2,s_2,N))%N


e_1=11
N=236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577
c_1=80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904 
e_2=13
c_2= 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664
m=Common_Modulus_Attack(N,e_1,c_1,e_2,c_2)
print(m)

motimotipurinn:/mnt/c/dev/pydev$ python3 pico.py 
424311244315114354

cpaw{424311244315114354}
ちなみにこれは

らしくrsaiseasyだそうです