AES, Advanced Encryption Standard, is the “new” standard block cipher selected by the NIST among a few other competitors. It has been designed by Vincent Rijmen and Joan Daemen, and initially named Rijndael.

It works for different key sizes: 128, 192 or 256 bits and works over input/outputs of 16 bytes.

On an mathematical point of view, AES performs operations over GF(2^8) - which can be mapped to polynomials of degree 7 with binary coefficients. Some operations are particularly easy to perform, as noted by FIPS 197, such as multiplication by x (to be represented as (02)) which corresponds to a left shift and XOR 1b. Then, multiplication by (03) corresponds to a multiplication by 2 and an addition.

Basically, the algorithm consists in:

• copying the input in a “state” array. The state is a two-dimensional array of 4×4 bytes. It is commonly represented as a one-dimension array of 4 32-bit words.

• performing an initial addition

• processing the state for 10, 12 or 14 rounds, depending on the key size. Each round uses a different key, derived from the key using a key expansion function. Each round processes the state with a series of transformations. The SubBytes and MixColumns transformations are commonly gathered in a single “Sbox” or lookup table, and the ShiftRows is implemented as a rotation on the state. The lookup table contains 256 entries of 32-bit words. The first element corresponds to (63).[02, 01, 01, 03] where (63) is the first element of the original Sbox (SubBytes transformation) and [02, 01, 01, 03] corresponds to an invertible polynomial in GF(2^8) used in the MixColumns transformation. The final round differs slightly from the others and requires its own lookup table of 256 bytes.

• finally, the output is copied from the “state”

The decryption procedure is globally the “same”, but to undo the encryption the rounds must be different. In particular, the MixColumns transformation does not use the same invertible polynomial, and the Sbox of SubBytes is inverted too. This means the decryption must be implemented separetely.

Typical speed reported by LibTomCrypt is 5 cycles per bit, for a full C implementation (no assembly), on an x86 processor.

References:

• FIPS 197

• Rijndael AES Specification: includes some nice optimization hints regarding implementation, such as grouping the first three transformations in the Sbox.

• Brian Gladman's C source.

• Vincent Rijmen's implementation.

DES (Data Encryption Standard) is a former block cipher standard. Because its security was at stake, it is gradually being replaced by AES. It was invented by IBM, with codename Lucifer, in 1976, and then selected in 1977 by the NIST. It uses 56 bit keys, and operates over 8 byte blocks.

The keys for DES usually also include 8 parity bits, which are included as the 8th, 16th… and 64th bit of the key. 8 bytes are consequently required to hold the key, although its strength is only that of 56-bit keys.

The algorithm consists in:

• an initial permutation. This permutation can be implemented as several shifts and XORs swapping rows.

• 16 rounds over 2 32-bit blocks. Actually, each round works on the right 32-bit (half) block, whereas the left 32 bits are taken, unchanged from the previous right 32-bit block. The computation of the right 32-bit block involves an XOR with the previous left 32-bit block and a computation using a special function that selects and expands the block to 48 bits, XORs it with a 48-bit round key (key schedule), processes it in an Sbox and finally performs a permutation to yield a new 32-bit block. Each round uses a different 48-bit key, derived from the original 56-bit key. Some DES keys are not acceptable and said to be weak or semi-weak because they output 16 identical subkeys or only 2 different subkeys. Weak keys are: 0101010101010101, FEFEFEFEFEFEFEFE, E0E0E0E0F1F1F1F1, 1F1F1F1F0E0E0E0E. Semi-weak keys are: 011F011F010E010E, 1F011F010E010E01, 01E001E001F101F1, E001E001F101F101, 01FE01FE01FE01FE, FE01FE01FE01FE01, 1FE01FE00EF10EF1, E01FE01FF10EF10E, 1FFE1FFE0EFE0EFE, FE1FFE1FFE0EFE0E, E0FEE0FEF1FEF1FE, FEE0FEE0FEF1FEF1.

