BKPCTF 2016 bob's hat (4/4)

問題解説

前回の続き．今まで通りopensslで鍵を見てみる．

$ openssl rsa -text -pubin < almost_there.pub
Public-Key: (1024 bit)
Modulus:
    00:9c:2f:65:05:89:91:20:90:6e:5a:fb:d7:55:c9:
    2f:ec:42:9f:ba:19:44:66:f0:6a:ae:48:4f:a3:3c:
    ab:a7:20:20:5e:94:ce:9b:f5:aa:52:72:24:91:6d:
    18:52:ae:07:91:5f:bc:6a:3a:52:04:58:57:e0:a1:
    22:4c:72:a3:60:c0:1c:0c:ef:38:8f:16:93:a7:46:
    d5:af:bf:31:8c:0a:bf:02:76:61:ac:ab:54:e0:29:
    0d:fa:21:c3:61:6a:49:82:10:e2:57:81:21:d7:c2:
    38:77:42:93:31:d4:28:d7:56:b9:57:eb:41:ec:ab:
    1e:aa:d8:70:18:c6:ea:34:45
Exponent:
    46:6a:16:9e:8c:14:ac:89:f3:9b:5b:03:57:ef:fc:
    3e:21:39:f9:b1:9e:28:c1:e2:99:f1:8b:54:95:2a:
    07:a9:32:ba:5c:a9:f4:b9:3b:3e:aa:5a:12:c4:85:
    69:81:ee:1a:31:a5:b4:7a:00:68:ff:08:1f:a3:c8:
    c2:c5:46:fe:aa:36:19:fd:6e:c7:dd:71:c9:a2:e7:
    5f:13:01:ec:93:5f:7a:5b:74:4a:73:df:34:d2:1c:
    47:59:2e:14:90:74:a3:cc:ef:74:9e:ce:47:5e:3b:
    6b:0c:8e:ec:ac:7c:55:29:0f:f1:48:e9:a2:9d:b8:
    48:0c:fe:2a:57:80:12:75
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQCcL2UFiZEgkG5a+9dVyS/s
Qp+6GURm8GquSE+jPKunICBelM6b9apSciSRbRhSrgeRX7xqOlIEWFfgoSJMcqNg
wBwM7ziPFpOnRtWvvzGMCr8CdmGsq1TgKQ36IcNhakmCEOJXgSHXwjh3QpMx1CjX
VrlX60Hsqx6q2HAYxuo0RQKBgEZqFp6MFKyJ85tbA1fv/D4hOfmxnijB4pnxi1SV
KgepMrpcqfS5Oz6qWhLEhWmB7hoxpbR6AGj/CB+jyMLFRv6qNhn9bsfdccmi518T
AeyTX3pbdEpz3zTSHEdZLhSQdKPM73SezkdeO2sMjuysfFUpD/FI6aKduEgM/ipX
gBJ1
-----END PUBLIC KEY-----

今回のは今までとがらりと違う鍵の値である．注目するのは$e$かなり大きいという点である．$e$が大きい時には，相対的に$d$が小さくなる．$d$が小さい時，Wiener's attackという超有名な攻撃手法が刺さる．これについての説明は公開鍵暗号 - RSA - Wiener's Attackがわかりやすい．実装面では，Wiener’s Attack を実装したやWiener's Attackがわかりやすい．

解き方

Wiener's attackを実装してがんばる．

#!/usr/bin/env ruby
#coding: ascii-8bit

require '~/ctf/tools/ctf/crypto.rb'
require '~/ctf/tools/ctf/misc.rb'

e = 0x10001

n = "00:9c:2f:65:05:89:91:20:90:6e:5a:fb:d7:55:c9:2f:ec:42:9f:ba:19:44:66:f0:6a:ae:48:4f:a3:3c:ab:a7:20:20:5e:94:ce:9b:f5:aa:52:72:24:91:6d:18:52:ae:07:91:5f:bc:6a:3a:52:04:58:57:e0:a1:22:4c:72:a3:60:c0:1c:0c:ef:38:8f:16:93:a7:46:d5:af:bf:31:8c:0a:bf:02:76:61:ac:ab:54:e0:29:0d:fa:21:c3:61:6a:49:82:10:e2:57:81:21:d7:c2:38:77:42:93:31:d4:28:d7:56:b9:57:eb:41:ec:ab:1e:aa:d8:70:18:c6:ea:34:45".gsub(/:/,"").hex

e = "46:6a:16:9e:8c:14:ac:89:f3:9b:5b:03:57:ef:fc:3e:21:39:f9:b1:9e:28:c1:e2:99:f1:8b:54:95:2a:07:a9:32:ba:5c:a9:f4:b9:3b:3e:aa:5a:12:c4:85:69:81:ee:1a:31:a5:b4:7a:00:68:ff:08:1f:a3:c8:c2:c5:46:fe:aa:36:19:fd:6e:c7:dd:71:c9:a2:e7:5f:13:01:ec:93:5f:7a:5b:74:4a:73:df:34:d2:1c:47:59:2e:14:90:74:a3:cc:ef:74:9e:ce:47:5e:3b:6b:0c:8e:ec:ac:7c:55:29:0f:f1:48:e9:a2:9d:b8:48:0c:fe:2a:57:80:12:75".gsub(/:/, "").hex

c = File.read('./almost_there.encrypted').to_hex

p, q = wieners_attack(e, n)
puts p
puts q

raise "Failed factorization" unless p * q == n

rsa = RSA.new(e, n, p, q)
puts rsa.decrypt(c).to_ascii

以下が実行結果である．

10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983
10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507
/3aAP5dF2zmrPh9K6A4AqMLsIiYDk2C2

得られたパスワードでzipファイルを展開すると以下のFLAGファイルが得られる．

$ cat FLAG
BKPCTF{Its_not_you,_its_rsa_(that_is_broken)}