AES

Universidade Federal do Ceará - Campus Quixadá

Roberto Cabral
rbcabral@[Link]

09 de Outubro de 2025

Criptografia
 Seção 1

Teoria de Galois
 Teoria de Galois

Introdução

• Aritmética de Galois é utilizada em muitas camadas do AES.

• Um corpo finito (Galois fields) é um conjunto com um número finito
de elementos.
• Grosseiramente falando, um corpo finito é um conjunto finito de
elementos que permite as seguintes operações: adição, subtração,
multiplicação e inversão.

Cabral (UFC) AES 09 de Outubro de 2025 1 / 47

 Teoria de Galois

Grupo

Um grupo é um conjunto de elementos G com uma operação ◦ que

combina dois elementos de G. Um grupo possui as seguintes propriedades:

1 A operação do grupo ◦ é fechada. Isto é, para todo a, b ∈ G, temos

que a ◦ b = c ∈ G.
2 A operação do grupo ◦ é associativa. Isto é, a ◦ (b ◦ c) = (a ◦ b) ◦ c
para todo a, b, c ∈ G.
3 Existe um elemento 1 ∈ G, chamado elemento neutro, tal que
a ◦ 1 = 1 ◦ a = a para todo a ∈ G.
4 Para cada a ∈ G existe um elemento a−1 ∈ G, chamado inverso de a,
tal que a ◦ a−1 = a−1 ◦ a = e.
5 Um grupo G é abeliano se, além das propriedades anteriores, temos
que a ◦ b = b ◦ a para todo a, b ∈ G

Cabral (UFC) AES 09 de Outubro de 2025 2 / 47

 Teoria de Galois

Grupo - Exemplo

• O conjunto de inteiros Zm = {0, 1, ..., m − 1} juntamente com a

operação de adição módulo m forma um grupo com elemento neutro
0.
• Todo elemento a tem um inverso −a tal que a + (−a) = 0 mod m.
• Note que esse grupo não pode ser formado com a operação de
multiplicação, pois alguns elementos a não possuem inverso tal que
aa−1 = 1 mod m.

Cabral (UFC) AES 09 de Outubro de 2025 3 / 47

 Teoria de Galois

Corpo

Um corpo F é um conjunto de elementos com as seguintes propriedades:

• Todos os elementos de F formam um grupo aditivo com o operador
de grupo “+” e o elemento neutro 0.
• Todos os elementos de F , exceto o zero, formam um grupo
multiplicativo com operador de grupo “×” e elemento neutro 1.
• Quando os dois grupos são misturados, a propriedade distributiva
continua valendo, isto é, para todo elemento
a, b, c ∈ F : a(b + c) = (a × b) + (a × c).

Teorema
Um corpo com ordem m só existe se, e somente se, m for uma potência
prima, isto é, m = pn , para algum inteiro positivo n e inteiro primo p.

Cabral (UFC) AES 09 de Outubro de 2025 4 / 47

 Teoria de Galois

Corpos primos

• O exemplo mais intuitivo de corpos finitos são os corpos de ordem

prima, isto é, com n = 1.
• Elementos do corpo GF (p) podem ser representados pelos inteiros
0, 1, 2, . . . , p − 1.
• As duas operações do corpo são a adição modular e a multiplicação
inteira módulo p.

Teorema
Seja p um primo. O anel inteiro Zp é conhecido por GF (p) e é
denominado um corpo primo, ou um corpo de Galois com um número
primo de elementos. Todos elementos não zeros de GF (p) possuem um
inverso. A aritmética em GF (p) é aplicada módulo p.

Cabral (UFC) AES 09 de Outubro de 2025 5 / 47

 Teoria de Galois

Anel inteiro

Anel
Um anel inteiro consiste de:
1. O conjunto Zm = {0, 1, 2, . . . , m − 1}.
2. Duas operações “+” e “×” para todo a, b ∈ Zm tal que:
1. a + b ≡ c mod m, (c ∈ Zm ).
2. a × b ≡ d mod m, (d ∈ Zm ).
• Exemplo - Seja m = 9, temos um anel Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}.
Vamos ver alguns exemplos:
• 6 + 8 = 14 ≡ 5 mod 9
• 6 × 8 = 48 ≡ 3 mod 9

Cabral (UFC) AES 09 de Outubro de 2025 6 / 47

 Teoria de Galois

Propriedades do Anel

