# Problem set 3

Due Tuesday, March 12 at 1:30pm in class. Total points 65.
This is a paper-and-pencil assignment, no programming is required.

## Problem 1 (6 points)

Suppose a group of 8 people uses a symmetric algorithm to communicate messages among each other. How many different keys will be needed if we want to guarantee that each pair may communicate messages to each other that no one else in the group is able to read?

How many different keys would be need if they use public key cryptography? A pair of a public and a private key is counted as one key.

For all problems below assume the following translation of letters into numbers, digits, and punctuation marks into numbers (use only upper-case letters):

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

 0 1 2 3 4 5 6 7 8 9 * space . , ? ! : ; - ( ) % \$ @ 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

There are 50 different characters total.

## Problem 2 (20 points)

Since this problem requires long computations, you may collaborate with ONE person ON THIS PROBLEM ONLY (both parts). It would also be OK if you write a Java program to perform the computation. Please submit the program and the output in this case.

Using p = 53 and n = 7, generate a sequence of pseudo-random numbers and encode the message:

MIDWAY UPON THE JOURNEY OF OUR LIFE
I FOUND MYSELF WITHIN A FOREST DARK.

Using p = 61 and n = 20, decode the following message. We draw zero in blue (0) to distinguish it from the letter O.

,%OGIR4:(ZF-4GZC@KB;SV)WETQ\$7V1\$EMQRX*RL
Q8Z7)YM@Z2L?52YWK.WFR713701WH(ZG-7-MWE)

If the message is longer than the sequence of distinct pseudo-random numbers
(1*n) % p, ... , (n*(p-1)) % p
generated from p and n, then just continue the sequence as follows:
(n*p) % p, (n*(p+1)) % p, ....
Note that (n*p) % p is zero, and the rest of the numbers repeat the first sequence, so no additional computations are needed.

Bonus question (2 points each): what is the source of each of the verses?

## Problem 3 (14 points)

Suppose you are given a message 15 characters long which is encoded using a pseudo-random sequence method (as in the previous problem). Suppose that each of the following operations takes a unit of time:
• generate a number in a pseudo-random sequence (given p and n).
• compute a decoding of a character (given the character code, the number to add, p, and n)
How many units of time it will take you (at most) to decode the message in the following two cases:

A. You know that p = 91?

B. You know that p < 23?

Please show how you have computed the answer. You may assume that the message is in recognizible English and that you need to decode the entire message to check whether the decoding makes a sensible English phrase.

## Problem 4 (18 points)

Given RSA cryptographic system with p = 23, q = 41, e = 7, and d = 503,
1. Encode the message m = 8.
2. Decode the criptotext c = 354 (it encodes a number).
It might be helpful for you to know that the keys are the same as those used in the handout.

## Problem 5 (7 points)

A. Given two primes p = 53, q = 91, determine the other elements of an RSA system: N, e, and d. Please show how you have determined each of these numbers. For a partial credit in this problem: if you cannot determine some of the numbers, please specify what equations the number must satisfy and which numbers you have tried for these equations.

B. Which of the numbers that you have determined form the public key, and which are part of the private key?