Public-key Cryptography

The original version of this document had examples of using RSA cryptography with Python. However, RSA should be avoided for modern secure systems due to concerns with advancements in the discrete logarithm problem. While I haven’t written Python in a while, I have done some research into packages for elliptic curve cryptography (ECC). The most promising one so far is PyElliptic, by Yann GUIBET.

Public key cryptography is a type of cryptography that simplifies the key exchange problem: there is no need for a secure channel to communicate keys over. Instead, each user generates a private key with an associated public key. The public key can be given out without any security risk. There is still the challenge of distributing and verifying public keys, but that is outside the scope of this document.

With elliptic curves, we have two types of operations that we generally want to accomplish:

  • Digital signatures are the public key equivalent of message authentication codes. Alice signs a document using her private key, and users verify the signature against her public key.
  • Encryption with elliptic curves is done by performing a key exchange. Alice uses a function called elliptic curve Diffie-Hellman (ECDH) to generate a shared key to encrypt messages to Bob.

There are three curves we generally use with elliptic curve cryptography:

  • the NIST P256 curve, which is equivalent to an AES-128 key (also known as secp256r1)
  • the NIST P384 curve, which is equivalent to an AES-192 key (also known as secp384r1)
  • the NIST P521 curve, which is equivalent to an AES-256 key (also known as secp521r1)

Alternatively, there is the Curve25519 curve, which can be used for key exchange, and the Ed25519 curve, which can be used for digital signatures.

Generating Keys

Generating new keys with PyElliptic is done with the ECC class. As we used AES-256 previously, we’ll use P521 here.

1 import pyelliptic
2 
3 
4 def generate_key():
5     return pyelliptic.ECC(curve='secp521r1')

Public and private keys can be exported (i.e. for storage) using the accessors (the examples shown are for Python 2).

1 >>> key = generate_key()
2 >>> priv = key.get_privkey()
3 >>> type(priv)
4 str
5 >>> pub = key.get_pubkey()
6 >>> type(pub)
7 str

The keys can be imported when instantiating a instance of the ECC class.

1 >>> pyelliptic.ECC(privkey=priv)
2 <pyelliptic.ecc.ECC instance at 0x39ba2d8>
3 >>> pyelliptic.ECC(pubkey=pub)
4 <pyelliptic.ecc.ECC instance at 0x39ad9e0>

Signing Messages

Normally when we do signatures, we compute the hash of the message and sign that. PyElliptic does this for us, using SHA-512. Signing messages is done with the private key and some message. The algorithm used by PyElliptic for signatures is called ECDSA.

1 def sign(key, msg):
2     """Sign a message with the ECDSA key."""
3     return key.sign(msg)

In order to verify a message, we need the public key for the signing key, the message, and the signature. We’ll expect a serialised public key and perform the import to a pyelliptic.ecc.ECC instance internally.

1 def verify(pub, msg, sig):
2     """Verify the signature on a message."""
3     return pyelliptic.ECC(curve='secp521r1', pubkey=pub).verify(sig, msg)

Encryption

Using elliptic curves, we encrypt using a function that generates a symmetric key using a public and private key pair. The function that we use, ECDH (elliptic curve Diffie-Hellman), works such that:

1 ECDH(alice_pub, bob_priv) == ECDH(bob_pub, alice_priv)

That is, ECDH with Alice’s private key and Bob’s public key returns the same shared key as ECDH with Bob’s private key and Alice’s public key.

With pyelliptic, the private key used must be an instance of pyelliptic.ecc.ECC; the public key must be in serialised form.

1 >>> type(priv)
2 <pyelliptic.ecc.ECC instance at 0x39ba2d8>
3 >>> type(pub)
4 str
5 >>> shared_key = priv.get_ecdh_key(pub)
6 >>> len(shared_key)
7 64

Our shared key is 64 bytes; this is enough for AES-256 and HMAC-SHA-256. What about HMAC-SHA-256? We could use a short key, or we could expand the last 32 bytes of the key using SHA-384 (which produces a 48-byte hash). Here’s a function to do that:

1 def shared_key(priv, pub):
2     """Generate a new shared encryption key from a keypair."""
3     shared_key = priv.get_ecdh_key(pub)
4     shared_key = shared_key[:32] + SHA384.new(shared_key[32:]).digest()
5     return shared_key

Ephemeral keys

For improved security, we should use ephemeral keys for encryption; that is, we generate a new elliptic curve key pair for each encryption operation. This works as long as we send the public key with the message. Let’s look at a sample EC encryption function. For this function, we need the public key of our recipient, and we’ll pack our key into the beginning of the function. This method of encryption is called the elliptic curve integrated encryption scheme, or ECIES.

 1 import secretkey
 2 import struct
 3 
 4 def encrypt(pub, msg):
 5     """
 6     Encrypt the message to the public key using ECIES. The public key
 7     should be a serialised public key.
 8     """
 9     ephemeral = generate_key()
10     key = shared_key(ephemeral, pub)
11     ephemeral_pub = struct.pack('>H', len(ephemeral.get_public_key()))
12     ephemeral += ephemeral.get_public_key()
13     return ephemeral_pub+secretkey.encrypt(msg, key)

Encryption packs the public key at the beginning, writing first a 16-bit unsigned integer containing the public key length and then appending the ephemeral public key and the ciphertext to this. Decryption needs to unpack the ephemeral public key (by reading the length and extracting that many bytes from the message) and then decrypting the message with the shared key.

1 def decrypt(pub, msg):
2     """
3     Decrypt an ECIES-encrypted message with the private key.
4     """
5     ephemeral_len = struct.unpack('>H', msg[:2])
6     ephemeral_pub = msg[2:2+ephemeral_len]
7     key = shared_key(priv, ephemeral_pub)
8     return secretkey.decrypt(msg[2+ephemeral_len:], key)

Up next

Key Exchange