Category: Security

AES Tutorial / Python Implementation June 10th, 2007

Update 2: 30-May-2016

There have been a number of comments and questions about whether this code is compliant or interoperable with other implementations. It is not. I wrote it as a non-crypto expert to teach myself more about AES. It was never intended to perform well or to be compatible with other AES implementations.

Update: 04-Apr-2009

I fixed two bugs in my AES implementation pointed out to me by Josiah Carlson. First, I was failing to pad properly files whose length was an even multiple of the block size. In those cases, bytes would be lost upon decrypting the file. Josiah also pointed out that I was using a static IV, which leaks information about messages which share common prefixes. This is a serious security bug and I was glad to have it pointed out.

Feel free to check out the changes I made or simply download the updated script.

I’ve put together a series of slides as well as a Python implementation of AES, the symmetric-key cryptosystem.

Source: pyAES.py

Sample Usage: (color added for clarity)

[brandon@zodiac pyAES]$ cat > testfile.txt
The sky was the color of television tuned to a dead channel.
[brandon@zodiac pyAES]$ ./pyAES.py -e testfile.txt -o testfile_encrypted.txt
Password:
Encrypting file: testfile.txt
Encryption complete.
[brandon@zodiac pyAES]$ ./pyAES.py -d testfile_encrypted.txt -o testfile_decrypted.txt
Password:
Decrypting file: testfile_encrypted.txt
Decryption complete.
[brandon@zodiac pyAES]$ cat testfile_decrypted.txt
The sky was the color of television tuned to a dead channel.
[brandon@zodiac pyAES]$ md5sum *
19725cef7495fd55540728759a6262c8 pyAES.py
2fffc9072a7c09f4f97862c0bceb6021 testfile_decrypted.txt
3e57070eaf1b4adf7f43b38e1c5ee631 testfile_encrypted.txt
2fffc9072a7c09f4f97862c0bceb6021 testfile.txt

Symmetric Key Cryptography

  • Identical keys used to encrypt/decrypt messages
  • Can be implemented as block ciphers or stream ciphers

Strengths:

  • Speed
  • Much less computationally intensive than public-key crypto
  • Easy to implement in hardware as well as software

Weaknesses:

  • Key Management
  • n users require n(n-1)/2 keys for all to communicate
  • secure key distribution is a challenge
  • Cannot be used (directly) for authentication or non-repudiation


AES – The Advanced Encryption Standard

  • Rijndael algorithm invented by Joan Daemen and Vincent Rijmen and selected as AES winner by NIST in 2001
  • AES uses fixed block size of 128-bits and key sizes of 128, 192 or 256 bits (though Rijndael specification allows for variable block and key sizes)
  • Most of the calculations in AES are performed within a finite field
  • There are a finite number of elements within the field and all operations on those elements result in an element also contained in the field


AES Operations

  • AES operates on a 4×4 matrix referred to as the state
  • 16 bytes == 128 bits == block size
  • All operations in a round of AES are invertible
  • AddRoundKey – each byte of the round key is combined with the corresponding byte in the state using XOR
  • SubBytes – each byte in the state is replaced with a different byte according to the S-Box lookup table
  • ShiftRows – each row in the state table is shifted by a varying number of bytes
  • MixColumns – each column in the state table is multiplied with a fixed polynomial


AES Operation – AddRoundKey

  • Each byte of the round key is XORed with the corresponding byte in the state table
  • Inverse operation is identical since XOR a second time returns the original values
# XOR each byte of the roundKey with the state table
def addRoundKey(state, roundKey):
    for i in range(len(state)):
        state[i] = state[i] ^ roundKey[i]


AES Operation – SubBytes

  • Each byte of the state table is substituted with the value in the S-Box whose index is the value of the state table byte
  • Provides non-linearity (algorithm not equal to the sum of its parts)
  • Inverse operation is performed using the inverted S-Box
