没有动态分配的RSA的实现

典型的RSA实现包含多精度整数库。典型的多精度整数库使用动态分配将大整数表示为正确大小的机器字数组。

我希望在使用多精度整数时，只有加密或解密已知长度的消息（通常是对称加密密钥）时才会遇到数学整数的限制，例如RSA-2048，它会是可以通过静态地或在堆栈上为所有必要的中间结果分配空间来实现算法。

我发现这个论坛post暗示这是可能的。它不表示最大整数大小。也许这很明显（“所有整数都需要2048位，呃！”）。无论如何，如果有的话，我会对现有的实现更感兴趣。

作为一个不值得自己进入的副问题，椭圆曲线加密的典型实现是否需要动态分配？

是否可以在没有动态分配的情况下实现多精度整数类

是。

我知道在C＃BigInteger类中有类似的实现。（并且不能承受底层clr运行时的作用）。

我不知道C / C ++中有任何静态大小的缓冲区。但我只熟悉Botan，Crypto ++和OpenSSL。

从我所看到的实现，公共指数e有时会得到优化，使其成为int或long 。但是n和d是多精度的。（而且我想看看有一天会如何爆炸）。

最后，路由器和其他低功耗设备通常会对发送和接收缓冲区进行优化（我曾经与一个电气工程师和设计路由器的人一起工作）。它们只保留一块内存，软件使用索引访问静态缓冲区。所以不难相信他们已经采取了你所说的优化。

RSA-2048，并且可以通过静态地或在堆栈上为所有必要的中间结果分配空间来实现该算法。

是的，如果您接受限制最大RSA模数大小或EC素数字段大小，则可以使用固定大小的缓冲区使用符号幅度方案。

RSA公钥是（e，n）。尽管有小e的警告，你需要两个2048/8 = 256个字节或八位字节的缓冲区。

没有预计算技巧的RSA私钥简单地是（e，d，n）。所以你需要三个256字节或八位字节的缓冲区。

如果您正在使用12位字节的PDP-8，那么您将需要更少的字节。

它不表示最大整数大小。

细节中的魔鬼可能是倍增。因此，您需要一个临时缓冲区来执行乘法运算。这意味着您将需要一个~2 * 2048位大小的缓冲区（乘以2 m大小的缓冲区会产生大小为2m -1的结果）。然后必须减少乘法的结果。他们可能会进一步优化，但我通常不关心这些细节。

相关，最大邮件大小和最大密文大小与n相关。在Crpyto ++中，可以使用MaxPreImageSize （对于纯文本）和MaxImageSize （对于密文）检索它们。 MaxPreImageSize和MaxImageSize返回n - 1 。

作为一个不值得自己进入的副问题，椭圆曲线加密的典型实现是否需要动态分配？

这取决于底层实现。素数域上的曲线由域参数定义（来自Certicom的SEC1，椭圆曲线域参数，第3节，第16页）：

 Elliptic curve domain parameters over F_p are a sextuple: T = (p, a, b, G, n, h)

p是一个大素数，它需要一个多精度整数
a和b是定义曲线的系数。通常是“小”（例如， a = 3），但是对于非标准曲线，它们可能需要多精度整数。例如，DJB的ed25519曲线是y^2 = x^3 - 102314837768112 x + 398341948620716521344 。
G是基点，因此它实际上是曲线上的一个元素（或点）。这意味着是（X，Y）坐标，可能需要多精度整数。
n是阶数G的素数，这意味着它的n和n一样大
h是辅助因子，通常非常小：4或2，或1。

为曲线创建密钥对时，需要一个随机私有指数d （或x ），并在取幂后创建一个元素（曲线上的点）。也就是说，公钥（X，Y）= G^x 。所以你还有三个多精度整数。

二进制字段上的曲线需要一种表达多项式的方法。所以你可能仍然需要多精度整数（用于素数域中的p ）。

因此，椭圆曲线上的大多数“事物”都需要一个多精度整数。

您可以在例如Elliptic Curve Cryptography（ECC）Brainpool标准曲线和曲线生成中查看域参数的示例。

Thomas Pornin在BearSSL内部实施的这种RSA实现具有我所询问的属性。来自BearSSL的网页：

没有任何动态分配。所有库中都没有一个malloc（）调用。

…

在大型桌面和服务器操作系统上，此function仍然提供了一个有趣的特性：免受内存泄漏和基于内存的DoS攻击。局外人不能让BearSSL分配兆字节的RAM，因为BearSSL实际上根本不知道如何分配RAM。