Pohlig-Hellman Attack - crypto-writeup-public

離散対数問題に対するアプローチの一つ。 DLPでもECDLPでも同じアルゴリズムが適用できる。

DLPに対するPohlig-Hellman Attack

前提として、巡回群 $G$ の位数 $\phi$ が次のように素因数分解可能であるとする。よくあるのは素数 $p$ を法とする乗法群で、その位数は $p-1$ なので、 $p-1$ がB-smoothな場合。

$\phi = \prod_i p_i^{e_i} = \prod_i q_i$

この場合に $h \equiv g^x$ の代わりに $h^{\frac{\phi}{q_i}} \equiv g^{x\frac{\phi}{q_i}}$ を考える。

$x = a_iq_i + b_i$ と表されるとすると、オイラーの定理より、 $g^{a_i\phi} \equiv 1$ となるので、

$h^{\frac{\phi}{q_i}} \equiv g^{b_i\frac{\phi}{q_i}}$

$h_i := h^{\frac{\phi}{q_i}}, g_i := g^{\frac{\phi}{q_i}}$ と置き直すと $h_i \equiv g_i^{b_i}$ という形のDLPが導ける。

$g_i^{b_iq_i} = g_i^{b_i\phi} \equiv 1$ より、 $g_i$ を生成元とした巡回群の位数は $q_i$ なので、もともとの $h \equiv g^x$ をBaby step Giant stepで解こうとすると $O(\sqrt{\phi}\log\phi)$ かかっていたのに対して、 $h_i \equiv g_i^{b_i}$ は $O(\sqrt{q_i}\log{q_i})$ で解ける。当然 Pollard's Rhoとかでもいい

このようにして求めた各 $b_i$ について、 $x = a_iq_i + b_i \to x \equiv b_i \mod q_i$ より、CRTで $x \mod \phi$ を復元することができる

実装。ちなみにsageのdiscrete_logはpohlig-hellman + BSGSらしいので、こんなことをしなくても脳死でdiscrete_log呼べばよい（※そうでもなくて、sageのdiscrete_logは素因数分解できた全部でbsgsやろうとするから、最後の一素因数についてはやらなくていい、みたいなばあいは手動で実装する必要があるのだった）

from Crypto.Util.number import *
from sage.all import *
def gen_weak_prime(size, smooth):
    """
    generate approximately size-bit prime p
    which p-1 factorized to p_1 * p_2 * ... * p_n and p_n is up to smooth-bit
    (it means that p-1 is <smooth>-smooth number)
    """
    p = 2
    while True:
        if p.bit_length() + smooth >= size:
            p *= getPrime(size - p.bit_length())
            if isPrime(p + 1):
                return p +1
            p = 2
        else:
            p *= getPrime(smooth + 1)
# generate params
p = gen_weak_prime(512, 32)
g = getRandomRange(2, p)
x = getRandomRange(2, p) # this is secret
h = pow(g, x, p)
# solve
factors = [f[0]**f[1] for f in factor(p-1)]
print("[+] factors: {}".format(factors))
# pohlig-hellman
bs = []
mods = []
for f in factors:
    k = (p-1)//f
    b = discrete_log(pow(h,k,p), pow(g,k,p), ord=f)
    bs.append(b)
    mods.append(f)
# recover using Chinese Remainder Theorem
y = CRT(bs, mods)
print("[+] {}".format(x == int(y)))
# check if sage is able to solve
g = Mod(g, p)
h = g**x
print("[+] {}".format(discrete_log(h, g) == x))

def pohlig_hellman(g, h, p, limit=100000):
    factors = [f[0]**f[1] for f in (p-1).factor(limit=limit) if f[0] <= limit]
    bs = []
    mods = []
    for f in factors:
        k = (p-1)//f
        b = discrete_log(pow(h,k,p), pow(g,k,p), ord=f)
        bs.append(b)
        mods.append(f)

    return CRT(bs, mods)

ECDLPに対するPohlig-hellman attack

picoctfのECC2という問題

#  Elliptic Curve: y^2 = x^3 + A*x + B mod M
#  M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
#  A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
#  B = *You can figure this out with the point below :)*
#
#  P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
#  n = *SECRET*
#  n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)
#
#  n < 400000000000000000000000000000
#
#  Find n.

from sage.all import *

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
Px, Py = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

_, b = PolynomialRing(GF(M), name="b").objgen()
f = Px**3 + Px*A + b - Py**2
B = Integer(f.roots()[0][0])

EC = EllipticCurve(GF(M), [A, B])
P = EC((Px, Py))
Q = EC((61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440))

order = EC.order()
factors = list(factor(order))
mods = []
zs = []
cur = 1

bound = 400000000000000000000000000000

for factor in factors:
    p, e = factor
    pe = p**e
    Pi = (order // pe) * P
    Qi = (order // pe) * Q
    zi = Pi.discrete_log(Qi)

    zs.append(zi)
    mods.append(pe)

    cur *= pe
    if cur > bound:
        break

print(CRT(zs, mods))