cryptography - 生成强 RSA key 的技巧

Question

是否有任何文档包括生成强 RSA key 的提示？

我的意思不仅仅是“使用带 -X 标志的 XXX 实用程序”。

我指的是理论上的一些规则。例如，模块n应不小于1024位等。

谁能告诉我吗？

Answer 1

为了回答你的问题，有这样的文档: ANSI X9.31 标准要求使用强质数来生成数字签名的 RSA key 。这使得使用 Pollard 的 p − 1 算法对 n = p q 进行因式分解在计算上不可行。然而，强素数并不能防止使用较新的算法(例如 Lenstra 椭圆曲线分解和数域筛算法)进行模分解。

第 4 版RSA 实验室关于当今密码学的常见问题于 1998 年发布，可以在此处找到 ftp://ftp.rsa.com/pub/labsfaq/labsfaq4.pdf 请注意以下问题:

问题 3.1.4。什么是强素数以及它们对于 RSA 是必要的吗？

In the literature pertaining to RSA, it has often been suggested that in choosing a key pair, one should use socalled “strong” primes p and q to generate the modulus n. Strong primes have certain properties that make the product n hard to factor by specific factoring methods; such properties have included, for example, the existence of a large prime factor of p-1 and a large prime factor of p+1. The reason for these concerns is some factoring methods (for instance, the Pollard p-1 and p+1 methods, see Question 2.3.4) are especially suited to primes p such that p-1 or p+1 has only small factors; strong primes are resistant to these attacks. However, advances in factoring over the last ten years appear to have obviated the advantage of strong primes; the elliptic curve factoring algorithm is one such advance. The new factoring methods have as good a chance of success on strong primes as on “weak” primes. Therefore, choosing traditional “strong” primes alone does not significantly increase security. Choosing large enough primes is what matters. However, there is no danger in using strong, large primes, though it may take slightly longer to generate a strong prime than an arbitrary prime. It is possible new factoring algorithms may be developed in the future which once again target primes with certain properties. If this happens, choosing strong primes may once again help to increase security.

问题 3.1.5。 RSA 中应使用多大的 key ？

The size of an RSA key typically refers to the size of the modulus n. The two primes, p and q, which compose the modulus, should be of roughly equal length; this makes the modulus harder to factor than if one of the primes is much smaller than the other. If one chooses to use a 768-bit modulus, the primes should each have length approximately 384 bits. If the two primes are extremely close (identical except for, say, 100 - 200 bits), or more generally, if their difference is close to any predetermined amount, then there is a potential security risk, but the probability that two randomly chosen primes are so close is negligible. The best size for an RSA modulus depends on one’s security needs. The larger the modulus, the greater the security, but also the slower the RSA operations. One should choose a modulus length upon consideration, first, of the value of the protected data and how long it needs to be protected, and, second, of how powerful one’s potential threats might be.

截至 2010 年，最大的分解 RSA 数字为 768 位长(232 位十进制数字)。它的因式分解通过最先进的分布式实现花费了大约 1500 个 CPU 年(实时时间为两年，在数百台计算机上)。这意味着，目前还没有考虑更大的 RSA key 。 实际上，RSA key 的长度通常为 1024 到 2048 位。一些专家认为，1024 位 key 在不久的将来可能会变得容易破解；很少有人认为 4096 位 key 在可预见的将来会被破解。因此，一般认为如果n足够大，RSA就是安全的。