密碼學程序設計實現(xiàn)RSA加解密

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class ProducePrime {
    /*
     * 獲取第一個素數(shù)的方法
     */
    
    public Integer Prime1() {
        List<Integer> list = new ArrayList<Integer>();// 存儲素數(shù)的集合
        for (int i = (int) Math.pow(2, 16) + 1; i <= Math.pow(2, 17); i+=2) {// 判斷奇數(shù)
            boolean num2 = true;// 防止被false覆蓋
            for (int m = 2; m <= Math.sqrt(i); m++) {// 提高試除效率
                if (i % m == 0) {
                    num2 = false;// 不是素數(shù)
                    break;
                } else if (num2) {
                    list.add(i);// 存儲素數(shù)到集合中
                }
            }

        }
        Random random = new Random();
        int n = random.nextInt(list.size());
        return list.get(n);

    }

    /*
     * 獲取第二個素數(shù)的方法
     */
    
    public int Prime2() {
        int max = (int) Math.pow(2, 22);
        int min = (int) Math.pow(2, 21);
        int temp = 0;
        int num = new Random().nextInt(max - min + 1) + min;// 隨機獲取指定范圍內(nèi)的數(shù)字
        if (Odd(num)) {
            boolean flag = true;
            for (int m = 2; m <= Math.sqrt(num); m++) {// 提高試除效率
                if (num % m == 0) {
                    flag = false;// 不是素數(shù)
                    num = num + 2;
                    continue;
                } 
                else if(flag) {
                    temp = num;
                }
            }
        }
        else {
            num = num + 1;
            boolean flag = true;
            for (int m = 2; m <= Math.sqrt(num); m++) {// 提高試除效率
                if (num % m == 0) {
                    flag = false;// 不是素數(shù)
                    num = num + 2;
                    continue;
                } 
                else if(flag) {
                    temp = num;
                }
            }
        }
        return temp;

    }

    public boolean Odd(int n) {
        boolean flag = true;
        if (n % 2 == 0) {
            flag = false;
            return flag;
        } else {
            return flag;
        }
    }

}

class Division {
    public void divison(int m) {
        int temp = 1;
        int c = 1;
        int[] arr = new int[1000];
        arr[0] = 2;
        for (int i = 3; i < 1000; i+=2) {// 判斷奇數(shù)即可
            boolean flag = true;
            for (int q = 2; q <= Math.sqrt(i); q++) {
                if (i % q == 0) {
                    flag = false;// 該數(shù)不是素數(shù)
                    break;
                }
            }
            if (flag) {
                arr[temp] = i;// 存儲1000以內(nèi)素數(shù)，用于試除
                temp++;
            }
        }
        
        System.out.println("1000以內(nèi)素數(shù)試除開始:");
        System.out.println();
        
        for (int a = 0; a < temp; a++) {
            int b = m % arr[a];// 試除1000以內(nèi)的素數(shù),保存余數(shù)
            System.out.println("試除第" + c + "次:" + m + " % " + arr[a] + "=" + b);
            c++;
            System.out.println("得到的余數(shù)為:" + b);
            System.out.println();
        }
        System.out.println("1000以內(nèi)素數(shù)試除結束");
    }
}

class MillerRabin {
    /*
     * Miller-Rabin檢測算法，n為檢測數(shù)據(jù)
     */
    
    public boolean MillerRabin2(int n) {
        int a = new Random().nextInt(n) + 1;
        long s = 1;
        long n2 = n - 1;
        long n3 = n - 1;
        int t = 0, temp = 0;
        boolean flag = true;
        out :
            for(;;) {
            if (n2 % 2 != 0) {
                s = temp;
                break out;
            }else {
                n2 = n2 / 2;
                temp++;
            }
        }
        t = (int) (n3 / Math.pow(2, s));
        int b = (int) Math.pow(a, t);
        for(long i = (long) Math.pow(2,s - 1); i >= 1; i--){
            if((Math.pow(b, i) + 1) % n == 0){
                break;
            }
            if(i == 1){
                if((Math.pow(b, i) - 1) % n == 0){
                    break;
                }
                else{
                    flag = false;
                }
            }
        }
        return flag;
    }

}

