Introducing CryptoKit

Public-Key Cryptography

HMAC and Sealed Box encryption use symmetric keys, where the sender and receiver both know the key. Symmetric keys must be transmitted “out of band”. If you can’t do this securely, you use public-key cryptography. In fact, most of the routine encryption on the internet uses public-key cryptography, including whenever Xcode signs your app.

Public-key cryptography creates two mathematically linked keys. You keep your private key secret and publish the corresponding public key data. You sign data or its digest with your private key, then send it. The receiver creates a public key from your public key data, then uses it to check the signed data or digest.

For example, your app might need to authenticate an operation with your back-end server. On the user’s device, it creates a private key, which it stores in Keychain or SecureEnclave, then registers the corresponding public key on the server. When your user sets up the operation, your app signs the operation’s details with the user’s private key and sends the signed details to the server, which verifies it with the user’s public key.

To send encrypted data, you and your recipient each create a pair of keys and publish the public keys. Both of you then combine your private key with the other’s public key to create a shared secret. Both of you use this shared secret to derive the same symmetric key, which you can then use for AEAD as described in the previous section.

Creating Private and Public Keys

The key feature of public-key cryptography is that it uses trapdoor algorithms: It’s very very difficult to compute the private key from the public key.

After its publication in 1978, RSA (Rivest-Shamir-Adleman) became the most popular public-key algorithm. It relies on the difficulty of determining the two prime number factors of a very, very, very large number. Other mathematicians rose to the challenge, developing factoring algorithms that could only be held at bay by increasing the size of the keys. Generating RSA keys is slow, and the time increases with key size. Eventually, factoring algorithms improved faster than the power of mobile devices to compute with very large numbers. Attention turned to another technology, which is proving much harder to attack.

ECC (Elliptic Curve Cryptography), first suggested in 1985, has been widely used since 2004 and became the preferred technology on servers at the end of 2015. ECC keys are much smaller than RSA keys with similar security: for example, the security of a 256-bit ECC public key is comparable to a 3072-bit RSA public key.

CryptoKit uses ECC algorithms exclusively. Your options here are NIST’s P256/P384/P521 or Daniel J. Bernstein’s Curve25519. P256 is by far the most widely used curve. It’s the default curve for OpenSSL, where it’s known as prime256v1. P384 requires 2-3 times as much computation as P256. The U.S. National Security Agency (NSA) requires P384 to protect top-secret information. P256 and P384 are in the NSA’s Suite B Cryptography, but P521 isn’t, and I couldn’t find any information about who uses it. Super-spooks, perhaps?

Bernstein released Curve25519 the same year as the NSA’s Suite B, but its popularity increased after whistleblower Edward Snowden released internal memos in 2013 suggesting the NSA had inserted a cryptographic back door into the elliptic curve-based pseudo random generator Dual_EC_DRBG. Both Dual_EC_DRBG and P256 rely on Nothing Up My Sleeve (NUMS) magic numbers. The cryptographic community suspected the NSA used special values to derive these magic numbers, enabling them to decrypt anything encrypted with P256. Curve25519 doesn’t rely on magic numbers. Its computational complexity is 40% lower than P256. And the 2018 TLS 1.3 standard requires support for it.

Many articles, like this one, use small prime number arithmetic to explain RSA in a way that’s easy to understand. The algorithm is quite clever.

Elliptic curve cryptography is even better! But a little more complicated to explain.

An elliptic curve consists of the (x,y) points satisfying an equation of this form:

y^2 = x^3 + ax + b

For example, y^2 = x^3 - x + 1 looks like this:

Graph of an elliptic curve

Graph of an elliptic curve

You can graph more elliptic curves at Desmos Graphing Calculator.

ECC uses two properties of elliptic curves:

1. Any non-vertical line intersects the graph at no more than three points.
2. The graph is symmetric around the x-axis.

These properties let you define a dot operation between any two points on the graph:

1. Draw a line between points A and B.
2. Where this line hits the graph at a third point, reflect across the x-axis to get point C = A dot B.

elliptic curve A dot B operation

elliptic curve A dot B operation

You can also define the point multiplication operation k * A, where k is a positive integer.

1. Start with A dot A to get point B: Draw the tangent line to the curve at point A and reflect across the x-axis where this line hits the graph. This is the first dot operation.
2. Now do A dot B to get point C, then A dot C = D, and so on. Do a total of k dot operations, ending at point P. If you tell someone where points A and P are, it’s really hard for them to calculate k.

The actual algorithm uses only integer values of x and y, modulo a prime number n. The start point is called the generator, so it’s usually named G. It has the property that n * G = G.

To set up an ECC cryptosystem, you pick a curve equation (the coefficient of x and the constant b), a generator point G on this curve and its corresponding prime number n. The private key is a randomly selected number k, and the public key is k * G — the endpoint on the curve after k dot operations on G.

Of course, you don’t need to do any of this. There are already standard curves like Curve25519 and those used by the NIST ECCs, and these are implemented in CryptoKit’s public-key methods.