A Primer on Public-Key Cryptography

In preparation for a future post discussing Elliptic curve cryptography (ECC), I’d like to introduce the broader concept of public-key cryptography first. Though these concepts are general, I’ll use the RSA algorithm as an example of a public-key cryptography system. This will also help us motivate our discussion of ECC in the follow-up post.

Introduction

Cryptography is a branch of math and computer science that deals with securing information using codes or ciphers. It’s a crucial technology for the modern internet. Though not infallible, cryptography allows us to securely browse the web, shop, or make online banking transactions. And-as you may know-cryptography is also behind cryptocurrencies and blockchains, such as Bitcoin and Ethereum.

Working With a Public-Key Cryptosystem

We need two keys to work with a public-key cryptosystem. One is a public key and the other is a private key-a key is nothing but a long sequence of numbers and characters (e.g. a large hexadecimal number). The private key is to be kept secure, while the public key can be shared with others.

Encryption and decryption of a message using public-key cryptography (public domain).

The RSA Algorithm

The RSA algorithm is based on prime factorization, which is a computationally hard operation. From the fundamental theorem of arithmetic, we know that any number can be decomposed into the product of unique primes-this is called prime factorization. Current prime factorization algorithms are not efficient when dealing with large numbers. And, as the numbers get larger, the algorithm takes longer to complete.

Public/Private Key Generation

Since we’re dealing with physical computers, we need to determine the maximum value that our keys can take. This value represents the modulus which is used with modular arithmetic to keep our numbers within our range.

Encryption/Decryption

Let’s say you want to receive an important message-containing private information-from your friend Bob. So you decide to use RSA encryption. First, you generate the key pair as described above. You then share the public key with Bob, who will use it to encrypt the information as follows.

Cryptographic Signatures

Now, suppose you want to send an encrypted message to your friend Alice. You will use Alice’s public key to encrypt the message. However, she needs to make sure the message came from you. To accomplish this, you can use RSA to cryptographically sign the message. Then Alice can check the signature in the message to verify it came from you.

Shortcomings of the RSA Algorithm

As I mentioned earlier, the RSA algorithm relies on the problem of prime factorization being computationally hard. Prime factoring becomes increasingly hard as the number to factor gets larger. However, as more computing power is available, breaking the RSA cryptosystem–i.e. guessing the private key from the public key–is now possible if the numbers are not large enough.

Software Engineer. Endurance sports enthusiast. Blog: stemhash.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store