AlexCTF: CR3 What is this encryption?

問題

問題文

Fady assumed this time that you will be so n00b to tell what encryption he is using

he send the following note to his friend in plain sight :

p=0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9

q=0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307

e=0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41

c=0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520

He is underestimating our crypto skills!

和訳

Fady は今回、あなたは彼が使っている暗号が何であるか分からない noob (初心者を意味するスラング) であることを確信しています。

彼は次のようなメモを彼の友達に誰にでも見える状態で送りました。

(略)

彼は私達の暗号スキルを過小評価しています!

問題概要

素数の組 {p, q} および正整数 e, 暗号文 c が与えられる。

平文 m を復号せよ。

解答例

指針

解説

RSA 暗号の原理

p, q, e, c という記号から最も広く使われている公開鍵暗号であるRSA暗号の問題であることが分かります。

RSA暗号では次のような記号が使われています。

記号 意味
m 平文
c 暗号文
p, q 十分に大きい素数の組 (p ≠ q )
n p * q
ϕ(n) (p-1) * (q-1)
e ϕ(n) 未満かつ e と ϕ(n) は互いに素となるような自然数
d 秘密鍵

RSA 暗号は大きい合成数素因数分解が困難であることを安全性の根拠とした公開鍵暗号であり素数の組 {p, q} は秘密にし {p, q} の積 n をとして {e, n} を公開鍵としていますが 今回は {p, q} が与えられているので平文 m を復号できます。

RSA 暗号において暗号化, 復号および秘密鍵の生成は次のように計算されます。

暗号化: c = me mod n

復号: m = cd mod n

秘密鍵の生成: d = e-1 (mod (p-1)(q-1))

モジュラ逆元の求め方

d は (p-1)(q-1) を法とする e のモジュラ逆元であり拡張ユークリッドの互除法により求めることができます。

このことを簡単に示すと以下のようになります。(ほぼ Wikipedia のコピペ)

{ \displaystyle
d \equiv e^{-1} \pmod{(p-1)(q-1)}
}

 {(p-1)(q-1) = \varphi(n)} とおいて式を変形すると

{ \displaystyle
ed \equiv 1 \pmod{ \varphi(n)}
}

{ \displaystyle
ed - 1 \equiv 0 \pmod{ \varphi(n)}
}

よって適当な整数 r を用いて

{ \displaystyle
ed - 1 = r \varphi(n)
}

と表せる。整理すると

{ \displaystyle
ed - r \varphi(n) = 1
}

これはベズーの等式  {ax + by = gcd(a, b) } と同じ形をしており拡張ユークリッド互除法を用いて計算できることが分かる。

拡張ユークリッドの互除法の実装

引数としてa, b を受取り ax + by = gcd(a, b) の解 x, y と gcd(a, b) を返す関数 extgcd() は次のように実装できます。

拡張ユークリッドの互除法再帰を用いても実装できますが Python では再帰の深さ制限を意識する必要のない非再帰版を用いたほうがいいかもしれないです。

def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b/a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g
def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a%b)
    return [y, x - a/b * y, g]

コード

Python で cd (mod n) を求めるには pow(c, d, n) が使えます。

求める d は合同式を満たす自然数のうち最も小さいものなので ϕ(n) との剰余を取ります。

#!/usr/bin/env python2
# coding: utf-8

def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b/a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g

p = 0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9
q = 0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307
e = 0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41
c = 0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520
n = p*q
phi = (p-1)*(q-1)
d = extgcd(e, phi)[0] % phi

print (format(pow(c, d, n), 'x')).decode("hex")
  • 実行結果
$ python solve.py
ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}

参考文献