BKPCTF 2016 bob's hat (1/4)

問題概要

bob’s hat — 4 : crypto : Alice and Bob are close together, likely because they have a lot of things in common.This is why Alice asked him a small question, about something cooler than a wiener.

配布されたzipファイルを展開すると以下の3つのファイルが手に入る．

1. パスワード付きzip(almost_almost_almost_almost_there.zip)
2. 公開鍵(almost_almost_almost_almost_there.pub)
3. 暗号化されたファイル(almost_almost_almost_almost_there.encrypted)

暗号化されたファイルを正しく復号できると，zipのパスワードがわかるようになっている．

まずはopensslで鍵の中身を見てみる．(毎回これ忘れてググってるとどうにかしたい)

$ openssl rsa -text -pubin < almost_almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
    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
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCG6ZYBPnfEFpkADglB1IDARrL3
Gk+Vs1CsGk1CY3KSPYpFYdlvv7AkBZWQcgGtMiXPbt7X3gLZHDhv+sKAty0Plcrn
H0Lr4NPtrqznzqMZX6MsHGCA2Q74U9Bt1Fcskrn4MQu8DGNaXiaVJRF1EDCmWQgW
VU52MDG8uzHj8RnGXwIDAQAB
-----END PUBLIC KEY-----

1024bitのNと適切なeに見えるが，とりあえずNを素因数分解できないか試してみる．今回は，fermat法を使ってみる．

fermat法

$ x^2 - y^2 = (x - y) \times (x + y)$となることを利用して，$n$が$x^2-y^2$で表す事ができる時，素因数分解できるというやつ．数式を見ればわかるが，素因数$x$と$y$が互いに近いときにはこれはかなり効いてくる．

fermat法を用いて上記の$N$を素因数分解してみるプログラムが以下である．非公開
の秘伝のタレの中にfermat法やto_ascii，to_hexは定義されている．

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

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

e = 0x10001
n = "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

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

p, q = fermat(n)
raise "Failed factorization" unless p * q == n

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

これを実行するとこんな感じで$p,q$そしてパスワードが求まる．

9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987245583
XtCgoEKksjKFWlqOSxqsEhK/+tsr1k5c

パスワードを使ってzipを展開してみると，今回と同様の3つのファイルが現れた．次回に続く．

余談

上記のプログラムで，$n$をハードコーディングしているのはopensslとか使って以下のようにやるとコケてしまったためである．

require 'openssl'

OpenSSL::PKey::RSA.new('./almost_almost_almost_almost_there.pub')
=begin
OpenSSL::PKey::RSAError: Neither PUB key nor PRIV key: not enough data
        from (irb):2:in `initialize'
        from (irb):2:in `new'
        from (irb):2
        from /home/vagrant/.rbenv/versions/2.3.1/bin/irb:11:in `<main>'
=end

ただ以下のようにBEGINとENDで囲まれた中身をBase64で戻してやって直接流し込むとちゃんと機能するらしい．

require 'openssl'
require 'base64'
body = File.read('./almost_almost_almost_almost_there.pub').split("\n")[1..-2].join("")
rsa = OpenSSL::PKey::RSA.new(Base64.decode64(body))
puts rsa.n
puts rsa.e