# A gentle introduction to RSA

This is an introductory article to RSA.

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

**Live**: The code is executed in your browser**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`

!

```
```

```
```

```
```

```
```