AES API

-- cccAES is an implementation of the Advanced Encryption Standard for ComputerCraft lua.

-- Copyright (c) 2012 KleinRefrigerator
-- Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
-- The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
-- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

-- pyAES by Brandon Stearne was immensely helpful in writing this.
--      See: http://brandon.sternefamily.net/files/mit-license.txt
-- Laws of Cryptography by Neal R. Wagner was also helpful in understanding the underlying algorithm
--      See: http://www.cs.utsa.edu/~wagner/laws/

-- "Law AES-1: Conventional block ciphers are always ugly, complicated, inelegant brutes, and the AES is no exception."
--          -Neal R. Wagner




-- the sbox and inverse sbox are used throughout AES to transform bytes
-- the sbox transform works as follows: for each byte in a string, append
-- sbox[byte+1] to a new string and then return it, e.g. "\0\1" transformed
-- will be "\99\124", since those are the first two bytes of sbox
-- the inverse transform works the same but with sboxInv
-- note that sboxInv[sbox[byte+1]+1] == byte
-- this transform can be done algorithmically, but it's faster to define it as a constant
local sbox = "\099\124\119\123\242\107\111\197\048\001\103\043\254\215\171\118\202\130\201\125\250\089\071\240\173\212\162\175\156\164\114\192\183\253\147\038\054\063\247\204\052\165\229\241\113\216\049\021\004\199\035\195\024\150\005\154\007\018\128\226\235\039\178\117\009\131\044\026\027\110\090\160\082\059\214\179\041\227\047\132\083\209\000\237\032\252\177\091\106\203\190\057\074\076\088\207\208\239\170\251\067\077\051\133\069\249\002\127\080\060\159\168\081\163\064\143\146\157\056\245\188\182\218\033\016\255\243\210\205\012\019\236\095\151\068\023\196\167\126\061\100\093\025\115\096\129\079\220\034\042\144\136\070\238\184\020\222\094\011\219\224\050\058\010\073\006\036\092\194\211\172\098\145\149\228\121\231\200\055\109\141\213\078\169\108\086\244\234\101\122\174\008\186\120\037\046\028\166\180\198\232\221\116\031\075\189\139\138\112\062\181\102\072\003\246\014\097\053\087\185\134\193\029\158\225\248\152\017\105\217\142\148\155\030\135\233\206\085\040\223\140\161\137\013\191\230\066\104\065\153\045\015\176\084\187\022"
local sboxInv = "\082\009\106\213\048\054\165\056\191\064\163\158\129\243\215\251\124\227\057\130\155\047\255\135\052\142\067\068\196\222\233\203\084\123\148\050\166\194\035\061\238\076\149\011\066\250\195\078\008\046\161\102\040\217\036\178\118\091\162\073\109\139\209\037\114\248\246\100\134\104\152\022\212\164\092\204\093\101\182\146\108\112\072\080\253\237\185\218\094\021\070\087\167\141\157\132\144\216\171\000\140\188\211\010\247\228\088\005\184\179\069\006\208\044\030\143\202\063\015\002\193\175\189\003\001\019\138\107\058\145\017\065\079\103\220\234\151\242\207\206\240\180\230\115\150\172\116\034\231\173\053\133\226\249\055\232\028\117\223\110\071\241\026\113\029\041\197\137\111\183\098\014\170\024\190\027\252\086\062\075\198\210\121\032\154\219\192\254\120\205\090\244\031\221\168\051\136\007\199\049\177\018\016\089\039\128\236\095\096\081\127\169\025\181\074\013\045\229\122\159\147\201\156\239\160\224\059\077\174\042\245\176\200\235\187\060\131\083\153\097\023\043\004\126\186\119\214\038\225\105\020\099\085\033\012\125"

-- these values are used to expand keys
local rcon = "\141\001\002\004\008\016\032\064\128\027\054\108\216\171\077\154\047\094\188\099\198\151\053\106\212\179\125\250\239\197\145\057\114\228\211\189\097\194\159\037\074\148\051\102\204\131\029\058\116\232\203\141\001\002\004\008\016\032\064\128\027\054\108\216\171\077\154\047\094\188\099\198\151\053\106\212\179\125\250\239\197\145\057\114\228\211\189\097\194\159\037\074\148\051\102\204\131\029\058\116\232\203\141\001\002\004\008\016\032\064\128\027\054\108\216\171\077\154\047\094\188\099\198\151\053\106\212\179\125\250\239\197\145\057\114\228\211\189\097\194\159\037\074\148\051\102\204\131\029\058\116\232\203\141\001\002\004\008\016\032\064\128\027\054\108\216\171\077\154\047\094\188\099\198\151\053\106\212\179\125\250\239\197\145\057\114\228\211\189\097\194\159\037\074\148\051\102\204\131\029\058\116\232\203\141\001\002\004\008\016\032\064\128\027\054\108\216\171\077\154\047\094\188\099\198\151\053\106\212\179\125\250\239\197\145\057\114\228\211\189\097\194\159\037\074\148\051\102\204\131\029\058\116\232\203"


