使用Java實現RSA演算法的程式

---

RSA演算法的名字來源於其發明者，它用於以高安全性加密文字。RSA技術是最常用的文字加密技術之一，因為它是一種非對稱加密演算法。它利用素數的數學特性來加密文字。

在RSA演算法中，傳送方和接收方都有私鑰。此外，還存在一個共同的公鑰，傳送方與接收方共享。傳送方使用自己的公鑰和私鑰加密明文，接收方使用其私鑰和共同的公鑰解密訊息。

問題陳述 - 我們需要使用RSA演算法生成與給定明文相關的密文。

示例

輸入

prime1 = 5, prime2 = 7, message = 32

輸出

2.0

解釋 - 我們使用RSA演算法加密文字。

輸入

prime1 = 11, prime2 = 23, message = 3434

輸出

228.0

解釋 - 我們根據RSA演算法執行操作來解密它。

方法一

在這種方法中，我們將按照RSA演算法編寫Java程式碼。RSA技術包含三個部分。在第一部分中，我們需要找到私鑰。在第二部分中，我們需要加密訊息，在最後部分中，我們需要解密訊息。

下面，我們提供了編寫RSA演算法的分步指南。

演算法

步驟1 - 將變數'd'初始化為0（私鑰），'e'用於儲存指數。還要定義prime1和prime2變數並初始化它們。

步驟2 - 同樣，將訊息初始化為正整數。

步驟3 - 之後，將prime1和prime2相乘並將結果儲存在primeMul變數中。

步驟4 - 接下來，將prime1 - 1和prime2 - 1相乘並將結果儲存在primeMul1變數中。

步驟5 - 現在，我們需要找到'e'的值，以便'e'和primeMul1的最大公約數為1。e的值可以在2到primeMul1之間。

步驟5.1 - 在getGCD()函式中，如果模為零，則返回num值。否則，遞迴呼叫getGCD()函式。

步驟6 - 我們的公鑰是{e, n}。

步驟7 - 現在，找到私鑰。

步驟7.1 - 遍歷1到9位數字。在迴圈中，如果1 + (m * primeMul1)可以被'e'整除，則將(1 + (m * primeMul1))/e儲存到'd'中，這將用於建立私鑰。

步驟8 - 我們的私鑰是{d, n}。

步驟9 - 要獲取密文，使用Math.pow()方法查詢訊息，並將其與primeMul變數的值取模。

步驟10 - 我們成功獲得了密文。我們需要解密密文以將其轉換為明文。

步驟11 - 要再次獲取明文，我們需要取(cipherd % primeMul)。

示例

import java.math.*;
import java.util.*;
public class Main {
   public static int getGCD(int mod, int num) {
      // If the mod is zero, return the num
      if (mod == 0)
         return num;
      else
         // recursive function call
         return getGCD(num % mod, mod);
   }
   public static void main(String args[]) {
      int d = 0, e; // Intialization      
      int message = 32; // number message      
      int prime1 = 5; // 1st prime number p
      int prime2 = 7; // 2nd prime number q
      int primeMul = prime1 * prime2; // performing operations
      int primeMul1 = (prime1 - 1) * (prime2 - 1);
      System.out.println("primeMul1 is equal to : " + primeMul1 + "\n");
      // Finding the valid public key
      for (e = 2; e < primeMul1; e++) {
         // Here e is a public key
         if (getGCD(e, primeMul1) == 1) {
            break;
         }
      }
      // Printing the public key
      System.out.println("Public key e is = " + e);
      // Calculating the private key
      for (int m = 0; m <= 9; m++) {
         // get the value of temp
         int temp = 1 + (m * primeMul1);
         // private key
         if (temp % e == 0) {
            d = temp / e;
            break;
         }
      }
      System.out.println("d is : " + d);
      double cipher;
      BigInteger d_message;
      // getting the cipher text
      cipher = (Math.pow(message, e)) % primeMul;
      System.out.println("Cipher text is : " + cipher);
      // Int to BigInteger
      BigInteger bigN = BigInteger.valueOf(primeMul);
      // Float to bigINt
      BigInteger bigC = BigDecimal.valueOf(cipher).toBigInteger();
      // decrypting the message
      d_message = (bigC.pow(d)).mod(bigN);
      // print decrypted message
      System.out.println("Decrypted text is : " + d_message);
   }
}

輸出

primeMul1 is equal to : 24

Public key e is = 5
d is : 5
Cipher text is : 2.0
Decrypted text is : 32

時間複雜度 - O(logn)，因為我們找到了GCD。

空間複雜度 - O(1)，因為我們使用了常量空間。

我們學習瞭如何實現RSA演算法。它是加密重要訊息的最佳技術之一。但是，對於大型訊息和素數，它也很耗時，但是當我們使用大型素數時，它變得更加複雜，並且對於駭客來說很難破解訊息。