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和扩展欧几里得算法来生成私钥。变量是无

回答

相关问题