• finally, the initial permutation is inverted and produces a 8-byte result.

The decryption of a DES block follows exactly the same algorithm, but from down to top.

DES's implementation is quite tricky because it operates over bits and not bytes. To compute the key schedule, it is usually acceptable to work using one byte per bit because the key schedule is only computed once. But, for the core of the algorithm (the rounds), this is not possible, and there are several tricks to operate over 32-bit integers as much as possible (for 32-bit platforms !). The following tricks are commonly implemented:

• the key schedule is typically prepared combined with the bit selection table E, memorized as 2 32-bit integers, using only 24 bits of each.

• the S-boxes are typically combined with the permutation P. Hence, there are 8 S-boxes of 64 32-bit integers.

Typical speed reported for DES is 23 cycles / bit for R. Outerbridge's implementation on x86.

DES's security is seriously compromised, mainly because 56-bit keys are too short to offer appropriate security using todays' machines. Currently, we know of:

• brute force attacks using specially crafted machines. EFF's DES Cracker with 1536 processors broke DES in 4 days in 1998. In 1999, Distributed.Net achieved that in only 23 hours using a network of 100 000 machines.

• differential cryptanalysis reduces the amount of clear texts down to 2^47.

• linear cryptanalysis reduces the amount to 2^43.

Since all those results have been published, research on DES has somewhat been abandonned (DES can perhaps be broken even quicker now), the focus being shift on AES. However, some applications still use DES or Triple DES.

Triple DES can be seen as an attempt to secure DES: it performs three loops of DES. Several Triple DES modes exist and are detailed in FIPS 163-3. Mainly, the best known modes are EDE3 and EDE2. The first one performs an Encryption using the 56 first bits of the key, then a Decryption using the next 56 bits and finally and Encryption using the last 56-bits. So the Triple DES key can be seen as a 168-bit key or 3 56-bit DES keys. Obviously, it is important the first and the second key are not identical. For EDE2, only 112-bit keys are used: encryption with K1, decryption with K2 and encryption with K1(=K3).

Other modes exists such as EEE3, where the algorithm is applied 3 times in encryption mode.

References:

• FIPS 46-3

• Triple DES standard test vectors and test plan (NIST 800-17).

• Richard Outerbridge's implementation in C (public domain).

• Eli Biham's paper on A Fast New DES Implementation in Software

RSA is perhaps the most famous crypto algorithm. Contrary to DES or AES, it is not a block cipher but a public-key cipher. It was invented in 1977 by Rivest, Shamir and Adleman.

Its theory relies on modular exponentation and the difficulty to factorize large integers.

The algorithm consists in computing the exponentiation of a message, modulo a modulus.

The modulus is the multiplication of two large primes p and q (or more) and the exponent is chosen such that it is invertible modulo (p-1)(q-1).

So, the public key consists of:

• the modulus n. The size of n is the 'strength' of RSA. It is the multiplication of two secret primes p and q. Note that, consequently, the modulus is odd. The strength of RSA relies on the fact the modulus cannot be easily factored.

• a public exponent, e, greater or equal than 3 (and smaller than the modulus), and prime with (p-1)(q-1). Instead of making sure e is prime with (p-1)(q-1), e is typically chosen within prime numbers, for example 65537. Beware that selecting a too small e (e.g. 3) is prohibited for security reasons.

The private key basically consists of:

• the modulus n.

• the first prime p

• the second prime q

• a private exponent, d, such that e.d mod (p-1)(q-1) = 1

Note that the modulus can also be computed as the multiplication of more than 2 primes (for example 4). In that case, all four primes must be known and kept secret.

Some algorithms use the Chinese Remainder Theorem (CRT) to compute faster modular exponentiation. Indeed, with CRT, it is possible to compute 2 modular exponentiation over half size primes instead of 1 modular exponentiation (which actually speeds up the process).

