1. ## RSA Decryption method

I am trying to understand how this method for simplifying the decryption process works. I understand that if I have the message c raised to the public exponent modulo the modulus, then to decrypt it, I need to raise the encrypted message to the private exponent modulo the modulus.

Say I have a public key (13, 673627) and a private key (103381, 673627) and I want to read the message 174277, I understand that I can do this by raising $\displaystyle 174277^{103381}$ and taking mod 673627 to get it. However, I have a guided question that goes through a method that doesn't require as much computation and I don't quite understand it.

It says "find the other information in (103381, 673627), $\displaystyle e_1$ is chosen so that $\displaystyle 13e_1 \equiv 1~mod~ p_1$, $\displaystyle e_2$ chosen so that $\displaystyle 13e_2 \equiv 1~ mod~ p_2$ and $\displaystyle c$ chosen so that $\displaystyle p_1c\equiv 1~ mod~ p_2$.

I factored the modulus to get 673627 = 919*733 = $\displaystyle p_1p_2$

I found that:

$\displaystyle 13(707) \equiv 1~ mod~ 919$

and

$\displaystyle 13(282)\equiv 1~ mod~ 733$

and

$\displaystyle 919(67)\equiv 1~ mod~ 733$

How do I use them to decrypt 174277?

2. ## Re: RSA Decryption method

are you sure it's not:

$\displaystyle 13e_1 \equiv 1\ \text{mod}\ (p_1-1)$ and

$\displaystyle 13e_2 \equiv 1\ \text{mod}\ (p_2-1)$ ...?

3. ## Re: RSA Decryption method

Yes... unfortunately. I saw the $\displaystyle (p_1 - 1)$ and $\displaystyle (p_2 - 1)$ algorithm on wiki and was hoping to be guided through it from there.

4. ## Re: RSA Decryption method

because it looks like a computational shortcut using the chinese remainder theorem, but there's nothing involving the inverse of p2 mod p1.

5. ## Re: RSA Decryption method

If it helps, here is a walk-through that parallels the guided question. I completed all the steps but couldn't get the answer 10000 - perhaps I am misunderstanding part of it. I can't be sure which variables are which in my question. I found all the values that satisfied the equations successfully but completing the final computation gave me something different to $\displaystyle 174277^{103381}~ mod~ 673627$.

Compute:

$\displaystyle a_1 = c^{exponent_1} ~mod~ p_1$

Compute:

$\displaystyle a_2 = c^{exponent_2}~mod~p_2$

Find:

$\displaystyle a \equiv a_1~mod~p_1$ and $\displaystyle a \equiv a_2~mod~p_2$

Compute:

$\displaystyle h = coefficient \times (a_1-a_2)~mod~p_2$

Finally compute:

$\displaystyle a_2+h\times p_2~mod~modulus$

6. ## Re: RSA Decryption method

well, see, that would work...if exponent1 and exponent2 were 103381 (mod p1-1) and 103381 (mod p2-1). are you working from a text, or from notes?

7. ## Re: RSA Decryption method

Method is from notes, question is from a handout.

So, in that case,

$\displaystyle a_1 = 174277^{565} ~mod ~919$

$\displaystyle a_2 = 174277^{169}~ mod ~733$

$\displaystyle \equiv 810~ mod ~919$

$\displaystyle \equiv 471~ mod ~733$

$\displaystyle a = (-84)(733)(810)+(67)(919)(471)$

But a doesn't seem to be used :S

How would you find the message with your method and maybe I can extract what I need to do from that.

8. ## Re: RSA Decryption method

calculate a mod 673627