Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this 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
1  
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
add comment

1 Answer

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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