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 “

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.