2

学生が公開鍵暗号を理解できるように、以下の ruby​​ スクリプトを作成しました。ここに示す「鉛筆と紙」の方法に従いました: http://sergematovic.tripod.com/rsa1.html

これは、p または q として 29 が選択されていない限り問題なく機能します。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
4

1 に答える 1

6

29がpまたはとして選択された場合q、z因子として28があり、したがって、コメントが主張するように、トーティエントの互いに素でk = 7はありません。

（これj*k % zは、常に7の倍数であることを意味するため、ループが終了することはありません。）

于 2012-04-16T20:45:23.397 に答える