RSA的实现，而不动态分配 [英] Implementation of RSA without dynamic allocation

问题描述

一个典型的RSA实现采用了多precision整数库。一个典型的多precision整数库使用动态分配来重新present大整数作为机器字数组大小正合适。

我期望必须有对数学整数使用多precision只能为整数加密或解密已知长度（通常是对称加密密钥）用，比如说的消息时，人们可能遇到的约束，RSA-2048 ，这将有可能由静态或在堆栈上的所有必要的中间结果分配空间来实现该算法。

我发现这个论坛主题表明这是可能的。它并不表示最大整数尺寸。也许是显而易见的（你需要的所有整数2048位，咄！）。在任何情况下，我会更感兴趣的是一个已经存在的实现，如果有一个。

作为一个侧面的问题，不应该有自己的条目，做椭圆曲线密码体制的典型的实现需要动态分配？

解决方案

  

是否有可能实现无动态分配一个多precision整数类

是

我在 C＃的BigInteger类。 （而不是承受潜在的CLR运行时做什么）。

我不知道在C / C ++任何静态大小的缓冲区。但是我只熟悉牡丹，加密+和OpenSSL。

这是我所看到的实现，公用指数电子有时会使其成为一个优化 INT 或长。但 N 和 D 是多precision。 （我想看看那个吹了一些天）。

最后，路由器和其它低功率设备往往需要在发送这个优化和接收缓冲区（我用一个人谁是一名电气工程师而设计的路由器工作）。他们只是预留一个内存块，软件使用索引来访问静态缓冲区。所以它不是很难相信他们已经采取了你说话的优化。

---

  

的RSA-2048，并且将有可能由静态或在堆栈上的所有必要的中间结果分配空间来实现该算法。

是的，你可以使用固定大小的缓冲区做到这一点与符号级方案，如果你接受限制最大RSA模数尺寸或EC主要字段的大小。

这是RSA公钥是（E，N）。尽管小电子邮件警告的，你需要的8分之2048= 256轮空或八位字节两个缓冲区。

没有precomputation招数一RSA私钥是根本（E，D，N）。所以，你将需要256字节或八位组三个缓冲器。

如果你是在PDP-8正在与12位字节，那么你就需要更少的字节。

---

  

这并不表示最大的整数大小。

在细节魔鬼可能倍增。所以，你需要一个临时缓冲区进行乘法运算。这意味着你将需要1〜2 * 2048位大小的缓冲区（乘以2 M 大小的缓冲区大小创建的结果2米-1 ）。然后将相乘的结果将必须减少。他们可能会进一步优化，但我通常不会用这些细节关心自己。

相关，最大邮件大小和最大密文大小与 N 。在Crpyto ++，他们可以与检索最高preImageSize （为纯文本）和 MaxImageSize （用于密文）。 最高preImageSize 和 MaxImageSize 收益 N - 1

---

  

作为一个侧面的问题，不应该有自己的条目，做椭圆曲线密码体制的典型的实现需要动态分配？

这取决于底层的实现。在黄金领域的曲线由域参数（通过Certicom的 SEC1，椭圆曲线域参数第3节，第16页）：

 在F_p椭圆曲线域参数是一个六重：   T =（P，A，B，G，N，H）
 

• P 是一个大素数，它需要一个多precision整数




• A 和 B 是定义曲线系数。在通常是小（例如， A = 3），但他们可能需要进行非标曲线多precision整数。例如，DJB的ed25519曲线 Y ^ 2 = X ^ 3 - 1023148​​37768112 X + 398341948620716521344




• 是基本点，所以它真的在曲线上的元素（或点）。这意味着是一个（X，Y）坐标大概需要多precision整数。




• N 是序素，这意味着其nealry大如<$ C $ ç> N




• ^ h 是辅助因子和它通常很小：4或2，或1

当您创建曲线密钥对，你需要一个随机专用指数 D （或 X ）和创建该幂后的元件（在曲线上点）。也就是说，公共密钥（X，Y）= G ^ X 。所以，你有三个多precision整数。

