RSA 演算法4)

〖Encrypt〗
 
上一篇|下一篇|回文章  分类讨论区   全部讨论区   本讨论区  
 
  发信人: Bird_Bird.pbbs@bbs.nju.edu.cn (Bird Bird), 信区: Encrypt
标  题: RSA 演算法4)
发信站: PowerBBS NJU Station (Wed Dec 24 04:06:15 1997)
转信站: whbbs!ustcnews!nju_pbbs


现在来讨论 RSA 演算法编码解码的速度........

因为我们是对一些很大的数作计算,
所以, 一些加减乘除的运算, 必须自己写成函式来处理这些事......

就 N-digit key 的资料而言, 加减法需要 O(N) 的时间,
乘除法需要 O(N^2) 的时间........
至於计算 a^b mod c, 则是需要 O(N^3) 的时间,
亦即, 要对 N-digit 的资料用 N-digit key 作编码解码,
是需要 O(N^3) 的时间........

一般的实作, N 是介於 512 至 1024 之间, (太小的话很有可能被因数分解开)
所以算算 N^3, 其计算量也是相当惊人的.......
这意味著, 用 RSA 演算法来编码解码其速度是非常慢的.......

既然 RSA 的速度很慢, 这就表示它并不适合所有情况.....
比如 ftp, 这就不适合全程使用 RSA 作编码解码.......

如何去改善速度? 还记得之前所提到的 DES 吧?
RSA 搭配上 DES 的话, 就可以弥补编码解码时速度太慢的问题了 :)

先前提到用 DES 作编码解码时, 双方必须使用同一个 key.......
所以, 我们可以用 RSA 演算法将 DES key 送给对方,
而後接下来的资料, 就全部利用 DES 来做编码解码,
如此, 整个过程中, 因使用 RSA 而耗掉的时间就不会太多 :)

再者, 产生 RSA key 所耗掉的时间, 也是相当惊人的..........
先前提到, 以 N-digit key 为例, 两个相邻质数平均间隔为 O(N),
对於这些数, 我们要利用费马小定理去判定是否可能为质数,
而计算 a^b mod c 所花的时间为 O(N^3),
所以算一算, 平均要找到一个 N-digit 质数, 需费时 O(N^4).......
所以在产生 RSA key 时也是一件非常耗时的工作.......
所以, 一般的作法是, 先花一大把时间去找 RSA key,
往後的编码解码就使用这一组 key.......

就以 stand-alone telnet daemon 为例好了,
可行的做法是 telnetd 一开始执行时, 先花时间运算出 RSA key,
之後 telnet 连上这个 telnetd 之後, 丢给 telnet 这个 RSA key (public),
然後 telnet 将 DES key 用这个 RSA key 编码丢後回给 telnetd,
之後的通讯就用这个 DES key 作编码解码.........

 小鸟
--
 * Origin: NJU PowerBBS


 
 
 
  
 
上一篇|下一篇|回文章  分类讨论区   全部讨论区   本讨论区  
 
Copyright(c)2000 白云黄鹤BBS站 All Rights Reserved.