Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

RSA算法详解

小饱1
214 0 0
什么是RSA& N( p: e, ~' G  x: u6 X, _
前面文章我们讲了AES算法,AES算法是一种是对称加密算法,本文我们来介绍一个十分常用的非对称加密算法RSA。
1 ^# `% j' x! z( H' c$ R. @! L5 a' [非对称加密算法也叫公钥密码算法,通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。+ B6 Y1 |% g% R2 ^: q2 N
RSA公司在1983年为RSA算法申请了专利。
/ U1 q0 k7 O; A9 lRSA的加密
6 x0 Q' n3 e: dRSA的加密可以用下面的公式来表示:
* I/ |  V4 ~1 d3 L6 l+ \) _! i# F0 }9 p9 D
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算,可以算是非常简单明了了。
8 |: H% O+ h' f2 [( F$ d简洁的才是最好的,这可能也是RSA算法这么通用的原因吧。
( ^1 {' E( O' h- T4 F3 J如果知道了E和N,那么就可以得到密文,所以我们把E和N的组合称为公钥,可以这样表示 公钥{E,N}。
& B, ?/ E' ^2 {' ?如何选择E和N是一个复杂的数学过程,我们会在后面讲到。
2 Z+ D6 j( s2 W2 ^& bRSA的解密
4 ~! X  z( l, C& w3 f先看一下RSA解密的公式:' j; `: a6 r  p9 L! r

- k9 H: p% q- N% i, X, c5 ?/ j通过公式可以看到,明文是通过密文的D次方,再和N取模得到的。这里的N和加密的N是同一个数字。
' b- h/ x; j& J/ F8 g# q/ ^7 aD和N的组合表示为私钥{D,N}。
6 r9 R8 N4 R( h+ p: V' y' X: R: xN,E,D的生成
+ ?- a; _7 C; r; j, C, W1 ~9 D3 v知道了RSA的加密和解密原理之后,接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。* f, O' }! O9 d5 h3 ]) Q
生成过程如下:
0 q7 u: j, a4 \8 h$ `. V: s' ?' I1. 生成N8 X# w0 f/ m/ `$ |' K
生成N的公式如下:
$ z' d+ R  m9 X. a
1 l7 S) g1 I7 Np和q是两个很大的质数,太小的话容易被破译,太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数,它是通过不断的重试得到的。
+ Q1 q2 y* k0 h6 A& {+ r2. 求L  I! p  B  n$ j* H3 f& D% [
L是一个中间数,它和p,q一样,不会出现在RSA的加密和解密过程。
9 M! U& M/ x1 p% t( }' SL的计算公式如下:7 ~+ D, H7 C$ L4 i. w, W+ q, E* W$ w

* a: a2 Q) E; u3 M+ v$ l( E- SL是p-1和q-1的最小公倍数* e' I" _& M; r2 q: ~
3. 求E) U, i' b# ^0 _& i
E就是用来加密的公钥了,E是一个比1大,比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
6 S, g& V- h0 T  y' v) I5 \! J/ ?- \8 `! j; U3 \: K6 D) R
这里E也是通过伪随机数生成器来生成的。
! C( L5 c: M& |! @% h找到了E和N,我们的公钥就生成了。  x6 s; u% F! O
4. 求D
+ P7 K2 {5 N; U# h计算D的公式如下:$ ?% v, S. P! ^) D& A
2 \5 M7 z. Y; D. B) {
破解RSA) c/ L" i$ Z( C! s6 B
如果想破解RSA, 对于密码破解者来说,他知道了公钥{E,N}, 知道了密文,根据公式:
0 f- Q" ?2 D# u+ E! @3 u4 _9 n
) L7 ?& D! `) ?6 t4 n有没有可能直接通过已知的三个变量,求出未知变量明文呢?
; M$ T% K" u, W8 }# M2 c' r这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。  j" ~$ ?( Y: w4 j( p% S! c
那么有没有可能通够暴力破解来得出密钥中的D呢?& g0 w% B3 N' q7 x8 n1 n- n
目前RSA算法中p和q的长度一般为1024比特以上,生成的N的长度为2048比特以上,E和D的长度和N差不多,如果要暴力破解2048比特的D是非常困难的。
2 U2 u# l, t, H% X3 C% j由公式:
8 ^9 k1 p5 K9 h/ H
6 r( t2 G% |8 C5 B可知,如果破解者知道了L的值,那么就可以轻易的求出D。而L是通过p和q计算出来的,所以p和q一定要保密,否则跟密码泄露是一样的。
8 c0 x1 _! ]7 z7 l. X因为 N= p * q , 而p和q都是质数, N又是已知的,那么我们可不可以通过质因数分解来得到?p和q呢?9 }. t, B/ V5 ^1 s: X) [( s
目前来说,还没有有效的对大整数进行质因素分解的高效算法,所以目前来说RSA算法还是很安全的,但是一旦有这样的算法出现,那么RSA将会很容易被攻破。
  Q  p9 e$ I' X5 K' U所以官方推荐:1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年,4096比特的算法可以用到2031年。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

小饱1 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    36