class Cryptify::Rsa

RSA implementation class.

Public Class Methods

new() click to toggle source

Construtor.

# File lib/cryptify.rb, line 31
def initialize

        prime_list = Prime.take(100)

        # Generate p and q
        @p = prime_list.sample
        prime_list.delete(@p)
        @q = prime_list.sample

        # Compute n.
        @n = @p * @q

        # 1.3 Calculate `z`.
        @z = (@p - 1) * (@q - 1)

        # 1.4 Calculate coprime.
        @z.downto(0) do |i|
                if self.is_coprime(i, @z)
                        @e = i; break;
                end
        end

        # 1.5 Modular inverse
        @d = modinv(@e, @z)

end

Public Instance Methods

decrypt(encrypted_message) click to toggle source

Decrypt message.

# File lib/cryptify.rb, line 75
def decrypt(encrypted_message)

        # Uses his private key (n, d) to compute:
        (encrypted_message ** @d) % @n

end
egcd(a, b) click to toggle source

Returns a triple (g, x, y), such that ax + by = g = gcd(a, b). Assumes a, b >= 0, and that at least one of them is > 0. Bounds on output values: |x|, |y| < [a, b].max

# File lib/cryptify.rb, line 107
def egcd(a, b)

        if a == 0
                return [b, 0, 1]
        else
                g, y, x = egcd(b % a, a)
                return [g, x - (b / a) * y, y]
        end

end
encrypt(message) click to toggle source

Encrypt a message.

# File lib/cryptify.rb, line 62
def encrypt(message)

        # Represent the message as a positive integer.
        # message = 29

        # Compute the ciphertext c to b.
        (message ** @e) % @n
end
is_coprime(a, b) click to toggle source

Checks whether `a` and `b` are coprime.

# File lib/cryptify.rb, line 86
def is_coprime(a, b)

        # Cycle from 2 until the smaller number of a and b.
        2.upto([a, b].min) do |i|

                # If both modulus with `i` are equal to `0`
                # then, the numbers are no coprime.
                if a % i == b % i && a % i == 0
                        return false
                end
        end

        return true
end
modinv(a, m) click to toggle source

Modular inverse.

# File lib/cryptify.rb, line 121
def modinv(a, m)
        g, x, y = self.egcd(a, m)
        return g != 1 ? nil : x % m
end