BKPCTF 2016 bob's hat (2/4)

問題概要

前回の続き．展開して得られた公開鍵の中身を見てみる．

$ openssl rsa -text -pubin < almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
    00:ab:e6:33:ce:c2:e7:ec:10:a8:51:92:79:05:a6:
    57:df:4e:10:41:60:23:c0:c3:4f:c6:4d:64:bd:8b:
    82:57:b7:bf:20:7a:dd:04:7b:0a:df:21:c5:25:b0:
    52:06:8c:70:29:5c:74:6c:3b:1b:e1:43:6f:39:ed:
    8b:f7:a8:13:e4:b8:45:ce:0c:a8:9c:a8:28:b4:57:
    63:d4:6b:18:98:c7:a2:fa:5f:8f:e7:84:28:ca:b6:
    cd:f7:0e:f8:71:db:97:1b:32:32:84:1a:1c:e2:45:
    9c:e6:50:a1:54:36:2f:80:cf:b6:41:63:c3:ca:63:
    ad:72:bc:fb:db:f0:15:4f:f7
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCr5jPOwufsEKhRknkFplffThBB
YCPAw0/GTWS9i4JXt78get0EewrfIcUlsFIGjHApXHRsOxvhQ2857Yv3qBPkuEXO
DKicqCi0V2PUaxiYx6L6X4/nhCjKts33Dvhx25cbMjKEGhziRZzmUKFUNi+Az7ZB
Y8PKY61yvPvb8BVP9wIDAQAB
-----END PUBLIC KEY-----

特に怪しいところはない．fermat法をしてみても素因素分解できない．そこで試しに前の問題で使った公開鍵のgcdをとってみる．そうすると1ではない値がでてきた．つまり素数の使い回しをしていることがわかる．

解き方

gcdをとって，出てきた値を$p$として，$N$を割って，$q$を作る．あとは前回と同じ手順．以下にプログラムを示す．

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

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

e = 0x10001

# from almost_almost_almost_almost_there.pub
n1 = "00:86:e9:96:01:3e:77:c4:16:99:00:0e:09:41:d4:80:c0:46:b2:f7:1a:4f:95:b3:50:ac:1a:4d:42:63:72:92:3d:8a:45:61:d9:6f:bf:b0:24:05:95:90:72:01:ad:32:25:cf:6e:de:d7:de:02:d9:1c:38:6f:fa:c2:80:b7:2d:0f:95:ca:e7:1f:42:eb:e0:d3:ed:ae:ac:e7:ce:a3:19:5f:a3:2c:1c:60:80:d9:0e:f8:53:d0:6d:d4:57:2c:92:b9:f8:31:0b:bc:0c:63:5a:5e:26:95:25:11:75:10:30:a6:59:08:16:55:4e:76:30:31:bc:bb:31:e3:f1:19:c6:5f".gsub(/:/, "").hex

p1,q1 = fermat(n1)

n2 = "00:ab:e6:33:ce:c2:e7:ec:10:a8:51:92:79:05:a6:57:df:4e:10:41:60:23:c0:c3:4f:c6:4d:64:bd:8b:82:57:b7:bf:20:7a:dd:04:7b:0a:df:21:c5:25:b0:52:06:8c:70:29:5c:74:6c:3b:1b:e1:43:6f:39:ed:8b:f7:a8:13:e4:b8:45:ce:0c:a8:9c:a8:28:b4:57:63:d4:6b:18:98:c7:a2:fa:5f:8f:e7:84:28:ca:b6:cd:f7:0e:f8:71:db:97:1b:32:32:84:1a:1c:e2:45:9c:e6:50:a1:54:36:2f:80:cf:b6:41:63:c3:ca:63:ad:72:bc:fb:db:f0:15:4f:f7".gsub(/:/, "").hex

p2 = n1.gcd(n2)
q2 = n2 / p2

puts p2
puts q2
raise "Failed factorization" unless p1 * q2 == n2

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

rsa = RSA.new(e, n2, p1, q2)
puts rsa.decrypt(c).to_ascii

以下が実行結果である．

9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
12401828372292379853813876769631673931562555174641979554254424458038243058638417065284301266881242433017828663818811606556559256084249679274024474025282343
rlSpJ6HbP+cZXaOuSPOe4pgfevGnXtLt

得られたパスワードを使って展開してみると，また同じように3つのファイルが得られた．次回に続く．