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
  • $\begingroup$ 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... $\endgroup$ – Maarten Bodewes Sep 21 '19 at 22:04

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$$


| improve this answer | |
  • 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

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