RSA Key Exchange Algorithm

Posted by irevived1 on August 29, 2016

08.29.2016

RSA Key Exchange Algorithm

RSA, designed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, is one of the first practical public-key cryptosystems and is widely used for secure data transmission. It is extremely difficult to factor the product of two large prime numbers and RSA took advantage of this mathematical property and made it into an asymmetric cryptographic algorithm.

Today, I am not going to talk about the history or the background of RSA, nor the practicality of the algorithm itself. Instead, we will be talking about the pure mathematical aspects of RSA, and maybe we’ll build some Ruby methods to clarify some of the key points as well.

Before diving deep into RSA, it is very important to understand a few key concepts:

  • What is greatest common divisor.
  • What is a prime number.
  • What does it mean to be relatively prime to a number.
  • Power modular arithmetic.
  • Inverse modular arithmetic.

Greatest Common Divisor: is the largest positive integer that divides the numbers without a remainder. For Example: 18 and 12, common divisor are: 6,3,2 For Example: 18 and 12, the greatest common divisor is 6

#simple method to find the GCD using The Euclidean Algorithm
#GCD method
def gcd(a,b)
  return b if a==0
  return gcd(b%a,a)
end

Prime number: A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

To verify whether a number is prime, you only need to check from 2 to square root of that particular number. If there aren’t any within the range that can be divided with the remainder of 0, then the number is a prime.

#A simple and slow prime method to find the next prime of a number
#random prime generator
def primeGen(num)
  loop do
    if num%2==0
      num += 1
      next
    elsif num%3==0 || num%5==0
      num += 2
      next
    else
      return num if Prime.prime?(num)
      num += 1
    end
  end
end

Co-prime: This one is a little bit tricky, is two integers a and b are said to be relatively prime, mutually prime, if the only positive integer that divides both of them is 1.

For example: 1,3,5,7 are coprimes of 8. Where as 1,2,4,5,7,8 are coprimes of 9

An interesting property for prime numbers: The number of coprimes for prime numbers will be the prime number - 1 For example, [1,2,3,4] are coprimes of 5 and [1,2,3,4,5,6] are coprimes 7

#here’s a ruby method to randomly pick a coprime from a given input
def get_E(limit)
  lower = limit >> 1
  loop do
    e = rand(lower..limit)
    return e if (gcd(e,limit)==1)
  end
end

Power Modular Arithmetic: This arithmetic comes in the form of (b^e)%n, the result will always be less than n. Without the proper algorithm, this arithmetic will have the potential to overflow the variable.

#power mod method
def power_mod(base,exp,mod)
  result = 1
  while ( exp > 0 )
    ( result = (result * base) % mod ) if exp % 2 == 1
    exp = exp >> 1
    base = (base*base) % mod
  end
  return result
end

Lastly, the Inverse modular arithmetic. The Inverse modular arithmetic can be expressed by the following equation:

ax + by = gcd(a, b)

A well known method to solve the modular multiplicative inverse is to use extended Euclidean algorithm. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

We know that in RSA, we will be dealing with finding the inverse mod of two numbers that are relatively prime, in this case, the section for gcd(a,b) can be simplified to 1:

ax + by = 1

We need to find x where x is a positive number.

This method can be a little bit difficult to code so I grabbed https://rosettacode.org/ for help:

