# Public-private algorithm where it is not possible to recover public key from private key?

Is there an asymmetric algorithm where it is not possible to extract a public key from private key? So far any algorithms I tried (dsa, rsa, ecdsa, ed25519) successfully recover their public keys from private ones with 'ssh-keygen -y -f private.key'.

• Why would you want a construction like this (what are you actually trying to accomplish)? It's pretty much contrary to the very definition of public-key cryptography. – Ella Rose Aug 20 '18 at 15:29
• @EllaRose I would like the recipient to decipher the message, but not encrypt it. – Ulex Aug 21 '18 at 8:34
• I can only guess, but you are proposing a solution instead of your actual goal, a typical XY problem. What is your actual goal? To make sure the message comes from a specific sender? There are better ways than ignoring the definition of the word public in public keys. – tylo Aug 21 '18 at 11:15
• @tylo i have one to many connectivity between $A$and $C_1...C_n$, where $A$ signs and encrypts a message that is sent to $C_1...C_n$. $C_1...C_n$ share private key. I'm using $A$'s private key to sign the message so $C$ can confirm it came from $A$ by checking the public key. However, I would like minimise the nuisance of $C_k$ sending a message to $C_l$ and making $C_I$ waste resources deciphering the messages (which will fail a subsequent signature verification anyway). I thought that by hiding the 'public' part of the key I can achieve something like this. Is there a better way? – Ulex Aug 21 '18 at 12:58
• Sharing private keys is a terrible idea, and your basic assumption is, that none of your parties is corrupted or malicious. So as soon as that's not the case, your security is broken. The 'nuisance' is not the problem: if you have any party with bad intentions, your entire security is gone. – tylo Aug 22 '18 at 14:59

RSA as initialy described (R.L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM, 1978) has this property that it is impossible to find the public key $(N,e)$ from the private key expressed as $(N,d)$. For modern parameters, pick random primes $p$ and $q$ in range $[2^{2047.5},2^{2048}]$, pick random $4095$-bit $d$ with $\gcd(p-1,d)=1=\gcd(q-1,d)$, compute $N=p\,q$ and $e=d^{-1}\bmod((p-1)(q-1))$, keep the private key $(N,d)$ and separately the public key $(N,e)$, but destroy $p$, $q$, and $(p-1)(q-1)$.

Note: While that original RSA system does not allow "to extract a public key from private key", it is still possible to test if public and private key match; that seems unavoidable for any public-key cryptosystem, be it for encryption or signature.

Modern RSA has $e$ (and often $p$ and $q$) in the private key, because

• it is generally a feature that the public key can be extracted from the private key
• having $p$ and $q$ allows to speed up private-key operation considerably
• having $e$ allows to verify computations made with the private key, which is useful to guard against some attacks.

Also, modern RSA typically uses small $e$ (often $2^{(2^k)}+1$ for $0\le k\le4$) and that makes guessing $e$ and verifying the guess trivial.

• It is arguable that $p$ and $q$ are part of the private key, and that this is simply throwing away part of the private key after deriving the public key from it (e.g. you could not derive $e$ without $p, q$ at all). Still, this is surely the closest OP can come to what they think they want, so +1 for that. – Ella Rose Aug 20 '18 at 15:41
• @Ella Rose: indeed, that method requires a trusted party to generate and distribute the private key, and the secret "public" key. For the reasons in your answer, I can't think of a method that does not. – fgrieu Aug 20 '18 at 15:53
• @EllaRose "It is arguable that $p$ and $q$ are part of the private key" No, it is not. The private key is exactly what the definition of the key generation algorithm says it is; if it says that the private key is $(N,d)$, then the private key is $(N,d)$, period. You can consider another encryption scheme where the private key is $(N,p,q,d)$, and even argue that it is "equivalent", but it is not the same. – fkraiem Aug 20 '18 at 17:11
• Although ssh-keygen in specific is (essentially always) part of OpenSSH which uses RSA in full PKCS1-CRT form which does allow trivial 'recovery' of e, as well as always using small e anyway (formerly 35, now 65537=F4) – dave_thompson_085 Aug 21 '18 at 2:24

Is there an asymmetric algorithm where it is not possible to extract a public key from private key?

No. The public key is not recovered from the private key, it is generated using the private key.

The inability to generate a public key from a private key implies the inability to have a public key that is linked with the private key. Hence you cannot have an asymmetric cryptosystem.

If you were hoping to to select a public key first and generate a private key from that, it cannot work that way: If you could do so using only the information of the public key, then so could anyone else, and therefore your "private" key would not be "private".

• No, the public key is not generated using the private key. Both keys are generated from the internal randomness of the key generation algorithm. – fkraiem Aug 20 '18 at 16:26