NCTF2021 暗号問題の解法

signin 問題

この問題では、RSA暗号のパラメータに関する特定の関係が与えられています。与えられた式は以下の通りです：

[k = (p2^{1024})//(q+r)--> p2^{1024}=k*(q+r)+m--> 2^{1024}/k=(q+r)/p+m/(k*p) ]

ここでk*p>>mであるため、

[2^{1024}/k は (q+r)/p よりも若干大きい ]

この性質を利用して、2**1024/kの連分数近似を行い、(q+r)/pの値を特定します（Wiener攻撃と同様のアプローチ）。その後、p,q,rを求め、dを計算して平文を復元します。

import gmpy2
from Crypto.Util.number import*

def fraction_to_continued(x, y):  # ユークリッドの互除法で分数を連分数に変換
    result = []
    while y:
        result.append(x // y)
        x, y = y, x % y
    return result

def continued_to_fraction(sub_result):
    numerator, denominator = 1, 0
    for i in sub_result[::-1]:  # 逆順に処理
        denominator, numerator = numerator, i * numerator + denominator
    return denominator, numerator  # 連分数の漸近分数の分母と分子を返す

# すべての漸近分数を計算
def get_convergents(x, y):
    cont_frac = fraction_to_continued(x, y)
    convergents = []
    for i in range(1, len(cont_frac)):
        convergent = continued_to_fraction(cont_frac[:i])
        convergents.append(convergent)
    return convergents

def wiener_attack(target, secret_key):
    for (prime_factor, sum_qr) in get_convergents(target, secret_key):
        if sum_qr == 0:  # 連分数の最初の要素が0の場合はスキップ
            continue
        if isPrime(prime_factor):
            if n % prime_factor == 0:
                print(prime_factor)
                print(sum_qr)
                return prime_factor, sum_qr
    
    return None, None

target = 2**1024
secret_key = 94541588860584895585135152950569493777168309607384495730944110393788712443252059813470464503558980161423182930915955597122997950103392684040352673659694990925903156093591505153081718027169554019948988048641061593654540898258994671824807628660558123733006209479395447337793897155523508261277918178756662618785
n=780382574657056148524126341547161694121139907409040429176771134165303790043856598163799273195157260505524054034596118923390755532760928964966379457317135940979046201401066257918457068510403020146410174895470232276387032511651496790519359024937958635283547294676457588680828221680705802054780628993173199987362419589945445821005688218540209709368995166794607635504501281131700210990592718388166388793182269128127850804650083811982799377308916540691843310867205397
prime_factor, sum_qr = wiener_attack(target, secret_key)

上記のコードでpとq+rを取得し、SageMathを使用して連立方程式を解いてp,q,rの値を求めます。その後、以下のコードで平文を復元します：

from Crypto.Util.number import*
p=9591034708161364221769733163551836281062083244512519384396165987809544507968391606587728397659016542948096617311787604058178460710869231247971978002127911
q=7783303527956388882925926241649086816516401013818809868989894869944824560842420253258139068646778092017713916219975429637932259781411715380715911885101359
r=10453894999046673647308947017087829722773272707345254431452943862698229414154549643006087444848992128177899286390321602677342098868495750510174086311850253
n=780382574657056148524126341547161694121139907409040429176771134165303790043856598163799273195157260505524054034596118923390755532760928964966379457317135940979046201401066257918457068510403020146410174895470232276387032511651496790519359024937958635283547294676457588680828221680705802054780628993173199987362419589945445821005688218540209709368995166794607635504501281131700210990592718388166388793182269128127850804650083811982799377308916540691843310867205397
phi=(p-1)*(q-1)*(r-1)
public_exponent=65537
private_exponent=inverse(public_exponent,phi)
ciphertext=601133470721804838247833449664753362221136965650852411177773274117379671405966812018926891137093789704412080113310175506684194683631033003847585245560967863306852502110832136044837625931830243428075035781445021691969145959052459661597331192880689893369292311652372449853270889898705765869674961705116875378568712306021536838123003111819172078652012105725060809972222290408551883774305223612755026614701916201374200602892717051698568751566665976546137674450533774
plaintext=pow(ciphertext,private_exponent,n)
print(long_to_bytes(plaintext))

実行結果としてフラグ b'nctf{238fa78a-5e61-4dc6-8faf-7e2e30e02286}' が得られます。

rsa 問題

16バイトのデータを4つに分割し、それぞれをlong型に変換すると32ビットの値になります。32ビットの数値は、高い確率でi(20ビット)*j(16ビット)またはそれ以下の因数に分解できます。

これを利用して、120秒の制限時間内にテーブルを構築し、検証を経て短時間でcを爆破します。

[m^e=i^ej^e ][c≡i^ej^e\ \ \ (mod\ n)\ \ \ \ \ \ \ \ -1 ][cの逆数*j^e≡i^eの逆数\ \ \ (mod\ n)\ \ \ \ \ \ \ \ -2 ]

テーブル { pow(i,-e,n) : i } を構築します。

jを総当たりし、式2を満たすjを見つけることで対応するmを取得します。

以下は公式ソリューションを参考にしたスクリプトです：

from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
def proof_of_work():
    rev = r.recvuntil(b"sha256(XXXX+")
    suffix = r.recv(16).decode()
    rev = r.recvuntil(b" == ")
    target = r.recv(64).decode()
    def f(x):
        hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
        return hashresult == target
    prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 4, 'upto')
    r.recvuntil(b'Give me XXXX: ')
    r.sendline(prefix.encode())
public_exponent = 65537

while True:
    connection = remote("43.129.69.35",10002)
    connection.recvuntil(b'n = ')
    modulus = int(connection.recvline().strip())
    factor_dict = {pow(i,-public_exponent,modulus):i for i in tqdm(range(1,2**20))}
    
    proof_of_work()
    secret = ''
    for i in range(4):
        ciphertext = int(connection.recvline().split(b'=')[1].strip())
        inverse_c = inverse(ciphertext,modulus)
        for j in range(1,2**16):
            s = inverse_c*pow(j,public_exponent,modulus)%modulus
            if s in factor_dict:
                secret += hex(factor_dict[s]*j)[2:].zfill(8)
                break
    print(len(secret),secret)
    if len(secret)!=32:
        connection.close()
        continue
    connection.recvuntil(b"Give me the secret:")
    connection.sendline(secret.encode())
    connection.interactive()

dlp&dsa 問題

これら2つの問題は、筆者のスキル不足により解くことができませんでした。2022年3月29日現在、問題の添付ファイルが見つからず、復現が困難な状況です。