为什么RSA密钥大小几乎总是2的幂？

#1 楼

在RSA中，公共模数$ N $的位大小$ n $通常采用$ n = c \ cdot2 ^ k $的形式，其中$ c $是一个小的奇整数。 $ c = 1 $（$ n = 512 $，$ 1024 $，$ 2048 $，$ 4096 $ .. bit）是最常见的，但$ c = 3 $（$ n = 768 $，$ 1536 $，$ 3072 $ .. bit）和$ c = 5 $（$ n = 1280 $ ..）是常见的。这样做的原因之一仅仅是限制可能性，并且在加密技术中到处都可以找到类似的进程，并且通常在二进制规则（例如RAM大小）的计算机中也可以找到。

分解的难度（因此，据我们所知，在没有旁通道和填充攻击的情况下，RSA的安全性随着$ n $的增长而平稳增长。但是，随着$ n $的增加，计算RSA公共和私有功能的难度会逐步增加（在下一段中会详细说明原因）。因此，仅一步以下的$ n $值比一步上方的$ n $更具吸引力：它们几乎一样安全，但后者在实际使用中更困难/更慢。而且，并非偶然的是，常见的RSA模数大小恰好在这些步骤之下。

创建步骤的一个主要因素是何时需要一个以上的单词/存储单元来存储数字。当存储单元为$ b $位时，RSA公共功能$ x \ mapsto x ^ e \ bmod N $每$ b $位有一个这样的步骤； RSA私有函数$ x \ mapsto x ^ d \ bmod N $的每个$ r \ cdot b $位有一个步骤，其中$ r = 1 $是朴素的实现，而$ r $等于在使用CRT且位大小相等的因素时，$ N $（最常见的是$ r = 2 $，但是我听说过$ r = 8 $的计划）。在任何适用于RSA的现代通用CPU上，$ b $是2的乘方，至少是$ 2 ^ 5 $，这有力地刺激了$ n $至少是$ 2 ^ 6 $的倍数（$ r = 2 $是常见的，并且是$ n $低于约一千的唯一合理选择）。注：$ n = 1984 = 31 \ cdot2 ^ 6 $在智能卡领域并不罕见，因为$ 2的下一个倍数^ 6 $将打破通用传输协议ISO / IEC 7816-3 T = 0中的声音屏障。有关此字段中常见RSA模数大小的列表，请搜索LENGTH_RSA_1984。

顺便说一句，当位数时，用欧几里得除法（在RSA中使用很多）编码商估计要简单得多。除数的提前是已知的。这产生了减少模数的可能比特大小的数量的动机。最简单的两种情况是，位数是$ b $的倍数，而位数是$ b $的倍数；前者赢了。

#2 楼

传统上使用二的幂。对于非常受限的体系结构，它还具有一些实现上的好处：它节省了一些指令。这间接意味着某些实现无法处理大小不是32或64的倍数的RSA密钥，这意味着，如果要获得最大的互操作性，则也不应使用其他密钥大小（即使代码不受此限制） ）。

（我见过野外使用的1152位和1536位大小的RSA密钥，因此对2的幂没有绝对的限制。）

#3 楼

选择RSA密钥大小的任何特定对齐方式（无论是2的幂，64的倍数，2的倍数），都没有密码优势。密码攻击的难度随位数的增加而大大增加。正如fgrieu所指出的那样，使用32或64的倍数的大小对防御者来说有一点优势，因为无论您使用2017-2048位数字还是2048-位数字进行操作，大多数bignum运算的成本实际上是相同的位数字。

但是，使用“标准”大小有时会有实际的优势-至少是32的倍数，更常见的是$（2 ^ k + 1）2 ^ m $形式的数字小$ k $。优点是您的密钥将与之一起使用的实现在这些大小的条件下进行测试的机会更大。 RSA计算涉及对大小的运算，并且可能包含仅在“非舍入”大小（例如，不是字长的倍数的大小）上明显的错误。某些实现甚至可能禁止使用未经测试的密钥大小，因此它们仅支持几种大小。

对于DSA，FIPS 186标准最初规定密钥大小应为整数。 512和1024之间的32个密钥。当前版本指定密钥大小必须为1024、2048或3072，并指定这些相同的密钥大小是供政府用于RSA的唯一有效密钥大小。将密钥大小限制为几个值可提高互操作性，并通过降低实现复杂性和增加测试覆盖范围来提高安全性。

#4 楼

这只是惯例，由诸如GPG和OpenSSL之类的产品强制执行，这些产品包含阻止您选择自己的确切位长的代码（它们出于特殊原因而强制填充或舍入）。这是强制执行此操作的GPG代码，例如：

 if( nbits < 768)
   {
     nbits = 2048;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }
 else if(nbits>3072)
   {
     nbits = 3072;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }

 if(nbits % 64)
   {
     nbits = ((nbits + 63) / 64) * 64;
     log_info(_("keysize rounded up to %u bits\n"), nbits );
   }


 /* To comply with FIPS rules we round up to the next value unless
    in expert mode.  */

 if (!opt.expert && nbits > 1024 && (nbits % 1024))
   {
     nbits = ((nbits + 1023) / 1024) * 1024;
     log_info (_("keysize rounded up to %u bits\n"), nbits );
   }