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

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.

## closed as unclear what you're asking by Squeamish Ossifrage, kelalaka, Maeher, Maarten Bodewes♦Sep 21 at 22:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to Cryptography Stack Exchange. Is this is about this encryption scheme: springerlink.com/content/87446r81342k3h8h ? – Paŭlo Ebermann Apr 26 '12 at 11:58
• 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
• Closing this old question since I consider "a LUC encryption scheme" not enough to go on. If the author wishes to explain then please adjust the question or comment below... – Maarten Bodewes Sep 21 at 22:04

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