Need Help...

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. Write a program to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adleman) cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate huge integers (hundreds of digits). The built-in Java type int is only capable of dealing with 16 or 32 bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers. You will use this data type to write a client program that encrypts and decrypts messages using RSA. Note: You're starting with a blank screen. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in. Remember to thoroughly test and debug each function as you write it. 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 Stanford University. 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 senders 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 were actually sent by the person who is represented as the sender. The encrypted signature is then decrypted using the purported senders 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 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: example p = 3 , q =11 n = pq m = (p - 1)(q - 1) 2. Select a number e where the gcd(e, m) = 1. Let the unencrypted message be s, such that the encrypted message Ris calculated by: R= (se) mod n 3. 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 = (Rd) 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 4. 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. http://www.rsasecurity.com/rsalabs/ - Information from the creators of RSA. http://pajhome.org.uk/crypt/ - An overview of the RSA encryption algorithm and mathematics. http://www.princeton.edu/~matalive/VirtualClassroom/v0.1/html/lab1/lab1_8.html - Another tutorial on RSA with some demonstration applets. The RSA cryptosystem. As discussed in Class, the RSA public key cryptosystem involves three integer parameters d, e, and n that satisfy certain mathematical properties. The private key (d, n) is known only by Bob, while the public key (e, n) is published on the Internet. If Alice wants to send Bob a message (e.g., her credit card number) she encodes her message as an integer M that is between 0 and n-1. Then she computes: E(M) = Me mod n and sends the integer E(M) to Bob. As an example, if M = 2003, e = 7, d = 2563, n = 3713, then Alice computes E(M) = 20037 mod 3713 = 129,350,063,142,700,422,208,187 mod 3713 = 746. When Bob receives the encrypted communication E(M), he decrypts it by computing: M = E(M)d mod n. Continuing with the example above, Bob recovers the original message by computing: M = 7462563 mod 3713 = 2003. Write your program using the RSA Encryption / Decryption algorithm. Run your program using several input values.