是否可以实现不动态分配的多精度整数类
Yes.
我知道类似的实现C# BigInteger 类 http://www.codeproject.com/Articles/2728/C-BigInteger-Class。 (并且不管底层 clr 运行时做了什么)。
我不知道 C/C++ 中有任何静态大小的缓冲区。但我只熟悉Botan、Crypto++和OpenSSL。
从我所看到的实现来看,公共指数e
有时会得到优化,使其成为int
or long
. But n
and d
是多精度的。 (我想看看有一天它会如何爆发)。
最后,路由器和其他低功率设备经常对发送和接收缓冲区进行这种优化(我曾经与一位电气工程师和设计路由器的人一起工作)。它们只是保留一块内存,软件使用索引来访问静态缓冲区。所以不难相信他们已经采取了你所说的优化。
RSA-2048,并且可以通过静态或在堆栈上为所有必要的中间结果分配空间来实现该算法。
是的,如果您接受限制最大 RSA 模数大小或 EC 素数字段大小,则可以使用固定大小缓冲区的符号幅度方案来实现这一点。
RSA 公钥是 (e,n)。尽管有小警告e
的,您将需要两个 2048/8 = 256 字节或八位字节的缓冲区。
没有预计算技巧的 RSA 私钥很简单 (e,d,n)。因此,您需要三个 256 字节或八位位组的缓冲区。
如果您正在使用 12 位字节的 PDP-8,那么您将需要更少的字节。
它不指示最大整数大小。
细节中的魔鬼可能是乘法。因此,您需要一个暂存缓冲区来执行乘法。这意味着您将需要一个 ~2*2048 位大小的缓冲区(乘以 2m
大小的缓冲区创建大小的结果2m -1
)。然后乘法的结果必须减少。它们可能是进一步的优化,但我通常不关心这些细节。
相关,最大消息大小和最大密文大小有关n
。在 Crpyto++ 中,可以使用以下命令检索它们MaxPreImageSize
(对于纯文本)和MaxImageSize
(对于密文)。MaxPreImageSize
and MaxImageSize
return n - 1
.
作为一个不值得单独讨论的附带问题,椭圆曲线密码学的典型实现是否需要动态分配?
这取决于底层的实现。素数域上的曲线由域参数定义(来自 Certicom 的SEC1,椭圆曲线域参数 http://www.secg.org/collateral/sec1_final.pdf,第 3 节,第 16 页):
Elliptic curve domain parameters over F_p are a sextuple:
T = (p, a, b, G, n, h)
-
p
是一个大素数并且需要一个多精度整数
-
a
and b
是定义曲线的系数。通常是“小”(例如,a
= 3),但它们可能需要非标准曲线的多精度整数。例如DJB的ed25519曲线是y^2 = x^3 - 102314837768112 x + 398341948620716521344
.
-
G
是基点,所以它实际上是曲线上的一个元素(或点)。这意味着 是 (X, Y) 坐标,并且可能需要多精度整数。
-
n
是一个素数G
这意味着它几乎和n
-
h
是辅助因子,通常非常小:4 或 2,或 1。
当您为曲线创建密钥对时,您需要一个随机的私有指数d
(or x
),并在求幂后创建一个元素(曲线上的点)。即公钥(X,Y)=G^x
。所以你还有三个多精度整数。
二进制字段上的曲线需要一种表达多项式的方法。所以你可能仍然需要多精度整数(用于p
在素数场)。
因此,椭圆曲线上的大多数“事物”都需要多精度整数。
您可以在以下位置查看域参数的示例:椭圆曲线密码学 (ECC) Brainpool 标准曲线和曲线生成 https://www.rfc-editor.org/rfc/rfc5639#page-8.