TransWikia.com

Are the asymmetric roles of the two keys in the elliptical curves the same (as for RSA)? Can they be interchanged indifferently?

Cryptography Asked by Benoit LEGER-DERVILLE on October 24, 2021

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

2 Answers

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.

Answered by Maarten Bodewes on October 24, 2021

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+Gcdots+G}_{dtext{ 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 $Qgets 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.

Answered by fgrieu on October 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP