CRIPTOGRAFIA
UESC SINFORM 2011
César Bravo
[email protected]
Referencias bibliográficas
• Routo Terada. Segurança de dados - criptografia em
redes de computador, Segunda Edição (livro p/ Ed. E.
Blücher, 2008).
• Viktoria Tkotz. Criptografia - Segredos Embalados para
Viagem. Novatec Editora, 2005, ISBN 85-7522-071-3.
• Severino Collier Coutinho. Números Inteiros e
Criptografia RSA. 213 páginas. Publicação: IMPA, 2007.
ISBN: 978-85-244-0124-4. Segunda Edição.
• Paulo Ribenboim. Números Primos: Mistérios e Recordes.
280 páginas. Publicação: IMPA, 2001. ISBN: 978-85-2440168-8.
2
Conferencias IACR
• International Association for Cryptologic
Research (IACR): http://www.iacr.org/
• Asiacrypt 2011, December 4-December 8,
2011, Seoul, Korea.
• Eurocrypt 2012, April 15-April 19, 2012,
Cambridge, UK.
• Crypto 2012, August 19-August 23, 2012,
Santa Barbara, USA.
3
Motivação
4
Motivação
www.oramag.com
5
Informe publicitário da Intel entre as páginas 24 e 25
Motivação
6
Motivação
São duas páginas que resumem o white paper de 13 páginas do L. Xu
7
Leslie Xu. WHITE PAPER: Securing the
Enterprise with Intel® AES-NI
•
•
www.intel.com/Assets/en_US/PDF/whitepaper/Intel_AES-NI_White_Paper.pdf
The Advanced Encryption Standard (AES)
Recommendations for Using inter AES-NI:
is a strong encryption algorithm adopted
• Secure Web transactions: (improve SSL
in 2001 by the U.S. government.
performance, accelerating e-commerce
sites).
It uses a key that can be 128, 192, or 256
bits long and is well respected as a means
of protecting data.
•
At the same time, AES implementation
can be very resource intensive, limiting its
use by many DBAs and solution architects.
•
In response to the need to implement
encryption
without
unacceptable
performance impacts to the system as a
whole, Intel introduced AES New
Instructions (AES-NI).
•
Supported by the Intel' Xeon® processor
5600 series, AES-NI is a set of processor
instructions
that
accelerate
AES
encryption and decryption, for greater
overall solution performance.
•
Enterprise applications: (speed up
robust
encryption
for
e-mail,
collaborative applications, enterprise
resource
planning,
customer
relationship management, and other
operations).
•
Full disk encryption (FOE):
The
growing popularity of FDE through
features such as Microsoft Windows
BitLocker demonstrates the value of
speeding up those operations.
8
Performance (vs) letra pequena
•
Intel may make changes to specifications and product descriptions at any time,
without notice.
•
Designers must not rely on the absence or characteristics of any features or
instructions marked 'reserved" or "undefined."
•
Intel reserves these for future definition and shall have no responsibility
whatsoever for conflicts or incompatibilities arising from future changes to them.
•
The information here is subject to change without notice.
•
Do not finalize a design with this information.
•
The products described in this document may contain design defects or errors
known as errata which may cause the product to deviate from published
specifications.
9
Performance (vs) letra pequena
• Intel may make changes to specifications and product descriptions at any
time, without notice.
• Designers must not rely on the absence or characteristics of any features
or instructions marked 'reserved" or "undefined."
• Intel reserves these for future definition and shall have no responsibility
whatsoever for conflicts or incompatibilities arising from future changes to
them.
• The information here is subject to change without notice.
• Do not finalize a design with this information.
• The products described in this document may contain design defects or
errors known as errata which may cause the product to deviate from
published specifications.
10
Detalhes técnicos sobre AES-NI
• Shay Gueron. White paper: Intel® Advanced Encryption
Standard (AES) Instructions Set. 79 pags. January 2010
(26/1/2010),
Rev.
3.0,
Intel
Corporation.
http://software.intel.com/en-us/articles/intel-advancedencryption-standard-aes-instructions-set/
http://software.intel.com/file/24917
• Shay Gueron; Michael E. Kounavis. White paper: Intel® CarryLess Multiplication Instruction and its Usage for Computing
the GCM Mode. 72 pags. January, 2010 (26/1/2010), Rev. 2.0,
Intel
Corporation.
http://software.intel.com/enus/articles/intel-carry-less-multiplication-instruction-and-itsusage-for-computing-the-gcm-mode/
http://software.intel.com/file/24918
11
Roteiro
• Definições básicas
• Algoritmo AES.
• Soluções Hardware-software
12
Definições básicas
• A Criptografia é a ciência de escrever mensagens
que ninguém deveria poder ler, exceto o
remetente e o destinatário.
• A Criptologia é o estudo da escrita cifrada e se
ocupa com a CRIPTOGRAFIA, a escrita secreta.
• A Criptoanálise é a ciência de "quebrar" o
método utilizado, decifrar e ler estas mensagens
cifradas.
13
• As palavras, caracteres ou letras da mensagem
original inteligível constituem a Mensagem ou
Texto Original, também chamado de
Mensagem ou Texto Claro.
• As palavras, caracteres ou letras da mensagem
cifrada são chamados de Texto Cifrado,
Mensagem Cifrada ou Criptograma.
• O processo de converter Texto Claro em Texto
Cifrado é chamado de composição de cifra ou
cifragem ou encriptação e o inverso é
chamado de decifração.
14
• No caso de criptografia digital, qualquer
mensagem cifrada é o resultado da aplicação
de um o algoritmo criptográfico, que é
invariável,
associado
a
uma
chave
criptográfica especifica, que pode ser variável.
• Tanto o remetente quanto o destinatário
precisam conhecer o algoritmo e a chave.
15
• Uma cifra é um método de se obter um
criptograma tratando os caracteres do texto
claro como unidades da cifragem. Geralmente
os caracteres são tratados um a um e,
excepcionalmente, em grupos de dois ou três.
• Um código é um método de se obter um
criptograma tratando palavras ou conjuntos
de palavras do texto claro como unidades da
cifragem. Neste caso, o número de substitutos
pode chegar a alguns milhares e costumam
ser listados em dicionários, conhecidos como
nomenclaturas.
16
Classificação de cifras
• As cifras, de acordo com a sua funcionalidade,
podem ser classificadas em categorias:
– Cifras de substituição: o valor nomimal ou
convencional dos caracteres do texto original é
mudado, sem que sua posição dentro do texto
seja mudada.
– Cifras de transposição: apenas a posição dos
caracteres do texto original é mudada, sem
qualquer alteração no seu valor nomimal.
17
Substituição (vs) transposição
• Conhecendo o funcionamento de uma cifra de
um determinado grupo, este conhecimento
pode ser aplicado a outras do mesmo grupo.
• Como os métodos de encriptação são
radicalmente diferentes, então os princípios
envolvidos na criptoanálise das duas
categorias também são fundamentalmente
diferentes.
18
Taxonomia de Cifras
19
Taxonomia de Cifras:
ESTEGANOGRAFIA
Histogramas
RGB originais
A imagem à direita está
escondida
na
imagem
à
esquerda.
Para
recuperar
a
imagem
escondida, deve-se retirar os seis
bits mais significativos (mais à
esquerda) nos valores de cada
canal RGB da imagem original.
Histogramas
RGB modificados
20
As cifras de substituição
• Quando os caracteres do texto claro são tratados um a
um, sendo substituídos por apenas um símbolo diferente
(um a um), trata-se de uma substituição monogrâmica
(mono = um e grama = caracter).
• Neste caso, o comprimento do texto original e o
comprimento do texto cifrado são iguais.
• A substituição monogrâmica pode ser dividida em dois
grupos:
• substituição monogrâmica monoalfabética,
chamada de substituição simples.
• substituição
monogrâmica
polialfabética,
simplesmente de substituição polialfabética.
também
chamada
21
Exemplo Substituição simples: A
cifra de Julio César.
• Suetônio, (69 d.C.), Vida dos Césares:
– Júlio César usava na sua correspondência
particular um código de substituição no qual cada
letra da mensagem original era substituída pela
letra que a seguia em três posições no alfabeto: a
letra A era substituída por D, a B por E, e assim
sucessivamente.
• Substituição do código de César:
• ABCDEFGHIJKLMNOPQRSTUVWXYZ
• DEFGHIJKLMNOPQRSTUVWXYZABC
22
Exemplo Substituição simples: A
cifra de Julio César+.
• Texto claro:
– AVE CAESAR MORITURI TE SALUTANT
• Mensagem cifrada:
– DYH FDHVDU PRULWXUL WH VDOXWDQW
23
Exemplo Substituição
polialfabética: A cifra de Vigenère
• Blaise de Vigenère (1523 - 1596). Traité des chiffres où secrètes
manières d'escrire, 1586.
• Descreve uma cifra de substituição polialfabética com palavra-chave
e apresenta uma tabela de alfabetos cifrantes que ficou conhecida
como Carreiras de Vigenère.
• Tabela das carreiras de Vigenère.
– A linha superior da tabela é o alfabeto
– A coluna lateral esquerda mostra o deslocamento dos
caracteres:
• Na linha 0, entra o alfabeto com deslocamento 0;
• na linha 1 os caracteres são deslocados em uma posição (o
alfabeto começa com a letra B);
• na linha 2 os caracteres são deslocados em duas posições e
24
assim sucessivamente.
Tabela das carreiras de Vigenère.
A coluna lateral esquerda
mostra o deslocamento dos
caracteres:
Na linha 0, entra o alfabeto
com deslocamento 0;
na linha 1 os caracteres são
deslocados em uma posição
na linha 2 os caracteres são
deslocados
em
duas
posições
E assim sucessivamente ...
25
• Para cifrar a primeira letra do texto claro com
a primeira letra da chave, procura-se a letra do
texto claro no cabeçalho e a letra da chave na
coluna da esquerda.
• A letra encontrada na intersecção das duas
referências será a substituta da letra do texto
claro. Por exemplo, uma letra A do texto claro
com a chave C será substituída pela letra C.
Texto Claro
A C
Chave
C
R
Deslocamento
2
17
Cifra
C
C
I
F
R
A
D
E
V
I
G E
N
E
R
E
26
• Para cifrar a primeira letra do texto claro com
a primeira letra da chave, procura-se a letra do
texto claro no cabeçalho e a letra da chave na
coluna da esquerda.
• A letra encontrada na intersecção das duas
referências será a substituta da letra do texto
claro. Por exemplo, uma letra A do texto claro
com a chave C será substituída pela letra C.
ACABOU A CHAVE E O TEXTO CLARO CONTINUA ..
Texto Claro
A C
I
F
R
A
D
E
V
I
G E
Chave
C
R
I
P
T
O
G
R
A
F
I
A
Deslocamento
2
17
8
15
19
14
6
17
0
5
8
0
Cifra
C
T
Q U
K
O
J
V
V
N O E
N
E
R
E
27
• Para cifrar a primeira letra do texto claro com
a primeira letra da chave, procura-se a letra do
texto claro no cabeçalho e a letra da chave na
coluna da esquerda.
• A letra encontrada na intersecção das duas
referências será a substituta da letra do texto
claro. Por exemplo, uma letra A do texto claro
com a chave C será substituída pela letra C.
REPETIR A CHAVE PARA ACOMPANHAR O TEXTO CLARO ...
Texto Claro
A C
I
F
R
A
D
E
V
I
G E
N
E
R
E
Chave
C
R
I
P
T
O
G
R
A
F
I
A
C
R
I
P
Deslocamento
2
17
8
15
19
14
6
17
0
5
8
0
2
17
8
15
Cifra
C
T
Q U
K
O
J
V
V
N O E
P
V
Z
T
28
Criptografia em blocos, chave única
rounds
B1
B2


