読者です 読者をやめる 読者になる 読者になる

バランスを取りたい

よくCTFの記事を書きます

Broken RSA

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

問題はこちら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()


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

-----BEGIN RSA PRIVATE KEY-----
MIIEJAIBAAKCAQEAggNgY3I2KU7KczjoE08f3B7Tv7xYBVbPw+FiymxNP3g4jYOP
LALTzSRLU1xsVVc+E36b/C7SVD9ZesJwSgpenDgCbU5+zDgLg4pqDIE2SpGKkCOR
SHSQDklHrnj48OTnwbGYEjVmAP6/j0UREk/dI0blJWFjg2D3HT0cpyoAuRJtgmLo
4o5uCX/ujYTPmY2VnaBYYZbStQ6L9k0SEdp5eYiakFS6a+Za3jJjM8vasIML0Q2h
Yu27RAvI8QC7CrpaQci6V9lLGX+kbiTLHkskyp4upvxkvI/Qw8MD14eLKnRHPppt
KV/UwWggbbfz3Ub0idQ9TP/A7uq/cgNsQs2A0QIDAQABAoIBAFgf/cdRlMhfUKMW
MLUJGvTjwPOTy0+ZYP1I51AlzJ8p6HdGliGwHjRw1rcTCk0y70Nhs4kbtNh4CXni
MOGAIraMIq9724uN/uqt5fnds3g1c+ffDAqunTLqoiMqwA14OJi5wKuGg0Ba0+e1
OjtwhqdJBqJs47UENc1zEnYMI37scmgp78kSXMeiRNVM6tNA+3ckcZaxYB5ZcLnX
HCkxots72SpjMoa733NASKfY+VnOQ8I2LqjRae3hY1Sey6wjTWlEDNarp5mvF+Kc
TkJbCBHXDrRu8OJnIXItE5rlNyKTAPjW7n0XuGCu98Xr3BeJkFQ/AAD//wAA//8A
AP//AAECBXNEhGcBAoH8ASC/p0UJw7hw0pM8Vr1tlz4S+AoGewLwUiJ4mZfuZODi
+NkOOukfEORr9vvOs9u69vfxI5jcGjo15LOked3rUCV4oA3QZ2al+YESeXEeS6ao
XkcVjPKADdJLTBoyb5PXR8whvX8H9Od9Sj4AAaYlCNWpQ30OU0fiV6BLsYpTxwyV
mU9wdYCpbQaTlhvFS3g+3h4hf6E4+TxaDBK3cpok2v/CX0dTXmXim3VPBRp4E43g
hxbKo8saD2szYU719kxsmXse7QHOUhwp3EOsDv7lww71TJX+dg4h4wZRcpahuz7u
+hhB9iZiIILTcBIr+1BZoE+Fv0QjaqmKdmnRAgVv2h4NAQKB/ACprlOMiq7Wm91R
oX8CeKKDM8Pjy6Llvr1SZ6H2k/QKlVSXnjWf1NKtA7tDAfRVwfteXQeiw6cjBrrl
tuBo6Ttc8MD91vXCWKPz1XfKUEM80Vfq+VkfCxx3zlwFMBzm6pPKGjycbLZAAMGQ
reiHf85dXoqn9NUEPRP09h+GcUUqDJ1yXQN/pr0OUivv9TgtcuPM2iM4cgLinGp2
BwnD4tvKOGTeB7EXs7NNxVUUIqjslGjP6GGoP5vVtdxg/LO2tnFG+8I+arzEKEBT
6AlaeL3UVrGtL/099a/oi33Stl06vlXzVsI5wOLeoBZzXjiOvIDKqi3YJaxPOBxq
8QIFLpMhL9s=
-----END RSA PRIVATE KEY-----

正しい秘密鍵を作ることができたので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で暗号問題を解きたい人はしっかり復習しておきましょう。

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