# A Working Intro to Cryptography

## Table of Contents

## Introduction

Recently at work I have been using the PyCrypto libraries quite a bit. The documentation is pretty good, but there are a few areas that took me a bit to figure out. In this post, I’ll be writing up a quick overview of the PyCrypto library and cover some general things to know when writing cryptographic code in general. I’ll go over symmetric, public-key, hybrid, and message authentication codes. Keep in mind this is a quick introduction and a lot of gross simplifications are made. For a more complete introduction to cryptography, take a look at the references at the end of this article. This article is just an appetite-whetter - if you have a real need for information security you should hire an expert. Real data security goes beyond this quick introduction (you wouldn’t trust the design and engineering of a bridge to a student with a quick introduction to civil engineering, would you?)

Some quick terminology: for those unfamiliar, I introduce the following terms:

- plaintext: the original message
- ciphertext: the message after cryptographic transformations are applied to obscure the original message.
- encrypt: producing ciphertext by applying cryptographic transformations to plaintext.
- decrypt: producing plaintext by applying cryptographic transformations to ciphertext.
- cipher: a particular set of cryptographic transformations providing means of both encryption and decryption.
- hash: a set of cryptographic transformations that take a large input and transform it to a unique (typically fixed-size) output. For hashes to be cryptographically secure, collisions should be practically nonexistent. It should be practically impossible to determine the input from the output.

Cryptography is an often misunderstood component of information security, so an overview of what it is and what role it plays is in order. There are four major roles that cryptography plays:

- confidentiality: ensuring that only the intended recipients receive the plaintext of the message.
- data integrity: the plaintext message arrives unaltered.
- entity authentication: the identity of the sender is verified. An entity may be a person or a machine.
- message authentication: the message is verified as having been unaltered.

Note that cryptography is used to obscure the contents of a message
and verify its contents and source. It will **not** hide the fact that
two entities are communicating.

There are two basic types of ciphers: symmetric and public-key ciphers. A symmetric key cipher employs the use of shared secret keys. They also tend to be much faster than public-key ciphers. A public-key cipher is so-called because each key consists of a private key which is used to generate a public key. Like their names imply, the private key is kept secret while the public key is passed around. First, I’ll take a look at a specific type of symmetric ciphers: block ciphers.

## Block Ciphers

There are two further types of symmetric keys: stream and block
ciphers. Stream ciphers operate on data streams, i.e. one byte at a
time. Block ciphers operate on blocks of data, typically 16 bytes at a
time. The most common block cipher and the standard one you should use
unless you have a very good reason to use another one is the
AES
block cipher, also documented in
FIPS PUB 197. AES
is a specific subset of the Rijndael cipher. AES uses block size of
128-bits (16 bytes); data should be padded out to fit the block size -
the length of the data block must be multiple of the block size. For
example, given an input of `ABCDABCDABCDABCD ABCDABCDABCDABCD`

no
padding would need to be done. However, given ```
ABCDABCDABCDABCD
ABCDABCDABCD
```

an additional 4 bytes of padding would need to be
added. A common padding scheme is to use `0x80`

as the first byte of
padding, with `0x00`

bytes filling out the rest of the padding. With
padding, the previous example would look like: ```
ABCDABCDABCDABCD
ABCDABCDABCD\x80\x00\x00\x00
```

.

Here’s our padding function:

` 1`

`def`

`pad_data`

`(`

`data`

`):`

` 2`

`# return data if no padding is required`

` 3`

`if`

`len`

`(`

`data`

`)`

`%`

`16`

`==`

`0`

`:`

` 4`

`return`

`data`

` 5`

` 6`

`# subtract one byte that should be the 0x80`

` 7`

`# if 0 bytes of padding are required, it means only`

` 8`

`# a single \x80 is required.`

` 9`

`10`

`padding_required`

`=`

`15`

`-`

`(`

`len`

`(`

`data`

`)`

`%`

`16`

`)`

`11`

`12`

`data`

`=`

`'`

`%s`

`\x80`

`'`

`%`

`data`

`13`

`data`

`=`

`'`

`%s%s`

`'`

`%`

`(`

`data`

`,`

`'`

`\x00`

`'`

`*`

`padding_required`

`)`

`14`

`15`

`return`

`data`

Our function to remove padding is similar:

`1`

`def`

`unpad_data`

`(`

`data`

`)`

`:`

`2`

