# RSA Decryption method

Printable View

• November 7th 2011, 03:11 AM
terrorsquid
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 $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), $e_1$ is chosen so that $13e_1 \equiv 1~mod~ p_1$, $e_2$ chosen so that $13e_2 \equiv 1~ mod~ p_2$ and $c$ chosen so that $p_1c\equiv 1~ mod~ p_2$.

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

I found that:

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

and

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

and

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

How do I use them to decrypt 174277?
• November 7th 2011, 05:26 AM
Deveno
Re: RSA Decryption method
are you sure it's not:

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

$13e_2 \equiv 1\ \text{mod}\ (p_2-1)$ ...?
• November 7th 2011, 05:34 AM
terrorsquid
Re: RSA Decryption method
Yes... unfortunately. I saw the $(p_1 - 1)$ and $(p_2 - 1)$ algorithm on wiki and was hoping to be guided through it from there.
• November 7th 2011, 05:42 AM
Deveno
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.
• November 7th 2011, 05:48 AM
terrorsquid
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 $174277^{103381}~ mod~ 673627$.

Compute:

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

Compute:

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

Find:

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

Compute:

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

Finally compute:

$a_2+h\times p_2~mod~modulus$
• November 7th 2011, 06:22 AM
Deveno
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?
• November 7th 2011, 03:14 PM
terrorsquid
Re: RSA Decryption method
Method is from notes, question is from a handout.

So, in that case,

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

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

$\equiv 810~ mod ~919$

$\equiv 471~ mod ~733$

$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.
• November 7th 2011, 04:11 PM
Deveno
Re: RSA Decryption method
calculate a mod 673627