Broken RSA - バランスを取りたい

セキュリティキャンプ2015内の出張CTF for ビギナーズで出題した問題です。

問題はこちら<a href="https://github.com/rekkusu/seccamp2015ctf/tree/master/broken_rsa">rekkusu/seccamp2015ctf</a>github.com

このWriteupを読む前にWikipediaのRSA暗号のページを一読しておくことをおすすめします。

1. 不思議な秘密鍵

秘密鍵private.pemが提供されているにも関わらず、この鍵ではencryptedを復号化することができません。また、private.pemで何らかのテキストを暗号化した場合でもやはり復号化することができません。

問題文でも鍵が怪しいといった内容が示されているので、鍵の内容をチェックしてみます。

% openssl rsa -in private.pem -text
Private-Key: (2048 bit)
modulus:
    00:82:03:60:63:72:36:29:4e:ca:73:38:e8:13:4f:
    1f:dc:1e:d3:bf:bc:58:05:56:cf:c3:e1:62:ca:6c:
    4d:3f:78:38:8d:83:8f:2c:02:d3:cd:24:4b:53:5c:
    6c:55:57:3e:13:7e:9b:fc:2e:d2:54:3f:59:7a:c2:
    70:4a:0a:5e:9c:38:02:6d:4e:7e:cc:38:0b:83:8a:
    6a:0c:81:36:4a:91:8a:90:23:91:48:74:90:0e:49:
    47:ae:78:f8:f0:e4:e7:c1:b1:98:12:35:66:00:fe:
    bf:8f:45:11:12:4f:dd:23:46:e5:25:61:63:83:60:
    f7:1d:3d:1c:a7:2a:00:b9:12:6d:82:62:e8:e2:8e:
    6e:09:7f:ee:8d:84:cf:99:8d:95:9d:a0:58:61:96:
    d2:b5:0e:8b:f6:4d:12:11:da:79:79:88:9a:90:54:
    ba:6b:e6:5a:de:32:63:33:cb:da:b0:83:0b:d1:0d:
    a1:62:ed:bb:44:0b:c8:f1:00:bb:0a:ba:5a:41:c8:
    ba:57:d9:4b:19:7f:a4:6e:24:cb:1e:4b:24:ca:9e:
    2e:a6:fc:64:bc:8f:d0:c3:c3:03:d7:87:8b:2a:74:
    47:3e:9a:6d:29:5f:d4:c1:68:20:6d:b7:f3:dd:46:
    f4:89:d4:3d:4c:ff:c0:ee:ea:bf:72:03:6c:42:cd:
    80:d1
publicExponent: 65537 (0x10001)
privateExponent:
    56:c6:24:26:1b:8b:74:a4:86:d0:c2:71:7a:b9:bb:
    bc:f1:c2:48:5d:4f:ae:38:93:b0:dc:14:50:a0:5a:
    2a:7b:75:db:55:ac:50:26:8e:f0:83:41:d7:20:7f:
    99:b2:01:d7:87:10:5b:0f:71:08:13:c4:08:00:10:
    6c:0a:61:bd:08:50:ee:5d:8e:99:84:ea:82:5f:f6:
    89:e4:0f:b5:53:50:55:05:b8:28:d0:cb:79:0d:85:
    cf:38:24:86:bb:70:c7:41:5e:0b:01:22:d4:95:32:
    8b:50:00:a5:e5:31:e6:22:a2:3c:01:b5:26:71:a8:
    5d:16:75:b2:48:81:6b:b3:b7:f5:fc:da:d3:3e:ef:
    3b:24:50:4b:81:15:c4:ed:3b:cb:ef:aa:75:ca:77:
    58:0d:c8:58:17:c1:53:e9:b9:91:c4:1b:d3:87:a2:
    3f:c9:b5:68:3c:78:28:19:00:54:b9:25:f5:37:1d:
    0b:0e:cc:b0:9c:41:c0:5c:4e:00:9a:0f:60:95:9e:
    af:c2:65:67:5b:ee:07:29:58:8e:08:99:ff:5c:d3:
    8d:46:1a:a4:62:3b:0f:7a:66:9c:11:b9:9d:79:68:
    80:6c:58:2b:7b:05:dd:3c:ab:9d:ed:61:19:06:11:
    ae:1b:55:d0:c4:96:4f:32:c4:14:b8:e0:f5:bc:14:
    95
