Python RSA 暴力破解

Question

我有一个练习来暴力破解一段用非常小的密钥加密的文本。我的 public 键是 (e = 5, n = 203)。文本已转换为 ASCII，移动了一个固定数字，然后使用 RSA public 密钥加密。我必须仅使用蛮力解密此文本。要解密，我使用的是简单的公式：

decrypt = (value**d)%n

其中 value 是我要解密的东西，d 是我不确定的值，n 是模数。

到目前为止，我已经将数字放在一个名为 en 的元组中，然后像这样遍历它：

for i in range(1,10):   
    for a in range(0,41):
       ans = (en[a]**i)%203
       print (chr(ans))

第一个 for 循环是 "d" 我不确定的私钥值，第二个 for 循环用于遍历 41 长度的元组。我还没有实现 block shift 部分，但我想检查一下这是否是暴力破解简单 RSA 密钥的正确方法。

Answer 1

你应该尝试通过蛮力分解 n:

for i in range(n):
    if n%i == 0:
        print i

，从中你会发现p=7和q=29。

d = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1)

因此 d = e^-1 mod 168，因此 d=162。

Answer 2

我冒昧地改进了 L3viathan 的回答，并提供了一个完整的工作源，可以复制粘贴和运行:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def factor(n):
    for i in range(3, n):
        if n%i == 0:
            return i

e = 5
n = 203

p = factor(n)
q = n//p
phi_n = (p-1) * (q-1)

# Only for python >= 3.8
# From https://docs.python.org/3/library/functions.html#pow
# If mod is present and exp is negative, base must be relatively prime to mod.
# In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.
# d_crack = pow(e, -1, phi_n)

# python < 3.8
d_crack = modinv(e, phi_n)

print('cracked d:', d_crack) # prints "cracked d: 101"

Python RSA 暴力破解

Python RSA Brute Force Check

python

encryption

cryptography

rsa

brute-force