公开密钥加密算法

rsa.rb

#!/usr/bin/ruby

=begin
RSA公开密钥算法

加密原理：
pq = p * q, p和q是素数
k = n * (p - 1) * (q - 1) + 1, n为任意正数
e, d = 能使e * d = k的任意正数

例子：
p = 3, q = 7
(pq, e)是公钥，(pq, d)是私钥
=end

def rsa(pq, k, mesg)
  mesg.collect do |x|
    x**k%pq
  end
end

orig = [7, 13, 17, 24]                        # 需要加密的信息
encode = rsa(33, 3, orig); print encode, "\n"
decode = rsa(33, 7, encode); print decode, "\n"

有效性

当p与q是非常大的素数时，从积pq中计算素数并不简单。RSA暗号中一般使用钥长是1024位。
1024位长的整数，用几千台超级计算机满负荷运行进行分散处理，在现实时间内，难以进行素因数分解。
RSA加密的强度，就归因于素因数分解的难度。