prime1:
    09:50:94:92:9b:6c:39:de:29:7b:5b:6f:a2:93:63:
    f8:de:56:20:f6:dd:5d:14:94:ec:e4:42:55:fa:be:
    db:ca:46:2a:73:2d:05:c7:e6:b1:53:42:76:89:35:
    67:7a:8d:d4:87:14:f6:b2:e3:68:d5:7f:af:6b:1e:
    2d:90:38:68:d6:71:44:48:f5:0d:5c:37:c7:ab:d1:
    eb:91:40:73:9a:0a:92:15:4b:cc:48:29:05:6c:dc:
    76:f5:11:bc:0b:90:dc:e5:ee:3d:bb:ed:c5:2d:c4:
    c0:b6:2b:c5:fa:d7:08:fe:14:78:56:7f:8f:48:b5:
    d7:8c:f1:10:32:cf:df
prime2:
    0d:f5:2f:1a:68:06:51:cc:d2:5b:83:32:ee:88:cf:
    e8:71:f9:bb:7e:1c:2e:ca:d3:ff:87:dc:17:8a:fe:
    85:92:aa:1e:df:3a:ce:78:84:35:32:71:fc:99:8c:
    ab:94:1f:9c:de:8c:55:bf:a0:b3:7e:0f:e9:10:c7:
    c6:58:5f:e1:4a:52:62:aa:2c:6f:f0:f7:cd:cc:cf:
    1d:4b:de:6d:0d:74:a6:02:9b:a9:7c:4b:10:43:e9:
    ae:53:ae:f9:60:68:2b:b3:59:e7:bb:33:0d:c7:0b:
    9a:89:dd:f2:30:e2:29:80:fe:da:1c:ce:9c:9d:2e:
    51:93:12:19:39:a8:1c:f0:05:4f
(省略)

ぱっと見では至って普通の秘密鍵に見えます。
RSAの鍵を見慣れている人はprime1とprime2のビット数が大きく異なることに気づくかもしれません。

ただ、暗号化したテキストを復号化することができないのでどこかがおかしいはずです。
復号化する時に使う値は $d$ =privateExponentなのでまずはそこを疑います。
dは他の値から計算される値で、

$ed \equiv 1 (\bmod{\:\phi(N)})$

となりますが、eは鍵を作成するときに自由に設定できる上今回は一般的な値なので $\phi(N)$ もしくは $N$ が怪しいということになります。

2. Nを素因数分解する

$\phi(N)$ は $N$ から計算されるので $N$ を詳しく見てみましょう。
RSA暗号では $N$ は素数 $p,q$ の積で作られます。 $d$ から元を辿ってきましたが $p,q$ より先はありません。

ここでもし $p,q$ が素数でなかったらどうでしょうか。 $p,q$ を元にして作った値すべてが間違っているということになります。
Broken RSAのキモはこの部分で、答えを言ってしまいますが $p,q$ は現実的な時間で素因数分解できる合成数でした。

SageMath Cloudのfactor関数に $N$ を加えると1分程度で素因数分解が終了します。 $N=pq$ であることを利用して $p,q$ を別々にfactor関数に掛けるともう少し高速化できます。

f:id:xrekkusu:20150816233638p:plain

