# 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.
Please show your computations.

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,
- Encode the message m = 8.
- 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?

This page has been created and is maintained by Elena Machkasova

Comments and suggestions are welcome at emachkas@wellesley.edu

Spring Semester 2002