Suppose you know that Alice’s RSA public key is the pair (5, 65). a. What is the corresponding private key? b. Suppose that you want to send Alice the plaintext p = 3. What is the result

CKDF120 - Assignment 2

Due date: March 26, 2021 (End of Week 9)

Name: ________________Jasmyn Garrido5_____________________

Question 1: RSA using CrypTool (2.5 points)

Before implementing the RSA cipher with an example data, we shall first demonstrate its workings using CrypTool. The demonstration material can be accessed through

Indiv. Procedures > RSA Cryptosystem > RSA Demonstration…

or

Encrypt/Decrypt > Asymmetric > RSA Demonstration…

This presents a window with a series of options. Make sure that the radius option of using p and q is elected, not the N and e option.

Next, we will enter some prime numbers for p and q ((Please refer to Module 3 for an understanding of the RSA steps, including the meanings of p and q). As thinking of large prime numbers can be a daunting task, the CrypTool has included a prime number generator; this can be accessed by clicking the button Generate prime numbers… Here make sure that the option for independent values is selected. For the lower value of each, we can use 500, and for the upper value, 1000. It is worth mentioning that these limits may also be entered in the form binary length, using the notation 2x where x is the number binary bits used to represent a number.

Once all that has been completed click Generate prime numbers, and prime numbers will be generated, this may be clicked several times to generate different prime numbers. Select Apply primes and these will be entered as the values for p and q. The values for n and β(n) will be automatically calculated. Now enter a value for e, this should be coprime to β(n), if in doubt use a known prime number such as 13. Select the input type as text, and enter the message (plaintext) M that you wish to encrypt (a word or phrase), and then select Encrypt.

1. Copy the obtained encrypted numbers in the above examples.

Note that your encrypted values will likely vary. Change the input type to numbers, and paste these numbers into the message input box (remember to include the separators, #). Select Decrypt and you should see your original message deciphered.

1. Encrypt a message of your choice using the values:

p = 59

q = 71

e = 13

1. Observe the results obtained and comment (vague or ambiguous answer will not be accepted)

What I have observed was how many numbers before # sign split them up. For example, in 1a) there are groups of six before the # splits the next group. For 1b) they are grouped in four before the # breaks it up. Also, I think in 1b) the amount of numbers grouped together is a lot more then in 1a). I am not sure it is because I have more words in the second plaintext message then I do the first one.

1. Encrypt the same message as above with the values:

p = 673

q = 619

e = 13

1. Observe the results obtained and comment (vague or ambiguous answer will not be accepted)

I noticed that with these new values the amount of numbers have changed again. For example, with 1b) there was only four number within each group and in 1d) is changed to six numbers within a group.

Note: For Questions 2 through 4, you are requested to show all the steps followed by displaying the content of the working area window of CrypTool (wherever applicable) in order to justify the answers that you provide. Also, be precise on all your answers; vague answers will not be accepted).

Question 2: (1 point)

Suppose you know that Alice’s RSA public key is the pair (5, 65).

1. What is the corresponding private key?

1. Suppose that you want to send Alice the plaintext p = 3. What is the resulting ciphertext, c, of encrypting this plaintext using Alice’s public key?

Question 3: RSA Implementation (2 points)

Next, we will encrypt a message using PKI (Public key infrastructure). PKI includes the user’s details in the encryption process as a form of authentication.

Scenario 1: Start by selecting Digital Signatures/PKI > PKI > Generate/Import Keys… This is where you can create a pair of asymmetric keys, one public and one private, using the user details to do so. Here you may choose from three ciphers, RSA, DSA and Elliptic curve. First select RSA. Also, select a bit size of 512. Next, enter the user details requested on the right. Once all this has been done select Generate new key pair… At this point, you may be required to move the mouse so that the system has some data to generate a random input.

Select Apply. You have just generated an asymmetric key pair. To view this key and any other asymmetric keys that have been generated select Digital Signatures/PKI > PKI > Key Display/Export Keys… This can also be used to view the details of each key and to delete them if needed.

Now that an asymmetric key pair is available, you can encrypt/decrypt the data using the RSA cipher. Open a new text file with the CrypTool and enter some text you wish to encipher. Select Encrypt/ Decrypt > Asymmetric > RSA Encryption… Select the line with your newly created key and then press Encrypt. The encrypted form of the text should appear.

