2
$\begingroup$

More precisely, and as for RSA, is it really true that it is not feasible to recirculate one of the keys knowing ONLY the other with the Elliptic Curves, as for RSA? Or does ECs work differently on this issue? I mean only mathematically (I'm not talking here about OpenSSL's deceptive abilities to keep items in a file to facilitate public key regeneration).

$\endgroup$
1
  • $\begingroup$ Elliptic curve is just a mathematical object, if you are speaking about keys you have to precise the cryptosystem. $\endgroup$
    – Ievgeni
    Jul 21, 2020 at 10:25

2 Answers 2

4
$\begingroup$

In both RSA and usual¹ Elliptic Curve Cryptography (ECC), there is a public key and a private key, forming a matching pair. In signature, the private key is used for signature generation, and the matching public key is used for signature verification. In (usually, hybrid) encryption, the public key is used for encryption, and the matching private key is used for decryption. This dual role with exchange of usage order of the public and private key applies to RSA and ECC alike.

In RSA, it is additionally mathematically possible to exchange the values of the public and private exponents $e$ and $d$. It is thus possible to exchange the values of the public and private keys when expressed as pairs of integers $(N,e)$ and $(N,d)$. Such exchange of values is almost never done in RSA practice².

Such exchange of values is not possible in ECC. That's because an ECC private key is an integer $d$ in $[0,n)$ where $n$ is the order of the generator $G$ of the Elliptic Curve, and the public key is $Q=dG=\underbrace{G+G\cdots+G}_{d\text{ times}}$ where $+$ is the point addition operation of the Elliptic Curve group. The private and public keys are different mathematical objects, which values can't be meaningfully exchanged.


With ECC, given the private key, it is possible to deduce (calculate) the corresponding public key, unlike RSA.

Yes, under appropriate hypothesis: having the RSA private key in a non-standard format, and with an unusually large public exponent $e$.

In ECC, given the Elliptic Curve group³ and the private key $d$, it is a basic operation to find the public key: just compute $Q\gets dG$.

In RSA, when given the private key, it is not always possible to compute the matching public key. Specifically, when the private key is given in the form $(N,d)$, and the public exponent $e$ of the public key $(N,e)$ is a large random secret, finding $e$ is hard. However, finding $e$ is trivial when it is part of the private key, e.g. because the private key is in the recommended RSA private-key format in PKCS#1v2: $(N,e,d,p,q,d_p,d_q,q_\text{inv})$. And finding $e$ is easy when $e$ is below some threshold, e.g. $e<2^{256}$, which also is usual.


¹ As codified e.g. by SEC1.

² Such exchange is insecure if one of the public/private exponents $e$ and $d$ is less than $2^{256}$, which is common for performance reasons. Exchanging public and private key is secure only if the first chosen among public/private exponents $e$ and $d$ is selected at random in a much larger set, or if both are secret, negating the benefits of public-key cryptography.

³ Usually a public parameter, e.g. secp256k1 for anything Bitcoin. Common ECC groups are codified in SEC2.

