密码学 - RSA加密

上一页
下一页

正如我们在前面的章节中看到的，RSA（Rivest-Shamir-Adleman）是一种流行的加密方法，用于保护在线共享的数据。它依赖于非常大的素数的数学特性。

RSA 加密是如何工作的？

RSA 加密通过以只有授权方才能解密的方式对数据进行编码来保护数据。以下是 RSA 加密工作原理的简要概述：

密钥生成

  • 从两个大素数开始，例如 p 和 q。
  • 将 p 和 q 相乘得到 n。
  • 找到 Φ(n)，计算方法为 (p-1) * (q-1)。Φ 代表欧拉函数。
  • 选择一个介于 1 和 Φ(n) 之间的整数 e，并且除了 1 之外与 Φ(n) 没有公因子（它们互质）。
  • 找到 d，它是模 Φ(n) 的 e 的乘法逆元。这意味着当 e 和 d 相乘时，结果是 1 余 Φ(n)，表示为 d * e ≡ 1 (mod Φ(n))。

加密

  • 要加密消息，首先将其转换为数字，通常使用预定义的代码，例如 ASCII 或 Unicode。
  • 然后使用公钥单独加密消息的每一部分。
  • 加密包括将消息块的数字形式提高到 e 的幂，并将结果除以 n，取余数。
  • 生成的加密消息（密文）是一串无法读取的数字，可以发送到不安全的通道。

使用 Python 实现 RSA

RSA 加密可以使用不同的方法实现，例如：

  • 使用 random 模块
  • 使用 rsa 模块
  • 使用 cryptography 模块

因此，在接下来的几节中，我们将详细介绍每种方法，以便您了解如何创建 RSA 加密以及更好地理解 Python。

使用 random 模块

此程序将使用 Python 的 random 模块为密钥生成创建随机数。在我们的代码中，我们将有 generate_keypair() 和 encrypt(public_key, plaintext) 方法。调用 generate_keypair() 方法时，它会生成随机素数 p 和 q。

因此，random 模块对于生成随机素整数 p 和 q 以及计算随机公指数 e 至关重要。这些随机值对于 RSA 加密技术的安全性与随机性非常重要。

示例

以下是一个使用 Python 的 random 模块进行 RSA 加密的 Python 程序：

import random

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

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

def mod_inverse(a, m):
   g, x, y = extended_gcd(a, m)
   if g != 1:
      raise Exception('Modular inverse does not exist')
   else:
      return x % m

def generate_keypair():
   p = random.randint(100, 1000)
   q = random.randint(100, 1000)
   n = p * q
   phi = (p - 1) * (q - 1)

   while True:
      e = random.randint(2, phi - 1)
      if gcd(e, phi) == 1:
         break
    
      d = mod_inverse(e, phi)
      return ((e, n), (d, n))

def encrypt(public_key, plaintext):
   e, n = public_key
   cipher = [pow(ord(char), e, n) for char in plaintext]
   return cipher

# our public and private keys
public_key, private_key = generate_keypair()
# Our secret message
message = "Hello, world!"
print("Our plaintext message: ", message)
encrypted_message = encrypt(public_key, message)
print("Encrypted message:", encrypted_message)

以下是上述示例的输出：

输入/输出

Our plaintext message:  Hello, world!
Encrypted message: [5133, 206, 9012, 9012, 7041, 3509, 7193, 3479, 7041, 6939, 9012, 1255, 3267]

使用 rsa 模块

可以使用 Python 的 rsa 包轻松高效地实现 RSA 密码术。

安装 rsa 模块

首先，如果您尚未安装 rsa 模块，则可以使用 pip 安装它：

pip install rsa

生成 RSA 密钥

安装模块后，您可以使用此 rsa 模块生成 RSA 密钥对。方法如下：

import rsa
# create a key pair with 1024 bits key length
(public_key, private_key) = rsa.newkeys(1024)

以上代码将生成一对 RSA 密钥：一个用于加密（公钥），另一个用于解密（私钥）。

加密消息

拥有密钥对后，您可以使用它们来加密和解密消息。

# Encrypting a message
message = b"Hello, world!"
encrypted_message = rsa.encrypt(message, public_key)

# Decrypting the message
decrypted_message = rsa.decrypt(encrypted_message, private_key)

print("Original message:", message.decode())
print("Decrypted message:", decrypted_message.decode())

