Programming Assignment #1

CSE 452: Fall 2004

Due Date: 10/12/04

Instructions: This programming assignment is designed to develop your Scheme programming skills and to illustrate how functional programming can be used for security applications. In particular, the assignment will familiarize you with the RSA key encryption system. The deliverables for this assignment include a Scheme program called “rsa-yourlastname.scm” and an additional file that is to be produced using word processing software like MS Word that will contain information and answers to specific exercises. In addition, a “README” file should be provided if there are any special instructions that are required to run your Scheme program (i.e., other than using the “load” command in the Scheme interpreter. All files are to be handed-in using the “handin” program by midnight on the due date shown.

A partially completed skeleton program “rsa.scm” is provided for you as part of this assignment. You will be asked to code four functions within this program and to use the completed RSA implementation to perform various encryption, decryption, and verification tasks.

RSA Background:

The RSA cryptography system was developed by Ronald Rivest, Adi Shmir, and Leonard Adelman of MIT, based upon the work of Whitfield Diffie and Martin Hellman of StanfordUniversity. In general, the RSA system works by applying a set of mathematical functions to convert blocks of characters into integers. RSA is a “public-private” key system. Conceptually, an individual uses RSA to generate a key pair containing a private key and a public key. The public key is made widely available but the private key is kept securely by the user. When someone wants to send an RSA encrypted message, they utilize the recipients public key to encode. The recipient then uses his/her private key to decode the message.

RSA also permits the use of “digital signatures” – a method of verifying the identity of the person who sent you the encrypted message. In general, encrypted messages are digitally signed by compressing the encrypted message with a publicly disseminated hash compression function that reduces the encrypted block of integers into a single number. This hashing produces an unencrypted signature that is then encrypted using the sender’s private key to form the encrypted signature for the message. To verify the signature, the recipient compresses the encrypted message with the public hash function to yield what the unencrypted signature should be if it werewas actually sent by the person who is represented as the sender. The encrypted signature is then decrypted using the purported sender’s public key and compared to the unencrypted signature produced by the hashing of the encrypted message. If the two match, the message has been verified. If it does not, , then the person who signed the message did not use the private key of the purported sender.

Figure 1 provides a useful schematic depicting the encryption, decryption, and signature flow of control of the RSA cryptography system.

Figure 1: Encryption and Digital Signature

From a mathematical perspective, the RSA encryption/decryption process may be summarized as follows:

1. Select two large prime numbers, p and q and compute:
n = pq
m = (p - 1)(q - 1)

  1. Select a the number e where the gcd(e, m) = 1. Let the unencrypted message be s, such that the encrypted message R S is calculated by:
    S R= (se) mod n
  1. To decrypt, another transformation is performed using the value of n and another special number d to yield the unencrypted message s’ as follows:
    s’ = (RSd) mod n
    where the value of d has the property s = s’ for every message s, such that
    s = (se)d mod n
    it can be shown that the value of d has the property:
    de = 1 mod m
  2. Thus, the private key consists of the value pair (n, d) and the public key consists of the value pair (n, e).

There are many on-line references that go into more of the details of RSA encryption. A few of these are provided below.

- Information from the creators of RSA.

- An overview of the RSA encryption algorithm and mathematics.

- Another tutorial on RSA with some demonstration applets.

Quick-Start Guide to Scheme:

The Gnu Scheme interpreter is loaded on the CSE Linux machine “adriatic.” In order to run the interpreter, use secure shell ( SSH) to login into to “adriatic.cse.msu.edu” by logging in with using your CSE username and password.

At the command prompt, simply type “scheme” and the interpreter will start. The Scheme interpreter has it’s own series of prompts on which code may be executed directly or through which external files of Scheme code may be loaded. To load your RSA implementation, simply use (load “rsa.scm”) at the command prompt (include the parenthesis) from the directory where your file is stored. Once the file is loaded into the interpreter you may run any of the RSA functions contained within that file from the interpreter prompt. For example, to encrypt a message you might use:

(define newmsg (RSA-encrypt “Hello world.” some-public-key))
where: newmsg = variable name corresponding to the encrypted msg.
RSA-encrypt = function name that encrypts a message.
“Hello world” = first argument to the function RSA-encrypt.

some-public-key = previously defined public key for recipient and second argument to the function RSA-encrypt.

To exit Scheme type (exit) at the interpreter prompt.

Programming Exercises:

  1. A series of public and private keys have been provided for you in the file “rsa.scm.” Start by loading the file into the Scheme interpreter and enter the following commands:
    (define test-public-key1 (key-pair-private test-key-pair1))
    (define result1 (rsa-encrypt “This is a test message.” test-public-key1))
    Entering result1 at the prompt should yield:
    (209185193 793765302 124842465 169313344 117194397 237972864)
    Unfortunately, this message cannot be decoded without the function “RSA-unconvert-list” which is used by the function “RSA-decrypt.” Your first task is to complete “RSA-unconvert-list.” Hint: this function is very similar in form to the “RSA-convert-list” function.
    Test your function using:
    (define test-private-key1 (key-pair-private test-key-pair1))
    (RSA-decrypt result1 test-private-key1)
    You should get the original message with some trailing spaces. A second key pair is provided for you as well. You should define these at the prompt as follows:
    (define test-public-key2 (key-pair-public test-key-pair2))
    (define test-private-key2 (key-pair-private test-key-pair2))
    Now try your hand at encrypting and decrypting some messages. Turn-in 2 additional examples (make sure you specify which keys you used).
  1. Now complete the procedure “encrypt-and-sign” that takes a message to be encrypted and signed, the sender’s private key, and the recipient’s public key, and produces a signed message whichthat consists of two parts: the encrypted message and the digital signature. Functions are already provided in the skeleton program “rsa.scm” that you may find useful for accomplishing the objectives of the procedure “encrypt-and-sign.”
    To test out your function try:
    (define result2 (encrypt-and-sign “Test message from user 1 to user 2”
    test-private-key1 test-public-key2))
    You should get an encrypted, signed message whose message part is:
    (499609777 242153055 12244841 376031918 242988502 31156692 221535122 463709109 468341391)
    and whose signature is 15378444.
    Now encrypt-and-sign the message “I can encrypt and sign” using test-private-key2 (sender’s key) and test-public-key1 (recipient’s key) as defined above and hand in the resulting message and signature part.
  1. Your next task is to complete the procedure “authenticate-and-decrypt” which inverses the procedure “encrypt-and-sign” to produce an unencrypted message if the signature is authentic, and conversely, indicates that the message is not authentic if the signature does not validate. As a test try to authenticate and decrypt “result2” from the above exercise:
    (authenticate-and-decrypt result2 test-public-key1 test-private-key2)
    Dr. Cheng has received a message that purportedly was sent to her by Dr. Punch. The message is defined in “rsa.scm” as “mystery-course-message” with the signature defined as “received-cheng-signature.” You have been provided with a copy of Dr. Cheng’s private key and your task is to decrypt the message and authenticate whether or not it came from Dr. Punch. Turn-in the decrypted message and indicate tell whether or not it was actually signed by Dr. Punch.
    Next, Presidential candidate John Kerry has received a message define in “rsa.scm” as “received-mystery-message” with a signature “received-mystery-signature.” Decrypt this message using John Kerry’s private key (provided) and figure out who sent it. Turn in your results.
  1. For your last exercise, complete the function “solve-ax+by=1” which takes two integer arguments “a” and “b” whose GCD is assumed to be 1 and returns a pair of integers “x” and “y”. This procedure solves equations of the form ax+by = 1 and is used to generate RSA key pairs. Hint: you will find that the use of recursion is useful for completing this procedure; let a=bq+r and solve bx+ry=1 recursively.
    To demonstrate that your function works correctly, find the integers x and y that satisfy the equation:
    233987973x + 41111687y = 1
    and hand-in your results.
    In addition, use the procedure “generate-rsa-key-pair” to generate a key pair for yourself. Hand-in this key pair and show that it can be used to encrypt and decrypt messages.