• O anel é fechado.
• O anel é associativo.
• O anel possui um elemento neutro (0 para adição e 1 para
multiplicação).
• Para qualquer elemento a pertencente ao anel, sempre existe um
elemento negativo −a tal que a + (−a) ≡ 0 mod m. Isto é, o inverso
aditivo sempre existe.
• O inverso multiplicativo existe apenas para alguns elementos. Seja
a ∈ Z, o inverso a−1 é definido por:
a × a−1 ≡ 1 mod m.
• Se o inverso existir, podemos dividir esse elemento, uma vez que
b/a ≡ b × a−1 mod m.

Cabral (UFC) AES 09 de Outubro de 2025 7 / 47

 Teoria de Galois

Exemplo

• Considere o corpo finito GF (5) = {0, 1, 2, 3, 4}, como fica a tabela

para adicionar e multiplicar cada elemento do corpo?
• Considere o corpo finito GF (2) = {0, 1}, como fica a tabela para
adicionar e multiplicar cada elemento do corpo?

Cabral (UFC) AES 09 de Outubro de 2025 8 / 47

 Teoria de Galois

Extensão de Corpo GF (2m )

• No AES o corpo finito contém 256 elementos e é denotado por

GF (28 ).
• Se a ordem do corpo finito não for prima, e 28 claramente não é, as
operações de adição e multiplicação não podem ser representadas
pela adição e multiplicação módulo 28 .
• Como m > 1, são chamados de extensão de corpos.
• Para trabalhar com extensão de corpos usamos uma notação diferente
para representar os elementos do corpo e regras diferentes para a
adição e multiplicação dos elementos do corpo.

Cabral (UFC) AES 09 de Outubro de 2025 9 / 47

 Teoria de Galois

Extensão de Corpo GF (2m )

• Os elementos na extensão de corpo GF (2m ) são representados por

polinômios com coeficientes em GF (2).
• Os polinômios possuem grau máximo de m − 1, de modo que haja m
coeficientes no total para cada elemento.
• No corpo GF (28 ), que é usado pelo AES, cada elemento
A ∈ GF (28 ) é representado por:
A(x) = a7 x7 + . . . + a1 x + a0 ∈ GF (2) = {0, 1}.
• Note que exitem exatamente 256 = 28 polinômios.
• Esse conjunto de 256 polinômios é o corpo finito GF (28 ).
• É importante observar que todo polinômio pode simplesmente ser
armazenado digitalmente como um vetor de 8 bits.
A = (a7 , a6 , a5 , a4 , a3 , a2 , a1 , a0 ).

Cabral (UFC) AES 09 de Outubro de 2025 10 / 47

 Teoria de Galois

Adição e Subtração em GF (2m )

• A adição e subtração é feita de forma similar a adição de polinômios

normais.
• É feito, simplesmente, uma adição ou subtração dos coeficientes com
potências iguais de x. as adições e subtrações dos coeficientes são
feitas no corpo GF (2).

Cabral (UFC) AES 09 de Outubro de 2025 11 / 47

 Teoria de Galois

Adição e Subtração em GF (2m )

Adição e Subtração em GF (2m )

Sejam A(x), B(x) ∈ GF (2m ). A soma de dois elementos é computada
como segue:
m−1
X
C(x) = A(x) + B(x) = ci xi , ci ≡ ai + bi mod 2 (1)
i=0

e a subtração é calcula da seguinte forma:

m−1
X
C(x) = A(x) − B(x) = ci xi , ci ≡ ai − bi ≡ ai + bi mod 2 (2)
i=0

Cabral (UFC) AES 09 de Outubro de 2025 12 / 47

 Teoria de Galois

Multiplicação em GF (2m )

Se multiplicarmos dois elementos de um corpo finito GF (2m ) usando a

multiplicação polinomial normal temos:

A(x) × B(x) = (am−1 xm−1 + . . . + a0 ) × (bm−1 xm−1 + . . . + b0 )

C(x) = c2m−2 x2m−2 + . . . + c0 ,

onde

c0 = a0 b0 mod 2
c1 = a0 b1 + a1 b0 mod 2
.. ..
. .
c2m−2 = am−1 bm−1 mod 2

Cabral (UFC) AES 09 de Outubro de 2025 13 / 47

 Teoria de Galois

Multiplicação em GF (2m )

• Todos os coeficientes ai , bi , ci são elementos de GF (2).

