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
ちゃんと復号されて元の文に戻った
暗号分野はあまり勉強してないけど、たまにやってみるとすごく面白い
それにしても暗号アルゴリズムを考える人はすげえなあ、、、