SECCON2017 Online CTF: Ps and Qs
問題
問題文
Ps and Qs
Decrypt it.
update: we fixed the flag, please try to submit again.
psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip (pass:seccon2017)
問題ファイルは下記のリンクのものを利用できる。
https://github.com/SECCON/SECCON2017_online_CTF/tree/master/crypto/200_Ps%20and%20Qs
問題概要
- RSA の公開鍵 2 つと暗号文が与えられる。
解答例
指針
- Common Factor Attack
解説
与えられた zip ファイルを解凍すると次の 3 つのファイルが見つかる。
$ unzip psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip Archive: psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip [psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip] cipher password: extracting: cipher inflating: pub1.pub inflating: pub2.pub
RSA の公開鍵のようなので openssl を使って 素数の積 n と e の値を取り出す。
$ openssl rsa -text -pubin < pub1.pub
Public-Key: (4096 bit)
Modulus:
00:cf:cf:bb:ee:a7:df:14:3a:8a:c2:08:b1:aa:1d:
2f:86:54:5a:c4:cb:58:8c:94:a3:fb:1c:14:ad:91:
a4:f0:b9:36:15:7c:5a:4b:86:9c:18:a8:b8:64:f4:
(略)
$ openssl rsa -text -pubin < pub2.pub
Public-Key: (4096 bit)
Modulus:
00:bb:33:cc:7f:cc:8e:ca:f3:bf:9e:d9:5c:58:37:
92:e1:ec:6b:80:ee:87:5e:c2:06:4d:bc:f0:75:95:
c8:34:49:23:bf:53:65:24:d4:e0:a7:55:74:c7:79:
(略)
Ps and Qs という問題名から 2 つの合成数が共通因数を持つと推測できる。
したがってユークリッドの互除法により最小公倍数を求めることで共通因数である素数 p が求まる。
取り出した素数の積をそれぞれ n1, n2 とすると n1 / p, n2 / p とすることでもう一方の素数も求まる。
n1 / p = q1, n2 / p = q2 として秘密鍵を (p, q1) の組と (p, q2) の組の 2 つ作成する。
このように共通の因数を含む合成数の素因数分解が容易であることを利用した攻撃方法を Common Factor Attack という。
現実にはそのような合成数の組がみつかる可能性はとても低い。
#!/usr/bin/env python2 # coding: utf-8 s1 = """00:cf:cf:bb:ee:a7:df:14:3a:8a:c2:08:b1:aa:1d: 2f:86:54:5a:c4:cb:58:8c:94:a3:fb:1c:14:ad:91: a4:f0:b9:36:15:7c:5a:4b:86:9c:18:a8:b8:64:f4: 72:6b:f8:fc:dc:02:0c:b4:10:42:ba:c9:67:84:ab: 7d:03:f9:37:49:47:ef:b0:bc:3d:66:58:31:97:43: 40:15:9f:fc:3d:b7:c8:e7:4b:63:90:fd:a6:ee:c3: 0b:81:c6:ff:62:4e:8d:3f:5b:17:bf:b7:a5:c7:ff: d8:ec:f4:e6:51:8b:39:3a:be:fd:dd:0f:ae:ba:43: 08:74:6b:a6:3f:81:06:b5:9d:7e:05:89:43:a0:01: 31:a7:d4:e5:38:c4:64:b2:70:57:76:47:ed:bc:47: 8c:c1:ce:95:85:ef:e8:77:30:5b:3a:7c:2e:7c:44: db:54:75:ed:da:dc:34:5a:2c:90:a9:46:77:1c:ac: 0a:45:4c:db:cb:46:1f:28:40:e7:61:3c:83:e9:ce: cc:94:03:7f:a0:9b:b9:da:a3:f1:80:56:2c:01:df: 0b:e6:c5:1f:0c:06:e8:f0:e2:d6:e1:a5:e5:0d:0a: 28:c3:88:11:40:77:0a:9f:45:93:41:46:b7:f3:59: b9:39:ce:23:f0:fa:50:7a:6f:4e:45:45:71:43:09: 52:00:3c:20:f1:d9:7a:67:14:0b:6e:5f:cb:fb:3b: 37:6e:4e:24:96:9a:eb:1d:48:9c:fc:72:af:4f:15: a4:78:8a:1a:a9:7c:89:75:6d:1d:4d:94:aa:47:e7: cd:3a:81:ae:cb:92:44:8c:c9:2c:77:d2:ef:57:6a: a0:db:c1:35:08:62:ac:cd:da:dd:bc:e8:03:57:f0: cd:5b:85:4d:d0:f8:c4:62:7f:e4:b7:18:b2:4e:cf: e1:1e:d2:4c:3b:e2:2f:00:64:3b:be:d4:ee:5e:34: 5a:f1:76:e5:b7:6d:23:a2:f8:0e:0e:c6:f3:4e:57: 18:c6:2a:70:fe:55:70:c2:8b:80:7b:44:f2:2e:ad: eb:d9:b5:ff:90:6f:6a:85:be:88:c0:c8:f6:e5:f8: 80:a5:1f:17:f8:4d:b1:c2:ee:fe:a8:af:34:04:04: 44:ce:d1:a3:7d:f0:e4:f5:f7:2c:c3:f5:0b:7e:42: 7c:8c:2d:8b:61:86:ea:d7:62:f0:c4:44:b3:ca:3a: 01:03:ed:12:a9:3b:ce:9c:ae:74:79:a2:29:eb:bc: 0a:64:8e:aa:6f:97:e5:05:1a:66:eb:09:eb:d7:34: 8e:92:f7:5f:12:5e:bd:c3:67:e2:a7:d1:da:77:59: d4:1f:ae:2e:26:35:bf:4b:7a:7f:91:be:ca:b3:ac: 7d:05:bd""" s2 = """ 00:bb:33:cc:7f:cc:8e:ca:f3:bf:9e:d9:5c:58:37: 92:e1:ec:6b:80:ee:87:5e:c2:06:4d:bc:f0:75:95: c8:34:49:23:bf:53:65:24:d4:e0:a7:55:74:c7:79: 8c:73:b1:97:dd:2b:1b:42:05:4b:1e:49:cb:45:fb: f0:4e:6f:11:4c:f8:a3:65:c3:df:36:45:52:4f:77: 82:68:03:8a:3f:a2:68:02:e9:d1:ed:bf:bb:5e:df: b5:a0:c3:75:37:0d:7f:10:f5:7d:ab:bd:4f:77:1d: ad:36:32:f0:1b:9b:ce:10:48:99:66:ee:88:2d:ab: 17:a3:3b:78:6a:a5:f7:31:65:a5:40:51:30:0b:1d: f9:28:03:92:a3:ed:e9:d3:fc:9c:4d:8a:6a:06:35: 1f:6e:f3:59:8e:8d:e2:b3:9d:3b:19:af:64:a1:71: 6c:d1:58:26:c3:f2:4c:b1:3d:eb:72:2c:3a:03:ef: 1d:2b:e2:d0:a5:a6:e2:10:ff:5d:01:83:67:be:3b: f9:9e:a2:6b:a0:06:e5:16:4a:4d:d5:5a:ab:cd:44: 9d:e5:ce:18:64:82:5d:c1:60:e5:0d:50:9e:b0:e6: fe:72:3e:f1:82:68:1e:dd:b9:40:84:b8:3e:c9:e2: e9:43:e8:7c:b8:75:09:ab:0f:d9:b1:ca:22:c1:ce: af:f3:9f:ca:cf:67:29:fc:0e:05:78:67:0d:87:d7: f0:f9:cc:be:09:cb:3e:12:ce:b8:95:57:2a:99:79: d1:0b:fd:bf:af:a2:60:56:8d:8d:b1:84:be:12:b3: e3:19:3e:07:72:9c:e3:c1:d9:cd:82:83:ed:69:83: a0:63:88:03:6a:0a:70:29:4f:23:39:29:44:77:82: 80:e7:de:9f:60:16:3a:81:50:e3:0f:f4:a4:ea:02: 79:2c:be:83:05:ba:a2:e9:9a:fe:51:e1:7d:af:c5: 6b:e0:d3:84:14:7b:cd:38:e9:d1:29:34:ec:71:26: 22:21:77:73:a4:b3:85:1a:9b:0c:6c:7c:3e:01:f6: 11:1a:1e:1a:55:7f:4e:2a:e4:a2:47:ce:9b:75:cc: cc:b1:81:98:25:f3:05:4a:a1:c0:55:bd:3e:23:40: 09:3a:e2:ef:1d:0f:a5:a1:76:82:5e:fd:f7:95:07: 02:7f:51:04:08:00:09:14:2f:0d:43:e2:f1:0c:fa: d2:20:81:3b:bb:90:14:d4:f4:32:5e:da:c5:38:fb: 5e:82:b7:53:e2:ad:3b:24:60:7d:73:80:aa:64:fc: b9:8b:59:ea:8b:5a:73:6b:80:93:83:24:8c:ec:e0: b1:72:55:ea:55:9e:90:12:7f:77:8a:f6:d7:e8:a6: 6d:ad:91""" n1 = int(s1.replace("\n", "").replace(":", "").replace(" ", ""), 16) n2 = int(s2.replace("\n", "").replace(":", "").replace(" ", ""), 16) e = 65537 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 = extgcd(n1, n2)[2] q1 = n1 / p q2 = n2 / p def int2bin(d): t = format(d, 'x') return (t if len(t) % 2 == 0 else "0" + t).decode("hex") def enclen(l): if l < 0x80: return chr(l) else: t = int2bin(l) return chr(0x80 + len(t)) + t def encint(n): t = int2bin(n) return "\x02" + enclen(len(t)) + t def generate_secret_key(n, p, q, e, s = "secret.key"): d = extgcd(e, (p-1)*(q-1))[0] % ((p-1)*(q-1)) exp1 = d % (p-1) exp2 = d % (q1-1) coef = pow(q, p-2, p) t = "".join(map(encint, [0, n1, e, d, p, q, exp1, exp2, coef])) t = "\x30" + enclen(len(t)) + t secret_key = "-----BEGIN RSA PRIVATE KEY-----\n" secret_key += t.encode("base64")[:-1] secret_key += "\n-----END RSA PRIVATE KEY-----" with open(s, 'w') as f: f.write(secret_key) generate_secret_key(n1, p, q1, e, "secret1.key") generate_secret_key(n1, p, q2, e, "secret2.key")
作成した秘密鍵の一方 (p, q1) で復号ができた。
$ cat cipher | openssl rsautl -decrypt -inkey secret1.key
SECCON{1234567890ABCDEF}
$ cat cipher | openssl rsautl -decrypt -inkey secret2.key
RSA operation error
4294956672:error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:rsa_pk1.c:273:
4294956672:error:04065072:rsa routines:RSA_EAY_PRIVATE_DECRYPT:padding check failed:rsa_eay.c:602:
PyCrypto を使った解法
PyCrypto ライブラリを使うと秘密鍵の生成をもっと楽にできる。
pip でインストールできる。
$ pip install pycrypto
自分の環境 (msys2) では CFLAGS に '-D_GNU_SOURCE' を渡す必要があった。
$ pip2 install pycrypto
(略)
/usr/include/sys/time.h:104:34: エラー: 不明な型名 ‘u_int’ です
bintime_mul(struct bintime *_bt, u_int _x)
^~~~~
error: command 'gcc' failed with exit status 1
----------------------------------------
Command "/usr/bin/python2 -u -c "import setuptools, tokenize;__file__='/tmp/pip-build-JABG7g/pycrypt, 'exec'))" install --record /tmp/pip-AfX1Cb-record/install-record.txt --single-version-externally-m
(略)
$ CFLAGS='-D_GNU_SOURCE' pip2 install pycrypto
Collecting pycrypto
Using cached pycrypto-2.6.1.tar.gz
Installing collected packages: pycrypto
Running setup.py install for pycrypto ... done
Successfully installed pycrypto-2.6.1
- PyCrypto を利用したコード
#!/usr/bin/env python2 # coding: utf-8 import codecs from fractions import gcd from Crypto.PublicKey import RSA from Crypto.Util.number import inverse def read_key(filename): with codecs.open(filename, "r") as input_file: data = input_file.read() pub = RSA.importKey(data) return pub def generate_secret_key(n, e, d, s = "secret.key"): key = RSA.construct(map(long, (n, e, d))) with open(s, 'w') as f: f.write(key.exportKey()) print "generated secret_key" pub1 = read_key("pub1.pub") pub2 = read_key("pub2.pub") p = gcd(pub1.n, pub2.n) q1, q2 = pub1.n / p, pub2.n / p e1, e2 = pub1.e, pub2.e d1 = inverse(pub1.e, (p-1)*(q1-1)) d2 = inverse(pub2.e, (p-1)*(q2-1)) generate_secret_key(pub1.n, pub1.e, d1, "secret1.key") generate_secret_key(pub2.n, pub2.e, d2, "secret2.key")
- 実行結果
$ python solve.py
generated secret_key
generated secret_key
$ cat cipher | openssl rsautl -decrypt -inkey secret1.key
SECCON{1234567890ABCDEF}
