[密码学基础][每个信息安全博士生应该知道的52件事][Bristol Cryptography][第22篇]如何用蒙哥马利算法表示一个数字和多个相乘的数字

我会带着你远行 2023-01-22 09:49 87阅读 0赞

> 这是一系列博客文章中最新的一篇，该文章列举了“每个博士生在做密码学时应该知道的52件事”:一系列问题的汇编是为了让博士生们在第一年结束时知道些什么。

### 安全和效率 ###

密码学的目标是设计高度安全的密码学协议,但是同时这些协议也应该被有效率的实现.这样就可以一次一次快速执行而不会因为用户变得而慢下来,例如,在线商场和网络银行都有这种需求.因此我们采取了一些措施来减少加密的成本.这些代价较高的操作就包括正整数模数的算法,因为除法比较费时.

### 模余操作的代价 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

### “蒙哥马利算法空间” ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

### 算法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

### 正确性证明 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

推荐论文（描述+实现）：Bos J W. Montgomery Arithmetic from a Software Perspective\[J\]. IACR Cryptol. ePrint Arch., 2017, 2017: 1057.

转载链接：https://www.cnblogs.com/zhuowangy2k/p/12047839.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221020/a60a7183c07b45d1b29d3364e8fc9955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221020/3b0ce0249bee4912bec50627ef575bfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20221020/96587d20a7a04f7c85ca47e7cbe5e909.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20221020/2bf1399df40c4944a3c2ec1ef2d1d40b.png