0
$\begingroup$

I just read through the text book definition of Diffie–Hellman key exchange. And from what i understand, the public key that is shared based on the protocol is calculated from:

g^k mod p

where g is a generator in the multiplicative group, and p is a large prime and k is the private key.

My question is, are all public/private key generated to have this relationship? Or this way of generating the public key from a private key and a g and p is peculiar to the Diffie–Hellman key exchange construction?

I mean if I want to generate a private key pair for use other than key exchange, for example for encryption, will I use a similar construct or something different?

$\endgroup$
2
  • $\begingroup$ It is based on a discrete logarithm. RSA is based on trapdoor permutation, and we have some other in Lattice based. The secret and public key is determined by the underlying problem, $\endgroup$
    – kelalaka
    Oct 28 '21 at 20:08
  • $\begingroup$ For encryption you can use a (EC)DH primitive to implement (EC)IES. For signatures there is (EC)DSA that is also derived from the Discrete Logarithm problem. However, that doesn't mean that you can use it for any particular scheme and it certainly doesn't mean that other algorithms work in a similar fashion or rely on the same DL-problem. $\endgroup$
    – Maarten Bodewes
    Nov 15 '21 at 0:22
4
$\begingroup$

My question is, are all public/private key generated to have this relationship?

No; DH does that, but there are other public key algorithms do something different.

With RSA [1], the public key is a pair $n, e$, while the private key can be represented as $n$ and a value $d = e^{-1} \bmod \text{lcm}(p-1, q-1)$ (where $p, q$ are the prime factors of $n$. As you can see, that's rather different.

Things get even more different when you start looking at postquantum algorithms, such as lattice schemes (e.g. NTRU) or code based schemes (e.g. McEliece).


[1]: Actually, it's far more common for questioners to assume that 'all-the-world-is-RSA'; it's rather refreshing to hear from another viewpoint...

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