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