CRIPTOGRAFIA - Stoastoa.usp.br/cesarabp/files/3246/18237/SINFORM-CRIPTO.pdf · •A Criptografia é a ciência de escrever mensagens que ninguém deveria poder ler, exceto o remetente

CRIPTOGRAFIA

UESC SINFORM 2011

César Bravo

[email protected]

mailto:[email protected]

2

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-244-0168-8.

3

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.

4

Motivação

5

Motivação

www.oramag.com

http://www.oramag.com/

6

Motivação Informe publicitário da Intel entre as páginas 24 e 25

7

Motivação São duas páginas que resumem o white paper de 13 páginas do L. Xu

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) is a strong encryption algorithm adopted in 2001 by the U.S. government.

• 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.

Recommendations for Using inter AES-NI: • Secure Web transactions: (improve SSL

performance, accelerating e-commerce sites).

• 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

http://www.intel.com/Assets/en_US/PDF/whitepaper/Intel_AES-NI_White_Paper.pdf



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

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.

11

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-advanced-encryption-standard-aes-instructions-set/

http://software.intel.com/file/24917

• Shay Gueron; Michael E. Kounavis. White paper: Intel® Carry-

Less 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/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode/


http://software.intel.com/en-us/articles/intel-advanced-encryption-standard-aes-instructions-set/





























http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode/









































12

Roteiro

• Definições básicas

• Algoritmo AES.

• Soluções Hardware-software

13

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.

14

• 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.

15

• 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.

16

• 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.

17

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.

18

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.

19

Taxonomia de Cifras

20

Taxonomia de Cifras: ESTEGANOGRAFIA

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 originais

Histogramas

RGB modificados

21

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, também chamada de substituição simples.

• substituição monogrâmica polialfabética, chamada simplesmente de substituição polialfabética.

22

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: • 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

23

Exemplo Substituição simples: A cifra de Julio César+.

• Texto claro: – AVE CAESAR MORITURI TE SALUTANT

• Mensagem cifrada: – DYH FDHVDU PRULWXUL WH VDOXWDQW

24

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 assim sucessivamente.

25

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 ...

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.

Texto Claro A C I F R A D E V I G E N E R E

Chave C R

Deslocamento 2 17

Cifra C C

27




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

ACABOU A CHAVE E O TEXTO CLARO CONTINUA ..

28




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

REPETIR A CHAVE PARA ACOMPANHAR O TEXTO CLARO ...

29

Criptografia em blocos, chave única

B1

CHAVE

C1

=

B2

CHAVE

C2

=

Bn

CHAVE

Cn

=

...

...

...

Ci=(Bi, CHAVE), 1i 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.

rounds

A B A B

0 0 0

0 1 1

1 0 1

1 1 0

30

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.

31




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

32

Cript. em blocos, múltiplas chaves

B1

CHAVE1

C1

=

B2

CHAVE2

C2

=

Bn

CHAVEn

Cn

=

...

...

...

Ci = (Bi, CHAVE), 1 i n.

CHAVEi = (CHAVEi-1), 1 < i n.

rounds

33

CRIPTOANÁLISE

• O objetivo é descobrir a chave, não apenas a mensagem.

• Estratégias gerais:

– Ataque de criptoanálise.

– Ataque de força-bruta.

34

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 decriptografar.

35

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.

Key Size (bits) Number of Alternative

Keys

Time required at 1

decryption/µs

Time required at 106

decryptions/µs

32 232 = 4.3 109 231 µs = 35.8 minutes 2.15 milliseconds

56 256 = 7.2 1016 255 µs = 1142 years 10.01 hours

128 2128 = 3.4 1038 2127 µs = 5.4 1024 years 5.4 1018 years

168 2168 = 3.7 1050 2167 µs = 5.9 1036 years 5.9 1030 years

26 characters

(permutation)

26! = 4 1026 2 1026 µs = 6.4 1012 years 6.4 106 years

21 characters

16 characters

µs : 10−6microssegundo = 10−6 segundo

36

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

37

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)

38

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

39

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

40

Segurança da Cifra Monoalfabetica

• Número total de chaves:

24 ! = 6.20448402 × 1023

• Mas o sistemas é inseguro ...

• Devido a características das linguagens naturais

41

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.

42

Freqüências das letras no Inglês

43

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 ...

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,



• 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,


• 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,


• 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

53

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

decrescente de Freqüência

Histograma por ordem

alfabética

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

http://www.numaboa.com.br/criptografia/criptoanalise/310-frequencia-portugues





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á

61

Letra Freq.% A 14.63 E 12.57 I 6.18 O 10.73 U 4.63

Letra Ocurr. A 15 E 8 O 6 I 4 U 0

62

Dispositivos criptográficos

Scytale 700 a.c. Grécia

Chave: diâmetro do cilindro

Thomas Jefferson 1795 EUA

Chave: ordem dos discos

Wadsworth 1817 EUA

Circulo interior completa 1 volta

para cada 33 voltas do exterior

