\mathbb{Z}_p

Zp​ 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

p

p

p 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