`if`

`not`

`data`

`:`

`3`

`return`

`data`

`4`

`5`

`data`

`=`

`data`

`.`

`rstrip`

`(`

`'\x00'`

`)`

`6`

`if`

`data`

`[`

`-`

`1`

`]`

`==`

`'\x80':`

`7`

`return`

`data`

`[:-`

`1`

`]`

`8`

`else`

`:`

`9`

`return`

`data`

Encryption with a block cipher requires selecting a
block mode. By far
the most common mode used is **cipher block chaining** or *CBC* mode.
Other modes include *counter (CTR)*, *cipher feedback (CFB)*, and the
extremely insecure *electronic codebook (ECB)*. CBC mode is the
standard and is well-vetted, so I will stick to that in this tutorial.
Cipher block chaining works by XORing the previous block of ciphertext
with the current block. You might recognise that the first block has
nothing to be XOR’d with; enter the
*initialisation vector*.
This comprises a number of randomly-generated bytes of data the same
size as the cipher’s block size. This initialisation vector should
random enough that it cannot be recovered.

One of the most critical components to encryption is properly
generating random data. Fortunately, most of this is handled by the
PyCrypto library’s `Crypto.Random.OSRNG module`

. You should know that
the more entropy sources that are available (such as network traffic
and disk activity), the faster the system can generate
cryptographically-secure random data. I’ve written a function that can
generate a
*nonce*
suitable for use as an initialisation vector. This will work on a UNIX
machine; the comments note how easy it is to adapt it to a Windows
machine. This function requires a version of PyCrypto at least 2.1.0
or higher.

`1`

`import`

`Crypto.Random.OSRNG.posix`

`as`

`RNG`

`2`

`3`

`def`

`generate_nonce`

`():`

`4`

`"""Generate a random number used once."""`

`5`

`return`

`RNG`

`.`

`new`

`()`

`.`

`read`

`(`

`AES`

`.`

`block_size`

`)`

I will note here that the python `random`

module is completely
unsuitable for cryptography (as it is completely deterministic). You
shouldn’t use it for cryptographic code.

Symmetric ciphers are so-named because the key is shared across any entities. There are three key sizes for AES: 128-bit, 192-bit, and 256-bit, aka 16-byte, 24-byte, and 32-byte key sizes. Instead, we just need to generate 32 random bytes (and make sure we keep track of it) and use that as the key:

`1`

`KEYSIZE`

`=`

`32`

`2`

`3`

`4`

`def`

`generate_key`

`():`

`5`

`return`

`RNG`

`.`

`new`

`()`

`.`

`read`

`(`

`KEY_SIZE`

`)`

We can use this key to encrypt and decrypt data. To encrypt, we need the initialisation vector (i.e. a nonce), the key, and the data. However, the IV isn’t a secret. When we encrypt, we’ll prepend the IV to our encrypted data and make that part of the output. We can (and should) generate a completely random IV for each new message.

` 1`

`import`

`Crypto.Cipher.AES`

`as`

`AES`

` 2`

` 3`

`def`

`encrypt`

`(`

`data`

`,`

`key`

`):`

` 4`

`"""`

` 5`

` Encrypt data using AES in CBC mode. The IV is prepended to the`

` 6`

` ciphertext.`

` 7`

` """`

` 8`

`data`

`=`

`pad_data`

`(`

`data`

`)`

` 9`

`ivec`

`=`

`generate_nonce`

`()`

`10`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`,`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

`11`

`ctxt`

`=`

`aes`

`.`

`encrypt`

`(`

`data`

`)`

`12`

`return`

`ivec`

`+`

`ctxt`

`13`

`14`

`15`

`def`

`decrypt`

`(`

`ciphertext`

`,`

`key`

`):`

`16`

`"""`

`17`

` Decrypt a ciphertext encrypted with AES in CBC mode; assumes the IV`

`18`

` has been prepended to the ciphertext.`

`19`

` """`

`20`

`if`

`len`

`(`

`ciphertext`

`)`

`<=`

`AES`

`.`

`block_size`

`:`

`21`

`raise`

`Exception`

`(`

`"Invalid ciphertext."`

`)`

`22`

`ivec`

`=`

`ciphertext`

`[:`

`AES`

`.`

`block_size`

`]`

`23`

`ciphertext`

`=`

`ciphertext`

`[`

`AES`

`.`

`block_size`

`:]`

