Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

RSA算法详解

小饱1
89 0 0
什么是RSA6 A. P+ K- p+ k6 y) ?
前面文章我们讲了AES算法,AES算法是一种是对称加密算法,本文我们来介绍一个十分常用的非对称加密算法RSA。
4 u: N: T* `: h# s5 t5 r, v; t) X非对称加密算法也叫公钥密码算法,通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。9 X) X, i3 x: S! X
RSA公司在1983年为RSA算法申请了专利。* `- [4 M$ O4 d2 R# x( P
RSA的加密" R- O# N: R4 E3 h4 }& D. t
RSA的加密可以用下面的公式来表示:
- U( t* U* S; N6 g) ?9 m
& T- _$ |. @3 i9 S4 Y& |通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算,可以算是非常简单明了了。5 F) z  W' |5 s/ B  {
简洁的才是最好的,这可能也是RSA算法这么通用的原因吧。8 }. l: x. n- b1 w
如果知道了E和N,那么就可以得到密文,所以我们把E和N的组合称为公钥,可以这样表示 公钥{E,N}。" S3 z9 C& |+ D) D# u5 B: m9 {
如何选择E和N是一个复杂的数学过程,我们会在后面讲到。
) i# M( ^( ]! m. |) ~8 S; PRSA的解密
& K# O5 {) n! _0 m先看一下RSA解密的公式:. d9 c1 d$ K1 O( L" J0 J& T
8 U: M) ~( r/ H4 K& Z
通过公式可以看到,明文是通过密文的D次方,再和N取模得到的。这里的N和加密的N是同一个数字。' U0 }" g- D* y6 U" @9 g
D和N的组合表示为私钥{D,N}。" i" j. B& m& U" k, G3 A  H  U! Y
N,E,D的生成. e1 P$ G( t( c, q4 K4 Y. Z, E- j
知道了RSA的加密和解密原理之后,接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。4 y6 [; }0 D7 J" {: C0 e
生成过程如下:
( T+ \; Q! W# \) F. j2 C1. 生成N
9 T1 |' o0 E/ c& f1 y* b4 T+ M# P生成N的公式如下:
; ]( M! O. R2 A4 u# k
& V) g( M9 D. }1 np和q是两个很大的质数,太小的话容易被破译,太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数,它是通过不断的重试得到的。0 a3 m( |! L0 g3 Y# F* ^' X
2. 求L+ M& u! X: p: {. L; w0 I
L是一个中间数,它和p,q一样,不会出现在RSA的加密和解密过程。$ j1 G2 @, S) f" U7 R
L的计算公式如下:1 X  `9 u0 A% D: Y- M; \
$ K' \" m- l( n6 B/ h! [" M2 k; Q
L是p-1和q-1的最小公倍数0 `+ e0 B9 J% n( Q; y* K) |+ p
3. 求E3 Z0 k0 r, {8 t, @3 j
E就是用来加密的公钥了,E是一个比1大,比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
2 B/ D  R0 a4 q" E. @+ z. c8 h" U: {) A8 e6 T
这里E也是通过伪随机数生成器来生成的。
' {9 a- a) E# T1 B& t3 q找到了E和N,我们的公钥就生成了。
$ Y$ p& q7 ?2 x6 z6 a; b* s% c' _4. 求D
+ c/ v% c9 p6 B# M* b) Y! W" C计算D的公式如下:
8 ^' L9 S% A: _' V6 n3 ^; @( a4 l8 h
破解RSA
! G9 G9 b# M) K1 \# C0 }2 U. Z如果想破解RSA, 对于密码破解者来说,他知道了公钥{E,N}, 知道了密文,根据公式:
' Z$ `4 S( }; Y  s6 r$ Y# }! g- v3 _) W( u/ p
有没有可能直接通过已知的三个变量,求出未知变量明文呢?" J( M  m% j. Y
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。  _5 s6 G2 N& n9 y- }
那么有没有可能通够暴力破解来得出密钥中的D呢?
5 [7 K0 g6 b2 o+ u9 ~3 G目前RSA算法中p和q的长度一般为1024比特以上,生成的N的长度为2048比特以上,E和D的长度和N差不多,如果要暴力破解2048比特的D是非常困难的。4 S! b% k0 r& p3 x1 |+ G
由公式:
$ r/ j' b$ \% i% K& L2 b
' Q& ?, w2 x2 H: r: A) u- M可知,如果破解者知道了L的值,那么就可以轻易的求出D。而L是通过p和q计算出来的,所以p和q一定要保密,否则跟密码泄露是一样的。
3 m/ R; c8 H5 `' R因为 N= p * q , 而p和q都是质数, N又是已知的,那么我们可不可以通过质因数分解来得到?p和q呢?
; w, j3 G$ E" a8 Q目前来说,还没有有效的对大整数进行质因素分解的高效算法,所以目前来说RSA算法还是很安全的,但是一旦有这样的算法出现,那么RSA将会很容易被攻破。8 \1 g$ M7 [7 a; Y; `
所以官方推荐:1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年,4096比特的算法可以用到2031年。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

小饱1 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    36