• O produto polinomial C(x), normalmente, possui grau maior que
m − 1 e deve ser reduzido.
• Para fazer a redução, o polinômio obtido pela multiplicação é dividido
por um certo polinômio e consideramos apenas o resto da divisão.
• Para tal, precisamos de polinômios irredutı́veis.
• Assim, todo corpo GF (2m ) requer um polinômio irredutı́vel P (x) de
grau m com coeficientes em GF (2).

Cabral (UFC) AES 09 de Outubro de 2025 14 / 47

 Teoria de Galois

Multiplicação em GF (2m )

Multiplicação em extensão de corpo

Sejam A(x), B(x) ∈ GF (2m ) e seja
m
X
P (x) ≡ pi , pi ∈ GF (2) (3)
i=0

um polinômio irredutı́vel. A multiplicação de dois elemento A(x), B(x) é

calculada por:
C(X) ≡ A(x) × B(x) mod P (x). (4)

O AES usa o seguinte polinômio irredutı́vel: P (x) = x8 + x4 + x3 + x + 1.

Cabral (UFC) AES 09 de Outubro de 2025 15 / 47

 Teoria de Galois

Exemplo

Multiplique os polinômios A(x) = x3 + x2 + 1 e B(x) = x2 + x no corpo

GF (24 ). O polinômio irredutı́vel é dado por: P (X) = x4 + x + 1. Nota:É

importante não confundir multiplicação em GF (2m ) com multiplicação

inteira!

Cabral (UFC) AES 09 de Outubro de 2025 16 / 47

 Teoria de Galois

Inversão em GF (2m )

• Inversão em GF (28 ) é a operação principal da transformação de

substituição de bytes do AES.
• Para um dado corpo finito GF (2m ) e seu correspondente polinômio
irredutı́vel P (x), o inverso A−1 é um elemento diferente de zero
A ∈ GF (2m ) definido como:
A−1 (x) × A(x) = 1 mod P (x)

Cabral (UFC) AES 09 de Outubro de 2025 17 / 47

 Teoria de Galois

Tabela do inverso multiplicativo em GF (28 ) usado no AES

Cabral (UFC) AES 09 de Outubro de 2025 18 / 47

 Teoria de Galois

Exemplo

Da tabela anterior, o inverso de

x7 + x6 + x = (11000010)2 = (C2)hex = (xy)

é dado pelo elemento da linha C, coluna 2:

(2F )hex = (00101111)2 = x5 + x3 + x2 + x + 1

Pode-se verificar pela multiplicação

(x7 + x6 + x) × (x5 + x3 + x2 + x + 1) ≡ 1 mod P (x)

Cabral (UFC) AES 09 de Outubro de 2025 19 / 47

 Teoria de Galois

Advanced Encryption Standard (2001, NITS)

• História:
• Concurso público.
• Foram submetidos 21 algoritmos e 15 foram aceitos.
• 5 finalistas: MARC, RC6, Rijndael, Serpent e Twofish.
• A cifra Rijndael foi escolhida como padrão.
• Critérios
• Segurança
• Custo computacional em software e hardware.
• Simplicidade e flexibilidade no projeto.

Cabral (UFC) AES 09 de Outubro de 2025 20 / 47

 Teoria de Galois

Advanced Encryption Standard (2001, NITS)

• O algoritmo Advanced Encryption Standard (AES) foi publicado pelo

NIST em 2001.
• AES é um cifrador de bloco que encripta uma mensagem M de 128
bits usando uma chave k e produz um texto encriptado C de 128 bits.
• O tamanho da chave pode ser de 128, 192 ou 256 bits.
• O cifrador AES é denotado por AES-128, AES-192 ou AES-256
dependendo do tamanho da chave usada.

Cabral (UFC) AES 09 de Outubro de 2025 21 / 47

 Teoria de Galois

Advanced Encryption Standard (2001, NITS)

• A cifra AES recebe como entrada uma mensagem a ser encriptada M

e uma chave k.
• A mensagem M é tratada como um estado de 128 bits, que pode
ser visto como uma matriz S de 4 × 4 bytes.
• O AES modifica o estado iterativamente usando um conjunto de
operações, onde o número de iterações N depende do tamanho da
chave.
• O estado é modificado a cada rodada pelas seguintes transformações:
• SubBytes.
• ShiftRows.
• MixColumns.
• AddRoundKey.

