Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

非对称加密之RSA算法

有个胖子他姓杨
102 0 0
简介; m2 p5 w) W$ g4 y- A; ]4 r
/ @% t) i8 `( y& ^4 j
    1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。
8 ]; L4 n+ l5 B8 {' X" ~/ l) ?
    具体是利用了:
: n7 u- _6 q8 ^' E
/ A- p3 c) ?1 h' _& ^& {    1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。( _5 s( }6 M- ]

6 Q5 P/ A( q$ y    2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。
* ]. E/ |7 O$ o! u5 K
* S' o2 C7 ~* z. |, J    原理- n! S4 L; Y/ A/ |( M( M
0 q1 x4 y: y- G# ~: J# f( R
    RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。: N" x: W8 D: e8 q( x* i; C
( c1 x! I4 s) f) g9 v+ @3 `! I
    公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。
9 P! x! u; c4 o
& T0 W/ k7 X2 V$ C0 j2 a8 D    加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。' W- w1 H% Y" X/ @4 B% X( s
# L  ~0 U/ L4 ]( j
    解密过程:(c^d)modn=m,其中d为解密密钥。
& H9 N0 s3 g  }, _) u2 J8 S3 K* i' k7 P
    解密密钥d的求解:% y) q6 `6 O% S, L. g* |

3 v9 m" B, n( T4 `5 F; u& ]    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
- M' N( `4 W3 G* A
# r/ l; S4 [2 V; U' I9 T, J2 z    费马定理:& o6 e" I) @* e( s: ~% A: }
7 Z1 D2 g# `( ]) P
    若p是素数,a与p互素,则a^(p-1)≡1(modp)4 Q$ ~* P- l  Q/ Y( L- g. Y
& z& C# R% w$ l* N) J
    举例/ T0 {) T5 O, o% d- ?8 d7 ^9 A
5 f4 H1 W, x; `; }4 D- Y. o( ^
    加密过程举例(1):
# `: J9 ~+ O  Z4 \
  ]0 |$ x: [. n+ ~6 U    1.挑选两个质数,如p=61和q=53" S5 a2 o3 e! F" D) n9 X( a

. s  U4 R3 v' T+ o8 {    2.计算N=p*q=3233
3 L/ q0 Y8 P* T! p
  l$ p- {- P, p6 b    3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】
" ]9 |# J0 O5 |
) d  n  G5 x4 I2 Z9 Q9 `    4.选择与3120互质的一个数e=178 Y. i! R: _- Z2 g9 i
7 x/ i6 r2 R8 k; p! d
    5.计算得出d,使得d是e关于3120的模逆,得出d=27530 b/ h- A  Y" O+ M- ^6 }

% Z3 K8 Z1 L/ R- o* f8 e4 {0 m- ]    6.如果明文是5,那么密文是5^17(mod3233)=3086( v0 O3 g, _* g" L" V

- ]/ A9 c" q" f2 K5 G: _/ k    7.解密,3086^2753(mod3233)=5: {; r* V# ~1 v' S* C4 H  S
4 p3 o8 x' x1 e8 w. q
    关于模逆:先用“辗转相除法”…
" N; L) F8 P7 }/ ~  ^9 q/ M* w* n2 _, _" U! @* `
    加密过程举例(2)-中间人:5 x; v9 Q- B% N$ T1 ^0 A3 m
9 |3 D; z0 w; h% P5 k
    A:有一个公钥n、e。例如:3127、3。
1 f. i& q' _9 |  {9 A6 p4 N7 |2 W3 k
    B:有一个信息m。例如:89。
5 G2 Q' |. c! a) F% b
4 Q2 @3 m+ m$ y5 a5 z6 Q    C:偷听者
, C- @" n2 P& u; `$ B" @/ [7 v5 T- m5 f7 Q
    A:
  L# A' Z8 I" ?- B2 W2 z9 g3 y5 t% }/ w% L2 v/ D$ D* ?
    第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。" l4 K8 T. h# c4 t. h
. @8 ~/ _* U8 @, [9 Y
    第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。
+ F$ M3 ~0 a6 j$ n
9 @( D& R" \6 D' H/ X+ K    例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。2 [, ]4 ~/ H, k" ~3 T
4 `/ F; n1 G9 }  b; F& ]& j
    第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。
7 l' X2 |8 K% |7 Y( A
( q9 q2 I9 ?  W+ W) j    C:获得n、e
7 w4 t* h; w! M7 J8 O3 a. l8 _  C( H
    B:
* `( N" q: G8 I$ v
4 L: c+ Q* \  F7 J    第一步:获得n、e
! b: y& t" S& B' C
% E( H, N7 @( a9 u    第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。
  h7 i4 k6 K! C6 ~/ ^' J4 d# j
0 f2 z) L3 @+ V0 I% _    第三步:发送c给A$ T. b7 o* R1 x" N1 l+ m6 E

0 v% t: W) g! s6 m/ g    C:" P. x% m7 @2 b. y
, G# K, e; ~, o# G" H- Q/ B
    第一步:截获加密信息c
7 ]4 w# ?3 A5 P# L
# O% L$ V- A$ k    第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。
. a4 J  Y5 U. a9 o
" ~8 r8 J$ G7 @: k' E    A:' W4 ?' ~3 X/ b' f: s$ y( v# c. ?

8 c# O9 S  v9 b- i    第一步:收到加密信息c5 ?' Q5 Q0 ?" J2 L4 k% \' `
7 }2 b- O/ T6 j
    第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。7 l& U% M! F" B4 D! ]4 C+ e7 s

: c- o: l5 c$ a- p2 P1 _( @    完成
" }1 u; L) ^9 @; z/ N3 q# O% _( i
    安全性
6 d* s: i- o+ p. e8 }0 p+ D0 x# J2 J1 a! Y9 c
    为什么RSA是不会被破解的呢?
6 Q  k+ L) H, w% ^. ~- E
5 W/ ]4 k8 Y" K- C7 V    为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。
4 x3 R4 D2 g, w! A% ?6 j( T! k; }" c* H. g8 _9 o
    1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:) J% w* {5 ^# I6 d+ U

8 t! ]7 f" M0 \8 b    读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。1 d! l2 v* j4 p3 Y
, k" Z8 a) J  R6 ^+ u
    书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。
