# Can I base a public-key cryptosystem only on a hash algorithm?

Could I base a public and private key system on just using a hashing algorithm? For example:

privKey = sha256( randomGenerator() )
pubKey = sha256( privKey )


Why do I need to use different algorithms? For example, RSA or ECC?

• It isn't clear how you intend to encrypt data with the hash function. What did you have in mind? Dec 9 '20 at 0:04
• I don't see how this poorly thought question deserve 2 upvotes and being a HNQ. Dec 9 '20 at 10:44
• This paper might be useful (specifically section 1.5) when the question is asking more for public-key encryption than asymmetric crypto in general.
– SEJPM
Dec 9 '20 at 12:19

I could base a public and private key system just using a hashing algorithm

Hash based signatures, such as Sphincs+, are essentially this (except that the relation between private key and public key is a tad more complicated.

However, to answer the question you appear to be answering: the problem with developing a public key cryptosystem is not just the relationship between the public and the private key. For public key encryption systems, there has to be a way for someone with the public key to encrypt a message (so someone can decrypt it if and only if they have the private key).

Similarly, for a public key signature system, there has to be a way to generate a signature (that works only if you have the private key), and anyone with the public key can verify it.

With your simple relationship, there is no way to use the public key to encrypt a message. And, while you can devise a way to use hash functions to sign a message, it is considerably more involved (because the only trick you have in validating a signature is revealing preimages; you can only do that once for each preimage, and hence you need a rather lot of cleverness to sign a number of messages.

There is actually a system for hash based signatures being standardized, see here.

Hou have described a system where the public key is derived from the private key in such a way that the private key cannot be recovered from the public key. However, it is unclear what operations you can perform with the public key that can only be reversed by persons having the private key. Without such operations the derived public key is useless.

Public keys and private keys do need to have a mathematical relation so that they can be used for encryption / decryption, key agreement or signature generation / verification. Such schemes are based on a specific mathematical problem such as the discrete logarithm problem (DLP) or the RSA problem - factorization of a number that is a product of two or more prime numbers.

The basic idea of public key cryptography goes beyond simply having two keys.

Instead you need the relationship between the keys and the algorithm that's used to allow data that's encrypted with the public key to be decrypted with the private key.

Most encryption algorithms use the same key for both encrypting and decrypting the data. In fact, for a long time most people who paid attention to cryptography at all never seem to have considered the possibility that cryptography could work any other way.

Public key cryptography uses one key for encrypting, and a different (but matching) key to decrypt that data.

I should probably add that there's also Diffie-Hellman key exchange. Since it accomplishes something similar, it's often discussed along with public key cryptography, and some people treat it as if it actually was public key cryptography. It's a little different though: it's a way for two people to exchange some data in a way that lets them create the same keys, but even if somebody else listens in on all the data they exchange, that third party can't reconstruct their key.

Like I said, that's not quite the same as PK cryptography, but it supports a roughly similar capability (A can send data to B securely, without secure channel to use to share the key), so it's often discussed together with it.

But again, Diffie-Hellman uses one fairly specific way of devising and exchanging information to work. Just generating one key, then doing something to generate another key from that isn't sufficient to do what it does.

• I think that digital signature generation / verification is a third one. That's not just the encryption with the private key that people seems to think (and indeed for PQC there are separate contests for each). To be honest, my answer isn't perfect either as it talks about "reversing the operation" with a key. Dec 9 '20 at 13:01
• @MaartenBodewes: though it's obviously related, I certainly wouldn't think of a digital signature as being the same as encryption (but yeah, closely enough related that I guess I can understand where some people would). Dec 10 '20 at 18:20