Cifra: voltas p/cada letra cifrada.

63

Máquina de Turing

64

Máquina de Turing

Tese de Church-Turing: Algoritmos são

máquinas de Turing que terminam de

executar para toda entrada de dados.

Turing Church

65

Máquina de Turing

Tese de Church-Turing: Algoritmos são

máquinas de Turing que terminam de

executar para toda entrada de dados.

Turing Church

Gödel Teorema de incompletude:

Nenhum sistema formal

que inclui a aritmética

pode ser completo

Número de Gödel: Todas

as máquinas de Turing

podem ser codificadas

por um número bem

definido.

Turing x Enigma: Colossus

66

Turing

Colossus MARK II 1943 - 1945

Lorenz Machine

Government Code and Cypher School

(GCCS)

Bletchley Park, Buckinghamshire,

England.

Enigma


67

Turing


Lorenz Machine


(GCCS)


England.

Enigma

A MAIORIA DOS ATAQUES

ERAM DE CIPHER TEXT


68

Turing


Lorenz Machine


(GCCS)


England.

Enigma

MAS ALGUNS ATAQUES

FORAM DE PLAIN TEXT ...

The piggy user

69

http://www.mathcomp.leeds.ac.uk/turing2012/WScie12/

70

http://www.mathcomp.leeds.ac.uk/turing2012/WScie12/

71

Sistemas criptográficos digitais

• Criptografia simétrica.

• Criptografia assimétrica.

• Assinatura digital

• Algoritmo Diffie-Hellman para intercambio de chaves

72

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

F.Network

1971

Feistel

73

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

F.Network

1971

Feistel

Assinatura digital

74

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

F.Network

1971

Feistel

DES e AES: padrões USA de criptografia

75

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

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.

76

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

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.

77

Linha do tempo

DES

1977

IBM

AES

1998

NIST

LUCIFER

1971

IBM

RSA

1978

Rivest

Shamir

Adleman

PGP

1991

Phil

Zimmerman

ElGamal

1984

Taher

ElGamal

ECC

1985

Koblitz

Miller

D-H

1976

Diffie

Hellman

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.

http://www.galois.ihp.fr/a-propos/

78




79

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:

(DC) = 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.

80

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.

81

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.

82

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

83

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.

84

Detalhes de implementação

• Gerador de chaves publica/privada

• Veiculo de publicação de chaves publicas

• Canal de envio de mensagens criptografadas.

85




• Canal de envio de mensagens criptografadas.

Software: DES, AES, PGP, etc.

86




• Canal de envio de mensagens criptografadas


World Wide Web.

87




• Canal de envio de mensagens criptografadas


World Wide Web.

email

88

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

89

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 ...

90

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.

91

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)).

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

93

D-H Key Exchange Alice Hacker Bob

Alice e Bob combinam p =23, g =5 p =23, g =5 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

Criptoanálise de D-H

94

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

95

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 = FPIP = Id64

Feistel scheme:

1. Expansão

2. Key Mixing

3. Substitution

4. Permutation

Bi = Li Ri-1

Li = Ri-1

Ri = Li-1 F(Ri-1, Ki)

96

DES

F

IP: Initial Permutation

FP: Final Permutation Feistel scheme

: XOR

97

EXPANSION

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

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

v 1 2 3 4 5 4 5 8 9 8 9 c d c d f g f g j k j k n o n o r s r s v 1

32bits 48bits

98

Key Mixing

Key Mixing

O resultado de EXPANSION é mesclado com a SubChave do round com XOR

A B A B

0 0 0

0 1 1

1 0 1

1 1 0

99

Substitution

Substitution

8 S-Boxes

Cada S-Box transforma 6 bits em 4 bits

100

S-Box S1

S5

Middle 4 bits of input

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Outer bits

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

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

S1(011011) = S101, 1101 = 0101

101

S-Box S5

S5

Middle 4 bits of input

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Outer bits

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

S5(011011) = S501, 1101 = 1001

102

Permutation

Permutation

O resultado de SUBSTITUTION é permutado com uma permutação P de 48 bits

103

Key Schedule 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

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Round Shift

1 1

2 1

3 2

4 2

5 2

6 2

7 2

8 2

9 1

10 2

11 2

12 2

13 2

14 2

15 2

16 1 PC2

PC1

104

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









Criptoanalise Diferencial

105

DES

PlainT

CipherT

DES

PlainT +

CipherT

DES

PlainT -

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.

106

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.

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).

107 (n) : quantidade números coprimos e menores que n

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

110

Problemas de implementação

• Fatoração eficiente de um número n.

• Determinar se um número inteiro n é primo.

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 = 22n + 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

http://mersenne.org/default.php

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 a2rd 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

http://www.openpgp.org/

http://www.ietf.org/rfc/rfc4880.txt

http://openpgp.nominet.org.uk/cgi-bin/trac.cgi



121

Soluções Hardware-software

• Requisitos de hardware/software

• Exemplos de instruções criptográficas