In that case, some other parameters are typically kept secret in the private key:

• the first CRT exponent dp = d mod (p-1)

• the second CRT exponent dq = d mod (q-1)

• a CRT coefficient u = 1/q mod p.

The most popular way to compute modular exponentiations use Montgomery's multiplications. Montgomery published in 1985 a way to compute modular exponentiation using only operations modulo powers of 2 - twice as more efficient. The theory is complex

and involves some pre-computing ®. Other optimizations exist (and can be combined) such as the binary method or sliding windows.

The generation of a key pair is a 'long' process because algorithms to output primes are lengthy.

A common way to generate a key pair is to generate a random number and divide it by the x first hard coded primes (and loop until it's okay) and/or to use better algorithms such as the Miller-Rabin primality test.

This only generates probable primes. Once p and q have been generated, all other factors are easily computed, including the private exponent. The public exponent is usually provided by the caller or fixed.

By definition, RSA will only work over integers small than the modulus (or the integer can be reduced). Consequently, the implementation must make sure prior to RSA computations that the input transforms to an appropriate integer. This is the task of RSA paddings.

PKCS#1 defines 4 paddings: two encryption schemes (RSAES-PKCS1.5 and RSAES-OAEP) and two signatures schemes with appendix (RSASSA-PKCS1.5 and RSASSA-PSS). PKCS#1 does not define signature schemes with message recovery.

The PKCS1.5 padding is the easiest to implement (but the least secure). For signatures, it consists in a leading 0×01 0×00, followed by a padding string of 0xff (at least 8), a 0×00 and the DER encoding of the Digest Information structure containing the digest algorithm and the digest of the message to sign.

For encryption, it is 0×00 0×02, followed by a padding string of random bytes, and finished by the message. The insertion of a random string ensures that the output of the encryption of two identical cleartexts produces different ciphertexts.

RSASSA-PSS was invented by Mihir Bellare and Phillip Rogaway and added to PKCS#1 in 1996.

It is possible to prove that, with PSS, the difficulty of forging signatures is directly related to the difficulty of inverting RSA.

Internally, the padding uses a hash function, a salt (random numbers) and a mask generation function (MGF - usually based on a hash)

RSAES-OAEP also is a late addition to PKCS#1, but its security isn't currently proved, although it is assumed it is better than PKCS1.5.

It starts with a leading 0×00 (which actually ensures the encoded message is smaller than the modulus), and uses

an optional label (a string), mask generation function and seed.

There are several RSA key formats. The so-called PKCS1 key format is for public keys:

RSAPublicKey ::= SEQUENCE {

  modulus INTEGER, -- n

  publicExponent INTEGER -- e }

X.509 also defines a public key format, used by several software such as OpenSSL:

SubjectPublicKeyInfo ::= SEQUENCE {

  algorithm AlgorithmIdentifier,

  publicKey BIT STRING

}

where, for RSA, the bit string actually corresponds to the encoding of PKCS#1 RSAPublicKey.

PKCS#8 also defines a key format for private keys (not restricted to RSA):

PrivateKeyInfo ::= SEQUENCE {

  version Version,

  privateKeyAlgorithm PrivateKeyAlgorithmIdentifier,

  privateKey PrivateKey,

  attributes [0] IMPLICIT Attributes OPTIONAL

The OID for RSA is 1.2.840.113549.1.1.1.

References:

• IEEE P1363a

• PKCS1

• Handbook of Applied Cryptography of A. Menezes, P. van Oorschot and S. Vanstone. Chapters 2, 4 and 14 particularly relate to RSA.

• NIST RSA test vectors

Diffie-Hellman is another public-key algorithm, commonly used to establish a secret between two different entities.

It has been invented by Diffie and Hellman (!) in 1976.

Its mathematical background relates to Galois Fields over prime numbers, i.e groups where a given prime (p) is used as a modulus over all operations.

Both parties share parameters which are:

• a prime number (p) defining the field GF(p).

• a generator (g). This integer is either in GF(p) or in GF(q), where q is a prime factor of p-1, such that p=jq +1. q is also called a subprime. It is not used in all forms of DH.

Additionally, the private key is a secret integer (x). If a subprime is used, x is smaller than q. Otherwise smaller than p.

The public key is an integer y computed as y = g^x mod p.

There are two different standards for DH: X9.42 and PKCS#3. The former uses a subprime, whereas the latter does not. Also, standards specify different conditions on sizes for primes or other parameters.

DSA is very similar to DH except it is designed for signatures, whereas DH is for secret establishments.

X9.42 defines a very simple key format for DH:

DiffieHellmanPublicNumber ::= INTEGER

and domain parameters:

DomainParameters ::= SEQUENCE {

	p INTEGER,	-- odd prime p= jq +1 

	g INTEGER,	-- generator, g^q = 1 mod p

	q INTEGER,	-- prime factor of p-1

	j INTEGER,	-- cofactor j>=2

	validationParams ValidationParms OPTIONAL

	

ValidationParms ::= SEQUENCE {	

	seed BIT STRING		-- seed for prime generation

	pGenCounter INTEGER	-- parameter verification

}

PKCS#3 defines another format for domain parameters:

DHParameter ::= SEQUENCE {

  prime INTEGER, -- p

  base INTEGER, -- g

  privateValueLength INTEGER OPTIONAL }

X.509 re-uses the SubjectPublicKeyInfo format but the BIT STRING of the public key is the integer Y

and the algorithm OID is 1.2.840.10046.2.1

Once a shared secret has been computed (Z), this shared secret must be derived into an appropriate key.

Several derivation algorithms exists although none seems either famous nor really standard: see in PKCS#3 or X9.42.

References

• RFC 2631

• PKCS3

The core of DSA is the same as DH's, but the parametrization is different because DSA is used for signatures.

Actually, DSA is the NIST's standard for signatures.

DSA uses a subprime q.

The signature process is:

• select a random k smaller than q.

• compute r = (g^k mod p) mod q

• compute s= k^-1(SHA1(m)+xr))mod q

Note the signature consists of two parts, and the first part does not use the input.

Key formats for DSA are defined in RFC 2459:

DSAPublicKey ::= INTEGER -- public key, Y

and for OpenSSL:

DSAPrivateKey ::= SEQUENCE {

  version INTEGER,

  p INTEGER,

  q INTEGER,

  g INTEGER,

  y INTEGER,

  x INTEGER

}

The signature format is defined in RFC 2459:

Dss-Parms  ::=  SEQUENCE  {

  p             INTEGER,

  q             INTEGER,

  g 



Dss-Sig-Value  ::=  SEQUENCE  {

  r       INTEGER,

  s       INTEGER  }

References

• NIST FIPS 186-2

• NIST Test vectors

==== ECDH ====

The ECDH algorithm translates to elliptic curves to finding a scalar

number k such that P=kG, where P is a known point of the curve, and G its generator or

base (a point too).

Elliptic curves are defined over GF(p) (finite fields of integers modulo p, whose characteristic is 1)

or over GF(2^m) (finite fields of m degree polynoms, where characterists is 2)

Over GF(p), an elliptic curve is y²=x^3 +ax+b mod p.

Over GF(2^m), it is y²+xy=x^3+ax²+b

When, for instance, a curve is defined over GF(p), this means that the coordinates x and y of a point of the curve are integers in GF(p).

Also, the order of a curve is the number of points of the curve + the point at infinity.

This is an important security parameter of the algorithm and it is typically big.

The order of a point is the smaller integer such that nP = infinity.

The public key is point Q : Q=d.G

The private key (d) is an integer between 1 and the order of the curve.

See P1363, X9.63, SEC1

I like this crypto library much, unfortunately, it looks like it won't be maintained any longer. You can download it here.