RSA的安全强度与模数大小的关系

#1 楼

那些似乎是基于通用数字字段筛选器的复杂性，通用数字字段筛选器是最快（如果不是最快的话）经典分解算法之一。我在Mathematica中确认了这一点。

这是GNFS的复杂性（源）：

$$ \ exp \ left（\ left（\ sqrt [3] {\ frac {64} {9}} + o（1）\ right）（\ ln n）^ {\ frac {1} {3}}（\ ln \ ln n）^ {\ frac {2} {3}} \ right）$$

其中$ n $是要分解的数字。在$ 2 ^ b $处评估上述表达式是对$ b $位整数进行分解所需的时间的近似值。这是一张显示$ 2 ^ {1024}，2 ^ {2048}，\ dots $的评估位长度的表：

Strength  RSA modulus size   Complexity bit-length
  80        1024               86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

我用以下Mathematica代码：

({#, N@Log2@gnfsComplexity[2^#]} &) /@ {1024, 2048, 3072, 7680, 15360}

其中gnfsComplexity定义为：

gnfsComplexity[n_] := Exp[(64/9 * Log[n])^(1/3) * (Log[Log[n]])^(2/3)]

这不是最漂亮的我曾经写过的东西，但似乎准确。 （对于不熟悉Mathematica的人，第二个代码段定义了一个函数，该函数是上述GNFS复杂度的数字$ n $的音译。第一个代码段以$ n = 2 ^ {1024}，2 ^ {2048来评估该复杂度} $等采用对数以2为底的对数，然后将其转换为数字近似值（十进制数字），而不是分数等精确结果。） RSA的大小，说明并不难。如果您查看问题中的文档，您会注意到分组密码的“安全位”与该分组密码的密钥大小（以位为单位）几乎完美相关（很少有例外）。这是因为我们对安全分组密码的最佳攻击本质上是对密钥的暴力搜索，这平均需要花费$ 2 ^ {n-1} $的时间，其中$ n $是密钥的位长。

但是，对于RSA而言，我们最好的攻击方法是不对密钥进行暴力搜索。取而代之的是，我们“简单地”分解（公共）模数，因此该方案的安全性围绕分解效率进行。 GNFS具有次指数级但仍然是超多项式的时间复杂度，并且可以使用该时间复杂度来粗略估计该方案提供的安全性。我相信这就是NIST在这里所做的。

#2 楼

我已经将上述等式重新格式化为GNU bc（在大多数Linux系统上找到的GNU coreutils的一部分）的程序。 GNU bc比Mathematica更容易找到（尽管它很古怪）。

代码如下：

$ cat RSA-gnfs.bc 
#!/usr/bin/bc -l

scale = 14
a = 1/3
b = 2/3
#print "RSA Key Length? "
c = read()

t = l( l(2 ^ c) )
# if b < 1, then a^b == e (l(a) * b)
m = e( l(t) * b )
t = 64 / 9 * l(2 ^ c)
n = e( l(t) * a )
o = e( m * n )
p = l(o) / l(2)
print "Strength: ", p, "\n"
quit

代码的几次运行，添加了上面未包含的密钥大小：

$ for x in 1024 2048 3072 4096 7680 8192 15360 16384
do echo $x | ./RSA-gnfs.bc ; done

Strength: 86.76611925027707
Strength: 116.88381329581011
Strength: 138.73628085271660
Strength: 156.49695341791272
Strength: 203.01873594416484
Strength: 208.47248637388102
Strength: 269.38477262126889
Strength: 276.51840722076620

根据此等式，如果您使用AES256作为对称密码，则这是具有相同强度的最小RSA密钥大小：

$ echo 13547 | ./RSA-gnfs.bc 
256.00114520595064

这里是“最高机密” AES192的最小等效项：

这是AES128的最小等效项：安全性”-符合此参数将产生新的最小RSA密钥大小：

$ echo 6707 | ./RSA-gnfs.bc 
192.00709600689071

#3 楼

相对于破坏对称加密算法所需的处理量，RSA的安全级别基于已知的对RSA的最强攻击。
NIST建议的方程式可计算FIPS 140-2中的近似密钥长度实施指导问题7.5。
它是：
$ x = \ frac {1.923 \ times \ sqrt [3] {L \ times ln（2）} {\ sqrt [3] {[ln（L \ times ln（2））^ 2}}} {ln（2）} $
该公式基于当前已知的最佳分解因数，即General Number Field Sieve，该公式可以非常精确地给出结果类似于其他答案中给出的公式。

密钥长度公式的官方强度结果
RSA-1024 80 79.999
RSA-2048 112 110.118
RSA-3072 128 131.97
RSA-7680 192 196.253
RSA-15360 256 262.619

此公式也适用于DSA组大小（假设子组足够大）。

#4 楼

先前的注释使分子中没有术语。

$$ x = \ frac {1.923 \ times \ sqrt [3] {L \ times ln（2）} {\ sqrt [3] { [ln（L \ times ln（2））^ 2}}-4.69} {ln（2）} $$

我在前面提到的NIST文档的第92页上找到此公式：

http://csrc.nist.gov/groups/STM/cmvp/documents/fips140-2/FIPS1402IG.pdf

实现此等式的GNU bc代码是：

$ cat RSA-NIST.bc 
#!/usr/bin/bc -l

scale = 14
a = 1/3
b = 2/3
#print "RSA Key Length? "
l = read()

t = l * l(2)
m = l(t)
# if b < 1, then a^b == e (l(a) * b)
n = e( l(m) * b )
o = e( l(t) * a )
p = (1.923 * o * n - 4.69) / l(2)
print "Strength: ", p, "\n"
quit

与先前的批处理输入一起运行：

$ for x in 1024 2048 3072 4096 7680 8192 15360 16384
do echo $x | ./RSA-NIST.bc ; done
Strength: 79.99990535892915
Strength: 110.11760837749330
Strength: 131.97008244495367
Strength: 149.73076030162618
Strength: 196.25255668821560
Strength: 201.70630874277964
Strength: 262.61861313789943
Strength: 269.75224986273620

我会注意到a）这个新等式运行得更快，并且b）这些数字意味着更低的强度。

根据该等式，如果您使用AES256作为对称密码，则这是将显示密码的最小RSA密钥大小。相同的强度：

$ echo 14446 | ./RSA-NIST.bc
Strength: 256.00032964845911

这里是“最高机密” AES192的最小等效项：

$ echo 7295 | ./RSA-NIST.bc 
Strength: 192.00346260354399

是AES128的最小等效项：

$ echo 2868 | ./RSA-NIST.bc 
Strength: 128.01675571278223

RFC-7525规范表示“实现不得协商提供少于112位安全性的密码套件”-符合此参数将产生新的最小RSA密钥大小：

$ echo 2127 | ./RSA-NIST.bc 
Strength: 112.01273358822347

令人惊讶的是，RSA使用NIST的公式显示-2048不符合要求-RSA-2127应该是它们的新最小值。