Q29.[Crypto] Common World - ITホスト太陽りお official website

Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました．しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう.

(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)

暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904

これは…？

フラグは以下のシンタックスです.
cpaw{復号した値}

※復号した値はそのままで良いですが，実は意味があります，余力がある人は考えてみてください.

RSAについて理解
自分なりに理解した今回の解法
1. ステップ1: n の因数分解
2. ステップ2: 秘密鍵の計算
復号した値について

RSAについて理解

公開鍵: (e,n)
秘密鍵: (d,n) ←今回はdがわからない

わかりやすい解説はぐぐってください

自分なりに理解した今回の解法

これは・・・?で提示されている1例では、Nが同じ値になっている(世間的には同じnが同じにならないようになっているらしい)
e1 = 11
N= (略)
C1 = 暗号文1
と
e2 = 13
N= (略)
C2 = 暗号文2
から、この情報から、平文を特定できるらしい

ステップ1: n の因数分解

e1=11 と e2=13 から最大公約数 gcd(e1,e2)=1 となることがわかります。
したがって、拡張ユークリッドアルゴリズムを使用して、a とb を見つけます。ここで、
a⋅e1 + b⋅e2=1。
a⋅11 + b⋅13=1
6⋅11 + -5⋅13=1 となり、 a=6, b=-5となるらしい

ステップ2: 秘密鍵の計算

M ≡ C1^a ⋅ C2^b mod n
となるらしいので、 C1^6 + C2^-5 の値を N で割ったあまりが答えになるらしい

GPTに生成してもらった今回の復号スクリプト

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('The modular inverse does not exist')
    else:
        return x % m

# 拡張ユークリッドのアルゴリズムを使って x と y を計算
e1 = 11
e2 = 13
n = 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577

_, x, y = egcd(e1, e2)

# 与えられた暗号文
C1 = 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904
C2 = 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664

# 平文 M を計算
M = (pow(C1, x, n) * pow(C2, y, n)) % n
print(M)