...
Bn
A
B
AB
0
0
0
0
1
1
1
0
1
1
1
0
Ci=(Bi, CHAVE), 1i  n.
No caso de Vigenère,  é a substituição definida pela tabela.
Mas poderia ser qualquer função matemática, por exemplo XOR.
Mas NÃO FAÇA ISSO: Todo mundo sabe decriptografar XOR.
29
CHAVE
CHAVE
=
=
C1
C2

...
CHAVE
=
...
Cn
Desvantagens
• A chave criptográfica é repetida em cada
round e, por isso:
– Pode-se coletar informação estatística sobre o
funcionamento da substituição
– Ou seja, pode-se identificar os casos nos quais a
chave e a texto claro fornecem a mesma saída.
• No caso de Vigenère, a combinação de texto
claro e o “A” da chave, NÃO PRODUZ
ALTERAÇÃO: V = (V, A), E = (E, A), etc.
30
• Para cifrar a primeira letra do texto claro com
a primeira letra da chave, procura-se a letra do
texto claro no cabeçalho e a letra da chave na
coluna da esquerda.
• A letra encontrada na intersecção das duas
referências será a substituta da letra do texto
claro. Por exemplo, uma letra A do texto claro
com a chave C será substituída pela letra C.
Texto Claro
A C
I
F
R
A
D
E
V
I
G E
N
E
R
E
Chave
C
R
I
P
T
O
G
R
A
F
I
A
C
R
I
P
Deslocamento
2
17
8
15
19
14
6
17
0
5
8
0
2
17
8
15
Cifra
C
T
Q U
K
O
J
V
V
N O E
P
V
Z
T
31
Cript. em blocos, múltiplas chaves
rounds
B1
B2


CHAVE1
CHAVE2
=
=
C1
C2
Bn
...

