Pas*_*uoq 8 c cryptography rsa
典型的RSA实现包含多精度整数库.典型的多精度整数库使用动态分配将大整数表示为正确大小的机器字数组.
我希望在使用多精度整数时,只有加密或解密已知长度的消息(通常是对称加密密钥)时才会遇到数学整数的限制,例如RSA-2048,它会是可以通过静态地或在堆栈上为所有必要的中间结果分配空间来实现该算法.
我发现这个论坛帖子暗示这是可能的.它不表示最大整数大小.也许这很明显("你需要所有整数2048位,呃!").无论如何,如果有的话,我会对现有的实现更感兴趣.
作为一个不值得自己进入的副问题,椭圆曲线加密的典型实现是否需要动态分配？
是否可以实现不动态分配的多精度整数类
是的。
我知道C# BigInteger Class中有类似的实现。（并且不管底层 clr 运行时做了什么）。
我不知道 C/C++ 中有任何静态大小的缓冲区。但我只熟悉Botan、Crypto++和OpenSSL。
从我所看到的实现来看，公共指数e有时会得到优化，使其成为intor long。但n和d是多精度的。（我想看看有一天它会如何爆发）。
最后，路由器和其他低功率设备经常对发送和接收缓冲区进行这种优化（我曾经与一位电气工程师和设计路由器的人一起工作）。它们只是保留一块内存，软件使用索引来访问静态缓冲区。所以不难相信他们已经采取了你所说的优化。
RSA-2048，并且可以通过静态或在堆栈上为所有必要的中间结果分配空间来实现该算法。
是的，如果您接受限制最大 RSA 模数大小或 EC 素数字段大小，则可以使用固定大小缓冲区的符号幅度方案来实现这一点。
RSA 公钥是 (e,n)。尽管有关于小 的警告e，您仍然需要两个 2048/8 = 256 字节或八位字节的缓冲区。
没有预计算技巧的 RSA 私钥很简单 (e,d,n)。因此，您需要三个 256 字节或八位位组的缓冲区。
如果您正在使用 12 位字节的 PDP-8，那么您将需要更少的字节。
它不指示最大整数大小。
细节中的魔鬼可能是乘法。因此，您需要一个暂存缓冲区来执行乘法。这意味着您将需要一个 ~2*2048 位大小的缓冲区（乘以 2m大小的缓冲区会产生 size 的结果2m -1 ）。然后乘法的结果必须减少。它们可能是进一步的优化，但我通常不关心这些细节。
相关的是，最大消息大小和最大密文大小有关n。在Crpyto++中，可以使用MaxPreImageSize（对于纯文本）和MaxImageSize（对于密文）来检索它们。MaxPreImageSize并MaxImageSize返回n - 1。
作为一个不值得单独讨论的附带问题，椭圆曲线密码学的典型实现是否需要动态分配？
这取决于底层的实现。素数域上的曲线由域参数定义（来自 Certicom 的SEC1，椭圆曲线域参数，第 3 节，第 16 页）：
Run Code Online (Sandbox Code Playgroud)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 标准曲线和曲线生成中查看域参数的示例。