RubyでRSAの実装をしてみる

先週から約1週間ずっと風邪をひいていて何もできていなかったのでウォームアップ的な感じで書いていく

RSAとは

RSAとは公開鍵暗号方式の一つであり、大きな素数素因数分解の難しさを安全性の根拠にしている。

暗号化と復号化は以下の式で表すことができる

暗号文 = 平文 ** E mod N  
平文 = 暗号文 ** D mod N

pとqを任意の素数、Lを(p - 1)と(q - 1)の最小公倍数とするとN,E,Dは以下で表すことができる

Nはpとqの積  
EはLとの最大公約数が1である素数(1 < E < L)  
DはEとの積の余りが1となる整数(1 < D <L)

実装

class RSA
  class << self

    def encrypt(plain_text, e, n)
      encrypted_data = plain_text.codepoints
      encrypted_data.map {|i| i ** e % n}
    end

    def decrypt(encrypted_text, d, n)
      decrypted_data = encrypted_text.map {|i| i ** d % n}
      decrypted_data.map {|i| i.chr(Encoding::UTF_8)}.join
    end

    def gen_prime(seq)
      loop do
        sample = seq.sample
        return sample if is_prime?(sample)
      end
    end
  end
  private

  def self.is_prime?(x)
    for i in 2...x
      return false if x % i == 0
    end
    true
  end
end

まずは2つの素数p,qを生成する
本来だと大きい素数のほうがいいが検証なので範囲を絞って素数を決定

seq = (1000..3000).to_a
p   = RSA.gen_prime(seq)
q   = RSA.gen_prime(seq)

次にN,L,E,Dを求めいていく

n = p * q
l = (p - 1).lcm(q - 1)
e = (2...l).find {|i| i.gcd(l) == 1}
d = (2...l).find {|i| (e * i) % l == 1}

これで暗号化と復号化に必要な要素が手に入った
実際に公開鍵であるE,Nを使って平文を暗号化してみる

plain_text = "Hello World"
encrypted_data = RSA.encrypt(plain_text, e, n)
p encrypted_data
-> [1303611, 1095333, 1510258, 1510258, 791038, 1417401, 854783, 791038, 642503, 1510258, 485707] 

暗号化された
最後に暗号化されたものを秘密鍵を使って復号してみる

puts RSA.decrypt(encrypted_data, d, n)
-> Hello World

ちゃんと復号されて元の文に戻った

暗号分野はあまり勉強してないけど、たまにやってみるとすごく面白い
それにしても暗号アルゴリズムを考える人はすげえなあ、、、