Common Modulus Attack in a Lucas Group

Question

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.

Answer 1

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