非对称加密体制——RSA算法

RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。它是一种比较典型的公开密钥加密算法，也是目前最常用的公钥加密算法。

一、原理及其安全性

在RSA中，e为加密指数，通常为65537(0x10001)，D为私钥，N为模数(由大素数P,Q构成)，(N,E)为公钥，C为密文，M为明文

1.加密和解密

明文为m，密文为c，则 RSA 的加密过程为：

c \equiv m^e \mod n

其中(e, n)为公钥。

解密过程中，使用私钥d来计算明文：

m \equiv c^d \mod n

如果用于数字签名，则与之相反，即私钥加密公钥解密。

密钥对的生成过程：

选择两个大素数(通常是2048位)p,q,得到N：

N=p*q

得到phi(n)：

phi(n)=lcm(p-1,q-1)

其中lcm表示最小公倍数。

根据欧拉函数，可得phi(n)=phi(p)*phi(q)=(p-1)*(q-1)

得到公钥加密指数e：1<e<phi(n),gcd(e,phi(n))=1 ，其中gcd表示求最大公约数。

得到私钥D:1<D<phi(n),e*D\mod phi(n)=1

以上，完成密钥对生成。

2.关于欧拉函数

(1) 欧拉函数：设m 是一个正整数，则在小于m 的正整数中与m 互素的整数的个数记为phi(m) , 也即\varphi(m)，叫做欧拉函数。

(2)若p 是素数，则\varphi(p)=p-1

(3)若m,n互素，则\varphi(mn)=\varphi(m)\varphi(n)

(4) 欧拉定理：设m 是大于 1 的整数，如果整数a 满足gcd(a,m)=1,则：

a^{\varphi(m)}\equiv1(mod\:m)

3.证明RSA的正确性

(1) 当 M 和 N 互素

(2) M 和 N不互素，所以 M 与 N 必定有除1以外的公因子，而又因 N 等于质数p和质数q的

乘积，所以 M 必然等于cp 或cq ,c\in N^* 。

根据：

即：

假设 ( m = cp )，然后，有如下推理过程：

则：

得证。

4.RSA的安全性

问题设定：已知c \equiv m^e \mod n。

此时的安全性在于，攻击者是否容易求得明文 M 。

一种“简单”的方法是：通过求得私钥 D，来获取明文 M 。要获得私钥 D ，根据密钥对的计算过程，需要将 N 分解为 P 和 Q ，然后计算 P−1 和 Q−1 从而由 phi(N) 推算出 D 。

RSA的安全性依赖于大数因子分解的困难性，至今还没有一个多项式时间的方法来实现大数因子分解。

这里需要补充两点：

第一，合数分解问题仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法，但是，也还没有人能够证明这种算法不存在。

第二，RSA的安全性是否等同于大数分解，也一直未能得到理论上的证明。因为没有证明破解RSA就一定需要做大数分解，不过至今也还没有找到比它更简单的方法

同样的，在数字签名之中，想要伪造，也必须求得私钥D。

二、代码实现

C++实现：

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

// Function to find gcd
int gcd(int a, int b) {
    int temp;
    while (true) {
        temp = a % b;
        if (temp == 0) {
            return b;
        }
        a = b;
        b = temp;
    }
}

// Function to find modular exponentiation
long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

// Simple RSA implementation
int main() {
    // Two random prime numbers (in a real application, these should be large random primes)
    double p = 13;
    double q = 17;

    // First part of public key:
    double n = p * q;

    // Finding other part of public key.
    // e stands for encrypt
    double e = 2;
    double phi = (p - 1) * (q - 1);
    while (e < phi) {
        // e must be co-prime to phi and smaller than phi.
        if (gcd((int)e, (int)phi) == 1) {
            break;
        } else {
            e++;
        }
    }

    // Private key (d stands for decrypt)
    // Choosing d such that it satisfies d*e = 1 + k * phi
    int k = 2;  // A constant value
    double d = (1 + (k * phi)) / e;

    // Message to be encrypted
    double message = 12;

    // Encryption c = (msg ^ e) % n
    double c = modExp(message, e, n);
    std::cout << "Encrypted message: " << c << std::endl;

    // Decryption m = (c ^ d) % n
    double m = modExp(c, d, n);
    std::cout << "Decrypted message: " << m << std::endl;

    return 0;
}

python实现：

import random
from sympy import isprime, mod_inverse

def generate_prime_candidate(length):
    # Generate random prime candidate
    p = random.getrandbits(length)
    # Apply a mask to set MSB and LSB to 1
    p |= (1 << length - 1) | 1
    return p

def generate_prime_number(length=1024):
    p = 4
    # Keep generating until a prime is found
    while not isprime(p):
        p = generate_prime_candidate(length)
    return p

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

def generate_keypair(p, q):
    if not (isprime(p) and isprime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')
    # n = pq
    n = p * q

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

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

    # Use 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)

    # Use Extended Euclid's Algorithm to generate the private key
    d = mod_inverse(e, phi)
    
    # Return public and private keypair
    # Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

def encrypt(pk, plaintext):
    # Unpack the key into it's components
    key, n = pk
    # Convert each letter in the plaintext to numbers based on the character using a^b mod m
    cipher = [pow(ord(char), key, n) for char in plaintext]
    # Return the array of bytes
    return cipher

def decrypt(pk, ciphertext):
    # Unpack the key into its components
    key, n = pk
    # Generate the plaintext based on the ciphertext and key using a^b mod m
    plain = [chr(pow(char, key, n)) for char in ciphertext]
    # Return the array of bytes as a string
    return ''.join(plain)

if __name__ == '__main__':
    print("Generating your public/private keypairs now . . .")
    p = generate_prime_number()
    q = generate_prime_number()
    public, private = generate_keypair(p, q)
    print("Your public key is ", public ," and your private key is ", private)
    message = input("Enter a message to encrypt with your public key: ")
    encrypted_msg = encrypt(public, message)
    print("Your encrypted message is: ")
    print(''.join(map(lambda x: str(x), encrypted_msg)))
    print("Decrypting message with private key ", private ," . . .")
    print("Your message is:")
    print(decrypt(private, encrypted_msg))