神のミソ汁のセカイ

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

Pragyan CTF 2015: Weak RSA Write-up

問題

Pragyan CTF 2015: Weak RSA

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

解答

与えられたファイルfooはtar形式だったので展開すると次の2つのファイルが現れた。

  • cipher.enc base64形式の暗号文
  • domain.csr 署名要求のためのcsrファイル

csrファイルの中身をopensslコマンドで確認してみる。

$ openssl req -text -modulus -noout -in domain.csr
Certificate Request:
    Data:
        Version: 0 (0x0)
        Subject: C=IN, ST=NITT, L=-, O=-, OU=-, CN=weakrsa.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:e8:95:38:49:f1:1e:93:2e:91:27:af:35:e1:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:51:f8:eb:7d:05:56:e0:9f:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:fb:ad:55
                Exponent: 65537 (0x10001)
        Attributes:
            a0:00
    Signature Algorithm: sha256WithRSAEncryption
        7e:d8:a8:25:51:a1:9e:7b:b1:cc:05:87:18:fc:65:59:ba:db:
        07:d7:cd:95:00:6e:ae:d9:4b:ad:ab:f5:b5:7c:92:e8:c0:59:
        2d:11:df:61:c8:db:e4:f8:f7:e0:d2:7c:94:9a:80:49:20:ee:
        2f:3b:96:f0:4e:5f:ab:12:6d:6d:10:7e:39:e9:c8:35:33:71:
        86:d6:0e:30:6b:46:e6:d1:95:42:94:d9:75:6b:cf:10:b2:62:
        fa:56:4c:f9:60:07:84:cf:73:46:85:24:e1:37:9b:aa:84:70:
        b0:3c:4d:09:45:cb:b7:52:28:db:ca:35:6a:9b:22:d6:fc:89:
        25:0a
Modulus=E8953849F11E932E9127AF35E1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051F8EB7D0556E09FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAD55

Modulusの値に特徴があるので因数分解できるかもしれない。

因数分解アルゴリズムを探しているとフェルマー因数分解Fermat’s factorization method - Wikipediaを見つけた。フェルマー法は素数$n$を$n=(a-b)^2=(a+b)(a-b)$の形に変形することで因数分解する。

上記wikipedia数学者の密室 12章 素因数分解アルゴリズムを参考にフェルマー法で$N$を因数分解を計算するプログラムを書いた。

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

import gmpy2 as gp2

def fermat_method(n):
    x = gp2.isqrt(N) + 1
    y = gp2.isqrt(pow(x, 2) - N)
    w = pow(x,2) - N - pow(y,2)
    while(w != 0):
        if (w == 0):
            break;
        if w > 0:
            y += 1
        else:
            x += 1
        w = pow(x,2) - N - pow(y,2)

    return (x-y, x+y)

N = 0xE8953849F11E932E9127AF35E1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051F8EB7D0556E09FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAD55

print('N=', N)
p, q = fermat_method(N)
print('p =', p)
print('q =', q)

実行結果

$ ./Fermat_method.py
N= 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013
p = 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453
q = 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521

無事、$N$の素因数分解に成功したので今度はRSA暗号のソルバを書いた。暗号文はcat cipher.enc | base64 -Dとしてbase64形式から整数に戻した。

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

import gmpy2
import binascii

e = 65537
p= 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453
q= 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521

n = p * q
d = gmpy2.invert(e, (p-1)*(q-1))
c = 76628905480111532581338914747271384782783511160722054233840492116126156700750989597598764086667087929882155574613772521441663047915366133539316120325991966661466348138266360394561245386367735156756154303638622049855225176518054696962110019925849223565063511436418197917317987706182132214656056698754744084973 # 暗号文
m = pow(c, d, n)
print (binascii.a2b_hex('%0128x' % m))

実行結果

$ ./solver.py
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\x00Congrats! The flag is too_close_primes'

よってflagはtoo_close_primes

感想

素因数分解は難しいとはいえ素数$p,q$の選び方次第では因数分解できるんだなあ。しかも和と差の積にして因数分解するアイデアは面白い。