OPERACOES COM BYTES

Definições de soma e produto de 2 bytes em 1 byte para as quais os axiomas de soma e produto valem.

Motivação

Para alguns sistemas criptográficos, especialmente o 4 AES, desejamos realizar transformações entre bytes que preservem os axiomas de anel (associatividade, comutatividade, existência de elemento neutro e distributividade) mas que mantém uma saída de mesmo comprimento que a entrada (i.e. multiplicar/somar dois bytes e obter um outro byte como resultado).

Soma

Para a soma, a operação escolhida é o XOR, denotada “\(\oplus\)”. De fato, temos: \[ \begin{gather} (A \oplus B) \oplus C = A \oplus (B \oplus C) \\ A \oplus B = B \oplus C \\ A \oplus 00000000 = A \end{gather} \] o que satisfaz os axiomas dados.

Código

Segue uma implementação em Python do algoritmo XOR:

def xor(a, b):
    output = ''

    for i in range(len(a)):
        if a[i] == b[i]:
            output += '0'
        else:
            output += '1'

Produto

Para o produto, escolhemos a multiplicação em \(GF(2^8)\), denotada “\(\otimes\)”. Procedemos da seguinte forma:

1. Para cada \(b = b_1 b_2b_3b_4b_5b_6b_7b_8\), associamos um polinômio \[ p_b(x) = b_1x^7 + b_2x^6 + b_3 x^5 + b_4 x^4 + b_5x^3 + b_6 x^2 + b_7x + b_8 \]
2. Fixamos um “polinômio módulo”, que deve ser um polinômio primo de grau 8 (i.e. tal que nenhum polinômio tenha resto 0 exceto ele próprio e 1), para que todo byte tenha um byte inverso. No caso do AES, o polinômio escolhido é o \[ m(x) = x^8 + x^4 + x^3 + x + 1 \]
3. Agora, se desejamos obter \(a \otimes b\), multiplicamos os dois polinômios correspondentes, mod 2: \[ T(x) = p_a(x) \cdot p_b(x) \text{ mod }2 \]
4. O polinômio em questão terá grau no máximo 14, sendo representado por uma palavra de 15 bits.
5. Então, obtemos o resto da divisão polinomial de \(T\) por \(m\). Basta tomar a diferença de grau \(d\) entre \(T\) e \(m\), multiplicar \(m\) por \(x^d\) e subtrair o resultado de \(T\), mod 2 (equivalente a um XOR). Repetimos isso até que \(d\) seja menor que o grau de \(m\), e o que restar em \(T\) é o resto \(p_{a \otimes b}\), que terá grau 7 ou menor.
6. Obtemos o byte correspondente a \(p_{a \otimes b}\), que é \(a \otimes b\).

De fato, esta definição de produto valida todos os axiomas dados.

Atalho para produto com \(00000010\)

Caso a multiplicação em questão seja \(a \otimes 00000010\), ou seja, a multiplicação pelo polinômio \(p_b(x) = x\), há um método bem mais rápido que o algoritmo acima:

Caso \(a_1 = 0\), o resultado é \(a \otimes b = a_2a_3a_4a_5a_6a_7a_8a_1\), ou seja, um shift circular.

Caso \(a_1 = 1\), o resultado é o byte correspondente a \(p_a(x) \cdot x + m(x) \text{ mod }2\).

Código

Segue uma implementação em Python do algoritmo de produto em \(GF(2^8)\):

def xtime(a, m):
    '''
    str, str -> str

    Recebe dois bytes a e m e retorna o produto [a * '00000010' mod m]
    como definido em GF(2^8). Ou seja, com a notação polinomial,
    retorna o produto [a(x) * x mod m(x)].
    '''

    if a[0] == '0':
        # se a = 0bcdefgh, a * x mod m = bcdefgh0
        return a[1:] + '0'
    else:
        # se a = 1bcdefgh, a * x mod m = (a * x) XOR m
        # o maior bit sempre resulta 0 e é desprezado
        return xor(byte_mult(a, '00000010'), m)[1:]

def byte_mult(a,b):
    prod = 15*'0'

    for i in range(8):
        for j in range(8):
            if a[i] == '1' and b[j] == '1':
                prod = flip_bit(prod, i+j)

    return prod


def byte_mult_mod(a, b, m):
    # se a = x ou b = x, usamos um atalho
    if a == '00000010':
        return xtime(b,m)
    if b == '00000010':
        return xtime(a,m)

    # produto dos polinômios correspondentes a a e b
    prod = byte_mult(a,b)

    # obter índices '1' de m
    m_ind = []
    for i in range(len(m)):
        if m[::-1][i] == '1':
            m_ind.append(i)

    while prod[:7] != '0000000':
        # grau do dividendo
        for i in range(15):
            if prod[i] == '1':
                deg = 14 - i
                break

        for i in m_ind:
            mult = deg - m_ind[-1]
            prod = flip_bit(prod, 14 - (mult + i) )

    return prod[7:]