9

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

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

我发现这个论坛主题表明这是可能的。它不指示最大整数大小。也许这很明显(“所有整数都需要 2048 位,呃!”)。无论如何,如果有的话,我会对已经存在的实现更感兴趣。

作为一个不值得加入的附带问题,椭圆曲线密码学的典型实现是否需要动态分配?

4

2 回答 2

3

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

是的。

我知道C# BigInteger Class中有类似的实现。(并且无法承受底层 clr 运行时的作用)。

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

根据我对实现的了解,公共指数e有时会得到优化,使其成为intor long。但是n并且d是多精度的。(我想看看有一天会发生什么)。

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


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

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

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

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

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


它不指示最大整数大小。

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

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


作为一个不值得加入的附带问题,椭圆曲线密码学的典型实现是否需要动态分配?

这取决于底层实现。素数域上的曲线由域参数定义(来自 Certicom 的SEC1,椭圆曲线域参数,第 3 节,第 16 页):

Elliptic curve domain parameters over F_p are a sextuple:

   T = (p, a, b, G, n, h)
  • p是一个大素数,它需要一个多精度整数

  • ab是定义曲线的系数。通常是“小”(例如,a= 3),但对于非标准曲线,它们可能需要多精度整数。例如,DJB 的 ed25519 曲线是y^2 = x^3 - 102314837768112 x + 398341948620716521344.

  • G是基点,所以它实际上是曲线上的一个元素(或点)。这意味着是 (X, Y) 坐标,可能需要多精度整数。

  • n是有序的素数,G这意味着它的近似值与n

  • h是辅因子,它通常非常小:4 或 2,或 1。

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

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

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

例如,您可以在椭圆曲线密码学 (ECC) Brainpool 标准曲线和曲线生成中查看域参数的示例。

于 2013-10-05T23:06:46.540 回答
1

这个RSA 实现,在BearSSL中,由 Thomas Pornin 编写,具有我所询问的属性。来自 BearSSL 的网页:

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

…</p>

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

于 2016-11-04T13:01:17.350 回答