Criptografia

Aprenda as técnicas de criptografia e como abordá-las em CTFs. Desde a criptografia clássica das

cifras até a criptografia moderna das chaves públicas.

O que é criptografia?

Cifra de César

Cifras de Substituição Simples

Cifra de Vigenère

One-Time Pad

Cifras de Transposição
O que é criptografia?
Criptografia vem do grego kryptós e graphein, que significam "secreta" e "escrita",

respectivamente. Até a era moderna, ela era sinônimo de encriptação, que é a conversão de uma

mensagem legível para algo aparentemente sem sentido, e é esse o conceito usado em CTFs.

Para entender melhor essa ideia, digamos que Alice quer mandar uma mensagem para Bob sem

que uma terceira pessoa, digamos Eve, descubra seu counteúdo.

Para isso, Alice usa um certo algoritmo para tornar a mensagem ilegível de forma que só Bob

saberá reverter a mensagem encriptada.

Assim, quando Eve interceptar a mensagem por meio do canal inseguro, se ela não possui o

algoritmo criptográfico usado por Alice e Bob, ela não será capaz de entender a mensagem.

Ao longo da história, várias técnicas de ocultar mensagens foram desenvolvidas. Antes da

criptografia pré-computacional, a criptografia clássica era formada por um conjunto de métodos

de substituição e transpoisção de caracteres. E com o advento da computação, a criptografia

moderna se tornou amplamente embasada em teorias matemáticas e práticas de ciência da

computação.

Para esse guia, começaremos com os métodos da criptografia clássica.

 Cifra de César
A Cifra de César é um dos métodos mais simples e comuns de encriptação. Mesmo não sendo

muito comum em CTFs, ainda é um conhecimento básico de criptografia.

Esse método tem esse nome pois era usado por Júlio César em suas
“ correspondências

Nessa cifra, cada letra da mensagem é substituida por uma letra do alfabeto deslocado por um

número fixo.

Por exemplo, se queremos encriptar a mensagem hack the planet , podemos deslocar cada letra

do alfabeto 3 vezes para direita (ou right 3). Assim, a substituição teria esse formato:

original
ABCDEFGHI JKLM

right
DEFGHI J KLMNOP
3

original
NOPQRSTUVWXYZ

right
QRSTUVWXYZABC
3

texto original: hack the planet

texto cifrado: kdfn wkh sodqhw

Dessa forma, o texto gerado se torna incompreensível de forma que só quem sabe o algoritmo

usado poderá recuperá-lo.

ROT13
Um dos tipos mais comuns de Cifra de César é o ROT13. Nele, o alfabeto é deslocado 13 vezes.

Como o alfabeto tradicional possui 26 letras, o ROT13 possui a propriedade de que o mesmo

algoritmo usado para encripitar a mensagem é usado para decriptar.

Detectando
Mensagens encriptadas pela cifra de césar normalmente produzirão um amontoado de caracteres

sem significado, como kdfn wkh sodqhw , e suas letras terão uma distribuição de frequência similar

à língua usada (provavelmente inglês), mas com as letras trocadas. Esse conceito será abordado

com mais profundidade em Cifras de Substituição.

Devido a facilidade de quebrar essa cifra, pode ser conveniente tentar solucioná-la sem nem ao

menos uma análise de frequência.

Solucionando
Como num alfabeto usual são usados apenas 26 caracteres, a Cifra de César possui apenas 25

tipos de rotações possíveis (pois a rotação 26 é a própria mensagem). Assim, um testa tudo,

onde você faz todos os tipos de rotações possíveis, é a opção mais simples.

Existem ferramentas online muito eficientes para quebrar uma Cifra de César, como o site dcode,

porém não é muito difícil codificar um testa tudo para isso.

Codificando um testa tudo

Primeiro, codificaremos uma função rot() que aplica a rotação em um caractere, de acordo com

o deslocamento determinado (o shift ):

def rot(char, shift):

return chr((ord(char) - ord('A') + shift)%26 + ord('A'))

Assim, podemos usar essa função para criar um caesar_brute_force() que recebe um texto cifrado
e imprime todas as rotações possíveis.

def caesar_brute_force(cipher_text):

cipher_text = cipher_text.upper()

for i in range(26):

line = ''

for c in cipher_text:

line += rot(c, i) if [Link]() else c

print(f'rot{i}:\t{line}')

Exercícios
OverTheWire: Krypton 1

OverTheWire: Krypton 2

WeChall: Caesar
Cifras de Substituição
Simples
Agora que você está familiarizado com a Cifra de César, vamos apresentar uma generalização

desse conceito: as cifras de substituição simples.

Em uma cifra de substituição simples, cada letra é substituida individualmente de acordo com um

