The Basics of Crypto 9: Public Key Encryption

Public key encryption algorithms (such as RSA) have two keys, a public and a private key. Public keys are used for encryption and private keys are used for decryption. A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. This means anyone can have the public key in order to encrypt a message and send it to a recipient in full knowledge that only the recipient will be able to decrypt and read the message.

Public key cryptography is based on a mathematic function called a trapdoor function which is difficult to understand and mostly not of great importance in this context however you can read more about them here. In short a trapdoor function is very quick and easy to do in one direction and very difficult (almost impossible) to do in reverse.

Encryption with Public Key Algorithms

For the purposes of simplicity in this example we are going to work on one public key encryption scheme, specifically RSA. In order to encrypt with RSA securely we will need to implement it in optimal asymmetric encryption padding (OAEP) mode, this involves generating a random string with which to pad the message before the RSA algorithm is applied. The bit string should be as long as the message modulus. RSA without OAEP mode has numerous weaknesses and should not be implemented without OAEP mode being enabled.

In order to encrypt with RSA-OAEP you require a number of things: a message (encrypting nothing is a waste of time after all), a key (typically a symmetric key as found in AES), a PRNG and two hashing functions. A diagram displaying the algorithm can be seen below and a description behind the math behind the encryption algorithm can be found here:

Digital Signing with RSA

Digital signatures are used to prove that the owner of a private key has signed a particular message and that the signature is genuine. The usefulness of these keys is that only the holder of the private key can generate the signature however whoever has a copy of the public key can verify the signature. It is important to remember that digital signatures are not the same as encryption, it is fine for a digital signature to leak information about the message it was used to sign for example. Digital signatures (provided they meet certain requirements) can also be used as evidence in a court of law, more information on this can be found here.

Elliptic Curve Digital Signature Algorithm (ECDSA)

A more modern alternative to RSA is ECDSA which is slowly becoming the digital signature algorithm of choice for the modern world.

Bitcoin is a good example of a system that relies on ECDSA for security. Every Bitcoin address is a cryptographic hash of an ECDSA public key. The ownership of the account is determined by who controls the ECDSA private key. To transfer an amount of Bitcoin to another person, you create a message that says something along the lines of “I give this Bitcoin to address X”, sign it with your private key and submit it to the Bitcoin system. The linchpin of the security and consistency of the Bitcoin system is the security of ECDSA private keys.

Elliptic curves and ECDSA in particular are also used in messaging and systems security. Apple has stated that they use ECDSA extensively in the Apple ecosystem. Messages through iMessage are signed with ECDSA and iCloud keychain syncing relies on ECDSA.

The main difference between RSA and ECDSA is that breaking RSA requires you to factor large numbers and breaking ECDSA requires you to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) which is a significantly harder problem to solve. Furthermore we are continually getting better at factoring large numbers.