Python實現DH密鑰協商算法中的解密過程

發表於 | 分類於

DH密鑰協商是一種建立密鑰的方法，而不是加密方法，由White field與Martin Hellman在1976年共同提出。下文先簡要介紹DH密鑰協商的原理，再介紹如何使用Python進行解密。

建立密鑰

任取大質數$q$，所有的運算都在$\mathbb Z_q$中進行。

假設發送方為Alice，接收方為Bob，雙方約定公開的DH參數$(q,g)$。

Alice選擇私鑰$a$，並計算公鑰$A=g^a\ ({\rm mod}\ q)$。

Bob選擇私鑰$b$，並計算公鑰$B=g^b\ ({\rm mod}\ q)$。

Alice和Bob分別通過$s=B^a\ ({\rm mod}\ q)$和$s=A^b\ ({\rm mod}\ q)$計算密鑰$s$。（由$B^a=g^{ab}=A^b\ ({\rm mod}\ q)$可確保Alice和Bob計算出的$s$是相同的）

  • $q,g,A,B$是公開的，$a$只有Alice知道，$b$只有Bob知道。

解密

DH密鑰協商只能通過遍歷解密，即對$a$（或$b$）進行從$1$至$q$的遍歷並逐一驗算是否滿足$A=g^a\ ({\rm mod}\ q)$。

代碼如下（其中的EEA和SAM已在《Python實現RSA算法的解密》中提及，不再贅述）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def eea(a,b): 
    x,x1=1,0
    y,y1=0,1
    r,r1=a,b 
    if b==0: 
        return a,1,0  
    while r1!=0:
        q=r//r1
        r,r1=r1,r-q*r1
        x,x1=x1,x-q*x1
        y,y1=y1,y-q*y1
    # r is gcd(a,b)
    # ax+by=r
    return r,x,y
def sam(a,e,n):
    k=len(bin(e))-2
    remainder=1
    x=a 
    for i in range(k): 
        if bin(e)[-i-1]=="1": 
            remainder*=x 
        x=x**2%n 
    return remainder%n
def dhke(q,g,A,B,limit): 
    a=1
    while sam(g,a,q)!=A and a<=limit: 
        a+=1
    if a>limit:
        return None 
    return sam(B,a,q)

例題

假設Alice和Bob通過DH密鑰協商交換了$(q,g,A,B)$，求生成的密鑰$s$。特別地，${\rm log}_gA,{\rm log}_gB\leqslant 10^4$。$(q,g,A,B)$如下：

1
2
3
4
q=179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227998859
g=3
A=112983575163002618947589666666735428181684517845144875096902910066434723952623016603393212501214127399908823223492478725971266042754892798177781267512821607470545283059472689034731313027619864228688466438258327552045437590203790635506728603774799021127049872571983254506993921153718739796769296097404717448108
B=111772767805210239496365191691516881043394988196297062013853646674574743401042736447328886156429629192691601526398366088012736749454626686281467579205675084461989494513294624066074137247913037330040487275346913253345733429767781900977102687185378411660147190296412313303321533586102552123457499563789255321369

使用代碼

1
print(dhke(q,g,A,B,10000))

可得

1
s=10828112783453462381041707802056149866596392072243903940987459672779260675319522663099080388770903982546250524992420350200207624327420612300170620802665302905750045777684348125827484365007590718638373187936889967309324722655294992225815410914105072210725045953105019352457540772995508978315699107247398350128
0%