RSA_algorithm.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 12 January 2016
# https://github.com/trizen

# A simple example for the RSA algorithm.

require('ntheory')

var p = %S<ntheory>.random_strong_prime(2048)
var q = %S<ntheory>.random_strong_prime(2048)

var n = p*q
var phi = (p-1)*(q-1)

func gcd(u,v) {
    while (v) {
        (u, v) = (v, u % v)
    }
    return abs(u)
}

var e = 0
for (var k = 16 ; gcd(e, phi) != 1 ; ++k) {
    e = (2**k + 1)
}

func invmod (a, n) {

    var (u, w) = (1, 0)
    var (q, r) = (0, 0)

    var c = n

    while (c != 0) {
        (q, r) = divmod(a, c)
        (a, c) = (c, r)
        (u, w) = (w, u - q*w)
    }

    u += n if (u < 0)

    return u
}

var d = invmod(e, phi)

func expmod(a,b,n) {
    var c = 1
    do {
        (c *= a) %= n if b.is_odd
        (a *= a) %= n
    } while (b >>= 1)
    return c
}

var m = 123456789
var c = expmod(m, e, n)
var M = expmod(c, d, n)
say M

assert_eq(M, m)