我编写了下面的 ruby 脚本来帮助我的学生理解公钥加密。我遵循此处显示的“铅笔和纸”方法:http://sergematovic.tripod.com/rsa1.html
只要没有选择 29 作为 p 或 q,这就可以正常工作。如果选择了 29,它会在计算 key 时挂起。谁能告诉我这是为什么?
#!/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
最佳答案
当 p
被选为 29 时或 q
, z
有 28 作为一个因素,因此 k = 7
正如您的评论所说,不是 totient 的相对素数!
(这意味着 j*k % z
始终是 7 的倍数,因此您的循环永远不会终止。)
关于ruby - Ruby 中的公钥加密演示,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10181359/