Crypto 离散对数

目录
警告
本文最后更新于 2021-02-26,文中内容可能已过时。

Diffie–Hellman

https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

Diffie-Hellman是一种建立密钥的方法,而不是加密方法,这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密,Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。

常规DHKE

1
2
3
4
p = 845529816183328832288826827978944092433
g = 419182772165909068703324756801961881648
g^a = 803331951724823196054726562340183173391
g^b = 382083902245594277300548430928765321436

求解(使用python,之后会写使用sage的办法)

1
2
3
4
5
6
7
8
import sympy
p = 845529816183328832288826827978944092433
g = 419182772165909068703324756801961881648
A = 803331951724823196054726562340183173391
B = 382083902245594277300548430928765321436
a = sympy.discrete_log(p, A, g)
s1 = pow(B, a, p)
print(s1)

ezDLP.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from Crypto.Util.number import *
from secret import FLAG
x=bytes_to_long(FLAG)
g=19
p=335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
h=pow(g,x,p)
print(h)
'''
h=288070582193475001909504295378200207136792251587351353940732202318682297787316601191342803740293641667166030405790174359803117153823317602439095131268330396229766357282227072993762551020587231292702403699516000471057760488787238992958524661312999763977971191744727118996099726307524151950658180747741385736794788110098941750638149275796253703522131736804632723063500938687719097522683840992547780858609532846661500496608942552864025726071593976927296153608998862502203763258458959937321417494481628869857697843269298862073323299759421651863743171274442055473027047992190944504867646064699614791693960085560721167301191728568202176563573179947585717804638241604020251809957303403123410751912133296521062265760540636346584828228233052904346970768897062465951900708331738488958277878087962433719597843503049933458513334644038917633168549393114576139521100421858234859901177191735977751496913701119609377406034509384460669523245603
'''

离散对数问题,英文是 Discrete logarithm Problem,有时候简写为 Discrete log,该问题是十几个开放数学问题(Open Problems in Mathematics, [0.a], [0.b])中的一个

$$y\equiv g^{x}(modp)$$

已知x,g,p,要求k的值是困难的。

但是在一些特殊的值或者比较小的值下,我们可以利用一些算法进行计算,比如这道题就用到了

Pohlig-Hellman 算法,具体介绍可以看https://www.ruanx.net/pohlig-hellman/

注意到

图片

SageMath里面的discrete_log可以直接用于求解

1
2
3
4
5
y = 288070582193475001909504295378200207136792251587351353940732202318682297787316601191342803740293641667166030405790174359803117153823317602439095131268330396229766357282227072993762551020587231292702403699516000471057760488787238992958524661312999763977971191744727118996099726307524151950658180747741385736794788110098941750638149275796253703522131736804632723063500938687719097522683840992547780858609532846661500496608942552864025726071593976927296153608998862502203763258458959937321417494481628869857697843269298862073323299759421651863743171274442055473027047992190944504867646064699614791693960085560721167301191728568202176563573179947585717804638241604020251809957303403123410751912133296521062265760540636346584828228233052904346970768897062465951900708331738488958277878087962433719597843503049933458513334644038917633168549393114576139521100421858234859901177191735977751496913701119609377406034509384460669523245603
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
g = 19
x = discrete_log(mod(y, p), mod(g, p))
print(hex(x))
0%