Fala, pessoal, tudo bem? Hoje vamos entender a diferença entre criptografia simétrica e assimétrica, entender criptografia RSA, que é o sistema assimétrico mais famoso hoje em dia, e ao fim, vamos entender a importância de números primos. Creio que o público-alvo já deve ter pelo menos uma noção do que é criptografia e para o que serve, então não vou me ater a esses floreios, vamos direto para o que importa aqui.

Vou começar explicando a cifra de César, um sistema criptográfico muito simples. Assim como o 'Hello, world!' está para a programação, a cifra de César está para a área de criptografia, então nós vamos usá-lo apenas como um pretexto para explicar simetria, e depois assimetria.

Cifra de César

A cifra de César é um tipo de criptografia de substituição, que consiste basicamente em uma troca de letras como vemos abaixo:

a	b	c	d	e	f	g	h	i	j	k	l	m
d	e	f	g	h	i	j	k	l	m	n	o	p

n	o	p	q	r	s	t	u	v	w	x	y	z
q	r	s	t	u	v	w	x	y	z	a	b	c

Analisando a tabela, você consegue deduzir como a encriptação é feita?

Exatamente, a encriptação será simplesmente pegar a letra que deseja criptografar e ver qual é a 3º letra à sua frente:
C(g) = k
C(y) = b (se não há mais letras à frente, voltamos para o início do alfabeto)

E a decriptação será o processo inverso da encriptação: pegar a letra criptografada e ver qual é a 3º letra que a precede.
C(g) = k => D(C(g)) = D(k) => G = D(k)

A cifra de César é um tipo muito fraco de criptografia. Por exemplo, se fizermos uma criptoanálise de frequência de letras, nós conseguimos inferir qual letra encriptada corresponde à original, e logo conseguimos pegar o esquema.

Porém há outro fator além deste que pode torná-la insegura para envio de dados, que é o fato de ser simétrica. Abaixo vamos entender o que significa ser simétrica, e porque isso pode ser um problema dependendo do contexto.

Criptografia simétrica vs. assimétrica

Na cifra de César, tanto o emissor quanto o receptor precisam simultaneamente ter ciência de quantas posições devem se deslocar no alfabeto para encriptar/decriptar a informação. Este segredo de quantas posições deslocar, nós vamos chamar de chave (há controvérsias se o tamanho do deslocamento na cifra de César é uma chave, pois é intrínseco no método que o deslocamento é sempre 3, mas para a explicação, vamos considerar o tamanho do deslocamento como uma chave).

Note que ambos os envolvidos na comunicação precisam ter em posse a mesma chave para estabelecer uma comunicação. Note também que esta chave serve tanto para encriptar quanto para decriptar uma mensagem. Então mesmo que por ventura uma parte deseje só criptografar para enviar à outra parte, ela ainda assim precisará de uma chave que desempenha as duas funções.

Quando ambos os envolvidos na comunicação são capazes de criptografar e descriptografar usando a mesma chave para isto, nós chamamos a chave de chave única, e dizemos que a criptografia é simétrica. A chave é única justamente porque ela é usada tanto na hora de criptografar quanto na hora de descriptografar.

Você pode levantar o seguinte questionamento: "E se dissermos ao receptor somente a informação que ele precisa para descriptografar, que é regredir 3 posições para achar a letra original? Assim não falaríamos a ele qual é a regra de encriptação."

Pois, bem, note que anteriormente eu coloquei "encriptar/decriptar" junto, pois no fim das contas, a regra de ambas as funções é a mesma coisa, já que sabendo uma delas, conseguimos chegar imediatamente na outra:

1. \Rightarrow Se para descriptografar, eu preciso regredir 3 posições, é lógico que para criptografar, eu preciso progredir 3 posições.
2. \Leftarrow Se para criptografar, eu preciso progredir 3 posições, é lógico que para descriptografar, eu preciso regredir 3 posições.
3. \Leftrightarrow Logo, eu descriptografo regredindo 3 posições se, e somente se, eu criptografo progredindo 3 posições.

Em alguns casos em que os canais de comunicação são poucos, e temos garantia que são confiáveis, pode ser interessante usar uma criptografia simétrica, considerando também que elas são bem mais rápidas na hora de serem geradas quando comparadas com as assimétricas. Porém na grande maioria dos casos é um problema usar chaves únicas.

Imagine um banco que possui vários clientes, e sempre que esses clientes precisam fazer uma transferência bancária, eles precisam enviar informações sigilosas pela rede. Seria insustentável uma criptografia simétrica nesse caso, pois se um monte de pessoas tem uma chave que encripta/decripta, basta uma pessoa maliciosa interceptar uma mensagem criptografada, e usar a própria chave dada a ele pelo banco para descriptografá-la.

Como o banco pode consertar esta falha?

Se o banco quiser continuar insistindo em chaves únicas, há várias maneiras de dificultar o trabalho do hacker, como por exemplo, criar chaves diferentes para cada usuário. Porém estas maneiras seriam muito mais uma solução paliativa do que uma solução de fato. Devemos considerar também que os métodos de criptografia simétrica hoje em dia são razoavelmente fáceis de serem burlados usando criptoanálise.

Já que os clientes apenas enviarão informações ao banco, a melhor opção então seria dar um jeito de delegar a eles somente a função de criptografar, e restringir ao banco a função de descriptografar os dados, concorda?

Pois bem, é justamente essa a ideia de uma criptografia assimétrica: você criar uma assimetria na comunicação onde somente uma parte tem poder de decriptar, e a outra parte pode apenas encriptar os dados e enviar para a parte capaz de decriptar.

Logo ao invés de haver uma chave única capaz de encriptar/decriptar, na criptografia assimétrica há duas chaves:

1. chave pública, que é capaz apenas de encriptar.
2. chave privada, que é capaz apenas de decriptar.

Vamos agora entender como funciona um método assimétrico.

Criptografia RSA

Apesar de ser necessário um conhecimento matemático para entender a criptografia RSA, a maioria dos conhecimentos serão tranquilos e intuitivos, como por exemplo, saber o que é máximo divisor comum (MDC), números primos, função de Euler, etc. Caso você não conheça algum desses assuntos, eu vou me esforçar ao máximo para explicá-los conforme eles forem demandados durante a explicação.

Primeiro passo é escolhermos dois números primos p e q com no mínimo do mínimo 150 casas decimais e guardá-los em segredo. A segurança do método está intimamente ligada à magnitude dos números primos, por isso devemos escolher números muito grandes.

Números Primos

Números primos são números que são divisíveis somente por 1 e por ele mesmo.

Exemplo:
2 é primo, pois só é divisível por 1 e por 2 (ele mesmo).
7 é primo, pois só é divisível por 1 e por 7.
6 não é primo, pois é divisível por 1, por 2, por 3 e por 6.

Os primos também precisam estarem distantes um do outro. Caso eles estejam muito próximos, conseguimos descobri-los por meio de um método de tentativa e erro.

Após isso, vamos multiplicar p e q para criar um número n que só é divísivel por p e q:
n = p \cdot q

Agora devemos escolher um número natural e tal que mdc(e, φ(n)) = 1
Onde φ(n) é a função de Euler. Ela também deve ser guardada em segredo.

Máximo Divisor Comum (MDC)

Como o próprio nome já diz, o mdc de dois números inteiros é o maior divisor capaz de dividir ambos simultaneamente.

Exemplo:
12 = 2^2\cdot3
10 = 2\cdot5
Logo mdc(12, 10) = 2, já que o fator máximo que ambos compartilham é 2^1.

Outro exemplo:
154 = 2\cdot7\cdot11
660 = 2^2\cdot3\cdot5\cdot11
Logo mdc(154, 660) = 2\cdot11 = 22, já que ambos têm simultaneamente 2^1 e 11^1 como fatores.

Função φ(n) de Euler

φ(n) nos informa a quantidade de números inteiros positivos z \leq n, tal que mdc(z, n) = 1, isto é, tal que z e n são primos relativos entre si.

Exemplo:
φ(12) = 4, pois há 4 números menores ou iguais a 12 que são primos relativos a 12:
mdc(1, 12) = 1 ✔
mdc(2, 12) = 2 ✘
mdc(3, 12) = 3 ✘
mdc(4, 12) = 4 ✘
mdc(5, 12) = 1 ✔
mdc(6, 12) = 6 ✘
mdc(7, 12) = 1 ✔
mdc(8, 12) = 4 ✘
mdc(9, 12) = 3 ✘
mdc(10, 12) = 2 ✘
mdc(11, 12) = 1 ✔
mdc(12, 12) = 12 ✘

Não precisamos testar um por um, há uma fórmula para calcular φ(n) de forma analítica:

1. Decompor n em seus fatores primos.
2. Calcular φ(p) para cada primo usando a fórmula φ(p^a) = p^a - p^{a-1}
3. Multiplicar todos os φ(p)

12 = 2^2\cdot3
φ(2^2) = 2^2-2^1 = 2
φ(3) = 3^1 - 3^0 = 3 - 1 = 2
logo φ(12) = φ(2^2)\cdotφ(3) = 2\cdot2 = 4

Encriptação

A chave pública consistirá de:

• o número n
• o número e

A chave pública será usada por quem quiser. Vamos ver a seguir como usar a chave pública para criptografar um bloco b de dados.

