Ruby中的公钥加密演示

Question

我写下了下面的ruby脚本，以帮助我的学生理解公钥加密。我遵循这里显示的“铅笔和纸张”方法：http://sergematovic.tripod.com/rsa1.html

只要29不选作p或q，如果选择29，则计算密钥时会挂起。谁能告诉我为什么？

#!/usr/bin/env ruby -wKU 

#initialize 
primes, p, q, n, z, k, j, m,e,d = nil 

def prime 
    primes = [2,3,5,7,11,13,17,19,23,29,31] 
    primes.sample 
end 

#pick p 
p= prime 
puts "p: " + p.to_s 

#pick q 
q=p 
while p==q 
    q = prime 
end 
puts "q: " + q.to_s 

#find n 
n=p*q 
puts "n: " + n.to_s 

#find z 
z=(p-1)*(q-1) 
puts "z: " + z.to_s 

#pick a relative prime of the totient 
k=7 

puts "k: " + k.to_s 

#calculate secret key 
j=0 
while j*k % z != 1 
    j+=1 
end 

puts "j: " + j.to_s 
#message 
m=16 
puts "Message: " + m.to_s 

#encrypt 
e = m**k % n 
puts "Encrypted: " + e.to_s 

#decrypt 
d = e**j % n 
puts "Decrypted: " + d.to_s 

Answer 1

当29被选为p或q，z有28的一个因素，因此k = 7是不的欧拉作为您的评论的权利要求相对黄金！

（这意味着j*k % z始终是7的倍数，所以你的循环永远不会终止。）