5
$\begingroup$

I'm still new to public key crypto. I'm trying to understand how it is that the private key is generated first in public key crypto? I would have expected the private and public key to be generated at the same time, as they would depend on each other.

For example, in a Bitcoin wallet, I can choose a private key (brain wallet), which will then be used to derive my public key (then my BTC address).

$\endgroup$
  • $\begingroup$ Guys, please also vote for the questions. I grant that this one is based on a false premise, but a 0 / 10 score for the Q / A is a bit much. $\endgroup$ – Maarten Bodewes Jan 7 '15 at 1:21
12
$\begingroup$

In general, the public and private keys are computed together.

For some schemes, the public key is computed from the private key. ElGamal is an example. (The system parameters include a suitable cyclic group $G$ with a generator $g$. Choose a random exponent $a$. Compute $y=g^a$. The public key is $y$, the private key is $a$.)

For other schemes, this is not the case. Some variants of RSA are examples. (Choose primes $p$ and $q$. Compute $n=pq$. Choose (somehow) $e$ relatively prime to $(p-1)(q-1)$. Compute an inverse $d$ of $e$ modulo $(p-1)(q-1)$. The public key is $(n,e)$, the private key is $(n,d)$ (or something equivalent). Notice (a) how the public key is completed before the private key, and (b) it is not in general possible to quickly compute the public key $(n,e)$ from the private key $(n,d)$.)

(For completeness: Note that of course, the private key cannot be quickly computed from the public key. If it could, any adversary could.)

$\endgroup$
  • 2
    $\begingroup$ ad (a). This is not mainly about the order of computations (which one could, by the way, rearrange to calculate $n=pq$ as the last step), but more about the data flow: The only thing that is non-deterministically generated is the tuple $(p,q,e)$, and this information is (computationally) stronger than the private key $(n,d)$. Hence $(p,q,e)$ could be regarded as a private key, but the "reduced form" $(n,d)$ is more convenient. It is really a matter of how the parameters are defined, but my point stands: (information that efficiently yields) the private key has to be generated first. $\endgroup$ – yyyyyyy Jan 5 '15 at 13:28
  • 1
    $\begingroup$ @yyyyyyy: In fact, many RSA implementations do store $p$ and $q$ as part of the private key, since doing so allows using the Chinese remainder theorem to speed up the algorithm. $\endgroup$ – Ilmari Karonen Jan 5 '15 at 13:37
6
$\begingroup$

The reason that one must be derived from the other is that the private and corresponding public key are strongly related: For instance, in RSA, the pair satisfies $ed\equiv 1\mod\varphi(n)$; in Diffie-Hellman, we have $A=g^a$; and so forth. Hence, it is just natural to start with with generating one part and deriving the other to satisfy the cryptosystem's requirements.

Now, if it was possible to do it the other way round — generate a public key and derive the private key — what would stop an attacker from doing the same? Any cryptosystem that permits this is broken by design, as it is obviously possible to efficiently compute the private key corresponding to a given public key.

$\endgroup$
1
$\begingroup$

The answer is: this question is based on a mistaken premise. The private key is usually not generated first. In general, they're generated at the same time.

For some schemes, the public key can be derived from the private key, but this doesn't always hold, and that will depend on specific properties of the particular public-key scheme. If it's possible to generate the private key first and then derive the public key from the private key, then that's a special property of the public-key scheme -- not something that is guaranteed to be possible for all public-key schemes.

$\endgroup$
0
$\begingroup$

I am not sure if this is possible in general (for any asymmetric cipher), but this is not prohibited.

In theory, private key contains the same information as public key. With unrealistic amount of time, you are able to compute private key from public key.

There is one strong requirement: one can't derive the private key from the public key (in a reasonable time). The opposite (i.e. one is not able to derive public key from private key) is not a requirement. Moreover, I don't know any asymmetric cipher where it is infeasible to compute the public key from a given private key.

For many asymmetric ciphers, you can see the public key as a subset of private key. (I do not distinguish if some parameter (modulus, public exponent, …) is included in the key or if it is feasible to calculate it from other parameters of the key in a small time.)

$\endgroup$
  • $\begingroup$ -1 for the second sentence. Maybe you could rewrite that one, I'm pretty sure you didn't mean that literally. Eh, 2nd sentence of 3nd paragraph wrong too, will stay at -1. $\endgroup$ – Maarten Bodewes Jan 5 '15 at 16:19
  • $\begingroup$ I've clarified the text. I hope it is not confusing now. $\endgroup$ – v6ak Jan 5 '15 at 18:53
0
$\begingroup$

That behavior seems to be due to the workflow of the application you mentioned. In fact the public key is generated first, the private key is derived from the public key. When you get your private key the application already knows the public key. Here is what happens, note the public key existing in step 4:

  1. Choose two distinct prime numbers p and q. For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
  2. Compute n = pq. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
  3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.
  4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime. e is released as the public key exponent. e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 216 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.
  5. Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)). This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n)) This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and φ(n), respectively.
  6. d is kept as the private key exponent.
$\endgroup$
  • $\begingroup$ If the private key were derived from the public key, couldn't I take someone else's public key and find their private key? $\endgroup$ – Random832 Jan 5 '15 at 16:23
  • $\begingroup$ If you want to derive the private key from the public one, you must beforehand know the factorisation (p,q) of the public modulus. Refer to @vbms who indicate a correct key generation process. the distinct primes (p,q) are randomly generated in such a way that gcd(e, $\phi(n)$)=1. $\endgroup$ – Robert NACIRI Jan 5 '15 at 23:10
  • $\begingroup$ @Random832 you would still need to know the value of p and q. $\endgroup$ – vbms Jan 10 '15 at 9:35

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.