RSA.frink

View or download RSA.frink in plain text format


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



View or download 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 17651 days, 5 hours, 8 minutes ago.