Exemplos de Algoritmos Criptográficos

Transcrição

Exemplos de Algoritmos Criptográficos
Tópicos em Computação: Segurança e Criptografia
Carlos André Batista de Carvalho
[email protected]
Conteúdo
Cifras Monoalfabéticas
Cifras Polialfabéticas
Padding (Enchimento)
Modos de Operação
Estrutura de Feistel
Cifra RSA
Carlos André B. de Carvalho
Tópicos em Computação
2
1
Cifras Monoalfabéticas
Cifragem
Substituição do símbolo indicado no alfabeto original pelo
símbolo correspondente no alfabeto cifrado
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
R
Carlos André B. de Carvalho
Tópicos em Computação
3
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RT
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTX
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL
Carlos André B. de Carvalho
Tópicos em Computação
4
2
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T W
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WK
Carlos André B. de Carvalho
Tópicos em Computação
5
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQ
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQL
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLO
Carlos André B. de Carvalho
Tópicos em Computação
6
3
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOS
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOST
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOSTO
Carlos André B. de Carvalho
Tópicos em Computação
7
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOSTOK
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOSTOKG
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Plaintext
deus e brasileiro
Ciphertext
RTXL T WKQLOSTOKG
Carlos André B. de Carvalho
Tópicos em Computação
8
4
Cifras Monoalfabéticas
Decifragem
Substituição do símbolo indicado no alfabeto CIFRADO pelo
símbolo correspondente no alfabeto ORIGINAL
Operação Inversa
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
m
Carlos André B. de Carvalho
Tópicos em Computação
9
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
ma
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
mar
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
mari
Carlos André B. de Carvalho
Tópicos em Computação
10
5
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria f
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria fo
Carlos André B. de Carvalho
Tópicos em Computação
11
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a p
Carlos André B. de Carvalho
Tópicos em Computação
12
6
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a pr
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a pra
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a prai
Carlos André B. de Carvalho
Tópicos em Computação
13
Cifras Monoalfabéticas
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a praia
Alfabeto original
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
Alfabeto cifrado
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Ciphertext
DQKOQ YGO Q HKQOQ
Plaintext
maria foi a praia
Carlos André B. de Carvalho
Tópicos em Computação
14
7
Cifras
Polialfabéticas
Cifra de Vigenère
Carlos André B. de Carvalho
Tópicos em Computação
15
Cifras Polialfabéticas
Cifragem
Substituição monoalfabética conforme o alfabeto cifrado
indicado
Chave
CIFRA
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
F
Carlos André B. de Carvalho
Tópicos em Computação
16
8
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FM
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZ
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ
Carlos André B. de Carvalho
Tópicos em Computação
17
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E D
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZ
Carlos André B. de Carvalho
Tópicos em Computação
18
9
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZF
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJ
Alfabeto original
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
Alfabeto cifrado
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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJI
Carlos André B. de Carvalho
Tópicos em Computação
19
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJIN
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJINM
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJINMN
Carlos André B. de Carvalho
Tópicos em Computação
20
10
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJINMNI
Alfabeto original
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
Alfabeto cifrado
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
Chave
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJINMNIO
Chave
CIFRA
CIFR A CIFRACIFRA
Plaintext
deus e brasileiro
Ciphertext
FMZJ E DZFJINMNIO
Carlos André B. de Carvalho
Tópicos em Computação
21
Cifras Polialfabéticas
Decifragem
Operação Inversa
Chave
CIFRA
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
m
Carlos André B. de Carvalho
Tópicos em Computação
22
11
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
ma
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
mar
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
mari
Carlos André B. de Carvalho
Tópicos em Computação
23
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
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
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria f
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria fo
Carlos André B. de Carvalho
Tópicos em Computação
24
12
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a
Alfabeto original
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
Alfabeto cifrado
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
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a p
Carlos André B. de Carvalho
Tópicos em Computação
25
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
C 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
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a pr
Alfabeto original
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
Alfabeto cifrado
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a pra
Alfabeto original
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
Alfabeto cifrado
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a prai
Carlos André B. de Carvalho
Tópicos em Computação
26
13
Cifras Polialfabéticas
Alfabeto original
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
Alfabeto cifrado
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
Chave
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a praia
Chave
CIFRA
CIFRA CIF R ACIFR
Ciphertext
OIWZA HWN R PTINR
Plaintext
maria foi a praia
Carlos André B. de Carvalho
27
Tópicos em Computação
Padding (Enchimento)
Mecanismo usado para que uma mensagem possua um
número inteiro de blocos
Algoritmo de Enchimento (RFC 1321)
Inserir bit 1 no final
Inserir zero ou mais 0s até completar um bloco
Exemplo: blocos de tamanho 4
010101011
1001011010
1101001
10110110
Adicionar 1
Original
0101010111
10010110101
11010011
101101101
Adicionar 0s
(Padding)
010101011100
100101101010
11010011
101101101000
OBS.: Caso a mensagem já possua um número inteiro de blocos
Bloco extra, devido a necessidade de realizar o processo inverso
Carlos André B. de Carvalho
Tópicos em Computação
28
14
Padding (Enchimento)
Algoritmo de Enchimento (RFC 1321)
Operação inversa
Retirar os 0s menos significativos
Retirar o 1
Exemplo: blocos de tamanho 4
Padding
010101010011
100101101010
110100101000
101101101100
Retirar 0s
010101010011
10010110101
110100101
1011011011
Retirar 1
(Original)
01010101001
1001011010
11010010
101101101
Carlos André B. de Carvalho
Tópicos em Computação
29
Modos de Operação
Modo ECB (Eletronic Codebook)
Cifragem dos blocos de forma independente
ci = ek(pi)
Exemplo (bloco de 4 bits): ek(p) = p XOR k
p = 01011000010
k = 0100
p (padding) = 010110000101
p1 = 0101 p2 = 1000 p3 = 0101
c1 = ek(p1) = 0101 XOR 0100 = 0001
c2 = ek(p2) = 1000 XOR 0100 = 1100
c3 = ek(p3) = 0101 XOR 0100 = 0001
c = 000111000001
Carlos André B. de Carvalho
Tópicos em Computação
30
15
Modos de Operação
Modo ECB (Eletronic Codebook)
Decigragem dos blocos de forma independente
pi = dk(ci)
Exemplo (bloco de 4 bits): dk(c) = c XOR k
c = 000111000001
k = 0100
c1 = 0001 c2 = 1100 c3 = 0001
p1 = ek(c1) = 0001 XOR 0100 = 0101
p2 = ek(c2) = 1100 XOR 0100 = 1000
p3 = ek(c3) = 0001 XOR 0100 = 0101
p (com padding) = 010110000101
p (original) = 01011000010
Carlos André B. de Carvalho
31
Tópicos em Computação
Modos de Operação
Modo CBC (Cipher Block Chaining)
Cifragem dos blocos
ci = ek ( pi ⊕ ci −1 )
Exemplo (bloco de 4 bits): ek(p) = p XOR k
p = 01011000010
k = 0100
vi = c0 =
p (padding) = 010110000101
p1 = 0101 p2 = 1000 p3 = 0101
c1 = ek(p1 ⊕ c0) = ek(0101 ⊕ 0000) = 0101 XOR
c2 = ek(p2 ⊕ c1) = ek(1000 ⊕ 0001) = 1001 XOR
c3 = ek(p3 ⊕ c2) = ek(0101 ⊕ 1101) = 1000 XOR
c = 000111011100
0000
0100 = 0001
0100 = 1101
0100 = 1100
XOR: Referente a função de cifragem (deve ser substituído conforme a cifra
utilizada)
⊕ : Referente ao modo de operação CBC (existe sempre ao utilizar esse modo
de operação
Carlos André B. de Carvalho
Tópicos em Computação
32
16
Modos de Operação
Modo CBC (Cipher Block Chaining)
Decigragem dos blocos
pi = d k (ci ) ⊕ ci −1
Exemplo (bloco de 4 bits): dk(c) = c XOR k
c = 000111011100
k = 0100
vi = c0 =
c1 = 0001 c2 = 1101 c3 = 1100
p1 = ek(c1)⊕ c0 = (0001 XOR 0100) XOR 0000 =
p2 = ek(c2)⊕ c1 = (1101 XOR 0100) XOR 0001 =
p3 = ek(c3)⊕ c2 = (1100 XOR 0100) XOR 1101 =
p (com padding) = 010110000101
p (original) = 01011000010
0000
0101
1000
0101
XOR: Referente a função de decifragem (deve ser substituído conforme a cifra
utilizada)
XOR: Referente ao modo de operação CBC (existe sempre ao utilizar esse
modo de operação
Carlos André B. de Carvalho
33
Tópicos em Computação
Modos de Operação
Modo CBC (Cipher Block Chaining)
Cifragem dos blocos
ci = ek ( pi ⊕ ci −1 )
Exemplo (bloco de 4 bits): ek(p) = p ADD k
p = 01011000010
k = 0100
vi = c0 =
p (padding) = 010110000101
p1 = 0101 p2 = 1000 p3 = 0101
c1 = ek(p1 ⊕ c0) = ek(0101 ⊕ 0000) = 0101 ADD
c2 = ek(p2 ⊕ c1) = ek(1000 ⊕ 1001) = 0001 ADD
c3 = ek(p3 ⊕ c2) = ek(0101 ⊕ 0101) = 0000 ADD
c = 100101010100
ADD: Referente a função de cifragem (adição)
⊕ : Referente ao modo de operação CBC
Carlos André B. de Carvalho
Tópicos em Computação
0000
0100 = 1001
0100 = 0101
0100 = 0100
34
17
Modos de Operação
Modo CBC (Cipher Block Chaining)
Decigragem dos blocos
pi = d k (ci ) ⊕ ci −1
Exemplo (bloco de 4 bits): dk(c) = c SUB k
c = 100101010100
k = 0100
vi = c0 = 0000
c1 = 1001 c2 = 0101 c3 = 0100
p1 = ek(c1)⊕ c0 = (1001 SUB 0100) XOR 0000 = 0101
p2 = ek(c2)⊕ c1 = (0101 SUB 0100) XOR 1001 = 1000
p3 = ek(c3)⊕ c2 = (0100 SUB 0100) XOR 0101 = 0101
p (com padding) = 010110000101
p (original) = 01011000010
SUB: Referente a função de decifragem (subtração)
XOR: Referente ao modo de operação CBC
Carlos André B. de Carvalho
Tópicos em Computação
35
Estrutura de Feistel
Cifras de bloco
Algoritmo
Divisão de um bloco de comprimento m em dois de comprimento m/2
Bi = Li | Ri é o bloco resultante da i-ésima rodada
ki é a chave da i-ésima rodada (i = 1, 2, …, r)
B0 é o bloco original (em claro)
Ri = Li −1 ⊕ f ( Ri −1 , ki )
Li = Ri −1
Decifragem
Execução na ordem inversa (i = r, …, 2, 1)
Ri −1 = Li
Li −1 = Ri ⊕ f ( Li , ki )
Carlos André B. de Carvalho
Tópicos em Computação
36
18
Estrutura de Feistel
Exemplo:
A cifra CABC é uma cifra de bloco de 8 bits, executada em 3
rodadas, utilizando a Estrutura de Feistel
Chave k = k1k2k3k4k5k6k7k8, de 8 bits.
Geração das subchaves: k1 = k1k4k2k7 e k2 = k2k3k8k5 e k3 = k2k5k3k8
Função de cifragem F(Ri-1,ki) = P(S(Ri-1 AND ki))
P(x1x2x3x4) = x4x1x3x2
S(x1x2x3x4)
x1x2\x3x4
00
01
10
11
Carlos André B. de Carvalho
00
0101
1100
0010
1011
01
0000
1010
1111
0100
10
1000
0011
0110
1101
11
1110
0111
0001
1001
Tópicos em Computação
37
Estrutura de Feistel
Exemplo:
Cifrar o bloco p = 10100110 com a chave k = 01001101
L0 = 1010
1ª Rodada
k1
L1
R1
R1
R1
=
=
=
=
=
Carlos André B. de Carvalho
R0 = 0110
0010
R0 = 0110
L0 XOR F(R0,k1) = L0 XOR P(S(R0 AND k1))
1010 XOR P(S(0110 AND 0010)) = 1010 XOR P(S(0010))
1010 XOR P(1000) = 1010 XOR 0100 = 1110
Tópicos em Computação
38
19
Estrutura de Feistel
Exemplo:
Cifrar o bloco p = 10100110 com a chave k = 01001101
L1 = 0110
2ª Rodada
k2
L2
R2
R2
R2
=
=
=
=
=
R1 = 1110
1011
R1 = 1110
L1 XOR F(R1,k2) = L1 XOR P(S(R1 AND k2))
0110 XOR P(S(1110 AND 1011)) = 0110 XOR P(S(1010))
0110 XOR P(0110) = 0110 XOR 0011 = 0101
Carlos André B. de Carvalho
Tópicos em Computação
39
Estrutura de Feistel
Exemplo:
Cifrar o bloco p = 10100110 com a chave k = 01001101
L2 = 1110
3ª Rodada
k3
L3
R3
R3
R3
=
=
=
=
=
R2 = 0101
1101
R2 = 0101
L2 XOR F(R2,k3) = L2 XOR P(S(R2 AND k3))
1110 XOR P(S(0101 AND 1101)) = 1110 XOR P(S(0101))
1110 XOR P(1010) = 1110 XOR 0110 = 1000
Criptograma c = 01011000
Carlos André B. de Carvalho
Tópicos em Computação
40
20
Estrutura de Feistel
Exemplo:
Decifrar o bloco c = 01011000 com a chave k = 01001101
L3 = 0101
Execução das rodadas na ordem inversa
3ª Rodada
R3 = 1000
Observe a inversão também dos blocos nas fórmulas
k3
R2
L2
L2
L2
=
=
=
=
=
1101
L3 = 0101
R3 XOR F(L3,k3) = R3 XOR P(S(L3 AND k3))
1000 XOR P(S(0101 AND 1101)) = 1000 XOR P(S(0101))
1000 XOR P(1010) = 1000 XOR 0110 = 1110
Carlos André B. de Carvalho
Tópicos em Computação
41
Estrutura de Feistel
Exemplo:
Decifrar o bloco c = 01011000 com a chave k = 01001101
L2 = 1110
2ª Rodada
k2
R1
L1
L1
L1
=
=
=
=
=
Carlos André B. de Carvalho
R2 = 0101
1011
L2 = 1110
R2 XOR F(L2,k2) = R2 XOR P(S(L2 AND k2))
0101 XOR P(S(1110 AND 1011)) = 0101 XOR P(S(1010))
0101 XOR P(0110) = 0101 XOR 0011 = 0110
Tópicos em Computação
42
21
Estrutura de Feistel
Exemplo:
Decifrar o bloco c = 01011000 com a chave k = 01001101
L1 = 0110
1ª Rodada
k1
R0
L0
L0
L0
=
=
=
=
=
R1 = 1110
0010
L1 = 0110
R1 XOR F(L1,k1) = R1 XOR P(S(L1 AND k1))
1110 XOR P(S(0110 AND 0010)) = 1110 XOR P(S(0010))
1110 XOR P(1000) = 1110 XOR 0100 = 1010
Texto original p = 10100110
Carlos André B. de Carvalho
Tópicos em Computação
43
Estrutura de Feistel
Exemplo alternativo de decifragem:
C = RiLi inversão dos blocos
Decifrar o bloco c = 10000101 com a chave k = 01001101
L3 = 1000
Agora o procedimento é o mesmo da cifragem
3ª Rodada
R3 = 0101
Exceto pela ordem das chaves
k3
L2
R2
R2
R2
=
=
=
=
=
Carlos André B. de Carvalho
1101
R3 = 0101
L3 XOR F(R3,k3) = L3 XOR P(S(R3 AND k3))
1000 XOR P(S(0101 AND 1101)) = 1000 XOR P(S(0101))
1000 XOR P(1010) = 1000 XOR 0110 = 1110
Tópicos em Computação
44
22
Estrutura de Feistel
Exemplo:
Decifrar o bloco c = 10000101 com a chave k = 01001101
L2 = 0101
2ª Rodada
k2
L1
R1
R1
R1
=
=
=
=
=
R2 = 1110
1011
R2 = 1110
L2 XOR F(R2,k2) = L2 XOR P(S(R2 AND k2))
0101 XOR P(S(1110 AND 1011)) = 0101 XOR P(S(1010))
0101 XOR P(0110) = 0101 XOR 0011 = 0110
Carlos André B. de Carvalho
Tópicos em Computação
45
Estrutura de Feistel
Exemplo:
Decifrar o bloco c = 10000101 com a chave k = 01001101
L1 = 1110
1ª Rodada
k1
L0
R0
R0
R0
=
=
=
=
=
R1 = 0110
0010
R1 = 0110
L1 XOR F(R1,k1) = L1 XOR P(S(R1 AND k1))
1110 XOR P(S(0110 AND 0010)) = 1110 XOR P(S(0010))
1110 XOR P(1000) = 1110 XOR 0100 = 1010
Texto original p = R0L0 = 10100110
Precisa inverter novamente
Carlos André B. de Carvalho
Tópicos em Computação
46
23
Cifra RSA
Geração de um par de chaves
Escolha de dois primos gigantes p e q.
p = 19 e q = 23
Cálculo da chave pública
N = p * q = 19 * 23 = 437
(p - 1) * (q - 1) = 18 * 22 = 396
396 = 22 * 32 * 11 e não pode ser dividido por 2, 3 e 11
e = 13
MDC(396,13) = 1
Kp = {e, N} = {13, 437} (chave publica)
Cálculo da chave privada
d * e = 1 (mod (p-1)*(q–1))
d = ?
Carlos André B. de Carvalho
47
Tópicos em Computação
Cifra RSA
Geração de um par de chaves
Cálculo da chave privada
Algoritmo de Euclides estendido: MDC (e, (p-1)*(q-1))
MDC (13, 396)
13 ÷ 396 = 0 com resto 13
13 = (1 * 13) + (0 * 396) = (1 *
396 ÷ 13 = 30 com resto 6
6 = (1 * 396) – (30 * 13)
13 ÷ 6 = 2 com resto 1
1 = (1 * 13) – (2 * 6)
(por
1 = (1 * 13) – (2 * ((1 * 396) –
1 = (1 * 13) – (2 * 396) + (60 *
1 = (61 * 13) – (2 * 396)
6 ÷ 1 = 6 com resto 0
Carlos André B. de Carvalho
Tópicos em Computação
13)
(1)
(2)
2: 6 = 396 – 30*13)
(30 * 13)))
13)
(3)
48
24
Cifra RSA
Geração de um par de chaves
Cálculo da chave privada
Por meio do algoritmo de Euclides obtivemos que
1 = (61 * 13) – (2 * 396)
Sabemos que: e = 13 e (p-1)*(q-1) = 396
Queremos obter d, em que: 13*d = 1 (mod 396)
(13*61) % 396 = 793 % 396 = 1
d = 61
Ks = {d, N} = {61, 437} (chave secreta)
Carlos André B. de Carvalho
Tópicos em Computação
49
Cifra RSA
Cifragem
C = M e (mod N )
Exemplo: M = 88 (caractere ‘a’ em ASCII)
Decomposição do expoente para facilitar os cálculos
C =
C =
881
882
884
888
C =
C =
C =
Algumas calculadores só trabalham com poucos dígitos (10 ou 12)
8813 (mod 437)
[881 * 884 * 888] (mod 437)
(mod 437) = 88
(mod 437) = 7744 (mod 437) = 315
(mod 437) = 3152 (mod 437) = 99225 (mod 437) = 26
(mod 437) = 262 (mod 437) = 676 (mod 437) = 239
[88 * 26 * 239] (mod 437)
[2288 * 239] (mod 437) = [103 * 239] (mod 437)
24617 (mod 437) = 145
Carlos André B. de Carvalho
Tópicos em Computação
50
25
Cifra RSA
Decifragem
M = C d (mod N )
Exemplo: C = 145
M = 14561 (mod 437)
M = [1451 * 1454 * 1458 * 14516 * 14532] (mod 437)
1451 (mod 437) = 145
1452 (mod 437) = 21025 (mod 437) = 49
1454 (mod 437) = 492 (mod 437) = 2401 (mod 437) = 216
1458 (mod 437) = 2162 (mod 437) = 46656 (mod 437) = 334
14516 (mod 437) = 3342 (mod 437) = 111556 (mod 437) = 121
14532 (mod 437) = 1212 (mod 437) = 14641 (mod 437) = 220
M = [145 * 216 * 334 * 121 * 220] (mod 437)
M = [31320 * 334 * 121 * 220] (mod 437) = [293 * 334 * 121 * 220] (mod 437)
M = [97862 * 121 * 220] (mod 437) = [411 * 121 * 220] (mod 437)
M = [49731 * 220] (mod 437) = [350 * 220] (mod 437) = [77000] (mod 437)
M = 88
Carlos André B. de Carvalho
Tópicos em Computação
51
OBRIGADO!
Agradecimentos
Contato:
Carlos André Batista de Carvalho
[email protected]
Carlos André B. de Carvalho
Tópicos em Computação
52
26

Documentos relacionados