Repeat the same steps as in Scenario 1, but this time, using DSA as cipher, along with the SAME plaintext.

1. Analyze the data encrypted with the RSA cipher. How does this encryption method compare to the DSA method? Justify your answer (vague or ambiguous answer will not be accepted)

Make sure that the encrypted data window is active, and then select

Encrypt/Decrypt > Asymmetric > RSA Decryption… Select your key and PIN, then press Decrypt

Your message should be displayed but will likely have all the HEX representations shown as well. To remove the hexadecimal representation and display the message in a more human legible way, select View > Show as Text, and should you wish to revert to the hexadecimal view select View > Show as HexDump.

1. Write your result of the decryption operation

Hybrid encryption

Now, we will examine a hybrid cipher (called RSA-AES) which combines the aspects of both AES and RSA ciphers.

To encrypt a message with it, select

Encrypt/Decrypt > Hybrid > RSA-AES Encryption… A GUI is presented.

Begin by clicking on the Generate session key button, you may be asked to move the cursor for random input. Once successfully completed, this button should turn green and the session key will be generated.

Click on the Select asymmetric key button and choose the key that you made during the above RSA encryption Scenario 1. Click on the remaining two red boxes, and select Save. You should now see your data encrypted with the hybrid cipher.

1. Write your result of the encryption operation.

To decrypt it select

Encrypt/Decrypt > Hybrid > RSA-AES Decryption…

At this dialog, select Continue, and then select the PSE (Personal Security Environment) with the appropriate private key and enter the PIN number of the PSE to open it.

Select Continue again to see the RSA private key used to encrypt the AES session key, and then press Decrypt.

1. Write your result of the decryption operation

Question 4: (4.5 points)

The RSA encryption algorithm works with numbers. As your task is to encrypt some textual messages, we obviously need a method for coding of a message into numbers. We next describe one such a method that is used in CrypTool. The method is called b-adic (where b is the number of plaintext elements) and works as follows. Suppose that the plaintext alphabet consists the following elements:

<space>ABCDEFGHIJKLMNOPQRSTUVWXYZ

that is, there are in total 27 different plaintext elements. Next, the alphabet elements are coded as follows:

<space> => 0

A => 1

B => 2

...

Z => 26

Depending on the bit length of the RSA modulus N and the selected alphabet, in CrypTool you can adjust the block length used with RSA encryption. Now, assume that we want to encrypt plaintext: MARIO. Assuming that we want to work with block of length 2, we obtain the following blocks:

MA#RI#O<space>

Encoding this with the above code, we obtain:

13 01 # 18 09 # 15 00

Finally, b-adic, that is, 27-adic coding of a numerical representation of the message is

obtained according to the following formula:

<letter 1> × 27 + <letter 2>

By applying this formula to the numerical representation of our message, we finally obtain:

352 # 495 # 405

It is this sequence of numbers that is encrypted into ciphertext (in the “block-by-block”

fashion).

1. (1 point) You are asked to encrypt your name using RSA with a small modulus N (that

is, N < 100000). Choose N such that the length of the resulting RSA modulus N allows

you to work with blocks of length 2. Use CrypTool to accomplish this as follows :

Fig. 1: CrypTool: The RSA encryption

• In the main menu, under “Crypt/Decrypt” select “Asymmetric => RSA Demonstration...” to open “The RSA Cryptosystem” window (Figure 1 (left)).

• Click on button “Options for alphabet and numeric system...” to open “Options for RSA Encryption” (Figure 1)(right).

• In the “Options...” window, in tab “Alphabet options” check “Specify alphabet:”, in tab “RSA variant” check “Normal”, in tab “Method for coding a block into numbers” check “b-adic”, set the block length to 2, and finally choose the “Decimal” number system. Click the “OK” button to save the settings.

1. (2.5 points) Show that CrypTool RSA encryption works by encrypting the first block of the message “manually”. You are allowed to use only multiplication and squaring operations (and of course your calculator). In order to make this process manageable, use “reduction by modulo” property, that is,

(a × b) mod N = (a mod N) × (b mod N) mod N .

Provide the steps of your calculation.

1. (1 point) After decryption of a given ciphertext, we have to decode the result back to its initial plaintext representation. How would you do this? Manually decode 354 into a plaintext alphabet <space>ABCDEFGHIJKLMNOPQRSTUVWXYZ, assuming the block length of 2 and 27-adic coding.

9