Primeiro devemos pegar um bloco b onde b é um número entre \;1\; e \;n-1:
1 < b < n - 1
Caso contrário, a encriptação não dará certa. Lembrando que qualquer informação pode ser representada como um número inteiro em um computador.

C(b) = resto da divisão de b^e por n

Alguns detalhes importantes:
Se e = 1,\;b^e = b^1
Como C(b) é igual ao resto da divisão de b^e por n,
E como b < n, o resto de b^1 por n é igual b
Logo C(b) = b, o que significa que não criptografamos b

1 < e < φ(n)

Em termos de pseudocódigo, poderíamos expressar C(b) da seguinte forma:
bloco_cript = exponencial_modular(base = b, expoente = e, mod = n)

Decriptação

A chave privada consistirá de:

• o número n
• um inverso positivo de e módulo φ(n). Chamaremos este número de " d "

n é usada tanto na chave pública quanto na privada, então ela é uma informação pública. Já d deve ser guardada em segredo. E por isso a importância de guardar φ(n) em segredo também, pois se não fosse, poderíamos usá-la em conjunto com e, que é uma informação pública, para descobrir d. Sem contar que a partir de apenas φ(n), nós conseguimos usar um método para descobrir os números primos p e q escolhidos.

Inverso de um número módulo m

O inverso de um número inteiro x módulo m é o número inteiro i que multiplicado por x fica congruente a 1 módulo m, isto é, o resultado da multiplicação entre x e i deixa resto 1 na divisão por m:

Um número x só tem inverso módulo m se, e somente se, mdc(x, m) = 1 (isto é, se x e m forem primos relativos entre si)

Exemplo:
13 \cdot i \equiv 1 (mod\;17)\;;\;mdc(13, 17) = 1, então existe inverso i
Usando algoritmo de Euclides para descobrir i:
17 = 13\cdot1 + 4 \Rightarrow 4 = 17 - 13\cdot1
13 = 4\cdot3 + 1 \Rightarrow 1 = 13 - 4\cdot3
1 = 13 - (17 - 13\cdot1)\cdot3 = 13 - 17\cdot3 + 13\cdot3
\Rightarrow 1 = 13\cdot4 + 17(-3) = 52 - 51 = 1
Logo 4 é o inverso de 13 módulo 17

d então é um número positivo que quando multiplicado por e, o resultado dessa multiplicação é congruente a 1 módulo φ(n):
ed \equiv 1\;(mod\;φ(n))

A chave privada será usada somente por nós. Vamos ver a seguir como usar a chave privada para descriptografar um bloco b de dados criptografados.

Vamos pegar um bloco b criptografado, isto é, pegar C(b), e aplicar a decriptação.

D(C(b)) = resto da divisão de [C(b)]^d por n

Prova

Se C(b) = resto da divisão de b^e por n
Isto significa que C(b) \equiv b^e\;(mod\;n)

Se D(C(b)) = resto da divisão de [C(b)]^d por n
Isto significa que D(C(b)) \equiv [C(b)]^d\;(mod\;n)

A notação " \equiv " significa "congruente a".
Um número x é congruente a y módulo m se, e somente se, eles deixam o mesmo resto de divisão quando divididos por m.

Exemplo:
10 é congruente a 34 módulo 8, pois o resto da divisão por 8 de ambos vale 2.
10\div8 = 1\cdot8 + 2
34\div8 = 4\cdot8 + 2

Como C(b) \equiv b^e, \;D(C(b)) \equiv (b^e)^d\;(mod\;n)

**Não confunda: C(b) é congruente a b^e, ele NÃO É igual a b^e

ed \equiv 1\;(mod\;φ(n)) implica em ed - 1 = φ(n)\cdot k \Rightarrow ed = φ(n)k + 1\;;\;\; k \in\mathbb{Z}\;

Se x \equiv y \; (mod\;m), então x e y deixam o mesmo resto em uma divisão por m:
x = m\cdot k + r
y = m\cdot k' + r