...
CHAVEn
=
...
Cn
Ci = (Bi, CHAVE), 1  i  n.
CHAVEi = (CHAVEi-1), 1 < i  n.
32
CRIPTOANÁLISE
• O objetivo é descobrir a chave, não apenas a
mensagem.
• Estratégias gerais:
– Ataque de criptoanálise.
– Ataque de força-bruta.
33
Ataque de criptoanálise
• ciphertext only
– sabendo algoritmo & criptograma, fazer analise
estatística para determinar texto claro.
• known plaintext
– Se conhece (ou suspeita) um criptograma associado
a um texto claro.
• chosen plaintext
– Escolhe texto claro e descobre criptograma.
• chosen ciphertext
– Escolhe criptograma e descobre texto claro.
• chosen text
– Escolhe texto claro ou cifrado para criptografar ou
34
decriptografar.
Busca por Força Bruta
• “Testar todas as chaves possíveis sempre funciona”
se há tempo, memória e capacidade computacional
suficientes ...
• A complexidade de tempo é proporcional ao
comprimento da chave
• É assumido que se conhece ou pode se reconhecer
texto claro.
µs : 10−6microssegundo = 10−6 segundo
Key Size (bits)
Number of Alternative
Keys
32
232 = 4.3  109
56
256 = 7.2  1016
128
2128 = 3.4  1038
2168 = 3.7  1050
Time required at 1
decryption/µs
231 µs
Time required at 106
decryptions/µs
= 35.8 minutes
2.15 milliseconds
= 1142 years
10.01 hours
2127 µs
= 5.4  1024 years
5.4  1018 years
2167 µs
= 5.9  1036 years
5.9  1030 years
2  1026 µs = 6.4  1012 years
6.4  106 years
255 µs
16 characters
168
21 characters
26 characters
(permutation)
26! = 4  1026
35
Criptoanalise da cifra de Julio Cesar
• Cada letra é substituída pela 3ra a seguir:
– A é substituída por D
– B é substituída por E
– Etc.
• Exemplo com texto claro em inglês:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
36
Cifra de Julio Cesar
• A transformação é:
a b c d e f g h i j k l m n o p q r s t u v w x y z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
• Associando um número a cada letra:
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
• Então a cifra de Julio Cesar é:
c = E(p) = (p + k) mod (26) (o criptograma de p é c)
p = D(c) = (c – k) mod (26) (c é decriptado como p)
37
Criptoanalise da cifra de Julio Cesar+
• Existem apenas 26 cifras possíveis:
– A é substituído por A, B,..., Z
• Pode-se tentar com cada cifra possível
• Busca por força bruta:
– Dada um texto cifrado, tentar com todas as cifras
possíveis.
– É preciso reconhecer quando se obteve texto claro
38
Cifra Monoalfabetica
• Ao invés de mudar o alfabeto, pode-se embaralhar as
letras arbitrariamente: ou seja, aplica-se uma
permutação no alfabeto.
• Cada letra do texto claro é substituída por uma letra
aleatória no texto cifrado.
• A chave, portanto tem comprimento 26:
Alfabeto: abcdefghijklmnopqrstuvwxyz
Cifra:
DKVQFIBJWPESCXHTMYAUOLRGZN
Texto claro : ifwewishtoreplaceletters
Texto cifrado: WIRFRWAJUHYFTSDVFSFUUFYA
39
Segurança da Cifra Monoalfabetica
• Número total de chaves:
24 ! = 6.20448402 × 1023
• Mas o sistemas é inseguro ...
• Devido a
naturais
características
das
linguagens
40
Criptoanalise e redundância
• Linguagens naturais são redundantes:
• th lrd s m shphrd shll nt wnt
• The LORD is my shepherd, I shall not want
• Gvrn rdz mpst pr ltrdmstics plcçs fnncrs
• Governo reduz imposto para eletrodomésticos e aplicações
financeiras
• Algumas letras são mais usadas que outras.
• Em Inglês a letra E é a letra mais usada
– Seguida por: T, R, N, I, O, A, S
• Letras pouco usadas: Z, J, K, Q, X
• Existem tabelas de freqüências de letras, digramas (duas letras
seguidas) e trigramas (três letras seguidas) para varias línguas.
41
Freqüências das letras no Inglês
42
Criptoanalise da Cifra
Monoalfabetica
• Procure uma tabela de freqüências DA LINGUA
DO TEXTO CLARO.
• Faça o histograma de freqüências das letras
que aparecem no texto cifrado.
• Decodifique o texto cifrado usando:
– Se a letra A do texto cifrado tem freqüência f(A).
– Procure na tabela de freqüências da língua do texto
claro a letra que tem essa freqüência.
• OBS: Precisa textos cifrados longos ...
43
Exemplo: criptograma1
•
•
•
•
•
•
•
n frnt f m cn s m fthr,
n frnt f m cn s m mthr,
m brthrs nd m sstrs,
th cll m,
nd sk m t tk m plc mng thm,
n th hlls f th vlhll,
whr th brvs lvs frvr
44
Exemplo: criptograma1+ u(0)
•
•
•
•
•
•
•
n frnt f m cn s m fthr,
n frnt f m cn s m mthr,
m brthrs nd m sstrs,
th cll m,
nd sk m t tk m plc mng thm,
n th hlls f th vlhll,
whr th brvs lvs frvr
45
Exemplo: criptograma1 + y(6)
•
•
•
•
•
•
•
n frnt f m cn s my fthr,
n frnt f m cn s my mthr,
my brthrs nd my sstrs,
thy cll m,
nd sk m t tk my plc mng thm,
n th hlls f th vlhll,
whr th brv lv frvr
46
Exemplo: criptograma1 + i(7)
•
•
•
•
•
•
•
In frnt f m I cn s m fthr,
in frnt f m I cn s m mthr,
m brthrs nd m sistrs,
th cll m,
nd sk m t tk m plc mng thm,
in th hlls f th vlhll,
whr th brv liv frvr
47
Exemplo: criptograma1 + o(11)
•
•
•
•
•
•
•
n front of m cn s m fthr,
n front of m cn s m mothr,
m brothrs nd m sstrs,
th cll m,
nd sk m to tk m plc mong thm,
on th hlls of th vlhll,
whr th brv lv forvr
48
Exemplo: criptograma1 + a(15)
•
•
•
•
•
•
•
n frnt f m can s m fathr,
n frnt f m can s m mthr,
m brthrs and m sstrs,
th call m,
and ask m t tak m plac amng thm,
n th halls f th valhalla,
whr th brav lv frvr
49
Exemplo: criptograma1 + e(24)
•
•
•
•
•
•
•
n frnt f me cn see m fther,
n frnt f me cn see m mther,
m brthers nd m ssters,
the cll me,
nd sk me t tke m plce mng them,
n the hlls f the vlhll,
where the brve lve frever
50
Exemplo: texto claro1
•
•
•
•
•
•
•
In front of me I can see my father,
In front of me I can see my mother,
my brothers and my sisters,
they call me,
and ask me to take my place among them,
in the halls of the Valhalla,
where the brave live forever
51
Exemplo: texto claro1 (arcaico)
• Lo, there do I see my father
• Lo, there do I see my mother and my sisters and my
brothers
• Lo, there do I see the line of my people back to the
beginning
• Lo, they do call to me
• They bid me take my place among them
• In the halls of Valhalla
• Where the brave may live forever
52
Freqüência de ocorrência de letras
no Português
Letra Freq.% Letra Freq.%
A
14.63
N
5.05
B
1.04
O
10.73
C
3.88
P
2.52
D
4.99
Q
1.20
E
12.57
R
6.53
F
1.02
S
7.81
G
1.30
T
4.34
H
1.28
U
4.63
I
6.18
V
1.67
J
0.40
W
0.01
K
0.02
X
0.21
L
2.78
Y
0.01
M
4.74
Z
0.47
Histograma por ordem
alfabética
Histograma por ordem
decrescente de Freqüência53
CORPUS
http://www.numaboa.com.br/criptografia/criptoanalise/310-frequencia-portugues
• Textos de domínio público dos autores:
– João do Rio: 49.958 palavras/232.882 letras.
– Machado de Assis: 26.326 palavras/115.580 letras.
– João Simões Lopes Neto:33.013 palavras/143.520 l.
– Rui Barbosa:4.781 palavras/23.121 letras.
– Lima Barreto: 41.633 palavras/200.581 letras.
– Saramago: 2.053/9.827 letras.
• Vogais acentuadas (á, ã, ô,...) transformados em
vogais normais e o C cedilha em C.
54
Exemplo: criptograma2
mnh trr tm plmrs
nd cnt sb
s vs q q grjm
n grjm cm l
55
Exemplo: criptograma2+u(0)
mnh trr tm plmrs
nd cnt sb
s vs q q grjm
n grjm cm l
56
Exemplo: criptograma2+i(4)
minh trr tm plmirs
nd cnt sbi
s vs q q grjim
n grjim cm l
57
Exemplo: criptograma2+o(6)
mnh trr tm plmrs
ond cnt o sb
s vs q q gorjm
n gorjm como l
58
Exemplo: criptograma2+e(8)
mnh terr tem plmers
nde cnt sb
s ves qe q grjem
n grjem cm l
59
Exemplo: criptograma2+a(15)
mnha trra tm palmras
nd canta saba
as avs q aq grjam
na grjam cm la
60
Exemplo: texto claro2
Minha terra tem palmeiras,
Onde canta o Sabiá
As aves, que aqui gorjeiam,
Não gorjeiam como lá
Letra Freq.%
A
14.63
E
12.57
I
6.18
O
10.73
U
4.63
Letra
A
E
O
I
U
Ocurr.
15
8
6
4
0
61
Dispositivos criptográficos
Scytale 700 a.c. Grécia
Chave: diâmetro do cilindro
Wadsworth 1817 EUA
Circulo interior completa 1 volta
para cada 33 voltas do exterior
Cifra: voltas p/cada letra cifrada.
Thomas Jefferson 1795 EUA
Chave: ordem dos discos
62
Máquina de Turing
63
Máquina de Turing
Turing
Church
Tese de Church-Turing: Algoritmos são
máquinas de Turing que terminam de
executar para toda entrada de dados.
64
Máquina de Turing
Turing
Church
Tese de Church-Turing: Algoritmos são
máquinas de Turing que terminam de
executar para toda entrada de dados.
Número de Gödel: Todas
as máquinas de Turing
podem ser codificadas
por um número bem
definido.
Gödel
Teorema de incompletude:
Nenhum sistema formal
que inclui a aritmética
pode ser completo
65
Turing x Enigma: Colossus
Turing
Enigma
Colossus MARK II 1943 - 1945
Government Code and Cypher School
(GCCS)
Bletchley Park, Buckinghamshire,
England.
Lorenz Machine
66
Turing x Enigma: Colossus
Turing
Enigma
Colossus MARK II 1943 - 1945
A MAIORIA DOS ATAQUES
ERAM DE CIPHER TEXT
Government Code and Cypher School
(GCCS)
Bletchley Park, Buckinghamshire,
England.
Lorenz Machine
67
Turing x Enigma: Colossus
Turing
Enigma
Colossus MARK II 1943 - 1945
MAS ALGUNS ATAQUES
FORAM DE PLAIN TEXT ...
Government Code and Cypher School
(GCCS)
Bletchley Park, Buckinghamshire,
England.
Lorenz Machine
68
The piggy user
69
http://www.mathcomp.leeds.ac.uk/turing2012/WScie12/
70
Sistemas criptográficos digitais
•
•
•
•
Criptografia simétrica.
Criptografia assimétrica.
Assinatura digital
Algoritmo Diffie-Hellman para intercambio de
chaves
71
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
1971
Feistel
72
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
Assinatura digital
1971
Feistel
73
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
DES e AES: padrões USA de criptografia
1971
Feistel
74
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
1971
Feistel
RSA e ElGamal: criptografia assimétrica.
RSA: primeiro sistema de chave publica; implementa idéias D-H.
A segurança é baseada na dificuldade de fatorar números.
ElGamal: Segurança baseada na dificuldade de calcular logaritmo
discreto.
75
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
1971
Feistel
ECC: Elliptic curve cryptography (Criptografia de Curva Elíptica).
Curva Eliptica: y2 = x3 + ax + b.
OBS: a, b e as componentes dos pontos (x, y) da curva devem
pertencer a um corpo de Galois.
Uso: dispositivos onde rapidez é o mais importante.
OBS: As operações do AES também estão definidas em corpos
de Galois.
76
Linha do tempo
LUCIFER
D-H
DES
RSA
ElGamal
ECC
PGP
AES
1971
IBM
1976
Diffie
Hellman
1977
IBM
1978
Rivest
Shamir
Adleman
1984
Taher
ElGamal
1985
Koblitz
Miller
1991
Phil
Zimmerman
1998
NIST
F.Network
1971
Feistel
PGP: É um protocolo para intercambio de mensagens
criptografados via email. Inclui a definição de formato de
mensagem, assinatura digital, o uso de um algoritmo assimétrico,
etc. As implementações incorporam gerenciador de chaves.
Zimmerman foi investigado durante vários anos pelo governo
USA: o PGP foi publicado na Internet e, na época, existiam
restrições à exportação de sistemas criptográficos que eram
considerados munição.
77
http://www.galois.ihp.fr/a-propos/
78
Criptografia simétrica
• A mesma chave é usada para criptografar e
decriptografar.
• Se C é o algoritmo para criptografar e D é o algoritmo
para decriptografar, então, desde o ponto de vista de
funções matemáticas, C e D podem ser consideradas,
funções inversas:
(DC) = Id
D(C (Texto, Chave)) = Texto.
• Em algumas implementações, de fato, C = D,
portanto, C2 = DC = Id. Ou seja basta aplicar o mesmo
algoritmo para decriptografar.
79
Criptografia assimétrica
• Cada usuário precisa ter
– Uma chave publica C, para criptografar.
– Uma chave privada D, para decriptografar.
• Todos os usuários publicam suas chaves
publicas: u1C, u2C, ..., unC, ... .
• A implementação do algoritmo “garante” que
só a chave privada unD, decriptografa as
mensagens criptografas com a chave publica
unC.
80
Desvantagens
• Vários usuários precisam proteger a mesma
chave privada.
• É necessário distribuir a chave entre esses
usuários.
• Se os usuários estão fisicamente longe o
problema de distribuição piora.
• Um usuário destinatário não tem garantia da
identidade do remetente da mensagem.
81
Assinatura digital
• OBJETIVO: Garantir identidade de remetente e
destinatário de uma mensagem:
– O Destinatário tem que ter segurança da
identidade do remetente.
– O Remetente tem que ter segurança que só o
Destinatário poderá abrir a mensagem
82
Assinatura digital+
• Solução
com
sistema
de
chave
publica/privada.
• Dados os usuários A(lice) e B(ob), com chaves
(AC , AD) e (BC , BD) respectivamente:
– Alice criptografa a mensagem M com sua chave
privada, E = AD(M): isso garante que o envelope E
foi preparado por Alice.
– Alice criptografa o envelope com a chave publica
de Bob, F = BC(E) = BC(AD(M)): isso garante que só
bob poderá ter acesso ao envelope.
83
Detalhes de implementação
• Gerador de chaves publica/privada
• Veiculo de publicação de chaves publicas
• Canal de envio de mensagens criptografadas.
84
Detalhes de implementação
• Gerador de chaves publica/privada
• Veiculo de publicação de chaves publicas
• Canal de envio de mensagens criptografadas.
Software: DES, AES, PGP, etc.
85
Detalhes de implementação
• Gerador de chaves publica/privada
• Veiculo de publicação de chaves publicas
• Canal de envio de mensagens criptografadas
Software: DES, AES, PGP, etc.
World Wide Web.
86
Detalhes de implementação
• Gerador de chaves publica/privada
• Veiculo de publicação de chaves publicas
• Canal de envio de mensagens criptografadas
Software: DES, AES, PGP, etc.
World Wide Web.
email
87
Sistema de Chave Publica-
Canal de comunicação
Bob tem certeza que foi Alice
que enviou a mensagem ... Mas
Alice não tem certeza que Bob é
o único que pode ler a
mensagem
88
Sistema de Chave Publica--
Canal de comunicação
Alice tem certeza que Bob é o
único que pode ler a mensagem
... Mas Bob não tem certeza
que foi Alice que enviou a
mensagem ...
89
Assinatura digital com chave pública
Alice tem certeza que Bob é o único que pode ler a mensagem.
Bob tem certeza que foi Alice que enviou a mensagem.
Bob tem certeza que Alice é a única que pode ler a mensagem.
Alice tem certeza que foi Bob que enviou a mensagem.
90
Assinatura digital++
• Para ter acesso à mensagem M, Bob:
– Decriptografa o malote recebido F com sua chave
privada: BD(F) = BD(BC(E)),
– Dessa forma, Bob tem acesso ao envelope
fechado por Alice: E = AD(M).
– Bob decriptografa o envelope com a chave publica
de Alice: M = AC(E) = AC(AD(M)).
91
D-H Key Exchange
• Para intercambio de chave SECRETA de
criptografia SIMETRICA através de canal
inseguro.
• Baseado na propriedade:
(ga mod p)b mod p = gab mod p == (gb mod p)a mod p = gba mod p
92
D-H Key Exchange
Alice
Hacker
Alice e Bob combinam p =23, g =5
p =23, g =5
Bob
Alice e Bob combinam p =23, g =5
Alice gera um número aleatório
secreto a= 6.
Bob gera um número aleatório secreto
b= 15.
Alice envia para Bob
•A = ga mod p
•A = 56 mod 23
•A = 15 625 mod 23
•A = 8
Bob envia para Alice
•B = gb mod p
•B = 515 mod 23
•B = 30 517 578 125 mod 23
•B = 19
A=8, B = 19
Alice recebe B = 19
Bob recebe A = 8
Alice calcula a chave secreta:
•Key = Ba mod p
•Key = 196 mod 23
•Key = 47 045 881 mod 23
•Key = 2
Bob calcula a chave secreta:
•Key = Ab mod p
•Key = 815 mod 23
•Key = 35184372088832 mod 23
•Key = 2
93
Criptoanálise de D-H
Alguém que conheça os inteiros combinados a=6 e b=15
pode calcular o secreto s:
s = 56*15 mod 23
s = 515*6 mod 23
s = 590 mod 23
s = 807793566946316088741610050849573099185363389551639556884765625 mod 23
s=2
94
DES
DES
• IP: Permutação Inicial
• 16 Feistel scheme rounds
• FP: Permutação Final
IP e FP são permutações
inversas de 64 bits:
IP  FP = FPIP = Id64
1.
2.
3.
4.
Feistel scheme:
Expansão
Key Mixing
Substitution
Permutation
Bi = Li Ri-1
Li = Ri-1
Ri = Li-1  F(Ri-1, Ki)
95
IP: Initial Permutation
DES
: XOR
F
FP: Final Permutation
Feistel scheme
96
EXPANSION
1
32
1 2 3 4 5 6 7 8 9 0 a b c d e f g h i j k l m n o p q r s t u v
32bits 
v 1 2 3 4 5 4 5
8 9 8 9
32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
c d c d
f g f g
j k j k
 48bits
