Thread: 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 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), is chosen so that , chosen so that and chosen so that .

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

I found that:



and



and



How do I use them to decrypt 174277?

are you sure it's not:

and

...?

Yes... unfortunately. I saw the and algorithm on wiki and was hoping to be guided through it from there.

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

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 .

Compute:



Compute:



Find:

and

Compute:



Finally compute:

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?

Method is from notes, question is from a handout.

So, in that case,











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.

calculate a mod 673627