unesp UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” CAMPUS DE GUARATINGUETÁ LUCIANO SAADE MINERVINO AES IP Core: Hardware Criptográfico Guaratinguetá 2013 LUCIANO SAADE MINERVINO AES IP Core: Hardware Criptográfico Trabalho de graduação apresentado ao Conselho de Curso de Graduação em Engenharia Elétrica da Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, como parte dos requisitos para obtenção do diploma de Graduação em Engenharia Elétrica. Orientador: Prof. Dr. Leonardo Mesquita Guaratinguetá 2013 M664a Minervino, Luciano Saade AES IP Core: hardware criptográfico / Luciano Saade Minervino – Guaratinguetá, 2016. 49 f : il. Bibliografia: f. 44-45 Trabalho de Graduação em Engenharia Elétrica – Universidade Estadual Paulista, Faculdade de Engenharia de Guaratinguetá, 2016. Orientador: Prof. Dr. Leonardo Mesquita 1. Hardware. 2. Criptografia. 3. Interfaces de usuário (Sistema de computador) I. Título CDU 004 MINERVINO, L. S. AES IP Core: Hardware Criptográfico. 2013. 49 f. Trabalho de Graduação (Engenharia Elétrica) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2013. RESUMO Neste trabalho foi desenvolvido um hardware criptográfico em FPGA. O algoritmo de criptografia utilizado foi o AES-256 implementado em VHDL. Na concepção do projeto bus- cou-se um equilíbrio entre área ocupada de hardware e velocidade de processamento. Tam- bém, através da comunicação UART e módulos de controle, foi criada uma interface com um computador pessoal permitindo o envio de arquivos para encriptação e decriptamento. PALAVRAS-CHAVE: Criptografia. FPGA. AES. MINERVINO, L. S. AES IP Core: Cryptographic Hardware. 2013. 49 f. Undergra- duate Work (Electrical Engineering) – Faculdade de Engenharia do Campus de Guaratinguetá, Universidade Estadual Paulista, Guaratinguetá, 2013. ABSTRACT This work developed a FPGA-based cryptographic hardware. The encryption algorithm used was AES-256 implemented in VHDL. The project aimed a balance between hardware fo- otprint and processing speed. Also, through the UART communication and control modules, an interface was created to a personal computer allowing sending files for encryption and de- cryption. KEYWORDS: Cryptography. FPGA. AES. LISTA DE ABREVIATURAS E SIGLAS AES Advanced Encryption Standard ASIC Application Specific Integrated Circuit DES Data Encryption Standard ECB Electronic CodeBook FIPS Federal Information Processing Standards FPGA Field Programmable Gate Array NIST National Institute of Standards and Technology NRE Non-recurring engineering OFB Output FeedBack ROM Read Only Memory RX Recepção SoC System on a Chip TX Transmissão UART Universal Asynchronous Receiver/Transmitter VHDL VHSIC Hardware Description Language VHSIC Very High Speed Integrated Circuits SUMÁRIO 1 INTRODUÇÃO.............................................................................................................9 1.1 FIELD-PROGRAMMABLE GATE ARRAY (FPGA)..................................................9 1.2 CRIPTOGRAFIA...........................................................................................................9 1.2.1 Criptografia Simétrica...............................................................................................10 1.2.2 Criptografia assimétrica.............................................................................................11 1.3 ÁLGEBRA ABSTRATA NA CRIPTOGRAFIA..........................................................12 1.4 ADVANCED ENCRYPTION STANDARD (AES).....................................................17 1.4.1 SubBytes......................................................................................................................19 1.4.2 SubBytes Inversa.........................................................................................................20 1.4.3 ShiftRows.....................................................................................................................20 1.4.4 ShiftRows Inversa.......................................................................................................20 1.4.5 MixColumns................................................................................................................21 1.4.6 MixColumns Inversa..................................................................................................21 1.4.7 AddRoundKey.............................................................................................................22 1.4.8 Expansão da Chave.....................................................................................................22 1.4.9 Decriptamento.............................................................................................................25 1.4.10 Decriptamento Equivalente.......................................................................................26 2 DESENVOLVIMENTO.............................................................................................27 2.1 CONSTRUÇÃO DOS COMPONENTES DO AES.....................................................27 2.2 CONSTRUÇÃO DA SUBBYTES E INVSUBBYTES...............................................28 2.2.1 Arquitetura compartilhada........................................................................................28 2.2.2 Análise da construção do módulo inversor multiplicativo......................................29 2.2.3 Mapeamento isomórfico e mapeamento isomórfico inverso...................................30 2.2.4 Adição em GF(24)........................................................................................................31 2.2.5 Potência quadrada em GF(24)....................................................................................31 2.2.6 Multiplicação por uma constante λ...........................................................................33 2.2.7 Multiplicação em GF(24)............................................................................................34 2.2.8 Multiplicação em GF(22)............................................................................................35 2.2.9 Multiplicação pela constante φ..................................................................................36 2.2.10 Inversão multiplicativa em GF(24)............................................................................37 2.3 MÓDULOS DE CONTROLE......................................................................................37 2.4 PROBLEMA DA METAESTABILIDADE..................................................................38 2.5 CIRCUITO EXPANSOR DA CHAVE.........................................................................39 2.6 MÓDULO AES COMPLETO......................................................................................39 3 CONCLUSÃO.............................................................................................................42 REFERÊNCIAS..........................................................................................................44 GLOSSÁRIO...............................................................................................................46 APÊNDICE A – Tabelas S-Box e Inverse S-Box......................................................47 9 1 INTRODUÇÃO A criptografia é muito utilizada atualmente, principalmente na internet e nos computa- dores. Seu objetivo é proteger dados sigilosos como números de cartões de crédito, ou tam- bém, o acesso a serviços como redes sem fio. No entanto, para se conseguir essa segurança a mais é necessário que o processador do computador, onde computador se refere a um equipa- mento genérico com capacidade de processamento de dados, gaste parte do seu tempo para encriptar ou decriptar esses dados. Quando a CPU não é muito rápida, como no caso dos dis- positivos móveis, os algoritmos de criptografia mais seguros, que fazem uso de operações ma- temáticas relativamente complexas, podem fazer uma diferença perceptível no desempenho do equipamento. Posto isso, nesse trabalho foi desenvolvido um coprocessador criptográfico em FPGA que permite terceirizar todo esse processo de criptografia liberando a CPU para ou- tras tarefas. Em seguida será definido alguns conceitos necessários para o entendimento do projeto. 1.1 FIELD-PROGRAMMABLE GATE ARRAY (FPGA) O field-programmable gate array (FPGA) é um dispositivo semicondutor que permite ao usuário programar suas funções e reconfigurar seu hardware. Qualquer função lógica que um circuito integrado de aplicação específica (ASIC) realize, poderá ser implementada no FPGA, com a vantagem dele poder ser atualizado após a instalação em campo; por isso o nome field-programmable. Outras vantagens, quando comparado a um projeto com ASIC, in- cluem: • Rápida prototipagem • Habilidade de reprogramar em campo para depurar • Menor custo Non-recurring engineering (NRE) • Longo ciclo de vida mitigando o risco da obsolescência Além disso, a execução dos algoritmos de criptografia em FPGA são mais rápidos que os mesmos algoritmos em software e por isso foram usados nesse projeto. 1.2 CRIPTOGRAFIA A criptografia é um conjunto de técnicas que transformam uma informação legível em algo incompreensível através de uma chave ou senha. Seu objetivo é esconder informação de pessoas não autorizadas, pois apenas com a chave a informação poderá ser recuperada. É im- portante que mesmo sabendo todo o processo de encriptação e decriptamento, não seja possí- 10 vel descobrir a informação sem a chave. Atualmente existem vários algoritmos de criptogra- fia, ou seja, sequências finitas de instruções que realizam a encriptação/decriptamento, dentre eles se destaca o AES utilizado neste trabalho. Os algoritmos de criptografia são classificados de acordo com o tratamento dado aos da- dos a serem processados e ao número de chaves. Se os dados são separados em blocos de ta- manho pré-definido para então serem processados, este será um algoritmo de bloco. No caso dos dados serem processados num fluxo contínuo, bit a bit, o algoritmo será de fluxo. Em re- lação ao número de chaves, a criptografia pode ser simétrica ou assimétrica. Na criptografia de chave simétrica os processos de cifragem e deciframento utilizam uma chave, ou seja, tan- to remetente quanto destinatário usam a mesma chave. Na criptografia assimétrica cada pes- soa tem um par de chaves denominado chave público-privada e chave privada. A chave pú- blico-privada é divulgada, enquanto a chave privada é mantida em segredo. Para mandar uma mensagem privada, o transmissor cifra a mensagem usando sua chave privada e a chave pú- blico-privada do destinatário pretendido, que deverá usar a sua respectiva chave privada e a chave público-privada do remetente para conseguir recuperar a mensagem original. Em segui- da esses processos serão detalhados. 1.2.1 Criptografia Simétrica Fonte: TRINTA; MACÊDO (2013) Figura 1 - Processo de criptografia por chave simétrica. 11 Como explicado anteriormente a criptografia simétrica utiliza apenas uma chave para encriptação e decriptamento da informação como ilustra a Figura 1. Tanto o remetente como o destinatário deverão manter a chave em segredo pois qual- quer pessoa com acesso a ela poderá descriptografar a mensagem. Além disso, não é possível saber quem enviou e quem recebeu a mensagem; em criptografia chamado de autenticidade e não-repúdio, respectivamente. Essas desvantagens criam um problema de gerenciamento das chaves que são geração, distribuição, backup, nova geração e o ciclo de vida em uma organi- zação. A criptografia de chave assimétrica, que será explicada em seguida, não tem esses pro- blemas, no entanto é lenta quando comparada à simétrica que por isso continua a ser usada em grandes volumes de dados. O AES usado aqui é de chave simétrica e também será descrito mais a frente. 1.2.2 Criptografia assimétrica A criptografia de chave assimétrica é também chamada de criptografia de chave pública por usar um mecanismo onde os usuários têm um par de chaves; a chave privada e a chave público-privada. A chave privada só é conhecida pelo usuário e a chave público-privada é ge- rada a partir da chave privada e de uma chave pública do sistema que é a mesma para todos usuário. Fazendo uma analogia onde as chaves são cores de tinta, a Figura 2 ilustra a comuni- cação entre duas pessoas e um observador que não pode interceptar a mensagem. Fonte: MACCORMICK (2012) Figura 2 - Processo de criptografia por chave assimétrica. 12 A Pessoa 1 e a Pessoa 2 têm suas cores privadas que não são conhecidas por ninguém além deles mesmos. Se a Pessoa 1 deseja mandar uma mensagem criptografada para Pessoa 2 é necessário que a Pessoa 1 use uma cor conhecida por ambas as partes sem deixar que o Ob- servador consiga descobrir essa cor. A Pessoa 1 e a Pessoa 2 misturam suas cores privadas com a cor pública obtendo cada um uma cor público-privada. Mesmo que o Observador olhe as cores público-privadas ele não conseguirá descobrir as cores privadas pois não é possível separá-las. Em seguida, a Pessoa 1 mistura sua cor privada com a cor público-privada da Pes- soa 2 gerando uma cor secreta que só a Pessoa 2 também conseguirá gerar se misturar sua cor privada com a cor público-privada da Pessoa 1. Dessa maneira tanto a Pessoa 1 quanto a Pes- soa 2 terão uma cor secreta compartilhada que poderá ser usada na comunicação. Esse mecanismo só funciona porque a operação de misturar cores não tem uma opera- ção inversa, ou seja, não é possível separar as cores depois que estão misturadas. Porém, na prática os computadores usam operações em bits no lugar de cores sendo necessário existir al- guma operação em bits que não seja inversível. E existe, é a exponenciação discreta, conside- rada não inversível porque não é conhecido nenhum método que permita calcular o logaritmo discreto de maneira eficiente nos computadores atuais. É curioso notar que cientistas estão trabalhando para desenvolver o computador quântico que em tese tornaria insegura toda a criptografia utilizada hoje em dia, uma vez que operações como o logaritmo discreto poderi- am ser facilmente resolvidas. No próximo tópico será detalhado como essa operação de expo- nenciação discreta é utilizada na criptografia. 1.3 ÁLGEBRA ABSTRATA NA CRIPTOGRAFIA Praticamente todos os algoritmos de criptografia, simétricos e assimétricos, envolvem operações aritméticas sobre inteiros. Se a operação de divisão é utilizada, então é preciso tra- balhar com a aritmética definida num campo. Isso porque na divisão todos os elementos não- nulos necessitam de um inverso multiplicativo. O campo é um elemento fundamental da álgebra abstrata e, a grosso modo, é definido como um conjunto onde é possível realizar adição, subtração, multiplicação e divisão sem sair desse conjunto. Nele a operação de divisão segue a seguinte regra: a /b=a(b−1 ) . Exemplos de campos são os números racionais, os reais e os complexos. Os inteiros não são um campo porque somente os elementos 1 e -1 têm um inverso multiplicativo que pertence aos inteiros, ou seja, (1−1 )=1 e ((−1) −1 )=1 pertencem, enquanto (2−1 )=0,5 não pertence. Se o conjunto de um campo tiver um número finito de elementos, esse campo será cha- 13 mado de campo finito ou campo de Galois, em homenagem ao matemático francês Évariste Galois. Dado um número primo p, define-se um campo finito de ordem p, GF(p), como o con- junto Zp de inteiros {0, 1, …, p-1} junto com as operações aritméticas de módulo p. Essas operações aritméticas modulares são algo que já estamos familiarizados: o relógio de pontei- ros tem 12 horas e, toda vez que excede as 12 horas, ele volta para 1 hora. Uma atividade que comece as 10 horas e dure 4 horas, terminará as 2, podemos dizer 10+4=2 nesse sistema de um relógio de 12 horas. Na matemática, a aritmética modular funciona da mesma maneira, exceto por dois detalhes: (i) o relógio pode ter qualquer tamanho, e (ii) o relógio começa em 0, não em 1. Por exemplo, escrevemos 11 mod 7=4 para indicar que 11 num sistema mó- dulo 7 é igual a 4, ou de outra forma, 11 divido por 7 tem resto 4. Por conveniência e para uma implementação eficiente, é preciso que o número de ele- mentos de um campo Zp utilize todos os padrões representáveis para um dado número de bits. Suponha que se deseje definir um algoritmo de criptografia que opere a 8-bits por vez, e uma das operações seja a divisão. Podemos representar nesse sistema os inteiros de 0 a 255. Po- rém, 256 não é um número primo, então se a aritmética for realizada em Z256, utilizando mó- dulo 256, esse conjunto de inteiros não será um campo. O número primo mais perto seria o 251, e o conjunto Z251 é um campo. Contudo, nesse caso os padrões de 8-bits representando os inteiros 251 a 255 não seriam usados, resultando em um uso ineficiente de espaço. Para contornar o problema, são usados campos representados por GF(pn), onde p é um número primo e n um inteiro positivo maior que 1. O total de elementos nesse campo é igual a pn e cada elemento é um polinômio de grau menor ou igual a n-1, com coeficientes pertencen- tes ao conjunto Zp. Nesse caso, as operações módulo pn não são usadas pois não gerariam um campo. No lugar, definiu-se as seguintes regras: 1. A aritmética nos coeficientes é realizada módulo p. Isso é, usa-se as regras da aritméti- ca para o campo finito Zp. 2. Se a multiplicação resultar em um polinômio de grau maior que n-1, então o polinô- mio será reduzido módulo algum polinômio irredutível m(x) de grau n. Isso é, o resto ao dividir por m(x). Para um polinômio f(x), o resto é expresso como r(x)=f(x) mod m(x). Para a criptografia os campos GF(2n) são os mais importantes. Isso fica fácil de entender ao analisarmos as operações em GF(2) apresentadas na Tabela 1. 14 Tabela 1 - Operações em GF(2). Operações em GF(2) a b a + b a x b 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Fonte: Próprio autor. A operação de soma é equivalente à operação lógica XOR e a multiplicação é equiva- lente à operação lógica AND, ambas de fácil implementação. Já a potência n vai indicar o nú- mero de elementos do campo e, nesse caso em específico, o número de bits usados nos blocos do algoritmo de criptografia. Outra propriedade importante dos campos GF(2n) pode ser observada através de outro exemplo. Supondo que se deseje construir um algoritmo de criptografia que utilize blocos de 3-bits e as operações de adição e multiplicação. Em Z8 a aritmética módulo 8 é bem definida, como mostram as Tabelas 2 e 3. Contudo, na multiplicação os números não-nulos não apare- cem em igual quantidade. Por exemplo, tem quatro ocorrências do número 3 e doze do 4. Por outro lado, existe o campo finito GF(23) cujas operações são mostradas nas Tabelas 4 e 5. Nesse caso, o número de ocorrências de números não-nulos é uniforme na multiplicação. A Tabela 6 resume esses resultados. Tabela 2 - Adição módulo 8. ADIÇÃO MÓDULO 8 + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 Fonte: Próprio autor. Tabela 3 - Multiplicação módulo 8. MULTIPLICAÇÃO MÓDULO 8 x 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 1 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1 Fonte: Próprio autor. 15 Os números destacados nas Tabelas 2, 3, 4 e 5 indicam que a operação inversa da res- pectiva tabela é possível. Por exemplo, na Tabela 2, 1+7=0 , portanto 7=(−1) ; na Ta- bela 3, 3⋅3=1 portanto 3=3−1 . Logo, algumas observações importantes podem ser tira- das: 1. Todos os elementos não-nulos da Tabela 5 têm um inverso multiplicativo, ao contrário da Tabela 3. 2. O esquema definido nas Tabelas 4 e 5 satisfaz os requisitos de um campo finito. 3. E também, intuitivamente, um algoritmo que mapeie os inteiros de forma desigual, como mostrado na Tabela 6, será criptograficamente mais fraco que outro que mapeie de forma igual. Tabela 6 - Ocorrências dos inteiros na multiplicação em Z8 e GF(23). OCORRÊNCIA DOS INTEIROS NA MULTIPLICAÇÃO EM Z8 E GF(23) INTEIRO OCORRÊNCIAS Z8 GF(23) 1 4 7 2 8 7 3 4 7 4 12 7 5 4 7 6 8 7 7 4 7 Fonte: Próprio autor. Tabela 4 - Adição em GF(23). ADIÇÃO EM GF(23) + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 0 3 2 5 4 7 6 2 2 3 0 1 6 7 4 5 3 3 2 1 0 7 6 5 4 4 4 5 6 7 0 1 2 3 5 5 4 7 6 1 0 3 2 6 6 7 4 5 2 3 0 1 7 7 6 5 4 3 2 1 0 Fonte: Próprio autor. Tabela 5 - Multiplicação em GF(23). MULTIPLICAÇÃO EM GF(23) x 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 3 1 7 5 3 0 3 6 5 7 4 1 2 4 0 4 3 7 6 2 5 1 5 0 5 1 4 2 7 3 6 6 0 6 7 1 5 3 2 4 7 0 7 5 2 1 6 4 3 Fonte: Próprio autor. 16 Uma técnica equivalente para definir um campo finito GF(2n) é através de um gerador. Um gerador g de um campo finito F de ordem q (contém q elementos) é um elemento do qual as primeiras q-1 potências geram todos os elementos não-nulos de F. Isso é, os elementos de F consistem em 0, g0, g1, …, gq-2. Pode ser mostrado que a raiz g de um polinômio irredutível é o gerador de um campo fi- nito definido por este polinômio. Aproveitando o exemplo do campo finito GF(23), se ele esti- ver definido sobre o polinômio irredutível x3 + x + 1, então o gerador g deve satisfazer f(g)=g3+g+1=0. Portanto, a solução dessa igualdade será g3=-g-1=g+1. Agora pode ser mos- trado que g de fato gera todos os polinômios de grau menor que 3: Para qualquer inteiro k, gk=gk mod 7. A Tabela 7 sintetiza esses resultados. Tabela 7 - Gerador para GF(23) usando x3+x+1. Representação em Potência Representação Polinomial Representação Binária Representação Decimal 0 0 000 0 g0(=g7) 1 001 1 g1 g 010 2 g2 g2 100 4 g3 g+1 011 3 g4 g2+g 110 6 g5 g2+g+1 111 7 g6 g2+1 101 5 Fonte: Próprio autor. A representação binária é determinada pelos coeficientes do polinômio em questão. Para o polinômio g2+1 os coeficientes são 1, 0 e 1, de maneira que em binário fique 101. A vantagem de se utilizar a representação em potência está no fato de tornar a multipli- cação mais simples. Para multiplicar (g2+g).(g2+1) normalmente aplicamos a distributiva ob- tendo (g4+g3+g2+1) e, em seguida, aplicamos (g4+g3+g2+1)mod(g3+g+1) para encontrar (g+1). Na representação em potência, o mesmo resultado é obtido se somarmos os expoentes módulo 7. Por exemplo, como g4=g2+g e g6=g2+1, então g4+g6=g(10 mod 7)=g3=g+1. g4 =g⋅(g3 )=g⋅(g+1)= g2 +g g5 =g⋅( g4 )=g⋅(g 2 + g)=g3 +g 2 =g2 + g+1 g6 =g⋅( g5 )=g⋅(g2 +g+1)=g3 + g2 +g=g2 +g+ g+1=g 2 +1 g7 =g⋅(g6 )=g⋅(g 2 +1)= g3 + g=g+ g+1=1=g0 17 Por último, se um campo possuí g=7 e utiliza aritmética módulo 19, um de seus elemen- tos é o 71≡7(mod 19). Os outros elementos podem ser gerados da mesma forma e, se fizermos 74=2401≡7(mod 19) ou 77=823543≡7(mod 19) obteremos o mesmo resultado. O logaritmo discreto é a operação que permite encontrar a potência x do gerador g dado um número N como em N=gx(mod p). É nessa operação que alguns algoritmos como o AES, discutido a se- guir, se baseiam. Pois os computadores não conseguem resolver esse problema de forma efici- ente. 1.4 ADVANCED ENCRYPTION STANDARD (AES) O National Institute of Standards and Technology (NIST) lançou em 1997 um concurso para eleger o sucessor do antigo padrão de criptografia, o Data Encryption Standard (DES). No concurso foi exigido dos candidatos que os algoritmos apresentados preenchessem os se- guintes pré-requisitos: • Ser divulgado publicamente. • Não possuir patentes. • Cifrar em blocos de 128 bits com chaves de 128, 192 e 256 bits. • Capacidade de ser implementado tanto em software quanto em hardware. • Ter maior rapidez em relação ao 3DES, uma variação recursiva do antigo padrão. Na primeira conferência em 1998 se apresentaram 15 candidatos. Na segunda, um ano depois, 5 finalistas foram indicados: MARS, Twofish, RC6, Serpent e Rijndael. Os belgas Vincent Rijmen e Joan Daemen se sagraram vencedores com o Rijndael. No AES o algoritmo recebe 128 bits ou 16 bytes de dados e uma chave que pode ser de 16, 24 ou 32 bytes (128, 192 ou 256 bits). Dependendo do tamanho da chave o algoritmo é chamado de AES-128, AES-192 ou AES-256. Na publicação do algoritmo o bloco de dados é retratado como uma matriz quadrada de bytes 4x4 chamada State. A cada passo da encriptação ou decriptamento ela é modificada. Após o passo final, ela é copiada para a matriz de saída. Essas operações estão ilustradas na Figura 3a. De maneira parecida, a chave também é retratada como uma matriz quadrada de bytes. A chave é expandida em um vetor de words (4 bytes) da chave da rodada. A Figura 3b mostra a expansão para uma chave de 128 bits. A ordem dos bytes dentro das matrizes é por coluna. Por exemplo, para dados de entrada de 128 bits, os primeiros 4 bytes ocuparão a pri- meira coluna. 18 O algoritmo consiste em N rodadas, onde o número de rodadas depende do tamanho da chave: 10 rodadas para chave de 16 bytes, 12 para chave de 24 bytes, e 14 para chave de 32 bytes. As primeiras N-1 rodadas consistem em quatro funções de transformação distintas: SubBytes, ShiftRows, MixColumns, e AddRoundKey. A rodada final contém apenas três trans- formações, e antes da primeira rodada tem uma transformação inicial (AddRoundKey), que pode ser considerada a Rodada 0. Cada transformação recebe uma ou mais matrizes 4x4 e de- volve uma matriz 4x4. A expansão da chave gera N+1 chaves de rodada, cada qual sendo uma matriz 4x4 distinta. As chaves da rodada servem como uma das entradas da transformação AddRoundKey. A Figura 4 resume todo esse processo. Fonte: STALLINGS (2010) Figura 3 - Estrutura dos dados no AES. 19 1.4.1 SubBytes A transformação SubBytes tem esse nome porque faz a substituição dos bytes da matriz State a partir de uma tabela chamada S-box. Essa tabela, apresentada no Apêndice A, é defini- da como uma matriz 16x16 de bytes que contém todas as 256 permutações possíveis para 8 bits. Cada byte da State é mapeado para um novo byte, da seguinte maneira: os quatro bits da esquerda são usados como endereço da linha na S-box e os quatro da direita como endereço da coluna. Por exemplo, o byte {95} (em hexadecimal) é substituído pelo byte da linha 9, coluna Figura 4 - Processo de encriptação no AES. Fonte: STALLINGS (2010) 20 5. Portanto, {95} é substituído por {2A}. A Figura 5 ilustra o processo. 1.4.2 SubBytes Inversa A transformação inversa da SubBytes é chamada InvSubBytes. Seu processo é idêntico ao da forma direta, só que a tabela utilizada é a Inverse S-box apresentada no Apêndice A. 1.4.3 ShiftRows Na transformação ShiftRows a primeira linha da matriz State não é alterada. A segunda linha é deslocada em anel para esquerda por 1 byte. A terceira e quarta linha são deslocadas da mesma maneira por 2 bytes e 3 bytes, respectivamente. A Figura 6 ilustra o processo. 1.4.4 ShiftRows Inversa A transformação inversa da ShiftRows é chamada InvShiftRows. O deslocamento das li- nhas se dá na direção oposta da ShiftRows, ou seja, as três últimas linhas são deslocadas em anel para direita em 1, 2 e 3 bytes, respectivamente. Fonte: STALLINGS (2010) Fonte: FIPS 197 (2001) Figura 5 - Transformação SubBytes. Figura 6 - Transformação ShiftRows. 21 1.4.5 MixColumns Essa transformação opera em cada coluna da matriz State individualmente. Cada byte de uma coluna é substituído por um valor que depende dos quatro bytes dessa coluna. Pode ser definida como a multiplicação matricial da State como segue: Cada elemento no produto matricial é a soma do produto dos elementos de uma linha por uma coluna. Nesse caso, as adições e multiplicações são realizadas em GF(28). A transformação MixColumns para uma coluna da State pode ser expressa como: 1.4.6 MixColumns Inversa A transformação inversa da MixColumns é chamada InvMixColumns, definida pela se- guinte multiplicação matricial: Generalizando para as colunas: Na documentação do AES é descrita outra representação das transformações MixColumns e InvMixColumns através de aritmética polinomial. Nela cada coluna da matriz State é definida como um polinômio de quatro termos com coeficientes em GF(28). Cada coluna é multiplica- da módulo (x4+1) pelo polinômio ({03}x3+{01}x2+{01}x+{02}) para a MixColumns, e pelo polinômio ({0B}x3+{0D}x2+{09}x+{0E}) para a InvMixColumns. [ 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 ][ s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 ]=[ s ' 0,0 s ' 0,1 s ' 0,2 s ' 0,3 s ' 1,0 s ' 1,1 s ' 1,2 s ' 1,3 s ' 2,0 s ' 2,1 s ' 2,2 s ' 2,3 s ' 3,0 s ' 3,1 s ' 3,2 s ' 3,3 ] [ 0E 0B 0D 09 09 0E 0B 0D 0D 09 0E 0B 0B 0D 09 0E ] [ s0,0 s0,1 s0,2 s0,3 s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s3,0 s3,1 s3,2 s3,3 ]=[ s ' 0,0 s ' 0,1 s ' 0,2 s ' 0,3 s ' 1,0 s ' 1,1 s ' 1,2 s ' 1,3 s ' 2,0 s ' 2,1 s ' 2,2 s ' 2,3 s ' 3,0 s ' 3,1 s ' 3,2 s ' 3,3 ] s ' 0, j=({0E}⋅s0, j)⊕({0B}⋅s1, j)⊕({0D}⋅s2, j)⊕({09}⋅s3, j) s ' 1, j=({09}⋅s0, j)⊕({0E}⋅s1, j)⊕({0B}⋅s2, j)⊕({0D}⋅s3, j) s ' 2, j=({0D}⋅s0, j)⊕({09}⋅s1, j)⊕({0E}⋅s2, j)⊕({0B}⋅s3, j) s ' 3, j=({0B}⋅s0, j)⊕({0D}⋅s1, j)⊕({09}⋅s2, j)⊕({0E}⋅s3, j) s ' 0, j=(2⋅s0, j)⊕(3⋅s1, j)⊕s2, j⊕s3, j s ' 1, j=s0, j⊕(2⋅s1, j)⊕(3⋅s2, j)⊕s3, j s ' 2, j=s0, j⊕s1, j⊕(2⋅s2, j)⊕(3⋅s3, j) s ' 3, j=(3⋅s0, j)⊕s1, j⊕s2, j⊕(2⋅s3, j) 22 1.4.7 AddRoundKey A AddRoundKey é uma transformação que aplica o operador lógico XOR entre os 128 bits da matriz State e os 128 bits da chave da rodada. 1.4.8 Expansão da Chave A expansão da chave varia conforme o tamanho da chave utilizada. Se a chave for de 128 bits cada chave de rodada ocupará 4 palavras (16 bytes), e como para esse tamanho de chave são necessárias 10 rodadas, o tamanho do vetor de palavras será de 44 palavras (176 bytes). Para uma chave de 192 bits a chave de rodada ocupará 6 palavras (24 bytes) e precisa- rá de 12 rodadas totalizando um vetor de 78 palavras (312 bytes). Para uma chave de 256 bits as chaves de rodada ocuparão 8 palavras (32 bytes) e precisarão de 14 rodadas totalizando 120 palavras (480 bytes). A Tabela 8 resume esses dados. Tabela 8 - Comprimento das chaves de rodada para os algoritmos do AES. Algoritmo Comprimento das Chaves de Rodada (palavras) Número de Rodadas AES-128 4 10 AES-192 6 12 AES-256 8 14 Fonte: Próprio autor. Todas as palavras geradas são salvas num vetor de palavras da rodada. As primeiras Nk palavras são preenchidas com a chave de cifra, e por isso Nk varia de 4, 6 ou 8 palavras para 128, 192 ou 256 bits, respectivamente. Cada palavra seguinte, w[i], é igual à operação XOR aplicada na palavra anterior, w[i-1], e a palavra Nk posições atrás, w[i-Nk]. Para palavras em posições múltiplas de Nk, uma transformação é aplicada a w[i-1] antes da XOR, seguida da XOR com uma constante de rodada, Rcon[i]. Essa transformação consiste na aplicação de um deslocamento em anel dos bytes da palavra (RotWord()), seguida pela substituição dos bytes utilizando a S-Box (SubWord()), assim como na transformação SubBytes. Para as chaves de 256 bits (Nk=8) a rotina de expansão é ligeiramente diferente que para 128 e 192 bits. Se i-4 for múltiplo de Nk(=8), então a transformação SubWord() é aplicada a w[i-1] antes da XOR. Por causa desta peculiaridade, a Figura 7 apresenta uma ilustração deste processo para uma chave de 256 bits. Seguindo a legenda da Figura 7 e observando a Figura 8 é possível generalizar o processo para 128 e 192 bits facilmente. 23 Figura 7 - Expansão de uma chave de 256 bits. Fonte: Próprio Autor 24 Figura 8 - Expansão de chaves de 192 e 128 bits. Fonte: Próprio Autor 25 1.4.9 Decriptamento As transformações do processo de encriptação podem ser invertidas e implementadas reversamente para gerar o processo de decriptamento. Como visto anteriormente, essas trans- formações são InvShiftRows(), InvSubBytes(), InvMixColumns() e AddRoundKey(). A Figura 9 mostra os processos de encriptação e decriptamento de maneira a facilitar a comparação. É possível notar que no decriptamento a sequência de transformações é diferente da en- criptação, enquanto que a expansão da chave permanece a mesma. No entanto, várias proprie- dades do algoritmo do AES permitem utilizar um decriptamento equivalente que tem a mesma sequência de transformações da encriptação (com as transformações trocadas pelas suas inver- sas). Fonte: STALLINGS (2010) Figura 9 - Processos de encriptação e decriptamento para uma chave de 128 bits. 26 1.4.10 Decriptamento Equivalente Duas propriedades permitem a construção do decriptamento equivalente: 1. As transformações SubBytes() e ShiftRows() comutam, de maneira que a ordem na qual são aplicadas não altera o resultado final. O mesmo é verdadeiro para suas inver- sas, InvSubBytes() e InvShiftRows(). 2. As operações MixColumns() e InvMixColumns() são lineares em relação às colunas, isto significa que InvMixColumns(State ⊕ Chave da Rodada)=InvMixColumns(State) ⊕ InvMixColumns(Chave da Rodada). Devido a essas propriedades é possível inverter a ordem de InvSubBytes() e InvShif- tRows(), mostradas na Figura 9, e inverter AddRoundKey() e InvMixColumns() usadas no laço das rodadas, após primeiro modificar as chaves com a transformação InvMixColumns(). As chaves da primeira e da última rodada não devem ser modificadas. A Figura 10 mostra o re- sultado dessas alterações. Essa estrutura é mais eficiente que a mostrada na Figura 9. Fonte: STALLINGS (2010) Figura 10 - Processo da decriptamento equivalente. 27 2 DESENVOLVIMENTO Cada transformação apresentada na introdução foi programada em VHDL apenas com lógica combinacional. As transformações foram arranjadas com suas inversas de maneira a criar componentes com um pino de seleção que permita optar pela encriptação ou decripta- mento. Por último, esses componentes foram conectados formando um componente maior ca- paz de executar o algoritmo do AES. Um cuidado especial foi dado às transformações SubBy- tes e InvSubBytes uma vez que se apresentam mais pesadas computacionalmente que as outras transformações. Buscando facilitar a utilização do módulo AES, também foram criados módulos de con- trole que permitem a comunicação entre o FPGA e um computador pessoal através do proto- colo UART. Um programa criado com a linguagem de programação Python rodando no com- putador faz a interface entre o usuário e o FPGA. Com ele é possível encriptar e decriptar qualquer tipo de arquivo. 2.1 CONSTRUÇÃO DOS COMPONENTES DO AES Para simplificar a utilização e o projeto, cada transformação com sua inversa foi posta num mesmo componente já que o número de entradas e saídas para elas são iguais. Um pino foi inserido para permitir selecionar a função desejada para o componente em questão. A Fi- gura 11 mostra a representação desses componentes chamados aqui de DualSubBytes, Du- alShiftRows e DualMixColumns. Figura 11 - Transformações com suas inversas no mesmo componente. Fonte: Próprio Autor 28 2.2 CONSTRUÇÃO DA SUBBYTES E INVSUBBYTES Uma das implementações mais comum e direta das transformações SubBytes e Inv- SubBytes é através do armazenamento das tabelas S-Box e Inverse S-Box em ROM. Esse mé- todo apresenta uma demora não gerenciável porque a memória ROM tem um tempo fixo de acesso para operações de leitura e escrita. Além disso, essa implementação é cara em termos de hardware. Uma maneira mais refinada é implementar as tabelas S-Box usando lógica combinacio- nal. As vantagens são uma menor área de ocupação de hardware e a possibilidade de pipeline para melhorar a performance. Os próximos tópicos abordarão as etapas dessa implementação 2.2.1 Arquitetura compartilhada A transformação SubBytes é construída tomando seu inverso multiplicativo em GF(28) seguido de uma transformação afim. Para a InvSubBytes a transformação afim inversa é apli- cada antes do inverso multiplicativo. Resumindo: SubBytes: → Inverso Multiplicativo em GF(28) → Transformação Afim InvSubBytes: → Transformação Afim Inversa → Inverso Multiplicativo em GF(28) A transformação afim e sua inversa podem ser representadas na forma matricial como mostra- do nas equações (1) e (2). AT (a)=[ 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 ]×[ a7 a6 a5 a4 a3 a2 a1 a0 ]⊕[ 0 1 1 0 0 0 1 1 ] (1) AT −1 (a)=[ 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 ]×[ a7 a6 a5 a4 a3 a2 a1 a0 ]⊕[ 0 0 0 0 0 1 0 1 ] (2) AT é a transformação afim e AT-1 sua inversa. O vetor a é o inverso multiplicativo do byte de 29 entrada vindo da matriz State. Como em SubBytes e InvSubBytes o inverso multiplicativo é utilizado, é possível compartilhar esse módulo numa arquitetura como mostra a Figura 12. No próximo tópico será discutido como construir tal módulo. 2.2.2 Análise da construção do módulo inversor multiplicativo Qualquer polinômio pode ser representado como bx+c, dado um polinômio irredutível x2+Ax+B. Assim, um elemento em GF(28) poderá ser representado por bx+c, onde b é o nib- ble (4 bits) mais significativo e c o menos significativo. O inverso multiplicativo para o polinômio bx+c pode ser calculado como mostra a equação (3). (bx+c ) −1 =b(b2 B+bcA+c2 ) −1 x+(c+bA)(b2 B+bcA+c2 ) −1 (3) Se o polinômio irredutível escolhido for x2+x+λ, então A=1 e B= λ. A equação (3) poderá ser simplificada para a equação (4). (bx+c ) −1 =b(b2 λ+c (b+c))−1 x+(c+b)(b2 λ+c (b+c))−1 (4) Na equação (4) é possível observar que existe as operações de multiplicação, adição, potência quadrada e inversão multiplicativa em GF(24). Cada operação dessa poderá ser transformada em blocos individuais na construção do módulo inversor multiplicativo. O circuito inversor multiplicativo em GF(28) pode ser produzido como na Figura 13. Os blocos da Figura 13 serão discutidos a seguir. É importante observar que o cálculo do inverso multiplicativo será feito decompondo o campo mais complexo GF(28) para campos de menor ordem em GF(21), GF(22) e GF((22)2). Para isso os seguintes polinômios irredutíveis serão usados: GF(22) → GF(2) : x2+x+1 GF((22)2) → GF(22) : x2+x+φ GF(((22)2)2) → GF((22)2) : x2+x+λ onde φ={10}2 e λ={1100}2. Fonte: MUI (2013) Figura 12 - SubBytes e InvSubBytes compartilhando o mesmo módulo inversor multiplicativo. 30 2.2.3 Mapeamento isomórfico e mapeamento isomórfico inverso O inverso multiplicativo de um campo composto, que é o campo definido em termos de outros campos mais elementares, não pode ser diretamente aplicado a um elemento baseado em GF(28). O elemento precisa ser mapeado para sua representação no campo composto via uma função isomórfica, δ. E também, após realizar a inversão multiplicativa, o resultado de- verá ser mapeado de volta para GF(28) via função isomórfica inversa, δ-1. Ambas as funções isomórficas podem ser representadas como matrizes 8x8. Se q for o elemento em GF(28), então o mapeamento isomórfico e seu inverso podem ser escritos como δ*q e δ-1*q, que são um caso de multiplicação matricial como mostrado nas equações (5) e (6), onde q7 é o bit mais significativo e q0 o bit menos significativo. δ×q=[ 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 ]×[ q7 q6 q5 q4 q3 q2 q1 q0 ] (5) Fonte: MUI (2013) Figura 13 - Módulo inversor multiplicativo para S-Box. 31 δ −1 ×q=[ 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 ]×[ q7 q6 q5 q4 q3 q2 q1 q0 ] (6) A multiplicação matricial pode ser traduzida para operação lógica XOR como mostra as equa- ções (7) e (8). δ×q=[ q7⊕q5 q7⊕q6⊕q4⊕q3⊕q2⊕q1 q7⊕q5⊕q3⊕q2 q7⊕q5⊕q3⊕q2⊕q1 q7⊕q6⊕q2⊕q1 q7⊕q4⊕q3⊕q2⊕q1 q6⊕q4⊕q1 q6⊕q1⊕q0 ] (7) δ −1 ×q=[ q7⊕q6⊕q5⊕q1 q6⊕q2 q6⊕q5⊕q1 q6⊕q5⊕q4⊕q2⊕q1 q5⊕q4⊕q3⊕q2⊕q1 q7⊕q4⊕q3⊕q2⊕q1 q5⊕q4 q6⊕q5⊕q4⊕q2⊕q0 ] (8) 2.2.4 Adição em GF(24) A adição de 2 elementos nesse campo pode ser traduzida como a operação XOR bit a bit entre os elementos. 2.2.5 Potência quadrada em GF(24) Fazendo k=q2, onde k e q são elementos em GF(24), representados pelos números biná- rios {k3k2 k1k0 }2 e {q3q2 q1q0}2 respectivamente. Então, pode-se escrever: k=(k3 k 2⏟ k H k1 k 0⏟ kL )=k H x+k L=(q3q2⏟ q H q1q0⏟ q L ) 2 =(qH x+qL) 2 k=qH 2 x2 +qH qL x+qH qL x+qL 2 =qH 2 x2 +qL 2 (9) 32 O termo x2 pode ser reduzido módulo o polinômio x2+x+φ. Definindo x2=x+φ e substi- tuindo x2 na equação (9) produz: k=qH 2 ( x+ϕ)+qL 2 k=qH 2 ⏟ k H x+(qH 2 ϕ+qL 2 )⏟ k L ∈ GF (22 ) (10) A equação (10) está agora decomposta para GF(22). Decompondo kH e kL mais uma vez para GF(2) levará à fórmula para computar a operação de elevar à segunda potência em GF(24). k H=qH 2 =(q3 q2) 2 =(q3 x+q2) 2 k H=q3 2 x2 +q3 q2 x+q3 q2 x+q2 2 =(q3 q2) 2 =(q3 x+q2) 2 =q3 x2 +q2 (11) Usando o polinômio irredutível x2+x+1, e fazendo x2=x+1, x2 é substituído na equação (11) obtendo uma nova expressão. k H=q3( x+1)+q2 k 3 x+k 2=q3 x+(q2+q3) ∈ GF (2) (12) O termo kL é decomposto de maneira similar. E φ é reescrito na sua representação poli- nomial. k L=qH 2 ϕ+bL 2 =(q3 q2) 2 {10 }2+(q1 q0) 2 k L=(q3 x+q2) 2 ({1 }2 x+0)+(q1 x+q0) 2 k L=(q3 2 x2 +q2 q3 x+q2 q3 x+q2 2 )(x )+(q1 2 x2 +q0 q1 x+q0 q1 x+q0 2 ) k L=q3 x3 +q2 x+q1 x2 +q0 (13) Como feito anteriormente, o termo x2 pode ser substituído visto que x2=x+1. Para o caso de x3, ele pode ser obtido multiplicando x2 por x. Isso é, x3=x(x)+x=x2+x. Substituindo x2, x3=x+1+x. Os dois termos x se cancelam, deixando x3=1. Substituindo agora na equação (13) vem: k L=q3(1)+q2 x+q1(x+1)+q0 k 1 x+k 0=(q2+q1) x+(q3+q1+q0) ∈ GF (2) (14) Das equações (12) e (14), a fórmula para computar a operação de elevar a segunda po- tência em GF(24) pode ser adquirida como mostrado abaixo. k 3=q3 k 2=q3⊕q2 k 1=q2⊕q1 k 0=q3⊕q1⊕q0 (15) 33 A equação (15) pode ser mapeada para o diagrama lógico de hardware mostrado na Fi- gura 14. 2.2.6 Multiplicação por uma constante λ Fazendo k=qλ, onde k={k3k2k1k0}2, q={q3q2q1q0}2 e λ={1100}2 são elementos de GF(24). k=(k3 k 2⏟ k H k1 k 0⏟ kL )=k H x+k L=(q3q2⏟ q H q1q0⏟ q L )(11⏟ λH 00⏟ λL ) k=(q H x+qL)(λH x+λ L) λL pode ser cancelado já que λL={00 }2 . k=qH λH x2 +qL λH x (16) A redução modular da equação (16) pode ser feita substituindo x2=x+ φ e usando o poli- nômio irredutível x2+x+φ. k=qH λH (x+ϕ)+qL λH x k=(q H λH+qLλ H)⏟ k H x+(qH λH ϕ)⏟ kL ∈ GF (22 ) (17) Como feito anteriormente, os termos kH e kL podem ser quebrados para GF(2) na equa- ção (17). k H=qH λH +qL λH k H=(q3 q2)(112)+(q1 q0)(112) k H=(q3 x+q2)(x+1)+(q1 x+q0)( x+1) k H=q3 x2 +(q3+q2) x+q2+q1 x2 +(q1+q0) x+q0 (18) Substituindo x2=x+1, na equação (18): k H=q3( x+1)+(q3+q2) x+q2+q1( x+1)+(q1+q0) x+q0 k H=(q3+q3+q2+q1+q1+q0) x+(q3+q2+q1+q0) k 3 x+k 2=(q2+q0)x+(q3+q2+q1+q0) ∈ GF (2) (19) O mesmo procedimento é tomado para decompor kL para GF(2). k L=qH λH ϕ Fonte: MUI (2013) Figura 14 - Diagrama da operação de elevar à segunda potência em GF(24). 34 k L=(q3 q2)(112)(102) k L=(q3 x+q2)( x+1)( x) k L=q3 x3 +q2 x2 +q3 x2 +q2 x (20) Novamente, o termo x2 pode ser substituído na equação (20) já que x2=x+1. Também, x3 é substituído com x3=1, o mesmo método usado anteriormente. k L=q3(1)+q2( x+1)+q3(x+1)+q2 x k L=(q3+q2+q2)x+(q3+q3+q2) k 1 x+k 0=(q3) x+(q2) ∈ GF (2) (21) Das equações (19) e (21) combinadas, a fórmula para computar a multiplicação por uma constante λ é mostrada abaixo. k 3=q2⊕q0 k 2=q3⊕q2⊕q1⊕q0 k 1=q3 k 0=q2 (22) Equivalentemente, a equação (22) pode ser mapeada para um diagrama lógico de hardware como mostra a Figura 15. 2.2.7 Multiplicação em GF(24) Fazendo k=qw, onde k={k3k2k1k0}2, q={q3q2q1q0}2 e w={w3w2w1w0}2 são elementos de GF(24). k=(k3 k 2⏟ k H k1 k 0⏟ kL )=k H x+k L=(q3q2⏟ q H q1q0⏟ q L )(w3 w2⏟ wH w1 w0⏟ wL )=(qH x+qL)(wH x+wL) k=(q H wH ) x2 +(qH wL+qL wH ) x+qL wL (23) Substituindo o termo x2 com x2=x+φ na equação (23): k=(q H wH )(x+ϕ)+(qH w L+qLwH ) x+q LwL k=k H x+k L=(qH wH +qH wL+qL wH ) x+qH wH ϕ+qL wL ∈ GF (22 ) (24) Fonte: MUI (2013) Figura 15 - Diagrama da operação de multiplicar pela constante λ. 35 A equação (24) está na forma de GF(22). Pode ser observado que nela existem as opera- ções de adição e multiplicação em GF(22). A adição em GF(22) nada mais é que a operação XOR bit a bit, como mencionado anteriormente. Por outro lado, a multiplicação em GF(22) precisa ser decomposta para GF(2) para ser implementada em hardware. Se isso fosse feito, a equação (24) ficaria muito complexa. Assim, a fórmula para multiplicação em GF(22) e para multiplicação pela constante φ serão deduzidas nos próximos tópicos. A Figura 16 mostra a implementação em hardware para multiplicação em GF(24). 2.2.8 Multiplicação em GF(22) Fazendo k=qw, onde k={k1k0}2, q={q1q0}2 e w={w1w0}2 são elementos de GF(22). k=(k1 k 0)=k 1 x+k 0=(q1 q0)(w1 w0)=(q1 x+q0)(w1 x+w0) k=q1 w1 x2 +q0 w1 x+q1 w 0 x+q0 w0 (25) O termo x2 pode ser substituído com x2=x+1 na equação (25): k=q1 w1( x+1)+q0 w1 x+q1 w0 x+q0 w0 k 1 x+k 0=(q1 w1+q0 w1+q1 w0) x+(q1 w1+q0 w0) ∈ GF (2) (26) A equação (26) pode ser implementada em hardware visto que a multiplicação em GF(2) envolve somente o uso de portas AND. A fórmula para computar a multiplicação em GF(2) é mostrada na equação (27). k 1=q1 w1⊕q0 w1⊕q1 w0 k 0=q1 w1⊕q0 w0 (27) A Figura 17 ilustra a implementação em hardware. Fonte: MUI (2013) Figura 16 - Diagrama da operação de multiplicação em GF(24). 36 A implementação da Figura 17 difere da equação (27) no cálculo de k1. Porém, como mostrado na equação (28), o resultado é o mesmo. k 1=(q1⊕q0)(w1⊕w0)⊕(q0 w0) k 1=(q1 w1)⊕(q0 w1)⊕(q1 w0)⊕(q0 w0)⊕(q0 w0) k 1=(q1 w1)⊕(q0 w1)⊕(q1 w0) (28) 2.2.9 Multiplicação pela constante φ Fazendo k=qφ, onde k={k1k0}2, q={q1q0}2 e φ={10}2 são elementos de GF(22). k=k 1 x+k 0=(q1 q0)(102)=(q1 x+q0)( x) k=q1 x2 +q0 x (29) Substituindo x2 com x2=x+1 na equação (29): k=q1( x+1)+q0 x k=(q1+q0) x+(q1) ∈ GF (2) (30) Da equação (30), a fórmula para computar a operação de multiplicação pela constante φ pode ser escrita como na equação (31). k 1=q1⊕q0 k 0=q1 (31) A implementação em hardware da equação (31) é mostrada na Figura 18. Fonte: MUI (2013) Fonte: MUI (2013) Figura 17 - Diagrama da operação de multiplicação em GF(2). Figura 18 - Diagrama da operação de multiplicação por uma constante φ. 37 2.2.10 Inversão multiplicativa em GF(24) Pela dificuldade de se deduzir a fórmula para o cálculo dos inversos multiplicativos, os resultados serão apenas expostos na equação (32). q3 −1 =q3⊕q3 q2 q1⊕q3 q0⊕q2 q2 −1 =q3 q2 q1⊕q3 q2 q0⊕q3 q0⊕q2⊕q2 q1 q1 −1 =q3⊕q3 q2 q1⊕q3 q1 q0⊕q2⊕q2 q0⊕q1 q0 −1 =q3 q2 q1⊕q3 q2 q0⊕q3 q1⊕q3 q1q0⊕q3 q0⊕q2⊕q2 q1⊕q2 q1 q0⊕q1⊕q0 (32) 2.3 MÓDULOS DE CONTROLE Para a recepção e envio de dados entre o FPGA e o computador foram criados dois mó- dulos que utilizam o protocolo UART para comunicação. Ambos foram implementados para funcionarem na taxa de 115200 bits/s que é uma taxa padrão. Não há bit de paridade e são usados 10 bits no total: um de início, oito de dados e um de parada. A Figura 19 ilustra esses módulos. No módulo receptor foi incluído um mecanismo que interpreta o primeiro byte recebido como uma instrução que indicará qual o tipo de dado dos próximos 16 bytes a serem recebi- dos. Por exemplo, se o primeiro byte for {01}16, os próximos 16 bytes recebidos serão enca- minhados como a primeira metade da chave, ou seja, a saída Key_0 na Figura 19 disponibili- zará os dados para o módulo AES. Uma exceção ocorre com a instrução {05}16 que não espera por mais bytes já que instrui o módulo AES a iniciar o processo. A Tabela 9 apresenta todas as instruções possíveis. Fonte: Próprio Autor Figura 19 - Módulos de recepção e transmissão. 38 Tabela 9 - Instruções para o módulo receptor. Instrução Significado {01}16 Primeira metade da chave {02}16 Segunda metade da chave {03}16 Dados para encriptação {04}16 Dados para decriptamento {05}16 Iniciar o processo Fonte: Próprio autor. 2.4 PROBLEMA DA METAESTABILIDADE Qualquer entrada assíncrona aplicada a um circuito em domínio síncrono (com clock) será uma fonte de instabilidade, uma vez que sempre haverá a possibilidade do circuito sín- crono amostrar o sinal assíncrono numa transição. Do ponto de vista das especificações, elementos síncronos como flip-flops têm um tem- po de configuração (setup time) e um tempo de espera (hold time). Pela sua natureza, uma en- trada assíncrona não pode ser confiada a respeitar essas especificações, e assim podem ocorrer transições que caiam na janela de tempo delimitada por elas. Quando isso acontece, três cená- rios são possíveis: 1. O estado do sinal anterior à transição é usado. 2. O estado do sinal posterior à transição é usado. 3. O flip-flop se torna metaestável. Os dois primeiros casos não têm grande consequência, já que o sinal é assíncrono. Porém, o terceiro caso pode danificar um sistema síncrono. Ele é causado pelo equilíbrio instável onde a tensão do componente se encontra em níveis intermediários. É impossível determinar o tem- po que o problema persistirá. A abordagem mais comum para minimizar o problema da propagação da metaestabili- dade em sistemas síncronos é usar um circuito de sincronismo para receber a entrada assíncro- na e alinhá-la com a temporização do resto do sistema. A Figura 20 apresenta o circuito sin- cronizador com dois flip-flops D, utilizado nesse projeto. 39 2.5 CIRCUITO EXPANSOR DA CHAVE Procurando minimizar o espaço ocupado em hardware, o circuito expansor da chave foi construído como um módulo que gera apenas uma chave de rodada por vez. Por causa disso, existe um pino de entrada no módulo para as constantes da rodada (Rcon). Apenas realimentando o módulo ilustrado na Figura 21, é possível gerar todas as chaves de rodada. A saída foi dividida em Key_0 e Key_1 porque para o AES-256 cada rodada utiliza apenas 128 bits da chave gerada por vez. 2.6 MÓDULO AES COMPLETO Para a construção do módulo AES todos os componentes criados até agora foram conec- tados formando um componente maior, o módulo AES. Na prática, esse invólucro que junta os componentes serve apenas para inserir um sinal de relógio que controle as entradas e saídas dos componentes. É nele que é definida a sequência de execução dos componentes. A Figura Fonte: Própio Autor Fonte: Próprio Autor Figura 20 - Circuito sincronizador com dois flip-flops tipo D. Figura 21 - Módulo expansor de chave de 256 bits. 40 23 mostra um esquemático do circuito completo. A implementação do circuito completo no FPGA, incluindo os módulos de controle, ocupa um total de 8697 elementos lógicos e funciona na frequência de 29,94 [MHz]. É importante observar que o circuito foi implementado no modo de operação electronic codebook (ECB) por ser o mais didático. Nesse modo, cada bloco cifrado é independente dos outros blocos cifrados de maneira que, se houver algum dado repetido, o resultado também será repetido. O ECB não é recomendado em aplicações práticas pois podem ocorrer situações como a mostrada na Figura 22. Um dos modos de operação que é muito utilizado e que resolve o problema apresentado na Figura 22 é o modo output feedback (OFB). Nele, após a encriptação de um bloco, a opera- ção XOR é aplicada entre esse bloco e o bloco anterior. Na primeira rodada um vetor de inici- alização é aleatoriamente gerado para permitir essa operação. Fonte: WIKIPEDIA (2013) Figura 22 - Comparação de imagem criptografada no modo ECB. 41 Fonte: Próprio Autor Figura 23 - Circuito esquemático completo do módulo AES. 42 3 CONCLUSÃO Por causa da intensa lógica que aumenta o tempo de resposta dos circuitos utilizados nas transformações SubBytes e InvSubBytes a frequência de trabalho do sistema é baixa. Outro ponto crítico em relação ao tempo é a comunicação serial. Nela os dados são transmitidos a taxa de 115200 bits/s, ou seja, para cada bloco de 16 bytes o tempo gasto na transmissão e re- cepção é de aproximadamente 3 ms. Se cada bloco leva em torno de 3,34 μs para ser processa- do, o tempo gasto para enviar e receber os dados é um pouco menor que 1000 vezes o tempo de processamento. A vantagem é que para esse tipo de comunicação são necessários apenas 3 fios. Caso a interface paralela fosse usada, seriam necessários pelo menos 33 fios. Uma solução para o primeiro problema seria incluir estágios de pipeline para dividir o tempo de resposta do circuito aumentando a frequência de trabalho do sistema em troca de um maior espaço em hardware. No entanto, como o tempo de processamento é cerca de 1000 ve- zes menor que o tempo da transmissão e recepção, mesmo que a melhora fosse grande, ainda sim seria desprezível. Para testar a eficiência do módulo AES foi utilizado um computador baseado em um system on a chip (SoC) Broadcom BCM2835 que inclui um processador ARM1176JZF-S de 700 MHz e 512 MB de memória RAM. Arquivos de tamanhos variáveis foram encriptados e decriptados através de dois programas. O primeiro programa é uma implementação em software do algoritmo AES-256 e o outro programa é uma interface para o módulo AES do FPGA. No teste foram medidos os tempos que cada implementação gastava para processar os arquivos de teste. Os resultados foram plotados no gráfico da Figura 24. Fonte: Próprio Autor Figura 24 - Comparação entre a velocidade de processamento das implementações AES. 43 Pelo gráfico da Figura 24 fica evidente a vantagem crescente com o tamanho dos arqui- vos. Portanto, a implementação do módulo AES em FPGA como coprocessador criptográfico é vantajosa em termos de velocidade quando comparada à solução em software, principalmen- te em computadores com configurações modestas, como os de dispositivos móveis. 44 REFERÊNCIAS ALTERA. FPGAs. Disponível em: < http://www.altera.com/products/fpga.html > Acesso em: 11 dez. 2013. FIPS-197. Federal information processing standards publication: advanced encryption standard. 2001. Disponível em: < http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf > Acesso em: 11 dez. 2013. FREIDIN, P. Tell me about metastability. Disponível em: < http://www.fpga- faq.com/FAQ_Pages/0017_Tell_me_about_metastables.htm > Acesso em: 11 dez. 2013. GOMES, O.S.M.. Desenvolvimento de hardware configurável de criptografia simétrica utilizando fpga e linguagem vhdl. 2011. 51 p. Dissertação (Mestrado) – Universidade Federal de Itajubá, Itajubá, 2011. MACCORMICK, J. Nine algorithms that changed the future: the ingenious ideas that drive today's computers. New Jersey: Princeton University Press, 2012. MUI, E.N. Practical implementation of Rijndael s-box using combinational logic. Disponível em: < http://www.xess.com/static/media/projects/Rijndael_SBox.pdf > Acesso em: 11 dez. 2013. PISA, P. O que é criptografia?. Disponível em: < http://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html > Acesso em: 11 dez. 2013. STALLINGS, W. Cryptography and network security: principles and practice. 5th ed. Boston: Prentice Hall, 2010. TRINTA, F.A.M; MACÊDO, C. Um estudo sobre criptografia e assinatura digital. Disponível em: Acesso em: 11 dez. 2013. http://www.xess.com/static/media/projects/Rijndael_SBox.pdf http://www.xess.com/static/media/projects/Rijndael_SBox.pdf http://www.xess.com/static/media/projects/Rijndael_SBox.pdf http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf http://www.di.ufpe.br/~flash/ais98/cripto/criptografia.htm http://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html http://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html http://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html http://www.fpga-faq.com/FAQ_Pages/0017_Tell_me_about_metastables.htm http://www.fpga-faq.com/FAQ_Pages/0017_Tell_me_about_metastables.htm http://www.fpga-faq.com/FAQ_Pages/0017_Tell_me_about_metastables.htm http://www.fpga-faq.com/FAQ_Pages/0017_Tell_me_about_metastables.htm http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf http://www.altera.com/products/fpga.html http://www.altera.com/products/fpga.html http://www.altera.com/products/fpga.html 45 WIKIPEDIA, A enciclopédia livre. Algoritmo de chave simétrica. Disponível em: < http://pt.wikipedia.org/wiki/Algoritmo_de_chave_simétrica > Acesso em: 11 dez. 2013. WIKIPEDIA, The free encyclopedia. Block cipher mode of operation. Disponível em: Acesso em: 11 dez. 2013. http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation http://pt.wikipedia.org/wiki/Algoritmo_de_chave_sim%C3%A9trica http://pt.wikipedia.org/wiki/Algoritmo_de_chave_sim%C3%A9trica http://pt.wikipedia.org/wiki/Algoritmo_de_chave_sim%C3%A9trica 46 GLOSSÁRIO Non-recurring engineering. Refere-se ao custo total de pesquisa, desenvolvimento, design e teste de um novo produto. Quando se está orçando um projeto este custo deverá ser analisado para saber se o produto será rentável. Diferente dos custos de produção, o NRE é um custo fixo em termos econômicos. 47 APÊNDICE A – Tabelas S-Box e Inverse S-Box