# inverse mod function obtained from https://rosettacode.org/wiki/Modular_inverse#Ruby
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end

  return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def invmod(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'The maths are broken!'
  end
  x % et
end

That took a while to explain what’s required to understand RSA.

Let’s use the methods above to demonstrate it, don’t forget to put require ‘prime’ on top of your ruby file.

In a parallel world, Alice has a password that wants to send to Bob. Bob will start to generate some numbers and will send some public keys to Alice.

#that’s the range for the random generator
range = (99999999..999999999)
p = primeGen(rand(range))
q = primeGen(rand(range))

puts "Random P: #{p}"
puts "Random Q: #{q}"

Bob will have to generate two prime numbers, called p and q, N will be the product of P and Q

n = p*q
puts "N = #{n}"

PHI is the number of coprimes in N, if p has p-1 coprimes and q has q-1 coprimes, the number of coprimes for will be (p-1)*(q-1)

phi = (p-1)*(q-1)
puts "PHI: #{phi}"

E is a number that is relatively prime to PHI

e = get_E(phi)
puts "The chosen E: #{e}"

Finally, D is the inverse mod of E and PHI.

d = invmod(e,phi)
puts "D = #{d}"

Then Bob sends the public keys to Alice, which is N and E

Alice receives N and E and proceeds to encrypt

puts "\nBob sends N and E to Alice."

Alice wants to send 12345678 to Bob.

m = 12345678
puts "Alice wants to send this message to Bob: #{m}"

Alice encrypts the password using the power mod, m^e mod N and sends the cipher message to Bob.

puts "Alice uses E and N to encrypt the message."
cipher = power_mod(m,e,n)
puts "Alice encrypts the message to: #{cipher}"

puts "\nAlice then sends her ciphered message back to Bob."

Finally, Bob receives the ciphered message and decrypts the password by using power mod again, cipher^d mod N

decipher =  power_mod(cipher,d,n)

if m == decipher
  puts "Bob decrypts the message and revealed: #{decipher}"
else
  puts "Unable to reveal the secret"
end

##############################Complete Code##############################

require 'prime'

# inverse mod function obtained from https://rosettacode.org/wiki/Modular_inverse#Ruby
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end

  return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def invmod(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'The maths are broken!'
  end
  x % et
end

#power mod method
def power_mod(base,exp,mod)
  result = 1
  while ( exp > 0 )
    ( result = (result * base) % mod ) if exp % 2 == 1
    exp = exp >> 1
    base = (base*base) % mod
  end
  return result
end

#random prime generator
def primeGen(num)
  loop do
    if num%2==0
      num += 1
      next
    elsif num%3==0 || num%5==0
      num += 2
      next
    else
      return num if Prime.prime?(num)
      num += 1
    end
  end
end

#GCD method
def gcd(a,b)
  return b if a==0
  return gcd(b%a,a)
end

#get E from PHI
def get_E(limit)
  lower = limit >> 1
  loop do
    e = rand(lower..limit)
    return e if (gcd(e,limit)==1)
  end
end

puts "This is an RSA Example"

range = (99999999..999999999)
p = primeGen(rand(range))
q = primeGen(rand(range))

puts "Random P: #{p}"
puts "Random Q: #{q}"
n = p*q
puts "N = #{n}"
phi = (p-1)*(q-1)
puts "PHI: #{phi}"
e = get_E(phi)
puts "The chosen E: #{e}"
d = invmod(e,phi)
puts "D = #{d}"

puts "\nBob sends N and E to Alice."
m = 12345678
puts "Alice wants to send thsi message to Bob: #{m}"
puts "Alice uses E and N to encrypt the message."
cipher = power_mod(m,e,n)
puts "Alice encrypts the message to: #{cipher}"

puts "\nAlice then sends her ciphered message back to Bob."
decipher =  power_mod(cipher,d,n)

if m == decipher
  puts "Bob decrypts the message and revealed: #{decipher}"
else
  puts "Unable to reveal the secret"
end

No matter how many times you run the simulation, Bob will always get the same message that Alice wants to send!

This is an RSA Example
Random P: 432751903
Random Q: 821428381
N = 355474695055959043
PHI: 355474693801778760
The chosen E: 314375684447020309
D = 207822147779699149


Bob sends N and E to Alice.
Alice wants to send thsi message to Bob: 12345678
Alice uses E and N to encrypt the message.
Alice encrypts the message to: 74798231699119844

Alice then sends her ciphered message back to Bob.
Bob decrypts the message and revealed: 12345678

Have a nice day,

-irevived1