nono
r s r s
97
v 1
Key Mixing
Key Mixing
A
B
AB
0
0
0
0
1
1
1
0
1
1
1
0
O resultado de EXPANSION é mesclado com a SubChave do round com XOR98
Substitution
8 S-Boxes
Substitution
Cada S-Box transforma 6 bits em 4 bits
99
S-Box S1
Os bits 0 e 5 endereçam a linha da S-Box
Os bits 1, 2, 3, 4 endereçam a coluna da S-Box
Middle 4 bits of input
S5
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00
1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111
01
0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000
10
0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000
11
1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101
Outer bits
S1(011011) = S101, 1101 = 0101
100
S-Box S5
Middle 4 bits of input
S5
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00
0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01
1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
10
0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
11
1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011
Outer bits
S5(011011) = S501, 1101 = 1001
101
Permutation
Permutation
O resultado de SUBSTITUTION é permutado com uma permutação P de 48 bits
102
PC1
Round
Shift
1
1
2
1
3
2
4
2
5
2
6
2
7
2
8
2
9
1
10
2
11
2
41 52 31 37 47 55
12
2
30 40 51 45 33 48
13
2
44 49 39 56 34 53
14
2
46 42 50 36 29 32
15
2
16
1103
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
PC2
Key Schedule
Dados específicos
• Cadê as outras S-Boxes?
• Quais são as permutações IP de 64bits e P de
48 bits?
• Consulte:
FIPS 46-3: Especificação oficial, 1999:
http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
Versão do padrão DES de 1993, em HTML:
http://www.itl.nist.gov/fipspubs/fip46-2.htm
104
Criptoanalise Diferencial
PlainT - 
PlainT
PlainT + 
DES
DES
DES
CipherT 
CipherT
CipherT 
Diferença
Diferença