1 ]+ c3 \; U6 U
+ B/ V1 J. ~+ f    到目前为止,关于RSA可靠性的描述:
  d4 Y: J, a# R4 C! i& h! U, `2 \+ o2 j
    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。5 A( H5 C0 E- @4 [) s

$ d' G* E! L$ X2 L' y! Z1 s# D    假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。
1 \$ [; ?7 j8 U. ~9 {; B3 N8 N$ ]$ }; s5 _
    只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。
0 _( C$ r' H: I4 M( Z9 A8 E
; o% G5 P. u. w: ?% S5 ~# ~    RSA的正确性:2 n9 F; G. [' ]% R) K; s

$ S9 |4 L0 S/ P! {    可以使用欧拉函数和欧拉定理来证明。# K4 w4 E; Z$ m; A7 {( ?6 n
! w5 y. P2 P5 ?* h& |
    (这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)
$ D1 O* S, J4 e) e
; e( Z( S7 [2 F0 B- _8 ]; V* Y    如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m. N( ~! m) L8 _! v: k. t' a7 F& [  o

9 L0 O- w; w/ X2 z7 F; R1 d    那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?
; [1 r! j9 {5 j! F% @; s0 x) s  Q4 K! E" w9 A/ P" h
    应用
" I  u/ _: }3 \. Z" z5 k9 ?3 q! I# `
    RSA的应用:数字签名
6 x' {' z7 f% D7 X2 r& L& V* ~* g& i6 B
    最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。- k% W' j  e. y5 ~6 f) J' N

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

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10