近50年后，RSA仍在新闻中：费马对RSA的攻击

经过近 50 年，RSA 仍然是新闻热点：Femat 对 RSA 的攻击

似乎很合适，在 1970 年代向世界发布 RSA 的出版物，现在又概述了对 RSA 的攻击。 这当然是强大的《科学美国人》[here]：

这个破解方法是众所周知的，与皮埃尔·德·费马的发现有关，即如果质数彼此非常接近，我们可以相当容易地将模数分解为它的质数因子。

费马定义了一种分解方法，如果这些质数彼此接近，则可以分解质数因子。在 RSA 中，我们使用一个模数（N），它是两个质数（p 和 q）的乘积。如果这些质数彼此接近，那么 N 可以被分解，并且 RSA 方法可以很容易地被破解。在 2019 年，人们发现 Rambus 密码模块选择了一个质数，然后又选择了一个接近它的质数。这导致了许多使用 Rambus 模块的打印机出现漏洞。在本例中，我们将使用费马的方法来分解一个模数，其中质数彼此相差 2100 以内。

方法

使用费马分解算法，我们假设两个大质数可以写成：

N =( a − b)( a + b)

然后，我们将第一个质数设为 a − b，第二个质数设为 a + b。如果质数很接近，那么 a 的值将接近 N 的平方根。因此，我们可以从 N 的平方根猜测 a 的值，然后递增 a 的值，对于每个猜测，我们取：

b ²= a ²− N

如果结果是一个平方值，我们就有 a 和 b 的正确值，并计算：

p = a + b

和：

q = a − b

然后是基本算法 [取自 [here][1]：

def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2
    a = gmpy2.isqrt(n)
    if a * a == n:
        return a, a
    a += 1  # ceil(sqrt(n))
    b2 = a * a - n
    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)
        b2 += a
        a += 1
        b2 += a
    return None

在本例中，我们使用 gmpy2 来计算整数平方根。以下是代码的轮廓[here]：

## Some code derived from https://github.com/google/paranoid_crypto/
import gmpy2
from gmpy2 import mpz, xmpz
import random
import sys
class RSAKey:
    def __init__(self): # constructor method
      e=bytearray(0)
      n=bytearray(0)
def Int2Bytes(int_val: int):
    return int.to_bytes(int(int_val), (int_val.bit_length() + 7) // 8, 'big')
def Bytes2Int(bytes_val: bytes) -> int:
    return int.from_bytes(bytes_val, 'big')
def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2
    a = gmpy2.isqrt(n)
    if a * a == n:
        return a, a
    a += 1  # ceil(sqrt(n))
    b2 = a * a - n
    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)
    b2 += a
    a += 1
    b2 += a
    return None
nsize=512
rsa_key1=RSAKey()
max_steps = 2
if (len(sys.argv)>1):
 nsize=int(sys.argv[1])
print(f"Prime number size: {nsize} bits\n")
p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(p + 2**100)
rsa_key1.n=p * q
print(f"== Try with p and q close to each other (within 2^100)==\n")
print(f"N={rsa_key1.n}")
result = FermatFactor(rsa_key1.n, max_steps)
try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor") # 能够分解
except:
    print("Success: Not able to factor") # 成功：无法分解

p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(random.getrandbits(nsize))
rsa_key1.n=p * q
print(f"\n== Try with p and q as random primes==\n")
print(f"N={rsa_key1.n}")
result = FermatFactor(rsa_key1.n, max_steps)
try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor") # 能够分解
except:
    print("Success: Not able to factor") # 成功：无法分解

一个示例运行[here]：

Prime number size: 256 bits

== Try with p and q close to each other (within 2^100)==

N=2939996184542009830552637750638122846095806360303151102342122127053148420301726390856520234993803536729525509434458704850858860323857335934417339321438959
Able to factor
Factors are 54221731663070387690963782749697789130088662657558419676189680837541283118477 and 54221731663070387690963782749697789130088662656290769075961451436044579913067

== Try with p and q as random primes==

N=4110412783524445774387304783164512688225499340717539143119125204475335655304450384315489380473160300859437389518848430795695254022438166111193003519297207
Success: Not able to factor

结论

经过近 50 年，RSA 方法仍然是新闻热点。现在，这里有一个使用费马方法的挑战：

Bob 使用 RSA 为 Alice 加密消息。 密码值为
8864908137467509983644182050398153834046403984217707202746928084958234520757384332932918976688075309988771489273547449419719263345203661331985727893486292
模数为11382627348373025287543453024103054449842443292685364469545512700086205931082801278230482806559999080698290003946353162530936339995472583045836479873343371
并使用 e=65537。
然而，他的生成器创建了两个非常接近的质数。 使用此信息，找到英国城市？

方法在这里：

[CTF Generator: Fermat's attack

Normally, in RSA, we select two prime numbers of equal length (\(p\) and \(q\)), and then multiply these to give a…

asecuritysite.com](https://asecuritysite.com/rsa/fermat_fact?source=post_page-----7537dd90c974---------------------------------------)

• 原文链接： medium.com/asecuritysite...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～