Furman University



Crypto Lab 3: Asymmetric Cryptography

While symmetric key cryptography (everyone has the same key) is fun and easy. It proposes a lot of issues when it comes with dealing with confidentiality when dealing with people you have never met or are in able to safely and easily transfer a symmetric key to. For instance, if I want to buy a book from . 1. All my private information including credit card information NEEDS to be secure or I will not do business with you. 2. I do not have time to go met someone to transfer a symmetric key. 3. It’s very very hard for amazon to come up with unique, non-reusable symmetric keys for every transaction.

So what do we do? Asymmetric cryptography.

Simply put, asymmetric cryptography allows two different parties to create private and public numbers and transfer information confidentially over the Internet securely. Have you ever noticed the padlock symbol on browsers when you are on certain web sites or how some website URLs start with HTTPS rather than HTTP? That indicates that your website connection is using SSL which implements asymmetric cryptography and even that algorithm you are about to attempt to code in Python.

DISCLAIMER: If you are ever in a situation to advise business technology strategy or apart of a project which requires SSL or any cryptographic technology, NEVER NEVER NEVER advise to implement you own homebrew solution!!! If you forget everything on this lab or after the course (Which I’m sure would make Dr. Healy very sad), please remember this.

RSA Encryption

The most famous and popular asymmetric cryptographic scheme is RSA.

What follows is a straightforward mathematical description of the mechanics of RSA encryption and decryption.

1. Alice picks two giant prime numbers, p and q. The primes should be enormous, but for simplicity we assume that Alice chooses p = 17, q = 11. She must keep these numbers secret.

2. Alice multiplies them together to get another number, N. In this case N = 187. She now picks another number e, and in this case she chooses e = 7.

(e and (p - 1) x (q - 1) should be relatively prime, but this is a technicality.)

3. Alice can now publish e and N in something akin to a telephone directory. Since these two numbers are necessary for encryption, they must be available to anybody who might want to encrypt a message to Alice. Together these numbers are called the public key. (As well as being part of Alice’s public key, e could also be part of everybody else’s public key. However, everybody must have a different value of N, which depends on their choice of p and q.)

4. To encrypt a message, the message must first be converted into a number, M. For example, a word is changed into ASCII binary digits, and the binary digits can be considered as a decimal number. M is then encrypted to give the ciphertext, C, according to the formula

C = Me (mod N)

5. Imagine that Bob wants to send Alice a simple kiss: just the letter X. In ASCII this is represented by 1011000, which is equivalent to 88 in decimal. So, M = 88.

6. To encrypt this message, Bob begins by looking up Alice’s public key, and discovers that N = 187 and e = 7. This provides him with the encryption formula required to encrypt messages to Alice. With M = 88, the formula gives

C = 887 (mod 187)

7. Working this out directly on a calculator is not straightforward, because the display cannot cope with such large numbers. However, there is a neat trick for calculating exponentials in modular arithmetic. We know that, since 7 = 4 + 2 + 1,

887 (mod 187) = [884 (mod 187) x 882 (mod 187) x 881 (mod 187)] (mod 187)

881 = 88 = 88 (mod 187)

882 = 7,744 = 77 (mod 187)

884 = 59,969,536 = 132 (mod 187)

887 = 884 x 882 x 881 = 88 x 77 x 132 = 894,432 = 11 (mod 187)

Bob now sends the ciphertext, C = 11, to Alice.

8. We know that exponentials in modular arithmetic are one-way functions, so it is very difficult to work backward from C = 11 and recover the original message, M. Hence, Eve cannot decipher the message.

9. However, Alice can decipher the message because she has some special information: she knows the values of p and q. She calculates a special number, d, the decryption key, otherwise known as her private key. The number d is calculated according to the following formula

e x d = 1 (mod (p-1) x (q-1))

7 x d = 1(mod 16 x 10)

7 x d = 1 (mod 160)

d = 23

