Assignment 5 Solutions to Programming Problems

Root-Finding

Several of the problems require finding integer square and cube roots. The following code uses binary search to find the ceiling of the kth root of N. When N is an exact kth power, this gives the exact root. The code is very simple, but you have to be careful about the construction of the loop. If you use 'while low < high' as the stopping condition, you're likely to get an infinite loop.

In [9]: 
def find_root(k,N):
    low=0
    high=N
    while low+1<high:
        mid=(low+high)/2
        if mid**k>=N:
            high=mid
        else:
            low=mid
    return high

Problem 1: Short Message, Small Exponent

If you know or suspect that M3 < N where M is the plaintext and N the modulus, then the plaintext is the exact cube root of the ciphertext. We can check this by first making sure that the root returned by find_root is indeed the exact cube root.

In [3]: 
from bytestuff import *
ciphertext='BOPsNWUf4Wlq0x7slBtDBKBAm8/7DZipepU3kklFB2GcurrqQNuouHpxocau3D5otveYhBw7z2AbETcKMuMkWZdToWSo92mK+UhNeP8wXNqVW7I7Fiy/'
ct=bytes_to_long(b64_to_bytes(ciphertext))
pt=find_root(3,ct)
if pt**3==ct:
    print 'perfect cube'
    print bytes_to_ascii(long_to_bytes(pt))
else:
    print 'not perfect cube'

perfect cube
Do you want to know a secret?

Do You Want to Know a Secret?, John Lennon and Paul McCartney

Problem 2: Small Exponent

We convert the three ciphertexts to numbers, and then use the Chinese Remainder Theorem to find the unique value less than the product of the three moduli congruent to each of the ciphertexts. The code below gives the CRT solution.

In [5]: 
import mrpt
def crt(values,moduli):
    numvalues=len(values)
    modproduct=1
    for modulus in moduli:
        modproduct *= modulus
    partial_products=[modproduct/modulus for modulus in moduli]
    inverses = [mrpt.modinverse(partial_products[i],moduli[i]) for i in range(numvalues)]
    summands=[values[i]*partial_products[i]*inverses[i] for i in range(numvalues)]
    return sum(summands)%modproduct

Let's apply this to the given ciphertext and moduli.

In [7]: 
ciphertext1=bytes_to_long(b64_to_bytes('PBq5gXUhUHA9odbER2Oow3aBRX5VzEPPRCPdcFPZisJSDtoDQtCGiDdcD4q5qNWtA7dMRZxktHzO1kQy1HNmgg6jjUnxuXPIihJgTG4rAQaAFVJrj9THVoaNb+QxovCU61c7N49H+tekr6xyGyGSok6wNnLZtE0GQd8p3zbyIAg='))
ciphertext2=bytes_to_long(b64_to_bytes('a11Wynb/5BbzR2+gfZ5vgyJvlk0VHAUP08F2tvEZKCsS4Q0zaHok9FBf3QSJxn7X+e9+bADoV0aycZpXh/8hchNE5jER156vamjQm/9cmLwVcQeK/IFJOOmvuFEWYwOg3L8r2Jsii6cn/XrStNZ4JypnOhzbyhR5Jd8hsC2pPIo='))
ciphertext3=bytes_to_long(b64_to_bytes('HlPEAzFjvc1ipxHIaig2o6WwpHfsHmIuS07lM0uKmY0VzcxyiOyB8Q0f4yjo8mu5yPYteO5Kiz5W3sk2j/d5ClmU7yUOVRxm5Q8LXymjpkhLK/I+cxO5P3WRjXF6tUiS/7cz+Koox/r1zC0W4BdfCzr3LSjM/khFHyRyxsmW9Ec='))
N1=116352696909960426025864851693810318405618117771451092066454825684677043175680039111752172705287741166921435658711582887107841565748470707915492808066623281928343866378761016071751094691691153177015920723800541267192488702040046723176890027878282090184778778793686252497241689941158021804171328580092708776333
N2=113159069239053057823530426012762733579195323934158077138440185385412667833688850511263203419882218256057634130377557866771685834979020529147973323837633935391154851580497106210797073916815264166772985134768913514820393183935763151959349642321950865577799563213986693573189083682991881468336071564883866833467
N3=84645091220488904665996303582605230466879862527671219768265030555132951506114250139685118956675414529710122137796339176130460114790081203074349445462593477716603703644138088562638660083014885373629701703614641595720381677601897924624948376232277832479665238039958287396790532376148968417689500200999461168369
x=crt([ciphertext1,ciphertext2,ciphertext3],[N1,N2,N3])
M=find_root(3,x)
#check for exact cube root
print M**3==x
print bytes_to_ascii(long_to_bytes(M))

True
If the homework brings you down, then we'll throw it on the fire and take the car downtown

Kooks, David Bowie

Problem 3. Common Modulus

