rsa-sample.rb

require 'prime'

# ref: http://quanon.hateblo.jp/entry/2015/03/26/205949
# p, q は素数
# N = p * q
# L は p - 1 と q - 1 の最小公倍数
# 1 < E < L となり、E と L は互いに素となる任意の数
# 1 < D < L で E * D を L で割った時のあまりが1となる任意の数

# 適当に素数を見つける
# 本当はもっと大きな素数である必要がある
p = 2311
q = 3571

n = p * q

l = (p - 1).lcm(q - 1)

# なんでもいいはずなのでsampleを使う
e = (2..l).select { |i| i.gcd(l) == 1 }.sample

# なんでもいいはずなのでsampleを使う
d = (2..l).select { |i| (e * i) % l == 1 }.sample

puts <<"EOF"
--- paramaters ---
p: #{p}
q: #{q}
n: #{n}
l: #{l}
e: #{e}
d: #{d}
公開鍵: [#{e}, #{n}]
秘密鍵: [#{d}, #{n}]
EOF

# 入力文字
print "enter text which you want to encrypto >> "
plain_text = gets.chomp

# 暗号化
plain_ints = plain_text.each_codepoint.to_a
encrypted_ints = plain_ints.map { |i|  (i ** e) % n }

puts <<"EOF"
--- encrypto ---
plain_text:     #{plain_text}
plain_ints:     [#{plain_ints.join(", ")}]
encrypted_ints: [#{encrypted_ints.join(", ")}]
EOF

# 複合化
decrypted_ints = encrypted_ints.map { |i| (i ** d) % n }
decrypted_text = decrypted_ints.map { |i| i.chr(Encoding::UTF_8) }.join

puts <<"EOF"
--- decrypto ---
decrypted_text: #{decrypted_text}
EOF

# Q 公開鍵から秘密鍵は求められるのか？
# L がわかれば、D は求められる
# L は N から算出可能 (p * q) なので
# 愚直に求めてみる

max_n = n**(1/2.0)

(2..max_n.to_i).each do |i|
  next unless (n % i) == 0
  j = n / i
  next unless i.prime? == true && j.prime? == true
  puts <<"EOF"
--- cal p and q from n --
search: 2..#{max_n.to_i}
p: #{i}, q: #{j}
EOF
  break
end