神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

BCTF CTF 2015: warmup Write-up

問題

BCTF CTF 2015: warmup

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

暗号文は

c=0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

であり16進数表記された整数である。リンクされているwarmup-c6aa398e4f3e72bc2ea2742ae528ed79.pub.xzを解凍するとRSA公開鍵warmup-c6aa398e4f3e72bc2ea2742ae528ed79.pub(以下warmup.pub)が手に入った。

公開鍵から秘密鍵を作り出して$c$を復号すればいいようだ。

opennsslで公開鍵の中身を見てみる。

$ openssl rsa -pubin -in warmup.pub -text -noout
Modulus (2050 bit):
    03:67:19:8d:6b:56:14:e9:58:13:ad:d8:f2:2a:47:
    17:bc:72:be:1e:ab:d9:33:d1:b8:69:44:fd:b7:5b:
    8e:d2:30:be:62:d7:d1:b6:9d:22:20:95:c1:28:c8:
    6f:82:01:2e:cb:11:61:91:fd:9d:01:8a:6d:02:f8:
    4d:b2:7b:c5:1a:21:30:7d:c8:6f:4b:f7:71:c6:91:
    c1:43:e5:ab:e5:49:b5:bd:2d:6e:b1:a2:1f:d6:27:
    0e:7e:1b:48:fe:06:11:fb:b2:e1:b0:b3:52:4e:6f:
    4d:e8:b4:e4:a3:45:da:44:a1:3d:e8:25:b7:26:08:
    db:6c:7c:4a:40:b7:82:66:e6:c8:7b:bf:de:f6:b4:
    83:81:d4:9c:45:07:a5:8b:cd:47:b7:6d:64:b4:59:
    08:b1:58:bd:7e:bc:4d:ac:b0:b1:cf:d6:c2:c1:95:
    74:f4:0e:b2:ef:d0:e9:e1:0d:c7:00:5c:ad:39:bc:
    af:52:b9:ea:c3:87:33:68:d6:90:31:c5:e7:24:68:
    4a:44:f0:68:ef:d1:d3:dc:09:6d:9b:5d:64:11:e5:
    8b:de:e4:3e:46:b9:9a:0d:04:94:b9:db:28:19:5a:
    f9:01:af:f1:30:d4:a6:e2:03:da:d0:8d:a5:7f:a7:
    e4:02:62:a5:ba:db:2a:32:3e:da:28:b4:46:96:ab:
    30:5d
Exponent:
    00:f3:95:9d:97:8e:02:eb:9f:06:de:f3:f3:35:d8:
    f8:af:d7:60:99:51:dd:ac:60:b7:14:b6:c2:2a:f0:
    fa:91:2f:21:0b:34:20:6b:d2:4a:96:01:c7:8d:f4:
    a0:27:5f:10:7f:d3:ab:55:2d:95:05:7e:b9:34:e7:
    1b:dd:cd:70:45:c2:4b:18:58:7b:8c:8f:cf:5a:dd:
    4c:5d:83:f0:c7:7c:94:dc:9c:50:cb:e4:38:e2:b6:
    7b:af:d3:16:33:b6:aa:f1:78:1d:90:c3:ad:6f:03:
    d0:37:b3:32:18:01:b2:35:46:d4:83:e6:7e:26:06:
    7f:7b:22:34:7d:db:c0:c2:d5:92:ce:81:4c:bf:5d:
    fc:cc:14:14:37:f1:4e:0b:39:90:f8:80:61:e5:f0:
    ba:e5:f0:1e:3f:a7:0d:b0:e9:60:5e:7c:fd:57:5e:
    9c:81:ef:ee:c5:29:c3:3f:d9:03:7a:20:fd:8a:cd:
    51:3a:c9:63:77:68:31:3e:63:f9:83:8a:e3:51:1c:
    dd:0a:9a:2b:51:6f:21:48:c8:d4:75:a3:60:a0:63:
    59:44:97:39:ee:cd:25:1a:bb:42:b0:14:57:3e:43:
    9f:2f:a4:57:35:57:b2:56:99:ff:c1:1e:63:1c:e8:
    ee:97:5a:86:e7:e2:72:bc:f5:f7:6a:93:45:03:48:
    fe:3f

上の結果から$e$が大きいことがわかる。RSAでは$e$が大きいと$d$が小さくなるので解読できる場合がある。

攻撃方法を探すとWiener’s Attackという攻撃を見つけた。 公開鍵暗号 - RSA - Wiener's Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです

連分数展開を用いて攻撃する手法のようだ。詳細は割愛(上のサイトのほかgoogleで調べると解説が多数ヒットする)。

githubにWiener’s Attackを行うプログラムがあったので利用させて頂いた。

pablocelayes/rsa-wiener-attack

上のプログラムを利用してWiener’s Attackを行い、得られた$d$を用いて復号するプログラムがこれ。

#! /usr/bin/env python3
# -*- coding  utf-8 -*-

import RSAwienerHacker
import binascii

e = int('00f3959d978e02eb9f06def3f335d8f8afd7609951ddac60b714b6c22af0fa912f210b34206bd24a9601c78df4a0275f107fd3ab552d95057eb934e71bddcd7045c24b18587b8c8fcf5add4c5d83f0c77c94dc9c50cbe438e2b67bafd31633b6aaf1781d90c3ad6f03d037b3321801b23546d483e67e26067f7b22347ddbc0c2d592ce814cbf5dfccc141437f14e0b3990f88061e5f0bae5f01e3fa70db0e9605e7cfd575e9c81efeec529c33fd9037a20fd8acd513ac9637768313e63f9838ae3511cdd0a9a2b516f2148c8d475a360a06359449739eecd251abb42b014573e439f2fa4573557b25699ffc11e631ce8ee975a86e7e272bcf5f76a93450348fe3f', 16)

n = int('0367198d6b5614e95813add8f22a4717bc72be1eabd933d1b86944fdb75b8ed230be62d7d1b69d222095c128c86f82012ecb116191fd9d018a6d02f84db27bc51a21307dc86f4bf771c691c143e5abe549b5bd2d6eb1a21fd6270e7e1b48fe0611fbb2e1b0b3524e6f4de8b4e4a345da44a13de825b72608db6c7c4a40b78266e6c87bbfdef6b48381d49c4507a58bcd47b76d64b45908b158bd7ebc4dacb0b1cfd6c2c19574f40eb2efd0e9e10dc7005cad39bcaf52b9eac3873368d69031c5e724684a44f068efd1d3dc096d9b5d6411e58bdee43e46b99a0d0494b9db28195af901aff130d4a6e203dad08da57fa7e40262a5badb2a323eda28b44696ab305d', 16)

d = RSAwienerHacker.hack_RSA(e, n)

c = int('1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86', 16)

m = pow(c, d, n)

print (binascii.a2b_hex('%0512x' % m))

実行結果は

$ ./solver.py
Hacked!
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00BCTF{9etRea4y!}'

よってflagはBCTF{9etRea4y!}

感想

Wiener’s Attackを行うプログラムを書こうと思ったけどうまく行かなくて既存のものを使った。暗号を勉強してる者としてWiener’s Attackはちゃんと理解しておきたい。