Detalhes: Coppersmith. The Data Encryption
Standard (DES) and its strength against attacks.
IBM Journal of Research and Development,
1994, volume 38, number 3, pp.243-250.
105
RSA
•
•
•
•
•
Escolher dois números primos GRANDES p, q.
n = pq
Chave publica (codificação): (n, e).
Chave privada (decodificação): (n, d).
Segurança: Dificuldade em fatorar o número n
para descobrir p, q.
106
Geração das chaves RSA
• Escolha aleatoriamente dois primos p e q.
• Calcule:
– n = pq
– (n) = (p - 1)(q - 1).
• Escolha e tal que 1 < e < (n) e ( e, (n) ) = 1.
• Calcule d o inverso multiplicativo de e:
de  1 mod (n).
(n) : quantidade números coprimos e menores que n
107
Chaves RSA
• Chave pública:
(n, e)
• Chave privada:
(n, d)
108
Codec RSA
• Criptografar mensagem m, onde 0< m < n:
c = me mod n
• Decifrar criptograma usando a chave privada
do receptor:
m = cd mod n
109
Problemas de implementação
• Fatoração eficiente de um número n.
• Determinar se um número inteiro n é primo.
110
Aproximação
• Funções que geram “candidatos a números
primos”: pseudoprimos.
• Testes de primalidade rápidos.
111
Pseudoprimos de Fermat
• Números de Fermat: Fn =
n
2
2
+1
– F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.
– Fn , para 5  n  32, são compostos.
– F23288 e F23471 são compostos.
• Existem outros primos de Fermat?
112
Pseudoprimos de Mersenne
• Números de Mersenne: Mn = 2n - 1
– Primos de Mersenne: M2 = 3, M3 = 7, M5 = 31, M7
= 127, M13 = 8.191, M17 = 131.071, M19 = 524.287
– Números de Mersenne compostos: M0 = 0
(composto, par); M1 = 1 (singular, ímpar); M4 = 15,
M6 = 63, M8 = 255, M9 = 511, M10 = 1.023, M11 =
2.047, M12 = 4.095
• Great Internet Mersenne Prime Search
– http://mersenne.org/default.php
113
Testes de primalidade de Fermat
• Se m é primo, e a é tal que mdc(a,m)=1:
am-1  mod m.
• OBS: Se m não é primo, ainda é possível (embora
pouco provável) que o supradito se verifique.
• Definição: Se m é ímpar composto, e a tal que
mdc(a,m)=1 e am-1  mod m, diz-se que m é
pseudoprimo para a base a, (m é um número
não primo que passa o teste de Fermat.)
114
Teste de primalidade Miller-Rabin
• Se é possível encontrar a tal que
ad
 1 (mod n) e
