# Missing public exponent

Using LUC RSA, I have a list of 8 public keys $$(R_1,n_1)$$ through $$(R_8,n_8)$$, and a list of $$8$$ messages $$M_1\dots M_8$$. The messages have all been double encrypted. However, one of the public key exponents, $$n_5$$, is not given. The problem is to decrypt all of the messages, and so I must also determine the value of the missing $$n$$. The hint is that the exponent was constructed "poorly".

Having factored all (including $$R_5$$) but two of the $$R$$s, I have decrypted $$5$$ of the messages.

My question is, what exactly is a poorly constructed public exponent look like, and how can I use what I have been given to discover the missing $$n$$?

Given the length of one particular encrypted message ($$M), it is likely that it was encrypted the last time with $$R_5$$.

So, I suppose what I'm asking is: Can you solve for n given $$E=M^n \mod R$$ where only R (public modulus) and E (ciphertext) are known? I suppose that's basically the DLP...

• The link in your post is broken, just to let you know. Sep 19 '19 at 9:37
• @Patriot the link is fixed now. Sep 19 '19 at 21:08
• Solving $E \equiv M^n \bmod R$ for $n$ given $E$, $M$, and $R$ is at least as hard as factoring $R$, but it's not clear this is even your task since you seem to be using something different from RSA. Maybe the exponent is small enough you can search for it by brute force using real number root-finding. Sep 19 '19 at 23:52
• Except that the definition of Lucas groups is not directly linked to, I see nothing unclear in the question, thus no reason to close it for that motive. And I don't know that we have a policy against interesting CTF-style crypto-related questions when they are not a straght dump of the givens. If the problem statement was online, I'd appreciate a link.
– fgrieu
Sep 20 '19 at 7:59

The hint as stated in the question is that the missing public exponent $$n_5$$ was constructed "poorly". But it could be that some other public exponents $$n_s$$ were constructed similarly, and this could reveal what "poorly" is. I'd check if some pattern emerges from

• the seven other $$n_s$$
• the five possibly different $$n'_s=n_s\bmod\Gamma(R_s)$$ for $$s$$ such that, further, $$R_s$$ is of known factorization as $$P_s^\,Q_s$$ so that we can compute the quantities $$\Gamma(R_s)=\operatorname{lcm}(P_s-1,P_s+1,Q_s-1,Q_s+1)$$
• the five $$m_s={n_s}^{-1}\bmod\Gamma(R_s)$$ for such $$s$$.

If nothing comes out of it, we can try to decrypt with guesses of $$n_5$$ and see if the plaintext's characteristics match those of the other plaintexts (e.g. range, padding, being composed in a certain alphabet/language..). Reasonable guesses could be:

• the seven other other known $$n_s$$
• the know $$n'_s$$ if different
• the few smallest positive $$n$$ that are coprime with $$\Gamma(R_5)$$
• $$n=m^{-1}\bmod\Gamma(R_s)$$ for the few smallest positive $$m$$ that are coprime with $$\Gamma(R_5)$$. This simplifies into raising the ciphertext to increasingly large powers $$m$$, and further speedups are possible for that by precomputing the ciphertext to small even powers.

I do not see that we could mount a discrete logarithm attack as considered in the end of the question, for lack of anything suggesting known plaintext.