Cabral (UFC) AES 09 de Outubro de 2025 22 / 47

 Teoria de Galois

AES - Encriptação

Cabral (UFC) AES 09 de Outubro de 2025 23 / 47

 Teoria de Galois

Estrutura interna AES

Cabral (UFC) AES 09 de Outubro de 2025 24 / 47

 Teoria de Galois

SubBytes

• A transformação SubBytes pode ser vista como uma linha de 16

S-boxes em paralelos, cada um como 8 bits de entrada e saı́da.
• Diferente do DES, todos os S-boxes são iguais.
• Nessa transformação, cada byte Ai do estado será trocado por:
S(Ai ) = Bi .
• O S-Box é o único elemento não linear do AES.
• O S-box de substituição é uma bijeção, isto é, cada uma das 256
possibilidades de entrada mapeiam em uma única saı́da.
• Essa propriedade permite inverter o S-box unicamente, o que é
necessário para a decriptação.
• Não existe nenhuma entrada tal que S(Ai ) = Ai .

Cabral (UFC) AES 09 de Outubro de 2025 25 / 47

 Teoria de Galois

S-box do AES

Cabral (UFC) AES 09 de Outubro de 2025 26 / 47

 Teoria de Galois

S-box do AES - Funcionamento interno

Cabral (UFC) AES 09 de Outubro de 2025 27 / 47

 Teoria de Galois

S-box do AES - Exemplo

Vamos assumir o S-box com entrada Ai = (11000010)2 = (C2)hex . Da

tabela de inversão podemos afirmar que:

A−1 = Bi′ = (2F )hex = (00101111)2

Aplicando a transformação afim ao vetor de bits anterior, temos:

Bi = (00100101)2 = (25)hex

Cabral (UFC) AES 09 de Outubro de 2025 28 / 47

 Teoria de Galois

Camada de difusão

• A camada de difusão é composta por duas subcamadas:

• As transformações ShiftRows e MixColumn.
• A difusão é espalhar a influencia dos bits pelo estado.
• A difusão é uma operação linear, assim sendo, se A e B forem
matrizes, DIFF(A) + DIFF(B) = DIFF(A + B).

Cabral (UFC) AES 09 de Outubro de 2025 29 / 47

 Teoria de Galois

ShiftRows

Realiza uma rotação nas linhas da matriz, isso assegura que os bytes de
uma coluna sejam dispersos nas quatro colunas.
   
t0 t1 t2 t3 t0 t1 t2 t3
t
 5 t6 t7 t4   t4 t5 t6 t7 
   
 = ShiftRows  (5)
t10 t11 t8 t9   t8 t9 t10 t11 
 

t15 t12 t13 t14 t12 t13 t14 t15

Cabral (UFC) AES 09 de Outubro de 2025 30 / 47

 Teoria de Galois

MixColumn

Calcula a multiplicação do estado, visto como matriz, com uma matriz

predefinida. Diferente da operação SubBytes, aqui as operações
aritméticas são realizadas no corpo binário F28 .
     
u0 u1 u2 u3 2 3 1 1 t0 t1 t2 t3
u
 4 u5 u6 u7  1 2 3 1  t5 t6 t7 t4 
   
= × (6)

 u8 u9 u10 u11  1 1 2 3 t10 t11 t8 t9 
 

u12 u13 u14 u15 3 1 1 2 t15 t12 t13 t14

Cabral (UFC) AES 09 de Outubro de 2025 31 / 47

 Teoria de Galois

MixColumn - Exemplo

Vamos assumir que a entrada do MixColumn é B = {25, 25, ..., 25}

02 · 25 = x · (x5 + x2 + 1)
x6 + x3 + x

03 · 25 = (x + 1) · (x5 + x2 + 1)
x6 + x3 + x + x5 + x2 + 1
x6 + x5 + x3 + x2 + x + 1
Os bytes de saı́da de C são computados por
(01 · 25 + 01 · 25 + 02 · 25 + 03 · 25)

Cabral (UFC) AES 09 de Outubro de 2025 32 / 47

 Teoria de Galois

AddRoundKey

Aplica uma operação XOR entre o estado e a chave de rodada

correspondente.

Cabral (UFC) AES 09 de Outubro de 2025 33 / 47

 Teoria de Galois

Algoritmo AES

Cabral (UFC) AES 09 de Outubro de 2025 34 / 47

 Teoria de Galois

Key Schedule

• Recebe a chave original como entrada e deriva as subchaves usadas

