Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

RSA算法详解

小饱1
92 0 0
什么是RSA
; w5 k' y- [; A) R# w前面文章我们讲了AES算法,AES算法是一种是对称加密算法,本文我们来介绍一个十分常用的非对称加密算法RSA。
2 c8 B" \4 O5 Q6 N4 G8 p- E非对称加密算法也叫公钥密码算法,通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。
1 t0 H& ^- ?8 ]9 K$ s6 g- d; ~. RRSA公司在1983年为RSA算法申请了专利。
% c5 ^) Y. B( p5 t- A& M# v) MRSA的加密
$ S- Y2 i3 _& Y2 `RSA的加密可以用下面的公式来表示:
- t/ w& [" D) T' b" _8 N' X6 {) F3 A
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算,可以算是非常简单明了了。
7 a' Q0 K+ p2 F- F: h简洁的才是最好的,这可能也是RSA算法这么通用的原因吧。
( Q/ L& i# h# x# t: u$ t: r: @如果知道了E和N,那么就可以得到密文,所以我们把E和N的组合称为公钥,可以这样表示 公钥{E,N}。
- K7 D; y! x8 a# z; L( q) h! ?0 R如何选择E和N是一个复杂的数学过程,我们会在后面讲到。
" {: k$ J' D& D- T! }* _% D$ C& ]RSA的解密$ A6 G7 g0 e* \6 U5 @: O6 c
先看一下RSA解密的公式:
) t& `. ^1 ~' `+ p7 h0 E5 y  E5 s, Y
& F" z! s& S" ~( O, q4 ?通过公式可以看到,明文是通过密文的D次方,再和N取模得到的。这里的N和加密的N是同一个数字。
7 u6 K. J5 Y/ X  |% I) wD和N的组合表示为私钥{D,N}。
' s: f1 u' E$ S4 N# \N,E,D的生成
$ ?; u( P7 A4 a知道了RSA的加密和解密原理之后,接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。( Y& E* V8 C& `% ]* z; b
生成过程如下:
  a; v" ?) V" U. C0 [1. 生成N
$ M% |* \9 q- a8 u& ~7 W, p- T" v生成N的公式如下:( ]8 `$ V+ ^) w& J4 n; v

" q3 f0 r! W) |2 [: t$ b# sp和q是两个很大的质数,太小的话容易被破译,太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数,它是通过不断的重试得到的。* `1 ^% P+ d5 N$ _
2. 求L. L% o& V6 i$ u* b/ ]
L是一个中间数,它和p,q一样,不会出现在RSA的加密和解密过程。. T8 j6 Y5 o$ i
L的计算公式如下:
1 i; `* X% X  W! z& Y& B+ N( y' ^# Q  O- |( a5 G
L是p-1和q-1的最小公倍数
+ I+ M7 ^2 G% U" {6 h" D3. 求E% Y4 K' |; f) f
E就是用来加密的公钥了,E是一个比1大,比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。; @  A3 h8 W( ?2 f& @9 A- p

) j* L) R: b+ A9 p. }  B这里E也是通过伪随机数生成器来生成的。: }6 k: _: x* w  _
找到了E和N,我们的公钥就生成了。
0 ~2 G. Z4 ?1 H* J9 v( x- ^4. 求D# b- @5 y/ L2 x! ^% l; f$ q5 P+ L' k9 c
计算D的公式如下:4 r5 ~2 M# w7 Q. G& h

) J" U% C5 p$ U# y# o破解RSA
3 O7 D/ a1 K5 \3 f0 d& C5 a) }如果想破解RSA, 对于密码破解者来说,他知道了公钥{E,N}, 知道了密文,根据公式:7 S1 q# t' l" F& K: T& B

8 c3 F1 P# \. a# ^( s# Z) k! {有没有可能直接通过已知的三个变量,求出未知变量明文呢?
0 _( b$ H3 n3 z! ]( F% B1 ~" j这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。% b2 O* I+ d- b
那么有没有可能通够暴力破解来得出密钥中的D呢?2 h- C; c( Q( f, S0 q4 }( F
目前RSA算法中p和q的长度一般为1024比特以上,生成的N的长度为2048比特以上,E和D的长度和N差不多,如果要暴力破解2048比特的D是非常困难的。0 n1 m+ Q5 N* ]1 F6 U7 Z+ D; T
由公式:
8 E+ S! a( J3 t$ y5 [7 R8 V( C1 @9 |' _; L. \9 ~* W
可知,如果破解者知道了L的值,那么就可以轻易的求出D。而L是通过p和q计算出来的,所以p和q一定要保密,否则跟密码泄露是一样的。
9 j% h" r" f  b( \/ O* C* }因为 N= p * q , 而p和q都是质数, N又是已知的,那么我们可不可以通过质因数分解来得到?p和q呢?
5 e' p8 G' N* o, Q# Q目前来说,还没有有效的对大整数进行质因素分解的高效算法,所以目前来说RSA算法还是很安全的,但是一旦有这样的算法出现,那么RSA将会很容易被攻破。
' n4 Y5 F6 ^  u$ m& G" M$ a所以官方推荐:1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年,4096比特的算法可以用到2031年。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

小饱1 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    36