-- argument names denote what a function can or should work with
-- str: arbitrary length bytestrings
--      often, however, a function that takes a "str" argument typically takes
--      a specific type--I have denoted this with comments on such functions
-- word: 4 byte strings
--      the AES standard is defined in terms of words
--      however, my implementation focuses on bytes instead
-- state: 16 byte strings
--      a state represents the current status of the algorithm
--      the main operations of AES work on states
-- key: 16, 24, or 32 byte strings
--      AES supports three key lengths, all implemented here:
--      128 bit (16 byte), 192 bit (24 byte), and 256 bit (32 byte)


-- returns a copy of a string shifted to the left for positive values of n
-- and to the right for negative values, wrapping values around to the other side
-- e.g. rotate("foo", 1) == "ofo" and rotate("foo",-1) == "oof"
-- the result is undefined if math.abs(n) > str:len(), but it should just return str

local function rotate(str, n) -- str is usually word
    local a
    -- correction for 1-based string indexing (damn you, lua)
    if (n > 0) then
        a = n + 1
    elseif (n < 0) then
        a = n
    else
        return str
    end
    return str:sub(a)..str:sub(1,a-1)
end


-- divides a 16 byte state into 4 virtual rows of 4 bytes each
-- then rotates the nth row n-1 and returns the result
-- this is one of the four AES round operations

local function shiftRows(state)
    local newS = ""
    for i = 0, 3 do
        newS = newS..rotate(state:sub(i*4+1,(i+1)*4),i)
    end
    return newS
end


-- the inverse transform of shiftRows: shifts by -(n-1) instead
-- shiftRowsInv(shiftRows(state)) == state

local function shiftRowsInv(state)
    local newS = ""
    for i = 0, 3 do
        newS = newS..rotate(state:sub(i*4+1,(i+1)*4),-i)
    end
    return newS
end


-- sbox transform: described above
-- this is one of the four AES round operations

local function subBytes(str) -- str is usually state
    local newW = ""
    for i = 1, #str do
        newW = newW .. sbox:sub(str:byte(i)+1,str:byte(i)+1)
    end
    return newW
end


-- inverse sbox

local function subBytesInv(str) -- str is usually state
    local newW = ""
    for i = 1, #str do
        newW = newW .. sboxInv:sub(str:byte(i)+1,str:byte(i)+1)
    end
    return newW
end


-- this takes two strings of equal length and returns a string that is
-- the bytewise xor of them
-- if strings are not of equal length, returns nil
-- this is one of the four AES round operations

