非对称加密算法之RSA算法实现

对称加密，非对称加密，公钥，私钥，RSA这些常常听到的，到底是怎么回事

有个同事问我公钥私钥到底为什么能互相解开，一时语塞，平时都只是知道怎么用，但很少去了解的更细，现在做个整理，记个笔记

非对称加密简述

公钥加密后的密文，只有私钥才能解密

简单来说，A和B要互相通信，A生成一个公钥和一个私钥，

A将公钥传给B，

此时B将公钥和真正的数据M加密，生成密文是N，

B再将N通过网络传给A，

A再通过秘钥将N解密，得到真正的数据M

公钥私钥原理（特指RSA算法）

网上抄的，但要理解

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

算法描述：(1)选择两个不同的大素数p和q；// p=3,q=11(2)计算乘积n=pq和Φ(n)=(p-1)(q-1)；//n=33,Φ(n)=20(3)选择大于1小于Φ(n)的随机整数e，使得gcd(e,Φ(n))=1；//gcd即最大公约数。//e和Φ(n)的最大公约数为1，也就是e只要不被Φ(n)整除就行，假如取e=3(4)计算d使得d*e=1mod Φ(n)；注：即d*e mod Φ(n) =1。//mod是求余函数//d*e与1关于Φ(n)同余,1除以20余数是1,那么说明d*3除以20,余数也是1//即3d=20k+1,k是整数,可取得d=7(5)对每一个密钥k=(n,p,q,d,e)，定义加密变换为Ek(x)=xe mod n，解密变换为Dk(x)=yd mod n，这里x,y∈Zn；(6)p,q销毁，以{e,n}为公开密钥，{d,n}为私有密钥。实例：1. 假设p = 3、q = 11（p，q都是素数即可。），则N = pq = 33；2. r =Φ(n)= (p-1)(q-1) = (3-1)(11-1) = 20；3. 根据gcd(e,Φ(n))=1，即gcd(e,20)=1，令e=3，则，d = 7。（两个数交换一下也可以。）到这里，公钥和密钥已经确定。公钥为(N, e) = (33, 3)，密钥为(N, d) = (33, 7)。

扩展:

1.RSA详解

2.RSA算法原理一

3.RSA算法原理二

java代码简约版实现：

package com.rsa;/*** Created by zhangshuai on /7/31.*/public class RsaTest {/*** RSA算法* @param baseNum 基数* @param key 公钥或密钥* @param message 加密或者解密的数据* @return*/public static long rsa(int baseNum, int key, long message){if(baseNum < 1 || key < 1){return 0L;}//加密或者解密之后的数据long rsaMessage = 0L;double pow = Math.pow(message, key);System.out.println("pow="+pow);long round = Math.round(pow);System.out.println("roud="+round);//核心算法rsaMessage = Math.round(Math.pow(message, key)) % baseNum;return rsaMessage;}public static void main(String[] args){//基数int baseNum = 3 * 11;//公钥int keyPublic = 3;//密钥int keyPrivate = 7;//未加密的数据long msg = 24L;//获得公钥加密后的数据long encodeMsg = rsa(baseNum, keyPublic, msg);//获得私钥解密后的数据long decodeMsg = rsa(baseNum, keyPrivate, encodeMsg);System.out.println("加密前：" + msg);System.out.println("加密后：" + encodeMsg);System.out.println("解密后：" + decodeMsg);}}

结果：

pow=13824.0roud=13824pow=2.187E10roud=21870000000加密前：24加密后：30解密后：24