我们可以将公共指数固定为我们喜欢的惯用值，例如$ e = 2 ^ {16} + 1 $或$ e = 3 $，因此只需要存储公共模数$ n $。我们不需要存储$ n $的最左边的位，它总是由定义来设置；也不会设置最右边的位，因为$ n $是奇数，所以总是被设置。稍加努力，我们可以节省（很少）几位，注意$ n $没有小除数，但是仍然是$ k \ sim m $位。 $ n $的$ \ left \ lfloor m / 2- \ log_2（m）-2 \ right \ rfloor $高位为任意常量，例如$ \ left \ lfloor \ pi \ cdot 2 ^ {\ left \ lfloor m / 2-log_2（m）-4 \ right \ rfloor} \ right \ rfloor $。
我们可以像选择常规RSA那样选择$ n $的最小素数$ p $，然后找到最大整数间隔$ [q_0，q_1] $，以使该间隔中的任何$ q $导致$ n = p \ cdot q $具有正确的高位，然后在该间隔中选择一个随机素数$ q $（大多数情况下，至少会有一个，如果没有的话，我们会尝试另一个$ p $）。
一些安全性论证是
生成RSA密钥$（p， q'）$使用常规方法，在某个适当范围内具有随机的大质数，除了$ n'= p \ cdot q'$和$ p 决定这些中$ n $的高位在$ n'$;
中，然后找到$ [q_0，q_1] $，在该间隔中生成$ q $作为随机质数，并设置$ n = p \ cdot q $;
可证明地给出与所述常规生成方法相同的$（p，q）$分布，因此同样安全；那么我们注意到$ n $的高位是随机的（某些分布离统一点不太远）并且是公共的，因此修复它对攻击没有太大帮助（我认为这可以做得很严格）。 >
现在，这是$ k \ sim m / 2 + \ log_2（m）$位来表示公钥。我们可以节省更多的位，每个位都会使生成私钥的工作量加倍（我们可以重复上面概述的生成过程，直到找到这些位等于某个公共任意常数或等于位的密钥如果希望更严格地确保该方案不被削弱，可以从其他哈希值中提取出来。）
我们可以做得更好，实际的限制是什么？在具有预定部分的RSA Moduli：技术和应用程序中，Marc Joye对此进行了讨论，并达到$ k \ sim m / 3 $（没有最优性要求）。我担心没有看到这样的论点，即算法3中选择$（p，q）$的方式不会削弱$ n $而不是专用的分解因数算法。
#1 楼
丹尼尔·伯恩斯坦（Daniel J. Bernstein）在他的论文“一种具有极快验证的安全公钥签名系统”中提到了压缩RSA公钥的方法。如果有一个更好的方法，但运行速度不是很慢，则可以将其重新用作分解算法。因此，如果可以将104到128位的任意字符串解压缩为安全的2048位RSA公钥的速度比正如大卫·施瓦茨（David Schwartz）提出的那样，这将是非常了不起的。每次运行算法时，您实际上都会发现大约2048位数字的大小相等的因子，其中您指定了很多位。
正如您所暗示的那样，另一种（不切实际的）减少模数未指定的低位存储的方法是以各种小质数为模存储其残基，并使用CRT进行重建。理论上，对于2048位模数，这应该节省3到4位。您可以节省空间，因为您可以依靠残差不为零。
评论
$ \ begingroup $
荣誉供伯恩斯坦参考。在1990年关于ISO 9796（-1）的论文中，它追溯了将$ m $的高位固定给Guillou和Quisquater的想法；那也一定是我学到的地方。但是，1990年的参考文献并未将固定位随机化，（后来）证明这是个坏主意，因为它可能有助于NFS。
$ \ endgroup $
–fgrieu♦
2012年1月19日在8:45
$ \ begingroup $
我无法遵循“如果有一种更好的方法，它运行得不是很慢，那么可以将其重新用作分解因数算法”，并且认为该方法已被参考文献中现在大大改进的范围所反对更新的问题。我能得到的最好的结果是，如果我们可以用生成成本$ X $达到$ k $位，那么我们就有一个成本$ X \ cdot 2 ^ k $的分解算法。
$ \ endgroup $
–fgrieu♦
2012年1月20日在16:56
#2 楼
实际上，通过使用不平衡的RSA密钥，我们似乎可以做得更好。例如，假设我们有一个512位的p和一个1536位的q。要生成密钥，我们可以选择一个随机的512位素数p，然后对于q，我们在$（C / p，（C + 2 ^ k）/ p）$（$ C $是我们的2048位常量，其中包括我们要强制使用的位，而$ k $是我们愿意改变的位数）。我们期望约$ 2 ^ k / p \ times（1 / / log（C / p））\约2 ^ {k-512} /（\ log（2）（2048-512））$素数;如果$ k \约522 $，则该范围内会有1个预期素数。这将使我们能够仅使用522位来表示2048位RSA密钥。我很确定，该算法会生成一个RSA模数，它比具有相同大小因子的随机模数不容易分解，但这并不能真正回答问题。现在，我们知道NFS花费的时间不会根据因素的大小而变化，但是如果因素较小，则ECM确实会加快速度。那么，在ECM变得比NFS更快（从而降低我们的安全级别）之前，我们可以赚多少美元？我不知道这个答案（或者即使我的512位因子示例已经超出限制；如果确实如此，也不会感到惊讶）。该技巧可用于在某种程度上缩小RSA公钥，但我不知道您可以使用多远。另一方面，我希望这是一项学术活动；如果您真的对小型公共密钥感兴趣，那么最好使用椭圆曲线算法（该算法具有小型公共密钥，而又看不到我们可以接近安全边缘的程度）。评论
$ \ begingroup $
我不遵循这个。我们期望在什么时间间隔内找到一个素数？对于1536位数字，大约0.1％是质数。
$ \ endgroup $
– ByteCoin
2012年1月19日3:00，
$ \ begingroup $
@ByteCoin：是的，大约1536位数字中的0.1％是质数，因此，如果我们将1536位数字的间隔设为1000个整数长，则我们有相当大的可能性至少其中之一实际上是质数。该间隔的大小为$（C + 2 ^ k）/ p-C / p = 2 ^ k / p $，因此$ 2 ^ k \ p约为p * 1000 $；也就是说，我们需要发布的位数（因为无法假定）比较小素数的位数大大约10
$ \ endgroup $
–雨披
2012年1月19日，下午3:58
$ \ begingroup $
如您所指出，ECM保理效率大大提高。因此，我几乎没有希望有一个普遍的，积极的安全论点，即该方案与平衡的RSA一样安全。
$ \ endgroup $
–fgrieu♦
2012年1月19日下午6:55
$ \ begingroup $
@fgrieu我似乎记得在某处读到，当小因子大约为模数位长度的1/3时，ECM和GNFS的预期运行时间大致相等。如果我们假设$ x ^ y + y ^ x $分解项目中的人员以最佳方式分配他们的工作量，那么我们可以看到他们的GNFS工作通常会产生150位数字的50位数字因子，而ECM发现的最大因子约为56数字。这使人们相信，至少对于这种大小的数，因子大小比应不大于1：2。
$ \ endgroup $
– ByteCoin
2012年1月19日下午14:43
$ \ begingroup $
@fgrieu您可能想要阅读Hinek撰写的“关于多主RSA的安全性”及其引用的一些著作，例如CompaqMultiPrimeWP.pdf。尽管您的计划onlt使用2素数，但有些计算需要权衡ECM和NFS的难度差异。特别地，随着n的大小增加，似乎因子的大小之间的比率可以安全地增加。我相信对于具有512位素数之一的2048位模数应该没问题。
$ \ endgroup $
– ByteCoin
2012年1月20日，0：16
评论
目的是减少为了发布给定的类似于RSA的方案而需要公开以公开公钥的位数，或者目的是减少必须安全存储以允许一个人再生自己的位数从头开始拥有自己的公钥？@ByteCoin：我想减少使用公共密钥需要公开的位数。在某些内存不足的情况下（例如智能卡），这是非常理想的。
这样只会在存储公钥时节省空间。要使用公共密钥加密或验证签名，您可能需要使用蒙哥马利表示法，在这种情况下，数字与模数的大小都相同，并且无法压缩。如果要对智能卡进行解密或签名，则可能是在利用CRT和Montgomery表示形式并使用较大的指数，因此压缩不再有用。这完全是学术性的，因为没人会在内存受限的系统中使用RSA！或者如果我弄错了，请赐教。
@ByteCoin：在智能卡中存储发行者/授权公钥时，我想节省空间。将事情推到极限，这可能是这种只有2kB EEPROM和两倍内存的现代设备。是的，可以在没有RSA硬件的此类设备上安全，合理地快速执行RSA或Rabin签名验证。第二个目标是缩短证书（使用具有消息恢复功能的ISO 9796-2签名嵌入ID和公钥），将它们限制在256字节的块限制内。
减少持久性存储需求的一种方法是（例如在EEPROM上）存储$ HASH（pk）$而不是$ pk $。当然，这意味着需要有一些替代位置，该位置可以提供完整的$ pk $用于操作。另外，所需的总存储量也在增加。