Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

非对称加密之RSA算法

有个胖子他姓杨
131 0 0
简介
; m" Y8 z/ s4 ~4 U% [% ~/ Y
4 _  F/ ]* {% W( G& l- f& h' f    1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。
/ b9 d0 W7 s2 o1 N8 t1 L
7 X0 Z# O; ~0 V7 o    具体是利用了:4 n( I! i: K4 r2 |# u1 x$ `

8 Z& ?+ V5 R: n/ d% w& ]    1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。
; e  @$ k1 S! m) j* E5 Q, G9 R$ I
: w5 H0 Y6 Z2 t    2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。
9 I2 B2 Q4 K* p; v# t. {$ l% w& q3 @/ p& }
    原理4 O* b' S+ N5 s0 E, w; `; C5 Q2 T
! m5 t& T& [, b/ f. ^+ z
    RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。" u! |1 G( A( G2 g  v3 U

; d2 m1 f! |5 J5 k5 C    公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。1 {% M7 U2 q8 d: h/ N
- x- o7 f* I6 n
    加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。& P; l" D  @% f) I4 K

! j0 ]1 Y( e. g: R/ J% [+ F1 y    解密过程:(c^d)modn=m,其中d为解密密钥。; N+ K* ?; e# n4 w, Y
2 E6 ]8 E' w6 P5 l, X$ R# w
    解密密钥d的求解:
7 @5 \7 h$ N( K# s/ j' }8 H
7 h4 S! |" T/ R- W7 V5 K! I    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
, F* N- L' W& w0 n- D. V/ W
% P: l' k, T0 b7 C3 T. o    费马定理:
) f) N  Y0 G- u8 v$ D3 A6 Z. A8 M3 W+ U, {' i
    若p是素数,a与p互素,则a^(p-1)≡1(modp)+ L. Q; Q1 [9 F% @+ a) e9 L

; r! @+ U& {* _9 L* T. S    举例# N& \1 e9 i. c' P

' @. h! b' s  P, g- |    加密过程举例(1):
/ I! P' i$ r* Z  Y8 u- Q$ A9 H1 ?/ c# X
    1.挑选两个质数,如p=61和q=53. l, _3 U6 O, w) Q8 y! |' ~0 ?- H

* k/ z: U. J- Q/ C' @    2.计算N=p*q=3233' l3 M: A8 H8 d, v* I4 t1 z
8 x  V8 M' P: P" Z9 `' ]2 z
    3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】, z& g+ q& [) s+ }9 s
  n% A8 P! h; n0 n9 \) U! ?
    4.选择与3120互质的一个数e=17- g6 U( c: A: s' S' \& K
' A  j" f7 t- P9 h1 a% s( y2 q
    5.计算得出d,使得d是e关于3120的模逆,得出d=2753
7 X/ N6 X. Y/ Y/ Z6 T
, h, g' R% `- b& L4 `& s    6.如果明文是5,那么密文是5^17(mod3233)=3086
/ k. W' `( C: E# t
; r) D# w8 |2 R$ E9 f    7.解密,3086^2753(mod3233)=53 x0 Q# l1 m# ~% {5 C' b) j

