Math 480 - Homework DUE 2016-05-27: Number Theoretic Public-Key Cryptography

Due 6pm on May 27, 2016

(Authors of this homework: John Jeng, Jonathon Lee, William Stein)

There are five problems. All problems have equal weight.

Problem 1 -- Large Exponents

Part A: Let $p$ be the next prime after $10^3$ and $q$ the next prime after $p$ .

A.1. What are the last 5 digits of $p^q$ ?
A.2. What is $p^{q}\pmod{10^5}$ ?
A.3. How many decimal digits does $p^q$ have?
A.4. What is $\log_{10}(p^q)$ ?

Part B: Let $p$ be the next prime after $10^{100}$ and $q$ the next prime after $p$ .

B.1. What are the last 5 digits of $p^q$ ?
B.2. How many decimal digits does $p^q$ have?
B.3. How does the number of decimal digits of $p^q$ compare to typical estimates for the number of atoms in the universe?

# Part A:
p =
q =
# A.1


# A.2


# A.3


# A.4

︠850adec3-e931-4b07-aab7-1881ffea4fb7︠
# Part B:
p =
q =
# B.1


# B.2


# B.3



︠4a0872de-7a85-4f2a-9c9e-3ad5fcc04cf1i︠
%md
### Problem 2 -- (Un)Friendly Primes
The following integer $n=pq$ is a product of two primes that are very close to each other.  Find $p$ and $q$.

Hint: Look up the [Fermat factorization method](https://en.wikipedia.org/wiki/Fermat%27s_factorization_method) or (really slow but it will work) compute $k = \lceil \sqrt{n}\rceil $ and use a for loop to search for a prime of $n$ that is close to $k$.

Problem 2 -- (Un)Friendly Primes

The following integer $n=pq$ is a product of two primes that are very close to each other. Find $p$ and $q$ .

Hint: Look up the Fermat factorization method or (really slow but it will work) compute $k = \lceil \sqrt{n}\rceil$ and use a for loop to search for a prime of $n$ that is close to $k$ .

# GIVEN:
n = 1589778526515925949592554996185602616583051281527497329806389286938676175550849931602819490640533993421299436233863010785836220708627819896428802655705196368985741169061589392187723374511476815445516292269023831265631925174400849066851






︠fac6f630-0734-418a-b101-29aad891ca60i︠
%md
### Problem 3 -- Good Ol' Quadratic Formula
The following integer $n=pq$ is a product of two primes:

$n = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261$

Also, $\varphi(n) = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562785111331930530840946832981377988381567455225122328078099291756141737769220473508429103166881380981562676242972$

Find $p$ and $q$.

Hint: Use the quadratic formula!  You know that $(x-p)(x-q) = x^2 - (p+q)x + pq$, you know $pq$, and you also know $\varphi(pq)=(p-1)(q-1) = pq - p - q + 1$.

Problem 3 -- Good Ol' Quadratic Formula

The following integer $n=pq$ is a product of two primes:

$n = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261$

Also, $\varphi(n) = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562785111331930530840946832981377988381567455225122328078099291756141737769220473508429103166881380981562676242972$

Find $p$ and $q$ .

Hint: Use the quadratic formula! You know that $(x-p)(x-q) = x^2 - (p+q)x + pq$ , you know $pq$ , and you also know $\varphi(pq)=(p-1)(q-1) = pq - p - q + 1$ .

# GIVEN:
n = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261

phi_n = 2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562785111331930530840946832981377988381567455225122328078099291756141737769220473508429103166881380981562676242972


︠e5158144-bfe0-4221-a938-99bc999ac8c4︠

︠74f223d7-be1a-4c85-af5d-acdaeb4e4bcb︠



︠f1abac05-9788-4bfe-9e9d-3145ce00f779i︠
%md
### Problem 4 -- Not so Random

> "We performed a large-scale study of RSA and DSA cryptographic keys in use on the Internet and discovered that significant numbers of keys are insecure due to insufficient randomness.  **We found that 5.57% of TLS hosts and 9.60% of SSH hosts share public keys in an apparently vulnerable manner...**" -- see https://factorable.net/

---

The following two integers $n_1$ and $n_2$ are RSA moduli that were randomly generated by Obama and Hillary.  It turnes out they weren't random enough in choosing $p$ and $q$, so both $n_1$ and $n_2$ ended up with the same prime $p$ (ie. $n_1 = p\cdot q_1$ and $n_2 = p\cdot q_2$). Factor both $n_1$ and $n_2$.

$n1 = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917$<br/>
$n2 = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757$

Problem 4 -- Not so Random

"We performed a large-scale study of RSA and DSA cryptographic keys in use on the Internet and discovered that significant numbers of keys are insecure due to insufficient randomness. We found that 5.57% of TLS hosts and 9.60% of SSH hosts share public keys in an apparently vulnerable manner..." -- see https://factorable.net/

The following two integers $n_1$ and $n_2$ are RSA moduli that were randomly generated by Obama and Hillary. It turnes out they weren't random enough in choosing $p$ and $q$ , so both $n_1$ and $n_2$ ended up with the same prime $p$ (ie. $n_1 = p\cdot q_1$ and $n_2 = p\cdot q_2$ ). Factor both $n_1$ and $n_2$ .

$n1 = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917$
$n2 = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757$

# GIVEN:
n1 = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917
n2 = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757

# sage will *NOT* factor these...
# len(n1.bits()) = 628
# len(n2.bits()) = 648

# You code goes here ...

Problem 5 -- "Year-old bug ruined crypto!"

The article "Socat slams backdoor, sparks thrilling whodunit -- Year-old bug ruined crypto" is about a potential backdoor in some networking software called Socat, in which "the SSL implementation uses a non-prime number as its Diffie-Hellman $p$ -parameter". See also Socat? What? (timeline of events).

Let $p=143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453$ be the Diffie-Hellman parameter actually used in socat.

5.a Use the is_prime function to show that $p$ is not prime.
5.b Use the trial_division function to find a divisor $d$ of $p$ , and let $p_2=p/d$ (in Sage, type p2=p//d or p2=ZZ(p/d) to get an integer rather than a rational number). Verify that $p_2$ is not prime.
5.c Use the trial_division function to find a divisor $d$ of $p_2$ , and let $p_3=p_2/d$ . Verify that $p_3$ is not prime.
5.d As far as I can tell searching online (e.g., here), further factoring of $p_3$ is an unsolved problem. How many binary bits does the number $p_3$ have? How does this compare to the number of bits of the current world record RSA factorization (which you can find here, by Sage developer Paul Zimmerman)?
5.e Let $X$ be the set of prime numbers $q$ that are obtained from $p$ by changing exactly one decimal digit. How many elements are in $X$ ? (Exclude changing the first digit to 0.)

# The "prime" p:
p =143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453