c - 没有动态分配的RSA的实现

Question

典型的 RSA 实现包含一个多精度整数库。典型的多精度整数库使用动态分配将大整数表示为大小恰到好处的机器字数组。

我预计当使用多精度整数仅使用 RSA-2048 加密或解密已知长度的消息(通常是对称加密 key )时，可能会遇到数学整数的界限，并且可以通过静态地或在堆栈上为所有必要的中间结果分配空间来实现该算法。

我找到了 this forum thread暗示这是可能的。它不表示最大整数大小。也许这是显而易见的(“所有整数都需要 2048 位，呃!”)。无论如何，如果有的话，我会对已经存在的实现更感兴趣。

作为一个不值得单独输入的附带问题，椭圆曲线密码术的典型实现是否需要动态分配？

Answer 1

Is it possible to implement a multi-precision integer class without dynamic allocation

是的。

我知道 C# BigInteger Class 中有类似的实现. (并且不考虑底层 clr 运行时的作用)。

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

根据我所见的实现，公共(public)指数 e 有时会得到优化，使其成为 int 或 long。但是 n 和 d 是多精度的。 (我想看看有一天会怎样)。

最后，路由器和其他低功率设备通常会在发送和接收缓冲区上进行这种优化(我曾经和一个设计路由器的电气工程师一起工作)。它们只是保留一 block 内存，软件使用索引来访问静态缓冲区。因此，不难相信他们已经采用了您所说的优化。

---

RSA-2048, and that it would be possible to implement the algorithm by allocating space for all necessary intermediate results either statically or on the stack.

是的，如果您同意限制最大 RSA 模数大小或 EC 素数字段大小，您可以使用固定大小缓冲区的符号幅度方案来做到这一点。

RSA 公钥是 (e,n)。尽管有关于小 e 的警告，您仍需要两个 2048/8 = 256 字节或八位字节的缓冲区。

没有预计算技巧的 RSA 私钥就是 (e,d,n)。因此，您需要三个 256 字节或八位字节的缓冲区。

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

---

It does not indicate maximum integer sizes.

细节中的魔鬼可能是乘法。所以你需要一个临时缓冲区来执行乘法。这意味着您将需要一个 ~2*2048 位大小的缓冲区(乘以 2 个 m 大小的缓冲区会创建大小为 2m -1 的结果)。然后必须减少乘法的结果。它们可能是进一步的优化，但我通常不关心这些细节。

相关，最大消息大小和最大密文大小与n有关。在 Crpyto++ 中，可以使用 MaxPreImageSize(对于纯文本)和 MaxImageSize(对于密文)检索它们。 MaxPreImageSize 和 MaxImageSize 返回 n - 1。

---

As a side-question that does not deserve its own entry, do typical implementations of elliptic curve cryptography require dynamic allocation?

这取决于底层实现。素数场上的曲线由域参数定义(来自 Certicom 的 SEC1, Elliptic Curve Domain Parameters，第 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

  一样大

• h 是辅助因子，通常很小:4 或 2，或 1。

当您为曲线创建 key 对时，您需要一个随机私有(private)指数 d(或 x)，这会创建一个元素(曲线上的点)求幂后。即公钥 (X, Y) = G^x。所以你还有三个多精度整数。

二进制文件上的曲线需要一种表示多项式的方法。所以您可能仍然需要多精度整数(用于素数字段中的 p)。

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

您可以在例如 Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation 查看域参数的示例。 .