`24`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`,`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

`25`

`data`

`=`

`aes`

`.`

`decrypt`

`(`

`ciphertext`

`)`

`26`

`return`

`unpad_data`

`(`

`data`

`)`

However, this is only part of the equation for securing messages: AES only gives us confidentiality. Remember how we had a few other criteria? We still need to add integrity and authenticity to our process. Readers with some experience might immediately think of hashing algorithms, like MD5 (which should be avoided like the plague) and SHA. The problem with these is that they are malleable: it is easy to change a digest produced by one of these algorithms, and there is no indication it’s been changed. We need, a hash function that uses a key to generate the digest; the one we’ll use is called HMAC. We do not want the same key used to encrypt the message; we should have a new, freshly generated key that is the same size as the digest’s output size (although in many cases, this will be overkill).

In order to encrypt properly, then, we need to modify our code a bit. The first thing you need to know is that HMAC is based on a particular SHA function. Since we’re using AES-256, we’ll use SHA-384. We say our message tags are computed using HMAC-SHA-384. This produces a 48-byte digest. Let’s add a few new constants in, and update the KEYSIZE variable:

`1`

`__aes_keylen`

`=`

`32`

`2`

`__tag_keylen`

`=`

`48`

`3`

`KEYSIZE`

`=`

`__aes_keylen`

`+`

`__tag_keylen`

Now, let’s add message tagging in:

`1`

`import`

`Crypto.Hash.HMAC`

`as`

`HMAC`

`2`

`import`

`Crypto.Hash.SHA384`

`as`

`SHA384`

`3`

`4`

`5`

`def`

`new_tag`

`(`

`ciphertext`

`,`

`key`

`):`

`6`

`"""Compute a new message tag using HMAC-SHA-384."""`

`7`

`return`

`HMAC`

`.`

`new`

`(`

`key`

`,`

`msg`

`=`

`ciphertext`

`,`

`digestmod`

`=`

`SHA384`

`)`

`.`

`digest`

`()`

Here’s our updated encrypt function:

` 1`

`def`

`encrypt`

`(`

`data`

`,`

`key`

`):`

` 2`

`"""`

` 3`

` Encrypt data using AES in CBC mode. The IV is prepended to the`

` 4`

` ciphertext.`

` 5`

` """`

` 6`

`data`

`=`

`pad_data`

`(`

`data`

`)`

` 7`

`ivec`

`=`

`generate_nonce`

`()`

` 8`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__aes_keylen`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

` 9`

`ctxt`

`=`

`aes`

`.`

`encrypt`

`(`

`data`

`)`

`10`

`tag`

`=`

`new_tag`

`(`

`ivec`

`+`

`ctxt`

`,`

`key`

`[`

`__aes_keylen`

`:])`

`11`

`return`

`ivec`

`+`

`ctxt`

`+`

`tag`

Decryption has a snag: what we want to do is check to see if the
message tag matches what we think it should be. However, the Python
`==`

operator stops matching on the first character it finds that
doesn’t match. This opens a verification based on the `==`

operator to
a timing attack. Without going into much detail, note that several
cryptosystems have fallen prey to this exact attack; the keyczar
system, for example, use the `==`

operator and suffered an attack on
the system. We’ll use the `streql`

package (i.e. `pip install streql`

)
to perform a constant-time comparison of the tags.

` 1`

`import`

`streql`

` 2`

` 3`

` 4`

`def`

`verify_tag`

`(`

`ciphertext`

`,`

`key`

`):`

` 5`

`"""Verify the tag on a ciphertext."""`

` 6`

`tag_start`

`=`

`len`

`(`

`ciphertext`

`)`

`-`

`__taglen`

` 7`

`data`

`=`

`ciphertext`

`[:`

`tag_start`

`]`

` 8`

`tag`

`=`

`ciphertext`

`[`

`tag_start`

`:]`

` 9`

`actual_tag`

`=`

`new_tag`

`(`

`data`

`,`

`key`

`)`

`10`

`return`

`streql`

`.`

`equals`

`(`

`actual_tag`

`,`

`tag`

`)`

We’ll also change our decrypt function to return a tuple: the original message (or None on failure), and a boolean that will be True if the tag was authenticated and the message decrypted

` 1`

`def`

`decrypt`

`(`

`ciphertext`

`,`

`key`

`):`

` 2`

`"""`

` 3`

` Decrypt a ciphertext encrypted with AES in CBC mode; assumes the IV`

` 4`

` has been prepended to the ciphertext.`

` 5`

` """`

` 6`

`if`

`len`

`(`

`ciphertext`

`)`

`<=`

`AES`

`.`

`block_size`

`:`

` 7`

`return`

`None`

`,`

`False`

` 8`

`tag_start`

`=`

`len`

`(`

`ciphertext`

`)`

`-`

`__TAG_LEN`

` 9`

`ivec`

`=`

`ciphertext`

`[:`

`AES`

`.`

`block_size`

`]`

`10`

`data`

`=`

`ciphertext`

`[`

`AES`

`.`

`block_size`

`:`

`tag_start`

`]`

`11`

`if`

`not`

`verify_tag`

`(`

`ciphertext`

`,`

`key`

`[`

`__AES_KEYLEN`

`:]):`

`12`

`return`

`None`

`,`

`False`

`13`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__AES_KEYLEN`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