class EuclideanAlgorithm {
    /*
     * 獲取私鑰d的方法
     * 歐幾里得擴展算法
     * 公鑰e = 17
     */
    
    BigInteger x, y, a, b, t, r;
    public BigInteger exgcd(BigInteger a, BigInteger b) {
        if (b == BigInteger.valueOf(0)) {
            x = BigInteger.valueOf(1);
            y = BigInteger.valueOf(0);
            return a;
        }
        r = exgcd(b, a.mod(b));
        t = x;
        x = y;
        y = t.subtract((a.divide(b)).multiply(y));
        return r;
    }
    
    public void XY(BigInteger fn, BigInteger e) {
        System.out.println("解得x為:" + x);
        System.out.println("解得y為:" + y);
        if (y.compareTo(BigInteger.valueOf(0)) < 0) {
            System.out.println("所以密鑰d為:" + (y.add(fn)));
        }else {
            System.out.println("所以密鑰d為:" + y);
        }
        
    }

}

class MoChongFuPingFang {
    /*
     * 模重復平方算法加密
     * 輸入加密明文m = 32655，公鑰e = 17，模數(shù)為n
     */
    
    String binary;
    long a = 1;
    BigInteger a2 = BigInteger.valueOf(a);

    public BigInteger Encryption(long m, long e2, long n) {
        binary = Long.toBinaryString(e2);
        BigInteger a3 = a2;
        BigInteger m2 = BigInteger.valueOf(m);
        BigInteger m3 = m2;
        BigInteger n2 = BigInteger.valueOf(n);
        
        for (int i = binary.length() - 1; i >= 0; i--) {
            if (binary.charAt(i) == '1') {
                a3 = a2.multiply(m2).mod(n2);
                a2 = a3;
                m3 = m2.multiply(m2).mod(n2);
                m2 = m3;
            }else {
                m3 = m2.multiply(m2).mod(n2);
                m2 = m3;
            }
        }
        return a3;  
    }

}

class PingFangCheng {
    /*
     * 平方乘算法解密
     * 密文m，私鑰d，模數(shù)n
     */
    
    String binary;
    long x = 0, y = 1;
    BigInteger x2 = BigInteger.valueOf(x);
    BigInteger y2 = BigInteger.valueOf(y);
    public BigInteger Decryption(long m, long d, long n) {
        binary = Long.toBinaryString(d);
        BigInteger x3 = x2;
        BigInteger m2 = BigInteger.valueOf(m);
        BigInteger n2 = BigInteger.valueOf(n);
        BigInteger y3 = y2;
        BigInteger c = BigInteger.valueOf(2);
        BigInteger c2 = BigInteger.valueOf(1);
        for(int i = 0; i < binary.length(); i++) {
            x3 = x2.multiply(c);
            x2 = x3;
            y3 = y2.multiply(y2).mod(n2);
            y2 = y3;
            if (binary.charAt(i) == '1') {
                x3 = x2.add(c2);
                x2 = x3;
                y3 = y2.multiply(m2).mod(n2); 
                y2 = y3;
            }
        }
        return y3;
    }

}

