RSA加密算法--Java实现

RSA加密算法的背景

1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以
实现非对称加密。这种算法用他们三个人的名字命名，叫做 RSA 算法。从那时直
到现在，RSA 算法一直是最广为使用的"非对称加密算法"。非对称加密算法是指：
1、A 生成密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥
则是保密的；
2、 B 获取 A 的公钥，然后用它对信息加密；
3、A 得到加密后的信息，用私钥解密。
即如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是
安全的

RSA 算法思想

RSA 的加密过程可以表示为(M:明文，C：密文)：
C= C=𝑴 𝒆 mod n ----即 RSA 加密是对明文的 e 次方后模 n，其中关键的在于 e 和 n，所以（e，n）,被称为被称为公钥。
RSA 的解密过程可以表示为(M:明文，C：密文)：
𝑴 = 𝑪 𝒅 mod n----即 RSA 解密是对密文的 d 次方后模 n，其中关键的在于 d 和 n，所以（d，n）,被称为被称为私钥。
算法流程：
<1> 选择 p、q：p 和 q 都是素数，且 p≠q
<2> 计算 n=pq
<3> 计算 φ(n)=(p-1)(q-1)
<4> 选择整数 e：gcd(φ(n), e) = 1，1<e<φ(n)
<5> 计算 d：de mod φ(n) = 1
<6> 公钥：KU = (e，n)
<7> 私钥：KP = (d, n)
以下列较特殊的例子为例：设 p=5,q=7
<1> n=pq=57=35，φ(n)=（5-1）（7-1）=24
<2> 由 1<E<φ(n)且 E 与 24 互质，可取 E=5
<3> ed mod 24 = 1，即 5d mod 24 = 1，可算出 d = 5
<4> 即公钥（N，E）=（35，5），私钥（N，D）=（35，5）
假设需加密内容 M=5，则加密后 C=M
e mod N = 5 5 mod 35=10，再对 C 进行
解密，及 M=C
d mod N =10 5 mod 35 = 5。

Java代码展示

package RSA;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class RSA {
    //RSA加密原理
    //1. 确定公钥---n
    public static int findN(int p,int q) {
        return p*q;
    }
    //2.确定e
    public static int findE(int p,int q) {
        List list = RSA.findArrayInNum(findN(p-1,q-1));
        return  (int) list.get((int)(Math.floor(Math.random()*list.size())));
    }
    //3.确定d
    public static int findD(int e,int p,int q) {
        int d = 0;
        for(int i=1;i<1000;i++) {
            if(e*i%((p-1)*(q-1)) == 1) {
                d = i;
                break;
            }
        }
        return d;
    }
    ///4.加密过程
    public static int encryption(int m,int e,int n) {
            int num ;
            num = (int) Math.pow(m, e);
            num = num%n;
            return num;
    }
    //5.解密过程
    public static int decryption(int c,int d,int n) {
        int num ;
        num = (int) Math.pow(c,d);
        num = num%n;
        return num;
    }
    
    public static List findArrayInNum(int n) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 2;i<n;i++) {
            if(isPrime(i)){
                list.add(i);
            }
        }
        return list;
    }
    public static Boolean isPrime(int a) {
        int k = 0;
        for(int i= 2;i<a;i++) {
            if(a%i==0) {
                k = 1;   //能整除不是质数
                break;
            }
        }
        return k == 0?true:false;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int p = 5;
        int q = 7;
        RSA rsa = new RSA();
        int n = rsa.findN(p, q);
        int e = rsa.findE(p, q);
        int d = rsa.findD(e, p, q);
        System.out.println("请选择要进行的操作:1.RSA加密  2.RSA解密");
        int choice = sc.nextInt();
        if(choice == 1) {
            System.out.println("公钥(E,N):"+e+","+n);
            System.out.println("密钥(D,N)"+d+","+n);
            System.out.println("请输入要加密的内容(这里仅限定数字):");
            int m = sc.nextInt();
            m = rsa.encryption(m, e, n);
            System.out.println("RSA加密之后的结果为:"+m);
        }
        if(choice == 2) {
            System.out.println("公钥(E,N):"+e+","+n);
            System.out.println("密钥(D,N)"+d+","+n);
            System.out.println("请输入要解密的内容(这里仅限定数字):");
            int c = sc.nextInt();
            c = rsa.encryption(c, e, n);
            System.out.println("RSA解密之后的结果为:"+c);
        }
    }
}

RSA加密算法--Java实现

RSA加密算法的背景

RSA 算法思想

Java代码展示

结果展示