/** This file is an initial attempt at demonstrating RSA encryption and
decryption. It also includes keypair generation.
This was inspired by an RSA "common factor" challenge described at:
See: http://www.loyalty.org/~schoen/rsa/
*/
/** This function generates an RSA keypair.
See: https://en.wikipedia.org/wiki/RSA_%28algorithm%29#Key_generation
Returns [n,e,d]
Public key is [n, e]
Private key is [n, d]
*/
generateKey[bits, e=65537] :=
{
// Step 1
hb = bits / 2
p = randomPrime[hb]
q = randomPrime[hb]
// Step 2
n = p*q
// Step 3
phi = (p-1)(q-1) // This is Euler's totient of n (since they're prime)
// Make sure 1 < e < phi
if e < 3 or e >= phi
{
println["Bad value of e: $e (phi was $phi)"]
return undef
}
// Step 4. At least check that the numbers are not coprime.
if gcd[e,phi] != 1
{
println["ERROR: e and phi are not coprime!"]
return undef
}
// Step 5: Find modular inverse of e
d = modInverse[e,phi]
if (d == undef)
{
println["ERROR: No modular inverse d found!"]
return undef
}
return [n, e, d]
}
/** Encrypt the message m (a number) using the public key [n,e]
See: https://en.wikipedia.org/wiki/RSA_%28algorithm%29#Encryption
THINK ABOUT: "at least nine values of m will yield a ciphertext c equal
to m, but this is very unlikely to occur in practice." Detect and handle
this case? */
encrypt[m,n,e] := modPow[m,e,n]
/** Decrypt some cryptext c (a number) using the private key [n,d]
See: https://en.wikipedia.org/wiki/RSA_%28algorithm%29#Decryption
*/
decrypt[c,n,d] := modPow[c,d,n]
/** Generate a random prime with the specified number of bits. This is done
by generating bits-1 bits, and then shifting them left and making the
lowest bit 1. This at least eliminates even numbers from being chosen
randomly. It could be done smarter, but be careful not to try to be too
smart! For example, using the nextPrime[] function in Frink to find the
next prime number after a randomly-chosen number would cause bias in the
numbers you selected. Think about why.
*/
randomPrime[bits] :=
{
n = 0
do
{
n = randomBits[bits-1] * 2 + 1
} while !isPrime[n]
return n
}
// Demonstration code for encryption/decryption (without proper padding.)
[n,e,d] = generateKey[2048]
println["Key generated."]
println["n=$n\ne=$e"]
message = "This is a test. There are many tests like it but this one is mine. \u{1f638}"
// Turn string into a number
mbytes = newJava["java.lang.String",message].getBytes["UTF-8"]
m = 0
for b = mbytes
m = m*256 + (b < 0 ? b+256 : b)
println["Unpadded message is $m"]
crypt = encrypt[m,n,e]
println["Encrypted message is $crypt"]
dec = decrypt[crypt, n, d]
println["Decrypted message is $dec"]
// Turn number back into a string
bytes = new array
while dec > 0
{
bytes.pushFirst[dec mod 256]
dec = dec div 256
}
println["Recovered bytes: "]
println[bytes]
a = newJava["java.lang.String", [bytes, "UTF-8"]]
println["Recovered message: "]
println[a.toString[]]
//println[factor[crypt]]