# RSA.frink

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

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 19030 days, 13 hours, 55 minutes ago.