• Simuladores

122

AES

• Algoritmo simétrico

• Atual padrão USA

123

Algoritmo AES

• Algoritmo CYPHER

– Transformações

• SubBytes, ShifRows, MixColumns, AddRoundKey.

• Key Expansion

• Algoritmo Inverse CYPHER

– Transformações

• InvSubBytes, InvShifRows, InvMixColumns, InvAddRoundKey

124

AES Fluxo de Dados ENC/DEC 323587-Intel_AES-NI_White_Paper

125

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

CIPHER http://www.conxx.net/rijndael_anim_conxx.html

126 Clique na figura para ver a animação

http://www.conxx.net/rijndael_anim_conxx.html

SubBytes


ShiftRows


MixColumns


AddRoundKey


131

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

Rounds 2 a 10


Key Schedule++


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

186

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.

187

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




188

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

189

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)

190

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.

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: AES Encrypt Round

– AESENCLAST: AES Encrypt Last Round

– AESDEC: AES Decrypt Round

– AESDECLAST: 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


Tmp := Shift Rows (Tmp)

Tmp := SubBytes (Tmp)


195

Instruções AESDEC , AESDECLAST

AESDEC

AESDEC xmm1, xmm2/m128

Tmp := xmm1


Tmp := InvShift Rows (Tmp)

Tmp := InvSubBytes (Tmp)

Tmp := InvMixColumns (Tmp)


AESDECLAST

AESDECLAST xmm1, xmm2/m128

State := xmm1


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



• Nr = number of rounds in the cipher

– Nr=10 para AES-128

– Nr=12 para AES-192

– Nr=14 para AES-256 198

word = 16bits

doubleword = 32bits

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)

203

Exemplo AESIMC

; xmm2 hold one 128-bit inputs (xmm2 = Round key)

; result delivered in xmm1

xmm2 = 48692853686179295b477565726f6e5d

AESIMC result (in xmm1): 27a6f6644b109c82b18330a81c3b3e5

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 Development Emulator Download:

– http://software.intel.com/en-us/articles/pre-release-license-agreement-for-intel-software-development-emulator-accept-end-user-license-agreement-and-download/

• Intel® C++ Studio XE 2011 for Linux ( Compilador c Intel):

– http://software.intel.com/en-us/articles/intel-software-evaluation-center/

205

http://software.intel.com/en-us/articles/pre-release-license-agreement-for-intel-software-development-emulator-accept-end-user-license-agreement-and-download/


































http://software.intel.com/en-us/articles/intel-software-evaluation-center/









Executa Round 0 e Round 1

206

• Func. aux p/ impressão

• main()

Setup

Imprime variáveis

Executa round 0

Imprime resultado round 0

Executa round 1

Imprime resultado round 1

Inverte Round 1 e Round 0

207

• Func. aux p/ impressão

• main()

Setup

...

...

Inverte round 1

Imprime resultado Iround 1

Inverte round 0

Imprime resultado Iround 0

Zoom : Round 0 e Round 1

208

Round 0

Round 1

Zoom: Inverte Round 1 e Round 0

209

Inverte

Round 0

Inverte

Round 1

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 gcc, para gerar o executável.

• Exemplo deExecuçã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 gfmul.c

– cp Fig08 reduce4.c

– cp Fig09 gcm.c

– cp Fig10 AES_GCM_decrypt.c

– cp Fig12 key_schedule.c

– cp Fig13 gcm_main.c

– cp Fig14 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 IV: [0x9313225df88406e555909c5aff5269aa]

The IV: [0x6a7a9538534f7da1e4c303d2a318a728]

The IV: [0xc3c0c95156809539fcf0e2429a6b5254]

The IV: [0x16aedbf5a0de6a57a637b39b]

The header buffer: [0xfeedfacedeadbeeffeedfacedeadbeef]

The header buffer: [0xabaddad2]

The PLAINTEXT: [0xd9313225f88406e5a55909c5aff5269a]

The PLAINTEXT: [0x86a7a9531534f7da2e4c303d8a318a72]

The PLAINTEXT: [0x1c3c0c95956809532fcf0e2449a6b525]

The PLAINTEXT: [0xb16aedf5aa0de657ba637b39]

The CIPHERTEXT: [0x8ce24998625615b603a033aca13fb894]

The CIPHERTEXT: [0xbe9112a5c3a211a8ba262a3cca7e2ca7]

The CIPHERTEXT: [0x01e4a9a4fba43c90ccdcb281d48c7c6f]

The CIPHERTEXT: [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

220

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:


• Dorothy Elizabeth Robling Denning. Cryptography and Data Security. 400 pages. Addison-Wesley Publishing Company; 1st edition (June 1982).









221

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-244-0168-8.

Documents

CRIPTOGRAFIA - Stoastoa.usp.br/cesarabp/files/3246/18237/SINFORM-CRIPTO.pdf · •A Criptografia é a ciência de escrever mensagens que ninguém deveria poder ler, exceto o remetente