`14`

`data`

`=`

`aes`

`.`

`decrypt`

`(`

`data`

`)`

`15`

`return`

`unpad_data`

`(`

`data`

`),`

`True`

We could also generate a key using a passphrase; to do so, you should use a key derivation algorithm, such as PBKDF2. A function to derive a key from a passphrase will also need to store the salt that goes with the passphrase. PBKDf2 takes three arguments: the passphrase, the salt, and the number of iterations to run through. The currently recommended minimum number of iterations in 16384; this is a sensible default for programs using PBKDF2.

What is a salt? A salt is a randomly generated value used to make sure the output of two runs of PBKDF2 are unique for the same passphrase. Generally, this should be a minimum of 16 bytes (128-bits).

Here are two functions to generate a random salt and generate a secret key from PBKDF2:

` 1`

`import`

`pbkdf2`

` 2`

`def`

`generate_salt`

`(`

`salt_len`

`):`

` 3`

`"""Generate a salt for use with PBKDF2."""`

` 4`

`return`

`RNG`

`.`

`new`

`()`

`.`

`read`

`(`

`salt_len`

`)`

` 5`

` 6`

` 7`

`def`

`password_key`

`(`

`passphrase`

`,`

`salt`

`=`

`None`

`):`

` 8`

`"""Generate a key from a passphrase. Returns the tuple (salt, key)."""`

` 9`

`if`

`salt`

`is`

`None`

`:`

`10`

`salt`

`=`

`generate_salt`

`(`

`16`

`)`

`11`

`passkey`

`=`

`pbkdf2`

`.`

`PBKDF2`

`(`

`passphrase`

`,`

`salt`

`,`

`iterations`

`=`

`16384`

`)`

`.`

`read`

`(`

`KEYSIZE`

`)`

`12`

`return`

`salt`

`,`

`passkey`

Keep in mind that the salt, while a public and non-secret value, must
be present to recover the key. To generate a new key, pass `None`

as
the salt value, and a random salt will be generated. To recover the
same key from the passphrase, the salt must be provided (and it must
be the same salt generated when the passphrase key is generated). As
an example, the salt could be provided as the first `len(salt)`

bytes
of the ciphertext.

That should cover the basics of block cipher encryption. We’ve
gone over key generation, padding, and encryption / decryption. This
code has been packaged up in the example source directory as `secretkey`

.

## ASCII-Armouring

I’m going to take a quick detour and talk about ASCII armouring. If
you’ve played with the crypto functions above, you’ll notice they
produce an annoying dump of binary data that can be a hassle to
deal with. One common technique for making the data a little bit
easier to deal with is to encode it with base64. There are a
few ways to incorporate this into python:
{Absolute Base64 Encoding}The easiest way is to just base64 encode
everything in the encrypt function. Everything that goes into the
decrypt function should be in base64 - if it’s not, the `base64`

module will throw an error: you could catch this and then try to
decode it as binary data.

### A Simple Header

A slightly more complex option, and the one I adopt in this
article, is to use a `\x00`

as the first byte of the ciphertext for
binary data, and to use `\x41`

(an ASCII “`A`

”) for ASCII encoded
data. This will increase the complexity of the encryption and
decryption functions slightly. We’ll also pack the initialisation
vector at the beginning of the file as well. Given now that the
`iv`

argument might be `None`

in the decrypt function, I will have
to rearrange the arguments a bit; for consistency, I will move it
in both functions. My modified functions look like this now:

