非对称加密之RSA算法
有个胖子他姓杨
发表于 2022-12-6 20:25:48
78
0
0
1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。, X; K8 U, N) `* B, M1 p( g
; D9 X+ l" d! D0 t3 `8 |
具体是利用了:
1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。
4 ^7 W+ T5 V/ ]+ X: l) X. a
2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。6 U( b8 x r4 G; r' N0 {
原理
RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。
X/ z# a# h4 ]9 }- Y+ _4 v
公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。* U( }& S+ C" y8 E3 C% {
& g" u { ?. c: b0 L6 ~
加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。% R7 ?2 E, F" d+ \$ K! \9 w
解密过程:(c^d)modn=m,其中d为解密密钥。" P$ N3 \2 b" y2 G- g! k% w
解密密钥d的求解:8 w& r! m( W6 \6 I6 r! r( P8 F
7 H1 m, J; a2 b" c3 J
(c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn) }6 ~3 V0 a- M8 C2 T: J
- r7 B# b7 Q J$ U" Q# U* I
费马定理:0 ~8 I1 F) V1 Z; [
若p是素数,a与p互素,则a^(p-1)≡1(modp)
; a% h- `6 W9 _9 z; Q; k8 C
举例
加密过程举例(1):
1.挑选两个质数,如p=61和q=538 K g/ y n; a) Z
2.计算N=p*q=32335 {( v( |$ O9 [2 q
3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】
4.选择与3120互质的一个数e=17
5.计算得出d,使得d是e关于3120的模逆,得出d=2753# ]) D, D1 _' e, g4 m
4 d5 s% p; V/ S
6.如果明文是5,那么密文是5^17(mod3233)=30869 ]8 i+ Z- B5 y- Y e: S/ _, g
7.解密,3086^2753(mod3233)=5& C, T# V# v9 G
关于模逆:先用“辗转相除法”…
2 g! K+ W5 |* O, Z' j3 ?) _
加密过程举例(2)-中间人:% w: k4 `' F( r
A:有一个公钥n、e。例如:3127、3。0 K& e7 @' ~9 c; `: b
' c) _9 i9 E& Q6 T6 ^$ V0 v& ^
B:有一个信息m。例如:89。: v5 L: Y. ^0 |
; Y! l7 b C M) z k+ \. S' `, J9 a
C:偷听者% [9 R& F3 k p
" ~ V) Q2 B' Q. Z
A:8 Q }- n$ ?2 y
+ G3 l! e2 i8 F, L, P9 d" |
第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。7 j/ r1 |9 u8 s1 S/ x
第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。' D( V& O# W0 ~2 H ?+ G3 b) a
例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。% L+ Z, I; U7 [3 q
- b( ^" O4 e% w ^2 T4 j* [5 c
第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。
C:获得n、e
B:
第一步:获得n、e
第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。
第三步:发送c给A B% D3 i: V0 ~0 h
Z2 ^! S% ?1 V( s4 J( K: o
C:
5 B% z' v1 L: q, H8 A5 v
第一步:截获加密信息c6 D) @9 ]& O/ D
第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。0 Y4 u |- ^4 ^( o& @! c9 l' T1 g
. G L3 Y" W/ ?. W# Y3 ]& q3 v
A:' Z$ l+ r3 y# w$ B1 V
# H9 i1 }" e3 A! N
第一步:收到加密信息c
第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。
完成
7 e, e, Q! X5 o8 D- f! ?$ H
安全性: L/ ?9 b( W) l6 [8 a
为什么RSA是不会被破解的呢?7 u; P; j% d6 z. G
为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。: B+ N2 c ]2 o- `' g( L7 g
! m- E% x* Q. [- N
1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:& x7 x2 O6 n; Q p& \1 S' }, ~
读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。
书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。
. v/ e, l6 G k% M/ \5 K+ s
到目前为止,关于RSA可靠性的描述:. N* P: C: s% u8 X
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
# `9 a! p- W7 n: d- r/ X
假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。$ B; g7 o- K5 u) S, L t" [9 r7 X
只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。
RSA的正确性:
可以使用欧拉函数和欧拉定理来证明。3 o: j; r: X5 O: y! z0 t
" r% P7 I" z- J
(这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)0 o; A+ {- _# K
" i- X! _- r4 Q0 T0 T1 A: S' W6 c
如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m7 A, \ j: u% B2 v9 c
那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?$ j$ E, B" H) B8 E& H
- f- N7 L0 f, u+ t7 M
应用
RSA的应用:数字签名
6 C8 z! o- K) J8 K% Z
最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。" H, I5 u; v0 ^/ U
$ j8 } f* a$ Y& y
验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。
如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
成为第一个吐槽的人