# do sbox transform on each of the values in the state table
def subBytes(state):
    for i in range(len(state)):
        state[i] = sbox[state[i]]

# sbox transformations are invertible
>>> sbox[237]
85
>>> sboxInv[85]
237
>>> sbox[55]
154
>>> sbox[154]
184
>>> sboxInv[184]
154
>>> sboxInv[154]
55


AES Operation – ShiftRows

  • Each row in the state table is shifted left by the number of bytes represented by the row number
  • Inverse operation simply shifts each row to the right by the number of bytes as the row number
# returns a copy of the word shifted n bytes (chars) positive
# values for n shift bytes left, negative values shift right
def rotate(word, n):
    return word[n:]+word[0:n]

# iterate over each "virtual" row in the state table
# and shift the bytes to the LEFT by the appropriate
# offset
def shiftRows(state):
    for i in range(4):
        state[i*4:i*4+4] = rotate(state[i*4:i*4+4],i)


AES Operation – MixColumns

  • MixColumns is performed by multiplying each column (within the Galois finite field) by the following matrix:

  • The inverse operation is performed by multiplying each column by the following inverse matrix:

# Galois Multiplication
def galoisMult(a, b):
    p = 0
    hiBitSet = 0
    for i in range(8):
        if b & 1 == 1:
            p ^= a
        hiBitSet = a & 0x80
        a <<= 1
        if hiBitSet == 0x80:
            a ^= 0x1b
        b >>= 1
    return p % 256

# mixColumn does Galois multiplication on a state column
def mixColumn(column):
    temp = copy(column)
    column[0] = galoisMult(temp[0],2) ^ galoisMult(temp[3],1) ^ \
                galoisMult(temp[2],1) ^ galoisMult(temp[1],3)
    column[1] = galoisMult(temp[1],2) ^ galoisMult(temp[0],1) ^ \
                galoisMult(temp[3],1) ^ galoisMult(temp[2],3)
    column[2] = galoisMult(temp[2],2) ^ galoisMult(temp[1],1) ^ \
                galoisMult(temp[0],1) ^ galoisMult(temp[3],3)
    column[3] = galoisMult(temp[3],2) ^ galoisMult(temp[2],1) ^ \
                galoisMult(temp[1],1) ^ galoisMult(temp[0],3)


AES – Pulling It All Together

The AES Cipher operates using a varying number of rounds, based on the size of the cipher key.

  • A round of AES consists of the four operations performed in succession: AddRoundKey, SubBytes, ShiftRows, and MixColumns (MixColumns is omitted in the final round)
  • 128-bit key → rounds, 192-bit key → 12 rounds, 256-bit key → 14 rounds
  • The AES cipher key is expanded according to the Rijndael key schedule and a different part of the expanded key is used for each round of AES
  • The expanded key will be of length (block size * num rounds+1)
  • 128-bit cipher key expands to 176-byte key
  • 192-bit cipher key expands to 208-byte key
  • 256-bit cipher key expands to 240-byte key


AES – Key Expansion Operations

AES key expansion consists of several primitive operations:

  1. Rotate – takes a 4-byte word and rotates everything one byte to the left, e.g. rotate([1,2,3,4]) → [2, 3, 4, 1]
  2. SubBytes – each byte of a word is substituted with the value in the S-Box whose index is the value of the original byte
  3. Rcon – the first byte of a word is XORed with the round constant. Each value of the Rcon table is a member of the Rinjdael finite field.
# takes 4-byte word and iteration number
def keyScheduleCore(word, i):
    # rotate word 1 byte to the left
    word = rotate(word, 1)
    newWord = []
    # apply sbox substitution on all bytes of word
    for byte in word:
        newWord.append(sbox[byte])
    # XOR the output of the rcon[i] transformation with the first part
    # of the word
    newWord[0] = newWord[0]^rcon[i]
    return newWord

AES – Key Expansion Algorithm (256-bit)

