RSA算法原理与加密解密 求私钥等价求求模反元素 等价于分解出2个质数 (r*X+1)%[(p-1)(q-1)]=0

Rsapaper.pdf http://people.csail.mit.edu/rivest/Rsapaper.pdf

【概述Abstract

1、将字符串按照双方约定的规则转化为小于n的正整数m，可能分为多段，这不是关键；

2、加密过程同解密过程，都是取明/密文的public/private次方，然后对公共的n取余数；

3、整数转化为字符串

】

A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret prime numbers p and q. Decryption is similar; only a different, secret, power d is used, where e · d ≡ 1 (mod (p − 1) · (q − 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.

【破解密钥思路】

When the user reveals E he reveals a very inefficient method of computing D(C): testing all possible messages M until one such that E(M) = C is found. If property (c) is satisfied the number of such messages to test will be so large that this approach is impractical.

【单向门  邮局信箱  A function E satisfying (a)-(c) is a “trap-door one-way function;” if it also satisfies (d) it is a “trap-door one-way permutation.”】

These functions are called “one-way” because they are easy to compute in one direction but (apparently) very difficult to compute in the other direction.

V Our Encryption and Decryption Methods

【*和论文结合起来看】

【

注意取e d 顺序，倾向*观点

Note: The authors of the original RSA paper carry out the key generation by choosing d and then computing e as the modular multiplicative inverse of d modulo φ(n). Since it is beneficial to use a small value for e (e.g., 65,537) in order to speed up the encryption function, current implementations of RSA, such as those following PKCS#1, choose e and compute d instead.^[2][18]】

RSA (cryptosystem) - Wikipedia https://en.wikipedia.org/wiki/RSA_(cryptosystem)

【

欧拉函数定义

注意不是整除，是存在只有为1的公约数

Euler's totient function - Wikipedia https://en.wikipedia.org/wiki/Euler%27s_totient_function

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.^[2][3] The integers k of this form are sometimes referred to as totatives of n.

大于等于1但小于等于（此处包含与否不影响结果）n的正整数中与n的最大公约数为1的正整数的个数

注意，结果中包含1；

】

【1既不是质数（素数）但是1与所有正整数互质】

【最大公约数   Greatest common divisor  Greatest common divisor - Wikipedia https://en.wikipedia.org/wiki/Greatest_common_divisor 】

【小于等于p^k的数中，与p^k有非1公约数的正整数的公约数为且仅为p的若干次方，从0到k次方，最小的数为p，下一个为p*2，下一个为p*3、、、至p*p^(k-1)，即p*i，i=1,2,3...,p^(k-1)，故

总数p^k-扣除的个数p^(k-1)】

若p1和p2互质,n=p1*p2,则ψ(n)= ψ(p1*p2)= ψ(p1) ψ(p2)

【gcd(p1,j1i)=1 gcd(p2,j2i)=1  gcd(p1,p2)=1

gcd(p1,j1i*j2i)=1 gcd(p2,j1i*j2i)=1

与p1互质的数与p2也互质，反之亦然

a b 均与p互质，则a*b也与p互质

故与p1*p2互质的数 为 （1,j1i）* (1,j2i)

个数为个数的积】

任意一个大于1的正整数都可以写成一系列质数的积

【算术基本定理 区别于 代数基本定理 见*英文版】

因为

n = (p1^k1)* (p2^k2)*……(pr^kr)   (p1~pr都是质数)

所以

ψ(n)= ψ((p1^k1)) ψ(p2^k2) ……ψ(pr^kr)   定理4

ψ(n)= (p1^k1)*(1-1/p1) * (p2^k2)(1-1/p2)……(pr^kr)*(1-1/pr)   定理3

ψ(n)= (p1^k1)* (p2^k2)*……(pr^kr) * (1-1/p1) (1-1/p2)…… (1-1/pr)

ψ(n)=n (1-1/p1) (1-1/p2)…… (1-1/pr)

　　　　【<n 且为正整数

=[p1^(k1-1)*(p1-1)]*[p2^(k2-1)*(p2-1)]*...*[pr^(kr-1)*(pr-1)]

待证明

】

(三)  欧拉定理：

正整数a与n互质，则下式恒成立

a^ψ(n) ≡1(mod n)

Operation

The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption.

A basic principle behind RSA is the observation that it is practical to find three very large positive integers e, d and n such that with modular exponentiation for all integers m (with 0 ≤ m < n):

【m^(ed)%n=m

m^(ed-1)%n=1

m、n互质

根据欧拉定理

ed-1可以至少可以取n的欧拉数

】

and that even knowing e and n or even m it can be extremely difficult to find d.

In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies:

RSA involves a public key and a private key. The public key can be known by everyone, and it is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted in a reasonable amount of time by using the private key. The public key is represented by the integers n and e; and, the private key, by the integer d (although n is also used during the decryption process. Thus, it might be considered to be a part of the private key, too). m represents the message (previously prepared with a certain technique explained below).

Key generation

The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
   • For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder.^[2] Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
   • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
3. Compute λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1), where λ is Carmichael's totient function. This value is kept private.
4. Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime.
5. Determine d as d ≡ e⁻¹ (mod λ(n)); i.e., d is the modular multiplicative inverse of e modulo λ(n).

• This means: solve for d the equation d⋅e ≡ 1 (mod λ(n)).
• e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly e = 2¹⁶ + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.^[14]
• e is released as the public key exponent.
• d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the private (or decryption) exponent d, which must be kept secret. p, q, and λ(n) must also be kept secret because they can be used to calculate d.

In the original RSA paper,^[2] the Euler totient function φ(n) = (p − 1)(q − 1) is used instead of λ(n) for calculating the private exponent d. Since φ(n) is always divisible by λ(n) the algorithm works as well. That the Euler totient function can be used can also be seen as a consequence of the Lagrange's theorem applied to the multiplicative group of integers modulo pq. Thus any d satisfying d⋅e ≡ 1 (mod φ(n)) also satisfies d⋅e ≡ 1 (mod λ(n)). However, computing d modulo φ(n) will sometimes yield a result that is larger than necessary (i.e. d > λ(n)). Most of the implementations of RSA will accept exponents generated using either method (if they use the private exponent d at all, rather than using the optimized decryption method based on the Chinese remainder theorem described below), but some standards like FIPS 186-4 may require that d < λ(n). Any "oversized" private exponents not meeting that criterion may always be reduced modulo λ(n) to obtain a smaller equivalent exponent.

Since any common factors of (p − 1) and (q − 1) are present in the factorisation of n − 1 = pq − 1 = (p − 1)(q − 1) + (p − 1) + (q − 1),^[15] it is recommended that (p − 1) and (q − 1) have only very small common factors, if any besides the necessary 2.^[2][16][17]

Note: The authors of the original RSA paper carry out the key generation by choosing d and then computing e as the modular multiplicative inverse of d modulo φ(n). Since it is beneficial to use a small value for e (e.g., 65,537) in order to speed up the encryption function, current implementations of RSA, such as those following PKCS#1, choose e and compute d instead.^[2][18]

Key distribution

Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable, but not necessarily secret, route. Alice's private key (d) is never distributed.

Encryption

After Bob obtains Alice's public key, he can send a message M to Alice.

【将明文转化为一个整数，可能对明文做截断处理，生成多个正整数，分段加密 string msg--->int m

by using an agreed-upon reversible protocol known as a padding scheme  通过双方约定好的字符串转整数算法

】

To do it, he first turns M (strictly speaking, the un-padded plaintext) into an integer m (strictly speaking, the padded plaintext), such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c, using Alice's public key e, corresponding to

This can be done reasonably quickly, even for 500-bit numbers, using modular exponentiation. Bob then transmits c to Alice.

Decryption

Alice can recover m from c by using her private key exponent d by computing

Given m, she can recover the original message M by reversing the padding scheme.

【因为求私钥，即求eKEY+1能被(p-1)(q-1)的整除的KEY，而e、p*q已被公开，故求私钥等价于分解p*q】

【e 与 n的欧拉数互质，一定存在 e对于n的欧拉数的模范元素，此处不要求e次小于n的欧拉数，

即

e 与 (p-1)(q-1)互质，一定存在 e对于 (p-1)(q-1)的模反元素，此处不要求e次小于 (p-1)(q-1)，

记这个模反元素为d

即ed-1可以被(p-1)(q-1)整除，记商为ratio

则d=[(p-1)(q-1)*ratio+1]/e， 根据模反元素定义，ratio一定存在

(e*KEY-1)%[(p-1)(q-1)]=0

公钥(p-1)(q-1)，e

私钥(p-1)(q-1)，d

(r*X+1)%[(p-1)(q-1)]=0

】

【取2个不同的质数 p ，q（如果相同呢？），取小于p*q的质数r

根据欧拉定理

存在质数d使得e*d-1（或者d为r的欧拉数减少1次方）可以被p*q的欧拉数整除

即

存在质数d使得e*d-1可以被(p-1)(q-1)整除

】

【欧拉定理

Euler's theorem - Wikipedia https://en.wikipedia.org/wiki/Euler%27s_theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that if n and a are coprime positive integers, then

】

设正整数k, e*d = kψ(n)+1;

则ed-kψ(n)=1

d = (kψ(n)+1) / e;

对于不定方程ax+by=c，设gcd(a,b)=d，如果ax+by=c有解，则d|c----->也就是说如果ed-kψ(n)=1 有解,则gcd(d,-k)能够整除1,而1显然可以被任何整数整除,所以该二元一次方程必定有解(d,k)

(欧几里得定理和扩展欧几里得定理计算二元一次方程)

2)        将n和d封装成私钥