factor(16412644668387448202602868564657817982712937117403326478040413244236254209496422904841684484070976457127375281938290368819113895947104117920301391301302458296995119090401217271530671857359331013018245353633823829023919982282853725331228993010723032259432768476189536325244779555100499288430162843372341424896331171429031460987478425485927429353451288825183178490523945285963321241638761938399327909890149306684087809043387541718932166246829150568334276381266981951527138353767039901526430946041905249119183001989621345785066731600788939651395359292331721765532484866325744418810054000818931641021711343993047877517521)
21312192379 * 41694776327 * 57712671469 * 69102768037 * 79753565033 * 86131058131 * 91838820179 * 129887877181 * 144561148073 * 156135349637 * 172718834527 * 183076580677 * 299708689207 * 315959390353 * 359234858707 * 359289993437 * 457408060411 * 472896378329 * 476875578869 * 495070766849 * 522484567589 * 539156063617 * 547718265481 * 558061439779 * 563426178853 * 578072728433 * 616107638803 * 623193007529 * 624533069099 * 672942390979 * 677437074187 * 686116305163 * 747518751157 * 748151626433 * 750776132569 * 752501396681 * 779700020551 * 784911464809 * 815527664663 * 823394947451 * 836607296719 * 838784442581 * 854962951303 * 871923615209 * 891152617007 * 933107199179 * 944189993029 * 957027949433 * 992735373053 * 1027411280821 * 1036372987901 * 1057330714703 * 1057438303553

3. dを再構築する

$\phi(N)$ は、 $N$ のすべての素因数それぞれから1を引いたものをすべて掛ければ求めることができます。

普通のRSA暗号であれば、 $N$ の素因数は $p,q$ のみなので、
$\phi(N) = (p-1) \times (q-1)$
となります。

今回は素因数がたくさんあるのですべてについて計算を行います。

$\phi(N)$ が計算できたらそれを使って

$ed \equiv 1 (\bmod{\:\phi(N)})$

となるような $d$ を計算します。

今回は
Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world
のコードを使って逆元の計算を行いました。

以下のコードではPyCryptoを使用してRSAの秘密鍵を生成する部分まで行っていますが、 $d$ がわかったら暗号文を $d$ 乗することでも復号化することができます。

from Crypto.PublicKey import RSA

def egcd(a, b):
    x, y = 0, 1
    u, v = 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
    gcd = b
    return gcd, x, y

def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None
    else:
        return x % m

M = [91838820179, 1036372987901, 957027949433, 547718265481, 891152617007, 495070766849, 1057438303553, 944189993029, 299708689207, 871923615209, 836607296719, 752501396681, 476875578869, 156135349637, 578072728433, 57712671469, 457408060411, 539156063617, 672942390979, 79753565033, 992735373053, 624533069099, 677437074187, 748151626433, 838784442581, 815527664663, 686116305163, 1027411280821, 129887877181, 933107199179, 472896378329, 183076580677, 172718834527, 41694776327, 69102768037, 1057330714703, 359234858707, 779700020551, 522484567589, 144561148073, 623193007529, 616107638803, 86131058131, 784911464809, 747518751157, 854962951303, 750776132569, 558061439779, 359289993437, 21312192379, 563426178853, 315959390353, 823394947451]
e = 65537L

N = 1
phi = 1
for x in M:
    N *= x
    phi *= x - 1

d = modinv(e, phi)

key = RSA.construct((N, e, d))
print key.exportKey()

最終的に復元された秘密鍵

正しい秘密鍵を作ることができたのでopensslを使って暗号文を復号化します。

% openssl rsautl -decrypt -in encrypted -inkey realkey.pem
FLAG{4c7u4lly_N_c4n_b3_br0k3n}

4. まとめ

Broken RSAは「もし $p, q$ が合成数だったら」という発想でRSAを考えなおした時、 $\phi(N)$ が大きく変わってくるが $N$ から $\phi(N)$ が計算できるならきちんと復号化できるという事実から生まれた問題です。
RSA暗号を詳しく知っていないと解くことができないのでCTFで暗号問題を解きたい人はしっかり復習しておきましょう。

素因数分解のところでちょっとエスパー分が入ってますが暗号問題はエスパーっぽいところがあるので慣れてください。