Pseudo-code for AES Key Expansion:

  1. expandedKey[0:32] → cipherKey[0:32] # copy first 32 bytes of cipher key to expanded key
  2. i → 1 # Rcon iterator
  3. temp = byte[4] # 4-byte container for temp storage
  4. while size(expandedKey) < 240
    temp → last 4 bytes of expandedKey

    # every 32 bytes apply core schedule to temp
    if size(expandedKey)%32 == 0
    temp = keyScheduleCore(temp, i)
    ii + 1
    # since 256-bit key -> add an extra sbox transformation to each new byte
    for j in range(4):
    temp[j] = sbox[temp[j]]
    # XOR temp with the 4-byte block 32 bytes before the end of the current expanded key.
    # These 4 bytes become the next bytes in the expanded key
    expandedKey.append( temp XOR expandedKey[size(expandedKey)-32:size(expandedKey)-28]

Another function to note…

# returns a 16-byte round key based on an expanded key and round number
def createRoundKey(expandedKey, n):
    return expandedKey[(n*16):(n*16+16)]


AES – Encrypting a Single Block

  1. state → block of plaintext # 16 bytes of plaintext are copied into the state
  2. expandedKey = expandKey(cipherKey) # create 240-bytes of key material to be used as round keys
  3. roundNum → 0 # counter for which round number we are in
  4. roundKey → createRoundKey(expandedKey, roundNum)
  5. addRoundKey(state, roundKey) # each byte of state is XORed with the present roundKey
  6. while roundNum < 14 # 14 rounds in AES-256
    roundKey → createRoundKey(expandedKey, roundNum)
    # round of AES consists of 1. subBytes, 2. shiftRows, 3. mixColumns, and 4. addRoundKey
    aesRound(state, roundKey)
    roundNumroundNum + 1
  7. # for the last round leave out the mixColumns operation
    roundKey = createRoundKey(expandedKey, roundNum)
    subBytes(state)
    shiftRows(state)
    addRoundKey(state)
  8. return state as block of ciphertext


AES – Encrypting a Single Block (Demo)

>>> key = passwordToKey("s0m3_p@ssw0rD")
>>> key
[62, 142, 78, 2, 164, 231, 18, 196, 148, 177, 82, 186, 240, 44, 136, 242,
23, 13, 20, 169, 248, 69, 163, 79, 13, 155, 97, 200, 241, 15, 76, 15]
>>> plaintext = textToBlock("Hiro Protagonist")
>>> plaintext
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> blockToText(plaintext)
'Hiro Protagonist'
>>> ciphertext = aesEncrypt(plaintext, key)

*** aesMain ***
initial state:
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
state after adding roundKey0:
[118, 231, 60, 109, 132, 183, 96, 171, 224, 208, 53, 213, 158, 69, 251, 134]

*** AES Round1 ***
state after subBytes:
[56, 148, 235, 60, 95, 169, 208, 98, 225, 112, 150, 3, 11, 110, 15, 68]
state after shiftRows:
[56, 148, 235, 60, 169, 208, 98, 95, 150, 3, 225, 112, 68, 11, 110, 15]
state after mixColumns:
[66, 80, 228, 230, 148, 33, 121, 29, 106, 95, 226, 146, 255, 98, 121, 117]
state after addRoundKey:
[85, 93, 240, 79, 108, 100, 218, 82, 103, 196, 131, 90, 14, 109, 53, 122]

<-- SNIP -->

*** AES Round 14 (final) ***
state after subBytes:
[0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97]
state after shiftRows:
[0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251]
state after addRoundKey:
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

>>> ciphertext
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

>>> blockToText(ciphertext)
'\xc3{\xcd\xb7\xd5\xca2\xdf\xdf\xa4cV~"k\x8e'
>>> cleartext = aesDecrypt(ciphertext, key)

*** aesMainInv ***
initial state:
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

*** AES Round 14 ***
state after addRoundKey:
[0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251]
state after shiftRowsInv:
[0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97]
state after subBytesInv:
[82, 42, 14, 152, 141, 242, 234, 99, 0, 121, 94, 197, 174, 42, 99, 216]

<-- SNIP -->

*** AES Round 0 (final) ***
state after adding roundKey0:
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> cleartext
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> blockToText(cleartext)
'Hiro Protagonist'


PyRSA – RSA in Python June 18th, 2005

PyRSA is a command line utility that allows users to digitally encrypt and sign messages using the public key encryption scheme, RSA. There are three basic functions that PyRSA performs: encryption, decryption, and key generation.

Downloads:

Source: pyrsa.py

Sample Use:

1. Generate a public and private key. In this example, we will specify a key of length 1024 bits. Allow several seconds of CPU time for the generation of the keys.

pyrsa.py -g 1024 Enter file identifier (i.e. first name): brandon

2. Now the files

brandon_privateKey.txt

and

brandon_publicKey.txt

are in the current directory. Next place the text we want to encrypt in a text file.

echo "The sky above the port was the color of television, tuned
to a dead channel." > message.txt

3. Encrypt the message using the public key and redirect the output to a text file.

pyrsa.py -e message.txt -k brandon_publicKey.txt > ciphertext.txt

4. At this point the file ciphertext.txt contains the encrypted message. The file can safely be sent to a recipient, i.e. as an email attachment, the contents utterly unreadable to anyone without the private key.

cat ciphertext.txt 32464047998704731086703458860763720628883125201
840735448292781611869424600546740055592235111171870058664751326891
416030992911165222195048303846516331939189036032662981573683210672
785053735077400433222553780571914729993485153779710689497701348386
214277988780913721453283666357504772556433129612632786845350983

5. Next we will assume the message has been sent to the individual who possesses the corresponding private key and he wants to decrypt the message.

pyrsa.py -d ciphertext.txt -k brandon_privateKey.txt
Decrypted text:
The sky above the port was the color of television, tuned to a dead channel.



RSA Algorithm May 5th, 2005

Overview

We have spent the last several weeks learning about encryption in my computer security class so I thought I’d share what I’ve learned on public key cryptography.

There is a very good description of RSA on Wikipedia, so I don’t want to simply restate what they have. The focus here will be the generation of public and private keys as I feel many of the RSA tutorials on the web are lacking a bit in that department. Computing the multiplicative inverse to get d from e is a little tricky, but we will walk through it step-by-step.

First, a brief overview of RSA, for those not familiar with it already. A message M is encrypted by raising it to the power of e and then taking the result modulo some number N. To decrypt the message, you simply raise the value of the encrypted message C to the power of d and again mod by N. The beauty of RSA is that e and N can be published publicly. Together they, in fact, comprise the public key. The private key, which is not be published, is comprised of d and N.

C = Me mod N
M = Cd mod N

If you’re like me, then you are astonished at 1) how simple this system is, and 2) that you can exponentiate messages twice (modulo some number) and leave the original message unaltered. The main question that my skeptical mind came up with when presented with this powerful encryption tool was, “wouldn’t it be easy to compute d if you have the values of e and N?” The answer is, of course, no. It turns out that it is very hard to do so. We shall see later that it is easy to compute d only when we have the factors of N. If we choose N to be arbitrarily large, factoring N can take an arbitrarily long period of time. Currently, there are no known polynomial-time algorithms which can perform this task. Factorization has, in fact, been shown to be in the set of problems known as NP. So the security of RSA is essentially provided by the hardness of the factorization problem. If someone figures out a way to factor large numbers fast, then RSA is out of business.

