ROUGH DRAFT authorea.com/6558
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • 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.