# CS111 Homework Assignment 2

Problem 1: Let $$x$$ be a positive integer and $$y = x^2+2$$. Can $$x$$ and $$y$$ be both prime? The answer is yes, since for $$x=3$$ we get $$y=11$$, and both numbers are prime. Prove that this is the only value of $$x$$ for which both $$x$$ and $$y$$ are prime.

Hint: Consider cases, depending on the remainder of $$x$$ modulo $$3$$.

Solution 1:
If $$x\neq3$$, then $$x=1$$ or $$x=2$$ in $$x$$ modulo $$3$$.
$$x=1$$ and $$x=2$$ would be prime under the equation $$x^2 = 1$$ (mod $$3$$)
However, with the equation $$x^2+2$$, both $$x=1$$ and $$x=2$$ result in 0 $$x^2+2=0$$(mod $$3$$)
This means that $$3$$ evenly divides into $$x^2+2$$ for $$x=1$$ and $$x=2$$, meaning that $$y$$ is not prime for both of these terms.
Additionally, $$y\neq3$$ because the equation is only true for $$x=1$$ and $$1$$ is not a prime number.
Therefore, since for $$x=1$$ and $$x=2$$, $$y$$ is divisible by $$3$$ and $$y\neq3$$, the only case where both $$x$$ and $$y$$ can be prime is $$x=3$$

Problem 2: Alice’s RSA public key is $$P = (e,n) = (13,77)$$. Bob sends Alice the message by encoding it as follows. First he assigns numbers to characters: blank is 2, comma is 3, period is 4, then A is 5, B is 6, ..., Y is 29, and Z is 30. Then he uses RSA to encode each number separately.

Bob’s encoded message is:

 11 58 52 30 57 61 60 22 30 10 26 35 52 23 30 10 41 22 23 52 38 30 52 12 58 46 30 57 61 60 30 35 26 46 30 50 41 23 52 61 22 52 30 52 12 58 73 30 26 23 30 57 61 60 30 69 37 58 26 23 58 53 

Decode Bob’s message. Notice that you don’t have Bob’s secret key, so you need to “break" RSA to decrypt his message.

For the solution, you need to provide the following:

• Describe step by step how you arrived at the solution:

• Show how you determined $$p$$, $$q$$, $$\phi(n)$$, and $$d$$;

• Show the computation for the first number in the message.

• Give Bob’s message in plaintext. (The message is a quote. Who said it?)

• If you wrote a program, attach your code to the hard copy. If you solved it by hand, attach your scratch paper with calculations.

Solution 2:
Since $$n$$ is a product of $$p$$ and $$q$$, which are both prime numbers, we compute the prime factorization of $$n=77=7*11$$.
So, $$p=7$$ and $$q=11$$
To compute $$\phi(n)$$, we use the formula $$\phi(n)=(p-1)(q-1)$$
$$\phi(n)=(7-1)(11-1)$$
$$\phi(n)=60$$
Now, we must compute $$d$$ using the formula: $$d=e^{-1} (mod\: \phi(n))$$
$$d=13^{-1} (mod\: 60)$$
Using linear combinations, we get:
$$13(37)=1+60(8) (mod\: 60)$$
$$13*37=1 (mod\: 60)$$
$$37=13^{-1} (mod\: 60)$$
$$d=37$$

To compute $$m$$ from $$c$$, we use $$m=c^d (mod\: n)$$.
Computing the first letter, $$11^{37} (mod\: 77)$$
$$11*11^{36} (mod\: 77)$$
$$11*121^{18} (mod\: 77)$$
$$11*(44^2)^{9} (mod\: 77)$$
$$11*11^9 (mod\: 77)$$
$$11*11*11^8 (mod\: 77)$$
$$11*11*121^4 (mod\: 77)$$
$$11*11*(44^2)^2 (mod\: 77)$$
$$11*11*11^2 (mod\: 77)$$
$$11*11*44 (mod\: 77)$$
$$121*44 (mod\: 77)$$
$$44*44 (mod\: 77)$$
$$=11 (mod\: 77)$$
The first letter is $$11$$ or G.
Using the the program whose source code is attached to the back of this document, the decrypted message is:
“GET YOUR FACTS FIRST, THEN YOU CAN DISTORT THEM AS YOU PLEASE.” - Mark Twain

To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday, April 29, and turn-in a paper copy in class.