0 F8 q& v2 Y3 ~: {    关于模逆:先用“辗转相除法”…
* X+ N+ Q, V3 I! X. o. s
7 k; s7 K& E4 E9 U1 P8 ?    加密过程举例(2)-中间人:' G. L+ Q, j5 E* s; h, ?) u
& q2 m$ K2 \  b( f. q. C
    A:有一个公钥n、e。例如:3127、3。% u% y0 i# y! ]) V7 s% V
5 I3 c$ a" g4 k; ~  x* l
    B:有一个信息m。例如:89。2 W6 {) e- U; w+ J- `/ F

/ n4 |! `: u& }( d7 y    C:偷听者
/ |& T2 r% [% R0 O( @# k5 D: N, u- r
    A:
, a( J% j) ~2 y# p  A- s8 ]$ c( j. |- @; e  ?% g0 }
    第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。
& N! {5 o, t  w2 N% N8 Z
% J% W- @6 L4 ^( [    第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。
% o5 n) |" j2 e; c! I) w
$ b7 ]8 o' }! ?7 P    例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
( p0 n. i# }( Z' E4 A/ W  f) `1 d2 b$ S% r0 |$ ?1 W% L& F
    第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。
% x+ L4 }! [# Z$ D# h+ w
: O; o* b# w" g5 e- b# K, d* z    C:获得n、e  I& r& m, _/ T) G# R
. E5 M1 {& C/ }/ B+ e( x
    B:, x' Z; h& F9 ?  |' B7 Z- D" `

$ t! L! J  j. i, `+ l0 I" G7 f    第一步:获得n、e
' H* F( t# D" N+ |% l, \* b8 v7 }; L7 v
, z8 e+ D( s, O: d* S" Q- {) Z    第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。. S7 {5 s0 @& D4 I5 M
( e- ?4 |% v) h* A! x; _* ^
    第三步:发送c给A* a: Y6 [1 W! d) b0 W- f) x

. y% U& u0 o" t% v& F7 p; c% K    C:& W" O3 A4 Z  n+ L

( Y4 _1 F# W* l. y% F    第一步:截获加密信息c
, d4 N: v3 h; |) f
: E5 T: c# ^8 F( Y0 r3 B    第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。' Q6 [& _' J" V& o
  Q1 a. x1 f- h! V% l  `
    A:1 T; g) }9 X% q2 G" Y5 ^% g! |

# K9 g1 h: A/ S* J* U! K* P/ O    第一步:收到加密信息c
$ h3 e6 ]5 z3 S8 D( m
* u4 ?9 L$ l; r. _" F1 d3 i    第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。
- `& u1 y7 j  n2 C8 F. X9 v+ V) u- K: P$ j& `" ~
    完成' ]( B7 o: A' q" x+ {3 c' L+ v# M

* w% l* Y5 K' ^; f: o2 G& u/ D# X4 t    安全性
2 k, X% c$ w$ `. F8 K( ^# p: C2 H! }, G7 d' ~
    为什么RSA是不会被破解的呢?# |7 C$ [- ?$ i1 T/ F& U
& V+ q; J/ S$ {5 Z8 v1 v  L
    为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。3 {% y0 I& J7 ?# Y

' Y$ K( {2 t& K  Y9 F2 `& Y7 Q) E    1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:
2 x% v" v8 A1 p9 u$ q3 _6 Q5 D& R' W$ G
    读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。; b/ {$ `( ]/ E% ?- ~, E

; ^8 K6 ^+ p5 M    书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。5 g* N' x3 T( t3 e. i

5 O3 R. ^+ {- x5 S) C4 \% I    到目前为止,关于RSA可靠性的描述:* P( o. r5 ]! D7 w

) [8 u3 D& e# k    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
8 z3 e: ~4 Z" ]! u1 R0 u1 D6 ~- l& J: Y
    假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。& E, W( ?0 \6 i( R) c1 m
" y3 T! M/ Z$ J& X/ a7 O) ]
    只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。, J$ A- j  y% j

, r$ ^3 x/ R7 K* x    RSA的正确性:
! W8 r8 u+ q. _3 E. z; I; A/ i- w
% l2 X" q+ R# S+ Q0 v    可以使用欧拉函数和欧拉定理来证明。
; I1 g' s5 j' F  `
, s/ Y/ f% W( f, J( X8 c( s2 L. j    (这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)
) O1 q; l. U) d# w& J* A1 t2 |; f$ s% S
    如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m
  a& r9 B0 h; r0 [# w: T; z! s& ]2 d2 i$ H9 r/ m- {
    那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?2 s1 h* n+ R% j" E  f' C! o
- P( _' b8 W( T( `* c! _/ E% b$ X. f
    应用
3 I9 ?9 v- I/ C9 A1 t) f# F5 `: I' R& G: C) c
    RSA的应用:数字签名
% ?8 q1 m* J5 f7 M" @. O+ u
9 g, p% U; P7 M1 B1 _$ q) L4 J    最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。3 g% R4 T4 J$ m7 ]( I! G* n0 A

: e# E/ m+ h1 y; x3 S; M    验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。
! C0 a2 a5 B$ O6 b+ r4 L1 {- z4 y  Z* j& }
    如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

有个胖子他姓杨 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    10