Math 307--CS367/567 Test II (take home)

This exam is due by midnight next Tuesday.  Please turn it in electronically as a Maple worksheet, including all work, including the text
of any Maple programs you use (other than functions in my public files).  Any such Maple program you use should be your own creation.

You are welcome to ask me for clarification of instruction on any of the tasks requested.  Please look at your email from time to time, as I may send mail to
the whole class if some important question comes up about the test which I think justifies this notification.

Please do not communicate in any way with classmates (or with anyone else but me) about this exam.  If you see the exam before 2:40 pm (it's about 12:30 pm as I write this remark), it's fair game; you can start working. 
1.  

a.  Write a Maple program which will find a primitive root mod P, where P is a prime of the form 2*p*q + 1, where p and q are also primes (primes of this form are used in one of the key exchange protocols in the book).   Your program may NOT use built in functions from numtheory (it is no fair to use "primroot"; actually, my experiments suggest that primroot won't work anyway if p and q are large!).  Your
function will need to take p and q as input (since P-1 = 2*p*q is hard to factor if p and q are large).

b.  Exhibit examples of your function for large p, q, and P.  You will need to write a function to generate examples:  they are not easy to find (or at least
my experiments suggest that it takes time).  But I was able to generate large examples fairly quickly with automation:  I wrote a function doublesafeprime(x,y) which generated a pair of primes p>x, q>y such that 2*p*q+1 is also prime, which didn't take too long to run.

c.  Generate an El Gamal public key (p,alpha,beta) (where the prime p = 2*q*r+1, q and r large primes) and secret exponent a, and give
an example of encryption and decryption using this El Gamal key (you may use the functions in elgamaltest.mws for this purpose).

2.  Give a complete example of key exchange using the MTI protocol between agents U and V and the sending of a Hill cipher message from U to V
using the resulting key.  You may use the function used in class to generate the Hill cipher key from the number K generated in the MTI protocol (the function
gethillkey in diffiehellman.mws); use cryptonotes1.mws to get the Hill cipher encoding and decoding functions.

Choose the public p and alpha yourself and generate the private values a_U, a_V  and public values b_U and b_V.  You may leave out the
certificates C(U) and C(V); assume that U and V know each other's public values b_U and b_V.  Then demonstrate the key exchange, generation of
the key, and transmission of a Hill cipher message from U to V (encryption by U and decryption by V).  

Provide some narrative telling what U and V are doing at each stage.

3.  I have the following sad story to tell.  Alice's public modulus N is given below.  

Originally, she was very happy with her public key (N,e_old), but someone found her decryption exponent d_old in a drawer.  Being cryptographically
naive, she changed her exponent to e_new and carried on as before.

Write a brief note authorizing Alice's bank to withdraw all her funds and pay them to you and sign it as Alice using the RSA signature protocol.  (To do this, you will of course need to break her new public key (N,e_new); show any programs you use for this purpose.)
> N:=2811015989963832533872581614049911671666799773015345866534728355593738133645400062056158656010392494732270433778896673;

  N := 28110159899638325338725816140499116716667997730153458665347\
        2835559373813364540006205615865601039249473227043377889667\
        3

> e_old:=39468789016576597;

                      e_old := 39468789016576597

> d_old:=2156026210735106577178543380004989188733768768607506855682181079799923162831175862779939718621629101101831237103571633;

  d_old := 2156026210735106577178543380004989188733768768607506855\
        6821810797999231628311758627799397186216291011018312371035\
        71633

> e_new:=9571856891572189657165267;

                  e_new := 9571856891572189657165267


4.  Break the following El Gamal public key using the Pohlig-Hellman algorithm.  As usual, if you use a program, show the text in your worksheet.
The work involved should be manageable by hand (easier than the class example, at any rate) , though it would certainly be easier with automation.
 Once you have broken it, decipher the attached ciphertext using the elgamaltest.mws functions (remember that elgamaltest.mws needs you to run
rsasupport.mws, and you need to set p, alpha, beta, and a to the right values to get elgamalstringdecipher to work).
> p:=119594217887;

                          p := 119594217887

> alpha:=1237;

                            alpha := 1237


> beta:=106630550246;

                         beta := 106630550246

> ciphertext:=541587105674140725056702530718050193579144623188092073082477711584382307322986270710310781754956500994364433286481013147624996442412366658204033793896869441696708682260178747102377402305382602947655769384600811361003090898612793958135677173827855420594340476539052675356865798035662712803973533882025477817912001278802363782100040004037026631429502080673908058628879392239503155740695811694010950316;

  ciphertext := 54158710567414072505670253071805019357914462318809\
        2073082477711584382307322986270710310781754956500994364433\
        2864810131476249964424123666582040337938968694416967086822\
        6017874710237740230538260294765576938460081136100309089861\
        2793958135677173827855420594340476539052675356865798035662\
        7128039735338820254778179120012788023637821000400040370266\
        3142950208067390805862887939223950315574069581169401095031\
        6

5.  An important secret message encoded with the Hill cipher has fallen into your hands, along with a cipher text associated with a known plaintext.  You are
confident that the key size is less than or equal to 5 by 5.  Decode the secret message.   Use the functions in cryptonotes1.mws.  You might want to look at
my examples in hillchallenge.mws.

> known_plaintext:="meetmeatfouroclockbehindalbertsonsonstatestreettoexchangethesecretplans";

  known_plaintext := "meetmeatfouroclockbehindalbertsonsonstatestr\
        eettoexchangethesecretplans"

> known_ciphertext:="ETYFMDSLTIYUTAFHZGBZSIXHBGMJLTXHFKSOAJVDXDJMFRLOJGDBEDNKZQGLCPQDZFGYWMDK";

  known_ciphertext := "ETYFMDSLTIYUTAFHZGBZSIXHBGMJLTXHFKSOAJVDXDJ\
        MFRLOJGDBEDNKZQGLCPQDZFGYWMDK"

> unknown_ciphertext:="KCTHOSJIXCWLMUPRFQQFKQHYDAZHAUBJWIZSQIQLMFCNIMLZLODHYORAKTDZIJHJ";

  unknown_ciphertext := "KCTHOSJIXCWLMUPRFQQFKQHYDAZHAUBJWIZSQIQLM\
        FCNIMLZLODHYORAKTDZIJHJ"

>