BKPCTF 2016 bob's hat (3/4)

問題概要

前回の続き．前回同様opensslで鍵の中身を見てみる．

$ openssl rsa -text -pubin < almost_almost_there.pub
Public-Key: (1040 bit)
Modulus:
    00:ba:d2:0c:f9:7e:d5:04:2d:f6:96:ce:4d:f3:e5:
    a6:78:cf:4f:b3:69:3d:3d:f1:2d:fe:9f:d3:fd:8c:
    c8:aa:b8:b9:55:33:e4:14:e3:fc:0c:37:7f:4e:e5:
    48:27:11:8b:1d:30:56:1a:3c:74:1b:ea:7c:76:89:
    97:89:b5:17:43:e0:76:09:2d:f9:eb:05:dc:97:eb:
    15:05:ce:9e:b1:2b:5a:b9:e1:0a:bf:56:f9:20:a5:
    8e:7e:00:ec:f0:59:77:e8:72:83:4d:d8:58:4c:f4:
    ac:87:cb:7d:c5:01:59:bd:96:2c:75:cb:ef:b6:c6:
    ac:3a:31:a7:4e:7d:8f:1e:4c:10:d5
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGhMA0GCSqGSIb3DQEBAQUAA4GPADCBiwKBgwC60gz5ftUELfaWzk3z5aZ4z0+z
aT098S3+n9P9jMiquLlVM+QU4/wMN39O5UgnEYsdMFYaPHQb6nx2iZeJtRdD4HYJ
LfnrBdyX6xUFzp6xK1q54Qq/VvkgpY5+AOzwWXfocoNN2FhM9KyHy33FAVm9lix1
y++2xqw6MadOfY8eTBDVAgMBAAE=
-----END PUBLIC KEY-----

また何の変哲もないような鍵の値．素因素分解の方法には前々回にあげたfermat法など優秀なアルゴリズムがあるが，愚直に小さい値から割っていくという力技ももちろん存在する．一瞬力技に見えるかもしれないが，素因数$p,q$のどちらかの値が小さいときには有効な手法である．

解き方

loopで1から順番に試し割りしていく．その他は今まで通り．

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

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

e = 0x10001

n = "00:ba:d2:0c:f9:7e:d5:04:2d:f6:96:ce:4d:f3:e5:a6:78:cf:4f:b3:69:3d:3d:f1:2d:fe:9f:d3:fd:8c:c8:aa:b8:b9:55:33:e4:14:e3:fc:0c:37:7f:4e:e5:48:27:11:8b:1d:30:56:1a:3c:74:1b:ea:7c:76:89:97:89:b5:17:43:e0:76:09:2d:f9:eb:05:dc:97:eb:15:05:ce:9e:b1:2b:5a:b9:e1:0a:bf:56:f9:20:a5:8e:7e:00:ec:f0:59:77:e8:72:83:4d:d8:58:4c:f4:ac:87:cb:7d:c5:01:59:bd:96:2c:75:cb:ef:b6:c6:ac:3a:31:a7:4e:7d:8f:1e:4c:10:d5".gsub(/:/,"").hex

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

i = 1
loop do
  break if n.gcd(i) != 1
  i += 1
end


p = i
q = n / i

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

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

以下が実行結果である．

54311
158304142767773473275973624083670689370769915077762416888835511454118432478825486829242855992134819928313346652550326171670356302948444602468194484069516892927291240140200374848857608566129161693687407393820501709299228594296583862100570595789385365606706350802643746830710894411204232176703046334374939501731
hQdK+dKleMJqth/dofWyFaiWp3PW7jil

見てわかるとおり，片方の素因数がかなり小さいことがわかる．
得られたパスワードで復号すると今まで通りの３つのファイルがでてきた．次回に続く