pelo algoritmo.
• O número de subchaves é igual ao número de rodadas mais um.
• Número de rodadas:
• 128 - 10 rodadas.
• 192 - 12 rodadas.
• 256 - 14 rodadas.
• As subchaves são calculadas recursivamente, isto é, para calcular ki , é
necessário conhecer ki−1

Cabral (UFC) AES 09 de Outubro de 2025 35 / 47

 Teoria de Galois

Key Schedule

• A chave de uma rodada i pode ser calculada da seguinte forma:

• Pegue a última coluna da matriz da chave e mova o byte do topo para
baixo (RotWord).
• Feito isso, passe cada byte dessa nova coluna pelo S-box (SubWord).
• Faça um XOR dessa coluna com uma constante de rodada (existe uma
constante para cada rodada).
• Finalmente, faça um XOR dessa coluna com a primeira coluna da fase
anterior (Rcon).
• Para as outras colunas, é só fazer um XOR da sua coluna com a coluna
anterior.

Cabral (UFC) AES 09 de Outubro de 2025 36 / 47

 Teoria de Galois

Key Schedule

Cabral (UFC) AES 09 de Outubro de 2025 37 / 47

 Teoria de Galois

Key Schedule

• Em software, é mais eficiente calcular todas as chaves de uma vez.

• Em hardware, normalmente é melhor calcular as chaves rodada por
rodada.

Cabral (UFC) AES 09 de Outubro de 2025 38 / 47

 Teoria de Galois

AES - Decriptação

• Como o AES não é baseado na rede de Feistel, todas as camadas

devem ser invertidas.
• Teremos:
• Inv subBytes.
• Inv ShiftRows.
• Inv MixColumns.
• A ordem das subchaves deve ser inversa.

Cabral (UFC) AES 09 de Outubro de 2025 39 / 47

 Teoria de Galois

AES - Dencriptação

Cabral (UFC) AES 09 de Outubro de 2025 40 / 47

 Teoria de Galois

AES - Estrutura interna Decriptação

Cabral (UFC) AES 09 de Outubro de 2025 41 / 47

 Teoria de Galois

Inv MixColumn

Calcula a multiplicação do estado, visto como matriz, com uma matriz

predefinida (inversa à matriz usada no MixColumn). As operações
aritméticas são realizadas no corpo binário F28 .
     
u0 u1 u2 u3 E B D 9 t0 t1 t2 t3
u
 4 u5 u6 u7   9 E B D   t5 t6 t7 t4 
    
= ×  (7)
 u8 u9 u10 u11  D 9 E B  t10 t11 t8 t9 


u12 u13 u14 u15 B D 9 E t15 t12 t13 t14

Cabral (UFC) AES 09 de Outubro de 2025 42 / 47

 Teoria de Galois

Inv ShiftRows

Realiza uma rotação nas linhas da matriz na ordem inversa do

ShiftRows.
   
t0 t1 t2 t3 t0 t1 t2 t3
t
 5 t6 t7 t4   t4 t5 t6 t7 
   
 = ShiftRows  (8)
t10 t11 t8 t9   t8 t9 t10 t11 
 

t15 t12 t13 t14 t12 t13 t14 t15

Cabral (UFC) AES 09 de Outubro de 2025 43 / 47

 Teoria de Galois

Inv SubBytes

• Usa-se um S-box inverso na decriptação.

• Como o S-box é uma bijeção, é possı́vel construir um S-box inverso
tal que: Ai = S −1 (S(Ai )), onde Ai e Bi são elementos do estado.

Cabral (UFC) AES 09 de Outubro de 2025 44 / 47

 Teoria de Galois

Inv SubBytes

Cabral (UFC) AES 09 de Outubro de 2025 45 / 47

 Teoria de Galois

Geração de Chaves - Decriptação

• As chaves de rodada devem ser geradas na ordem inversa.

• Na prática, geram-se as chaves na ordem original e usa na ordem
inversa.

Cabral (UFC) AES 09 de Outubro de 2025 46 / 47

 Teoria de Galois

Exercı́cios

• 4.3
• 4.4
• 4.5
• 4.6
• 4.11

Cabral (UFC) AES 09 de Outubro de 2025 47 / 47

 AES

Universidade Federal do Ceará - Campus Quixadá

Roberto Cabral
rbcabral@[Link]

09 de Outubro de 2025

Criptografia