Python实现Diffie-Hellman密钥交换大模数n计算卡死问题排查

程序卡死不是异常故障，是你写的模幂运算逻辑复杂度过高：(g ** a) % n的执行逻辑是先完整计算g^a的全部值，再对n取模。当指数a的取值随n增大到2^20以上时，g^a的结果会达到数百万到数亿位长度，内存占用和计算量会指数级上升；如果n取2048比特安全长度，a也是2048比特量级的数，g^a的数值规模是现有通用计算能力不可能完成存储和计算的，表现出来就是程序停止响应。

Python标准库内置了优化实现的快速模幂算法，通过三参数pow()函数调用即可使用。该函数在运算过程中每一步都会取模，始终把数值控制在模数n的长度范围内，哪怕4096比特级别的参数也能毫秒级完成计算，完全不依赖第三方库，符合原生实现要求。
你只需要修改两处代码即可解决卡死问题：

• 在generate_partial_key()函数中，把b = (g ** a) % n替换为b = pow(g, a, n)
• 在find_shared_key()函数中，把shared_key = (partial_key ** private_key) % n替换为shared_key = pow(partial_key, private_key, n)

修复性能问题后，你的代码还有几个逻辑错误和安全缺陷：

• DH公共参数选择不符合密码学要求：模数n必须为大素数，生成元g需要是模n的原根，你当前使用n = 2**20是合数，不满足DH密钥交换的数学前提，会导致密钥交换逻辑完全失效，无安全性可言。练习场景下可以自行实现Miller-Rabin素性检测算法生成符合长度要求的素数n，再计算对应原根g。
• 私钥取值范围错误：DH私钥的合法取值区间是[1, n-2]，当前代码用random.randint(1,n)可能生成值为n的私钥，此时模运算结果为0，会直接泄露密钥。
• 加解密逻辑有bug且无实际安全性：
  • 用明文字符编码乘共享密钥的方式加密是线性变换，没有任何保密能力，仅可作为编程练习使用，绝对不能用于实际场景
  • 解密时使用/做除法会返回浮点数，大整数运算下会出现精度丢失，应该使用整数除法//；如果要做正确的乘法类加密，需要计算共享密钥模对应素数的逆元来做解密运算
  • 解密时输入的加密消息分割后，每个元素前后可能带空格，直接转int会报错，需要先做空白字符裁剪处理

内容的提问来源于stack exchange，提问作者Remsforian