是否可以在没有动态分配的情况下实现多精度整数类
是的。
我知道C# BigInteger Class中有类似的实现。(并且无法承受底层 clr 运行时的作用)。
我不知道 C/C++ 中有任何静态大小的缓冲区。但我只熟悉 Botan、Crypto++ 和 OpenSSL。
根据我对实现的了解,公共指数e
有时会得到优化,使其成为int
or 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
(对于密文)来检索它们。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
h
是辅因子,它通常非常小:4 或 2,或 1。
当您为曲线创建密钥对时,您需要一个随机私有指数d
(或x
),并在求幂后创建一个元素(曲线上的点)。也就是说,公钥 (X, Y) = G^x
。所以你还有三个多精度整数。
二进制文件上的曲线需要一种表达多项式的方法。所以你可能仍然需要多精度整数(用于p
素数字段)。
因此,椭圆曲线上的大多数“事物”都需要一个多精度整数。
例如,您可以在椭圆曲线密码学 (ECC) Brainpool 标准曲线和曲线生成中查看域参数的示例。