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.
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
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.
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'
Do You Want to Know a Secret?, John Lennon and Paul McCartney
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.
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.
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))
Kooks, David Bowie
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.
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)
The value above resulted from the fist try! Let's just double-check:
r=84702430274642621186558361479907208126536215430888351611763113302053668759376518966574603201810531886301918785137891516381481460563722248458623633033117567487261216931156488628528561268316437765031590235973463993733552958965089383663795852205431573480872177279353787007855990277856866386711714548893140166850
print pow(r,2,modulus)
OK, so we've got our nontrivial square root. Let's use it to factor the modulus.
import mrpt
v=mrpt.extended_euclid(r-1,modulus)
p=v[0]
print p
q=modulus/p
print q
Now that we have the factorization, we can compute the decryption exponent for Alicia.
m=(p-1)*(q-1)
d2=mrpt.modinverse(3,m)
print d2
Finally, let's perform the decryption and convert it to ASCII.
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
It's All About the Pentiums, Weird Al Yankovic
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.
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))
Let's Do It (Let's Fall in Love), Cole Porter
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.
N=44942328371557897693232629769725618340449424473557664318357520289433168951375257965482422556404457451718583809223835908839177304881817776122373012546300858156599365147254125813646902409581676334412474588981831055885482882035536045011307598963087362918606041763675201773971544892845603922900169970837338793663
A=find_root(2,N)
x=find_root(2,A*A-N)
print x*x==A*A-N
So we win. Let's compute the factors and complete the decryption.
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
What's the Ugliest Part of your Body?, Frank Zappa.
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...
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'
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.
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
The plaintext is just the product of the two matched values, which we translate to ASCII.
bytes_to_ascii(long_to_bytes(m1*m2))
It sounds like the title of a TV police drama, but it's just our new 4-letter department prefix.