` 1`

`def`

`encrypt`

`(`

`data`

`,`

`key`

`,`

`armour`

`=`

`False`

`):`

` 2`

`"""`

` 3`

` Encrypt data using AES in CBC mode. The IV is prepended to the`

` 4`

` ciphertext.`

` 5`

` """`

` 6`

`data`

`=`

`pad_data`

`(`

`data`

`)`

` 7`

`ivec`

`=`

`generate_nonce`

`()`

` 8`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__AES_KEYLEN`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

` 9`

`ctxt`

`=`

`aes`

`.`

`encrypt`

`(`

`data`

`)`

`10`

`tag`

`=`

`new_tag`

`(`

`ivec`

`+`

`ctxt`

`,`

`key`

`[`

`__AES_KEYLEN`

`:])`

`11`

`if`

`armour`

`:`

`12`

`return`

`'`

`\x41`

`'`

`+`

`(`

`ivec`

`+`

`ctxt`

`+`

`tag`

`)`

`.`

`encode`

`(`

`'base64'`

`)`

`13`

`else`

`:`

`14`

`return`

`'`

`\x00`

`'`

`+`

`ivec`

`+`

`ctxt`

`+`

`tag`

`15`

`16`

`def`

`decrypt`

`(`

`ciphertext`

`,`

`key`

`):`

`17`

`"""`

`18`

` Decrypt a ciphertext encrypted with AES in CBC mode; assumes the IV`

`19`

` has been prepended to the ciphertext.`

`20`

` """`

`21`

`if`

`ciphertext`

`[`

`0`

`]`

`==`

`'`

`\x41`

`'`

`:`

`22`

`ciphertext`

`=`

`ciphertext`

`[`

`1`

`:]`

`.`

`decode`

`(`

`'base64'`

`)`

`23`

`else`

`:`

`24`

`ciphertext`

`=`

`ciphertext`

`[`

`1`

`:]`

`25`

`if`

`len`

`(`

`ciphertext`

`)`

`<=`

`AES`

`.`

`block_size`

`:`

`26`

`return`

`None`

`,`

`False`

`27`

`tag_start`

`=`

`len`

`(`

`ciphertext`

`)`

`-`

`__TAG_LEN`

`28`

`ivec`

`=`

`ciphertext`

`[:`

`AES`

`.`

`block_size`

`]`

`29`

`data`

`=`

`ciphertext`

`[`

`AES`

`.`

`block_size`

`:`

`tag_start`

`]`

`30`

`if`

`not`

`verify_tag`

`(`

`ciphertext`

`,`

`key`

`[`

`__AES_KEYLEN`

`:]):`

`31`

`return`

`None`

`,`

`False`

`32`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__AES_KEYLEN`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

`33`

`data`

`=`

`aes`

`.`

`decrypt`

`(`

`data`

`)`

`34`

`return`

`unpad_data`

`(`

`data`

`),`

`True`

### A More Complex Container

There are more complex ways to do it (and youâ€™ll see it with the public keys in the next section) that involve putting the base64 into a container of sorts that contains additional information about the key.

## 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`

`)`

## Key Exchange

So how does Bob know the key actually belongs to Alice? There are two
main schools of thought regarding the authentication of key ownership:
centralised and decentralised. TLS/SSL follow the centralised school:
a root certificate^{1} authority (CA) signs intermediary CA
keys, which then sign user keys. For example, if Bob runs Foo Widgets,
LLC, he can generate an SSL keypair. From this, he generates a
certificate signing request, and sends this to the CA. The CA, usually
after taking some money and ostensibly actually verifying Bob’s
identity^{2}, then signs Bob’s certificate. Bob sets up his
webserver to use his SSL certificate for all secure traffic, and Alice
sees that the CA did in fact sign his certificate. This relies on
trusted central authorities, like VeriSign^{3} Alice’s web
browser would ship with a keystore of select trusted CA public keys
(like VeriSigns) that she could use to verify signatures on the
certificates from various sites. This system is called a public key
infrastructure. The other school of thought is followed by PGP^{4} -
the decentralised model.