签名和验证

RSA 也可以用于数字签名。以下是签名和验证给定消息的方法：

# Signing a message
signature = rsa.sign(message, private_key, 'SHA-256')

# Verifying the signature
rsa.verify(message, signature, public_key)

完整代码

以下是供您参考的完整代码。运行代码并查看输出：

import rsa
# create a key pair with 1024 bits key length
(public_key, private_key) = rsa.newkeys(1024)

# Encrypting a message
message = b"Hello, world!"
encrypted_message = rsa.encrypt(message, public_key)

print("Original message:", message.decode())
print("Encrypted message:", encrypted_message)

# Signing a message
signature = rsa.sign(message, private_key, 'SHA-256')

# Verifying the signature
rsa.verify(message, signature, public_key)

以下是上述示例的输出：

输入/输出
Original message: Hello, world!
Encrypted message: b'g\x078$xx,5A[\x11h\r\x15v4\x0f-?\xa8\x18\xad\xda\x93\xa8\x982\x1b\xf3\xaee\xd3\x85+MZ*=\xd0\x8f\xefV\xed5i\xc9A\xe4\xa377\x1d\xce\xf0\xb6\xa9/:\xf8Y\xf9\xf1\x866\x8d\x1c!\xb9J\xf1\x9dQ8qd\x01tk\xd61U\x8c2\x81\x05wp\xcb)g6\t\xe9\x03\xa0MQR\xcb\xa6Bhb\x05\xb5\x06f\x04\r\x17\x9c\xe8B%]\x95\xd8D\x84Xr\x9c\x93\xc8\xaeN[m'

使用 Cryptography 模块

因此，我们可以使用 cryptography 模块生成 RSA 密钥对。此代码生成一个私有 RSA 密钥并提取匹配的公钥。两个密钥都转换为 PEM 格式并存储在单独的文件中。这些密钥可用于加密和解密消息。提供的代码演示了使用公钥进行加密。

示例

以下是使用 cryptography 模块进行 RSA 加密的 Python 实现：

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa

# Generate an RSA private key
private_key = rsa.generate_private_key(
   public_exponent=65537,
   key_size=2048,
   backend=default_backend()
)

# Get the public key from the private key
public_key = private_key.public_key()

# The keys to PEM format
private_key_pem = private_key.private_bytes(
   encoding=serialization.Encoding.PEM,
   format=serialization.PrivateFormat.PKCS8,
   encryption_algorithm=serialization.NoEncryption()
)
public_key_pem = public_key.public_bytes(
   encoding=serialization.Encoding.PEM,
   format=serialization.PublicFormat.SubjectPublicKeyInfo
)

# Save the keys to files or use them as needed
with open('private_key.pem', 'wb') as f:
   f.write(private_key_pem)

with open('public_key.pem', 'wb') as f:
   f.write(public_key_pem)

# Encrypting a message
message = b"Hello, world!"
encrypted_message = public_key.encrypt(
   message,
   padding.OAEP(
      mgf=padding.MGF1(algorithm=hashes.SHA256()),
      algorithm=hashes.SHA256(),
      label=None
   )
)

print("Original message:", message.decode())
print("Encrypted message:", encrypted_message)

以下是上述示例的输出：

输入/输出
Original message: Hello, world!
Encrypted message: b'L\xae\x1f\xf6\xe6\x91q#+R\xdf\tv\xcb\x8d\xb6\x03g)/\x80=\xb9\xf7\x98\xe3\xbf\xdau\xcb\xbd\nFTo\xe0\xb9\rc\xf2\x8c \x03\xebl\x11\xe7\'\xb4\xe1\xdaJ\xab\x9cD\x184\xae4[\xcb\x94a\x8bP\xa5\xac+r\x9d\xc1\xc1P\x82\xfb\xb4I"\xa4W\x1e\x0b\xed\xd8\xc9\x9d=\x81\xda\n\xfd\xa2\xb8&6T3\xdf>\xd5o\xc0\xc2\x0c\x05gk\xa3\xd2\xfa\xc4\xe5c\xe6\xc88He\xff-\x14\xc2?@*\xaao\xd3s\xbeEE\xa5T\x8b1\x0f\x1aT\x1c\xd7?\xef\x8f$\xf7\x99(\xc1\x9c\xd5\xdb\x92\xe2b}Efzntjy\xc7\xdf\xe6\x1a\xbe\x9e\x1au\xe5\xb2p\xa4\xbb\xd6>\xf4\x83\x9c]q7(x\\\x1b\x83\xe9Q\x8aB\xe3\xe9f\x1dy\x15\xf2r\xda\x01+\xf9c\xaf\xd5m\xba\x9du\xda.\xfc&\xedQK\xba\x8e\xbe^\x7fc\x8d\xab\xbb\xebK\n\x9a\x01\xe2q\xcd\xc61T\xe2\n\x11\x94x\xa6?dLc\x82\x02%\xf8\x18-\xea'

