1

我正在尝试使用汇编在 PIC16 微控制器中实现 RSA！
我写了一个数学库，可以执行加法、减法、乘法和模幂运算（都是无符号的）。

但现在我坚持找到满足以下条件的“d”的最后一步：
d*e = 1 (mod phi(n))
我想避免实现扩展的欧几里得算法，它有点复杂并且需要有符号的操作。

我尝试使用欧拉定理http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem
计算它， 但是我需要找到 phi(phi(n) 这是一个复杂的过程，除非 p 和 q 是安全的素数。

我剩下的唯一选择是循环 d=(KN+1)/e 同时改变 k 直到 (KN+1) mod e = 0
所以我现在的问题是：最后一个公式是计算 d 的唯一其他选择吗?
（如果没有）还有哪些其他选择？
K 的限制是什么？

4

1 回答 1

1

您可以实现二进制扩展欧几里得算法。该算法可以在应用密码学手册 - 第 14.4.3 章中找到。它只需要多精度的加法、减法和移位。注意：14.64 描述了如何优化算法以获得乘法逆 -(d)在这种情况下。

通常为 选择一个相对较小且汉明权重较低的素数(e)，例如(65537)。由于gcd(65537, phi(n)) = 1，乘法逆将始终存在。

于 2014-03-29T00:42:44.867 回答