crypto-writeup-public

corCTF 2021 | dividing secrets

corctf2021 discrete_log legendre記号平方剰余 quadratic_residue getstrongprimeはsafe_primeを返すわけではない pohlig-hellman_attack 作問するときに気をつけること

from Crypto.Util.number import bytes_to_long, getStrongPrime
from random import randrange
from secret import flag

LIMIT = 64

def gen():
    p = getStrongPrime(512)
    g = randrange(1, p)
    return g, p

def main():
    g, p = gen()
    print("g:", str(g))
    print("p:", str(p))
    x = bytes_to_long(flag)
    enc = pow(g, x, p)
    print("encrypted flag:", str(enc))
    ctr = 0
    while ctr < LIMIT:
        try:
            div = int(input("give me a number> "))
            print(pow(g, x // div, p))
            ctr += 1
        except:
            print("whoops..")
            return
    print("no more tries left... bye")

main()

$y = g^x \mod p$ というdiscrete logをときたい。 $d$ を入力としてあたえると $g^{\lfloor x / d \rfloor} \mod p$ を計算してくれるオラクルが64回実行できる

一見すると $d$ を $2^k$ としてうまくlegendre記号などを考えることで1bitずつリークできそうに見える。しかしオラクルは64回しか実行できない。

だがさらによくみるとフラグは毎回固定なので64回のオラクルを何回も実行でき、1bitずつリークできるならフラグ全体が読めることがわかる

オラクルについて考えてみる。 $g$ が $\mod p$ において平方剰余でないとき、 $g^x \mod p$ がquadratic residueかどうかをみることで $x$ の偶奇がわかる。とけそう

別解

getStrongPrimeはsafe primeを返すわけではないことを思い出すと、小さい素因数を集めてきてPohlig-Hellman Attackによってdiscrete logが解ける。512bitを復元するに足るまでmodを集めることでオラクルを一切使わずに問題が解ける

#作問するときに気をつけること

別々解

$x<d$ のとき、 $g^{x/d}=1$ となることをオラクルとして二分探索が可能。