Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

非对称加密之RSA算法

有个胖子他姓杨
101 0 0
简介. b3 y$ n1 f% {# P. [

, b7 X+ m. J2 j    1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。2 n6 H  A0 a$ [5 z9 }% `
& a* g: P, f% i7 y; w
    具体是利用了:
* R. w; z: U, B7 J# S/ `
/ W( H$ z/ i- [    1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。2 j7 o1 @8 d7 Z7 G

1 T- Y2 K5 k- y* c1 |( l* R. s  D! ^# h    2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。( ^2 k7 Z% V1 d3 T

9 h# r/ e2 x$ M! d    原理
. Z4 Z" r" O: n% |9 d& s& V$ n
# L- }- h3 ]* ^# U; W, d( [# s+ i    RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。
3 m6 ]$ f$ a# A9 u: s5 v5 k! h1 Z" J. g
    公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。
+ Y5 Y  g6 j2 }) n" U% ], g9 |1 \/ {
    加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。
$ p" X% r, b' |0 X" [6 O9 [& x, V
- y4 s  x4 }9 X3 s- g% O    解密过程:(c^d)modn=m,其中d为解密密钥。
/ E2 j( y' I' H( `( ]
' `. j2 b7 A/ Z/ D' m    解密密钥d的求解:' _; s; a0 ]1 O

: X3 ~' [9 j( J2 a6 y: F    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
4 m0 q) T8 h% ^+ [- r$ ?
, t0 x: D5 V4 D; h" i6 W* q) ]    费马定理:
* C% l& v. [: h% E6 e  A) L
) I; G' G7 X( s0 |- ?    若p是素数,a与p互素,则a^(p-1)≡1(modp)
# {" L- _. L5 `# B# h1 B5 `5 z7 S1 B7 d3 s% S/ S
    举例% Q0 H- o5 p: \! W0 M

/ `; ?' H) o. }, [" V    加密过程举例(1):
* m" w  G+ `/ T- r& ^- j; G3 D* {, C; Q/ z5 c& w  ?& `
    1.挑选两个质数,如p=61和q=53/ w/ L0 n* d8 t! Y

3 V' F7 v  e% v, B9 e1 h    2.计算N=p*q=3233
7 z3 ]; O+ ^- d1 K, N1 C
# x$ l% h! l$ _% \) {! y    3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】
; g  t+ P+ u. V& o' Q% d% e; C3 _2 F) y6 x( v; t
    4.选择与3120互质的一个数e=17
' L9 y4 t3 U. V# N( T# t0 x8 O$ i1 Q! x
    5.计算得出d,使得d是e关于3120的模逆,得出d=2753
# W9 I5 v: D4 _8 {) y
& G: ?( Q! a' o8 X; N( }    6.如果明文是5,那么密文是5^17(mod3233)=3086' w& @9 O8 G9 O! A) `

  B/ O3 p2 u" K9 q    7.解密,3086^2753(mod3233)=5
: m7 l/ o3 q! D3 z8 l/ N4 P
- z( O# z3 A4 ]) C: Z$ f& C    关于模逆:先用“辗转相除法”…
  ]* _% n+ }" Q3 ?( `- f$ [* s
3 x) J9 }8 s6 d! M# c    加密过程举例(2)-中间人:( Y: G% R! ]1 Q

