i am wondering how to break DH(small nonprime number). Let's say we don't know:

$a$: Alice's private key

$b$: Bob's private key

And we know:

$N$: nonprime number

$p$,$q$: $N = p * q$ ($p$ and $q$ are prime number)

$g$: the base

$A$: Alice's public key A = pow(g, a, N)

$B$: Bob's public key B = pow(g, b, N)

Now we want to calculate shared_secret = pow(A, b, N) or shared_secret = pow(B, a, N)

If we want to find shared secret, we need to find private key $a$ or $b$ first. We now have $g^{a} \equiv A \bmod pq$

And then
${x_p}$ with $g^{x_p} \equiv A \bmod p$
${x_q}$ with $g^{x_q} \equiv A \bmod q$

And then
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

I know we need to use the Chinese Reminder theorem after that, but i don't know how to start it. Any suggestions?


If we want to find shared secret, we need to find private key $a$ or $b$ first

No, for two reasons:

  • $a$ is not needed. Having found what the question notes $x_p$ and $x_q$, it is easy to compute the shared secret reduced modulo $p$, and modulo $q$, and then use the straight Chinese Reminder Theorem to find the shared secret. It tells when $p$ and $q$ are coprime (including, distinct primes as here and in RSA), and $0\le m<p\,q$, it holds $$\begin{align} &m_p=m\bmod p\quad\text{and}\quad m_q=m\bmod q\\ \iff&m=\left(\left(\left(q^{-1}\bmod p\right)\,(m_p-m_q)\right)\bmod p\right)q+m_q\end{align}$$
  • We can't find $a$ for certain, for there can be several equivalent $a$ (just as there are several equivalent private exponents $d$ in RSA). The best we can aim at is finding a working $a$, or best the smallest positive working $a$.

Hint if we want to find an $a$:

  • use Fermat's little theorem to define a modular equation involving only $a$, $x_p$ and $p$; and a similar one involving only $a$, $x_q$ and $q$. The question nearly does that, but extra parenthesis are required to fix the equations if we stick to proper notation as explained below, and the same quantity is designated by two different letters, creating confusion.
  • then solve for $a$ using a slight variant of the Chinese Reminder Theorem, applicable when the moduli are not coprime: we first divide one of the moduli by the Greated Common Divisor of the moduli, adjust the equation accordingly, and are back to the straight CRT.

Note: $u\equiv v\pmod n$ is a notation meaning that $n$ divides $u-v$, for some integer $n>0$. Whereas $v\bmod n$ without an opening parenthesis immediately before $\bmod$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\equiv v\pmod n$. And $v^{-1}\bmod n$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\,v\equiv1\pmod n$, assuming $\gcd(v,n)=1$. Baring parenthesis, operator $\bmod$ is understood to be evaluated after addition of what's on its left (stopping at the first $=$), but it is best to use explicit parenthesis when the modulus is a sum, as in $u\bmod(n-1)$. Also it is best to avoid $u\equiv v\bmod n$ and use \pmod instead of \bmod if $u\equiv v\pmod n$ is meant, or use $u=v\bmod n$ if $0\le u<n$ is additionally implied.

| improve this answer | |

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.