We use the given (e,d) pair to factor the modulus. The technique is to choose a random 1< a < n , initially set k=ed-1 and then repeatedly divide k by 2 until either k is odd, or ak mod n is different from 1. With luck, this will give us a square root of 1 mod n that is different from 1 and -1. Otherwise we start over with a new a. The code below was executed repeatedly until the desired result was obtained.

In [1]: 
import random
modulus = 118655596447903224963869613053944974689306948978385022351313547236325408711597515968013120482999812623684614237188826586513936280546323473924322265897469916282911780567243884859836121621708694140679468147474220271417145483116948895892297437839699778114403528270801117190611396069302409336194794071895031049811
e=5
d=23731119289580644992773922610788994937861389795677004470262709447265081742319503193602624096599962524736922847437765317302787256109264694784864453179493978848181776281125630457673065339633910037899644296946114786385008468034547208885433370715974640426127989454209067113013826578800440508863151210816724921125
a=random.randint(1,modulus-1)
k=e*d-1
while pow(a,k,modulus)== 1 and k%2==0:
    k=k/2
print pow(a,k,modulus)

84702430274642621186558361479907208126536215430888351611763113302053668759376518966574603201810531886301918785137891516381481460563722248458623633033117567487261216931156488628528561268316437765031590235973463993733552958965089383663795852205431573480872177279353787007855990277856866386711714548893140166850

The value above resulted from the fist try! Let's just double-check:

In [2]: 
r=84702430274642621186558361479907208126536215430888351611763113302053668759376518966574603201810531886301918785137891516381481460563722248458623633033117567487261216931156488628528561268316437765031590235973463993733552958965089383663795852205431573480872177279353787007855990277856866386711714548893140166850
print pow(r,2,modulus)

1

OK, so we've got our nontrivial square root. Let's use it to factor the modulus.

In [4]: 
import mrpt
v=mrpt.extended_euclid(r-1,modulus)
p=v[0]
print p
q=modulus/p
print q

9345627908020883592059183774476639067502773242191442250750611223997993367537076814402588115616274180469539920131046480649632520914167877599120349931066599
12696374991140732140512287020446900076448408004471301395588880879144950845314388316181671710959709583111459835650579061613542779292624001438897461475377589

Now that we have the factorization, we can compute the decryption exponent for Alicia.

In [5]: 
m=(p-1)*(q-1)
d2=mrpt.modinverse(3,m)
print d2

79103730965268816642579742035963316459537965985590014900875698157550272474398343978675413655333208415789742824792551057675957520364215649282881510598313262827272587603752101525576884465446366792998814323153715954616694893448490696284777902386582134753759964847363557043379421929334801696210504036055749737083

Finally, let's perform the decryption and convert it to ASCII.

In [6]: 
from bytestuff import *
ciphertext='LbJFbZa7eoMEQE8uPICTjzxFqvtM2qLPf6OSNOR6bgIJ8IlSWMMIOL4s7qevd77GRtLTz6EgC38EVjbp+ZHKJ5inX582MlxjD6WYcqGEYOnvCFGBpeFJnkAvhFIWxNyIx1tk1xxQgTHU8wMHjq/rMCl6USuZcSH4L1bzUMmgfZE='
c=bytes_to_long(b64_to_bytes(ciphertext))
pt=pow(c,d2,modulus)
plaintext=bytes_to_ascii(long_to_bytes(pt))
print plaintext

Wanna be hackers? Code crackers? Slackers wasting time with all the chatroom yakkers?

It's All About the Pentiums, Weird Al Yankovic

Problem 4. Moduli with a common factor

This one's easy. Finding a gcd of the two moduli gives us factorizations for them both, and then we can proceed to compute both decryption exponents and decrypt.

In [7]: 
N1=87750187518907655534583445808737942078016029371855217057442341331127022016930461105786023716013285380470222803872626192434912740863485532564125627646878636545449869643527771922181597178447982975143657375859594541373428795038041796818858805812228886812351199020336314262507362189851970680226889619203804537151
N2=59077605606399909603607705484000546044333045357566473814158491087439387780574866766800852465743470772146755309189078604396507686696592563062056700875467732286553829707195406383141965288479916793429869646143662227281782900822010619445408818002981548245734527538573941174294649831309213962935858200869524073603
v=mrpt.extended_euclid(N1,N2)
p=v[0]
print p
q1=N1/p
print q1
q2=N2/p
print q2
m1=(p-1)*(q1-1)
d1=mrpt.modinverse(65537,m1)
m2=(p-1)*(q2-1)
d2=mrpt.modinverse(65537,m2)
ciphertext1='Ur/BIau7ZZBdwxD8P3xDJFJGMfkJDXNU5rbY7GlvlRkGae4NEMo3pMq9r8Jk2akGSj47SZ00L+eTmeMIIfis3RoG7jjBdj03p5lLtgrLwnjP0lzr31fasl5+NVZIvmnoEt56Figi54lIAXEj4ig06MHFG2KfotLYJTnwabangS4='
ciphertext2='CPEXorDgegEqM6UttzFLaccAN/t4QB1FTDS+NL3TSofQlq3Rs/BebbNn4Qj/Vo4FmTwV3P0+n+hlIhjXzOgEgdgV3BmiBE3rIBHqUc+q0FoVvWJU1+jvFpEeellYZMX8vG7O9us5JKfDAHjPaHWZSwv++BSX4rh+5O01flxzlJA='
c1=bytes_to_long(b64_to_bytes(ciphertext1))
c2=bytes_to_long(b64_to_bytes(ciphertext2))
p1=pow(c1,d1,N1)
p2=pow(c2,d2,N2)
print bytes_to_ascii(long_to_bytes(p1))
print bytes_to_ascii(long_to_bytes(p2))

