5
$\begingroup$

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<R$), 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...

$\endgroup$
  • $\begingroup$ The link in your post is broken, just to let you know. $\endgroup$ – Patriot Sep 19 '19 at 9:37
  • 1
    $\begingroup$ @Patriot the link is fixed now. $\endgroup$ – Maeher Sep 19 '19 at 21:08
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Sep 19 '19 at 23:52
  • $\begingroup$ 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. $\endgroup$ – fgrieu Sep 20 '19 at 7:59
1
$\begingroup$

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.

$\endgroup$

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.