\\RSA program by L. Finotti
\\genrsa(n) generates a triple (N,e,d) where N is a n-bit integer,
\\e is a random integer coprime with phi(N) and ed = 1 Mod phi(N).
\\the functions encrypt and decrypt then can be used for their 
\\named purpose. Sometimes the program hangs when trying to find p,q.
\\p, q are primes with (p-1)/2,(q-1)/2 also prime and suitably far apart.

{
l2(n)=ceil(log(n)/log(2))
}

{
findprime(n,m)=m=random;
	until(m>2^(n-2), m = ((m * random)+1)%(2^(n-1)));
	m = nextprime(m%(2^(n-1)));
	until(isprime(2*m +1), m = nextprime(m+2));
	2*m + 1;
}

{
genrsa(n, np, tries, e, d, p, q)=np=tries=e=d=p=q=0;
	np=round(n/2)+ceil(log(n)/2);
	p = q = 1;
	until(l2(p*q) == n,
		print("finding a ", np, " bit p"); 
		p = findprime(np);
		print("p has ", l2(p), " bits.");
		print("finding a ", n-l2(p)," bit q"); 
		q = findprime(n - l2(p));
		print("q has ", l2(q), " bits.");
		tries = 0;
	        while((l2(p*q) != n) & (tries <= 20),
	        	print("p*q has ", l2(p*q), 
	        		" bits.  finding another ", n-l2(p)," bit q");
	        	q = findprime(n-l2(p));
	        	tries = tries + 1;
	        );
	        if((tries > 20),
	        	print("I couldn't find p and q with gap ",
	        	abs(2*l2(p) - n)),
	        );
	        np = np - 1;
	);
	print("generating public key");
	e = 0;
	until(gcd(e, (p-1) * (q-1)) == 1,
		e = (2*(random*random)+1)%((p-1)*(q-1));
	);
	print("generating private key");
	d = lift(1/Mod(e, (p-1) * (q-1)));
	[p*q, e, d]
}

{
encrypt(msg, rsavector)=lift(Mod(msg, rsavector[1])^rsavector[2])
}

{
decrypt(ctext, rsavector)=lift(Mod(ctext, rsavector[1])^rsavector[3])
}