4
$\begingroup$

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ .

I thought one way is to produce a prime $p$ that $p-1$ is an smooth integer which then makes discrete logarithm problem easy using Pohlig-Hellman algorithm but i couldn't find any algorithm for generating such primes. Trivially, we can generate random numbers and then check if it's prime and if it's prime, check if $p-1$ can be factorized to a set of small prime numbers. It can be done in another way, considering a set of small prime numbers and generating random exponents for every prime in the set, multiplying all primes powered to their exponent. By doing so, we have a number $r$ that can be factorized to small prime numbers and then we can check if $r+1$ is prime.

Clearly these methods are just trial and error and may take a long time to find such prime, specially when it comes to generating 256 bit prime numbers. Is there any better algorithm ?

What are other ways to generate a 256 bit long weak modulus?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This is not a weak public key, but rather a group with a generic backdoor that can be used to break all public keys. A weak public key would be an $x$ that you know or has very low entropy. Of course, a generic backdoor is much stronger. $\endgroup$
    – Yehuda Lindell
    Dec 31, 2017 at 8:34
  • $\begingroup$ @YehudaLindell You're right, edited. $\endgroup$
    – Mehran Torki
    Dec 31, 2017 at 10:14
  • $\begingroup$ How is the group $(\mathbb{Z}_p,+)$ not a straightforward solution to your problem? Taking discrete logarithms is always trivial in this group (this boils down to modular division in the field $\mathbb{F}_p$). In general, if you simply want a group where discrete log is easy, you will have plenty such groups available... $\endgroup$
    – Geoffroy Couteau
    Dec 31, 2017 at 16:56
  • $\begingroup$ @GeoffroyCouteau I'm looking for some groups that make discrete logarithm easy and the weakness is not easily detectable (use cases are detecting kleptography attacks). The group you mentioned is easy to detect so it may not be used by an attacker. $\endgroup$
    – Mehran Torki
    Dec 31, 2017 at 19:52

1 Answer 1

Reset to default
7
$\begingroup$

Is there any better algorithm ?

Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You say that it's trial and error (and it is), however it's about as efficient as the traditional algorithms we use to search for primes; if you're looking for an $q$ bit prime, then you'd expect to need to try an average of $\log(2^q) / 2 = q \log(2)/2$ sets of primes before finding one that makes up a prime (actually, a bit less, because you know apriori the numbers you generate won't have $q_1, q_2, ..., q_n$ as a factor).

An alternative approach to creating a weak DLog problem is to make $g$ weak; that is, generate a $p$ of the form $2qr + 1$, where $q$ is a small prime and $r$ is a large one (and the same algorithm can be used to seach for it). Then, you select $g$ to be of order $q$ (that is, you select a random value $h$ and set $g = h^{2r} \bmod p$, and check that it's not 1); if $q$ is an $m$-bit prime, then the discrete log problem will take $O(2^{m/2})$ time; for example, $m=32$ makes this solvable in milliseconds.

Of course, the use of either approach can be fairly easily detected by someone examining $p$ and $g$...

Improve this answer
$\endgroup$
3
  • $\begingroup$ In you alternative approach, should $p$ be prime ? if i get it right, your alternative approach is using weak subgroup, is it ? $\endgroup$
    – Mehran Torki
    Dec 31, 2017 at 6:42
  • 1
    $\begingroup$ @MehranTorki: yes, it assumes $p$ is prime. If we consider composite $p$ values, then we can try to hide the trapdoor (but still the fact that we're using a composite modulus is still obvious) $\endgroup$
    – poncho
    Dec 31, 2017 at 17:39
  • 1
    $\begingroup$ @MehranTorki: see crypto.stackexchange.com/questions/32415/… for a discussion of composite modulii (and how they can be used to do weakness hiding) $\endgroup$
    – poncho
    Dec 31, 2017 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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