Assignment 6 Solutions

Problem 1

Let's do a few calculations with the given data, and see what they mean.

In [5]: 
from mrpt import *
p=191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707852046983
print is_probable_prime(p)
q=(p-1)/2
print is_probable_prime(q)
g=5
print pow(5,q,p)

True
True
191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707852046982

The first two outputs show that p is prime, and that p=2q+1, where q is prime. If we take the powers of an element mod p, we know that they break into repeated copies of a cycle whose length is a divisor of p-1. The only divisors of p-1 are 1,2,q, and p-1 itself---this is where we use the fact that p is prime. If the powers of 5 broke into cycles of length 2, then we would have 25=52 mod p =1, which of course is not true. If they broke into two cycles of length q, then we would have 5q mod p = 1, but the calculation above shows this is false. The only remaining possibility is a single cycle of length p-1, so 5 is a primitive element.

Problem 2

Let's first establish the parameters for the remaining problems. We already have p and and g. It remains to set Alice's private key and public key.

In [6]: 
private_key=42694797205671621659845608467948077104282354898632405210027867058530843815065930986742716022222447350595400603633273172816767784236961837688169657044396569579700949515830214254992L
public_key=pow(g,private_key,p)

Now we take the two components of the message sent by Bob. Alice raises the first component to her private key, and multiplies the second component by the inverse of the result. Convert it all to ASCII to read the message.

In [7]: 
from bytestuff import *
alpha=73982478796308483406582889587923018499575337266536017447507799702797406257043632101045569763590982806403627704785985032506296784648293661856246199184245278019913797261546316759270
beta=1227561673735205443986782574414500194775280963876704725208507831364630528829422611287956320336912905023628854115065478249082243473610928313596901712034514819305660036543382454852
shared_key=pow(alpha,private_key,p)
message = modinverse(shared_key,p)*beta % p
print bytes_to_ascii(long_to_bytes(message))

All the world's a stage, and all its men and women merely players.

Problem 3

From the known plaintext-ciphertext pair we can deduce the shared key alphasecret, then use this with ciphertext of the second message to extract the plaintext.

In [8]: 
mess1ascii="Now my charms are all o'erthrown and what strength I have's mine own."
mess1=bytes_to_long(ascii_to_bytes(mess1ascii))
beta2=17606878671981551311137298337848994393797765223509173646178261989274226953505667592410786573428076963287971811161509360601971410344413313700739795932040261074709506491861567699546
beta3=116115839773157782821329377087409766815814624668492668098672866213651171163182813304753241741593566110843721045751605192482170477996370202802973966889697676265503034822908949368607
shared_key=beta2*modinverse(mess1,p)%p
mess2=modinverse(shared_key,p)*beta3%p
print bytes_to_ascii(long_to_bytes(mess2))

We are such stuff as dreams are made on.

Problem 4

Knowing the discrete log of alpha and the public key lets Eve compute the shared key. Combining this with beta gives the plaintext.

In [9]: 
discrete_log=138670566126823584879625861326333326312363943825621039220215583346153783336272559955521970357301302912046310782908659450758549108092918331352215751346054755216673005939933186397777
shared_key=pow(public_key,discrete_log,p)
beta4=112018886720018236580229932176683955946063514397085867696250318378121351302079624330821244744748925197792097406122146093507280201522804485024833199924734248052247065779216659451112
mess4=modinverse(shared_key,p)*beta4%p
print bytes_to_ascii(long_to_bytes(mess4))

How sharper than a serpent's tooth it is to have a thankless child.