$\endgroup$
7
  • 1
    $\begingroup$ For both ECC and RSA as it's actually (securely) used, it's possible to calculate the public key when given the private key. It's possible to construct custom RSA-like systems with non-standard key formats (not PKCS#1) where this isn't the case, but I don't know of any reason to do that and am not aware of any system that does. $\endgroup$ Jul 21, 2020 at 13:10
  • $\begingroup$ @SAI Peregrinus: So with RSA-like system, one reason is to be able to strongly separate roles. A "third" party may give one of keys pair to decipher (and only decipher) and the other to encrypt (and only encrypt). Of course, in this schema, there is no longer the notion of "public" key exclusively used and widely distributed for the sole purpose of encryption. This can be of interest in specific cases of secret management. No ? $\endgroup$ Jul 21, 2020 at 13:47
  • $\begingroup$ @SAI Peregrinus: It's a bit crooked, but with RSA and ECC someone who decrypts a message can't prove that they didn't encrypt a message themselves. It could be useful to prove that any encrypted message received never came from the decryptor. $\endgroup$ Jul 21, 2020 at 13:54
  • 2
    $\begingroup$ You'd use signature generation for that, and you'd do it with the separate key pair of the sender rather than with the key pair of the receiver. $\endgroup$
    – Maarten Bodewes
    Jul 21, 2020 at 14:18
  • 2
    $\begingroup$ @Benoit LEGER-DERVILLE: what matters is that in all asymmetric algorithms, it is (computationally) impossible to get from the public key to the private key. I think it does not matter much if it is possible to go from private key to public key. Argument: That's not possible for RSA as originally defined, with random secret $d$ and private key $(N,d)$. That's possible with RSA as actually practiced, with moderate $e$ or private key with more components. Yet we seldom need to distinguish these two variants of RSA. $\endgroup$
    – fgrieu
    Jul 22, 2020 at 8:27
3
$\begingroup$

It is a mistake to think that the RSA keys can be interchanged. In all real systems the RSA public exponent is very small or even directly known. That means all the public key properties are known if the private key is known, as the private key contains the modulus - the only other part of that makes up the public key.

I'm not sure why you call the properties of OpenSSL "deceptive" here. OpenSSL keeps to the PKCS#1 standard, which has been created initially by RSA labs:

--
-- Representation of RSA private key with information for the CRT
-- algorithm.
--
RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e <-- >>> there it is <<<
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Similarly, with EC key pairs, the public key point is directly calculated from secret $s$ that forms the private key (together with the pre-established domain parameters). It's just a point multiplication with the base point of the parameters, to be exact. One reason why it is probably not stored with ECC private keys is that it is so easy to regenerate the public point that storage is not really required.

$\endgroup$
7
  • $\begingroup$ Thanks a lot. Yes, but during OpenSSL workshops with my students, we have to convince them that mathematically, given a private key with RSA, it is not possible to directly find the corresponding public key. Which, by the way, is a strength of RSA (possibility of giving on the one hand the ability to decipher without being able to encrypt for example). And I understand from your answer that ECCs work differently on this point. $\endgroup$ Jul 21, 2020 at 11:44
  • 1
    $\begingroup$ " Yes, but during OpenSSL workshops with my students, we have to convince them that mathematically, given a private key with RSA, it is not possible to directly find the corresponding public key. " No you don't and you shouldn't. Personally, you're better off explaining that the base operation performed with the public and private key is modular exponentiation, and keep it at that. That's also how PKCS#1 v2.0 explains it. The operations are mathematically identical (although in practice you'd use CRT parameters for the private key calculations). $\endgroup$
    – Maarten Bodewes
    Jul 21, 2020 at 12:01
  • $\begingroup$ Yes, thank you @Maarten Bodewes. But my main point was to understand (with your help :) that mathematically RSA and ECC differ intrinsically in the nature of their two keys (deductible or not from each other). This is a fundamental point for me in the existence of asymmetric algorithms. Regarding the implementations, I know as you do that the road is different, complex, etc. $\endgroup$ Jul 22, 2020 at 8:05
  • $\begingroup$ Sure, there are differences. But those differences are not in the way public and private key must be handled. As long as you make that clear, because as it stands you seem to be propagating a common myth. $\endgroup$
    – Maarten Bodewes
    Jul 22, 2020 at 8:09
  • $\begingroup$ I do not think I contribute to any myth? Quite the contrary, it is fundamental in my eyes, and as already said, I want to understand the algorithmic and mathematical basis of RSA and ECC with respect to their key pair. Mathematically with ECC one derives from the other by nature, and with the principle of modular exponentiation not with RSA maths. However, I have heard your warning about the implementation of the "official" RSA and the choices (I do not disagree) that were made. $\endgroup$ Jul 22, 2020 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.