非对称加密之RSA算法
有个胖子他姓杨
发表于 2022-12-6 20:25:48
109
0
0
) v2 q% f7 J* h% B4 x4 w0 G! n
1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。
具体是利用了:$ O5 ]* Q1 A" T7 t1 J' O/ g
% {8 ~6 ]$ @. _2 ~/ [
1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。
2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。2 @* C3 D% {0 N K4 n3 V9 m
原理
RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。
7 ? h; s6 N5 _& H; W7 J; e! U
公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。
加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。" V. v' N# U6 q6 {/ b* `) c2 G; `
解密过程:(c^d)modn=m,其中d为解密密钥。
. @' C- Q8 a( c) i( U/ B" m1 y
解密密钥d的求解:9 b1 O- v1 N- w& j4 M& t
* Y+ _8 \) j% z% v# A" f2 ~+ j. a
(c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
费马定理:, d! D# D. `* x% U- G. i0 Z
7 _0 U! m+ A0 i
若p是素数,a与p互素,则a^(p-1)≡1(modp)
2 N& [* ?( @; U/ q% M
举例
+ l1 \# C3 e0 u9 r' D' ?$ N
加密过程举例(1):; q7 h+ P; M( W1 X4 V ?( N' K7 U: u
. y$ r( O' L+ }" u( Z
1.挑选两个质数,如p=61和q=532 i8 R$ F' k3 V3 D9 l! i
/ I- s" c1 o4 d( W( K
2.计算N=p*q=3233
- y2 A+ l" l+ F4 X, c8 \
3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】
, ?+ o& T! N8 e0 [; p
4.选择与3120互质的一个数e=17: v, H% \& p' G5 y) }5 V4 ~
3 s9 P) X2 l4 c/ s4 f: g
5.计算得出d,使得d是e关于3120的模逆,得出d=2753
6.如果明文是5,那么密文是5^17(mod3233)=3086
7.解密,3086^2753(mod3233)=5
& g2 P- h0 e. m- }7 C
关于模逆:先用“辗转相除法”…
加密过程举例(2)-中间人:" ~: d4 ]8 o- D
' _! N2 z. w( a1 _, x" p
A:有一个公钥n、e。例如:3127、3。
B:有一个信息m。例如:89。% H4 L- i4 s& y: [9 ^9 Y9 k% d
9 t! `% [ P9 O
C:偷听者
A:# N" M- M) w9 S2 K# d
第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。
$ |0 w7 U5 u9 R7 q8 [# B3 [
第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。% ]! l, l: _! I7 @. {+ w
例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。, D6 m: ?9 X: \( y( S$ a# e
; L+ r, k& s2 |& R5 n
第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。
C:获得n、e
B:
2 q! j) C' [8 T2 ~) {
第一步:获得n、e( _0 z& s5 [- h/ i- j5 ]
) f0 x# `1 m0 _4 B4 j
第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。
第三步:发送c给A
C:3 N: O9 ]/ B3 Q, ^, b* s# d9 i
R7 b, Q5 A1 \" O
第一步:截获加密信息c
* L; W: Y; ^8 M1 Z7 b
第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。
2 y% }3 w+ F0 I- y" X: K$ H' P
A:
第一步:收到加密信息c$ e% X* W$ ~ Q+ S/ f9 W0 s
第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。
* R. [5 L P; O1 h% l
完成
安全性
* B: n6 q1 q0 w" G; v7 Y" i
为什么RSA是不会被破解的呢?& j5 i/ N1 B: b$ V5 ]
为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。
1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:: @' k# [7 \8 Z0 C* Z
' y: h( u9 F9 L0 w2 K0 a4 v
读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。! t+ d$ h! L% v5 E7 T
3 M ]/ i( H. A8 R9 G; J
书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。
/ [& c: o( c: c( @6 c) E
到目前为止,关于RSA可靠性的描述:7 O5 L5 b/ V3 B9 J; i H% {* y
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
; z' y& n) G' g$ w' I
假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。. [ k2 F+ j+ W( a2 h" i5 s
只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。
0 I% W' \& [6 F/ h) R3 \
RSA的正确性:
可以使用欧拉函数和欧拉定理来证明。* s& w$ c: }; b( ?
; _* {: b" N/ [) h) S( w
(这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)& f! H; ^2 t0 W3 u; ^, {
如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m
那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?8 z' t' I" X, d5 _2 a$ F$ J% P
应用
RSA的应用:数字签名- i8 U `7 m) K! m1 z% d- C
$ [8 ? f \5 o) F
最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。# ~# | Y2 X, q- n- p
6 \. I- q5 z9 I/ b
验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。 t; f% y% z& [0 ^) W
9 t& _5 P' }& Z `* ~9 \; l
如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
成为第一个吐槽的人