为什么RSA使用不动点类型数字？

Question

为什么RSA使用定点数字而不是浮点数？是否有太多浮点实现可供选择？定点算法是否增加了因式分解的难度？或者是别的什么东西？

浮点的额外复杂性不是会增加算法的安全性吗？

Answer 1

为什么RSA使用不动点类型数字？

从技术上讲，RSA是在等价类的残差类上运行的，定义为“两个整数是等价的”是“它们共享相同的余数”。

这些类仅由整数填充，因此RSA操作不需要浮点存储类型。因此，浪费空间对指数进行排序是没有意义的，因为它是不需要的--即使是大整数也可以使用任意精确的算术库存储在内存中--例如，如果将整数分成32位块或4个字节，则只需要128个4字节块来存储该整数，即512字节。

这是不是因为只有不动点算法提供了因式分解的困难？

当您开始定义其他集合时，分解变得更加复杂。例如，在某些构造下，一个数可以是不可约的，但不是素数。

由于RSA在我们所知道和理解的最简单的集合(整数)下工作得很好，除非我们需要它，否则没有必要引入额外的复杂性。

Answer 2

浮点数是实数的近似值。它们适用于连续式计算，在这种情况下，输入的微小变化会导致输出的小变化。

密码学通常涉及到从连续中得到的尽可能多的计算。无论两个不相同的消息有多么相似，它们都不应该有相似的散列，或者相似的签名，或者类似的加密。浮点完全不适合这一点。

密码学通常涉及某种看上去不可逆转的扰码，只有在一个秘密密钥的情况下才能逆转(或者根本不能)。自然过程往往是连续的，因此是可逆的。混沌过程的过去无法计算，它倾向于在某个点涉及整数--通常是多次迭代或循环，每次迭代时都会碰到或忽略一个阈值。整数是不可逆性产生的方式。

密码运算的结果必须是可复制的。例如，解密过程必须精确地逆转加密过程。浮点数在那里处于劣势，因为对它们的操作往往在不同的处理器体系结构之间存在差异。

许多密码学，包括RSA，都依赖于整数的“nice”属性，这些属性通常与可除性(基本上是整数的一个属性)有关。浮点数没有使算法工作的属性。

复杂性并不能保证密码算法的安全性。这是数学性质的组合，也是没有人找到办法打破它们的组合。浮点计算绝对没有什么可获得的，正如我们所看到的，还有很多损失。