Class: Cryptify::Rsa

Inherits:
Object
  • Object
show all
Defined in:
lib/cryptify.rb

Overview

RSA implementation class.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Rsa

Construtor.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# 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

Instance Method Details

#decrypt(encrypted_message) ⇒ Object

Decrypt message.



75
76
77
78
79
80
 
# 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) ⇒ Object

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



107
108
109
110
111
112
113
114
115
116
 
# 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) ⇒ Object

Encrypt a message.



62
63
64
65
66
67
68
69
 
# 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) ⇒ Object

Checks whether a and b are coprime.



86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# 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) ⇒ Object

Modular inverse.



121
122
123
124
 
# File 'lib/cryptify.rb', line 121

def modinv(a, m)
  g, x, y = self.egcd(a, m)
  return g != 1 ? nil : x % m
end