MAT312: Applied Algebra

Computer project #2

This project is similar to project #1, except that in this case the message was encoded with a poor choice of primes. Your job is to crack the code, decipher the message, and save the world.

As before, Message is a message which has been encrypted using the RSA public key algorithm. In its encrypted form, it consists of 30 numbers of about 70 decimal digits each. To get Maple to read it, you must hit the enter key for each statement.

> Message :=[
13538355509825098433817370926846543919557618499237576192098246352249328, 4288631183008148222245169930544201064436274587412275369523418748801451, 13111522597076326283731781125350440020750846270752206992134849857445558, 23445040905763019929260502479371806274153356976083214903855583773649152, 24981107695348169489280262930682208281602995470706428076926633376896388, 1810122994695891479396696828024199360828431282850965867602581040338129, 338968533708729116353941477874393243256905895461547755738088991142309, 10246061141520056357110501708185946324904154164588322355979352741892110, 26771924859918960404494509514731677698127036477382375977258376265281282, 26086683209557675290839296871435592287115137243415111840942441232109781, 12030743828607362357689024235363326199536161912805862286118765328506247, 6711353086217090392544698546934183798005821146570923708450384727375787, 9404427465295141226096007183116150199481189289774968168740119794246714, 27140404046308762893094890395854086938657754547516000267249338941002102, 22824400246154264316495348301599100259922768735450011009742545640398770, 12844753218630148577500389061739741237346858698121676853383367963356972, 12656900291905081666057697726323575464153031698602409768725750790221081, 9128399445564784935468325546954945903390175564677010550827489350481665, 1462477682644429296070141172700462230079039137822876836723042099168994, 26767930246506739446563284468633124742267462780690963089990837504602166, 26649687286372732341378969898844355219329717392638840243671854721928643, 27149224393117154994849603843271853891347718002688277820144076575398054, 16377605414442092111877627185463674674910220425473664503730976288670026, 26016845553791401610070492488218139106368886689332861371007833241250517, 20564334850692186581317145377273150911004397404537868685196624575449462, 21414607912747143936886577387304522692506496345672951724577839345356072, 79991848365246740193983934361605494240006768820454709360009627229985, 7281267267054040587811908517170389134748042772257000377189509121332945, 10038099270738439341621472388355782696615407460357145991750833581958941, 19312121694824256292880058640333274620788725194560429244270423719031594]:

As before, the notation Message[n] allows you to refer to the [Maple Math] number in the list.

The message was encoded using the following base , which is, as usual, the product of two primes.

> base := 27606985387162255149739023449107931668458716142620601169954803000803329;

The message was encoded using the public exponent a below.

> a:=95541407564551142884433930859007846184688349517132011538195190379009;

Unfortunately for the sender (but fortunately for you), the sender of the message wasn't paying attention in class and chose a base which is not sufficiently large to provide cryptographic security. In order to crack the code, you need only factor the base and determine the mutiplicative inverse of a , then proceed as in project 1. There are a few words on how to do this at the end.

As in the first project, after cracking the code, you have a pile of 30 numbers, and you need to convert these numbers back to readable text. In this case, the message was read 32 characters at a time (instead of 47 as before), so the each chunk of the message can be viewed as a 32-digit number in base 128 (such numbers are about 70 digits long when written in base 10). As before, spaces, punctuation, line breaks, and so on were treated as part of the message, and also encoded. Below is a version of PrintNumberAsText which translates such numbers back to text. It is essentially the same as the version in project 1.

> PrintNumberAsText:= proc(num)
local i,p,k;
p:=128;
k:=32;
printf("%s",
convert([seq( iquo(modp(num,p^(k-i+1)), p^(k-i)), i=1..k)],'bytes'));
end;

Now we return to the mechanics of cracking the code. One thing we need to know is how to factor the base. Maple will factor integers using the ifactor command. For example, to factor the number 1234567890123456789, we do the following:

> ifactor(123456789012345678901);

WARNING: big numbers take a long time to factor. Maple may take a few minutes to factor the number called base above. Factoring another number only slightly larger may take an hour or two, and, of course, factoring a 100-digit number should not be doable at all with today's computers.

In order to avoid retyping the factors, we have to do a little trickiness. If this confuses you, just ignore this part, or cut and paste the answer.

One way would be to use ifactors instead, but here's another. First, factor the number with ifactor , and give the result a name. Then each factor can be accessed using Maple's op command, as below:

> facts:=ifactor(123456789012345678901);
f1:=op([1,1],facts);
f2:=op([2,1],facts);

Now we can use f1 and f2 for the factors instead of trying to retype them. That is, of course, less important in this example where the factors are short.

The other mechanical piece needed is how to compute the multiplicative inverse. Maple does this easily. for example, to compute the inverse of 9 modulo 17 (the answer should be 2, since 2*9=18=1 mod 17), we just do

> 1/9 mod 17;

Or, to compute the inverse of 123456789012345678901 mod 510422739085023549128244953257600876799 and call it inv , the command is essentially the same:

> inv := 1/23456789012345678901 mod 510422739085023549128244953257600876799;

Armed with those two bits of information, your deep understanding of the RSA algorithm, and your experience with project 1, you should now be able to figure out the decryption key and decipher the message. Good Luck.

>