r
2
a d
 1 (mod n), 0  r  s - 1.
• Então n não é primo
• OBS: d é um inteiro impar.
115
Teste de primalidade AKS
• Agrawal-Kayal-Saxena
• Baseado na identidade:
(x - a)n  (xn - a) mod n
Que é verdadeira somente quando n é primo
• OBS: Verificar diretamente essa identidade
leva tempo exponencial, mas existem
algoritmos de tempo polinomial para AKS.
116
PGP
• Pode incluir compressão e outros detalhes
mas nós focaremos:
– Privacidade via criptografia
– Autenticidade via assinatura digital.
• Requere algoritmo de Hash (MD5, SHA-1, etc.)
• Requere algoritmo assimétrico:
– Alice(Chave publica, Chave privada): (AC , AD)
– Bob(Chave publica, Chave privada): (BC , BD)
117
Criptografia PGP
1. Alice gera chave de sessão CS (n. aleatório)
2. Alice encripta a chave de sessão usando a chave
publica de Bob: BC(CS)
3. Alice encripta a mensagem usando a chave de
sessão: E = CS(M).
4. Alice envia para Bob: BC(CS).CS(M)
5. Bob decriptografa a chave de sessão usando sua
chave privada: CS = BD(BC(CS)).
6. Bob decriptografa a mensagem usando a chave
de sessão M = CS(CS(M))
118
Assinatura digital PGP
1. Alice gera código HASH para a msg. M: H(M)
2. Alice criptografa a o código HASH com sua
chave privada: AD(H(M)) (assinatura digital)
3. Alice envia para Bob: M.AD(H(M)).
4. Bob usa a chave publica de Alice p/ recuperar
código Hash da msg.: H(M) = AD(AC(H(M))).
5. Bob gera código Hash para a mensagem M.
6. Se (4) coincide com (5) significa que a
mensagem M não foi alterada.
119
Detalhes sobre PGP
• Consulte:
– http://www.openpgp.org/
• Request for Comments: 4880 OpenPGP
Message Format:
– http://www.ietf.org/rfc/rfc4880.txt
• OpenPGP SDK:
– http://openpgp.nominet.org.uk/cgi-bin/trac.cgi
120
Soluções Hardware-software
• Requisitos de hardware/software
• Exemplos de instruções criptográficas
• Simuladores
121
AES
• Algoritmo simétrico
• Atual padrão USA
122
Algoritmo AES
• Algoritmo CYPHER
– Transformações
• SubBytes, ShifRows, MixColumns, AddRoundKey.
• Key Expansion
• Algoritmo Inverse CYPHER
– Transformações
• InvSubBytes, InvShifRows, InvMixColumns,
InvAddRoundKey
123
AES Fluxo de Dados ENC/DEC
323587-Intel_AES-NI_White_Paper
124
Algoritmo CIPHER
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
AddRoundKey(state, w[0, Nb-1]) // See Sec. 5.1.4
for round = 1 step 1 to Nr–1
SubBytes(state)
// See Sec. 5.1.1
ShiftRows(state) // See Sec. 5.1.2
MixColumns(state) // See Sec. 5.1.3
AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
end for
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
out = state
end
125
CIPHER
http://www.conxx.net/rijndael_anim_conxx.html
Clique na figura para ver a animação
126
SubBytes
Clique na figura para ver a animação
127
ShiftRows
Clique na figura para ver a animação
128
MixColumns
Clique na figura para ver a animação
129
AddRoundKey
Clique na figura para ver a animação
130
Algoritmo INVERSE CIPHER
InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) // See Sec. 5.1.4
for round = Nr-1 step -1 downto 1
InvShiftRows(state) // See Sec. 5.3.1
InvSubBytes(state)
// See Sec. 5.3.2
AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
InvMixColumns(state) // See Sec. 5.3.3
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0, Nb-1])
out = state
end
131
Rounds 2 a 10
Clique na figura para ver a animação
132
Key Schedule++
Clique na figura para ver a animação
133
Key Schedule01
134
Key Schedule02
135
Key Schedule03
136
Key Schedule04
137
Key Schedule05
138
Key Schedule06
139
Key Schedule07
140
Key Schedule08
141
Key Schedule09
142
Key Schedule10
143
Key Schedule10b
144
Key Schedule11
145
Key Schedule12
146
Key Schedule13a
147
Key Schedule13b
148
Key Schedule14
149
Key Schedule15
150
Key Schedule16a
151
Key Schedule16b
152
Key Schedule17
153
Key Schedule18
154
Key Schedule19
155
Key Schedule19b
156
Key Schedule20
157
Key Schedule21
158
Key Schedule22
159
Key Schedule22b
160
Key Schedule23
161
Key Schedule23b
162
Key Schedule24
163
Key Schedule24b
164
Key Schedule25
165
Key Schedule26
166
Key Schedule27
167
Key Schedule28
168
Key Schedule28b
169
Key Schedule29
170
Key Schedule30
171
Key Schedule31
172
Key Schedule31b
173
Key Schedule32
174
Key Schedule33
175
Key Schedule34
176
Key Schedule34b
177
Key Schedule35
178
Key Schedule36
179
Key Schedule37
180
Key Schedule37b
181
Key Schedule38
182
Key Schedule39
183
Key Schedule40
184
Key Schedule41
185
Pronto para implementar?
• Definir EDD adequadas para cada algoritmo a
ser implementado.
• Ao inves de re-invetar a roda, consultar as
recomendações da especificação oficial.
186
Especificação AES
(extrato)
Federal Information
Processing Standards Publication 197
November 26, 2001
Announcing the
ADVANCED ENCRYPTION STANDARD (AES)
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
187
2.1 Termos e Acrônimos
AES: Advanced Encryption Standard
Inverse Cipher: transformação de texto
cifrado a texto claro usando a chave
Affine Transformation: y = Ax + v
Key Expansion: rotina para gerar
RoundKeys a partir da chave
Array:
Plaintext: texto claro
Bit:
Rijndael: Algoritmo do AES
Block: sequencia de bits para entrada,
saida, State e RoudKey. Array de bytes
Round Key: são derivadas da chave
usando KeyExpansion
Byte:
State: Resultado intermediário do Cipher
Cipher: transformação de texto claro a
texto cifrado usando a chave.
S-Box: Substituição não linear usada em
Key Expansion
Cipher Key: Chave secreta
Word: 32bits == 4bytes
Ciphertext: saida do Cipher/entrada para
Inverse Cipher
188
2.2 Parâmetros de Alg., Símbolos e Funções
AddRoundKey(): RoundKey  State
Rcon[]: Array constante para um round.
InvMixColumns(): Inverso de MixColumns
RotWord(): permutação ciclica de 4 bytes
InvShiftRows(): Inverso de ShiftRows
ShiftRows(): permutação ciclica das três
últimas linhas do State.
InvSubBytes(): Inverso de SubBytes
SubBytes(): Aplicação de S-Box no State
K: Chave criptografica
SubWord(): Aplicação de S-Box a palavra de
4bytes
MixColumns(): Mistura colunas
XOR: OU Exclusivo
Nb: número de colunas (32bits words)
que formam o State. Só pode ser Nb = 4.
: OU Exclusivo
Nk: número de colunas (32bits words) que
formam a chave K. Pode ser Nk = 4, 6, 8.
: Multiplicação de polinomios de grau < 4,
modulo x4 + 1.
Nr: número de rounds. Pode ser Nr = 10,
12, 14.
: Multiplicação em corpo finito (corpo de
Galois)
189
3.1 Entradas e Saídas
• A entrada e a saída do AES é formada por
sequencias de 128 bits.
• Essas sequencias são denominadas de blocos.
• A qtde de bits nos blocos é o comprimento.
• A Cipher Key do AES pode ser de 128, 192 ou
256 bits.
• A numeração dos bits inicia em zero.
• O index i de um bit pode ser de 0 ≤ i 128, 0 ≤
i  192 ou 0 ≤i 256.
190
Intel® Advanced Encryption
Standard (AES) Instructions Set
• Shay Gueron
• http://software.intel.com/file/24917
• Apresenta instruções AES da Intel
191
State, Bit, Byte, DoubleWord @ xmm
192
Exemplo
e598271ef11141b8ae52b4e0305dbfd4
193
Arquitetura Intel® AES
• Fluxo criptográfico / decriptografico:
– AESENC:
– AESENCLAST:
– AESDEC:
– AESDECLAST:
AES Encrypt Round
AES Encrypt Last Round
AES Decrypt Round
AES Decrypt Last Round
• Expansão de chave
– AESIMC:
AES Inverse Mix Columns
– AESKEYGENASSIST : AES Key Generation Assist
194
Instruções AESENC , AESENCLAST
AESENC
AESENC xmm1, xmm2/m128
Tmp := xmm1
Round Key := xmm2/m128
Tmp := ShiftRows (Tmp)
Tmp := SubBytes (Tmp)
Tmp := MixColumns (Tmp)
xmm1 := Tmp xor Round Key
AESENCLAST
AESENCLAST xmm1, xmm2/m128
Tmp := xmm1
Round Key := xmm2/m128
Tmp := Shift Rows (Tmp)
Tmp := SubBytes (Tmp)
xmm1 := Tmp xor Round Key
195
Instruções AESDEC , AESDECLAST
AESDEC
AESDEC xmm1, xmm2/m128
Tmp := xmm1
Round Key := xmm2/m128
Tmp := InvShift Rows (Tmp)
Tmp := InvSubBytes (Tmp)
Tmp := InvMixColumns (Tmp)
xmm1 := Tmp xor Round Key
AESDECLAST
AESDECLAST xmm1, xmm2/m128
State := xmm1
Round Key := xmm2/m128
Tmp := InvShift Rows (State)
Tmp := InvSubBytes (Tmp)
xmm1:= Tmp xor Round Key
196
Key Expansion
•
•
•
•
•
AES usa chaves de 128, 192 ou 256 bits.
Expandida em 10, 12, ou 14 “round keys”, resp.
Cada “round key” é de 128 bits.
A Expansão depende apenas da chave.
Key Expansion combina:
– SubWord(RotWord(tmp))
– SubWord(tmp)
// Chaves de 256bits
• E usa of the RCON values.
197
Key Expansion Parameters
(FIPS197)
• Nb = 4 (data blocks de 128 bits)
• Nk = numero de doublewords na chave:
– Nk = 4 para AES-128
– Nk = 6 para AES-192
– Nk = 8 para AES-256
word = 16bits
doubleword = 32bits
• Nr = number of rounds in the cipher
– Nr=10 para AES-128
– Nr=12 para AES-192
– Nr=14 para AES-256
198
Key Expansion algorithm (FIPS197)
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
Begin
word tmp
while (i = 0; i < Nk; i = i+1)
w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
end while
while (i = Nk; i < Nb * (Nr+1); i = i + 1)
tmp = w[i-1]
if (i mod Nk = 0)
tmp = SubWord(RotWord(tmp)) xor RCON[i/Nk]
Else if (Nk = 8)
tmp = SubWord(tmp)
end if
w[i] = w[i-Nk] xor tmp
end while
end
199
Instrução AESKEYGENASSIST
AESKEYGENASSIST xmm1, xmm2/m128, imm8
Tmp := xmm2/LOAD(m128)
X3[31-0] := Tmp[127-96];
X2[31-0] := Tmp[95-64];
X1[31-0] := Tmp[63-32];
X0[31-0] := Tmp[31-0];
RCON[7-0] := imm8;
RCON [31-8] := 0;
xmm1 := [
RotWord (SubWord (X3)) XOR RCON,
SubWord (X3),
RotWord (SubWord (X1)) XOR RCON,
SubWord (X1)]
200
Exemplo AESKEYGENASSIST
; xmm2 holds a 128-bit input
; imm8 holds the RCON value
; result delivered in xmm1
xmm2 = 3c4fcf098815f7aba6d2ae2816157e2b
imm8 = 1
AESKEYGENASSIST result (in xmm1) :
01eb848beb848a013424b5e524b5e434
201
AES-128 Key Expansion
Key=0x0f0e0d0c0b0a09080706050403020100
; Saida Key_Schedule[].
movdqu xmm1, XMMWORD PTR Key
movdqu XMMWORD PTR Key_Schedule, xmm1
mov rcx, OFFSET Key_Schedule+16
aeskeygenassist xmm2, xmm1, 0x1
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x2
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x4
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x8
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x10
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x20
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x40
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x80
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x1b
call key_expansion_128
aeskeygenassist xmm2, xmm1, 0x36
call key_expansion_128
jmp END;
key_expansion_128:
pshufd xmm2, xmm2, 0xff
vpslldq xmm3, xmm1, 0x4
pxor xmm1, xmm3
vpslldq xmm3, xmm1, 0x4
pxor xmm1, xmm3
vpslldq xmm3, xmm1, 0x4
pxor xmm1, xmm3
pxor xmm1, xmm2
movdqu XMMWORD PTR [rcx], xmm1
add rcx, 0x10
Ret
END:
202
Instrução AESIMC
AESIMC
• AESIMC xmm1, xmm2/m128
• RoundKey := xmm2/m128;
• xmm1 := InvMixColumns (RoundKey)
Exemplo AESIMC
; xmm2 hold one 128-bit inputs (xmm2 = Round key)
; result delivered in xmm1
xmm2 = 48692853686179295b477565726f6e5d
AESIMC result (in xmm1): 27a6f6644b109c82b18330a81c3b3e5
203
Exemplo em C com 2 rounds
• Figure 32. Isolating the AES Transformations
• pags.33-35
• Pre-requisitos:
– Compilador C da intel instalado
– Emulador sde da intel instalado
• Estrutura do exemplo:
– Função auxiliar para impressão
– Função main() faz e desfaz dois rounds
204
Downloads
• Intel® Software
Download:
Development
Emulator
– http://software.intel.com/en-us/articles/prerelease-license-agreement-for-intel-softwaredevelopment-emulator-accept-end-user-licenseagreement-and-download/
• Intel® C++ Studio XE 2011 for Linux (
Compilador c Intel):
– http://software.intel.com/en-us/articles/intelsoftware-evaluation-center/
205
Executa Round 0 e Round 1
• Func. aux p/ impressão
• main()
Setup
Imprime variáveis
Executa round 0
Imprime resultado round 0
Executa round 1
Imprime resultado round 1
206
Inverte Round 1 e Round 0
• Func. aux p/ impressão
• main()
Setup
...
...
Inverte round 1
Imprime resultado Iround 1
Inverte round 0
Imprime resultado Iround 0
207
Zoom : Round 0 e Round 1
Round 0
Round 1
208
Zoom: Inverte Round 1 e Round 0
Inverte
Round 1
Inverte
Round 0
209
Compilar e executar o exemplo:
Isolating the AES Transformations
• Colocar o caminho dos compiladores intel no
variável de ambiente:
source /opt/intel/bin/compilervars.sh ia32
• // compilar com compilador intel:
icc Fig32.c -o maintest
• // Executar com simulador:
./sde -- ./maintest
210
Saida da exeução do maintest
Demonstrating the exposed transformations:
DATA:
[0x00112233445566778899aabbccddeeff]
Round Key 0:
[0x000102030405060708090a0b0c0d0e0f]
After Round 0:
[0x00102030405060708090a0b0c0d0e0f0]
Round Key 1:
[0xd6aa74fdd2af72fadaa678f1d6ab76fe]
After ShiftRows:
[0x0050a0f04090e03080d02070c01060b0]
After SubBytes:
[0x6353e08c0960e104cd70b751bacad0e7]
After MixColumns:
[0x5f72641557f5bc92f7be3b291db9f91a]
After AddRoundKey:
[0x89d810e8855ace682d1843d8cb128fe4]
AES Round using exposed transformations:[0x89d810e8855ace682d1843d8cb128fe4]
AES round using AESENC instruction:
[0x89d810e8855ace682d1843d8cb128fe4]
Going backwards using exposed inverse transformations:
After InvAddRoundKey:
[0x5f72641557f5bc92f7be3b291db9f91a]
After InvMixColumns:
[0x6353e08c0960e104cd70b751bacad0e7]
After InvSubBytes:
[0x0050a0f04090e03080d02070c01060b0]
After InvShiftRows:
[0x00102030405060708090a0b0c0d0e0f0]
Final:
[0x00112233445566778899aabbccddeeff]
Returned to initial state.
211
Biblioteca AES em assembler
Pags. 41-72
• Salvar
Fig39, Fig40, Fig41 em key_expansion.s
Fig42 em aes.c
Fig43, Fig44 em ecb.s,
Fig45, Fig46 em cbc.s,
Fig47 em ctr.s
• Compilar *.s usando (gcc version 4.4.2):
gcc -maes -msse4 *.s
212
Biblioteca AES em assembler
Pags. 41-72
• Salvar as funções de teste:
– Fig48 em ecb_main.c
– Fig49 em cbc_main.c
– Fig50 em ctr_main.c
• Linkar os arquivos com
executável.
• Exemplo deExecução:
gcc, para gerar o
icc ecb_main.c ecb.o key_expansion.o aes.c -DAES128 -o ecb_exe
icc ecb_main.c ecb.o key_expansion.o aes.c -DAES256 -o ecb_exe
213
Intel® Carry-Less Multiplication Instruction
and its Usage for Computing the GCM Mode
• Shay Gueron; Michael E. Kounavis.
• http://software.intel.com/file/24918
• Apresenta operação de multiplicação sem
transporte ("e vai 1“) em Corpos de Galois.
214
Pag.27: How to Use the Code Examples
• Há vários problemas:
– gcc NÃO COMPILA: Problema de cast.
– Tipo uint8 não está presente no Fedora14.
– Função com nome errado, etc.
• Diagnósticos:
– gcc: pode ser versão, biblioteca, kernel, etc.
– uint8 não é obrigatoria, mas “recomendada”(?).
– Quem já não errou ao fatorar codigo fonte?
215
Solução para um dos exemplos
• Use compilador Intel ao invés de gcc
• Defina uint8 como uint8_t de <stdint.h>
• Corrija o código fonte ... Fig14 trocar
"AES_128_Key_Expansion" por
"AES_128_Key_Expansion_unrolled”
• Apenas foi compilado o primeiro exemplo na
pagina 27.
216
Exemplo corrigido
• Copiar
– cp Fig05
– cp Fig08
– cp Fig09
– cp Fig10
– cp Fig12
– cp Fig13
– cp Fig14
gfmul.c
reduce4.c
gcm.c
AES_GCM_decrypt.c
key_schedule.c
gcm_main.c
Fig14-Main-Function-for-Testing.c
217
Compilar e executar
• Colocar o caminho dos compiladores Intel no
variável de ambiente:
source /opt/intel/bin/compilervars.sh ia32
• Compilar:
icc key_schedule.c main.c gfmul.c reduce4.c AES_GCM_decrypt.c gcm_main.c -o AES128_GCM –DTEST6
• Executar:
./sde -- ./AES128_GCM6
218
Saída
CPU check passed. AES instructions are supported.
The Key:
[0xfeffe9928665731c6d6a8f9467308308]
The
The
The
The
[0x9313225df88406e555909c5aff5269aa]
[0x6a7a9538534f7da1e4c303d2a318a728]
[0xc3c0c95156809539fcf0e2429a6b5254]
[0x16aedbf5a0de6a57a637b39b]
IV:
IV:
IV:
IV:
The header buffer:
The header buffer:
[0xfeedfacedeadbeeffeedfacedeadbeef]
[0xabaddad2]
The
The
The
The
PLAINTEXT:
PLAINTEXT:
PLAINTEXT:
PLAINTEXT:
[0xd9313225f88406e5a55909c5aff5269a]
[0x86a7a9531534f7da2e4c303d8a318a72]
[0x1c3c0c95956809532fcf0e2449a6b525]
[0xb16aedf5aa0de657ba637b39]
The
The
The
The
CIPHERTEXT:
CIPHERTEXT:
CIPHERTEXT:
CIPHERTEXT:
[0x8ce24998625615b603a033aca13fb894]
[0xbe9112a5c3a211a8ba262a3cca7e2ca7]
[0x01e4a9a4fba43c90ccdcb281d48c7c6f]
[0xd62875d2aca417034c34aee5]
The tag:
[0x619cc5aefffe0bfa462af43c1699d050]
The tag is equal to the expected tag.
The cipher text is equal to the expected cipher text.
Decryption succeeded.
The decrypted text is equal to the original plaintext.
219
Otras Referencias bibliográficas
• Federal Information. Processing Standards Publication
197. November 26, 2001. Specification for the
ADVANCED ENCRYPTION STANDARD (AES).
• DES: FIPS 46-3: Especificação oficial, 1999:
http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
Versão do padrão DES de 1993, em HTML:
http://www.itl.nist.gov/fipspubs/fip46-2.htm
• Dorothy Elizabeth Robling Denning. Cryptography and
Data Security. 400 pages. Addison-Wesley Publishing
Company; 1st edition (June 1982).
220
Referencias bibliográficas
• Routo Terada. Segurança de dados - criptografia em
redes de computador, Segunda Edição (livro p/ Ed. E.
Blücher, 2008).
• Viktoria Tkotz. Criptografia - Segredos Embalados para
Viagem. Novatec Editora, 2005, ISBN 85-7522-071-3.
• Severino Collier Coutinho. Números Inteiros e
Criptografia RSA. 213 páginas. Publicação: IMPA, 2007.
ISBN: 978-85-244-0124-4. Segunda Edição.
• Paulo Ribenboim. Números Primos: Mistérios e Recordes.
280 páginas. Publicação: IMPA, 2001. ISBN: 978-85-2440168-8.
221