非对称加密之RSA算法
有个胖子他姓杨
发表于 2022-12-6 20:25:48
193
0
0
1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
具体是利用了：' o' n5 `4 i6 K- j
, L8 u/ }! g3 O; F
1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。* G# @. Q6 b# e" y% y8 @7 T2 k8 }
2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。
. N, R+ H7 Q- @- d
原理
( r; { S8 \' I0 A3 l' |6 P H% C
RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。; a f$ d! q( Z" ^6 U1 a5 e
) C, m! R7 w+ o* M; k% K
公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。7 }% B7 Y! g$ F1 i- a
: C* ]( K6 c v' w2 I
加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。
9 s/ ^0 U/ K+ ~% D# m- d, z
解密过程：(c^d)modn=m，其中d为解密密钥。
5 F, F- g$ p/ U; v
解密密钥d的求解：
2 W8 J+ x* d3 C, ^6 ~) O* s2 h
(c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
费马定理：) G, c+ |! ~ M( h, i
若p是素数，a与p互素，则a^(p-1）≡1（modp）
0 S0 S/ M' ]7 M4 C0 U3 R- q- b
举例& C/ U j0 H2 [5 a% H; P( Z; a, F
) T: H6 t3 p& `- D
加密过程举例（1）：
) Q8 q9 e/ @' X0 E3 J4 r+ M
1.挑选两个质数，如p=61和q=53
) K+ w6 v* D) ]9 y6 h* ^
2.计算N=p*q=3233
3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】+ g4 |; L" j2 u2 X# E% g7 W" X. {
0 k9 p+ R' K; E& W$ y
4.选择与3120互质的一个数e=17
8 t4 ~3 b5 V( ~% U+ j
5.计算得出d，使得d是e关于3120的模逆，得出d=2753; \* C1 u3 I: N' f- U
6.如果明文是5，那么密文是5^17(mod3233)=3086
7.解密，3086^2753(mod3233)=5: F- T# l* Y4 Q3 j. T# G. o$ P7 f
关于模逆：先用“辗转相除法”…
/ b3 F1 T: @6 A3 Y3 Z
加密过程举例（2）-中间人：
7 \9 G4 Z( u' g7 O4 E
A：有一个公钥n、e。例如：3127、3。7 W0 f. S$ Z- m6 Y$ Z
0 N4 h5 T0 f; H7 W/ ?
B：有一个信息m。例如：89。
+ C9 {6 j" ]* p: u8 l9 d5 \- j5 [9 |4 S& z
C：偷听者
A：
第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。
第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。* u/ s A' [+ x
0 J& x' R% k: j0 v4 {
例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。! q0 ~4 S$ P# j) ^. ^' R5 A
+ o* u0 Z+ ?6 T
C：获得n、e
4 N- n" h: s* o' `
B：! k# N* e) {/ y6 O
第一步：获得n、e
第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。
第三步：发送c给A
& b- Q( W, x X- J
C：
第一步：截获加密信息c
第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。
A：: V; @ Q$ w5 r7 e& S
第一步：收到加密信息c& n7 C _6 \. W' _7 t+ @' a
) T5 j" y+ @! N. ^2 y5 b
第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。, j% `8 g" m4 s5 \& {
完成
安全性/ z2 |8 u* {: W+ t
7 G2 @8 F* Q+ x
为什么RSA是不会被破解的呢？
为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。
1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：. ]1 f0 {( C* ]
g; p2 T( E& H
读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。2 ?/ Z1 O6 }' u+ R
到目前为止，关于RSA可靠性的描述：
6 n; Q5 `4 R1 D! h% S/ Z! z, J
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。6 }( j: x* s% H9 I5 W' @
& W( Q' `8 z. H9 n0 m" y7 g
假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。: w/ L- |) ^( s: l( g
$ Y& ?# E: g* w( U, h
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
RSA的正确性：
可以使用欧拉函数和欧拉定理来证明。- w4 ]: M1 K- k6 F9 [3 ]$ J: C; K
（这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）$ d5 p+ v+ }& y; V$ p2 W
4 v$ f; f2 `; R6 r5 {, P; N8 D, f
如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m
那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？
应用" @7 X2 Z# G, w7 }. ~, r
) V, {! u! U5 v1 }/ e; s9 M
RSA的应用：数字签名
) t" i: S3 I; @3 w0 a
最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。
* r. f2 N* |) P5 u0 b
验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。* Z4 [& ]9 C6 w* F! Q* C
如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
成为第一个吐槽的人
