# Math Help - RSA cipher problem

1. ## RSA cipher problem

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

2. ## Re: RSA cipher problem

OK, this is my understanding of RSA-style encryption:

First, one picks two distinct primes, $p$ and $q$. The message is then encoded using a modulus $n = pq$.

The encryption key $e$ is then chosen to be an integer $1 < e < \varphi(n)$, where $\varphi$ is the Euler totient function.

The message $m$ (which is an integer) is then turned into the ciphertext $c = m^e\text{ (mod }n)$.

Together, $(e,n)$ make up the public key.

The private key (which must be kept secret) is $(d,n)$, where $d = e^{-1}\text{ (mod }\varphi(n))$

The message $c$ is sent to the holder of the private key.

To recover the plaintext $m$, one computes:

$c^d = (m^e)^d = m^{ed} = m^{ee^{-1}} = m\text{ (mod }\varphi(n))$

***************************

I am unfamiliar with your notation, so what follows here is just a guess:

$p = 5, q = 41$, so that $n = 205$ and $\varphi(n) = \varphi(5)\varphi(41) = (4)(40) = 160$.

Presumably, we have "two messages" encoded, $c_1 = 1$ and $c_2 = 115$

Presumably the encryption key is $77$.

To find the decryption key, we compute $(77)^{-1}\text{ (mod }160)$, which we have previously found to be $133$.

Next, we calculate $1^{133}$ and $115^{133}$ modulo $205$.

The first one is easy, it will be $1$. The second one is a bit more involved. I do not know what this "method of repeated squaring" is, but it may be similar to what I have done below (and my calculations may be off).

Working mod 205, we have:

$(155)^{133} = (115)((155)^2)^{66}$. As $115^2 = 13225 = 13120 + 105 = 64*205 + 105$, this is:

$= (115)(105)^{66} = (115)((105)^2)^{33}$. Now $105^2 = 11025 = 10856 + 160 = 53*205 + 160$, so:

$= (115)(160)^{33} = (115)(160)(160)^{32}$. Dealing with the left first, we have $(115)(160) = 18400 = 18245 + 155 = 89*205 + 155$, so we have:

$= (155)(160)^{32} = (155)((160)^2)^{16}$. So (whew, this tires me out) $160^2 = 25600 = 25420 + 180 = 124*205 + 180$, and:

$= (155)(180)^{16} = (155)((180)^2)^8$. Same process: $180^2 = 32400 = 32390 + 10 = 158*205 + 10$, thus:

$= (155)(10)^8 = (155)(100)^4 = (155)(100^2)^2$. Here, $100^2 = 10000 = 9840 + 160 = 48*205 + 160$, and we get:

$= (155)(160)^2 = (155)(180)$ (we calculated $160^2$ earlier). As $(155)(180) = 27900 = 27880 + 20 = 136*205 + 20$, we finally arrive at:

$= 20$.

So the decrypted numerical message is: <1,20>, that is the text message is: <A,T>.

***************************

The above has a lot of guesswork on my part, and my calculations may be wrong.

3. ## Re: RSA cipher problem

Thanks again Deveno your guesses are right and I could follow your work till the point she you calculated 1 ^133 and 115 ^133 modulo 205.
Why do you used modulo 205? On mine calculation I used modulo 133 since (77)−1 (mod 160) = 133.

I'm not saying you are wrong just wanna understand the reasons specially because with the modulo 205 you come to a result and with the modulo 133 I got stuck.

4. ## Re: RSA cipher problem

The encryption and decryption takes place mod 205.

The exponents we use ($d$ and $e$) are calculated using mod $\varphi(205)$ = mod 160.

The reason we do this is that if $\text{gcd}(a,n) = 1$,

$a^{\varphi(n)} = 1\text{ (mod }n)$ <---this is often called Euler's theorem.

So if $u = v\text{ (mod }n)$ we have:

$a^u = a^{v + k\varphi(n)} = a^v\cdot a^{\varphi(n)} = a^v\cdot 1 = a^v \text{ (mod }n)$

That is, when working mod n, and working with exponents, we work mod $\varphi(n)$ in the exponents.

Since our encryption exponent is 77, we need to find the inverse of 77 mod 160, which "undoes" the encryption when we exponentiate by it.

But both the encryption and decryption take place mod 205. The 133 is just the $d$ we need to exponentiate by to decrypt, just like 77 is the $e$ we use to encrypt.

5. ## Re: RSA cipher problem

Deveno I finally could understand it and by using my method I was able to arrive to the same result that you pointed out of 1 and 20.
Thank you so much for all your help and attention.

xxx