alfabeto de substituição. Esse alfabeto pode ser uma rotação fixa do alfabeto normal (como a

cifra de César) ou algum embaralhamento mais complexo.

Alguns exemplos notáveis de cifra de substituição simples são:

Cifra de Atbash
Seu nome tem origem da primeira, última, segunda e penúltima letra Hebraica
“ (Aleph-Taw-Bet-Shin)

Nessa cifra, cada letra é mapeada para o alfabeto invertido, ou seja, a primeira vira a última, a

segunda vira a penúltima e assim por diante.

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

cifra: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Assim, se usarmos essa cifra em may the force be with you , obteremos:

original: M A Y T H E F O R C E B E W I T H Y O U

cifrado: N Z B G S V U L I X V Y V D R G S B L F

A Cifra de Atbash pode ser interpretada como um caso particular da Cifra de Affine, uma cifra que
usa aritimética modular para encriptar.

Cifra da Palavra-Chave
A Cifra da Palavra-Chave ou keyword cipher consiste em escolher uma chave e usá-la para decidir

como as letras serão susbtituidas.

As palavras repetidas dessa chave serão removidas e a própria chave será o começo do alfabeto a

ser mapeado. O resto das letras continuarão em ordem alfabética, tirando as letras já usadas.

Por exemplo, escolhendo a chave Marvin , o novo alfabeto terá esse formato

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

cifra: M A R V I N B C D E F G H J K L O P Q S T U W X Y Z

Assim, ao encriptar a mensagem Arthur Dent , obteremos:

original: A R T H U R D E N T

cifrado: M P S C T P V I J S

Detectando
Como mencionado na seção de Cifra de César, uma mensagem encriptada por uma cifra de

substituição simples terá uma distribuição de frequência das letras semelhante ao da língua

usada, mas com as letras trocadas.

Essa distribuição de frequência de um texto pode ser identificada através de uma análise de

frequência.

Nas línguas naturais, algumas letras aparecem mais frequentemente que outras, como uma

espécie de digital do idioma. Por exemplo, a letra mais comum na lígua inglesa é o "e", em

português é o "a".

Essa análise de frequência pode ser feita simplesmente contando as letras do texto. Existem
ferramentas online para isso como o site dcode ou pode ser feito rapidamente com um biblioteca

em Python, onde text é o texto a ser analisado:

from collections import Counter

Counter([Link]()).most_common()

Solucionando
O ponto fraco de cifras de substituição simples é que elas são muito suscetíveis à análises de

frequência.

Assim, se você tiver um texto de tamanho razoável, por volta de 50 caracteres, é possível analisar

a frequência com que as letras aparecem e deduzir qual foi o alfabeto de substituição usado.

O site guaballa é um excelente decodificador de cifras de substituição simples.

Referências
Cifra de Atbash: Jeremiah's Game

Cifra da Palavra-Chave: GeeksforGeeks

Learn Cryptography

Exercícios
OverTheWire: Krypton 3
 Cifra de Vigenère
Devido à vulnerabilidade das cifras de substituição simples, foi necessário a criação de uma cifra

que conseguisse se proteger disso. A Cifra de Vigenère veio com esse propóstio e é

basicamente uma extensão da fórmula da Cifra de César. Ela gera uma distribuição praticamente

uniforme em uma análise de frequência e foi considerada inquebrável por 3 séculos.

Ela tem esse nome em homenagem a Blaise de Vigenère

“

Essa Cifra consiste basicamente em pegar uma palavra-chave e aplicar a cifra de César várias

vezes, de acordo com os caracteres da palavra-chave.

Por exemplo, se nós queremos encriptar a mensagem the cake is a lie usando a palavra-chave

portal , primeiro cada caractere da palavra-chave terá um número de rotações equivalente (de

acordo com sua posição no alfabeto):

letra
POR T A L

rotações
161518201 12

Assim, para cada letra da mensagem será rotacionada de acordo com a sequência de rotações

acima:

mensagem: T H E C A K E I S A L I E

chave: P O R T A L P O R T A L P

mensagem cifrada: I V V V A V T W J T L T T

Essa cifra, diferentemente das cifras de substituição simples, é uma Cifra de Substituição

Polialfabética.

Detectando
Um texto encriptado por essa cifra pode ser detectado através de uma análise de frequência.

A Cifra de Vigenère costuma gerar textos com uma distribuição de frequência das letras próximo

ao uniforme. Se um texto cifrado que não é esperado esse tipo de distribuição obter esse

resultado, provavelmente é Cifra de Vigenère, ou alguma outra Cifra Polialfabética.

Solucinando
Mesmo gerando uma distribuição uniforme em análises de frequência, essa cifra tem uma

vulnerabilidade: a palavra-chave é usada várias vezes em um texto grande.

Dessa forma, se a chave tiver tamanho 5, por exemplo, e ajustarmos o texto em linhas de

