/* This script for GNU bc (binary calculator) illustrates the RSA algorithm
   Read the comments to understand more of it.
   I am not a cryptographer, so I cannot make any claims about the strength
   or correctness of this script. No warranty.
	
	(c) Bart Vanhauwaert, 2002
	bvh@irule.be

	This code is distributed under the GNU public license */


define euclid(a,b)
{
	auto mult,rem
	mult = a/b;
	rem = a%b;
	if (rem != 1)
	{
		tmp = euclid(b,rem);
		ll1 = l2;
		ll2 = l1 - mult*l2;
		l1 = ll1;
		l2 = ll2;
	} else {
		l1 = 1;
		l2 = -mult;
	}
}

define expmod(a,b,m)
{
	if (b == 1)
	{
		return (a%m);
	} else {
		if ( (b%2) == 0 )
		{
			return (expmod((a*a)%m,b/2,m));
		} else
		{
			return ((expmod(a,b-1,m)*a)%m);
		}
	}
}


define isprime(n)
{
	if (expmod(2,n-1,n) != 1) return (0);
	if (expmod(3,n-1,n) != 1) return (0);
	if (expmod(5,n-1,n) != 1) return (0);
	if (expmod(7,n-1,n) != 1) return (0);
	if (expmod(13,n-1,n) != 1) return (0);
	return (1)
}

define firstprime(n)
{
	for (i=n; i<n+1000; ++i)
	{
		if (isprime(i))
			return (i)
	}
	return (-1);
}

define rsa(d1,e1,n1,c1)
{
	r = expmod(c1,e1,n);
	s = expmod(r,d1,n)

	print "rsa_crypt(",c1,") = ",r,"\n"
	print "rsa_decrypt(",r,") = ",s,"\n"
}

/* everything from now on in hex */
ibase=16
obase=10
/* pick a small number for 200, it doesn't really matter */
e = firstprime(200)
/* These form the heart of the RSA algorithm.
   The strength lies in the difficulty to factor n.
	You _HAVE_ to change the values 1234567890ABCDEF and 9876543210FEDCBA
	in some random sequence AND KEEP THEM SECRET. The longer the sequences,
	the stronger the key (currently approx 128 bits). */
p = firstprime(1234567890ABCDEF)
q = firstprime(9876543210FEDCBA)
n = p*q
phin = (p-1)*(q-1)
tmp = euclid(phin,e)
d = l2
if (d<0) d = d+phin
/* Sanity check */
print "This value must be 1 (sanity check) : ",d*e % phin,"\n\n"
/* Example of the rsa algorithm on 1000 */
print "RSA parameters\n"
print "D = ",d,"\n"
print "E = ",e,"\n"
print "n = ",n,"\n\n"
print "RSA algorithm\n"
l = rsa(d,e,n,1000)
l = rsa(e,d,n,1000)