神のミソ汁のセカイ

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

backdoor CTF 2015: RSALOT Write-up

問題

backdoor CTF 2015: RSALOT

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

解答

問題ファイルを解凍すると100個のRSA公開鍵(1.pem100.pem)とflag.encが入っていた。 flag.encの中身はflagを暗号化してbase64エンコードしたものみたいだ。これをデコードしてRSA暗号で復号すればflagが手に入りそう。

opensslで公開鍵の中身を覗くとprivate exponentはどの公開鍵も65537だが法は全て異なっていた。 もし、この中に共通の素数を持つ法があればgcdを計算することで法を因数分解できる。 法同士のgcdを計算するために、まずは次のシェルスクリプトを使って法をファイルに1つずつ取り出した。

#!/bin/sh
for var in `ls -1 *.pem`
do
    openssl rsa -pubin -in "$var" -noout -modulus | sed "s/Modulus=//g" > "modulus/$var.mod.txt"
done

法を抜きだしたら全ての法の組み合わせでgcdを計算してgcd≠1であるファイルを探し出す。 今度はpythonでプログラムを書いた。

# -*- coding : UTF-8 -*-

import math
import binascii

def getint(filename):
    f = open(filename, 'r')
    hex_str = f.read().strip()
    return int(hex_str, 16)

for i in range(1, 100):
    for j in range(i+1, 101):
        n1 = getint('modulus/'+str(i)+'.pem.mod.txt')
        n2 = getint('modulus/'+str(j)+'.pem.mod.txt')
        if math.gcd(n1, n2) != 1:
            print ('i=',i,'j=', j)
            common_prime = math.gcd(n1, n2)
            q1 = n1 // common_prime
            q2 = n2 // common_prime
            print ('common_prime', common_prime)
            print ('q1: ', q1)
print ('q2: ', q2)

実行結果

$ python3 search_common_prime.py
i= 64 j= 87
common_prime 168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691
q1:  137852341825115687630372545540234125575043643297743715914372468140743017665122928684176567678186288631724569119078697598260381091322877334920545216266418987980787824645288016924652387350842372904949656504253960440751217710040954075691996893620788950284865727480192510130305432030965910622333944701850333681207
q2:  139208418683860744636489594107518498051692876942105482068436575406002091300025595750940476658875774324613311765708231971440632450100860632595797604226237831396754383891914573698131769762436941837224713009721577421233571830899874638297795728204831707647487557389464078420524002550428515370686466308350190419191

64.pem87.pemに共通の素数がある事がわかった。これらを元に秘密鍵を作って復号すればいい。 秘密鍵の作成にはrsatoolを使った。

組み合わせが2種類あるので秘密鍵を2つ作って復号する。それぞれprivate64.keyとprivate87.keyという名前で保存しておいた。 復号プログラムはhttps://docs.launchkey.com/developer/encryption/python/python-encryption.htmlのコードを利用した。

# -*- coding : utf-8 -*-

def decrypt_RSA(private_key_loc, package):
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP
    from base64 import b64decode
    key = open(private_key_loc, "r").read()
    rsakey = RSA.importKey(key)
    rsakey = PKCS1_OAEP.new(rsakey)
    decrypted = rsakey.decrypt(b64decode(package))
    return decrypted

package = open('flag.enc', "r").read()
message = decrypt_RSA('private87.key', package)

print (message)

実行結果

$ python3 depython3 decrypt_RSA.py
b'the_flag_is_b767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa'

よってflagはb767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa(秘密鍵はprivate87.key)

感想

RSAを勉強した知識が生きた。