3
$\begingroup$

How the use of unsafe prime in DH key exchange makes DH vulnerable to be broken? can anyone explain to me what is safe prime, and what is the difference between safe and strong prime? How the attacker can solve DL problem if safe prime hasn't been used even if the prime is large enough says >1024 bits

$\endgroup$
  • 2
    $\begingroup$ All strong primes are also safe primes. Pohlig-Hellman: Basically split the group into many small ones and break it in them. $\endgroup$ – SEJPM Dec 4 '16 at 23:38
3
$\begingroup$

First some definitions:

A safe prime is a prime $p$ of the form $p = 2q + 1$ where $q$ is also prime. This is important as the Pohlig-Hellman algorithm runs faster as the largest factor of $p - 1$ becomes smaller. A safe prime is optimal in this sense as $p - 1 = 2q$ and $q$ is therefore the largest possible factor of $p - 1$.

Strong primes are defined here: https://en.wikipedia.org/wiki/Strong_prime#Definition_in_cryptography

Notice that depending on your definition of "large prime factors" either all strong primes are safe, or they are distinct but similar class of primes.

The fastest algorithms for breaking Diffie-Hellman in the generic case of a group of order $p$ (i.e. those that also work in elliptic curve groups) are $\mathcal{O}(\sqrt{q})$ where $q$ is the largest prime factor of $p$. Hence it is important that $q$ be as large as possible. Ensuring $p$ is a safe prime is a good way of enforcing this.

In specific cases, when groups are represented as $\mathbb{Z}_{p}^{\ast}$, since the fastest algorithms (Index Calculus and Function Field Sieve) are sub-exponential and do not depend on the prime factors of $p$, it is less crucial in these settings.

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