DUE-2016-05-27.sagews

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 = next_prime(10^3)
q = next_prime(p)

print "========= A.1 ========="
print "p^q =", p^q
print "Last 5 digits of p^q =", 41329
print
print "========= A.2 ========="
print mod(p^q, 10^5)
print
print "========= A.3 ========="
print "Digits in p^q:", len((p^q).digits(10))
print
print "========= A.4 ========="
print "log_10(p^q) =", N(log(p^q, 10))

========= A.1 ========= p^q = 8744830539705623882919160591366188006057037316762924945765138359989197240906255103792204310771413750519018076685515611805693775007294447613294749949228827711959008412042541300296382333158715268188562703273045602076204292395446810037494901909321294641034241083512245232603055807379746430706498900551248828762860450726891845410274618844092532264775872538270993334357492744286963766327269277505728560569301158078201462206730312478210783604738028185270999596634175542878223605016611846850025466739596889337323399193483754438149294735175652440848388464518671295176398307140129556223855569590791121932132966422682087077668643993242671938058036208307452475376037739514982172910683111126133429439927040663465928047551264685996932785579450803107199313582558798609097932735525813047779768754143619015878005278254485142458410899584586880435931322549669702209319946217137998758782028694912702472588139634634776139538606930592090242701063696596976931497838828064414236835588055280338281397700708561036690417208865164603905197074677593044344807735406649484831205350792466110015528221826719266731256323407259244117177596470403651252354519893006930416885220734019053866898281129231645244427652372056552392051999858316932636223731602371584773564705934163365635701467261701253550279723963105028362122518873165936022500831094397872000339079760973300523950946032225690643530911739004390300804905712497498006149944700038600306975089805380325234019793938080493536612408537845294792177233599379767206158764736471876021456135906509706899415116201950048139907171528080893790224766750976041125665354875341334461063911878876055974900267905483088772245544469416271832275202321018678219685454301813688924940254584062259413768435079950889118250203522504096294826436430141031256091092794112794059434487124529979659222731059713958422847549380176266764668228107601164634767456217977548598945302620699334298298518548283168544922909635235793839667432954098495670269023245329352250036140633635381781510700531561823919748772914212080223440849007259065129348578025276536322562738112203151359344423104467930999222160231482165281673247153497038255167689259351514220029962950817786337963441056296676573220494928821783324274642068766228139229857207832807258308317299239464525088038943599720327120127164403385544975928175073174762329048903667080993177491712079599166350898920611668658159970765348086868184439592383767531648096753617517688795038166923081661851287133852262147432305098979621537961850332957755216651896219942587832094435338611011326109862845071356276366729345078805358310972430452855547979596800986278084084241187602311485799763360226338314855757204449408376815599201275678425509990118562963283216804889985564518387595907292036841466125689419260187623158393645582031295600537643017993169809203831138478041827693317553170901096187782433556873996671814430485598506466259435704714110880255658499130578058830996281178468122683295734933937737299991930137989379431188969851155372099297326204934341794635419090054909787383829220334339099942825241165994499319109306661978297841329 Last 5 digits of p^q = 41329 ========= A.2 ========= 41329 ========= A.3 ========= Digits in p^q: 3043 ========= A.4 ========= log_10(p^q) = 3042.94175139799

#Part B:
p = next_prime(10^100)
q = next_prime(p)

print "========= B.1 ========="
print "Last 5 digits:", pow(p, q, 10^5)
print
print "========= B.2 ========="
print "Number of digits:", ceil(q*log(p, 10))
print
print "========= B.3 ========="
print "Typical estimates for atoms in the universe -- way smaller than p^q."
10^80

========= B.1 ========= Last 5 digits: 73147 ========= B.2 ========= Number of digits: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000095016 ========= B.3 ========= Typical estimates for atoms in the universe -- way smaller than p^q. 100000000000000000000000000000000000000000000000000000000000000000000000000000000

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

# ANSWER (brute force)
k = ceil(sqrt(n))
for i in range(-1000,1000):
    p = k + i
    if is_prime(p) and n%p == 0:
        print "i =", i
        print "p =", p
        print "q =", n/p
        break

i = -225 p = 1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689818201 q = 1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689818651

#ANSWER
a = ceil(sqrt(n))
diff = sqrt(a^2-n)
p = a - diff
q = a + diff
p * q == n
p, q

True (1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689818201, 1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689818651)

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

#ANSWER
def crack_rsa(n, phi_n):
	R.<x> = PolynomialRing(QQ)
	f = x^2 - (n+1 -phi_n)*x + n
	return [b for b, _ in f.roots()]

crack_rsa(n, phi_n)

[68636564122675662743823714992884378001308422399791648446212449933215410614414642667938213644208420192054999687, 32929074394863498120493015492129352919164551965362339524626860511692903493094652463337824866390738191765712603]

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$

# SOLUTION
p = next_prime(158973487230591572494688767425734734677346736743673247551365849673432467246724672245245623462457265)
q1 = next_prime(4148371087431413452252472467356242824146736473467346358735783245724744133252473657567247246724631461)
q2 = next_prime(1408956133409813612456256845725734673467346713465347396494683424672467657246824625627247613743727)
print "p =", p
n1 = p * q1
n2 = p * q2
print "n1 =", n1
print "n2 =", n2
g = gcd(n1, n2)
print "q1 =", n1/g
print "q2 =", n2/g

p = 158973487230591572494688767425734734677346736743673247551365849673432467246724672245245623462457457 n1 = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917 n2 = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757 q1 = 4148371087431413452356242824146736473467346358735783245724744133252473657567247246724631781 q2 = 1408956133409813612456256845725734673467346713465347396494683424672467657246824625627247613743901

# GIVEN TO STUDENTS (Don't delete this cell, delete this comment)
n1 = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917
n2 = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757

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

628 646

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

# SOLUTION: 5.a
is_prime(p)

False

# SOLUTION: 5.b
trial_division(p)

271

trial_division(p//271)

13597

is_prime(p//271//13597)

False

len((p//271//13597).bits())

1002

s = str(p)
X = []
for i in range(len(s)):
    for d in '0123456789':
        if s[i] != d:
            t = s[:i] + d + s[i+1:]
            if t[0] != '0':
                q = ZZ(t)
                if q.is_prime():
                    X.append(q)

len(X)

4