This is an introductory article to RSA.

Inspiration

Crypto

All the code snippets of this page are live and interactive powered by the klipse plugin:

  1. Live: The code is executed in your browser
  2. Interactive: You can modify the code and it is evaluated as you type

Prime numbers

$p = 541
$q = 547
$n = $p*$q
$phi = ($p-1)*($q-1)

def gcd(u, v)
  u, v = u.abs, v.abs
  while v > 0
    u, v = v, u % v
  end
  u
end

$e = 65537
gcd($phi, $e)


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

$d = invmod($e, $phi)

$public_key = [$e, $n]
$private_key = [$d, $n]

def pow_mod (a,b,n)
  res = 1
  b.times {
    res = res * a % n
  }
  res
end

def encrypt(m, pub)
  e,n = pub
  pow_mod(m,e, n) 
end

encrypt(189, $public_key)

def decrypt(c, pri)
  d,n = pri
  pow_mod(c,d,n)
end

decrypt(165775,$private_key)

x = 187
decrypt(encrypt(x, $public_key),$private_key)

It works because (m**e)**d = (m**ed) = m (because e*d=1!