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.

  • $\begingroup$ Welcome to Cryptography Stack Exchange. Is this is about this encryption scheme: springerlink.com/content/87446r81342k3h8h ? $\endgroup$ – Paŭlo Ebermann Apr 26 '12 at 11:58
  • 1
    $\begingroup$ 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.) $\endgroup$ – 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_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$$


  • 1
    $\begingroup$ 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." $\endgroup$ – D.W. Jan 9 '13 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.