Asymmetric Encryption: Elliptic Curve Cryptography

Elliptic Curve (EC) cryptography has become increasingly popular. RSA was invented first and was easier to vet mathematically, but EC cryptography has survived decades of inspection and it is increasingly being used. One benefit of EC is that it provides better security with smaller key sizes.

Learning Objectives

You should be able to:

  • Explain the basic concepts of EC security
  • Use OpenSSH to create an EC key pair

Video Walkthrough

Use this video to follow along with the steps in this lab.

Elliptic Curve Cryptography Principles

The following is a simplified explanation of how keys are generated in elliptic curve cryptography. EC cryptography's security comes from the challenge of determining how lines traverse special curves.

Consider the following curve on a graph.

Sample elliptic curve graph

The curve is defined by a formula (something like y^2 = x^3 + 7). There is a generator point G, which can be considered a starting point, which is part of a curve's parameters. The private key is a random number in a range defined in the curve's parameters. For example, a curve might tell people to pick a number between 17 and 2^255. For simplicity's sake, imagine that we randomly came up with the number 6 as our random number. We would start at point G and follow specific rules for hopping around the curve. The image below shows what 6 "hops" would look like.

Public key on a curvey where the private key is 6

So, given a curve with the starting point G, we pick a random number, and that random number will correspond to a public key point on the curve. A key concept in EC cryptography is that if we are given a random point on the curve, it is tremendously difficult to determine how many hops it took to get there. There is no easy way to find the private key when given the public key.

In reality, your computer does not "hop" trillions of times to determine the public key. EC cryptography is computationally efficient. Essentially, a single multiplication operation can be done to compute the public key.

Exercise

Next, you will create an EC key pair using OpenSSH. OpenSSH is commonly used on the internet for secure communications.

  • Launch your Linux virtual machine and access the terminal.
  • Navigate to your home directory with the following command:
cd ~
  • Run the following command to launch the key creation process with OpenSSH.
ssh-keygen -t ed25519
  • The ed25519 refers to a specific curve specification.
  • You will be prompted to enter optional information. Simply press enter to accept the defaults. You can leave the password empty.
  • You should see output similar to the following.

Elliptic curve key pair created with OpenSSH

  • You will notice a "randomart" image. This image is supposed to make it easier for you to recognize that the correct key is being shared. For example, if you logged onto a server, and the server presented the same randomart image, that could give you more confidence that you are connecting to the right service. The randomart image is a representation of the public key and can be shared. Below is a different randomart image than the one shown in the previous key generation process.
The key's randomart image is:
|       .++++==+**|
|        .+.ooO**=|
|        o o.Oo*.+|
|       . . . B.= |
|        S   ..+. |
|         .   .+ .|
|           . . o.|
|          E +   .|
|           +     |
  • Note that the key pair was created very quickly. Though benchmarks for creating keys is tricky, a ballpark number is that it's about 1,000 times faster to create an EC key than an RSA key for equivalent security.
  • Navigate to the hidden .ssh directory and use cat to display the contents of the private key and the public key. The public key has a .pub extension. The private key has no extension.
cd .ssh
cat id_ed25519
cat id_ed25519.pub

You should see something similar to the following.

Elliptic curve key contents

It is important to note that the public key really just represents a point on the curve. The private key is just a large number.

Reflection

  • How can we be sure that the math behind elliptic curve cryptography is sound?
  • Will quantum computers just break all of your current cryptography algorithms?

Key Terms

  • OpenSSH: An open-source implementation of the Secure Shell (SSH) protocol, providing encrypted communication sessions over a computer network. OpenSSH includes tools for secure remote login, file transfer, and tunneling, and it is widely used for secure access to remote systems.
  • Curve ed25519: A specific elliptic curve used in public-key cryptography, known for its high performance and security. Ed25519 is used for creating digital signatures and is part of the EdDSA (Edwards-curve Digital Signature Algorithm). It is favored for its speed, security, and resistance to certain types of cryptographic attacks.
  • Elliptic Curve Private Key: A secret value used in elliptic curve cryptography (ECC) that is known only to the owner. It is a randomly selected number that serves as the basis for generating the corresponding public key. The private key is used for decrypting data and creating digital signatures.
  • Elliptic Curve Public Key: A value derived from the elliptic curve private key using a mathematical function based on elliptic curve operations. The public key can be shared openly and is used for encrypting data and verifying digital signatures. It is computationally infeasible to derive the private key from the public key, ensuring the security of the cryptographic system.