In PGP, this is manifested as the Web of Trust^{5}. For example, if
Carol now wants to talk to Bob and gives Bob her public key, Bob can
check to see if Carol’s key has been signed by anyone else. We’ll also
say that Bob knows for a fact that Alice’s key belongs to Alice, and
he trusts her^{6}, and that Alice has signed Carol’s key. Bob sees
Alice’s signature on Carol’s key and then can be reasonably sure that
Carol is who she says it was. If we repeat the process with Dave,
whose key was signed by Carol (whose key was signed by Alice), Bob
might be able to be more certain that the key belongs to Dave, but
maybe he doesn’t really trust Carol to properly verify identities. Bob
can mark keys as having various trust levels, and from this a web of
trust emerges: a picture of how well you can trust that a given key
belongs to a given user.

The key distribution problem is not a quick and easy problem to
solve; a lot of very smart people have spent a lot of time coming
up with solutions to the problem. There are key exchange protocols
(such as the Diffie-Hellman key exchange^{7} and IKE^{8} (which
uses Diffie-Hellman) that provide alternatives to the web of trust
and public key infrastructures.

## Source Code Listings

### secretkey.py

` 1`

`# secretkey.py: secret-key cryptographic functions`

` 2`

`"""`

` 3`

`Secret-key functions from chapter 1 of "A Working Introduction to`

` 4`

`Cryptography with Python".`

` 5`

`"""`

` 6`

` 7`

`import`

`Crypto.Cipher.AES`

`as`

`AES`

` 8`

`import`

`Crypto.Hash.HMAC`

`as`

`HMAC`

` 9`

`import`

`Crypto.Hash.SHA384`

`as`

`SHA384`

` 10`

`import`

`Crypto.Random.OSRNG.posix`

`as`

`RNG`

` 11`

`import`

`pbkdf2`

` 12`

`import`

`streql`

` 13`

` 14`

` 15`

`__AES_KEYLEN`

`=`

`32`

` 16`

`__TAG_KEYLEN`

`=`

`48`

` 17`

`__TAG_LEN`

`=`

`__TAG_KEYLEN`

` 18`

`KEYSIZE`

`=`

`__AES_KEYLEN`

`+`

`__TAG_KEYLEN`

` 19`

` 20`

` 21`

`def`

`pad_data`

`(`

`data`

`):`

` 22`

`"""pad_data pads out the data to an AES block length."""`

` 23`

`# return data if no padding is required`

` 24`

`if`

`len`

`(`

`data`

`)`

`%`

`16`

`==`

`0`

`:`

` 25`

`return`

`data`

` 26`

` 27`

`# subtract one byte that should be the 0x80`

` 28`

`# if 0 bytes of padding are required, it means only`

` 29`

`# a single \x80 is required.`

` 30`

` 31`

`padding_required`

`=`

`15`

`-`

`(`

`len`

`(`

`data`

`)`

`%`

`16`

`)`

` 32`

` 33`

`data`

`=`

`'`

`%s`

`\x80`

`'`

`%`

`data`

` 34`

`data`

`=`

`'`

`%s%s`

`'`

`%`

`(`

`data`

`,`

`'`

`\x00`

`'`

`*`

`padding_required`

`)`

` 35`

` 36`

`return`

`data`

` 37`

` 38`

` 39`

`def`

`unpad_data`

`(`

`data`

`):`

` 40`

`"""unpad_data removes padding from the data."""`

` 41`

`if`

`not`

`data`

`:`

` 42`

`return`

`data`

` 43`

` 44`

`data`

`=`

`data`

`.`

`rstrip`

`(`

`'`

`\x00`

`'`

`)`

` 45`

`if`

`data`

`[`

`-`

`1`

`]`

`==`

`'`

`\x80`

`'`

`:`

` 46`

`return`

`data`

`[:`

`-`

`1`

`]`

` 47`

`else`

`:`

` 48`

`return`

`data`

` 49`

` 50`

` 51`

`def`

`generate_nonce`

`():`

` 52`

`"""Generate a random number used once."""`

` 53`

`return`

`RNG`

`.`

`new`

`()`

`.`

`read`

`(`

`AES`

`.`

`block_size`

`)`

` 54`

` 55`

` 56`

`def`

`new_tag`

`(`

`ciphertext`

`,`

`key`

`):`

` 57`

`"""Compute a new message tag using HMAC-SHA-384."""`

` 58`

`return`

`HMAC`

`.`

`new`

`(`

`key`

`,`

`msg`

`=`

`ciphertext`

`,`

`digestmod`

`=`

`SHA384`

`)`

`.`

`digest`

`()`

` 59`

` 60`

` 61`

`def`

`verify_tag`

`(`

`ciphertext`

`,`

`key`

`):`

` 62`

`"""Verify the tag on a ciphertext."""`

` 63`

`tag_start`

`=`

`len`

`(`

`ciphertext`

`)`

`-`

`__TAG_LEN`

` 64`

`data`

`=`

`ciphertext`

`[:`

`tag_start`

`]`

` 65`

`tag`

`=`

`ciphertext`

`[`

`tag_start`

`:]`

` 66`

`actual_tag`

`=`

`new_tag`

`(`

`data`

`,`

`key`

`)`

` 67`

`return`

`streql`

`.`

`equals`

`(`

`actual_tag`

`,`

`tag`

`)`

` 68`

` 69`

` 70`

`def`

`decrypt`

`(`

`ciphertext`

`,`

`key`

`):`

` 71`

`"""`

` 72`

` Decrypt a ciphertext encrypted with AES in CBC mode; assumes the IV`

` 73`

` has been prepended to the ciphertext.`

` 74`

` """`

` 75`

`if`

`len`

`(`

`ciphertext`

`)`

`<=`

`AES`

`.`

`block_size`

`:`

` 76`

`return`

`None`

`,`

`False`

` 77`

`tag_start`

`=`

`len`

`(`

`ciphertext`

`)`

`-`

`__TAG_LEN`

` 78`

`ivec`

`=`

`ciphertext`

`[:`

`AES`

`.`

`block_size`

`]`

` 79`

`data`

`=`

`ciphertext`

`[`

`AES`

`.`

`block_size`

`:`

`tag_start`

`]`

` 80`

`if`

`not`

`verify_tag`

`(`

`ciphertext`

`,`

`key`

`[`

`__AES_KEYLEN`

`:]):`

` 81`

`return`

`None`

`,`

`False`

` 82`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__AES_KEYLEN`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

` 83`

`data`

`=`

`aes`

`.`

`decrypt`

`(`

`data`

`)`

` 84`

`return`

`unpad_data`

`(`

`data`

`),`

`True`

` 85`

` 86`

` 87`

`def`

`encrypt`

`(`

`data`

`,`

`key`

`):`

` 88`

`"""`

` 89`

` Encrypt data using AES in CBC mode. The IV is prepended to the`

` 90`

` ciphertext.`

` 91`

` """`

` 92`

`data`

`=`

`pad_data`

`(`

`data`

`)`

` 93`

`ivec`

`=`

`generate_nonce`

`()`

` 94`

`aes`

`=`

`AES`

`.`

`new`

`(`

`key`

`[:`

`__AES_KEYLEN`

`],`

`AES`

`.`

`MODE_CBC`

`,`

`ivec`

`)`

` 95`

`ctxt`

`=`

`aes`

`.`

`encrypt`

`(`

`data`

`)`

` 96`

`tag`

`=`

`new_tag`

`(`

`ivec`

`+`

`ctxt`

`,`

`key`

`[`

`__AES_KEYLEN`

`:])`

` 97`

`return`

`ivec`

`+`

`ctxt`

`+`

`tag`

` 98`

` 99`

`100`

`def`

`generate_salt`

`(`

`salt_len`

`):`

`101`

`"""Generate a salt for use with PBKDF2."""`

`102`

`return`

`RNG`

`.`

`new`

`()`

`.`

`read`

`(`

`salt_len`

`)`

`103`

`104`

`105`

`def`

`password_key`

`(`

`passphrase`

`,`

`salt`

`=`

`None`

`):`

`106`

`"""Generate a key from a passphrase. Returns the tuple (salt, key)."""`

`107`

`if`

`salt`

`is`

`None`

`:`

`108`

`salt`

`=`

`generate_salt`

`(`

`16`

`)`

`109`

`passkey`

`=`

`pbkdf2`

`.`

`PBKDF2`

`(`

`passphrase`

`,`

`salt`

`,`

`iterations`

`=`

`16384`

`)`

`.`

`read`

`(`

`KEYSIZE`

`)`

`110`

`return`

`salt`

`,`

`passkey`

### publickey.py

` 1`

`# publickey.py: public key cryptographic functions`

` 2`

`"""`

` 3`

`Secret-key functions from chapter 1 of "A Working Introduction to`

` 4`

`Cryptography with Python".`

` 5`

`"""`

` 6`

` 7`

`import`

`Crypto.Hash.SHA384`

`as`

`SHA384`

` 8`

`import`

`pyelliptic`

` 9`

`import`

`secretkey`

`10`

`import`

`struct`

`11`

`12`

`13`

`__CURVE`

`=`

`'secp521r1'`

`14`

`15`

`16`

`def`

`generate_key`

`():`

`17`

`"""Generate a new elliptic curve keypair."""`

`18`

`return`

`pyelliptic`

`.`

`ECC`

`(`

`curve`

`=`

`__CURVE`

`)`

`19`

`20`

`21`

`def`

`sign`

`(`

`priv`

`,`

`msg`

`):`

`22`

`"""Sign a message with the ECDSA key."""`

`23`

`return`

`priv`

`.`

`sign`

`(`

`msg`

`)`

`24`

`25`

`26`

`def`

`verify`

`(`

`pub`

`,`

`msg`

`,`

`sig`

`):`

`27`

`"""`

`28`

` Verify the public key's signature on the message. pub should`

`29`

` be a serialised public key.`

`30`

` """`

`31`

`return`

`pyelliptic`

`.`

`ECC`

`(`

`curve`

`=`

`'secp521r1'`

`,`

`pubkey`

`=`

`pub`

`)`

`.`

`verify`

`(`

`sig`

`,`

`msg`

`)`

`32`

`33`

`34`

`def`

`shared_key`

`(`

`priv`

`,`

`pub`

`):`

`35`

`"""Generate a new shared encryption key from a keypair."""`

`36`

`key`

`=`

`priv`

`.`

`get_ecdh_key`

`(`

`pub`

`)`

`37`

`key`

`=`

`key`

`[:`

`32`

`]`

`+`

`SHA384`

`.`

`new`

`(`

`key`

`[`

`32`

`:])`

`.`

`digest`

`()`

`38`

`return`

`key`

`39`

`40`

`41`

`def`

`encrypt`

`(`

`pub`

`,`

`msg`

`):`

`42`

`"""`

`43`

` Encrypt the message to the public key using ECIES. The public key`

`44`

` should be a serialised public key.`

`45`

` """`

`46`

`ephemeral`

`=`

`generate_key`

`()`

`47`

`key`

`=`

`shared_key`

`(`

`ephemeral`

`,`

`pub`

`)`

`48`

`ephemeral_pub`

`=`

`struct`

`.`

`pack`

`(`

`'>H'`

`,`

`len`

`(`

`ephemeral`

`.`

`get_pubkey`

`()))`

`49`

`ephemeral_pub`

`+=`

`ephemeral`

`.`

`get_pubkey`

`()`

`50`

`return`

`ephemeral_pub`

`+`

`secretkey`

`.`

`encrypt`

`(`

`msg`

`,`

`key`

`)`

`51`

`52`

`53`

`def`

`decrypt`

`(`

`priv`

`,`

`msg`

`):`

`54`

`"""`

`55`

` Decrypt an ECIES-encrypted message with the private key.`

`56`

` """`

`57`

`ephemeral_len`

`=`

`struct`

`.`

`unpack`

`(`

`'>H'`

`,`

`msg`

`[:`

`2`

`])[`

`0`

`]`

`58`

`ephemeral_pub`

`=`

`msg`

`[`

`2`

`:`

`2`

`+`

`ephemeral_len`

`]`

`59`

`key`

`=`

`shared_key`

`(`

`priv`

`,`

`ephemeral_pub`

`)`

`60`

`return`

`secretkey`

`.`

`decrypt`

`(`

`msg`

`[`

`2`

`+`

`ephemeral_len`

`:],`

`key`

`)`

- A certificate is a public key encoded with X.509 and which can have additional informational attributes attached, such as organisation name and country.↩
- The extent to which this actually happens varies widely based on the different CAs.↩
- There is some question as to whether VeriSign can actually be trusted, but that is another discussion for another day…↩
- and GnuPG↩
- http://www.rubin.ch/pgp/weboftrust.en.html↩
- It is quite often important to distinguish between
*I know this key belongs to that user*and*I trust that user*. This is especially important with key signatures - if Bob cannot trust Alice to properly check identities, she might sign a key for an identity she hasn’t checked.↩ - http://is.gd/Tr0zLP↩
- https://secure.wikimedia.org/wikipedia/en/wiki/Internet_Key_Exchange↩