isaaclyman · February 7, 2025 18:37 · Feb 7, 2025 · Feb 7, 2025 · Feb 7, 2025
diff --git a/rsa_crypto.rb b/rsa_crypto.rb
@@ -8,14 +8,16 @@ def encrypt(message, exponent, modulus)
 
     def decrypt(message, exponent, modulus)
       message.chars.each_slice(modulus.to_s.size).map do |arr|
-        (arr.join.to_i ** exponent) % modulus
+        # Equivalent to `(arr.join.to_i ** exponent) % modulus`, but WAY faster
+        arr.join.to_i.pow(exponent, modulus)
       end.pack('c*')
     end
 
     private
 
     def crypt_byte(byte, exponent, modulus)
-      crypted = ((byte.to_i ** exponent) % modulus).to_s
+      # Equivalent to `crypted = ((byte.to_i ** exponent) % modulus).to_s`
+      crypted = byte.to_i.pow(exponent, modulus).to_s
       missing_chars = modulus.to_s.size - crypted.size
       '0' * missing_chars + crypted
     end

diff --git a/rsa_crypto_spec.rb b/rsa_crypto_spec.rb
@@ -1,5 +1,4 @@
 # frozen_string_literal: true
-# Note: This test suite takes a long time to run.
 
 require_relative '../rsa_keygen'
 require_relative '../rsa_crypto'
@@ -41,7 +40,7 @@
   end
 
   context 'with generated key pairs' do
-    primes = [757, 1033, 1609, 2243, 2383, 3209]
+    primes = [757, 1033, 1609, 2243, 2383, 3209, 5867, 7121, 7877]
 
     primes.permutation(2).each do |arr|
       context "with primes [#{arr[0]}, #{arr[1]}]" do

diff --git a/rsa_crypto_spec.rb b/rsa_crypto_spec.rb
@@ -41,7 +41,7 @@
   end
 
   context 'with generated key pairs' do
-    primes = [757, 1033, 1609, 2243, 2383, 3209, 4027, 5417]
+    primes = [757, 1033, 1609, 2243, 2383, 3209]
 
     primes.permutation(2).each do |arr|
       context "with primes [#{arr[0]}, #{arr[1]}]" do

diff --git a/rsa_keygen.rb b/rsa_keygen.rb
@@ -20,7 +20,7 @@ def public_key
 
   private
 
-  attr_accessor :prime_p, :prime_q, :modulus_n
+  attr_accessor :prime_p, :prime_q
 
   def modulus_n
     @modulus_n ||= prime_p * prime_q

diff --git a/Gemfile b/Gemfile
@@ -0,0 +1,5 @@
+source 'https://rubygems.org'
+ruby '3.3.4'
+
+gem 'prime'
+gem 'rspec'
diff --git a/rsa_crypto.rb b/rsa_crypto.rb
@@ -0,0 +1,23 @@
+# frozen_string_literal: true
+
+class RSACrypto
+  class << self
+    def encrypt(message, exponent, modulus)
+      message.bytes.map { |b| crypt_byte(b, exponent, modulus) }.join
+    end
+
+    def decrypt(message, exponent, modulus)
+      message.chars.each_slice(modulus.to_s.size).map do |arr|
+        (arr.join.to_i ** exponent) % modulus
+      end.pack('c*')
+    end
+
+    private
+
+    def crypt_byte(byte, exponent, modulus)
+      crypted = ((byte.to_i ** exponent) % modulus).to_s
+      missing_chars = modulus.to_s.size - crypted.size
+      '0' * missing_chars + crypted
+    end
+  end
+end
diff --git a/rsa_crypto_spec.rb b/rsa_crypto_spec.rb
@@ -0,0 +1,57 @@
+# frozen_string_literal: true
+# Note: This test suite takes a long time to run.
+
+require_relative '../rsa_keygen'
+require_relative '../rsa_crypto'
+
+describe RSACrypto do
+  test_messages = [
+    '0',
+    'TEST_MESSAGE',
+    'MY NAME IS FRED',
+    '23iorfanv84809293nioafnkl'
+  ]
+
+  shared_examples :encrypts_decrypts_messages do
+    test_messages.each do |message|
+      it "private-encrypts and public-decrypts '#{message}'" do
+        encrypted = RSACrypto.encrypt(message, private_key_exponent, shared_modulus)
+        expect(encrypted).not_to eq(message)
+
+        decrypted = RSACrypto.decrypt(encrypted, public_key_exponent, shared_modulus)
+        expect(decrypted).to eq(message)
+      end
+
+      it "public-encrypts and private-decrypts '#{message}'" do
+        encrypted = RSACrypto.encrypt(message, public_key_exponent, shared_modulus)
+        expect(encrypted).not_to eq(message)
+
+        decrypted = RSACrypto.decrypt(encrypted, private_key_exponent, shared_modulus)
+        expect(decrypted).to eq(message)
+      end
+    end
+  end
+
+  context 'with a known good RSA key pair' do
+    let(:shared_modulus) { 25777 }
+    let(:private_key_exponent) { 3 }
+    let(:public_key_exponent) { 16971 }
+
+    include_examples :encrypts_decrypts_messages
+  end
+
+  context 'with generated key pairs' do
+    primes = [757, 1033, 1609, 2243, 2383, 3209, 4027, 5417]
+
+    primes.permutation(2).each do |arr|
+      context "with primes [#{arr[0]}, #{arr[1]}]" do
+        let!(:keys) { RSAKeygen.new(arr[0], arr[1]) }
+        let(:shared_modulus) { keys.public_key[1] }
+        let(:private_key_exponent) { keys.private_key[0] }
+        let(:public_key_exponent) { keys.public_key[0] }
+
+        include_examples :encrypts_decrypts_messages
+      end
+    end
+  end
+end
diff --git a/rsa_keygen.rb b/rsa_keygen.rb
@@ -0,0 +1,56 @@
+# frozen_string_literal: true
+
+require 'prime'
+
+class RSAKeygen
+  def initialize(prime_p, prime_q)
+    raise 'Both p and q must be prime' unless prime_p.prime? && prime_q.prime?
+
+    @prime_p = prime_p
+    @prime_q = prime_q
+  end
+
+  def private_key
+    @private_key ||= [private_exponent_d, modulus_n]
+  end
+
+  def public_key
+    @public_key ||= [public_exponent_e, modulus_n]
+  end
+
+  private
+
+  attr_accessor :prime_p, :prime_q, :modulus_n
+
+  def modulus_n
+    @modulus_n ||= prime_p * prime_q
+  end
+
+  def totient
+    @totient ||= (prime_p - 1).lcm(prime_q - 1)
+  end
+
+  def public_exponent_e
+    @public_exponent_e ||= 3.upto(totient).find do |attempt|
+      attempt.prime? && totient % attempt != 0
+    end
+  end
+
+  def modular_multiplicative_inverse(a, m)
+    raise "#{a} and #{m} are not coprime" unless a.gcd(m) == 1
+    return m if m == 1
+
+    m0, inv, x0 = m, 1, 0
+    while a > 1
+      inv -= (a / m) * x0
+      a, m = m, a % m
+      inv, x0 = x0, inv
+    end
+    inv += m0 if inv < 0
+    inv
+  end
+
+  def private_exponent_d
+    @private_exponent_d ||= modular_multiplicative_inverse(public_exponent_e, totient)
+  end
+end