RSA 加密算法

前置知识

欧拉函数

欧拉函数，即 \(\phi(n)\) ，表示不超过 \(n\) 的数中与 \(n\) 互素的数的个数。

当 \(n\) 为素数时，显然有 \(\phi(n) = n - 1\)

欧拉函数的常用性质

• 积性函数：若 \(gcd(x, y) = 1\) ，则有 \(\phi(xy) = \phi(x) \phi(y)\)
• \(n = \sum_{d | n} \phi(d)\)
• 若 \(n = p ^ k\) ，\(p\) 是素数，则有 \(\phi(n) = p ^ k - p ^ {k - 1}\)
• 若 \(n = \prod_{i = 1} ^ s p_i ^ {k_i}\) ，则有 \(\phi(n) = n \prod_{i = 1} ^ s \frac{p_i - 1}{p_i}\)
• \(\phi(n) = \sum_{d | n} d\ \mu(\frac{n}{d})\)

欧拉定理

若 \(gcd(a, n) = 1\)，则有： \[ a ^ {\phi(n)} \equiv 1\ (mod\ n) \]

逆元

对于整数 \(x\) 而言，若存在 \(y\) 使得 \(xy \equiv 1\ (mod\ p)\)，则称 \(y\) 是 \(mod\ p\) 意义下的逆元，记做： \[ y \equiv x ^ {-1}\ (mod\ p) \]

RSA 加密算法

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它使用一对密钥，分为公钥和私钥。公钥用于加密数据，而私钥用于解密数据。RSA 是目前广泛用于加密和数字签名的加密技术之一。它的名称源自其发明者：Ron Rivest、Adi Shamir 和 Leonard Adleman。

RSA 的具体过程可以描述如下：

1. 挑选两个大素数 \(p\) 和 \(q\)，令 \(n = pq\)，\(n\) 在这里称为模数

2. 计算 \(n\) 的欧拉函数，\(\phi(n) = (p - 1)(q - 1)\)

3. 选择一个公开的加密指数（公钥）\(e\)（通常是一个小素数，\(e < \phi(n)\)），同时生成 \(e\) 在 \(mod\ \phi(n)\) 意义下的逆元 \(d\)，即 \(ed \equiv 1\ (mod\ \phi(n))\)

4. 加密过程：\(c = m ^ e\ mod\ n\)

   \(key_e = \{e, n\}\)

5. 解密过程：\(m = c ^ d\ mod\ n\)

   \(key_d = \{d, n\}\)

原理： \[ c ^ d = m ^ {ed} = m ^ {k\phi(n) + 1} \] 由欧拉定理： \[ c ^ d \equiv m ^ {k\phi(n) + 1} \equiv m\ (mod\ n) \]

代码实现

• 生成密钥：

  from cryptography.hazmat.backends import default_backend
  from cryptography.hazmat.primitives.asymmetric import rsa
  from cryptography.hazmat.primitives import serialization
  
  # 生成RSA密钥对
  private_key = rsa.generate_private_key(
      public_exponent=65537,
      key_size=2048,
      backend=default_backend()
  )
  
  # 保存私钥到文件
  with open("private_key.pem", "wb") as private_key_file:
      private_key_pem = private_key.private_bytes(
          encoding=serialization.Encoding.PEM,
          format=serialization.PrivateFormat.PKCS8,
          encryption_algorithm=serialization.NoEncryption()
      )
      private_key_file.write(private_key_pem)
  
  # 获取公钥
  public_key = private_key.public_key()
  
  # 保存公钥到文件
  with open("public_key.pem", "wb") as public_key_file:
      public_key_pem = public_key.public_bytes(
          encoding=serialization.Encoding.PEM,
          format=serialization.PublicFormat.SubjectPublicKeyInfo
      )
      public_key_file.write(public_key_pem)

• 加密 & 解密：

  from cryptography.hazmat.backends import default_backend
  from cryptography.hazmat.primitives import hashes
  from cryptography.hazmat.primitives.asymmetric import padding
  from cryptography.hazmat.primitives import serialization
  
  # 加载私钥
  with open("private_key.pem", "rb") as private_key_file:
      private_key = serialization.load_pem_private_key(
          private_key_file.read(),
          password=None,
          backend=default_backend()
      )
  
  # 加载公钥
  with open("public_key.pem", "rb") as public_key_file:
      public_key = serialization.load_pem_public_key(
          public_key_file.read(),
          backend=default_backend()
      )
  
  # 要加密的数据
  data = b"Hello, RSA encryption!"
  
  # 加密数据
  ciphertext = public_key.encrypt(
      data,
      padding.OAEP(
          mgf=padding.MGF1(algorithm=hashes.SHA256()),
          algorithm=hashes.SHA256(),
          label=None
      )
  )
  
  print("Ciphertext:", ciphertext)
  
  # 解密数据
  plaintext = private_key.decrypt(
      ciphertext,
      padding.OAEP(
          mgf=padding.MGF1(algorithm=hashes.SHA256()),
          algorithm=hashes.SHA256(),
          label=None
      )
  )
  
  print("Decrypted Data:", plaintext.decode('utf-8'))