Key Generation

As was mentioned above, RSA’s security is rooted in the fact that N is hard to factor. Therefore, we should choose N to be the product of two large primes, p and q. For clarity in this example, we will choose relatively small values for p and q, but later we will discuss the proper choices for these coefficients given a desired level of security.

  1. For this example, let P = 647 and Q = 1871. This means that the modulus, N = 1210537. (Incidentally, factoring this value of N took 0.056 seconds on UCR’s mainframe).
  2. Compute the totient of N, φ(N) = (P – 1)(Q – 1) = 1208020.
  3. Now we choose a number e which should be coprime to φ(N). The easiest way to do this is to simply choose a prime number. For this example, let e = 1127.
  4. The next step is to compute d such that (d * e) mod φ(N) = 1. If this is confusing, that is okay. This property is important because it ensures that (Me)d (mod n) = M. It may help to have a look at Euler’s Theorem if you are still confused.

The best way to compute the multiplicative inverse, d from e and φ(N) is to use the Extended Euclidean Algorithm. Here is Euclid’s algorithm for our example:

1127 1208020 (1, 0) (0, 1) We start with unit vectors (1, 0) and (0, 1) which correspond to the values of e and φ(N), respectively.

For each operation we perform on the left two columns, we perform the same operation on the right two columns.

