非对称加密之RSA算法
有个胖子他姓杨
发表于 2022-12-6 20:25:48
107
0
0
1 ~* ]# `) |0 ]9 X% r
1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。
2 y) C( V( u1 F: @, a$ F2 O* o
具体是利用了:
8 c5 Q$ S3 Q( Z# L
1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。
2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。8 S8 T' D& L4 M8 e
( {6 O! k+ i Z) J! Y; H
原理
RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。5 ? k2 O; f" _7 N. w( S1 k: o
; D6 e8 f6 f/ N1 ?/ B3 W
公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。" @2 R% ]1 \8 L3 n8 V% J
加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。" s. w# d! @2 V/ R
解密过程:(c^d)modn=m,其中d为解密密钥。
解密密钥d的求解:
(c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn; U/ w; t7 e" H# E5 R0 E
+ ~7 ?5 u/ R1 T
费马定理:) f3 t9 h7 q' p# Z& K. L( Y ?4 m% f5 ?
若p是素数,a与p互素,则a^(p-1)≡1(modp)- a& D. B9 W& T
举例
* v( G+ G" x g9 V+ Z d; w
加密过程举例(1):8 Q3 }/ t' \+ i% d! [
1.挑选两个质数,如p=61和q=532 X9 Z p X1 f9 S& f3 v
2.计算N=p*q=3233
+ F1 u- F9 V0 @! h! ]6 d" B
3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】
4.选择与3120互质的一个数e=17, ]( R7 T5 e" s4 D
4 z6 k0 w& d( x0 {1 F, H
5.计算得出d,使得d是e关于3120的模逆,得出d=27531 k9 N" n8 N9 I5 I
$ B6 ^4 C4 m1 {
6.如果明文是5,那么密文是5^17(mod3233)=30866 R' h5 u: S$ B
8 n% O2 T2 e# r3 U% T8 |5 [
7.解密,3086^2753(mod3233)=5( Q- T! s7 T9 s
4 o& k! g/ I4 L# i4 O5 j
关于模逆:先用“辗转相除法”…* u% O0 e1 V2 ^3 U$ ?: {- s3 w- h6 h
加密过程举例(2)-中间人:6 ?! e( e- t6 s' _$ e
9 u* z8 k# x' c; N: S' V! t; F
A:有一个公钥n、e。例如:3127、3。
: M5 S% l, u9 ]! P+ I0 h
B:有一个信息m。例如:89。
C:偷听者
A:
; Y/ s. a3 T6 A
第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。
5 q5 a- N, S7 F7 C$ |" E
第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。# ]0 w3 n* O6 \+ R
例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。
1 q8 H0 b) B4 @3 {; D, {
C:获得n、e4 r4 C- x6 ~7 C' c! K: P# V
, _( ^; t# V$ l+ P& T# \
B:
" c+ t/ Z" W* j" [5 |- R' L
第一步:获得n、e& H `2 y$ {; W/ V5 e7 F" y
9 P' H; X2 }% G" o8 i5 C
第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。 O1 e) Z# E% L, Z+ s
第三步:发送c给A* n9 p" C3 D9 Y5 m' M; F( S
C: ^ j% N7 E; c3 Z+ R% j
! ^- F, y7 N2 {" ~6 s4 r7 v
第一步:截获加密信息c; B% f* N) l6 m% Y& Y
3 v$ S" K4 W- |" J& \& y7 }
第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。
4 d5 E7 ~- x) u) Z. `
A:
! ?5 I: y4 w7 z
第一步:收到加密信息c7 A; B; Z" V9 F8 J6 l F2 B
第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。6 T% ~ U" r. ?
完成
安全性9 C K, o# s! E
# c8 [7 P7 B0 E
为什么RSA是不会被破解的呢?; I9 c6 k9 T- e8 m l
0 I4 |( U4 c6 _4 }
为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。/ D! z# B8 K) I) o5 s5 A2 M% k
1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:
' k* |/ x6 {# J3 |( Y' Z
读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。! x( g$ |, i7 `, d+ f
& K. ^1 E. g# I( y1 _" Y$ d& x+ ?/ {+ a
书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。
到目前为止,关于RSA可靠性的描述:
" H7 r) M# T/ J. ^1 b
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
3 ?) O% x' K) O' S9 j
假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。: F( v4 @; E; n4 w% v4 D/ b
: l% n/ E0 Q) s- ?. t
RSA的正确性:) o9 w9 o; R `8 Q* L; u9 p1 B
: F- N5 u! ?: U6 t7 P
可以使用欧拉函数和欧拉定理来证明。7 m7 f9 ]$ T- l6 f( O$ o
(这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)( c1 l% E' n0 l8 U
如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m
那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?
7 {% n' V3 p, b0 j* e) `) j$ q
应用
RSA的应用:数字签名
最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。
' e+ H% L: t4 H* _1 H1 W6 [
验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。
如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
成为第一个吐槽的人