cryptography - 如何计算具有大质数的大数的模数？

Question

我正在软件环境中使用椭圆曲线加密技术。我想咨询如何有效地实现大数对大质数的模运算。例如(192位数) mod (192位梅森素数)

如果有任何技巧或算法可以引用，那将非常有帮助，因为我正在处理资源受限的传感器节点。

Answer 1

没有192位Mersene prime ，正如问题中所考虑的那样。

实现 192 位整数 x 模另一个 192 位素数 p 的模约简非常简单:结果是 x 当x<p，否则 x-p。

也许真正的问题是关于有效的模约简模一个更大数量的 192 位素数 p，对于椭圆曲线密码学中常用的素数 p。这样的素数通常以允许有效模约简的方式选择。例如，对于 P-192，质数模 p 为 specified是 6277101735386680763835789423207666416083908700390324961279 这是 ffffffffffffffffffffffffffffffffffffffffffffffffff_h 或 2¹⁹²-2⁶⁴-1。这个 p 非常接近 (2³²)⁶，以至于在以 2³² 为基数时，商的估计模块化缩减中的数字模 p 非常容易，就像在执行教科书时估计新数字一样 Euclidian division以 10 为基数计算 999899 很容易:大多数时候，被除数最左边的数字就是商的新数字。