(Deducing the value of d is not straightforward, but a technique known as Euclid’s algorithm allows Alice to find d quickly and easily.)

10. To decrypt the message, Alice must simply use the following formula,

M = Cd mod(N)

M = Cd mod(187)

M = 1123 mod(187)

M = [111 mod (187) x 112 mod (187) x 114 mod (187) x 1116 mod (187)] (mod 187)

M = 11 x 121 x 55 x 154 (mod 187)

M = 88 = X in ASCII

Rivest, Shamir, and Adleman had created a special one-way function, one that could be reversed only by someone with access to privileged information, namely the values of p and q. Each function can be personalized bu choosing p and q, which multiply together to give N. The function allows everybody to encrypt messages to a particular person by using that person’s choice of N, but only the intended recipient can decrypt the message because the recipient is the only person who knows p and q, and hence the only person who knows the decryption key, d.

Now it’s time to attempt implementing the RSA algorithm in Python. Fortunately a lot of the housekeeping code (key generation, checks to see if numbers are prime) is already done for you.

Please navigate to the class Website or OUT folder on the CS domain and save the RSA.py file to your flash drive in a new folder called “RSALab”

Before you freak out and second guess staying in this class, you only have to add about 5-10 lines of code. EVERYTHING for the most part, has already been done for you! If you can understand the math and steps detailed above, then you will not have a problem with this lab and should be done very quickly.

You do not need to understand what all of the code does. You only need to understand the process of how RSA works. The code provided will help you pick your p and q and test to see if they will work for our needs. The code also helps deal with the more difficult parts of the lab.

With this said, DO NOT CHANGE ANY OF THE CODE THAT IS ALREADY IN PLACE. OTHERWISE THE APPLICATION MIGHT NOT WORK AND Dr. Healy AND THE LAB AIDE WILL BE VERY CONFUSED WHEN YOU ASK US WHY ITS NOT WORKING. DO NOT CHANGE THE CODE, UNLESS IT SAYS YOU CAN.

The parts you are suppose to add to are surrounded with comments that say “#Students start coding here” and “#students stop coding here”. Only code in between those comments.

Open the “RSA.py” file in your Python coding application.

Scroll down till you see the first block of comments indicating where you need to code the encrypt potion of the code.

For encryption, you need to set up a variable called ciphertext to hold the encrypted message. For now it will be empty.

Now let’s create a for-loop to help walk through the plaintext message so we can encrypt each character individually.

In the loop we need to convert the plaintext character to its ASCII number. To make things even easier the first line in your loop will be:

plaintextNum = ord(plaintext[i])

Next we need to start applying the RSA algorithm. First we need to apply our public key as the exponent e, onto the plaintextNum variable. We can do this by using the math.pow(x, y) function. The variable that is the base goes where x is and the exponent goes in y.

Now we need to modulos the result by the public key N.

Last we need to convert the ciphertextNumber to the ciphertext character. To make things easier there is a function to help us do that. To make matters easier the following line of code will accomplish this for you.

ciphertextChar = myformat(ciphertextNum)

This is all you need to do for encryption. Please get someone to check your work for you.

Now we need to write the code to decrypt messages.

The code that iterates through the ciphertext message has already been written for you. All you need to do is write the code that applies the decryption algorithm which is very easy and very very similar to the code you previously wrote for encryption.

First we need to apply our private exponent d to the ciphertextNum. This can be done the same way we accomplished it before with the math.pow() function. Then we need to modulus the result by the public key N.

The last step is to convert the plaintext number to its character form. This can be done with the following line of code.

plaintext = plaintext + plaintextChar

At this point, if everything was done correctly the application should work. We can now edit the plaintext message at the beginning of the code to whatever you would like. After you do this, run the code and in the interactive window you should see the values for p,q,N,e,d, the ciphertext message and the decrypted text message printed. If the decrypted message is the same as your plaintext message you used, then you successfully implemented the RSA algorithm

Get Dr. Healy or the Lab Aide to check your work.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download