密碼學 - 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演算法。

列印頁面
上一頁
下一頁
廣告
© . All rights reserved.