Download or view RSA.frink in plain text format
/** This file is a basic demonstration of RSA encryption and
decryption. It also includes keypair generation. It does *not* include
padding of the message, which is important for security in a real-world
setting. See OAEP for information about the padding problem.
https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding
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.)
println["Generating key..."]
[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 = stringToBytes[message, "UTF-8"]
m = 0
for b = mbytes
m = m*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]
decode = bytesToString[bytes, "UTF-8"]
println["Recovered message: "]
println[decode]
Download or view RSA.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19966 days, 19 hours, 13 minutes ago.