local function strXor(str1, str2)
    if (#str1 ~= #str2) then return nil end
    res = ""
    for i = 1, #str1 do
        res = res .. string.char(bit.bxor(str1:byte(i), str2:byte(i)))
    end
    return res
end


-- Galois Multiplication
-- takes two bytes, does some shit, gives you another byte

local function galoisMult(a, b)
    local p = 0
    local hiBit = 0
    for i = 1,8 do
        if (bit.band(b,1) == 1) then
            p = bit.bxor(p, a)
        end
        hiBit = bit.band(a, 0x80)
        a = bit.blshift(a, 1)
        if hiBit == 0x80 then
            a = bit.bxor(a, 0x1b)
        end
        b = bit.brshift(b, 1)
    end
    return p % 256
end


-- does a bunch of galois multiplication and xor'ing to a column

local function mixColumn(word)
    local temp = ""
    for i = 1,4 do temp = temp .. word:sub(5-i,5-i) end
    local newW = ""
    for i = 1,4 do
        temp = rotate(temp,-1)
        newW = newW .. string.char(bit.bxor(bit.bxor(bit.bxor(galoisMult(temp:byte(1),2), galoisMult(temp:byte(2),1)), galoisMult(temp:byte(3),1)), galoisMult(temp:byte(4),3)))
    end
    return newW
end


-- inverse transform of mixColumn

local function mixColumnInv(word)
    local temp = ""
    for i = 1,4 do temp = temp .. word:sub(5-i,5-i) end
    local newW = ""
    for i = 1,4 do
        temp = rotate(temp,-1)
        newW = newW .. string.char(bit.bxor(bit.bxor(bit.bxor(galoisMult(temp:byte(1),14), galoisMult(temp:byte(2),9)), galoisMult(temp:byte(3),13)), galoisMult(temp:byte(4),11)))
    end
    return newW
end


-- wrapper for mixColumn: applies it to each of the four virtual columns
-- this is one of the four AES round operations

local function mixColumns(state)
    local cols = {}
    for i=1,4 do
        local temp = ""
        for j=0,3 do
            temp = temp .. state:sub(i+j*4,i+j*4)
        end
        cols[i] = mixColumn(temp)
    end
    state = ""
    for i=1,4 do for j=1,4 do
        state = state .. cols[j]:sub(i,i)
    end end
    return state
end


-- inverse of mixColumns

local function mixColumnsInv(state)
    local cols = {}
    for i=1,4 do
        local temp = ""
        for j=0,3 do
            temp = temp .. state:sub(i+j*4,i+j*4)
        end
        cols[i] = mixColumnInv(temp)
    end
    state = ""
    for i=1,4 do for j=1,4 do
        state = state .. cols[j]:sub(i,i)
    end end
    return state
end


-- this is a sub-operation of expandKey

local function keyScheduleCore(word, i)
    word = rotate(word, 1)
    local newW = ""
    for j = 1, #word do
        local c = sbox:byte(word:byte(j)+1)
        if (j == 1) then
            c = bit.bxor(c,rcon:byte(i+1))
        end
        newW = newW .. string.char(c)
    end
    return newW
end


-- expands the key to give sufficient round keys for the 10, 12, or 14 rounds
-- 16 byte keys -> 176 bytes, 24 -> 208, 32 -> 240

function expandKey(key)
    local nWord = #key / 4
    if (nWord ~= 4 and nWord ~= 6 and nWord ~= 8) then
        return nil
    end
    local nRound = nWord + 6
    local eKey = key
    local i = nWord
    while (i < 4*(nRound+1)) do
        local temp = eKey:sub((i-1)*4+1,i*4)
        if (i % nWord == 0) then
            temp = keyScheduleCore(temp, i/nWord)
        elseif (nWord == 8 and (i%8) == 4) then
            temp = subBytes(temp)
        end
        local temp2 = eKey:sub((i-nWord)*4+1,(i-nWord+1)*4)
        for i = 1, 4 do
            eKey = eKey .. string.char(bit.bxor(temp:byte(i),temp2:byte(i)))
        end
        i = i + 1
    end
    return eKey
end


-- this runs one round of AES given a state and a round key

function AESRound(state, roundKey)
    state = subBytes(state)
    state = shiftRows(state)
    state = mixColumns(state)
    -- add the round key
    state = strXor(state, roundKey)
    return state
end


-- this runs one round of AES backwards given a state and a round key
-- note that strXor has no inverse since xor is symmetric -- x ^ y ^ y = x

function AESRoundInv(state, roundKey)
    -- add the round key
    state = strXor(state, roundKey)
    state = mixColumnsInv(state)
    state = shiftRowsInv(state)
    state = subBytesInv(state)
    return state
end


-- retrieves the (round+1)th group of 16 bytes from an expanded key

function getRoundKey(eKey, round)
    return eKey:sub(16*round+1,16*(round+1))
end


-- this function represents a single block cipher operation
-- given a state and an expanded key, it runs the full 10-14 rounds
-- on a single block of data
-- these block cipher operations can be used together in different modes

function AESMain(state, eKey)
    local nRound = #eKey/16-1
    if (nRound ~= 10 and nRound ~= 12 and nRound ~= 14) then return nil end

    -- zeroth round has only a round key
    local roundKey = getRoundKey(eKey, 0)
    state = strXor(state, roundKey)

    for i=1,nRound-1 do
        roundKey = getRoundKey(eKey, i)
        state = AESRound(state, roundKey)
    end
    -- no mixColumns in final round
    roundKey = getRoundKey(eKey,nRound)
    state = subBytes(state)
    state = shiftRows(state)
    state = strXor(state, roundKey)

    return state
end


-- single decryption operation, inverse of AESMain

function AESMainInv(state, eKey)
    local nRound = #eKey/16-1
    if (nRound ~= 10 and nRound ~= 12 and nRound ~= 14) then return nil end

    -- going in reverse, so do the last round first with no mixColumns
    roundKey = getRoundKey(eKey, nRound)
    state = strXor(state, roundKey)
    state = shiftRowsInv(state)
    state = subBytesInv(state)

    for i=nRound-1,1,-1 do
        roundKey = getRoundKey(eKey, i)
        state = AESRoundInv(state, roundKey)
    end

    -- zeroth round with only a round key
    roundKey = getRoundKey(eKey, 0)
    state = strXor(state, roundKey)

    return state
end