Here is part a:

First applying the division algorithm repeatedly :

160 = 2 x 77 + 6

77 = 12 x 6 + 5

6 = 1 x 5 + 1

Now eliminating multiples of 5 and 6 :

1 = 6 -1 x 5

= 6 -1(77 - 12 x 6)

= (1 x 6) - (1 x 77) + (12 x 6)

= -1 x 77 + 13 x 6

= -(1 x 77) + 13(160 - 2 x 77)

= -(1 x 77) + (13 x 160) - (26 x 77)

= -27 x 77 + 13 x 160

Hence :

-27 x 77 = -13 x 160 + 1

and -27 is congruent to 133(mod 160)

Thus the multiplicative inverse of 77 in Z160 is 133.

Now an RSA cipher is defined on Z205 by R77 (m) congruentm77 (mod 205)

b) write down the deciphering rule for this cipher justifying your answer to reference to part (a)

From part (a) we know that (R77)^-1 = R133

A message is coded numerically using the correspondence A = 1, B=2, ..., Z=26. It is then enciphered using the RSA cipher above to give the cipher text <1, 115>.

c) By using the repeated squaring technique decipher the cipher text and recover the message.

Now we need to find the R133(1) and R133(115)

R133(1) = 1 = 1 (mod 133) = 1

R133(115) = 115^1 = 115 (mod 133) = 115

= 115^2 = 13225 (mod133) = 58

= 115^4 = 58^2 = 3364 (mod 133) = 39

= 115^8 = 39^2 = 1521 (mod 133) = 58

From here the sequence repeats alternating between 39 and 58.

Then I used R133(115) = 115^128 x 115^4 x 115^1 = 58 x 39 x 115 = 260130 = 115 (mod 133)

Which for me looks totally wrong since there is no letter correspondet to the value of 115.

Hope my notations is not too messy. I really need to understand where I went wrong.

xxx