RSA Python和擴展歐幾里得算法來生成私鑰。變量是無

問題簡單RSA加密算法。 Extended Euclidean algorithm用於生成私鑰。與multiplicative_inverse(e, phi)方法的問題。它用於找出兩個數的乘法倒數。該函數不能正確返回私鑰。它返回值None的值。RSA Python和擴展歐幾里得算法來生成私鑰。變量是無

我有以下代碼：

import random 

def gcd(a, b): 
    while b != 0: 
     a, b = b, a % b 
    return a 

#Euclidean extended algorithm for finding the multiplicative inverse of two numbers 
def multiplicative_inverse(e, phi): 
    d = 0 
    x1 = 0 
    x2 = 1 
    y1 = 1 
    temp_phi = phi 

    while e > 0: 
     temp1 = temp_phi/e 
     temp2 = temp_phi - temp1 * e 
     temp_phi = e 
     e = temp2 

     x = x2- temp1* x1 
     y = d - temp1 * y1 

     x2 = x1 
     x1 = x 
     d = y1 
     y1 = y 

    if temp_phi == 1: 
     return d + phi 

def generate_keypair(p, q): 
    n = p * q 

    #Phi is the totient of n 
    phi = (p-1) * (q-1) 

    #An integer e such that e and phi(n) are coprime 
    e = random.randrange(1, phi) 

    #Euclid's Algorithm to verify that e and phi(n) are comprime 
    g = gcd(e, phi) 
    while g != 1: 
     e = random.randrange(1, phi) 
     g = gcd(e, phi) 

    #Extended Euclid's Algorithm to generate the private key 
    d = multiplicative_inverse(e, phi) 

    #Public key is (e, n) and private key is (d, n) 
    return ((e, n), (d, n)) 


if __name__ == '__main__': 
    p = 17 
    q = 23 

    public, private = generate_keypair(p, q) 
    print("Public key is:", public ," and private key is:", private)

由於以下行d = multiplicative_inverse(e, phi)可變d包含None值，則在加密期間，收到以下錯誤：

TypeError: unsupported operand type(s) for pow(): 'int', 'NoneType', 'int'

輸出對於我在問題中提供的代碼：

Public key is: (269, 391) and private key is: (None, 391)

問題：爲什麼變量包含None值。如何解決這個問題？

來源

2016-09-24 Chichi

[在模塊化結構中計算乘法倒數]（https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures）的僞代碼相對簡單並易於映射到Python。建議你再看一遍。你犯了很多錯誤。忘記在'else'分支上返回一些有用的東西只是你問題的開始。 –

那麼我不確定算法本身，並不能告訴你是否它是錯誤或正確的，但你只返回multiplicative_inverse函數的值if temp_phi == 1。否則，結果是無。所以我打賭你的temp_phi != 1當你運行該功能。函數邏輯中可能存在一些錯誤。

來源

2016-09-24 13:04:22

我認爲這是一個問題：

if temp_phi == 1: 
    return d + phi

此功能僅在條件temp_phi等於1返回一定的價值，否則它不會返回任何值。

來源

2016-09-24 13:06:21

RSA Python和擴展歐幾里得算法來生成私鑰。變量是無

回答

相關問題