在Python中測試RSA

Question

我創建了一個用於測試RSA的小代碼，但是當我嘗試使用長度爲6-7位的密鑰解密消息 時，需要一段時間並給出了錯誤的 結果。

from math import sqrt 


def isPrime(n): 
    x = int(sqrt(n)) + 1 

    if n < 2: 
     return False` 

    for i in range(2, x): 
     if (n/i).is_integer(): 
      return (i, False 

    return True 


def factor(num): 
    hold = list() 
    inum = int(sqrt(num) + 1) 

    hold.append((1, num)) 
    if num % 2 == 0: hold.append((2, int(num/2))) 

    for i in range(3, inum, 2): 
     x = num/i 

     if x.is_integer(): 
      hold.append((i, int(x))) 

    return hold 


def egcd(a, b): 
    #Extended Euclidean Algorithm 
    x,y, u,v = 0,1, 1,0 

    while a != 0: 
     q, r = b//a, b%a 
     m, n = x-u*q, y-v*q 
     b,a, x,y, u,v = a,r, u,v, m,n 
    gcd = b 

    return y 


def fastMod(n, e): 
    if e == 0: 
     return 1 

    if e % 2 == 1: 
     return n * fastMod(n, e - 1) 

    p = fastMod(n, e/2) 
    return p * p 


def decrypt(p, q, em): 
    #Uses CRT for decrypting 
    mp = em % p; mq = em % q; 
    dp = d % (p-1); dq = d % (q-1); 
    xp = fastMod(mp, dp) % p; xq = fastMod(mq, dq) % q 

    log = egcd(p, q) 
    cp = (p-log) if log > 0 else (p+log) 
    cq = cp 

    m = (((q*cp)*xp) + ((p*cq)*xq)) % n 

    return m 


def encrypt(pm): 
    return fastMod(pm, e) % n 

有什麼辦法來提高速度或修復任何錯誤嗎？ 我試着解密一些我用9-10位數字的密鑰進行的消息，但是它需要太長的時間才能得到 。

Answer 1

很多東西需要改進，但最值得注意的是：

• 對於RSA加密/解密：fastMod()應該採取模數作爲輸入參數，並通過模數每一次迭代減少。我發現this code這說明了正確的做法。
• 參數生成：在實踐中，不能使用像isPrime()這樣的函數來確定素數，因爲它在指數時間內運行。相反，你應該做Miller-Rabin/Strong pseudo prime tests，它可以使用fastMod()作爲子程序。

順便說一下，您正在實施的教科書RSA，這是非常不安全的。您需要使用諸如OAEP之類的填充來提高安全性，但是您需要非常小心，以便實現這一點以防止各種形式的攻擊（例如旁道攻擊）。

至於你爲什麼得到錯誤的結果，很難說沒有看到你所有的代碼。也許你想包含一個生成參數的main函數，並試圖將它們用於加密和解密。

編輯：我確實注意到這看起來很可疑：log = egcd(p, q)。不知道你在這裏做什麼。我建議你首先計算d作爲e mod (p-1)*(q-1)的倒數，並驗證你得到的是正確的（即乘以d*e mod (p-1)*(q-1)並確保結果爲1）。如果是這樣，那麼使用d做一個fastMod()來查看它是否解密（它應該）。一旦你得到了這個工作，然後繼續使CRT工作。