Join Log in
Score:0
Finlay Weber avatar Crypto

Are all public key a result of computing g^k mod p

ng flag
Finlay Weber

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?

63
0 + 0
kelalaka avatar
in flag
kelalaka
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,
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
For encryption you can use a (EC)DH primitive to implement [(EC)IES](https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme). 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*.
0
Reply
Score:4
poncho avatar Crypto
my flag
poncho

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

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.