Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

RSA算法详解

小饱1
69 0 0
什么是RSA
! \; l( Z' Y% K前面文章我们讲了AES算法,AES算法是一种是对称加密算法,本文我们来介绍一个十分常用的非对称加密算法RSA。
" s3 M  K6 U3 W7 p& k非对称加密算法也叫公钥密码算法,通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。
) O+ ?. s3 R3 @0 @" i5 ]$ u$ _- O) ?RSA公司在1983年为RSA算法申请了专利。
- t2 v  e. f. o. tRSA的加密
5 C+ r' \/ P* W- G' YRSA的加密可以用下面的公式来表示:6 X) B% R5 E9 j+ |

0 R5 F6 E) _3 Q通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算,可以算是非常简单明了了。" A  v7 d8 Y8 o2 q( \
简洁的才是最好的,这可能也是RSA算法这么通用的原因吧。
8 Q  _/ d, i' c5 Z/ b如果知道了E和N,那么就可以得到密文,所以我们把E和N的组合称为公钥,可以这样表示 公钥{E,N}。
2 I' E; G+ X4 Y# Y& b/ G+ p" I如何选择E和N是一个复杂的数学过程,我们会在后面讲到。9 \6 [. b" f+ A* U- J7 _) p- b
RSA的解密; y  n5 F. m' U/ B. x7 K
先看一下RSA解密的公式:
1 x* u' }& ?6 j6 Z: E" r; Y% c+ @) U, e* v0 V# O
通过公式可以看到,明文是通过密文的D次方,再和N取模得到的。这里的N和加密的N是同一个数字。
6 H# d2 L9 [& AD和N的组合表示为私钥{D,N}。
7 P# U* G+ i3 I! I, s+ y1 KN,E,D的生成
! R2 q0 q/ z" ?8 v7 s知道了RSA的加密和解密原理之后,接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。
, J1 ~" T" o4 u9 v# o) o生成过程如下:
7 R( c2 |/ \7 P' I9 t1 d# s4 O: }1. 生成N
' A! h5 |7 W4 \生成N的公式如下:
! Z; d- ]5 Q8 c1 F# z( U% T) L" K# O8 ?$ x9 N
p和q是两个很大的质数,太小的话容易被破译,太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数,它是通过不断的重试得到的。" S2 {0 z4 q2 X& g5 ~
2. 求L
8 k  o+ g6 w6 w: f- U% R% R" _L是一个中间数,它和p,q一样,不会出现在RSA的加密和解密过程。" H3 e: X, X9 k4 h1 I5 a9 v
L的计算公式如下:3 z, m9 u- ^1 g0 {& _7 I
. r/ n& [6 W9 @: U9 z& R5 t+ Y# x  x" c
L是p-1和q-1的最小公倍数
! T7 m( F# P, u7 p$ V2 M# f% X3 P3. 求E
! @: k3 Q! `6 ?' w+ P" q, y' C% }E就是用来加密的公钥了,E是一个比1大,比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。$ m3 Z( K" v- M/ F/ |8 Z
6 s8 H0 {& z# m6 C: p
这里E也是通过伪随机数生成器来生成的。, B4 _2 j' M  g4 F
找到了E和N,我们的公钥就生成了。
2 z& w9 {/ B( V% o2 u9 k6 U4. 求D
% G/ q. h  G( o' W8 A计算D的公式如下:. ~% ]7 O" C1 P" \6 V
9 r2 |- X+ p% n' }8 @+ G" Q8 j
破解RSA# n/ _# {3 J: F' I
如果想破解RSA, 对于密码破解者来说,他知道了公钥{E,N}, 知道了密文,根据公式:
& A$ Z, u/ H7 ~+ |( N
# i; p1 E1 P' {; v) M+ N  I$ d有没有可能直接通过已知的三个变量,求出未知变量明文呢?6 ^8 U' ?( a: l' y
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。) @' `9 u' C+ t0 y% W$ e' z' |
那么有没有可能通够暴力破解来得出密钥中的D呢?
5 c* m0 n+ l4 i* p1 |2 i目前RSA算法中p和q的长度一般为1024比特以上,生成的N的长度为2048比特以上,E和D的长度和N差不多,如果要暴力破解2048比特的D是非常困难的。
! w5 L& l5 v! D# ?4 r1 z' V由公式:- |7 e, q  k1 r+ d

3 p2 [# Q0 H" R8 w1 w; \可知,如果破解者知道了L的值,那么就可以轻易的求出D。而L是通过p和q计算出来的,所以p和q一定要保密,否则跟密码泄露是一样的。0 R* G# F. E' F! ^+ q8 k9 [9 J3 o
因为 N= p * q , 而p和q都是质数, N又是已知的,那么我们可不可以通过质因数分解来得到?p和q呢?) X0 M6 @$ \7 N4 \3 L4 c. m
目前来说,还没有有效的对大整数进行质因素分解的高效算法,所以目前来说RSA算法还是很安全的,但是一旦有这样的算法出现,那么RSA将会很容易被攻破。
) I9 N+ J" D, W! R5 l; \' y. Y: |所以官方推荐:1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年,4096比特的算法可以用到2031年。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

小饱1 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    36