离散对数

概括一下离散对数的解决方法

离散对数在$y=g^{x} \mod p$求x
椭圆曲线中$Q = k*P$求k
这两个式子比较关键，所以就先摆出来了，下面的方法都是基于这两个式子的

一.求离散对数的方法

BSGS大步小步法

• 原理：令$x = i*m +j$，其中$m = \sqrt{p}$且$i,j\in(0,m)$

有

$y\equiv g^{x}\equiv g^{i*m+j} \mod p$

此时考虑

$y*g^{-mi}\equiv g^{j} \mod p$

于是我们可以先枚举j，将$g^{j}$存到表里，再枚举i，计算$y*g^{-mi}$ 跟表进行碰撞(类似于mitm)，如果得到的值在表中，则对应的i，j满足$x = i*m +j$

• 代码：

def bsgs(g, y, p):
    m = isqrt(p)+1
    S = {powmod(g, j, p): j for j in range(m)}
    gs = powmod(g, p - 1 - m, p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p

• 使用条件： p较小的时候比较容易爆破出来

Pohlig_Hellman

• 原理：
  
• 代码：(不需要手搓，因为discrete_log可以直接利用)

from Crypto.Util.number import *
from sympy.polys.galoistools import gf_crt
from sympy.polys.domains import ZZ
import gmpy2
import random

def Pohlig_Hellman(g, h, p):
    # 模数分解
    p_1 = p - 1
    d, factors = 2, []
    while d*d <= p_1:
        while (p_1 % d) == 0:
            factors.append(d)
            p_1 //= d
        d += 1
    if p_1 > 1:
        factors.append(p)
    factors = [[i, factors.count(i)] for i in set(factors)]

    # 求每个素因子进制下的c_i
    x = []
    for factor in factors:
        c_i_list = []
        for i in range(factor[1]):
            if i != 0:
                beta = (beta * pow(g, -(c_i_list[-1] * (factor[0] ** (i - 1))), p)) % p
            else:
                beta = h
            e1 = pow(beta, (p-1) // (factor[0] ** (i + 1)), p)
            e2 = pow(g, (p-1) // factor[0], p)
            for c_i in (range(factor[0])):
                if pow(e2, c_i, p) == e1:
                    c_i_list.append(c_i)
                    break
        x.append(c_i_list)

    # 将模p_i意义下的p_i进制表示转换为模p_i意义下的十进制
    system = []
    for i, factor in enumerate(factors):
        res = 0
        for j, x_j in enumerate(x[i]):
            res += x_j * (factor[0] ** j)
        res = res % (factor[0] ** factor[1])
        system.append(res)

    # 中国剩余定理
    factors = [factors[i][0] ** factors[i][1] for i in range(len(factors))]
    result = gf_crt(system, factors, ZZ)
    return result


if __name__ == "__main__":
    p = 7863166752583943287208453249445887802885958578827520225154826621191353388988908983484279021978114049838254701703424499688950361788140197906625796305008451719
    a = random.randint(0, 2 ** 512)
    x = random.randint(0, 2 ** 256)
    b = pow(a, x, p)
    print("real_x = {}".format(x))

    res = Pohlig_Hellman(a, b, p)
    print("x1 = {}".format(res))

# sage: p = 7863166752583943287208453249445887802885958578827520225154826621191353388988908983484279021978114049838254701703424499688950361788140197906625796305008451719
# sage: primitive_root(p)
# 13
    g = 13 # p的本原元为13
    u = Pohlig_Hellman(g, a, p)
    v = Pohlig_Hellman(g, b, p)
    try:
        x = gmpy2.invert(u, p - 1) * v % (p - 1)
        print("x2 = {}".format(x))
    except: # u 和 p-1 可能不互素，导致之间没有逆元；该情况将u除以最大公因数使得两者之间互素即可，最后结果除以相应的数即可
        i = 0 
        gcd = gmpy2.gcd(u, p - 1)
        while True:
            if gmpy2.gcd(u, p - 1) != 1:
                u = u // gmpy2.gcd(u, p - 1)      
                i += 1
            else:
                break
        assert gmpy2.gcd(u, p - 1) == 1
        x = (gmpy2.invert(u // gmpy2.gcd(u, p - 1), p - 1) * v) % (p - 1) // (gcd ** i)
        print("x = {}".format(x))

     
"""
a ^ x \equiv b (mod p) 之中a不是原根
real_x = 17475167858715014509948693871106677723065342839264165381680037187400995034209
x1 = 3931583376291971643604226624722943901442979289413760112577413310595676694494454509217307369704071534867821221958389972909818020158235480633350085553499260068
x = 17475167858715014509948693871106677723065342839264165381680037187400995034209
"""

"""
a ^ x \equiv b (mod p) 之中a是原根
real_x = 59538927048508916825466804038603833711975305674466217174924215808245351055236
x1 = 59538927048508916825466804038603833711975305674466217174924215808245351055236
x2 = 59538927048508916825466804038603833711975305674466217174924215808245351055236
"""

• 使用条件：适用于一个由小素数组成的p-1(p为素数时，式子的阶)，且p不能过大

discrete_log

其实discrete_log只是一个函数，而不能被称作一种方法

• 原理：sagemath里面的discrete_log就是利用 Pohlig-Hellman 和大步小步算法实现的
• 代码：

from Crypto.Util.number import *
p = 146808027458411567
a = 46056180
b = 2316783294673
E = EllipticCurve(GF(p),(a,b))
P = E(119851377153561800,50725039619018388)
Q = E(22306318711744209,111808951703508717)

num1 =  discrete_log(Q,P,operation = '+')
print(num1)
#13566003730592612

• 使用条件：满足BSGS大步小步法或Pohlig_Hellman其中一种条件即可

Pohlig_Hellman+discrete_log

在做题的时候发现很多题不能用discrete_log，而使用Pohlig_Hellman，感觉很困惑，其实呢，就是在使用discrete_log前，先使用一次Pohlig_Hellman

• 原理：就是使用Pohlig_Hellman将大数分解成好几个小数，来达到降阶的效果，再使用discrete_log来求解(我的理解就是类似于使用了两次Pohlig_Hellman的感觉)
• 代码：

def r(h, g, N, p, qi):
    """
    N : p-1
    qi: N中的素因子
    """

    Zp = Zmod(p)
    h = pow(h, N//qi, p)
    g = pow(g, N//qi, p)
    ri = discrete_log(Zp(h), Zp(g))
    return int(ri)

for qi in tmp_list:
    tmp = r(c,m,n-1,n,qi)
    print(tmp)
    r_list.append(tmp)
x = crt(r_list, tmp_list)
#########################################椭圆曲线
def Pohlig_Hellman(n,P,Q): # n为阶，Q = k * P
    factors = list(factor(n))
    m = 1
    moduli = []
    remainders = []
    print(f"[+] Running Pohlig Hellman")
    print(factors)
    for i, j in factors:
        if i > 10**9: # 把过大的数过滤掉，防止计算不出
            print('不考虑的数：',i)
            break
        mod = i**j
        g2 = P*(n//mod)
        q2 = Q*(n//mod)
        r = discrete_log(q2, g2, operation='+')
        remainders.append(r)
        moduli.append(mod)
        m *= mod
    r = crt(remainders, moduli)
    return r

• 使用条件：当p较大且能拆解出来较大素数的时候

cado-nfs

• 原理：
  
• 条件：应该是目前能解离散对数最好的办法

./cado-nfs.py -dlp -ell 22345678901234567830123456789012345678901234567890123456807 target=49341873303751285095603174930981210164964894155978049874920 223456789012345678301234567890123456789012345678901234568071

其他

sagemath中可以直接使用求解离散对数的其他函数(实在没有办法的时候可以尝试)
参数说明：求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是+与*，默认为*；bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。

discrete_log_rho(a,base,ord,operation)
discrete_log_lambda(a,base,bounds,operation)

二.例题

[第五空间 2021]ecc

print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)



def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)

'''
Try to solve the 3 ECC
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)
'''

只写一下第二关的wp吧，这里注意用的P.order()，因为咱们求的是$Q = k*P$ ,而不是$P =k*G$所以不用E.order()

from Crypto.Util.number import *
p = 1256438680873352167711863680253958927079458741172412327087203
a = 377999945830334462584412960368612
b = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[a,b])
P = E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
# Q = k * P
def Pohlig_Hellman(n,P,Q): # n为阶，Q = k * P
    factors = list(factor(P.order()))
    m = 1
    moduli = []
    remainders = []
    print(f"[+] Running Pohlig Hellman")
    print(factors)
    for i, j in factors:
        if i > 10**9: # 把过大的数过滤掉，防止计算不出
            print('不考虑的数：',i)
            break
        mod = i**j
        g2 = P*(n//mod)
        q2 = Q*(n//mod)
        r = discrete_log(q2, g2, operation='+')
        remainders.append(r)
        moduli.append(mod)
        m *= mod
    print(remainders)
    print(moduli)
    r = crt(remainders, moduli)
    return r

x = Pohlig_Hellman(n,P,Q)
print(x)
print(x*P)

来源未知

import hashlib
from Crypto.Util.number import *
secret = getPrime(128)
m = getPrime(128)
n = getPrime(1024)
c = pow(m, secret, n)
flag = "flag{"+hashlib.md5(str(secret).encode()).hexdigest()+"}"
print("m = %d" % m)
print("n = %d" % n)
print("c = %d" % c)
# m = 211060723077960779250044744266141176829
# n = 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119974022969989259739901207135911877936187
# c = 32977205552939587326066964781587345932834856116807593874246357335611184723568494377764636367075033866504466671442418777279691941123340914970584204650416137940499348297233941269700668358058974528742129237158207741614517093787264725738282484698794547919205696467463725584733972956537910246421504887816202122161

import hashlib
m = 211060723077960779250044744266141176829
n = 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119974022969989259739901207135911877936187
c = 32977205552939587326066964781587345932834856116807593874246357335611184723568494377764636367075033866504466671442418777279691941123340914970584204650416137940499348297233941269700668358058974528742129237158207741614517093787264725738282484698794547919205696467463725584733972956537910246421504887816202122161
tmp_list = [659, 144811523, 158091863, 167642023, 194814973]

def r(h, g, N, p, qi):
    """
    N : p-1
    qi: N中的素因子
    """
    Zp = Zmod(p)
    h = pow(h, N//qi, p)
    g = pow(g, N//qi, p)
    ri = discrete_log(Zp(h), Zp(g))
    return int(ri)
r_list = []
for qi in tmp_list:
    tmp = r(c,m,n-1,n,qi)
    print(tmp)
    r_list.append(tmp)
x = crt(r_list, tmp_list)

module = 1
for i in tmp_list:
    module *= i  
while True:
    if int(x).bit_length()>128:
        print('fail')
        break
    if int(pow(m, x, n))==c:
        print('x =', x)
        flag = "flag{"+hashlib.md5(str(x).encode()).hexdigest()+"}"
        print(flag)
        break
    x += module
# crt结果：425215994037823111210955984648839730 nbits() = 119
# x = 256148714020855512578941590011688772421
# flag{bbb04cf5180893e23e559c63ceae5b8f}

本文参考：
记ECC例题
密码学——离散对数问题(DLP)
Cado-nfs使用
Pohlig-Hellman算法解决DLP问题

文中的一些想法，如果哪里有问题，也希望师傅们指正，探讨