comprimento 5, cada coluna terá a mesma rotação. Assim, podemos chutar tamanhos da palavra-

chave e usar a mesma análise de cifra de substituição simples para cada coluna.

Uma ferramenta online muito útill para quebrar a Cifra de Vigenère é o site dcode.

Referências
GeeksforGeeks

Exercícios
OverTheWire: Krypton4

OverTheWire: Krypton5

picoCTF-2018: blaise's cipher

One-Time Pad
Por muitos anos, o problema de esconder os padrões da língua ainda persistia, porém no final do

século XIX surgiu aquele que seria o método mais forte de criptografia: o one-time pad.

Funcionamento
Primeiro, precisamos gerar uma sequência aleatória de bits do mesmo tamanho da mensagem,

essa será o one-time pad. Essa chave deverá ser passada por um meio seguro para o destinatário.

Para esse exemplo, usaremos codificação em base64 para os caracteres.

mensagem: H O P E

one-time pad: y T 2 5

Depois, vamos criar o texto cifrado a partir da mensagem e do one-time pad. Para isso,

codificaremos a mensagem e o one-time pad em binário e realizamos a operação de ou exclusivo

bit a bit, ou XOR.

A operação XOR de dois bits retorna 1, se eles forem diferentes, e 0, se forem

“ iguais.

mensagem: H O P E -> 000111 001110 001111 000100

one-time pad: y T 2 5 -> 110010 010011 110110 111001

XOR |

texto cifrado: 1 d 5 9 -> 110101 011101 111001 111101

Já para recuperar a mensagem, usamos exatamente a mesma operação, realizando um XOR bit a

bit com o texto cifrado e o one-time pad.

Após um uso, o one-time pad deverá ser destruído.

A criptografia perfeita
No final da década de 1940, Claude Shannon provou que se cada chave for usada uma única vez

e ela for gerada aleatoriamente, então o método de one-time pad é perfeitamente seguro.

Isso pode ser visualizado pelo seguinte exemplo: digamos que temos uma mensagem de 24 bits,

logo temos 2^24 possíveis valores para a chave. A partir disso, temos dois problemas:

Poderíamos tentar verificar todas as chaves. Para uma mensagem de 24 bits, ainda é uma

alternativa viável, mas de expandirmos para 54, mesmo se checando 1 milhão de valores por

segundo, ainda levaríamos mais de 570 anos para checar todas as possibilidades.

Outro problema é que cada possível chave gera uma possível mensagem com igual probabilidade

das demais, assim se checarmos todas as chaves, veríamos todas as combinações possíveis de

mensagens de 24 bits.

possível
chave
mensagem

AA 1d
AA 59

AA 1d
AB 58

... ...

+J LU
z5 KE

... ...

yT HO
25 PE

... ...

Dessa forma, não há como distinguir a mensagem real de todas as outras possibilidades.

Entetanto, mesmo a técnica de One-time pad sendo simples e teoricamente inquebrável, na

prática ela possui alguns pontos negativos, que costumam trazer suas vulnerabilidades:

A chave precisa ser usada uma única vez. Se repetida, ela pode ser facilmente quebrada.

Essa era a principal vulnerabilidade de uma cifra semelhante, a Cifra de Vernam.

Ainda é preciso de um canal seguro para distribuir as chaves.

Conseguir bits realmente aleatórios é bem difícil. O exército dos Estados Unidos

conseguiu decifrar, em 1944, as mensagens alemãs cifradas por one-time pad porque as

chaves não eram completamente aleatórias.

A chave precisa ser tão longa quanto a mensagem. Isso implica numa grande dificuldade

de gerar e armazenar chaves para mensagens longas.

Esses dois últimos pontos, especialmente, acabam tornando o one-time pad teórico impraticável.

Linear Feedback Shift Register

Como alternativa às longas sequências de bits realmente aleatórias, foi criado um algoritmo

determinístico capaz de produzir valores pseudo-aleatórios: o linear feedback shift register

ou LFSR.

Valores pseudo-aleatórios são sequências de bits que parecem ser aleatórias. Elas não são

aleatórias de fato, pois são criadas por algoritmos determinísticos, mas, para efeitos práticos, tem

as mesmas propriedades de sequências aleatórias.

Esses valores pseudo-aleatórios são criados da seguinte maneira:

Primeiro, precisamos de uma sequência de bits inicial, chamada de seed. Essa seed dará o

tamanho do registrador, que é um elemento que armazena todos os bits necessários para gerar

o próximo.

Depois, geraremos uma nova sequência através da operação XOR de dois bits, colocando os bits

resultantes à direita.
Por exemplo, a imagem acima representa o registrador com a seed. Nela, os bits 11 e 9 foram

escolhidos para gerar o próximo. Essas posições são chamadas de tap, ela é uma numeração que

