sal*_*bob 5 math rsa public-key-encryption
我只是想了解RSA的密钥生成部分,更具体地说,选择p和q素数.给定模数的目标位长度n,我应该生成p和q的范围是多少？
模量n是p和q的乘积,其中p和q都是素数.我已经读过p和q应该相对接近,并且在sqrt(n)附近.如果目标位长度是例如32位(我意识到非常小),那么p和q应该是最大16位的随机素数吗？
谢谢你的任何澄清
抢
Mar*_*son 16
对于32位模数的问题是有点学术兼职:在选择你的首要目标p,并q为使产品难以因式分解,但找到了一些比较小的素因式分解2^32是那么容易,几乎没有一点担心的大小p而q在这种情况下.请注意,只要数学是完全正常的,p并且q是不同的素数.
对于一些更现实的,像1024位模数,那么,你是非常安全的选择两个512位的素数p和q随机:即选择p并q均匀地从设定范围内的所有素数[2^511, 2^512].有一个" 强素数 " 的概念,它是旨在避免特定可能的已知攻击的素数 - 例如,你会看到建议,p并且q应该选择这样的p-1并且q-1有很大的因素,以防止使用Pollard'的简单因素分析' p-1'算法.但是,这些建议并不适用于大模量和最先进的分解算法(GNFS,ECM).还有其他一些可能的情况,理论上可以给出一个简单的分解,但它们在实践中不太可能从随机选择中出现,p并且q它们不值得担心.
总结:只需选择两个具有相同位长的随机素数,就可以了.
还有几点需要考虑的其他评论和事项:
当然,如果你选择两个512位的素数,你会拥有或者 1023位或 1024位模数; 这可能不值得担心,但如果你真的关心恰好得到一个1024位模数,你既可以限制的范围p,并q进一步说[1.5 * 2^511, 2^512],或只是抛出任何1023位模数,然后再试一次.
不要故意选择p并使q它们彼此靠近:如果p并且q彼此真正相近(例如,比较小10^10,比如说),那么他们的产品pq很容易被Fermat的方法分解.但是如果你选择随机素数p并且q在范围内[2^511, 2^512],那么任何现实概率都不会发生这种情况.
当随机选择素数时,一个诱人的策略是在该范围内选择一个随机(奇数)整数[2^511, 2^512],然后递增它直到找到第一个素数.但请注意,这并没有在所有素数中给出统一的选择:在大差距之后出现的素数比其他素数更有可能出现.一个更好的策略就是继续选择随机奇数并保持第一个是素数(或者更可能的是,这么多随机选择的基数的强可能素数,你可以在实践中确定它是素数).
确保你有一个非常好的随机数加密源,供你的素数生成.