public class RSADemo {
    public static void main(String[] args) {
        ProducePrime ProducePrime = new ProducePrime();
        Division Division = new Division();
        EuclideanAlgorithm euclideanAlgorithm = new EuclideanAlgorithm();
        MoChongFuPingFang moChongFuPingFang = new MoChongFuPingFang();
        PingFangCheng pingFangCheng = new PingFangCheng();
        MillerRabin MillerRabin = new MillerRabin();
        Scanner scanner = new Scanner(System.in);
        System.out.println("/****************/");
        System.out.println("RSA算法加密解密實現(xiàn)");
        System.out.println("/****************/");
        int p = 1009;//ProducePrime.Prime1();
        //int p = ProducePrime.Prime1();
        System.out.println("輸出滿足要求的第一個素數(shù)p:" + p);
        int q = 997;//ProducePrime.Prime2();
        //int q = ProducePrime.Prime2();
        System.out.println("輸出滿足要求的第二個素數(shù)q:" + q);
        System.out.println("/****************/");
        long n = (long)p * q;//避免越界，強制轉(zhuǎn)型
        long fn = (long)(p - 1) * (q - 1);
        System.out.println("n=p*q=" + n);
        System.out.println("f(n)=(p-1)*(q-1)=" + fn);
        System.out.println("/****************/");
        Division.divison(p);
        System.out.println("/****************/");
        int p2 = (int)p;
        boolean flag = MillerRabin.MillerRabin2(p2);
        System.out.println("Miller-Rabin算法檢測標志符為:" + flag);
        System.out.println("/****************/");
        System.out.println("請輸入公鑰e:");
        long e = scanner.nextLong();
        BigInteger e3 = BigInteger.valueOf(e);
        BigInteger fn2 = BigInteger.valueOf(fn);
        System.out.println("公鑰e與fn的最大公約數(shù)為:" + euclideanAlgorithm.exgcd(fn2, e3));//最大公約數(shù)        
        euclideanAlgorithm.XY(fn2, e3);
        System.out.println("/****************/");
        //加密明文
        System.out.println("加密開始:");
        System.out.println("請輸入明文m:");
        long m = scanner.nextLong();
        System.out.println("請輸入公鑰e:");
        long e2 = scanner.nextLong();
        System.out.println("加密后的密文m2為:" + moChongFuPingFang.Encryption(m, e2, n));
        System.out.println("/****************/");
        //解密密文
        System.out.println("解密開始:");
        System.out.println("請輸入密文m2:");
        long m2 = scanner.nextLong();
        System.out.println("請輸入密鑰d:");
        long d2 = scanner.nextLong();
        System.out.println("解密后的明文為:" + pingFangCheng.Decryption(m2, d2, n));
    }
}
  • 一些說明：
  1. 大素數(shù)的運算使用BigInteger類解決數(shù)據(jù)長度溢出的問題。
  2. 自動獲取的大素數(shù)用來加解密會失敗，多番檢查也沒找到問題所在。
  3. 自定義的素數(shù)p = 1009，q = 997，公鑰e = 17可以加解密成功。
  4. 如果您有興趣，不妨試試解決這個問題，手動狗頭。
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 本文主要介紹移動端的加解密算法的分類、其優(yōu)缺點特性及應用，幫助讀者由淺入深地了解和選擇加解密算法。文中會包含算法的...
    蘋果粉閱讀 11,679評論 5贊 29
  • 公鑰密碼系統(tǒng)及RSA公鑰算法 本文簡單介紹了公開密鑰密碼系統(tǒng)的思想和特點，并具體介紹了RSA算法的理論基礎，工作原...
    火狼o閱讀 4,432評論 2贊 15
  • 姓名：于川皓 學號：16140210089 轉(zhuǎn)載自：https://baike.baidu.com/item/RS...
    道無涯_cc76閱讀 2,804評論 0贊 1
  • 密鑰分為兩種：對稱密鑰與非對稱密鑰 對稱密鑰加密，又稱私鑰加密，即信息的發(fā)送方和接收方用一個密鑰去加密和解密數(shù)據(jù)。...
    卡卡羅2017閱讀 10,500評論 0贊 6
  • 我媽今天陪客戶吃飯去了，老說舍不得我，要早早回家，但卻經(jīng)常偶爾性回家已半夜。今天讓我爸拉著我去接他。給我打了電話，...
    蘇田田閱讀 224評論 0贊 0

友情鏈接更多精彩內(nèi)容