começa do 1, indo da direita para esquerda.

Para descrever essas posições do algoritmo, usamos a notação [N, k] LFSR , que representa um

algoritmo de LFSR com um registrador de N bits com taps em N e k . Na imagem acima, temos

um [11,9] LFSR .

Abaixo, está uma pequena simulação de um [5,4] LFSR com a seed 00001 .

[5,4] LFSR

novo bit

seed -> 00001 0

00010 0

00100 0

01000 1

10001 1

00011 0

00110 0

01100 1

11001 0

10010 1

00101 0

registrador

Assim, precisamos apenas criar uma lista de pequenas seeds e distribuí-las por um canal seguro,

usando elas para criar chaves do one-time pad, por meio do LFSR.
Exercícios
Krypton 6

Referências
Khan Academy

Computer Science - Sedgewick & Wayne

Mensagens alemãs não aleatórias

Cifras de Transposição
Na tentativa de encontrar um método alternativo às cifras de substituição simples, que estavam

se tornando frágeis, foram criadas as Cifras de Transposição. Nessa cifra, o texto permanece o

mesmo mas as ordem dos caracteres são alteradas, embaralhando a mensagem de acordo com

um padrão.

Existem vários padrões diferentes para realizar a transposição, os dois mais famosos são a

transposição colunar simples e a rail fence.

Transposição colunar
Com essa regra, a mensagem é escrita horizontalmente numa matriz de largura fixa e a saída é o

texto lido verticalmente nessa matriz.

Numa transposição colunar simples essa leitura é feita por colunas da esquerda para direita.

Por exemplo, com texto a wizard is never late a encriptação será da forma

Texto: A WIZARD IS NEVER LATE

Matriz:

A W I Z A R

D I S N E V

E R L A T E

Texto cifrado: ADEWIRISLZNAAETRVE

Para decriptar, escrevemos o texto cifrado verticalmente numa matriz de mesma largura e lemos

o texto horizontalmente.

A ordem de leitura de colunas pode ser determinada também de acordo com uma palvra-chave.

O tamanho da palavra-chave definirá a largura da matriz usada e cada caractere determina a

ordem que as colunas serão lidas. Por exemplo, usando a chave FRODO , numeramos as letras em

ordem alfabética: 25314 . Assim, podemos usar essa ordem para ler as colunas e gerar o texto

cifrado

Texto: A WIZARD IS NEVER LATE

Ordem: 2 5 3 1 4

Matriz: A W I Z A

R D I S N

E V E R L

A T E

Texto cifrado: ZSRAREAIIEEANLWDVT

Rail Fence
Nesse tipo de transposição, os caracteres são escritos numa matriz usando um padrão fixo em

zigue-zague e a saída é o texto lido horizontalmente. o rail fence admite várias variações, como a

linha que a primeira letra começa e o número de linhas usadas. Por exemplo, usando um rail fence

com duas linhas

Texto: A WIZARD IS NEVER LATE

Matriz:

A - I - A - D - S - E - E - L - T -

- W - Z - R - I - N - V - R - A - E

Texto ciffrado: AIADSEELTWZRINVRAE

Outro exemplo mas com três linhas será da forma

Texto: A WIZARD IS NEVER LATE

Matriz:
 A - - - A - - - S - - - E - - - T -

- W - Z - R - I - N - V - R - A - E

- - I - - - D - - - E - - - L - - -

Texto ciffrado: AASETWZRINVRAEIDEL

Para descriptografar, é necessário o conhecimento do padrão usado e preencher as lacunas com o

texto cifrado horizontalmente e depois ler em zigue-zague.

Essa técnica foi usada na Guerra Civil norte-americana para cifrar as mensagens dos confederados

e dos federalistas.

Identificando
Como apenas a ordem do texto é alterada, a distribuição de frequência das letras será muito

parecida com a frequência da língua usada. Assim, uma análise de frequência do texto cifrado é

um ótimo método para identificar o uso de uma cifra de transposição.

Além disso, podem ter sido usadas cifras de substituição em conjunto, dificultando a indentificação.

Solucionando
Um primeiro método que podemos pensar para quebrar cifras de transposição é testar todas as

possíveis permutações dos caracteres. Porém, um texto de 20 caracteres geraria 20! possíveis

permutações. Se computássemos 100 milhões de valores por segundo, demoraríamos mais de

300 anos para computar todos. Logo, testar todas as possibilidades é inviável.

Como existem vários métodos diferentes de cifras de transposição, cada um necessita de uma

abordagem diferente.

Nesses dois posts no StackExchange: [1] e [2], Ilmari Karonen mostra métodos para resolver

manualmente cifras de transposição colunar.

Referências
Applied Cryptography, second edition

Exercícios
WeChall: Transposition I