Public Key Cryptography and Digital Signatures

…simply explained

Public key cryptography:
Public key cryptography is a cryptographic system that uses private/public keys. The advantage of this approach is in not requiring some sort of secure channel for the initial exchange of secret keys between communicators. This makes secure communication with strangers on open networks possible.

The private key is a random hexadecimal number that must be kept private by the account holder.

A public key is another hexadecimal number which can be shared publicly.

Pick a number, any number

In most common encryption systems, the public and private keys are both generated at the same time. In others, the public key is generated from the private key. The public and private keys are associated with each other through a mathematical relationship. However, there is no way use the public key to figure out the private key. That is because these systems are based on math problems with no efficient solutions which can take outputs and work backwards from to get the original inputs.

RSA and Prime Numbers:
One example of a hard math problem providing security for an encryption system is found in the popular RSA cryptography system. RSA uses prime numbers to ensure security. A public key cryptographic system needs a set of algorithms that is easy to do in one direction, but difficult to undo. RSA uses an easy algorithm that multiplies two prime numbers.

If multiplication is the easy, then the difficult part is factoring the product of the multiplying those two primes.

A prime number is a natural number (aka whole number used in counting) greater than 1 and can only be divided by 1 and itself. Examples of prime numbers are 3, 5, 7, 11, 13, 17, etc.

A product is the result of multiplying two factors. Ex: A * B = C. 
The factors are A and B. The product is C.

A composite number is a positive integer that is formed when multiplying two or more other positive integers. Thus composite numbers are divisible by more than 1 and itself. When two primes (or any number of positive integers) are multiplied, we get a composite number.

Factoring out a number just means finding the numbers that make up the composite number.

Factoring out the two prime numbers that make up RSA’s 232 digits length number will take a very long time. However, generating and checking those two primes is relatively easy.

Algorithms that have this property, easy in one direction and hard in the other, are known as trapdoor functions. Other algorithms use other types of hard math problems with this one way property to provide security to their system. Ethereum uses something called Elliptical Curve Cryptography which will be described in a future post.

Digital signatures:
Simply, digital signatures are a way to validate the authenticity and integrity of any data. To create a digital signature, the signing software creates a one-way hash of the data to be signed. The private key is then used to encrypt the hash. This encrypted hash, plus other information like the hashing algorithm used, is the digital signature.

Public key cryptography with digital signatures:
A digital signature with public key cryptography securing a message is created in the following way. First, the message is digitally signed like explained above. Then, this bundle is encrypted with the sender’s private key, and again with the receiver’s public key

Looking at it like hypothetical function calls, it may look something like this:

public_key_of_recipient(private_key(message_hashing(message) + message + type of hashing algorithm))
Keep this a secret

Decrypting secured messages with digital signatures:
When the recipient receives the information, the recipient can decrypt the outer layer with his private key. This ensures that only the receiver can read the information. Then, the receiver can decrypt the inner layer with the sender’s public key. This assures that the sender was indeed the expected person. This is possible because the private and public keys are linked mathematically.

After decryption the receiver can verify the message was not tampered with en-route by running the message through same hashing algorithm as the sender. If they match, we have a valid message.