MAT 331: Project 3

Project description:

Cryptography has been used for secure communication for thousands of years. The modern world simply depends on cryptography; every time you make a mobile phone call, make an electronic transaction or an online payment with a credit card, or send a secure email, encryption is vital for protecting sensitive information. In this project we are interested in the theoretical foundations of the asymmetric/symmetric key cryptosystems, and on how they can be efficiently used together to make the information exchange more secure.

Tasks:

Introduction
Browse the web and describe some areas of our everyday life for which cryptography is essential. Describe the concept of End-to-End encryption and Digital Signatures.

Mathematical explanations
Describe the mathematics behind the RSA cryptosystem and prove Euler’s Theorem. Also describe the mathematics behind Friedman’s test (Friedman’s test uses the index of coincidence of a ciphertext to calculate a probable keyword length for the Vigenère cipher).

Project overview
In this project we will use a Vigenère cipher to communicate secret information. Our alphabet will be the 26-letter English alphabet, numerically represented as integers between 0 and 25.  As always, we first need to agree on a secret keyword for the Vigenère cipher (to be used for both encoding and decoding). Each letter from the plaintext/ciphertext message will be encoded/decoded separately, using the corresponding letter from the keyword. 
We will use RSA to securely exchange the keyword. My RSA scheme will the following: 
public modulus m=2480646863865156240312764602400149650804447106891126179090516987413492462101441 
and public key e=17.

Part 1 - RSA

Your first task will be to set up your own RSA scheme. For the purpose of this project, we will assume that it is secure enough if you choose two prime numbers with exactly 40 (decimal) digits. Submit your public RSA information on Blackboard. Note: Send only the public information! 
There are tables of prime numbers available online. You can also tell Mathematica to generate a pseudo-random prime number with k digits by using the command RandomPrime[10^k]. Double check that the number generated is indeed prime by using the Boolean function PrimeQ[...].

After you complete the first step, you will receive message-signature pairs encoded with your RSA public information. Eve is also trying to get access to our private communications, so she will also try to send you fake Vigenère keywords encoded with your RSA public key. You will decode the message-signature pairs, and keep only the information for which the signature is valid, and discard the rest.

The decoded message with valid digital signature will be an integer x between 1 and your RSA modulus. You will take this integer x and convert it to base 26.  This will be our keyword for the Vigenère cipher.

For example, if the decoded message is x=190, then its base 26 representation is 78, which corresponds to the English word “HI”.

Part 2 - Vigenère

Build an interactive model in Mathematica for encoding/decoding English text messages that have been encrypted using a Vigenere cipher with keyword k. Your model should have a textbox s, in which the text to be encoded/decoded can be written, and a textbox k for the keyword. By default, these boxes should be populated with the encrypted text below, and respectively with the key that you have obtained after the RSA decoding process. For these default settings, the model should output the decoded text.

s=“KLIQEJXUULFYTECJXFRPKLOVCNLOPYBITKCSISWMLXOIRYIWDWKLIQEJXUULFYT”

Add some extra functionality to your model from part 2. We know that the Vigenère cipher is vulnerable to statistical analysis, so you will now try to make your model work even if no key is provided. If the keyword box is empty, then you will compute the index of coincidence of the ciphertext and use Friedman’s test to guess the probable keyword length. Remember that you need to have a reasonably long chunk of encrypted text for statistical analysis to work; also recall that Friedman’s test is not very accurate so it is usually used in combination with other tests (if you get 7.2 by Friedman’s test, then the keyword could easily have length 6, 7 or 8). The keyword length tells you how many Caesar ciphers were used, so you can now proceed and break each of them by using letter frequency analysis (or in the worst case scenario, by brute-force approach).

Your model should output the index of coincidence of the ciphertext and the decoded message (or a very short list with attempted decodings, including the correct one). Do not output thousands and thousands of attempted decodings! If you want to print other relevant information (like the probable keyword length), please feel free to do so.

s=””.

s=””.

Part 3 - RSA Common Modulus Problem

Does it work to break the RSA modulus m=2480646863865156240312764602400149650804447106891126179090516987413492462101441 by a brute force approach? How long does it take?

In this part, we will explore a vulnerability of the RSA system, known as the common modulus problem. Suppose that Alice and Kate use the same RSA modulus m as above, but with different encryption exponents (Subscript[e, Alice])=17 and (Subscript[e, Kate])=169. Bob wants to send the message x to both Alice and Kate. He first encrypts x using Kate’s public exponent, and sends Kate the ciphertext 249081508444719456881769789206569419957026519534551194619251016972858511647493. Then he encrypts x using Alice’s public exponent and sends the ciphertext 548038685778480218593900000000000000000 to Alice. If Eve intercepts both of the ciphertexts, explain how she can recover the plaintext without knowing either decryption exponent, then apply her method to find x.

Conclusions and references

Give some brief instructions on how your model should be tested (how to use the controls, what functionalities you have implemented, etc.).

Formulate your conclusions after testing your interactive model. Is the index of coincidence an accurate estimate for the length of the key? How secure is our communication protocol? How secure is RSA?

Don’t forget to include all relevant references.