# Math Help - RSA public key cryptosystem

1. ## RSA public key cryptosystem

The message 58 − 0 − 24 − 23

has been encoded from single letter message units using the RSA public
key cryptosystem. The alphabet consists of the ordinary English alphabet
A - Z and the letter b which stands for space. The recipient was foolish to
adopt as his public key: n = 91, e = 59.

Find the secret key and decode the message.

I've worked out d to be 11, with 59d = 1 mod 72.

So using the formula M = C^11 mod 72, I know I have to calculate $58^{11}, 0^{11}, 24^
{11}$
and $23^{11}$

So calculating the first one in a table...

mod 72
n 58^n
1 58
2 52
4 40
8 16
11 = 58 x 52 x 16 = 48256

I then get 48256 = 16 mod 72 which gives me the letter Q.

But I know that the message should be LATE, so can anyone please explain where I am going wrong?!

2. Originally Posted by hunkydory19
So using the formula M = C^11 mod 72
The above is wrong. It should read M = C^11 mod 91

3. Hello,

Originally Posted by hunkydory19
The message 58 − 0 − 24 − 23

has been encoded from single letter message units using the RSA public
key cryptosystem. The alphabet consists of the ordinary English alphabet
A - Z and the letter b which stands for space. The recipient was foolish to
adopt as his public key: n = 91, e = 59.

Find the secret key and decode the message.

I've worked out d to be 11, with 59d = 1 mod 72.

So using the formula M = C^11 mod 72, I know I have to calculate $58^{11}, 0^{11}, 24^
{11}$
and $23^{11}$

So calculating the first one in a table...

mod 72
n 58^n
1 58
2 52
4 40
8 16
11 = 58 x 52 x 16 = 48256

I then get 48256 = 16 mod 72 which gives me the letter Q.

But I know that the message should be LATE, so can anyone please explain where I am going wrong?!

There are two steps :

- the part where you have to find d such that $ed \equiv 1 \mod {\color{red}\varphi(n)}$

- the part where you have to calculate $M=C^{d} \mod {\color{red}n}$

4. Originally Posted by Moo
Hello,
- the part where you have to find d such that $ed \equiv 1 \mod {\color{red}\varphi(n)}$
hunky has done this part correctly. And obtained d=11. What is the mistake you are talking about?

5. Originally Posted by Isomorphism
hunky has done this part correctly. And obtained d=11. What is the mistake you are talking about?
I was just pointing out the differences in the two steps with the modular. I know he has done this part correctly ^^

6. Another RSA question that I'm stuck on...this time with 2 message units...

The message
309 − 95 − 723

has been encoded from blocks of two-letter message units using the RSA
public key cryptosystem. The alphabet consists of the ordinary English
alphabet A - Z and the letter b which stands for space. The recipient was
foolish to adopt as his public key: n = 3599, e = 1967.

(a) Find the secret key and decode the message.

Found p = 61, q = 58.

So 1967d = 1 mod 3480.

Used Euclids alg to find d = 23.

So using $M = C^{23} mod 3599$, need to calculate remainders of $309^{23}, 95^{23}, 723^{23}$by 3599.

First number:

n 309^n mod 3599
1 309
2 1907
4 1659
8 2645
16 3168

So 23 = 3168 x 1599 x 1907 x 309 = number in standard form

So I split the numbers up into:

3168 x 1599 = 1172 mod 3599
1907 x 309 = 2626 mod 3599

Then 1172 x 2626 = 527 mod 3599
So 527 = (27 x 19) + 14
Hence corresponding letters are T and O.

Tried doing the same thing for the second number:

n 95^n mod 3599
1 95
2 1827
4 1656
8 3497
16 3206

So 23 = 3206 x 1656 x 1907 x 309 = number in standard form

Splitting numbers:

3206 x 1656 = 611 mod 3599
1907 x 309 = 2656 mod 3599

Then 611 x 2656 = 2931 mod 3599

But 2931 / 27 = 108 which doesn't correspond to any letters!

Can anyone please explain what I am supposed to do at this point?

7. Yop,

I find that $95^{23} \equiv 81 \mod 3599$

81=3x27

So the first letter is $\equiv 3 \mod 27 \rightarrow 3$ -> C
The second letter $\equiv 0 \mod 27 \rightarrow 27$ -> space

Isn't it ?

8. Cheers for replying Moo, but how did you find 81 though? Is the method I used above not the correct way of doing it?

Also aren't you supposed to assume that the alpahebet is number starting from 0, with 26 = b, so 3 would be D and 0 would be A? Although it doesn't actually say how it's numbered in the question so not too sure....

9. but how did you find 81 though?
My precious calculator

Is the method I used above not the correct way of doing it?
It's correct ! The part which is incorrect is :

So 23 = 3206 x 1656 x 1907 x 309 = number in standard form
You took the two numbers in red from the table of 309, not of 95

For the numeration... Yep, it may be more logical.

But I think the most important in it is to find the modulus After that, you can do everything you want

10. Ohhhhhhh yeeeeeah

Thanks for that Moo, genius as always.