python实现Diffie-Hellman密钥交换算法

timerring

发布于 2022-07-20 14:41:20

1.4K0

文章被收录于专栏：TechBlogTechBlog

Program : Diffie–Hellman key exchange (on group)

In this part, you are required to implement the Diffie–Hellman key exchange algorithm in

\mathbb{Z}_p

from scratch. (Hint: review the procedure of ElGamal algorithm). As the Setup procedure is the same as ElGamal algorithm, it is assumed that the public parameters of

and

\alpha

are both set to constants in this part.

p: 11483166658585481347156601461652228747628274304826764495442296421425015253161813634115028572768478982068325434874240950329795338367115426954714853905429627
alpha: 9312361210673900259563710385567927129060681135208816314239276128613236057152973946513124497622387244317947113336161405537229616593187205949777328006346729

In this program, two parties, Alice and Bob, want to get a symmetric key for future symmetric encryption via Diffie–Hellman key exchange, and hope that adversaries learn nothing about the shared symmetric key. In this program, it is assumed that only Honest-but-Curious adversaries exist.

Your program will output the following items:

All the transmission data on the communicate channel (in correct order, if necessary), e.g. Alice to Bob: blah blah blah.
The symmetric key that Alice gets, that is the result of Diffie–Hellman key exchange.
The symmetric key that Bob gets, that is the result of Diffie–Hellman key exchange.

Example Output

Alice to Bob: 8940959903919892646369383076988236263414149283589789417534093823879702643730138301746710316972043367005133179322397075568692734123174632487566957931486431
Bob to Alice: 4384683352873557635562368964248068727038294529254597987180258684651520296204501642442796366842225710992904070529210926322430373646688781391733323295711438
Result (Alice view): 11340178546045069617516325240966622435238310460224925781433563012664618800006804703149537436309299281476260328893892580363729101975655852342449233799172983
Result (Bob view): 11340178546045069617516325240966622435238310460224925781433563012664618800006804703149537436309299281476260328893892580363729101975655852342449233799172983

solution code

import random

p: int = 11483166658585481347156601461652228747628274304826764495442296421425015253161813634115028572768478982068325434874240950329795338367115426954714853905429627
alpha: int = 9312361210673900259563710385567927129060681135208816314239276128613236057152973946513124497622387244317947113336161405537229616593187205949777328006346729


# 快速模幂函数:
def quick_mod(in_a: int, in_b: int, in_p: int) -> int:
    in_a %= in_p  # 预处理
    ans = 1  # 记录结果
    while in_b != 0:
        if in_b & 1:
            ans = (ans * in_a) % in_p
        in_b >>= 1  # 移位操作
        in_a = (in_a * in_a) % in_p
    return ans


da: int = random.randint(1, p - 1)
pa: int = quick_mod(alpha, da, p)
print('Alice to Bob:', pa)

db: int = random.randint(1, p - 1)
pb: int = quick_mod(alpha, db, p)
print('Bob to Alice:', pb)

k_Alice: int = quick_mod(pb, da, p)
print('Result (Alice view):', k_Alice)

k_Bob: int = quick_mod(pa, db, p)
print('Result (Bob view):', k_Bob)

output

Alice to Bob: 5401715652811798129297331183196252248450609218063188670304313143373208976703187421383700793089900140600880484160655782279227609131431659730556049081414488
Bob to Alice: 10381154167090192760107089673416704448415008747056849721982037743379509557693524847560794289113004966742132559903754830205621033822324882161216780933705183
Result (Alice view): 8104765534365036719551043733060004916489593108004314113023589709245844912143607805211963817440317208929064111677451038766659888032127613276974880121512400
Result (Bob view): 8104765534365036719551043733060004916489593108004314113023589709245844912143607805211963817440317208929064111677451038766659888032127613276974880121512400

进程已结束，退出代码为 0