Time needed to factor large integers
8 months ago
- #Cryptography
- #Factoring Algorithms
- #RSA
- GNFS（通用数域筛）算法是目前已知针对大于古戈尔数（10^100）的大数分解最快的算法。
- 使用GNFS分解数字n的预期时间与exp(f(n)g(n))成正比，其中f(n)相对恒定，而g(n)随n变化更显著。
- 在密码学应用中，f(n)中的o(1)项不可忽略，实际密钥尺寸下该值通常约为0.27。
- 1024位RSA密钥提供80比特安全性，相当于破解80位对称加密密钥的强度。
- RSA密钥的安全级别与g(n)成正比，其表达式为(log n)^(1/3)(log log n)^(2/3)。
- 实证数据显示，RSA密钥的安全级别约为2.55*x^(1/3)*log(x)^(2/3)，其中x=log(2)*b（b为密钥比特长度）。
- 分解2048位RSA密钥所需的能量将超过全球年能源产量。
- RSA加密并非通过密钥分解被攻破，而是通过利用实现漏洞被破解。