This is an introductory article to RSA.

Inspiration 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`!

``````
``````
``````
``````
``````
``````
``````
``````