Sendo assim x - y = mk + r - (mk' + r) = mk + \cancel{r} - mk' - \cancel{r} = m(k - k') = mk''

Logo \;x - y = mk''
(este " k'' " é um número inteiro que multiplicado por m, resulta em x - y)

Sabemos que φ(n) = (p-1)(q-1)\;, logo \;ed = (p-1)(q-1)k + 1

Sabemos também que D(C(b)) \equiv b^{ed}\;(mod\;n)

Então D(C(b)) \equiv b^{(p-1)(q-1)k + 1} = b\cdot b^{(p-1)(q-1)k}\;(mod \;n)

Agora basta nós analisarmos algumas situações para simplificarmos a expressão acima:

Sobre os símbolos que aparecerão abaixo:

• " \mid " significa “divide”
• " \nmid " significa "não divide"

• Se p \nmid b:

  • Pelo pequeno teorema de Fermat, temos que b^{(p - 1)} \equiv 1\;(mod\;p)
    Então b\cdot(b^{(p - 1)})^{(q - 1)k} ≡ b\cdot(1)^{(q - 1)k} = b\;(mod\;p)

    Teorema de Fermat: se p é um número primo e p \nmid a, então a^{p−1} \equiv 1\;(mod\;p).

• Se p \mid b:

  • b \equiv 0\;(mod\;p) \Rightarrow b^{ed} \equiv 0^{ed}\;(mod\;p)

    Sejam m e x números inteiros. Se m \mid x, então\;x \equiv 0\;(mod\;m)

    Se b \equiv 0 \;(mod\;p)\; e \;b^{ed} \equiv 0\;(mod\;p)
    Entao b^{ed} ≡ b \;(mod\;p)

Analogamente, o mesmo vale para o primo q: \;b^{ed} \equiv b\;(mod\;q)

Pelas expressões modulares, sabemos que:

• b^{ed} - b = p\cdot k\;, portanto p \mid b^{ed} - b
• b^{ed} - b = q\cdot k\;, portanto q \mid b^{ed} - b

Já que p e q dividem \;b^{ed} - b\;, \;e mdc(p, q) = 1 - pois são dois números primos -, nós podemos afirmar que:

• p\cdot q \mid b^{ed} - b \Rightarrow b^{ed} \equiv b \;(mod\;pq)

n = pq

Como D(C(b)) ≡ b^{ed}\;(mod\;n)\; e \;b^{ed} \equiv b \;(mod\;n)

D(C(b)) ≡ b\;(mod\;n)
\Rightarrow D(C(b)) = resto da divisão de [C(b)]^d por n\;\;\;\;\blacksquare

Em termos de pseudocódigo, poderíamos expressar D(C(b)) da seguinte forma:
bloco_decript = exponencial_modular(base = bloco_cript, expoente = d, mod = n)

Agora vocês conseguem compreender a importância dos números primos? Toda a criptografia RSA está baseada no fato de não ser possível encontrar os divisores de um número de maneira analítica. A única forma é por meio da tentativa e erro.
Então apesar de n ser um número conhecido por qualquer um, a única forma de descobrir seus divisores p e q, é tentando dividi-lo por uma quantidade avassaladora de possibilidades.

Porém, se por um acaso conseguirmos descobrir um divisor de n \rightarrow automaticamente temos o outro divisor \rightarrow então tendo os dois divisores de n, isto é, os primos p e q, conseguimos calcular φ(n) \rightarrow tendo φ(n), conseguimos calcular d \rightarrow e tendo d, conseguimos decriptar o número.

Vamos agora a um exemplo prático:

**Visando praticidade, nós vamos usar apenas números de pequena magnitude

Escolhendo os primos:

p = 11 e q = 13

Calculando n:

n = 11\cdot13 = 143

Calculando φ(n):

φ(143) = (11 - 1)\cdot(13 - 1) = 120

Escolhendo e tal que mdc(e, 120) = 1:

e = 7

Você pode conferir que de fato mdc(7, 120) = 1

Calculando d:

e \cdot d \equiv 1\;(mod\;φ(n)) \Rightarrow 7 \cdot d \equiv 1\;(mod\;120)

Usando algoritmo de Euclides para descobrir d:
120 = 7\cdot17 + 1
\Rightarrow 120\cdot1 + 7(-17) = 1
\Rightarrow 120(1-7) + 7(-17 + 120) = 1 (Se não entendeu este passo, não se preocupe)
\Rightarrow 120(-6) + 7\cdot103 = 1
d = 103

p	q	n	φ	e	d
11	13	143	120	7	103

Aplicando a criptografia em um bloco b de dados qualquer

b = 54\;\;(1 < 54 < 143 - 1)

b^e = 54^7

resto da divisão de 54^7 por 143: \;r = 76

C(b) = 76

Aplicando a descriptografia no bloco b criptografado

[C(b)]^d = 76^{103}

resto da divisão de 76^{103} por 143: \;r = 54

D(C(b)) = 54 = b

Isso é tudo, pessoal! Obrigado a todos que leram até aqui. Espero ter sido claro em minhas explicações.

Os conceitos matemáticos que usei aqui, como módulo, algoritmo de Euclides, etc, são vistos em uma disciplina chamada "Teoria dos Números". Caso queira se aprofundar, recomendo o livro do IMPA: Teoria dos Números - um passeio com primos e outros números familiares pelo mundo inteiro

Caso tenha gostado deste material, considere dar uma lida neste meu outro post também: Como um computador soma números? Clique aqui e entenda! [CIRCUITOS DIGITAIS].