使用 Java 实现 RSA

下面的 Java 代码使用 RSA 加密算法。该代码利用许多 Java 标准库模块和类，例如 java.math.BigInteger、java.security.SecureRandom 和 java.lang.String。BigInteger 类接受任意精度的整数，这对于处理 RSA 加密和解密中的大数很有用。SecureRandom 类生成密码学上安全的随机数，然后用于生成 RSA 密钥。String 类用于操作字符串。

示例

使用 Java 实现 RSA 算法如下：

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSA {

   private BigInteger prKey;
   private BigInteger pubKey;
   private BigInteger mod;

   // Generate public and private keys
   public RSA(int bitLength) {
      SecureRandom random = new SecureRandom();
      BigInteger p = BigInteger.probablePrime(bitLength / 2, random);
      BigInteger q = BigInteger.probablePrime(bitLength / 2, random);
      mod = p.multiply(q);
      BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
      pubKey = BigInteger.probablePrime(bitLength / 4, random);
      while (phi.gcd(pubKey).intValue() > 1) {
         pubKey = pubKey.add(BigInteger.ONE);
      }
      prKey = pubKey.modInverse(phi);
   }

   // Encrypt plaintext
   public BigInteger encrypt(String message) {
      BigInteger plaintext = new BigInteger(message.getBytes());
      return plaintext.modPow(pubKey, mod);
   }

   public static void main(String[] args) {
      RSA rsa = new RSA(1024);

      // Message to encrypt
      String plaintext = "HELLO TUTORIALSPOINT";
      System.out.println("Plaintext: " + plaintext);
      // Encrypt the message
      BigInteger ciphertext = rsa.encrypt(plaintext);
      System.out.println("Ciphertext: " + ciphertext);
   }
}

以下是上述示例的输出：

输入/输出

Plaintext: HELLO TUTORIALSPOINT
Ciphertext: 81613159022598431502618861082122488243352277400520456503112436392671015741839175478780136032663342240432362810242747991048788272007296529186453061811896882040496871941396445756607265971854347817972502178724652319503362063137755270102568091525122886513678255187855721468502781772407941859987159924896465083062

使用 C++ 实现 RSA

以下是使用C++实现的简单RSA算法。这段代码涵盖了密钥生成、加密和解密过程。

示例

#include<iostream>
#include<math.h>
using namespace std;
// find gcd
int gcd(int a, int b) {
   int t;
   while(1) {
      t= a%b;
      if(t==0)
      return b;
      a = b;
      b= t;
   }
}
int main() {
   //2 random prime numbers
   double p = 13;
   double q = 11;
   double n=p*q;//calculate n
   double track;
   double phi= (p-1)*(q-1);//calculate phi
   //public key
   //e stands for encrypt
   double e=7;
   //for checking that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
   while(e<phi) {
      track = gcd(e,phi);
      if(track==1)
         break;
      else
         e++;
   }
   //private key
   double d1=1/e;
   double d=fmod(d1,phi);
   double message = 9;
   double c = pow(message,e); //encrypt the message
   c=fmod(c,n);
   cout<<"Original Message = "<<message;
   cout<<"\n"<<"Encrypted message = "<<c;
   return 0;
}

以下是上述示例的输出：

输入/输出

Original Message = 9
Encrypted message = 48

摘要

RSA加密在保障在线数据安全方面起着至关重要的作用。它涉及生成成对的公钥和私钥，从而创建安全连接。这些密钥用于加密和解密消息，确保只有预期的接收者才能访问信息。您可以使用不同的方法在Python中实现RSA加密，例如random模块、RSA模块或cryptography模块。每种方法都有其自身的优势，使您在保护数据方面具有灵活性和效率。我们也已经使用Java和C++实现了RSA算法。

打印页面
上一页
下一页
广告