CS/MATH111 ASSIGNMENT 2
due Tuesday, April 29 (8AM)
0.1in Individual assignment: Problems 1 and 2.
0.1in
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.
ANSWER: If \(x\)=\(0\) (mod \(3\)),then for \(x\) to be prime \(x\) must be \(3\). If \(x\)=\(1\)(mod\(3\)), then \(x\) has to be \(4\).The this shows that the next \(x\) will be prime relative to \(3\).We can then assume \(x\)=\(2\)m+\(1\), and \(y\)=\(2\)n+\(1\) , since odd numbers can be represented as \(2\)n+\(1\) and \(2\)m+\(1\) where m and n are integers.
So the equation will be:
\(2\)n+\(1\)=(\(2\)m+\(1\))(\(2\)m+\(1\))+\(2\)
\(2\)n+\(1\)=(\(4\)m)(\(4\)m)+\(4\)m+\(1\)+\(2\)
\(2\)n+\(1\)=(\(4\)m)(\(4\)m)+\(4\)m+\(3\)
When solving for this the right hand side will be even since and odd plus and odd results in and even integer.The right hand side will be divisible by \(2\) when m does not equal \(1\) showing that \(x\) and \(y\) be both prime only when \(x\)=\(3\), When x does not equal 3 the right side will be even and divisible by 2 while the left side will be odd.
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.
ANSWER: Since n=\(77\), and it had to be composed of prime numbers p and q. p=\(11\) and q=\(7\). We know that e times x will give us \(1\) times the mod of ((p-\(1\))(q-\(1\))). Next we compute s, and t such that: \(13\)s+\(60\)t=\(1\) Using Euclidean Algorithm we find s=\(37\) and t=-\(8\). That gives us d since d=s, so d=37. Since we know n=p*q, we have n=\(77\). I used a program to figure decode the numbers. I just set up the equation: (encrypted number)^s(mod n) THE ASWER TO THE MESSAGE: Get your facts first, then you can distort them as you please. by Mark Twain.
0.1in
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.