五、RSA算法可靠性论证

从上文可以统计出整个算法涉及到的量有6个，其中三个为由私钥持有者生成，三个是私钥持有者推导出来的

生成量：p,q,e

推导量：n, ψ(n),d

密钥中只有公钥被发布,所有人都可以获取。而公钥由n和e封装起来,因此,如果要破解一份RSA加密过的密文,我们必须使用私钥(私钥由n和d封装而成)

n可以从公钥获取。

(假设mc为明文，c为密文，则公钥由n和e封装则意味着求取密文的运算中，n，e和mc是已知数，只有c是未知数；私钥由n和d封装，同上，解密密文的运算中，n，d和c是已知的，只有mc是未知数。)

因此,破解私钥的关键就是破解e对于ψ(n)的模反元素d。

其数学关系是：  e*d=1(modψ(n));

因此需需要先求出ψ(n),而求出ψ(n)需要知道ψ(p)和ψ(q)(因为ψ(n)= ψ(p* ψ(q))

而p和q只能通过分解n的质因数获得。所以,整个RSA算法都基于n这个大数不能分解质因数这个基础上。

因此，只要n够大，私钥就不会被破解

六、加解密过程：假设明文是m,c是密文

(一)  加密：使用公钥(n,e)

先将其换算成asc码或者unicode等其他数值。且m必须小于n

则加密算法是

m^e=c(mod n)

推出

m^e / n = k ……c这里c就是密文，k我们不关心

(二)  解密：使用私钥(n,d)

1.        简单的说解密就是通过下式求m。(一定可以求解出m)

c^d = m(mod n)

推出
c^d / n = k … … m    m就是明文编码，不关心k

查表得出明文

JAVA的非对称加密算法RSA——加密和解密 - 牵着妞去散步 - 博客园 https://www.cnblogs.com/OnlyCT/p/6586856.html

下面简单总结加密和解密的完整过程。

l  签名过程：

1.        A提取消息m的消息摘要h(m),并使用自己的私钥对摘要h(m)进行加密,生成签名s

2.        A将签名s和消息m一起,使用B的公钥进行加密,生成密文c,发送给B。

l  验证过程：

1.        B接收到密文c,使用自己的私钥解密c得到明文m和数字签名s

2.        B使用A的公钥解密数字签名s解密得到H(m).

3.        B使用相同的方法提取消息m的消息摘要h(m)

4.        B比较两个消息摘要。相同则验证成功;不同则验证失败。

package com.joe.main;  

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;  

/**
 * @Description Demo说明：
 *              1、按照加密解密和签名验签的逻辑,编写简单的demo,不涉及java中继承的RSA相关类和Sigesture签名类
 *              2、只能对数字和字母进行加密, 不涉及编码和解码问题 。 3、不做数字签名和验证了,涉及到提取信息摘要。
 */
public class EnAndDe {
    private long p = 0;
    private long q = 0;
    private long n = 0;
    private long t = 0; // 欧拉函数  

    private long e = 0; // 公匙
    private long d = 0; // 密匙  

    private String mc; // 明文
    private long c = 0; // 密文
    private long word = 0; // 解密后明文  

    // 判断是一个数 x 否为素数素数就是判断在 (2,√x)范围内有没有除1外的因数,如果没有则x数素数
    public boolean isPrime(long t) {
        long k = 0;
        k = (long) Math.sqrt((double) t);
        for (int i = 2; i <= k; i++) {
            if ((t % i) == 0) {
                return false;
            }
        }
        return true;
    }  

    // 随机产生大素数(1e6数量级，注意，太大了要超出范围)
    public void bigprimeRandom() {
        do {
            p = (long) (Math.random() * 1000000);
        } while (!this.isPrime(p));
        do {
            q = (long) (Math.random() * 1000000);
        } while (p == q || !this.isPrime(q));
    }  

    // 输入PQ
    public void inputPQ() throws Exception {  

        this.bigprimeRandom();
        System.out.println("自动生成两个大素数p,q分别为:" + this.p + " " + this.q);  

        this.n = (long) p * q;
        this.t = (long) (p - 1) * (q - 1);  

        System.out.println("这两个素数的乘积为p*q：" + this.n);
        System.out.println("所得的t=(p-1)(q-1)：" + this.t);
    }  

    // 求最大公约数
    public long gcd(long a, long b) {
        long gcd;
        if (b == 0)
            gcd = a;
        else
            gcd = gcd(b, a % b);
        return gcd;  

    }  

    // 生成公匙
    public void getPublic_key() throws Exception {
        do {  

            this.e = (long) (Math.random() * 100000);
            // e满足 e∈(1, ψ(n))且e与ψ(n)最大公约数为1,即 e与t互质
        } while ((this.e >= this.t) || (this.gcd(this.t, this.e) != 1));
        System.out.println("生成的公钥为：" + "(" + this.n + "," + this.e + ")");
    }  

    // 生成私钥 e*d=1(modψ(n))==> d = (kψ(n)+1) / e
    public void getPrivate_key() {
        long value = 1; // value 是e和d的乘积
        outer: for (long k = 1;; k++) {
            value = k * this.t + 1;
            if ((value % this.e == 0)) {
                this.d = value / this.e;
                break outer;
            }
        }
        System.out.println("产生的一个私钥为：" + "(" + this.n + "," + this.d + ")");
    }  

    // 输入明文
    public void getText() throws Exception {
        System.out.println("请输入明文：");
        BufferedReader stdin = new BufferedReader(new InputStreamReader(
                System.in));
        mc = stdin.readLine();  

    }  

    // 解密密文
    public void pascolum() throws Exception {
        this.getText();
        System.out.println("输入明文为: " + this.mc);
        // 加密
        ArrayList cestr = new ArrayList();
        for (int i = 0; i < mc.length(); i++) {
            this.c = this.colum((long) mc.charAt(i), this.n, this.e);
            cestr.add(c);
        }
        System.out.println("加密后所得的密文为：" + cestr);
        // 解密
        StringBuffer destr = new StringBuffer();
        for (int j = 0; j < cestr.size(); j++) {
            this.word = this.colum(Long.parseLong(cestr.get(j).toString()),
                    this.n, this.d);
            destr.append((char) word);
        }
        System.out.println("解密后所得的明文为：" + destr);  

    }  

    // 加密、解密计算
    public long colum(long mc, long n, long key) {
        BigInteger bigy = new BigInteger(String.valueOf(mc));
        BigInteger bign = new BigInteger(String.valueOf(n));
        BigInteger bigkey = new BigInteger(String.valueOf(key));
        return Long.parseLong(bigy.modPow(bigkey, bign).toString());// 备注1
    }  

    public static void main(String[] args) {
        try {
            EnAndDe t = new EnAndDe();
            t.inputPQ();
            t.getPublic_key();
            t.getPrivate_key();
            t.pascolum();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }  

}  

备注1：modPow(a,b)是java类BigInteger中的一个方法，返回结果是：调用该方法的对象的a次幂,模b的结果

What a meaningless sense if losing myself,though owning all of the world.

 

自动生成两个大素数p,q分别为:192817 637309
这两个素数的乘积为p*q：122884009453
所得的t=(p-1)(q-1)：122883179328
生成的公钥为：(122884009453,56699)
产生的一个私钥为：(122884009453,84333590963)
请输入明文：
343i5435dsfs
输入明文为: 343i5435dsfs
加密后所得的密文为：[104962964505, 53575721421, 104962964505, 73241667689, 115165799367, 53575721421, 104962964505, 115165799367, 58398500538, 71277672989, 121734470069, 71277672989]
解密后所得的明文为：343i5435dsfs

方要我们自行生成一对公私钥后将其中的公/私钥指数和模数发给他们

php实现rsa签名和验签 - 云+社区 - 腾讯云 https://cloud.tencent.com/developer/article/1153658

这两天在弄某支付接口相关的东西,以前没做过这块,在签名和验签的过程中遇到了一些问题,记下来.

首先生成一个1024位的私钥:

openssl genrsa -out private.pem 1024

然后根据私钥导出公钥

openssl rsa -in private.pem -pubout -out public.pem

php的openssl扩展里已经封装好了签名和验签的方法,分别是openssl_sign和openssl_verify.

function sign($data){
    $p = openssl_pkey_get_private(file_get_contents('private.pem'));
    openssl_sign($data, $signature, $p);
    openssl_free_key($p);
    return bin2hex($signature);
}

function verify($data, $sign){
    $p = openssl_pkey_get_public(file_get_contents('public.pem'));
    $verify = openssl_verify($data, hex2bin($sign), $p);
    openssl_free_key($p);
    return $verify > 0;
}

实际情况是测试接口并没有提供公私钥,而是提供了公/私钥指数,模数.通过java的RSAPrivateKeySpec和RSAPublicKeySpec来实现签名和验签,遂写了一个jar用命令行来调用:

package org;

import java.math.BigInteger;
import java.security.KeyFactory;
import java.security.PrivateKey;
import java.security.Signature;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;

/**
 * @author eslizn
 *
 */
public class SignVerify {

     /**
     * @param args
     * @throws Exception
     */
     public static void main(String[] args) throws Exception {
         if(args.length == 4 && args[0].equals("sign")){
             System.out.println(Sign(args[1], new BigInteger(args[2], 16), new BigInteger(args[3], 16)));
             System.exit(0);
         }

         if(args.length == 5 && args[0].equals("verify")){
             System.out.println(Verify(args[1], args[2], new BigInteger(args[3], 16), new BigInteger(args[4], 16)) ? "1" : "0");
             System.exit(0);
         }
     }

     /**
     * Sign
     *
     * @param data
     * @param mod
     * @param exp
     * @return
     * @throws Exception
     */
     public static String Sign(String data, BigInteger mod, BigInteger exp) throws Exception{
         RSAPrivateKeySpec spec = new RSAPrivateKeySpec(mod, exp);
         KeyFactory keyFactory = KeyFactory.getInstance("RSA");
         PrivateKey signKey = keyFactory.generatePrivate(spec);
         Signature signature = Signature.getInstance("SHA1withRSA");
         signature.initSign(signKey);
         signature.update(data.getBytes());
         return byteArray2HexString(signature.sign());
     }

     /**
     * Verify
     *
     * @param data
     * @param sign
     * @param mod
     * @param exp
     * @return
     * @throws Exception
     */
     public static boolean Verify(String data, String sign, BigInteger mod, BigInteger exp) throws Exception{
         RSAPublicKeySpec spec = new RSAPublicKeySpec(mod, exp);
         KeyFactory keyFactory = KeyFactory.getInstance("RSA");
         java.security.PublicKey verifyKey = keyFactory.generatePublic(spec);
         Signature verifier = Signature.getInstance("SHA1withRSA");
         verifier.initVerify(verifyKey);
         verifier.update(data.getBytes());
         return verifier.verify(hexString2ByteArray(sign));
     }

     public static byte[] hexString2ByteArray(String hexStr){
         if (hexStr == null)
             return null;
         if (hexStr.length() % 2 != 0)
             return null;
         byte data[] = new byte[hexStr.length() / 2];
         for (int i = 0; i < hexStr.length() / 2; i++){
             char hc = hexStr.charAt(2 * i);
             char lc = hexStr.charAt(2 * i + 1);
             byte hb = hexChar2Byte(hc);
             byte lb = hexChar2Byte(lc);
             if (hb < 0 || lb < 0)
                 return null;
             int n = hb << 4;
             data[i] = (byte)(n + lb);
         }
        return data;
    }

    public static byte hexChar2Byte(char c){
        if (c >= '0' && c <= '9')
            return (byte)(c - 48);
        if (c >= 'a' && c <= 'f')
            return (byte)((c - 97) + 10);
        if (c >= 'A' && c <= 'F')
            return (byte)((c - 65) + 10);
        else
            return -1;
    }

    public static String byteArray2HexString(byte arr[]){
        StringBuilder sbd = new StringBuilder();
        byte arr$[] = arr;
        int len$ = arr$.length;
        for (int i$ = 0; i$ < len$; i$++){
        byte b = arr$[i$];
        String tmp = Integer.toHexString(0xff & b);
        if (tmp.length() < 2)
            tmp = (new StringBuilder()).append("0").append(tmp).toString();
            sbd.append(tmp);
        }
        return sbd.toString();
    }
}

巧合的是写完后通过沟通,对方要我们自行生成一对公私钥后将其中的公/私钥指数和模数发给他们.有的时候可能有的办法比技术实现更方便.附上取公/私钥指数和模数的代码:

function getPrivate($file){
    $p = openssl_pkey_get_private(file_get_contents($file));
    $res = openssl_pkey_get_details($p);
    var_dump($res);
    openssl_free_key($p);
    return array(
        'n' => bin2hex($res['rsa']['n']),#模数
        'e' => bin2hex($res['rsa']['e']),#公钥指数
        'd' => bin2hex($res['rsa']['d']),#私钥指数
    );
}

非对称加密算法-RSA算法 - The Last Song 的专栏 - CSDN博客 https://blog.csdn.net/kongqz/article/details/6302980

package com.neo.RSA;

import org.apache.commons.codec.binary.Base64;

import javax.crypto.Cipher;
import java.security.*;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.HashMap;
import java.util.Map;

/**
 * 非对称加密算法RSA算法组件
 * 非对称算法一般是用来传送对称加密算法的密钥来使用的，相对于DH算法，RSA算法只需要一方构造密钥，不需要
 * 大费周章的构造各自本地的密钥对了。DH算法只能算法非对称算法的底层实现。而RSA算法算法实现起来较为简单
 *
 * @author kongqz
 */
public class JavaRsa {
    //非对称密钥算法
    public static final String KEY_ALGORITHM = "RSA";
    /**
     * 密钥长度，DH算法的默认密钥长度是1024
     * 密钥长度必须是64的倍数，在512到65536位之间
     */
    private static final int KEY_SIZE = 512;
    //公钥
    private static final String PUBLIC_KEY = "RSAPublicKey";
    //私钥
    private static final String PRIVATE_KEY = "RSAPrivateKey";

    /**
     * 初始化密钥对
     *
     * @return Map 甲方密钥的Map
     */
    public static Map<String, Object> initKey() throws Exception {
        //实例化密钥生成器
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance(KEY_ALGORITHM);
        //初始化密钥生成器
        keyPairGenerator.initialize(KEY_SIZE);
        //生成密钥对
        KeyPair keyPair = keyPairGenerator.generateKeyPair();
        //甲方公钥
        RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();
        //甲方私钥
        RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();
        //将密钥存储在map中
        Map<String, Object> keyMap = new HashMap<String, Object>();
        System.out.println("keyMap:" + keyMap);
        keyMap.put(PUBLIC_KEY, publicKey);
        keyMap.put(PRIVATE_KEY, privateKey);
        System.out.println("keyMap:" + keyMap);
        return keyMap;
    }

    /**
     * 私钥加密
     *
     * @param data 待加密数据
     * @param key  密钥
     * @return byte[] 加密数据
     */
    public static byte[] encryptByPrivateKey(byte[] data, byte[] key) throws Exception {
        //取得私钥
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(key);
        System.out.println("pkcs8KeySpec:" + pkcs8KeySpec);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        //生成私钥
        PrivateKey privateKey = keyFactory.generatePrivate(pkcs8KeySpec);
        System.out.println("privateKey:" + privateKey);

        //数据加密
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        System.out.println("cipher:" + cipher);

        cipher.init(Cipher.ENCRYPT_MODE, privateKey);
        System.out.println("cipher.doFinal(data):" + cipher.doFinal(data));
        return cipher.doFinal(data);
    }

    /**
     * 公钥加密
     *
     * @param data 待加密数据
     * @param key  密钥
     * @return byte[] 加密数据
     */
    public static byte[] encryptByPublicKey(byte[] data, byte[] key) throws Exception {

        //实例化密钥工厂
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        //初始化公钥
        //密钥材料转换
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(key);
        System.out.println("x509KeySpec:" + x509KeySpec);
        //产生公钥
        PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);
        System.out.println("pubKey:" + pubKey);
        //数据加密
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        System.out.println("cipher:" + cipher);
        cipher.init(Cipher.ENCRYPT_MODE, pubKey);
        System.out.println("cipher.init(Cipher.ENCRYPT_MODE, pubKey):" + cipher.doFinal(data));
        return cipher.doFinal(data);
    }

    /**
     * 私钥解密
     *
     * @param data 待解密数据
     * @param key  密钥
     * @return byte[] 解密数据
     */
    public static byte[] decryptByPrivateKey(byte[] data, byte[] key) throws Exception {
        //取得私钥
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        //生成私钥
        PrivateKey privateKey = keyFactory.generatePrivate(pkcs8KeySpec);
        System.out.println("decryptByPrivateKey-privateKey:" + privateKey);

        //数据解密
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        System.out.println("decryptByPrivateKey-cipher.doFinal(data):" + cipher.doFinal(data));
        return cipher.doFinal(data);
    }

    /**
     * 公钥解密
     *
     * @param data 待解密数据
     * @param key  密钥
     * @return byte[] 解密数据
     */
    public static byte[] decryptByPublicKey(byte[] data, byte[] key) throws Exception {

        //实例化密钥工厂
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        //初始化公钥
        //密钥材料转换
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(key);
        //产生公钥
        PublicKey pubKey = keyFactory.generatePublic(x509KeySpec);
        //数据解密
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, pubKey);
        return cipher.doFinal(data);
    }

    /**
     * 取得私钥
     *
     * @param keyMap 密钥map
     * @return byte[] 私钥
     */
    public static byte[] getPrivateKey(Map<String, Object> keyMap) {
        Key key = (Key) keyMap.get(PRIVATE_KEY);
        return key.getEncoded();
    }

    /**
     * 取得公钥
     *
     * @param keyMap 密钥map
     * @return byte[] 公钥
     */
    public static byte[] getPublicKey(Map<String, Object> keyMap) throws Exception {
        Key key = (Key) keyMap.get(PUBLIC_KEY);
        return key.getEncoded();
    }

    /**
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        //初始化密钥
        //生成密钥对
        Map<String, Object> keyMap = JavaRsa.initKey();
        //公钥
        byte[] publicKey = JavaRsa.getPublicKey(keyMap);

        //私钥
        byte[] privateKey = JavaRsa.getPrivateKey(keyMap);
        System.out.println("公钥：\n"+Base64.encodeBase64String(publicKey));
        System.out.println("私钥：\n" + Base64.encodeBase64String(privateKey));

        System.out.println("================密钥对构造完毕,甲方将公钥公布给乙方，开始进行加密数据的传输=============");
        String str = "RSA密码交换算法";
        System.out.println("\n===========甲方向乙方发送加密数据==============");
        System.out.println("原文:" + str);
        //甲方进行数据的加密
        byte[] code1 = JavaRsa.encryptByPrivateKey(str.getBytes(), privateKey);
        System.out.println("加密后的数据：" + Base64.encodeBase64String(code1));
        System.out.println("===========乙方使用甲方提供的公钥对数据进行解密==============");
        //乙方进行数据的解密
        byte[] decode1 = JavaRsa.decryptByPublicKey(code1, publicKey);
        System.out.println("乙方解密后的数据：" + new String(decode1) + "\n\n");

        System.out.println("===========反向进行操作，乙方向甲方发送数据==============\n\n");

        str = "乙方向甲方发送数据RSA算法";

        System.out.println("原文:" + str);

        //乙方使用公钥对数据进行加密
        byte[] code2 = JavaRsa.encryptByPublicKey(str.getBytes(), publicKey);
        System.out.println("===========乙方使用公钥对数据进行加密==============");
        System.out.println("加密后的数据：" + Base64.encodeBase64String(code2));

        System.out.println("=============乙方将数据传送给甲方======================");
        System.out.println("===========甲方使用私钥对数据进行解密==============");

        //甲方使用私钥对数据进行解密
        byte[] decode2 = JavaRsa.decryptByPrivateKey(code2, privateKey);

        System.out.println("甲方解密后的数据：" + new String(decode2));
    }
}

　　

keyMap:{}
keyMap:{RSAPublicKey=Sun RSA public key, 512 bits
  modulus: 9240044710867494912585831069170888399022790165196118946275326140848554643574034384515939267781952577892601470596983513190437403733818259515255163304444331
  public exponent: 65537, RSAPrivateKey=sun.security.rsa.RSAPrivateCrtKeyImpl@40a9f}
公钥：
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALBsZdJMV7owsqz9hXcQ5Bzlvu9l8UX1BMBhSuUzxx3Ri9B+6cjbMXa7//hkzvHXbbysi2qUkLmFQR1y/XvegasCAwEAAQ==
私钥：
MIIBVAIBADANBgkqhkiG9w0BAQEFAASCAT4wggE6AgEAAkEAsGxl0kxXujCyrP2FdxDkHOW+72XxRfUEwGFK5TPHHdGL0H7pyNsxdrv/+GTO8ddtvKyLapSQuYVBHXL9e96BqwIDAQABAkEAruI1KPsed2XwqIUDeVzYE0E3PU67lhJlLGMFgCEMf6PfLnzc5oPMFsMZpvx6d5OnUSDJdz90dkGpOocfi/CWKQIhAPjmkQ49v8wDassy/OZ52wnMWPIlS3mKRkVde6CkCnEXAiEAtXSdJSDbts43xJ4qQH5ER2PeNNY8ele0GX0b4zyGiI0CIA2pMfrzHqzG3zyp3sGTnJcMFTGtJFhWY4b5G4j0l/IfAiAqLHBZsMlgM43CpQAs/Svha9S5cxGbXcb+JZXVuruKAQIgJpEedrg+u1J/OHsrQCF1vogDUuwJBfXHf+9CryR6Ems=
================密钥对构造完毕,甲方将公钥公布给乙方，开始进行加密数据的传输=============

===========甲方向乙方发送加密数据==============
原文:RSA密码交换算法
pkcs8KeySpec:java.security.spec.PKCS8EncodedKeySpec@42110406
privateKey:sun.security.rsa.RSAPrivateCrtKeyImpl@40a9f
cipher:javax.crypto.Cipher@366e2eef
cipher.doFinal(data):[B@35fb3008
加密后的数据：Ys5HQsCNZEJVyZk6rhIaQ23Za8UYwWk4pHbpsruAD5dBBUygXrPfvylIOXRStuznS5c4jR1qm4RIepR1za5wcQ==
===========乙方使用甲方提供的公钥对数据进行解密==============
乙方解密后的数据：RSA密码交换算法

===========反向进行操作，乙方向甲方发送数据==============

原文:乙方向甲方发送数据RSA算法
x509KeySpec:java.security.spec.X509EncodedKeySpec@7225790e
pubKey:Sun RSA public key, 512 bits
  modulus: 9240044710867494912585831069170888399022790165196118946275326140848554643574034384515939267781952577892601470596983513190437403733818259515255163304444331
  public exponent: 65537
cipher:javax.crypto.Cipher@54a097cc
cipher.init(Cipher.ENCRYPT_MODE, pubKey):[B@36f6e879
===========乙方使用公钥对数据进行加密==============
加密后的数据：O6cqf/XRiRkWSbVfXm5gRnJFOMDnnLZ8zSKTl/A9H+LVtFa7h3+/GLndRTCpTB4unNfToLKkQOWcYUP3S13G4w==
=============乙方将数据传送给甲方======================
===========甲方使用私钥对数据进行解密==============
decryptByPrivateKey-privateKey:sun.security.rsa.RSAPrivateCrtKeyImpl@40a9f
decryptByPrivateKey-cipher.doFinal(data):[B@5a61f5df
甲方解密后的数据：乙方向甲方发送数据RSA算法

　注意：

　

keyMap:{RSAPublicKey=Sun RSA public key, 512 bits
modulus: 9240044710867494912585831069170888399022790165196118946275326140848554643574034384515939267781952577892601470596983513190437403733818259515255163304444331
public exponent: 65537, RSAPrivateKey=sun.security.rsa.RSAPrivateCrtKeyImpl@40a9f}