MAT312: Applied Algebra

Computer project #1

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

> Message :=[
250668736648976381400853039711696519700273239009930768993830716776093228677439240295257178981316117701965624531104681458002208123032739455036441595688900759757446466769583605417595786288394551208695477810891237, 247849682655655471804778511653871068180575500506496445672016587529503240181045730250615753995088063425354618059050602479665939668341353696216632702442384515847788360895757550652478657543926477631892150313607981, 158888150623565196510391782736285548849345587444080442415350678772433463873606381824658787433905283328668731692271091343883688444770592754324370812288411526113824574066229853220150124534146420063066674871855199, 117131208664456769432547321142231623657048062827688498314177701736054330532675519552661766304185661524609961916813128312161514809099995726998115418381951863530436556157042842660730462932805835224547159284816740, 267120648655711195114497528395544897196016955040936469542380483686533524849835269438609839288886800254097204533727955116874064250281172519730453170348333981151651248228551415519215212586190598658444540481109856, 6777906472735566816243836385657453513205134744604240536631988497498214533636239667634941607711157567161322142535456374871288867835215632555059190354761033008989984565322669665188828297490724841391423164185633, 265060506338420976147702543461995541983881336903703803514517701031232105427966048548767835626448604599151287785677661159671094150859723707254476140521486489354114718637027760701307547925715802976542431336473443, 210925570057129959129830126072250384685979999355126279817242164752620990494825428163700890823013307942267277918208857036332759955422909551928768341433501401849297988437512790988023406088121035312585410317782475, 65866953148805306342732721653384427346106048968575636439165154291048712857474197780370632685095104999664340288808341173963013568826616528837758313014516195657318311016628854261310963745162078100050716226611115, 160364807321654355117173024504231777273750448921296760322408519230559210201182897852667639536616716633724735675259319287829292309149745538203036191712119662748026816106976295976715622823033717286844415486423824, 226348620153385254622143996318532553026502038858722559629681446428216992557498939509821338093558406570734512566608941376658306058713744022153081579147464514463154399265835580265846041752335067549550575177130890, 97659200289387202800000884166373351969136053085657951584925431702078703423201001205142438546998319164792543498737530279138080277711254641710986307834275371382401009325149811750883774801625027633504394724386126
]:

To reference any one of the numbers in the message, use the notation Message[n] for the number in the list.

(note that the : at the end of the statement supresses any Maple output.)

The message was encoded using the following base , which happens to be the product of two primes of about 100 digits each.

> base := 306452378368439048068163462827732718518746357439816786462853527051887614619645017555473997034658600670196373847577090557186847481568857514863943420768079192496582103845106570240909529229513539067993374460489159;

The message was encoded using the exponent below, which will be of little help in deciphering the message. However, you could use it to

forge a different one.

> encodingExponent:=187278234236304263949178832508721960012571205799023577441844978842826472165275383825939373;

The exponent x below will allow you to decipher the message, by computing , mod , where represents each number in the message above.

> x := 98246007475185045209994421243798892261304114349053505420355263096907344146258364563089483610310824068274750765894969973907087571226283671518590912120556739039303875632185301094653927842294310968495586626369445;

Of course, the resulting computation gives you numbers, and you would like something you can read. To do so, you will need to know how the words were converted to large integers. Here's how: the message was read in 47 characters at a time. Each character was viewed as a number between 0 and 127 (by assigning it the corresponding ASCII code), and the resulting block was interpreted as a 47-digit number in base 128 (such numbers are about 210 digits long when written in base 10). Spaces, punctuation, line breaks, and so on were treated as part of the message, and also encoded.

For example, to encode the first 47 characters of the previous paragraph, we would compute

+ ... +

because O=79, f=102, space=32, c=99, o=111, (and so on) in the ASCII code. To write such a number as printable text, we just reverse the process. Rather than make you worry how to do all that, below is a little Maple procedure which does that:

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

Make sure that you can use PrintNumberAsText to decipher what the number below represents. (Note that this process, while hard for people to read, is NOT encryption, merely translation).

> trialnum:= 767881737176172013294653540993500170940865317690485262301912883980080798615353381549606267397341184;

>

Finally, you might need to know how to compute powers modulo p in Maple-- you do this using &^ and mod . For example, to compute

, we do the following

> 5 &^ 2 mod 4;

A more complicated example might be to compute the third number in the message raised to the 178th power, mod 47:

> Message[3] &^ 178 mod 47;

or, if you prefer to write modular arithmetic in functional notation, you could write the same command as

> modp(Message[3] &^ 178, 47);

That should be enough information to do the project.

You are now finally ready to decipher the message!

>