7196374956433770227547248608893896429626249406750827049349260715142230549561071493948146929280708519534606518413307850044753445115893857814651359686719641
12193665289835462899020256374089855012532917030410792896104465123403486343995909374972777802206463562802150366029242535967439035237934106479697698314377111
8209356233388422580997374265115089914115312854203339025899248239165045354360263954757711657292853273752978579859815407616488573091540460210837207761007483
In Spain the best upper sets do it, Lithuanians and Letts do it.
Some Argentines without means do it, people say in Boston even beans do it.

Let's Do It (Let's Fall in Love), Cole Porter

5. Prime Factors Close Together

We'll use the algorithm described in Written Problem 2 and our root-finding function to compute A and then x. If A2-N turns out to be a perfect square, then we win and obtain a prime factorization.

In [11]: 
N=44942328371557897693232629769725618340449424473557664318357520289433168951375257965482422556404457451718583809223835908839177304881817776122373012546300858156599365147254125813646902409581676334412474588981831055885482882035536045011307598963087362918606041763675201773971544892845603922900169970837338793663
A=find_root(2,N)
x=find_root(2,A*A-N)
print x*x==A*A-N

True

So we win. Let's compute the factors and complete the decryption.

In [12]: 
p=A-x
q=A+x
print p
print q
m=(p-1)*(q-1)
d=mrpt.modinverse(65537,m)
ciphertext='KT2TxpqVdLmfhFTBGU4u/BcnE2wjzAWeE3MyCimQkRTgYTM+SPVd8K8vmHJU/Qzw4N6V9UpHo968bZDV80ykpOT9LE1LLnhI96pDUmdEdVWANnR1vPnyc9zOXoe2y9gBK/GeLz1fF9gY8awtf6d8froMrHZHWpdjC4jdwwx75D0='
ct=bytes_to_long(b64_to_bytes(ciphertext))
pt=pow(ct,d,N)
plaintext=bytes_to_ascii(long_to_bytes(pt))
print plaintext

6703903964971298549787012499102923063739682910296196688861780721860882015036774274627050328265043172433130018153448401781094087328384234861741343429594899
6703903964971298549787012499102923063739682910296196688861780721860882015036775265204573949228308469059140518029775535989414351351931141643645143982457637
What's the ugliest part of your body? Some say your nose, some say your toes, but I think it's your mind.

What's the Ugliest Part of your Body?, Frank Zappa.

Problem 6. Small Message

We first create a dictionary of all the values m1e mod n as m1 varies from 1 to 4 million. This may take a while...

In [1]: 
from bytestuff import *
import mrpt
dictionary={}
N=104267313539010410259697196441509577894896177181353222939098975044658256653731229369696658803005865075730776171497005390040729021346385892644721558032556950267328480157757202775565554421465561098972037171123794802541382258202303916754661689619425811225128735978214662249095628369305188282273814273882601469489
ciphertext='j/pGAvf886IqKc4IN6TNPTSymwReGjUxUjB7F7r2aEk9bIuZPuRezm3wGCYBifv7u7kDcLQ9k4f/i5luqD/oFGS8PaJljrftLmlpa6hlUm8S/dU8h1tFW884ddtAoGTfZbN5vN4hNcSBGWPQHNzghDgwzNw/4IrqjGL81DckUdY='
c=bytes_to_long(b64_to_bytes(ciphertext))
e=65537
for j in range(1,4000000):
    u=pow(j,65537,N)
    if not u in dictionary:
        dictionary[u]=j
print 'done'

done

Not too bad---the dictionary was built in less than 5 minutes. Now let's compute cm2-e mod n for various m2 and hope for a match.

In [2]: 
for j in range(1,4000000):
    u=(c*mrpt.modinverse(pow(j,e,N),N))%N
    if u in dictionary:
        m1=dictionary[u]
        m2=j
        break
print m1
print m2

3572819
467

The plaintext is just the product of the two matched values, which we translate to ASCII.

In [3]: 
bytes_to_ascii(long_to_bytes(m1*m2))
Out[3]:
'csci'

It sounds like the title of a TV police drama, but it's just our new 4-letter department prefix.