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)$ ...?

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.

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.

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$

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?

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.

Re: RSA Decryption method