如何在 Python 中计算 RSA 私钥

Question

我正在创建一个加密和解密数据的程序。我需要计算密钥，但我不知道如何将代数转换为可在 python.

中使用的表达式

我尝试使用代数，但我无法理解。我正在使用 python 3.6.1

def genkey():
    p = 3 #prime 1
    q = 11 #prime 2
    n = p * q# pubkey part 1
    z = (p-1)*(q-1)# 20
    k = 7 #coprime to z and pub key part 2
    #j = ?
    return (n,k,j)

j 应等于 3，公式为
k * j = 1 ( mod z )

I am using pre-calculated numbers for testing

Link to site

Answer 1

对于 RSA：

我会提供一些我自己学士论文的算法和代码

p和q，两个质数
n = p*q，n是public键的一部分
e 或 public exponent 应该与 n 的欧拉函数互质，对于素数 (p-1)(q-1)

查找 public 指数的代码：

def find_public_key_exponent(euler_function):
    """
    find_public_key_exponent(euler_function)

    Finds public key exponent needed for encrypting.
    Needs specific number in order to work properly.

    :param euler_function: the result of euler function for two primes.
    :return:               public key exponent, the element of public key.
    """

    e = 3

    while e <= 65537:
        a = euler_function
        b = e

        while b:
            a, b = b, a % b

        if a == 1:
            return e
        else:
            e += 2

    raise Exception("Cant find e!")

接下来我们需要欧拉函数 (n) 和 e 的模乘逆函数，它等于 d，我们的最后一个分量：

def extended_euclidean_algorithm(a, b):
    """
    extended_euclidean_algorithm(a, b)

    The result is the largest common divisor for a and b.

    :param a: integer number
    :param b: integer number
    :return:  the largest common divisor for a and b
    """

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


def modular_inverse(e, t):
    """
    modular_inverse(e, t)

    Counts modular multiplicative inverse for e and t.

    :param e: in this case e is a public key exponent
    :param t: and t is an Euler function
    :return:  the result of modular multiplicative inverse for e and t
    """

    g, x, y = extended_euclidean_algorithm(e, t)

    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % t

Public键：(n, e) 私钥： (n, d)

加密：<number> * e mod n = <cryptogram>

解密：<cryptogram> * d mon n = <number>

还有一些限制，所以密码应该是安全的，但它会在我提供的条件下工作。

当然，您需要找到获得大质数的方法，请阅读 prime testing

如何在 Python 中计算 RSA 私钥

How to calculate RSA private key in Python

python

cryptography

rsa

对于 RSA：