在提交了二进制的曲线需要一种方法来恩preSS多项式。所以，你可能还需要多precision整数（在黄金领域用于 P ）。

所以，大多数的椭圆曲线上的'东西'需要一个多precision整数。

您可以看到域参数的例子，例如椭圆曲线加密（ECC ）Brainpool标准曲线与曲线生成。

A typical RSA implementation incorporates a multi-precision integer library. A typical multi-precision integer library uses dynamic allocation to represent large integers as arrays of machine words just the right size.

I expect there must be a bound on the mathematical integers one may encounter when using the multi-precision integers only to encrypt or decrypt messages of known length (typically, symmetric encryption keys) with, say, 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.

I found this forum thread suggesting this is possible. It does not indicate maximum integer sizes. Perhaps it is obvious ("you need 2048 bits for all integers, duh!"). In any case, I would be more interested in an already existing implementation, if there is one.

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

解决方案

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

Yes.

I'm aware of a similar implementation in C# BigInteger Class. (And not withstanding what the underlying clr runtime does).

I'm not aware of any static-sized buffers in C/C++. But I'm only familiar with Botan, Crypto++, and OpenSSL.

From what I've seen of implementations, the public exponent e sometimes gets an optimization of making it an int or long. But n and d are multi-precision. (And I'd like to see how that blows up some day).

Finally, routers and other low powered equipment often take this optimization on send and receive buffers (I used to work with a guy who was an electrical engineer and designed routers). They simply reserve a chunk of memory and the software uses an index to access the static buffer. So its not hard to believe they have taken the optimization you speak of.

---

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.

Yes, you could do that with a sign magnitude scheme using fixed sized buffers if you accepted to limit the maximum RSA modulus size or EC prime field size.

An RSA public key is (e,n). Notwithstanding the warning on small e's, you would need two buffers of 2048/8 = 256 byes or octets.

A RSA private key without the precomputation tricks is simply (e,d,n). So you would need three buffers of 256 bytes or octets.

If you were working on a PDP-8 with 12-bit bytes, then you would need fewer bytes.

---

It does not indicate maximum integer sizes.

The devil in the detail is probably multiplication. So you would need a scratch buffer to perform the multiplication. That means you will need a ~2*2048-bit sized buffer (multiplying 2 m sized buffers creates a result of size 2m -1). The result of the multiplication would then have to be reduced. Their may be further optimizations, but I don't usually concern myself with those details.

Related, the maximum message size and maximum cipher text size is related to n. In Crpyto++, they can be retrieved with MaxPreImageSize (for the plain text) and MaxImageSize (for the cipher text). MaxPreImageSize and MaxImageSize return n - 1.

---

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

It depends on the underlying implementation. A curve over a prime field is defined by domain parameters (from Certicom's SEC1, Elliptic Curve Domain Parameters, Section 3, page 16):

Elliptic curve domain parameters over F_p are a sextuple:

   T = (p, a, b, G, n, h)

• p is a large prime and it needs a multi-precision integer

• a and b are coefficients that define the curve. The usually are 'small' (for example, a = 3), but they could require multi-precision integers for non-standard curves. For example, DJB's ed25519 curve is y^2 = x^3 - 102314837768112 x + 398341948620716521344.

• G is the base point, so its really an element (or point) on the curve. That means is a (X, Y) coordinate and probably requires multi-precision integer.

• n is a prime of order G which means its nealry as large as n

• h is the cofactor and its usually very small: 4 or 2, or 1.

When you create a key pair for the curve, you need a random private exponent d (or x), and that creates an element (point on the curve) after the exponentiation. That is, Public Key (X, Y) = G^x. So you have three more multi-precision integers.

A curve over a binary filed needs a way to express the polynomial. So you would probably still need the multi-precision integer (used for p in the prime field).

So, most of the 'things' on an elliptic curve need a multi-precision integer.

You can see examples of the domain parameters at, for example, Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation.

这篇关于RSA的实现，而不动态分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！