警告
本文最后更新于 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}~(mod~p)$$
已知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))
|
wjh 收录于 Crypto