# Can you help me understand the Common Modulus Attack in a Lucas Group?

I'm trying to decrypt a message that is encrypted using a LUC encryption scheme and running into roadblocks. I know that with RSA if Alice and Bob use the same public modulus but different encryption exponents, with $\gcd(n_A,n_B)=1$ then you can find the plaintext $M$.

I'm provided $R$ (public modulus), $n_A$ (Alices public encryption exponent), $n_B$ (Bob's public encryption exponent. I am also provide two lists of packets that contain the same message sent from a third user, Carol, to both Alice and Bob. Lets call the first packet with the same message $c_{1A}=(x_A,y_A)$ (Alices packet), and $c_{1B}=(x_B,y_B)$ (Bob's packet). I assumed that I could then use the extended euclidean algorithm to find $r$ and $s$ such that $rn_A+sn_B=1$, which I did. Then shouldn't I be able to find the plain text by, $(x_A)^{-r}(x_B)^{s} \mod{R} = M$ where $x_A$ and $x_B$ are the ciphertext?

This is where I am running into problems. Do I need to perform this operation in the Lucas group? As it stands all of my values are scalar.

-
phku, I think we need to see a specification of the encryption algorithm you are using before we can tell you how to attack it. How is the ciphertext $(x_A,y_A)$ computed from the message? (You should describe the public-key encryption scheme, in a way that is accessible to everyone and doesn't require paying money.) – D.W. Jan 9 '13 at 7:27

Just find the modular multiplicative inverse $x_C$ of $x_A$ using the extended Euclidean algorithm:

$$(x_A)^{-r}\equiv(x_C)^{|r|}\mod{R}$$

and

$$x_Ax_C \equiv 1\mod{R}$$

Then, once you have $x_C$, you'll be able to compute:

$$(x_C)^{|r|}(x_B)^{s}\mod{R} \equiv M$$

http://en.wikipedia.org/wiki/Modular_exponentiation

-
I don't see how this answers the question. The question was "Do I need to perform this operation in the Lucas group? As it stands all of my values are scalar." – D.W. Jan 9 '13 at 7:26