Diffie-Hellman密钥交换算法

Crypto学习记录 Diffie-Hellman

Created At : 2023-05-01 14:50

Count:882 Views 👀 :

介绍
算法过程
例题
1. 代码分析
2. 解题过程
总结

介绍

Diffie-Hellman密钥交换算法是一种密钥协商协议，它能够让两个通信方在不共享密钥的情况下，通过公开交换的信息来协商生成一个共享密钥。该算法的基本思想是利用离散对数问题的难度，使得攻击者无法推断出通信双方协商出的共享密钥。

算法过程

通信双方$Alice和Bob$协商一个大素数$p$和一个原根$g$。
Alice选择一个私有密钥a，并计算出公钥$A = g^a mod p$。
Bob选择一个私有密钥b，并计算出公钥$B = g^b mod p$。
$Alice和Bob$分别将自己的公钥$A和B$发送给对方。
$Alice$计算出共享密钥$K = B^a mod p$。
$Bob$计算出共享密钥$K = A^b mod p$。

例题

from sage.all import *
from Crypto.Util.number import *
from secret import Alice_secret, Bob_secret, FLAG
import random

f = open('output', 'w')

N=0x2be227c3c0e997310bc6dad4ccfeec793dca4359aef966217a88a27da31ffbcd6bb271780d8ba89e3cf202904efde03c59fef3e362b12e5af5afe8431cde31888211d72cc1a00f7c92cb6adb17ca909c3b84fcad66ac3be724fbcbe13d83bbd3ad50c41a79fcdf04c251be61c0749ea497e65e408dac4bbcb3148db4ad9ca0aa4ee032f2a4d6e6482093aa7133e5b1800001
g = 2

A = power_mod(g, Alice_secret, N)
f.write("Alice send to Bob: {{ 'g': {g}, 'A': {A} }}\n".format(g=g, A=hex(A)))
B = power_mod(g, Bob_secret, N)
f.write("Bob send to Alice: {{'B': {B} }}\n".format(B=hex(B)))

shared_secret = pow(A, Bob_secret, N)

p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a=-3
b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984
E = EllipticCurve(GF(p), [a, b])
G = E.random_point()
Pa = shared_secret * G
f.write(f"Alice send to Bob: {{ 'E': {E}, 'G': {G.xy()}, 'Pa': {Pa.xy()} }}\n")

k = random.randint(2, p)
m = E.lift_x(Integer(bytes_to_long(FLAG)))
P1 = k * G
P2 = k * Pa
c = m + P2
f.write(f"Bob send to Alice: {{ {P1.xy()}, {c.xy()} }}\n")

代码分析

可以看到下面这部分就是DH算法的基础过程：

N = ...
g = 2

A = power_mod(g, Alice_secret, N)
f.write("Alice send to Bob: {{ 'g': {g}, 'A': {A} }}\n".format(g=g, A=hex(A)))
B = power_mod(g, Bob_secret, N)
f.write("Bob send to Alice: {{'B': {B} }}\n".format(B=hex(B)))

shared_secret = pow(A, Bob_secret, N)

接着构造了一个在域p下的，系数为a、b的椭圆曲线：

p = ...
a = -3
b = ...
E = EllipticCurve(GF(p), [a, b])
G = E.random_point()#作用是随机选择一个椭圆曲线E上的点G作为基点。
Pa = shared_secret * G#公钥

再解释下面这部分代码：

k = random.randint(2, p)
m = E.lift_x(Integer(bytes_to_long(FLAG)))
#在曲线上找到一点，该点x坐标等于flag转整数
P1 = k * G
P2 = k * Pa
#基点和公钥分别乘上k
c = m + P2
f.write(f"Bob send to Alice: {{ {P1.xy()}, {c.xy()} }}\n")#输出P1和c的x、y坐标

解题过程

已知条件：

$P1 = k*G$
$P2 = k*Pa$
$Pa = sharedsecret*G$

又$c = m + P2 \Rightarrow m = c - P2 = c - ksharedsecretG $

$\Rightarrow m = c - P1*sharedsecret$

单独解释求解Bob_secret从而解出shared_secret：

可以看到N的位数是00001，可以想到N-1比较光滑（指模数N-1的质因数分解中包含了较小的质数，N-1尾数为00000，含较小质数2），从而可以运用Pohlig-Hellman算法来解离散对数问题（DLP），sympy.discrete_log这个函数使用了这个算法。

代码：

N = ...
g = 2
A = ...
B = ...

p = ...
a = -3
b = ...

#Bob_secret = sympy.discrete_log(N,B,g)
#shared_secret = pow(A, Bob_secret, N)
Bob_secret = 523395080617584542626887374797915530377197776414307699064494325754883865689240606662282052952769155869279302851357127396057956141700522707614969003724858649469855458912748021620773222294584347455737042066389082761054791847391943575954645806724433924897674867376454396257875249718213145700160788809038411884417511593659507
shared_secret = 210079986310539059026469300720655426951919393335485123618687987029746658763798439576376646226161293006261472023436870446704160814487044427272498126726277523426054334489402918696632471053566567964288295442264373353184045686758631952518445700562724692050307270259376021103356466045824174058551054535796277627154836626119222585862131679625673279898703654

E = EllipticCurve(GF(p), [a, b])
P1 = E((2032638959575737798553734238953177065671021112450002471824225734491735604600003028491729131445734432442510201955977472408728415227018746467250107080483073647, 3510147080793750133751646930018687527128938175786714269902604502700248948154299853980250781583789623838631244520649113071664767897964611902120411142027848868))
c = E(6670373437344180404127983821482178149374116817544688094986412631575854021385459676854475335068369698875988135009698187255523501841013430892133371577987480522, 6648964426034677304189862902917458328845484047818707598329079806732346274848955747700716101983207165347315916182076928764076602008846695049181874187707051395)
P2 = shared_secret*P1
m = (c-P2)[0]#去x坐标
print(long_to_bytes(m))

总结

学习了Diffie-Hellman算法，但目前来说只能是了解了吧，还需要不断学习。同时再次熟悉了ECC。对光滑数和Diffie-Hellman算法有了进一步了解。

参考：2023 hgame crypto wp 全 - App1e_Tree - 博客园 (cnblogs.com)

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com