6 C! o6 `/ T: j. w3 g! x    A:有一个公钥n、e。例如:3127、3。- O3 n" @! a" e/ j
) G6 b8 m& c. f# T3 }$ G
    B:有一个信息m。例如:89。, B5 f8 M- _( k9 o4 n; I4 j
3 |  r/ _- K+ w# q4 A  N+ Q
    C:偷听者
& \" z, u+ P% t, b1 M8 G% w# Q$ c  D  b5 L; \
    A:
0 Z: B0 s" g0 o
# H* h! _$ O8 }    第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。' i: U% l: o, K$ f+ ~; Z

0 V% Q0 L( c! y  u1 Z) q    第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。
' Y9 Q4 E  J+ N3 t+ x3 s3 {( P# k1 N8 N7 W3 W/ k1 N9 s
    例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。& b, k; [# L$ U$ o& Z! i

0 J( q' J3 j0 E# f) d    第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。4 |5 k4 R! c; B2 c. A; d
: a- b1 C! U  j8 K
    C:获得n、e( J3 u! O1 }6 [( r9 g9 r

' Q' w7 g* C  [    B:
2 A3 a; D* P0 x0 T& q; f( `$ D  {8 l" ^5 w: E1 b6 `
    第一步:获得n、e
' m& i! @( h$ F7 E7 |, a1 w5 ^$ x
9 E4 m+ _5 O5 g6 b    第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。
/ R0 m* S" d' l+ K
+ \  V- F% \0 ?5 ]    第三步:发送c给A* p  h' O+ D' \& _

4 _1 d9 C( i& \( U    C:3 s+ W% v3 K9 M, p- b
  |' B, ]+ U3 ~$ x* e
    第一步:截获加密信息c
0 y, |) [7 F( W9 D1 ~7 U6 f* Q5 ]5 |4 G
    第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。  E4 e1 u5 @* w$ s/ h

% u! A4 B4 \1 C3 ^    A:5 a  `& _7 U0 l) e, N+ c6 E
6 `$ q1 P- O% R! v' H3 E
    第一步:收到加密信息c' X: x' v5 Z7 n$ O+ U
4 ^8 C$ {! d+ ?7 [, ]
    第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。
1 X, n' i! e% u" b# ^* R, y" e, h+ A( j4 [
    完成9 r  j# {) [2 [
% h, O! ^6 Y' Z
    安全性3 Q3 `5 U0 b# j8 t7 Y
- e5 [( M# M3 k$ h+ D
    为什么RSA是不会被破解的呢?! a  V2 j+ L/ V, M% G) _

1 H# O$ m: ]8 x! D2 Z0 f1 t# |    为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。
" ?- ~- E: U  U& }- e: R  H( b* \! m7 Z. d% T' \  a
    1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:
: m$ d+ z* }% i! z4 x1 E. P$ g
7 \- d  T2 x/ j3 n1 y    读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。% Z  |+ m+ x. P9 S8 S

7 ]7 V, B) u" F$ {) {    书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。4 [) |. M; o( ~& E" ~
" P# f+ K( S" B. k9 h) w3 ]/ b
    到目前为止,关于RSA可靠性的描述:) Z% R0 ?3 W  H, M
& n0 F8 o; v" J6 a0 Z; c5 [2 h
    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
- {* m: k! z' z/ R- s7 a1 v# J' s% Q6 h. R% h! \
    假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。
( L/ ]; C- s8 m# Z: }! I$ Q  `0 a# J  c3 Q
    只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。
1 A6 q$ G5 g! G( S
! j0 N  X0 n2 ]; K: F: ]$ a    RSA的正确性:6 d& L( m9 h, c0 i1 J1 Z, K

2 Z8 }; F) S$ |: l: A( \# k    可以使用欧拉函数和欧拉定理来证明。
7 e0 G9 ^2 h  Y" @/ p" {
9 O; Z1 b" G. z# v) c4 }/ G    (这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)$ p: ^3 P' }  B3 c; \
( z# s6 v# S+ F1 r6 e
    如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m* x7 s4 w' ^! j7 Y0 N8 {" T
! k, b! }# Z- d# w$ L% A3 G
    那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?
: C( `5 p. x& v' n4 Z7 {' k( X& g' K  v0 ~
    应用/ F% a& v. x' U8 k
8 ~) z, g! ]7 l4 v/ V  n" D
    RSA的应用:数字签名/ h5 p& c2 v2 P/ Z! Q$ ~* q+ |
' q/ d0 H$ W; {2 N( ]0 q  a% \
    最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。% V7 d, G. h& I& Y" r+ @
6 }7 d0 t2 K% n  J5 i' v
    验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。5 b2 L$ b, q* }+ Q3 k' e. R& p7 _

7 G# n( c, T, ]9 o    如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10