/** 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]