For example, in the first step, 1127 divides 1208020 1071 times and leaves a remainder of 1003. The corresponding operation in columns 3 and 4 is to subtract (1, 0) from (0, 1) 1071 times yielding (-1071, 1).

The algorithm terminates when we have 1 and 0, not necessarilly in that order, in the first two columns. The value for d is in the column that corresponds to the 1 in the first two columns.

*Note: it is worth mentioning that it is possible for the extended Euclidean algorithm to yield a negative result for d. Obviously, this is not a suitable decryption exponent because raising an integer to a negative number results in a fraction. The simple fix here is to mod the negative value of d by φ(N), giving us a positive value of d between 0 and φ(N).

1127 1003 (1, 0) (-1071, 1)
124 1003 (1072, -1) (-1071, 1)
124 11 (1072, -1) (-9647, 9)
3 11 (107189, -100) (-9647, 9)
3 2 (107189, -100) (-331214, 309)
1 2 (438403, -409) (-331214, 309)
1 0 (438403, -409) (-1208020, 1127)

From the above calculations we know that d = 438403. So we have both the public and private keys for this user:

public key = (1127, 1210537)
private key = (438403, 1210537)

To prove that this system works, observe the following computations. Let our message M = 247. The first step is to compute C = 2471127 mod 1210537.

A brief aside:
This exponentiation can be computed easily because we are using relatively small values for e and d. However, real world implementations of RSA often use 1024 bit encryption, meaning the exponent is 1024 bits long. That is roughly equivalent to a 300 decimal digit number. To compute an exponent of that order of magnitude in the conventional way, multiplying the base by itself e times would be prohibitively expensive. Even if we could compute 1 billion multiplications per second, the computation would take longer than the current age of the universe. So it is useful to use an alternative method like exponentiation by squaring. Here is a script that computes large exponents fast. Another consideration is the storage of a very large number such as Cd. Rather than keeping the value in main memory as we exponentiate, we can simply keep the value modulo N. And now back to our example…

2471127 mod 1210537 = 611545. This number was easily obtained with the Python interpreter in a fraction of a second. Raising this number, however to the value of d, 438403, should not be done the conventional way. On the school’s mainframe this calculation took 11 minutes, 23.65 seconds. This is a situation where we can see the power of divide-and-conquer algorithms. Using our recursive exponentiation function we show that 611545438403 mod 1210537 = 247. Voilá, out pops our original message. Additionally, the exponentiation took only 31.16 seconds on the same machine with the repeated squaring method. This can be vastly improved, too, once we develop a non-recursive function. That will be critical when we want to provide real security via RSA and we don’t want to wait 10 minutes to decrypt the message.

PyRSA now available.

East Bay Psychotherapist
Licensed Clinical Social Worker provides psychotherapy and counseling services for couples and individuals in the East Bay Area.