非对称加密机制

image.png

只有Bob 持有私钥，而且只有Bob 才能解密，Alice也不行

伪代码

key_pair->{Kpub,Kpri}

Y=E(Kpub,X);
X=D(Kpri,Y);

密钥对 key_pair

加密：输入公钥Kpub、明文X 产生 密文 Y
解密：输入私钥Kpri,密文Y 产生 明文X

一般要求

image.png

安全要求

image.png

详解RSA加密过程

RSA加解密算介绍

1、1977年MIT 的 Rivest-Shamir-Adleman 三位提出的，并以他们的首字母命名。
2、一直沿用至今，成为被广泛接受且被实现的通用公钥加密算法

RSA以整数域的指数运算、模运算为主，以分组为单位进行加密

C=P^e mod n
P=C^d mod n

其中，值{e,n} 组成公钥，值{d,n} 组成私钥

P代表明文，C代表密文 ，
加密过程：对明文P 计算e次方，然后对n 求模，余数就是密文；
解密过程：对密文C 求d次方，然后对n 求模，然后余数就是明文

RSA 加解密- 小数演示

例如选择下面的几个数
e=7 , d=23,n=187

加密过程
c(m=88)=m^e mod n=88^7 mod 187=11

解密过程
m(c=11)=c^d mod n=11^23 mod 187=88

m 为明文88 ； 11就是加密的结果 也就是 密文；

image.png image.png image.png

欧拉定理（费马欧拉定理）

image.png

反过来求 p 和 q 很难

image.png

目前只有1,5 两个与6互质， 也可以通过 计算出 Q(6)=(2-1)*(3-2)=2个

image.png

(x^e)d (mod n)=x^(tQ(n)+1) mod n=((x^Q(n))t)*x mod n= (1^t) *x

(2²⁾2=2^(2*2)=24=16

因为x^Q(n) mod n---1

RSA算法实现

image.png

1000位 或者更大位

实践生产中 使用的是快速模幂算法

java 中提供了 modPow

快速幂取模的modPow方法

image.png

BigInteger p,e,n;
//c=p^e mod n
BigInteger c=p.modPow(e,n);

密钥生成的宏观描述

RSA算法中涉及的数{n,p,q,e,d} 来自密钥生成

image.png

选择2个大质数

image.png

目前还没有好的方法验证是不是质数
根据数论的知识，平均每个Logn 就会有一个质数
排除掉偶数之后，大概有 logn 二分之一 这么多次
比如我们要招 2^1024 之前的质数， 那么要尝试 log2^1024 除以 2 大概要360次的尝试
找两次 找 到 p 和 q 两个大的质数

RSA示例演示

image.png

欧拉定理 :
Q(n)=(p-1)(q-1)=160
Q(187)=(17-1)(11-1)=1610=160

image.png

实际上，通常直接选择e=65537=2^16+1

gcd 就是 求最大公约数的方法
通常是 e=65537 = 2^16+1

确定d

image.png image.png

因为 fai n 和 e 是互质，所以gcd(fai n ,e) 也等于1

image.png

fai n 、e 已知量

t、d 看做未知量

必等式，一定存在整数 x ,y 使得

ax+by=gcd(a,b)

已知a,b 对他们进行辗转相除 可以得到他们的最大公约数

在欧几里得里面只用到了 余数

在扩展欧几里得算法，还利用了代余除法得到的商

在辗转相除的时候就能得到必等式的x,y

扩展欧几里得算法可以得到模板元素

求出模板元素是RSA 加密运算中 产生公私钥必须的步骤

有关扩展欧几里得具体实现 可以参考 提供的详细资料

image.png

扩展欧几里得算法 ext_gcd可以直接求出 t、d 的值

t 可以忽略 我们不需要，d的值是我们想要的

ext_gcd演算 扩展欧几里得算法演算

image.png image.png image.png

第一行是被除数
第二行是除数
第一行的 ri 的 160 就是 Q(n)
第二行 e 就是 ri 的 7

第一行 第二行的 t 和d 分别写做 1 0 ， 0 1 因为还没有开始计算

第一行被除数的系数 t 就是 1
第二行 除数的系统d 就是 1

第一次计算

image.png image.png

为什么6 要写在除数里面呢，因为这是欧几里得的辗转相除法，上一步的余数就是下一步的除数，交换辗转相除

160%7=22 余数6

t 的计算方法

x[i]=x[i-2]-q[i]*x[i-1]

当前值=倒数两个的值- qi倒数一个的值
1=1-220=1
t[i]=t[i-2]-q[i]t[i-1]=1-220=1

第三行 qi=22 t[i-1]=0 t[i-2]=1

d 的计算方法

x[i]=x[i-2]-q[i]*x[i-1]

当前值=倒数两个的值- qi倒数一个的值
1=0-221=-22
d[i]=d[i-2]-q[i]d[i-1]=0-221=-22

第三行 qi=22 d[i-1]=1 t[i-2]=0

第二次计算

image.png

r[i-1]%r[i]

7%6=1 余数 1

第二次t 的计算方法

q[i]=q[2]=1

x[i]=x[i-2]-q[i]*x[i-1]

当前值=倒数两个的值- qi倒数一个的值
-1=0-11=-1
t[i]=t[i-2]-q[i]t[i-1]=0-11=-1

第四行也就是q[2], q[i]=1 t[i-1]=1 t[i-2]=0

第二次d 的计算方法

q[i]=q[2]=1
x[i]=x[i-2]-q[i]*x[i-1]

当前值=倒数两个的值- qi倒数一个的值
23=1-1(-22)=23
d[i]=d[i-2]-q[i]d[i-1]=1-1(-22)=23

第四行 qi=1 d[i-1]=-22 t[i-2]=0

结果

image.png

验证一下

image.png

实际生成中

image.png image.png

modInverse(模反计算)

image.png

e就是 7 phi 是 160 7.modInverse(160)

计算结果表格

image.png

公钥加密

image.png

m=88 n=187 m 是消息正文

私钥解密

image.png

c=11 n=187

RSA安全性浅析

1、逆计算不可行
基于详细 x^e(mod n) 是单向函数

2、破解密钥很困难
已知公钥{n,e}求{d} 只能试图分解n=pq难度巨大

如果是n 是2千位的大数，一般认为是几百年的时间是不够的

image.png

这里是一个 168位的数字，谁能看出来他是谁和谁的乘积？

image.png

实际中 比这个数还要大很多很多

RSA安全性

RSA生产使用的安全建议：
1、在一般的场合下，使用1024位及以上的密钥
2、在高级别安全场景下，使用2048位及以上的密钥