Diffie-Hellman算法

参考文章：

https://fishni.github.io/2021/03/16/Crypto-02-Diffie-Hellman%EF%BC%88DH%EF%BC%89%E5%AF%86%E9%92%A5%E4%BA%A4%E6%8D%A2/

Diffie-Hellman算法

秘钥交换算法 是一种建立秘钥的方法，而不是加密方法，所以一般需要结合其他一种加密算法使用

幂模运算

整数b(底数)的e次方(指数) 除以正整数m(模) 所得的余数c 称为幂模

DHKE协议的过程

下面两个图相对很好理解

原根： https://blog.csdn.net/dreamzuora/article/details/52744471

假设一个数 g 是P的原根，那么 g^i mod P 的结果两个不同，且有 g∈(1,P) i∈(1,P) 那么g可以称为P的一个原根

即 g^i mod p ≠ g^j mod p (p为素数) 且 i≠j i,j∈(1,p-1) 则g为p的原根

光滑数：可约数分解为小素数乘积的正整数

一般来说 素数600位以上时，很难被破解。当素数较小时，存在暴力破解的风险

例题

My buddies Whitfield and Martin were trying to share a secret key between themselves, and I was able to eavesdrop on their conversation. I bet I could probably figure out their shared secret with a little math…

p = 69691
g = 1001
A = 17016
B = 47643

Note: submit either the shared secret or the shared secret wrapped in utflag{}

g^i mod p = A -> i (b)

g^i mod p = B -> i （a)

分别算出 A B的私钥i i取值在 1~p

K = B^a mod p = A ^ b mod p
 
pow(B,a,p) pow(A,b,p)
 
p=69691
g=1001
A=17016
B=47643
 
# g^i mod p  = A   -> i
# g^i mod p = B   -> i
# 分别算出 A B的私钥i    i取值在 1~p
# K = B^a mod p = A ^ b mod p
# K = pow(B,a,p)    K = pow(A,b,p)
 
for i in range(p):
    if pow(g,i,p) == A :
        print("a:",i,"\t K=",pow(B,i,p))
        break
 
for i in range(p):
    if pow(g,i,p) == B:
        print("b:",i,"\t K=",pow(A,i,p))
        break
         
# a: 12552   K= 53919
# b: 7919    K= 53919

flag_exchange 【 这个还是不太懂 后面学明白了再回来看】

看完这道例题 就稍微有点印象了 当然不是完全懂 再看下对应的题目

之前的moectf flag_exchange 也是使用该加密算法

from Crypto.Util.number import isPrime
from random import getrandbits
  
with open("flag.txt","rb") as fs:
    flag = fs.read().strip()
  
def diffie_hellman(p, flag):
    alice_privKey = getrandbits(1024)
    alice_pubKey = pow(7, alice_privKey, p)
    bob_privKey = getrandbits(1024)
    bob_pubKey = pow(7, bob_privKey, p)
    # aK =  7^ak mod p
    # bK =  7^bk mod p
  
    superkey = pow(bob_pubKey, alice_privKey, p)
    # K = bK ^ ak mod p
    m = int.from_bytes(flag, 'big')
    return (m * superkey) % p, alice_pubKey, bob_pubKey
     
    # m*SK mod p    aK     bK
  
  
from typing import Callable
  
def chall(input:Callable[[str],None], print:Callable[[str],None]):
    p = int(input("P = "))
    # 大素数p
    if isPrime(p) and p.bit_length() >= 1024:
        c, alice_pubKey, bob_pubKey = diffie_hellman(p, flag)
        #  c = m*SK mod p  =>  m = c*Sk^-1 mod p
         
        print("Alice's public key: {}".format(alice_pubKey))
        print("Bob's public key: {}".format(bob_pubKey))
        print("Ciphertext: {}".format(c))
    else:
        print("Invalid P")

生成一个光滑素数p

g = 7

B = 7 ^ b mod p
A = 7 ^ a mod p 
这里的 A B 是由自定义a  b 计算而来

随后可得superkey 
SK = B^a mod p 
算出superkey 
#  c = m*SK mod p  =>  m = c*SK^-1 mod p
m即flag

WP 有点看不懂 感觉A B c是自己定义生成的 如果是自己生产的话 那就比较好理解

#sage
import gmpy2
from Crypto.Util.number import *
 
# 构造一个很光滑的p，即p可以分解成许多小素数之积
p = 1
i = 2
while isPrime(p+1) ==False or p.bit_length()<1024 :
    p *= i
    i = gmpy2.next_prime(i)
 
#print(p+1) 取p+1为对应素数p
# A B c ??? 感觉像是自己构造生成的
 
g = 7
p = 20404068993016374194542464172774607695659797117423121913227131032339026169175929902244453757410468728842929862271605567818821685490676661985389839958622802465986881376139404138376153096103140834665563646740160279755212317501356863003638612390661668406235422311783742390510526587257026500302696834793248526734305801634165948702506367176701233298064616663553716975429048751575597150417381063934255689124486029492908966644747931
A = 20336091449271352050000450320351597189353592062279377142884247684088072216754371140723688503847322269500056016823378486967669507529408071986247421480538070427020298314420596325895121922786822444746298488308935254197730980462214370281102952073051791017954008911348128021296665124600273965642418702110947948173149809724203543773244607616601110670126605337319276524135448598308833199821995622969372761107826550795621362415457182
B = 3016038452071464751422492594184606815201979377859418872430468328543181786920301668755954977729921559697635702877324759319811639923934643618711315555467453055288843246623654939387741368313873206560664229687375070952935800932126812264287402142801364732994539469801252414404987968911552061069354407508916590343552775560281691608737262245571829068155383159065889848197300894149747651679644288337413872066182471443965426404626423
c = 8101058129734054038632640353434785588447342802920921913999474154497466343094694993166042668700504613189281291125022077749043805204765309971981658929422844998392130190493145455241084775180221325627765838099393607299071835294706132501949635214088146102721237571159346281928107966372652823580266088579392328383545323322931789769149936581855383571990955947284354676448353798975087410774586309247023597516943906734455833918792577
 
a = discrete_log(mod(A,p),mod(g,p))
 
b = discrete_log(mod(B,p),mod(g,p))
# print(a)
# print(b)
 
superkey = pow(B, a, p)
 
p = gmpy2.mpz(p)
superkey = gmpy2.mpz(superkey)
 
d = gmpy2.invert(superkey,p) % p
m = c*d % p
print(long_to_bytes(int(m)))