Criptografia de chave assimétrica

Nesta lição vamos explorar a criptografia de chave assimétrica, que forma a base de muitas interações seguras em redes hoje em dia.

Ao final da lição, teremos coberto:

• O que é criptografia de chave assimétrica
• Usos da criptografia de chave assimétrica, incluindo troca de chaves e assinaturas digitais
• Segurança da criptografia de chave assimétrica em geral
• Mais detalhes sobre os algoritmos RSA, DSA e Curvas Elípticas e sua segurança
• Alguns exemplos de código Python mostrando como os algoritmos funcionam na prática
• Ameaças a esses algoritmos provenientes tanto de computadores clássicos quanto quânticos

Introdução à criptografia de chave assimétrica

Como aprendemos na última lição, a criptografia de chave simétrica é muito rápida e eficiente para proteger informações, mas tem algumas limitações:

1. À medida que o número de partes que desejam trocar informações com segurança aumenta, a quantidade de chaves necessárias cresce combinatorialmente. Não há mecanismo para distribuir essas chaves com segurança entre remetentes e destinatários.
2. Não há provisão para não-repúdio. Qualquer parte consegue decifrar ou cifrar mensagens sem nenhuma forma de garantir que uma mensagem foi recebida ou de onde ela se originou.

A solução para ambos os problemas é fornecida pela criptografia de chave assimétrica (AKC, do inglês asymmetric key cryptography), também conhecida como criptografia de chave pública (PKC, do inglês public key cryptography), que, portanto, forma um pilar da segurança digital moderna.

A criptografia de chave assimétrica (AKC) envolve o uso de um par de chaves — uma pública, uma privada. As chaves pública e privada são criptograficamente vinculadas e tipicamente geradas ao mesmo tempo como um par de chaves usando um algoritmo matemático especializado. A chave pública, como o nome sugere, deve ser distribuída livremente, enquanto a chave privada é mantida em segredo pela parte que gerou o par de chaves. A segurança das comunicações que empregam pares de chaves assimétricas é garantida enquanto a chave privada permanecer confidencial.

Figura 1. Cifração com chave assimétrica

A AKC oferece diversas funções úteis, como:

1. Cifração e decifração para garantir a confidencialidade das comunicações.
2. Assinaturas digitais para garantir autenticidade, integridade e não-repúdio.
3. Troca segura de chaves para facilitar o uso posterior de criptossistemas simétricos.

Em aplicações modernas, a AKC é usada principalmente para assinaturas digitais e troca segura de chaves. Nesta lição, apresentamos essas duas funções-chave e, em seguida, discutimos diversas variações de protocolos criptográficos para essas funções.

Troca de chaves com criptografia de chave assimétrica

Um dos problemas fundamentais em criptografia é a troca de chaves de forma segura. Por exemplo, se duas partes querem usar cifração simétrica, ambas precisam da mesma chave para cifrar e decifrar mensagens. Mas como elas trocam essa chave com segurança? A criptografia de chave assimétrica resolve isso por meio de mecanismos de troca de chaves interativos e não interativos.

Troca de chaves interativa

Um protocolo de troca de chaves interativo se refere a um método em que duas partes colaboram para criar uma chave de segredo compartilhado por um canal de comunicação inseguro. Essa chave de segredo compartilhado pode então ser usada para tarefas de cifração e decifração simétricas.

O mais conhecido entre esses protocolos é o algoritmo Diffie-Hellman (DH), criado especificamente para facilitar a troca de chaves. Neste protocolo, cada parte gera um par de chaves (pública e privada) e divulga sua chave pública. Em seguida, cada parte usa sua própria chave privada e a chave pública da outra parte para gerar uma chave de segredo compartilhado. O DH emprega os princípios da aritmética modular para garantir que ambas as partes terminem com o mesmo segredo compartilhado, mesmo que cada parte tenha acesso apenas à chave pública da outra.

Os criptossistemas modernos baseados em criptografia de curva elíptica (ECC) estendem esse conceito com o Diffie-Hellman de curva elíptica (ECDH). O ECDH funciona de forma semelhante ao DH, mas utiliza as propriedades das curvas elípticas, resultando em um sistema mais seguro e eficiente.

Figura 2. Protocolo de troca de chaves

Troca de chaves não interativa

Ao contrário dos protocolos de troca de chaves como DH e ECDH, que são interativos e exigem comunicação de ida e volta para decidir a chave simétrica, a AKC também oferece formas não interativas de estabelecer uma chave de segredo compartilhado. Nesses esquemas, uma parte gera um par de chaves (pública e privada) e compartilha a chave pública com a outra parte. Essa segunda parte então gera uma chave simétrica aleatória, a cifra com a chave pública recebida e a envia de volta para a primeira parte. A primeira parte usa sua chave privada para decifrar a mensagem recebida, obtendo assim a chave simétrica compartilhada. Esse esquema é não interativo no sentido em que a chave simétrica é determinada por uma parte e simplesmente comunicada com segurança à outra parte em forma cifrada.

Uma consideração importante na troca de chaves não interativa diz respeito à diferença de comprimento em bits entre a chave simétrica que as partes desejam trocar e os tamanhos de mensagem recomendados em AKC. Tipicamente, as chaves simétricas modernas têm entre 128 e 256 bits, enquanto os criptossistemas de chave assimétrica como o RSA trabalham com tamanhos de mensagem em torno de 1024 a 4096 bits. Portanto, ao usar a AKC para transmitir uma chave simétrica, ela deve ser codificada em uma mensagem mais longa de 1024 a 4096 bits por questões de segurança. Isso pode ser feito por duas abordagens:

• Troca de chaves baseada em padding: Nesta abordagem, a chave simétrica mais curta (128 a 256 bits) é gerada primeiro e, em seguida, um esquema de padding reversível previamente acordado, como o OAEP, é usado para incorporá-la em uma mensagem mais longa (1024 a 4096 bits). Essa mensagem mais longa é cifrada com a AKC e transmitida como texto cifrado. O destinatário primeiro decifra o texto cifrado e depois remove o padding para extrair a chave simétrica mais curta.

• Mecanismos de encapsulamento de chaves (KEMs): Com a troca de chaves baseada em KEM, um texto simples longo e aleatório (1024 a 4096 bits) é gerado primeiro, a partir do qual uma chave simétrica mais curta (128 a 256 bits) pode ser extraída usando uma função de derivação de chaves (KDF) acordada previamente. O texto simples mais longo é cifrado usando AKC e transmitido ao destinatário como texto cifrado. O destinatário decodifica o texto cifrado usando sua chave privada e, em seguida, usa a KDF para extrair a chave simétrica mais curta (128 a 256 bits). Criptossistemas populares como o RSA, com sua capacidade de cifrar dados diretamente, podem ser usados para implementar KEMs.

Figura 3. Mecanismo de Encapsulamento de Chaves

Assinaturas digitais com criptografia de chave assimétrica

As assinaturas digitais são outra aplicação poderosa da criptografia de chave assimétrica. Elas fornecem autenticação, integridade e não-repúdio, possibilitados pelo fato de que, na AKC, cada entidade possui chaves privadas únicas. A ideia básica por trás dos protocolos de assinatura é que os remetentes de mensagens seguras irão adicionalmente assinar digitalmente as mensagens usando sua chave privada exclusiva. O receptor irá então verificar a assinatura digital usando a chave pública do remetente. Na AKC, as assinaturas digitais podem ser implementadas usando algoritmos projetados especificamente para esse fim ou usando criptossistemas genéricos.

Figura 4. Assinaturas digitais com criptografia de chave assimétrica

Algoritmos de assinatura digital dedicados

Atualmente, o padrão federal dos EUA para processamento de informações (FIPS) para assinaturas digitais é um esquema dedicado simplesmente intitulado Algoritmo de Assinatura Digital (DSA). De forma um tanto similar ao protocolo Diffie-Hellman, o DSA usa as propriedades algébricas da exponenciação modular e dos inversos multiplicativos para geração e verificação de assinaturas.

O algoritmo de assinatura digital de curva elíptica (ECDSA) é uma variante do DSA baseada em ECC, oferecendo a mesma funcionalidade, mas com chaves significativamente mais curtas. Isso resulta em eficiência melhorada, tornando-o uma escolha popular para sistemas com restrições de recursos.

Tanto o DSA quanto o ECDSA serão ilustrados com mais detalhes mais adiante.

Esquemas de assinatura digital usando criptossistemas genéricos

Além de algoritmos dedicados, assinaturas digitais também podem ser geradas usando criptossistemas assimétricos genéricos, como o RSA.

O RSA, que será discutido em detalhes em uma seção posterior, também explora inversos multiplicativos modulares e exponenciação modular como operações fundamentais, mas as combina em uma sequência diferente do DSA. No RSA, o assinante tipicamente cria um hash da mensagem e depois cifra o hash com sua chave privada, criando a assinatura digital. Qualquer parte pode então verificar essa assinatura decifrando-a com a chave pública do assinante e comparando com a mensagem hasheada.

Aplicações da criptografia de chave assimétrica

A criptografia de chave assimétrica é ubíqua nas aplicações de tecnologia digital modernas. As funcionalidades básicas da AKC descritas acima formam os blocos de construção de muitos protocolos de aplicação de nível superior, incluindo:

1. Comunicação pela internet: A comunicação segura pela internet, como HTTPS, depende fortemente da criptografia de chave assimétrica. O Transport Layer Security (TLS) e seu predecessor, o Secure Sockets Layer (SSL), usam criptografia de chave assimétrica durante o processo de handshake inicial para estabelecer uma chave simétrica, que é então usada no restante da sessão de comunicação.

2. Autenticação: A criptografia de chave assimétrica é usada para criar assinaturas digitais, permitindo que uma entidade autentique um documento ou mensagem digital como proveniente de um remetente específico. Isso é usado em muitos cenários, desde a verificação de atualizações de software até contratos digitais legalmente vinculantes.

3. Cifração de e-mail: Protocolos de cifração de e-mail como PGP (Pretty Good Privacy) e sua alternativa de código aberto GPG (GNU Privacy Guard) usam criptografia de chave assimétrica para garantir que apenas o destinatário pretendido possa ler o conteúdo do e-mail.

4. Shell seguro (SSH): O SSH é um protocolo para login remoto seguro e outros serviços de rede seguros sobre uma rede insegura. Ele usa criptografia de chave assimétrica para autenticar o servidor perante o cliente e, opcionalmente, o cliente perante o servidor.

5. VPN (rede privada virtual): A cifração de chave assimétrica é usada para estabelecer conexões seguras em VPNs, garantindo comunicação segura sobre redes públicas.

6. Blockchain e criptomoedas: Tecnologias blockchain, incluindo Bitcoin e Ethereum, usam criptografia de chave assimétrica. Por exemplo, a propriedade de Bitcoin é estabelecida por meio de assinaturas digitais usando criptografia de chave assimétrica.

7. Autoridades certificadoras: A criptografia de chave assimétrica é usada por autoridades certificadoras (ACs) para emitir e assinar certificados digitais, que são usados em comunicação TLS, assinatura de código, cifração de e-mail e muito mais. Um certificado digital vincula uma chave pública a uma entidade específica (por exemplo, uma pessoa ou servidor).

Figura 5. Emissão e assinatura de certificados digitais usando criptografia de chave assimétrica

Segurança da criptografia de chave assimétrica

Vários conceitos criptográficos se combinam para possibilitar a criptografia de chave assimétrica segura, incluindo:

Sigilo da chave privada: O requisito de segurança mais básico da AKC é que a chave privada permaneça secreta. No entanto, como a chave privada deve ser matematicamente vinculada à chave pública, o sigilo da chave privada também exige que seja computacionalmente inviável derivar a chave privada a partir do conhecimento da chave pública. Os esquemas de geração de chaves na AKC dependem de problemas matemáticos computacionalmente difíceis para facilitar esse requisito.

Funcionalidade de alçapão: Na AKC, as operações de cifração e decifração envolvem chaves complementares diferentes de um único par de chaves. O texto cifrado gerado pela cifração usando uma das chaves (por exemplo, a chave pública) deve ser indecifrável para terceiros, mas facilmente decifrável pelo detentor da chave complementar (neste caso, a chave privada). Em outras palavras, a cifração deve se assemelhar a uma função de mão única com alçapão, de forma que terceiros não consigam inverter a operação e recuperar o texto simples, mas a chave privada fornece um alçapão secreto que permite inversão fácil. Algoritmos populares de AKC usam exponenciação modular para configurar o comportamento de função de mão única com alçapão.

Aleatoriedade: O processo de geração de chaves também deve explorar a aleatoriedade para garantir que as chaves sejam imprevisíveis, pois qualquer padrão ou previsibilidade na geração de chaves pode ser explorado por um atacante. A aleatoriedade também é usada para padding durante a cifração para gerar textos cifrados semanticamente seguros e dentro de esquemas de assinatura digital para produzir assinaturas únicas, mesmo quando a mesma mensagem é assinada várias vezes. Por essa razão, o uso de geradores de números aleatórios robustos é uma parte importante da AKC.

Tamanho de chave grande: Assim como no caso da SKC, tamanhos de chave grandes garantem proteção contra ataques de força bruta. No entanto, como tamanhos de chave grandes também aumentam o custo computacional do processo de cifração e decifração, uma solução ideal precisa equilibrar considerações de segurança e eficiência. A tabela a seguir mostra os tamanhos de chave típicos para vários protocolos e aplicações de criptografia de chave assimétrica:

Protocolo	Tamanhos de Chave Típicos (em bits)	Aplicação
RSA	1024 (obsoleto), 2048, 3072, 4096	Cifração, assinaturas digitais
DSA	1024 (obsoleto), 2048, 3072	Assinaturas digitais
DH	2048, 3072, 4096	Troca de chaves
ECDH	224, 256, 384, 521	Troca de chaves
ECDSA	224, 256, 384, 521	Assinaturas digitais

Infraestrutura de chave pública: Na AKC, as chaves privadas devem ser mantidas em segredo pelos proprietários, enquanto as chaves públicas são compartilhadas. É necessário um mecanismo seguro para gerenciar e distribuir essas chaves públicas entre os usuários. A infraestrutura de chave pública (PKI) fornece uma maneira de fazer isso usando certificados digitais. Um certificado digital comprova a identidade do proprietário da chave pública e é emitido por uma autoridade confiável, como uma autoridade certificadora (que faz parte de uma PKI). Portanto, a PKI desempenha um papel integral na segurança de aplicações modernas que usam AKC, ao possibilitar o gerenciamento de chaves em larga escala (criando, gerenciando, distribuindo e revogando certificados digitais).

Riscos de segurança para a criptografia de chave assimétrica

Conforme indicado na tabela acima, algoritmos de chave assimétrica modernos, como o RSA, tipicamente empregam tamanhos de chave muito maiores do que os equivalentes de chave simétrica comumente usados, como o AES-128. Mesmo os protocolos baseados em ECC (ECDH e ECDSA) que têm tamanhos de chave menores empregam um mínimo de pelo menos 224 bits para chaves. Isso implica que um ataque de força bruta envolvendo uma busca exaustiva no espaço de chaves privadas para identificar a chave correta é computacionalmente intratável no futuro previsível. Isso permanece verdadeiro mesmo se computadores quânticos fossem implantados para essa tarefa. Portanto, ataques contra a AKC geralmente se concentram em explorar outras potenciais fraquezas de criptossistemas específicos. Alguns modos de ataque bem documentados têm como alvo:

1. Fraqueza algorítmica usando meios matemáticos e computacionais sofisticados para minar as suposições de dificuldade usadas para formular algoritmos de chave assimétrica. Por exemplo, a segurança do RSA é fundamentada na dificuldade de fatorar grandes números primos, e avanços computacionais recentes permitiram a fatoração bem-sucedida de chaves RSA de 829 bits. Portanto, o RSA de 1024 bits está atualmente obsoleto. Como será discutido mais tarde, o principal risco representado pelos computadores quânticos à AKC também se enquadra nessa categoria.

2. Aleatoriedade imperfeita, que pode levar a fraquezas no processo de geração de chaves. Por exemplo, se o gerador de números aleatórios usado para criar as chaves for falho e gerar chaves que não são verdadeiramente aleatórias, um atacante pode ser capaz de prever as chaves.

3. Falhas de implementação, como erros na implementação de algoritmos criptográficos que inadvertidamente revelam informações sobre as chaves. Por exemplo, padding incorreto pode potencialmente revelar detalhes sobre as chaves.

4. Canais laterais que se referem ao vazamento de informações do sistema físico que realiza a criptografia. Esses vazamentos podem ser na forma de informações de temporização, consumo de energia ou até mesmo som, que podem ser explorados em um chamado ataque de canal lateral. Por exemplo, analisar quanto tempo as operações criptográficas levam para executar pode revelar o número de '1's em uma chave binária. Esse vazamento aparentemente inocente reduz significativamente o espaço de busca, revelando possíveis soluções para problemas que inicialmente pareciam intransponíveis.

5. Troca de chaves interceptando chaves enquanto estão sendo trocadas, como dentro de um ataque de homem no meio (MITM). O protocolo DH é suscetível a ataques MITM se etapas adicionais de autenticação não forem incorporadas.

6. Armazenamento de chaves, com o objetivo de roubar chaves de armazenamentos com segurança precária. Isso inclui ataques físicos como manipulação ou roubo de dispositivos de armazenamento.

Proteger os criptossistemas de chave assimétrica contra a variedade de ataques possíveis é, portanto, uma tarefa significativa envolvendo considerações matemáticas, de hardware, software, logísticas e jurídicas.

RSA

O algoritmo RSA (Rivest-Shamir-Adleman) é um dos primeiros criptossistemas de chave pública e é amplamente usado para transmissão segura de dados. É um criptossistema versátil no sentido de que fornece as operações necessárias para possibilitar cifração, decifração, assinaturas digitais e troca de chaves dentro de uma estrutura comum.

Nesta seção, vamos ilustrar a criptografia de chave assimétrica (AKC) usando RSA por meio de exemplos simples.

Vamos usar o cenário padrão de duas partes, Alice e Bob, que desejam se comunicar com segurança usando AKC.

O algoritmo RSA

O algoritmo RSA básico envolve quatro operações: geração de chaves, distribuição de chaves, cifração e decifração:

1. Geração de chaves:

   As chaves pública e privada são geradas com base em princípios matemáticos relacionados a números primos, onde calculá-los é fácil, mas o processo inverso é difícil.

   Vamos nos referir a elas como:

   • Chave pública: $(e, n)$
   • Chave privada: $(d, n)$

   Observe que $n$ é comum tanto à chave pública quanto à chave privada, e é conhecido como módulo. Vamos precisar usar isso mais tarde.

Detalhes matemáticos

• Escolha dois números primos distintos, $p$ e $q$.
  • Escolhidos aleatoriamente (por segurança).
  • Eles devem ter magnitude similar, mas diferir no comprimento por alguns dígitos, para tornar a fatoração mais difícil.
  • Números primos podem ser escolhidos eficientemente usando um teste de primalidade.
• Compute $n = p*q$.
  • $n$ é o módulo tanto para a chave pública quanto para a chave privada.
• Compute a função totiente $φ$$(n) = (p-1)*(q-1)$.
  • O totiente deve ser mantido em segredo e tipicamente descartado após a geração de chaves.
• Escolha um inteiro $e$ tal que $1 < e <$$φ$$(n)$ e $gcd$$(e,$$φ$$(n)) = 1$.
  • Ou seja, $e$ e $φ$$(n)$ devem ser coprimos.
  • Esse número $e$ forma o expoente da chave pública e é tipicamente escolhido como um número pequeno para eficiência computacional.
  • O número primo $65537 = 2^{16} + 1$ é frequentemente usado.
  • Compute $d$ para satisfazer a relação de congruência $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • Ou seja, $d$ é o inverso multiplicativo de $e$ módulo $φ$$(n)$.
    • Isso é computado de forma mais eficiente usando o algoritmo euclidiano estendido.
    • Esse número $d$ é o expoente da chave privada.
• A chave pública consiste em $(e, n)$, e a chave privada é $(d, n)$.

2. Distribuição de chaves:

   • A chave pública $(e, n)$ é tornada pública para aqueles que podem querer enviar uma mensagem.
   • A chave privada $(d, n)$ é mantida em segredo.

3. Cifração:

   • Alice deseja enviar uma mensagem $M$ para Bob. Neste caso, um simples inteiro.
   • Alice usa a chave pública de Bob $(e, n)$ para cifrar a mensagem em texto cifrado $C$.

   Detalhes matemáticos

   • $M$ é um inteiro $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, onde $C$ é o texto cifrado.

4. Decifração:

   • Bob recebe o texto cifrado $C$.
   • Bob usa sua chave privada $(d, n)$ para decifrar a mensagem de volta para a mensagem $M$.

   Detalhes matemáticos

   • $M ≡ C^d (mod n)$.

Este é o esboço básico do RSA. Na prática, esquemas de padding mais sofisticados são aplicados ao texto simples $M$ antes da cifração para garantir que textos simples iguais resultem em textos cifrados diferentes. Isso evita uma série de possíveis ataques contra implementações ingênuas do RSA e possibilita a segurança semântica.

Ilustração do RSA em Python

Nas células de código a seguir, ilustramos um exemplo simples do algoritmo RSA usando inteiros pequenos e depois demonstramos aplicações práticas de distribuição de chaves e assinatura digital usando bibliotecas Python que implementam RSA.

nota

Nota: Nesta seção vamos mostrar os cálculos matemáticos em detalhes como parte do código Python.

Geração de chaves RSA

Vamos percorrer passo a passo uma instância simples do algoritmo RSA usando números primos pequenos.

Vamos precisar ser capazes de computar o máximo divisor comum de dois inteiros, pois isso será necessário para testar se dois inteiros são coprimos.

Vamos explicar uma forma simples de calcular isso, mas é muito mais eficiente com inteiros maiores usar a função Python math.gcd.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

A primeira fase do fluxo de trabalho do RSA é a geração de chaves. Isso é iniciado pela escolha de dois números primos, que devem ser mantidos em segredo pela entidade que está gerando as chaves.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Em seguida, o módulo $n$, que é simplesmente o produto dos dois primos escolhidos, é computado. Esse módulo será publicado como parte da chave pública.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

A função totiente de Euler $\varphi(n)$ é computada em seguida, pois é necessária para a operação de inverso multiplicativo modular usada para determinar as chaves no RSA. $phi$ também é mantido em segredo e tipicamente descartado após a geração de chaves.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Agora estamos prontos para calcular as chaves pública e privada. No RSA, cada uma delas é especificada por uma tupla de dois inteiros. A primeira entrada em cada tupla é um inteiro distinto, e a segunda entrada é o módulo $n$ que é comum a ambas as chaves.

A primeira entrada na chave pública pode ser qualquer inteiro maior que 1 que seja coprimo com $phi$. Dois inteiros são coprimos se seu máximo divisor comum é 1. Portanto, usamos a função math.gcd para encontrar um inteiro $e$ coprimo com $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

A chave privada requer um inteiro $d$, que é o inverso multiplicativo de $e$ módulo $phi$; ou seja, satisfaz a relação de congruência $d*e\equiv 1 \pmod{\varphi(n)}$. Para esta ilustração simples onde estamos lidando com inteiros pequenos, podemos simplesmente percorrer os inteiros positivos para localizar um $d$ adequado. Em situações reais, o eficiente algoritmo euclidiano estendido é usado para esse fim.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Agora formamos as tuplas $(e, n), (d, n)$, que formam as chaves pública e privada respectivamente. A chave pública é então publicada, enquanto a chave privada é mantida em segredo.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

A cifração e decifração no RSA usam a operação de exponenciação modular. Além disso, as chaves pública e privada são complementares, de forma que qualquer uma pode ser usada para cifrar uma mensagem que a outra pode decifrar.

Aqui ilustramos o caso em que a chave pública $(e,n)$ é usada para cifração e a chave privada $(d, n)$ é usada para decifração, definindo uma função Python para cada operação.

Em seguida, ciframos e deciframos uma mensagem inteira $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Embora os inteiros pequenos usados acima sejam úteis para esboçar facilmente as ideias centrais do algoritmo RSA, em aplicações reais o RSA requer o uso de inteiros muito grandes. Por exemplo, o RSA de 2048 bits envolve o uso de um módulo $n$ de 2048 bits, cujos equivalentes em inteiros decimais estão em torno de 10$^{616}$. Esses números verdadeiramente enormes são necessários para a segurança prática do RSA.

Troca de chave simétrica com RSA

Como discutido anteriormente, a AKC permite que duas partes que desejam se comunicar estabeleçam de forma segura um segredo compartilhado, que pode ser usado, por exemplo, como chave secreta para cifração simétrica subsequente de texto simples em massa.

Vamos considerar o seguinte cenário. Alice e Bob querem usar a SKC para cifrar e decifrar mensagens. No entanto, antes que esse processo possa ser inicializado, eles precisam concordar com uma chave secreta comum. Uma opção é para uma das partes — digamos Alice — gerar uma chave secreta e depois transmiti-la com segurança para Bob. Para realizar essa transferência segura, Alice decide usar o RSA como o mecanismo de encapsulamento de chaves (KEM).

Isso envolve as seguintes etapas:

• Primeiro, Alice gera uma chave simétrica aleatória que ela pretende compartilhar com Bob.
• Em seguida, Bob gera um par de chaves assimétricas e torna sua chave pública disponível em um canal adequado.
• A seguir, Alice usa a chave pública de Bob para cifrar a chave simétrica, encapsulando-a em um texto cifrado.
• Então, Alice transmite o texto cifrado por um canal confiável, mas não necessariamente seguro.
• Por fim, Bob recebe o texto cifrado e o decifra usando sua chave privada. Ele agora tem acesso à chave simétrica gerada por Alice.

Figura 1. Troca de chave simétrica com RSA

Exemplo de troca de chaves baseada em padding em Python

Um fluxo de trabalho prático utilizando RSA para troca de chaves não interativa baseada em padding é agora ilustrado usando a biblioteca Python cryptography.

Importe os módulos necessários da biblioteca Python cryptography. Se necessário, essa biblioteca pode ser instalada usando o comando pip install cryptography.

Alice então gera uma chave secreta aleatória, que ela pretende transmitir para Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Usando o módulo rsa da biblioteca cryptography, Bob gera um par de chaves e depois transmite sua chave pública. Qualquer um pode interceptar a chave pública e ler os números públicos $(e,n)$ que formam a chave.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

Neste ponto, assumimos que Alice recebeu a chave pública transmitida por Bob. A symmetric_key de Alice acima agora pode ser cifrada usando a chave pública de Bob para produzir o texto cifrado. Em uma situação realista, Alice também usará métodos de padding adicionais como o OAEP para garantir a segurança semântica de suas comunicações com Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice então transmite o texto cifrado por um canal aberto, confiante de que apenas Bob com a chave privada correspondente será capaz de decifrá-lo. Assumimos que Bob recebeu o texto cifrado e agora pode decifrá-lo usando sua chave privada confidencial.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

Neste ponto, Alice e Bob têm acesso à chave simétrica secreta, que podem usar para aplicações de SKC.

Simulando um Mecanismo de Encapsulamento de Chaves com RSA em Python

No fluxo de trabalho a seguir, ilustramos o uso do RSA para simular um Mecanismo de Encapsulamento de Chaves (KEM), pelo qual uma mensagem secreta aleatória suficientemente longa é trocada com segurança e subsequentemente convertida em um segredo compartilhado do comprimento apropriado usando uma KDF.

Mais uma vez, Alice e Bob querem estabelecer um segredo compartilhado de forma não interativa, e Alice é a parte que decide qual segredo usar.

Começamos importando algumas bibliotecas Python necessárias.

Bob então gera seu par de chaves RSA e transmite sua chave pública.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice primeiro gera um segredo aleatório longo a partir do qual o segredo compartilhado será eventualmente derivado. Em um KEM puro, o segredo longo seria um elemento aleatório da estrutura algébrica subjacente ao criptossistema. No caso do RSA de 2048 bits, isso seria um inteiro aleatório módulo o módulo RSA de 2048 bits. Como um KEM puro não requer padding adicional, mas neste exemplo estamos apenas simulando um KEM usando RSA e a biblioteca cryptography requer o uso de padding ao cifrar com RSA, usaremos um segredo longo um pouco mais curto que, no entanto, é muito mais longo do que uma chave AES padrão de 256 bits.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Em seguida, Alice cifra o segredo longo usando a chave pública de Bob e o segredo cifrado é comunicado a Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob decifra o segredo cifrado recebido de Alice usando sua chave privada.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Finalmente, tanto Alice quanto Bob aplicam separadamente uma Função de Derivação de Chaves (KDF) acordada sobre o segredo longo para derivar a chave simétrica.

Observe que o processo envolve um protocolo de hash e o uso de um sal aleatório que garante unicidade e imprevisibilidade da chave simétrica compartilhada caso o segredo longo seja reutilizado (não recomendado). No entanto, o próprio sal não precisa ser secreto e, uma vez gerado aleatoriamente — digamos por Alice neste exemplo —, pode ser transmitido para Bob junto com o segredo longo cifrado.

Vamos assumir, portanto, que tanto Alice quanto Bob têm acesso ao mesmo sal aleatório.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Assinaturas digitais com RSA

Vamos agora estender o cenário de comunicação confidencial acima com Alice e Bob para um que também inclua validação com a ajuda de uma assinatura digital.

Como antes, Alice vai enviar confidencialmente a Bob uma mensagem encapsulando uma chave simétrica, mas ela também vai assinar digitalmente a mensagem para que Bob, ao recebê-la, possa verificar que foi Alice quem a originou e que o conteúdo da mensagem não foi adulterado durante a transmissão.

De forma mais geral, é desejável possibilitar a validação sem comprometer a confidencialidade, de modo que qualquer parte interessada seja capaz de verificar a integridade, autenticidade, e estabelecer o não-repúdio em relação a uma dada comunicação, mesmo que essa parte não tenha acesso à mensagem de texto simples real.

Vamos considerar essa configuração geral que então envolve as seguintes etapas:

• Primeiro, tanto Bob quanto Alice tornam suas chaves públicas disponíveis por um canal aberto.
• Em seguida, Alice cifra o texto simples usando a chave pública de Bob, criando um texto cifrado.
• A seguir, Alice cria um hash do texto cifrado com uma função hash e cifra o hash resultante usando sua chave privada. Esse hash cifrado é a assinatura.
• Então, Alice transmite tanto o texto cifrado quanto a assinatura por um canal aberto.
• Em seguida, Bob usa a chave pública de Alice para decifrar a assinatura, revelando o hash do texto cifrado.
• A seguir, como Bob também tem acesso ao próprio texto cifrado, ele usa a mesma função hash usada por Alice para recriar uma segunda instância do hash do texto cifrado. Se esta última corresponder à obtida ao decifrar a assinatura de Alice, então a mensagem está validada, mesmo que o próprio texto cifrado ainda não tenha sido decifrado.
• Por fim, Bob, tendo validado a mensagem, decifra o texto cifrado usando sua própria chave privada.

Figura 2. Assinaturas digitais com RSA

Este fluxo de trabalho para uma assinatura digital é ilustrado a seguir.

Importamos novamente alguns módulos úteis da biblioteca cryptography. Como antes, Alice pretende enviar com segurança uma chave simétrica para Bob, mas ela também deseja assiná-la digitalmente. Neste caso, precisamos de chaves públicas tanto de Alice quanto de Bob. Portanto, o primeiro passo é para que tanto Alice quanto Bob criem seu próprio par de chaves usando RSA e transmitam sua própria chave pública para o mundo.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

No próximo passo, como antes, Alice usa a chave pública de Bob para cifrar a chave simétrica e prepara o texto cifrado.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

Nesta etapa, em vez de apenas transmitir o texto cifrado, Alice pretende anexar uma assinatura digital a ele para que possa provar a Bob que ela foi a remetente da mensagem. Isso é feito em duas etapas:

1. Criar um hash do texto cifrado usando um algoritmo de hashing.
2. Cifrar o hash usando a chave privada de Alice, o que equivale a uma assinatura.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice então transmite o texto cifrado e a assinatura por uma rede para que Bob possa interceptar ambos.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Do lado de Bob, a primeira tarefa é verificar a integridade e autenticidade do texto cifrado. Para fazer isso, Bob cria um hash do texto cifrado recebido usando o mesmo algoritmo de hashing usado por Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Em seguida, Bob decifra a assinatura recebida usando a chave pública de Alice. Como Alice usou sua chave privada para criar a assinatura, Bob consegue decifrá-la usando a chave pública de Alice. A assinatura decifrada nada mais é do que um hash do texto cifrado criado do lado de Alice. Se o hash criado por Bob corresponder à assinatura decifrada, então Bob verificou que o texto cifrado que recebeu não foi adulterado e que foi Alice quem assinou o texto cifrado.

No código Python abaixo, essas operações são combinadas em uma função utilitária chamada verify fornecida por um objeto associado à chave pública de Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Tendo verificado a integridade e autenticidade do texto cifrado recebido, Bob pode então decifrá-lo usando sua chave privada, porque Alice criou o texto cifrado usando a chave pública de Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

No cenário de assinatura digital acima, qualquer parte — não apenas Bob — pode verificar que Alice é a remetente do texto cifrado porque todos podem acessar a chave pública de Alice, o texto cifrado e a assinatura digital. Além disso, após enviar o texto cifrado e a assinatura, Alice não pode negar tê-lo feito, pois a assinatura pode ser decifrada para um hash significativo usando apenas sua chave pública. Isso estabelece o não-repúdio.

Ao possibilitar a distribuição segura de chaves e apoiar o não-repúdio, a criptografia de chave pública estabelece uma base sólida para a comunicação digital segura.

Quebrando o RSA

A utilidade e a segurança do algoritmo RSA descritos acima dependem de duas premissas matemáticas:

1. Encontrar o inverso multiplicativo modular $d$ tendo acesso apenas a $(e, n)$ é computacionalmente inviável.

2. No contexto do RSA, a operação de exponenciação modular se comporta como uma função trapdoor unidirecional. Quando usada para criptografia, ela produz um texto cifrado ininteligível e, sem acesso à chave privada, inverter a operação para recuperar o texto puro a partir do texto cifrado não é viável. No entanto, com acesso à chave privada, que age como uma trapdoor, o texto cifrado pode ser facilmente decifrado.

O ataque mais proeminente ao algoritmo RSA tem como objetivo minar a premissa 1, recuperando com eficiência o número da chave privada $d$ por meio da fatoração do módulo $n$. Como será ilustrado a seguir, é fácil recuperar $d$ se tivermos acesso aos fatores primos $p$ e $q$ de $n$ ou ao totiente $φ$$(n)$. Lembre-se de que $p$, $q$ e $φ$$(n)$ são mantidos em segredo durante a geração das chaves e descartados depois. Um terceiro que recupere essas informações usando um computador clássico ou quântico essencialmente descobre a chave privada, quebrando o RSA. Portanto, a fatoração de primos é o primitivo computacional fundamental necessário para quebrar o RSA.

Computação clássica e RSA

A fatoração de inteiros grandes é conhecida por exibir escalabilidade super-polinomial ou subexponencial em computadores clássicos. O melhor algoritmo clássico conhecido para fatorar inteiros maiores que $10^{100}$ é o peneira geral do corpo de números (GNFS)

Detalhe matemático

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

como função do inteiro $n$ a ser fatorado.

Essa escala é super-polinomial no número de bits necessários para representar $n$.

Portanto, a fatoração de primos é considerada ineficiente em computadores clássicos.

Atualmente, os maiores inteiros fatorados em hardware clássico estão na faixa de 829 bits ou 250 dígitos decimais. Dado o crescimento exponencial no poder da computação clássica que foi testemunhado nas últimas décadas, o RSA de 1024 bits não é mais considerado seguro no curto prazo e está atualmente obsoleto. No entanto, no futuro previsível, a fatoração de inteiros de 2048 bits com magnitude na faixa de $10^{617}$ é atualmente considerada inviável em sistemas clássicos, sugerindo viabilidade contínua. O advento dos computadores quânticos, porém, invalida essa avaliação.

Algoritmo quântico de Shor e o RSA

Provavelmente o algoritmo quântico mais conhecido hoje é o algoritmo de Shor para encontrar os fatores primos de inteiros. Quando introduzido por Peter Shor em 1994, foi reconhecido como o primeiro algoritmo quântico que oferecia uma aceleração super-polinomial em relação aos algoritmos clássicos em um problema de grande importância prática: a fatoração de primos.

O algoritmo de Shor pode fatorar primos com $O(n^2)$, onde $n$ é o número de bits.

Explicação matemática do algoritmo de Shor

No contexto do RSA, o algoritmo de Shor funciona explorando a periodicidade da função exponencial modular $f(x) = a^x (mod~n)$ e fornece um primitivo quântico de encontrar período que permite a fatoração eficiente de primos do módulo $n$.

Um esboço simplificado de alto nível do esquema geral de Shor para quebrar o RSA é o seguinte:

1. Dado o módulo $n$, publicado como parte da chave pública, escolha um número $a$ coprimo a $n$, ou seja, $gcd(a,n) = 1$. Como sabemos que $n = p*q$ tem exatamente dois fatores primos $(p, q)$, quase qualquer número menor que $n$ escolhido aleatoriamente provavelmente será coprimo a $n$.

2. Tendo escolhido $a$, encontre o expoente $r$ tal que $a^r \equiv 1 (mod~n)$. Isso implica $a^r - 1 \equiv 0 (mod~n)$. A existência de um expoente $r$ tal que a congruência acima se mantém é garantida pela propriedade de periodicidade da exponenciação modular.

3. Se $r$ for par, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ para algum inteiro $\gamma$. O lado esquerdo dessa última igualdade deve conter $p$ e $q$ como dois de seus fatores primos, já que o lado direito também os contém. Se $r$ for ímpar, volte ao passo 1 e tente uma escolha diferente de $a$.

4. Use o algoritmo de Euclides estendido para encontrar $gcd((a^{r/2} - 1), n)$ ou $gcd((a^{r/2} + 1), n)$. O MDC calculado provavelmente identificará um dos fatores primos $p$ ou $q$. Divida $n$ por esse fator primo para recuperar o outro.

5. Conhecidos $p, q$, use os passos do algoritmo RSA original para reconstruir o totiente $\phi(n)$ e gerar o número da chave privada $d$ como o inverso modular do número de chave pública conhecido $e$.

Em agosto de 2023, Oded Regev publicou uma melhoria em relação ao original de Shor, usando uma abordagem multidimensional que resultou em $O(n^{1.5})$. Continuam a existir pesquisas nessa área, incluindo a de Ragavan e Vaikuntanathan, que pode melhorar o tempo, o custo ou o número de qubits necessários. Embora não seja possível dizer quando a execução desses algoritmos contra a criptografia RSA do mundo real se tornará verdadeiramente viável, isso está cada vez mais próximo.

Exemplo em Python demonstrando como quebrar a criptografia RSA

Nas células de código a seguir, ilustramos um exemplo de como encontrar uma chave privada tendo acesso apenas à chave pública. Isso usará computação clássica de força bruta, mas mostra como o algoritmo de Shor poderia ser usado — inclusive com chaves grandes.

nota

Nesta seção, mostraremos os cálculos matemáticos em detalhes como parte do código Python.

No exemplo, temos uma chave pública $(5, 247)$ e iremos recuperar a chave privada.

Passo 1: O primeiro passo é escolher um número coprimo a 247. Quase qualquer número que tentarmos vai funcionar. Vamos escolher 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Passo 2: Em seguida, precisamos encontrar o período $r$ tal que $6^r \equiv 1 (mod~247)$. Neste exemplo, calculamos $r$ classicamente por força bruta, mas também poderíamos usar o algoritmo de Shor em um computador quântico usando o Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Passo 3: Como o período $r = 36$ é par, podemos calcular $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Passo 4: Encontre o MDC de qualquer um desses fatores com $n$. Simplesmente divida $n$ pelo fator primo já encontrado para obter o segundo fator primo.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Passo 5: Tendo recuperado os fatores primos de $n = 247$ como $p_{found}=13$ e $q_{found}=19$, calculamos o totiente $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

A chave privada é o inverso modular do número de chave pública $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

No esquema acima, o passo 2 é a operação crucial de encontrar o período, para a qual o algoritmo de Shor usa dois primitivos quânticos fundamentais: a transformada de Fourier quântica e a estimativa de fase quântica. Para uma explicação detalhada dos aspectos quânticos do algoritmo de Shor, veja a lição sobre estimativa de fase e fatoração em Fundamentos de Algoritmos Quânticos. Os passos 1 e de 3 a 5 envolvem operações relativamente baratas que podem ser facilmente executadas em computadores clássicos.

Opcionalmente, aqui está um tutorial visual detalhado da implementação do algoritmo de Shor.

Em computadores quânticos, o algoritmo de Shor pode exibir escalabilidade poliogarítmica tão favorável quanto $O((log~n)^2 (log~log~n))$ em termos do módulo $n$, ou escalabilidade polinomial em termos do número de bits necessários para representar $n$. Isso é uma aceleração super-polinomial em comparação ao algoritmo GNFS clássico.

Estimativas recentes de recursos indicam que, com base em certas suposições sobre a configuração do hardware, dezenas de milhares a vários milhões de qubits serão necessários para quebrar o RSA de 2048 bits usando o algoritmo de Shor. Não é inconcebível que computadores quânticos com dezenas de milhares de qubits se tornem disponíveis nos próximos anos, tornando a extremidade inferior da estimativa de recursos acessível.

Troca de chaves Diffie-Hellman e o Algoritmo de Assinatura Digital

Na seção anterior, discutimos o criptossistema RSA, cuja segurança se baseia na dificuldade computacional da fatoração de primos. Aqui, discutiremos dois protocolos populares de criptografia assimétrica: a troca de chaves Diffie-Hellman (DH) e o Algoritmo de Assinatura Digital (DSA), ambos baseados em um problema matemático diferente: o problema do logaritmo discreto (DLP).

O problema do logaritmo discreto

Na equação a seguir, precisamos encontrar $a$ tendo apenas $e$, $M$, $c$:

$a^e$ $mod$ $M = c$

Acredita-se que isso seja difícil com computadores clássicos devido ao uso da aritmética modular e, portanto, é uma boa base matemática para um algoritmo de criptografia.

Isso é conhecido como o problema do logaritmo discreto (DLP).

Detalhes matemáticos do problema do logaritmo discreto

O DLP é tipicamente formulado no contexto de grupos cíclicos e é enunciado da seguinte forma.

Considere um grupo cíclico $G$ gerado por um elemento $g \in G$ e, dado um elemento arbitrário $h \in G$, encontre um inteiro $k$ tal que $h = g^{k}$.

Aqui o inteiro $k \equiv log_{g}h$ é o logaritmo discreto. A propriedade cíclica de $G$ garante que, para todo $h$, existe um inteiro $k$ válido.

Para criptografia, o DLP no grupo multiplicativo de inteiros módulo um número primo $p$, denotado $(\mathbb{Z}_p)^{\times}$, é bastante útil. Os elementos de $(\mathbb{Z}_p)^{\times}$ são classes de congruência rotuladas por inteiros módulo $p$ que são coprimos a $p$.

Por exemplo:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{e}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

A operação de multiplicação $(\times)$ nesses grupos é simplesmente a multiplicação inteira ordinária seguida de redução módulo $p$, e a exponenciação por um inteiro $k$ é apenas a multiplicação repetida $k$ vezes e a redução módulo $p$.

Vamos ilustrar uma instância do DLP em $(\mathbb{Z}_7)^{\times}$.

Esse grupo multiplicativo tem dois geradores $\{[3],[5]\}$, também conhecidos como raízes primitivas. Usaremos $[5]$ como gerador; ou seja, geraremos cada elemento de $(\mathbb{Z}_7)^{\times}$ usando potências inteiras sucessivas de 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Vemos que, na aritmética módulo 7, elevar 5 a potências inteiras sucessivas gera cada elemento de $(\mathbb{Z}_7)^{\times}$ exatamente uma vez antes que o ciclo se repita indefinidamente com período $p-1 = 6$.

Portanto, o DLP em $(\mathbb{Z}_7)^{\times}$ com gerador [5] é:

$\mathrm{Dado}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, encontre~} k \mathrm{~tal~que~} 5^{k} \equiv h~(mod~7)$.

A partir da saída da célula Python acima, vemos que:

$h = 2 \implies k=4 \mathrm{~ou~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~ou~} 3 = log_5(6) (mod~7)$

Na aritmética de números reais ordinários, a exponenciação é uma função monótona e encontrar o logaritmo de qualquer número em qualquer base é computacionalmente fácil. Em contraste, como fica evidente no simples exemplo de $(\mathbb{Z}_7)^{\times}$ acima, a exponenciação modular é não-monótona e, embora seja periódica com período $p-1$, é altamente não trivial nos demais aspectos. Portanto, calcular seu inverso — o logaritmo discreto — acaba sendo ineficiente para $p$ grande em computadores clássicos.

Essa observação fundamenta tanto a troca de chaves Diffie-Hellman (DH) quanto o Algoritmo de Assinatura Digital (DSA), que são discutidos na próxima seção.

O DLP pode ser estendido a subgrupos cíclicos da seguinte forma:

• Considere $(\mathbb{Z}_p)^{\times}$ definido acima e um elemento $g \in (\mathbb{Z}_p)^{\times}$ de ordem prima $r$, ou seja, $g^r \equiv 1 (~mod~p)$.
• O conjunto de potências inteiras de $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ é um subgrupo cíclico de $(\mathbb{Z}_p)^{\times}$ com ordem de grupo $r$.
• Um DLP pode ser especificado em $\langle g \rangle$ escolhendo um $h \in \langle g \rangle$ e pedindo por $1 \le a \le r$ tal que $g^a~(mod~p) = h$

Troca de chaves Diffie-Hellman

Em 1976, Whitfield Diffie e Martin Hellman propuseram um protocolo de troca de chaves para permitir a criação de uma chave secreta compartilhada em canais de comunicação inseguros. Essa chave secreta poderia então ser usada pelas partes para criptografia simétrica. O algoritmo se baseia no DLP.

Figura 1. Troca de chaves Diffie-Hellman

Detalhes matemáticos da troca de chaves Diffie-Hellman

Com Alice e Bob sendo as duas partes que se comunicam, o protocolo funciona da seguinte forma:

• Primeiro, Alice e Bob concordam com um número primo grande $p$ e uma raiz primitiva ou gerador $a$.
• Em seguida, Alice escolhe um expoente secreto $k_A$ aleatoriamente com $1 \le k_A \le p-2$ e calcula $h_A = a^{k_A}~(mod~p)$. $k_A$ e $h_A$ são as chaves privada e pública de Alice, respectivamente.
• Depois, Bob escolhe um expoente secreto $k_B$ aleatoriamente com $1 \le k_B \le p-2$ e calcula $h_B = a^{k_B}~(mod~p)$. $k_B$ e $h_B$ são as chaves privada e pública de Bob, respectivamente.
• Então, Alice envia $h_A$ para Bob e Bob envia $h_B$ para Alice por um canal confiável, mas não necessariamente seguro.
• Alice usa o $h_B$ que recebeu para calcular a chave secreta compartilhada $\kappa = h_B^{k_A}~(mod~p)$.
• Por fim, Bob usa o $h_A$ que recebeu para calcular a chave secreta compartilhada $\kappa = h_A^{k_B}~(mod~p)$.

Com esse protocolo:

• Alice e Bob têm a garantia de terminar com a mesma chave secreta $\kappa$ porque $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Um terceiro que intercepte $h_A$ ou $h_B$ não consegue construir a chave secreta $\kappa$ porque não tem acesso a $k_B$ ou $k_A$, respectivamente.
• Extrair $k_A$ ou $k_B$ usando as informações públicas $a$, $p$, $h_A$ e $h_B$ é computacionalmente difícil, pois equivale a resolver o DLP em $(\mathbb{Z}_p)^{\times}$.

Ilustração do protocolo Diffie-Hellman em Python

Vamos ver um exemplo simples do protocolo DH em Python usando números primos pequenos:

nota

Nesta seção, mostraremos os cálculos matemáticos em detalhes como parte do código Python.

Passo 1: Alice e Bob concordam com um primo $p$ e uma raiz primitiva $a$. Vamos escolher $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Passos 2, 3: Alice escolhe um expoente secreto $k_A$ e calcula $h_A = a^{k_A}~(mod~p)$. Da mesma forma, Bob escolhe um expoente secreto $k_B$ e calcula $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Passo 4: As duas partes divulgam suas chaves públicas $h_A$ e $h_B$.

Passos 5, 6: Cada parte combina sua chave privada com a chave pública da outra parte para criar a chave secreta compartilhada.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice e Bob agora podem usar a chave secreta compartilhada para criptografia simétrica.

Segurança da troca de chaves Diffie-Hellman

Como mencionado acima, a segurança do DH está condicionada à dificuldade computacional de resolver o DLP com primos grandes $p$. Em aplicações típicas, o NIST recomenda inteiros primos de 2048 ou 3072 bits para a troca de chaves DH, o que é considerado suficientemente seguro contra tentativas de resolver o DLP usando computadores clássicos.

Ataques Man-in-the-middle (MITM): O fato de que o DH é um esquema interativo em que o segredo compartilhado depende da combinação da chave privada de uma parte com a chave pública da outra o torna vulnerável a um chamado ataque Man-in-the-middle (MITM).

Detalhes matemáticos da segurança DH e ataques MITM

Nesse cenário, um terceiro — por exemplo, Eve — intercepta as chaves públicas $h_A, h_B$ durante a transmissão e substitui sua própria chave pública $h_E$ por cada uma de $h_A$ e $h_B$ antes de encaminhá-las para Bob e Alice, respectivamente.

Então, em vez de usar $h_B$ para criar seu segredo compartilhado, Alice usará $h_E$ pensando que está usando a chave pública de Bob. Da mesma forma, em vez de usar $h_A$ para criar seu segredo compartilhado, Bob usará $h_E$ pensando que está usando a chave pública de Alice.

Como $h_E$ foi usada para criar o segredo compartilhado de Alice (e de Bob), o texto puro criptografado por Alice (ou Bob) pode ser decifrado por Eve.

Portanto, a troca de chaves DH é tipicamente usada em conjunto com um algoritmo de assinatura digital para garantir que cada parte use uma chave pública autenticada para criar seu segredo compartilhado.

O Algoritmo de Assinatura Digital (DSA)

Embora criptossistemas genéricos como o RSA forneçam funcionalidade de assinatura digital, em 1994 o NIST adotou um esquema de assinatura especializado baseado em exponenciação modular e no problema do logaritmo discreto como padrão federal para assinaturas digitais. Esse esquema, que ficou conhecido simplesmente como Algoritmo de Assinatura Digital (DSA), envolve quatro fases distintas:

1. Geração de chaves:

   As chaves DSA são geradas a partir de:

   • 2 primos que atendem a certas regras
     • $p$ — tipicamente 256 bits (chamaremos esse comprimento de $N$)
     • $q$ — tipicamente 3072 bits (chamaremos esse comprimento de $L$)
   • Uma função hash criptográfica que converterá strings de comprimento $L$ para $N$
   • Um parâmetro adicional $g$ (veja os detalhes abaixo)

   A partir disso, escolhemos um número aleatório $x$ como chave privada e somos capazes de calcular uma chave pública $y$.

   Detalhes matemáticos da geração de chaves

   • Geração de parâmetros: Matematicamente, o DSA envolve um subgrupo cíclico de $(\mathbb{Z}_p)^{\times}$ gerado por um elemento $g$ de ordem prima q < p. O primeiro passo do DSA é, portanto, selecionar dois primos p, q para configurar as estruturas matemáticas necessárias.

     • Escolha um primo $q$ de $N$ bits.
     • Escolha um primo $p$ de $L$ bits tal que $p-1$ seja um múltiplo de $q$. A escolha de $p$ especifica o grupo $(\mathbb{Z}_p)^{\times}$.
     • Escolha um inteiro $1 < h < p-1$ aleatoriamente e compute $g = h^{(p-1)/q}~mod~p$. Se $g=1$, o que ocorre raramente, tente outro $h$.
     • Verifique se $g^q~mod~p = 1$. $g$ é, portanto, um gerador de um subgrupo cíclico $\langle g \rangle$ de $(\mathbb{Z}_p)^{\times}$ de ordem prima $q$.

     Os parâmetros $(q, p, g)$ especificam uma instância do algoritmo e são informações públicas. Tipicamente, $N \sim 256$ e $L \sim 3072$ em aplicações reais.

     O protocolo também requer uma função hash criptográfica $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ que mapeia strings binárias de $L$ bits para strings de $N$ bits, por exemplo, SHA-256.

   • Geração do par de chaves: O assinante precisa gerar um par de chaves em seu lado.

     • Escolha um inteiro secreto aleatório $x \in \{1,2...q-1\}$. $x$ é a chave privada.
     • Gere $y = g^{x}~mod~p$. $y$ é a chave pública do assinante.

2. Distribuição de chaves:

   As seguintes informações são compartilhadas com qualquer pessoa que queira validar uma assinatura:

   • Os parâmetros usados $(p,q,g)$, que descrevem o algoritmo
   • A função hash $H$
   • A chave pública $y$

3. Assinatura:

   • O assinante pode agora assinar uma mensagem $m$. A assinatura resultante é $(r,s)$.
   • A mensagem e a assinatura são enviadas ao destinatário.

   Detalhes matemáticos de como assinar uma mensagem

   O assinante assina uma mensagem $m$ da seguinte forma:

   • Escolha um inteiro secreto $k$ aleatoriamente de $\{1,2...q-1\}$.
   • Calcule $r = (g^k~mod~p)~mod~q$. Na rara ocorrência de $r=0$, tente outro $k$ aleatório.
   • Calcule $s = (k^{-1} (H(m) + xr))~mod~q$. Em rara ocorrência, se $s=0$, tente outro $k$ aleatório.
   • A assinatura é a tupla $(r, s)$.
   • O assinante transmite a mensagem $m$ bem como a assinatura $(r,s)$ ao verificador.

   Como $r$ e $s$ são inteiros módulo $q$, o tamanho da assinatura é da ordem de $N$ bits e não dos $L$ bits mais longos.

4. Verificação:

   O destinatário agora deseja verificar a autenticidade do remetente. Ele tem acesso às informações públicas $(q, p, g, H, y, (r,s), m)$ e pode executar um cálculo que prova que o remetente tinha acesso à chave privada $x$.

   Detalhes matemáticos do esquema de verificação do DSA

   • Verifique se $0 \lt r \lt q$ e $0 \lt s \lt q$, ou seja, $r$ e $s$ são inteiros válidos módulo $q$.
   • Calcule $w = s^{-1}~mod~q$.
   • Calcule $u_1 = H(m)w~mod~q$.
   • Calcule $u_2 = rw~mod~q$.
   • Calcule $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • A assinatura é verificada se $v = r$.

   Para assinaturas legítimas, a correção do algoritmo DSA é demonstrada facilmente da seguinte forma:

   • No lado do assinante: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$.
   • Considerando o lado direito da última igualdade, um verificador pode calcular $s^{-1}$ e $H(m)$ porque $s$, $q$, $m$ e $H$ são informações públicas.
   • Assim, o verificador computa $w = s^{-1}~mod~q$ e $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • O verificador também computa $u_2 = rw~mod~q = rs^{-1}~mod~q$, pois $r$ também é público.
   • Observe que $k = (u_1 + xu_2)~mod~q$.
   • No entanto, o verificador não tem acesso a $x$, pois é a chave privada do assinante, portanto $k$ em si não pode ser calculado diretamente. O esquema se baseia no fato de que, mesmo sem conseguir calcular $k$, com um assinante legítimo, o verificador deve conseguir recalcular $(g^k~mod~p)~mod~q = r$ com a ajuda da chave pública do assinante $y = g^{x}~mod~p$.
   • Portanto, o verificador calcula $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • A última igualdade se sustenta porque $g$ tem ordem $q$ e estabelece $v = r$ para assinaturas válidas.

Ilustração do DSA em Python

Neste exemplo, usaremos primos pequenos para ilustrar o processo do DSA em um cenário em que Alice envia uma mensagem assinada para Bob. Usaremos inteiros pequenos neste exemplo. Um cenário real empregaria primos muito maiores, da ordem de 2048 a 3072 bits.

nota

Você pode tentar reexecutar este exemplo com valores diferentes para ver como o algoritmo se comporta, mas certifique-se de começar a execução a partir da primeira célula desta seção.

Começamos importando as bibliotecas necessárias e escolhendo nossos parâmetros. Os parâmetros inteiros $p$, $q$, $g$ são informações públicas e satisfazem as seguintes regras:

• $p$, $q$ são ambos primos
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Em seguida, a assinante, Alice, gera sua chave privada.

A chave privada, k (alice-private-key no código Python), deve satisfazer:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice mantém sua chave privada em segredo.

Em seguida, Alice calcula sua chave pública usando exponenciação modular. Inverter esse passo para recuperar a chave privada é uma instância do DLP, sendo difícil de computar em computadores clássicos quando primos grandes são usados.

A partir da explicação matemática acima, sabemos que isso pode ser calculado usando a fórmula:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Como de costume, Alice disponibiliza sua chave pública em um canal não necessariamente secreto.

Agora Alice pode assinar uma mensagem.

Para o esquema de assinatura digital, precisamos gerar um hash $H(m)$ da mensagem $m$ a ser assinada.

Vamos assumir que Alice e Bob concordam em usar um algoritmo de hash específico com comprimento de hash $N$ igual ao número de bits em $q$. Neste exemplo simples, limitaremos as saídas de nossa função hash fictícia por $q$. A função hash aqui é trivial, simplesmente gerando um inteiro aleatório.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Em seguida, Alice precisa gerar um número secreto aleatório por mensagem $k$, bem como seu inverso multiplicativo módulo $q$, para calcular a assinatura.

Um algoritmo simples de força bruta pode ser usado para calcular o inverso modular. No entanto, é melhor usar a função Python integrada pow, conforme mostrado abaixo.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice pode agora calcular a assinatura.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Observe que existem certas condições que exigirão que escolhamos um valor diferente de $k$ no caso em que $r$ ou $s$ resultem em $0$. Nesse caso, geraremos um novo valor e repetiremos.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice divulga a mensagem e sua assinatura para o destinatário ou verificador, Bob.

Bob já obteve a chave pública de Alice anteriormente e agora pode verificar a assinatura para autenticar sua mensagem.

Para isso, ele realiza algumas verificações e, em seguida, regera um hash da mensagem divulgada por Alice e calcula as quantidades auxiliares $w$, $u_1$, $u_2$ e $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Por fim, Bob verifica se $v$ é igual a $r$. Se forem iguais, a assinatura é verificada.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Segurança do DSA

Na computação clássica, a segurança do DSA pode ser influenciada por vários fatores:

1. Tamanho da chave: Como sempre, o tamanho da chave fornece proteção básica contra ataques de força bruta. Aplicações modernas que usam DSA utilizam tamanhos de chave de pelo menos 2048 bits.

2. Qualidade de $k$: No DSA, cada assinatura precisa de um valor $k$ único, aleatório e secreto (veja acima). A unicidade, a entropia e o sigilo de $k$ são críticos, e a fraqueza em qualquer um desses aspectos pode levar ao comprometimento da chave privada $x$. Os geradores de números aleatórios usados para gerar $k$ precisam ser seguros por si mesmos.

3. Robustez da função hash: Como o DSA usa uma função hash como parte do processo de geração e verificação de assinaturas, uma função hash fraca poderia comprometer a segurança da assinatura digital. Por exemplo, o uso do SHA-1 com DSA está obsoleto e recomenda-se o SHA-2 ou superior.

Além dessas, uma implementação robusta do DSA também deve se proteger contra outros tipos de ataques que visam a criptografia de chave assimétrica, conforme descrito anteriormente.

Troca de chaves autenticada com Diffie-Hellman e DSA

Protocolos modernos de segurança de rede, como o Transport Layer Security (TLS) e muitos outros, envolvem a combinação das funcionalidades de troca de chaves e autenticação. No contexto do Diffie-Hellman, a autenticação é necessária para proteger contra ataques MITM. Nas células de código a seguir, ilustramos um exemplo em que Alice e Bob realizam uma troca de chaves autenticada combinando os protocolos Diffie-Hellman e DSA. Para isso, usaremos a biblioteca Python cryptography.

Figura 2. Troca de chaves autenticada com Diffie-Hellman e DSA

Primeiro, Alice e Bob concordam com um conjunto de parâmetros DH e geram um conjunto de pares de chaves DH pública-privada.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

As chaves públicas DH são divulgadas. Em seguida, tanto Alice quanto Bob geram um par de chaves separado para uso com o DSA. Essas chaves serão usadas para assinar as chaves públicas DH a serem trocadas.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice assina sua chave pública DH usando sua chave privada DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Da mesma forma, Bob assina sua chave pública DH usando sua chave privada DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

As chaves públicas DH e as assinaturas correspondentes são agora divulgadas por Alice e Bob. Tendo recebido a chave pública e a assinatura da contraparte, cada parte verifica se a assinatura é válida. Dessa forma, um ataque MITM pode ser evitado, pois Alice, por exemplo, sabe que a chave pública DH de Bob foi de fato assinada por Bob e vice-versa.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Após a verificação das assinaturas, Alice e Bob geram o segredo compartilhado, o que completa a troca de chaves.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Opcionalmente, para segurança adicional, Alice e Bob podem usar uma função especializada de derivação de chave, como HKDF, para gerar uma chave simétrica mais segura a partir de seu segredo compartilhado usando técnicas de key stretching.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Quebrando o Diffie-Hellman e o DSA

Tanto o protocolo Diffie-Hellman (DH) quanto o DSA envolvem a geração de chaves públicas da forma $y = g^{x}~mod~p$, onde a chave privada $x$ é o logaritmo discreto.

Um atacante que consiga resolver uma instância do PLD pode expor a chave privada de uma das duas partes e, combinando-a com a chave pública da segunda parte, obter acesso ao segredo compartilhado. No caso do DSA, um atacante que consiga resolver o PLD pode recuperar a chave privada do assinante, anulando a premissa básica de uma assinatura digital.

Em sistemas computacionais clássicos, acredita-se que o PLD não tenha solução em tempo polinomial. Mas como Peter Shor demonstrou no seu artigo original de 1994, o algoritmo de Shor também resolve o PLD em tempo polinomial em computadores quânticos.

O algoritmo de Shor e o problema do logaritmo discreto

O algoritmo de Shor é capaz de resolver o problema do logaritmo discreto em tempo polinomial. Ele alcança essa eficiência principalmente usando algoritmos quânticos que conseguem encontrar o período de uma função que depende da entrada do problema — o que é então combinado com operações mais convencionais.

Detalhes matemáticos do algoritmo de Shor

O algoritmo de Shor fornece uma solução eficiente para o PLD mapeando-o para um problema mais geral em teoria de grupos, conhecido como o problema do subgrupo oculto (HSP, do inglês hidden subgroup problem).

No HSP, é dado um grupo algébrico $G$ e uma função $f: G \rightarrow X$ de $G$ para algum conjunto $X$, tal que $f$ é constante em cada coset de algum subgrupo $H$ de $G$ (e distinta em cosets diferentes). A tarefa é então determinar $H$. Sabe-se que computadores quânticos conseguem resolver o HSP em grupos Abelianos finitos em tempo polinomial em $log~|G|$, onde $|G|$ é a ordem do grupo.

No caso do PLD inteiro discutido nesta lição, o mapeamento para o HSP é o seguinte:

• Seja $p$ um número primo e considere o PLD dado por $y = g^r~mod~p$, onde $g$ é um gerador de $(\mathbb{Z}_p)^{\times}$. Como $g^{p-1} \equiv 1~mod~p$, $g$ tem ordem $p-1$.
• Escolha $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$, onde $\mathbb{Z}_{p-1}$ é o grupo dos inteiros módulo $(p-1)$.
• Escolha $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ dada por $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$.
• O kernel de $f$ é então o subgrupo $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ é constante nos cosets $(\delta, 0) + H_0$ e "esconde" o subgrupo $H_0$, configurando um HSP.

Com base nisso, o algoritmo quântico de Shor para o PLD inteiro usa um oráculo quântico para avaliar a função $f$ em um estado que representa uma superposição uniforme sobre $G$, e então usa a transformada de Fourier quântica e medições com estimativa de fase para produzir estados quânticos que permitem identificar o gerador $(r, 1)$ de $H_0$. A partir disso, $r$, o logaritmo discreto de interesse, pode ser extraído.

O artigo original de Shor contém uma descrição detalhada do algoritmo.

Criptografia de curvas elípticas

A criptografia de curvas elípticas (ECC), baseada na matemática das curvas elípticas, oferece uma abordagem poderosa para a criptografia de chave assimétrica. A ECC é conhecida por fornecer um nível de segurança semelhante ao de métodos como o RSA, mas com chaves menores, tornando-a mais eficiente e especialmente adequada para sistemas com recursos limitados, como sistemas embarcados e dispositivos móveis, onde a economia de armazenamento e processamento proporcionada por chaves menores é muito desejável.

Princípios básicos da criptografia de curvas elípticas

Uma curva elíptica tem tipicamente a forma $y^2 = x^3 + ax + b$, com algumas propriedades interessantes:

• É simétrica horizontalmente. Assim, para qualquer ponto $(x,y)$ na curva, seu reflexo $(x,-y)$ também está na curva.
• Qualquer linha reta não vertical intersecta a curva em no máximo três pontos.

Figura 1. Operações de adição e duplicação de ponto em uma curva elíptica. A faceta 1 define P + Q = -R. A faceta 2 ilustra a duplicação de ponto 2Q = -P. A faceta 3 define o inverso aditivo de um ponto como seu reflexo em relação ao eixo x, ou seja, P = -Q

A criptografia de curvas elípticas faz uso de uma série de operações aritméticas aplicadas a pontos na curva. Cada operação efetivamente leva a um novo ponto na curva. Esse é um processo simples de seguir em uma direção e, com chaves menores, é mais eficiente do que outros algoritmos como o RSA — mas tentar reverter esse processo é muito difícil, daí sua aplicação à criptografia.

Princípios matemáticos da criptografia de curvas elípticas

Uma curva elíptica sobre um corpo algébrico $K$ é definida por uma equação matemática, tipicamente da forma $y^2 = x^3 + ax + b$, com coeficientes $a, b \in K$, e descreve pontos $(x, y) \in K \otimes K$ com o requisito adicional de que a curva não tenha quinas nem auto-interseções.

As propriedades das curvas elípticas permitem definir operações de "adição" e "multiplicação escalar" envolvendo pontos na curva.

Adição: Se $P$ e $Q$ são dois pontos em uma curva elíptica, então $P + Q$ descreve um terceiro ponto único identificado da seguinte forma: traça-se a reta que intersecta $P$ e $Q$ e encontra-se o terceiro ponto, $R$, onde a reta intersecta a curva novamente. Definimos então $P + Q = −R$, o ponto oposto a $R$ refletido pelo eixo $x$ (veja a figura abaixo). Quando a reta passando por $P, Q$ não intersecta a curva em nenhum $(x, y)$ finito, dizemos que ela intersecta a curva no ponto no infinito $\mathbf{O}$.

A adição em curvas elípticas satisfaz as propriedades algébricas de grupo, com o ponto no infinito como identidade aditiva.

Duplicação e multiplicação escalar: A operação de duplicação de ponto, que corresponde à multiplicação escalar por $2$, é obtida fazendo $P = Q$ na operação de adição e, graficamente, envolve a reta tangente em $P$. A multiplicação escalar geral por um inteiro $n$, definida como $nP = P + P + ...~n$ vezes, é obtida por duplicações e adições sucessivas.

Problema do logaritmo discreto em curvas elípticas

O problema do logaritmo discreto em curvas elípticas (ECDLP, do inglês Elliptic Curve Discrete Logarithm Problem) tem muitas semelhanças com o problema do logaritmo discreto discutido anteriormente, sendo baseado nos desafios de encontrar fatores.

A operação de multiplicação escalar em curvas elípticas permite a definição do problema do logaritmo discreto em curvas elípticas:

Dados os pontos $P, Q$ em uma curva elíptica tal que $Q = nP$, determine $n$.

Esse problema é considerado intratável em computadores clássicos para valores grandes de $n$ e fornece uma base para a segurança criptográfica.

Descrição matemática do ECDLP

A criptografia de curvas elípticas é baseada principalmente no ECDLP formulado sobre certos corpos finitos algébricos. Em 1999, o NIST recomendou dez corpos finitos para uso em ECC. São eles:

• Cinco corpos primos $\mathbb {F} _{p}$ para primos $p$ de tamanho $\{192, 224, 256, 384, 521\}$ bits.
• Cinco corpos binários $\mathbb {F} _{2^{n}}$ para $n \in \{163, 233, 283, 409, 571\}$.

Com a configuração acima, um criptossistema de chave assimétrica baseado em ECC no caso de corpos primos pode ser especificado da seguinte forma:

• Escolha um $p$ da lista de valores recomendados pelo NIST para especificar $\mathbb {F} _{p}$.

• Selecione os parâmetros $a, b$ da curva elíptica.

• Escolha um ponto base $G$ que "gera" um subgrupo cíclico na curva com ordem $n$; ou seja, o menor inteiro tal que $nG = \mathbf{O}$.

• Calcule o cofator $h = |E(\mathbb {F} _{p})|/n$, onde $|E(\mathbb {F} _{p})|$ é o número de pontos na curva. $h$ é tipicamente um inteiro pequeno.

• Os parâmetros de domínio $(p, a, b, G, n, h)$ permitem especificar as chaves assimétricas da seguinte forma:

  • A chave privada é um inteiro escolhido aleatoriamente $d$ com o mesmo número de bits do primo $p$. Ela deve ser mantida em segredo.
  • A chave pública é o resultado de "multiplicar" o ponto base $G$ pela chave privada $d$. Isso é tipicamente denotado como $Q = dG$.

Recuperar $d$ equivale a resolver o ECDLP, o qual se assume ser intratável para $d$ grande. O ECDLP, portanto, constitui a base para esquemas de troca de chaves e assinaturas digitais, em analogia direta com os esquemas Diffie-Hellman e DSA definidos sobre $(\mathbb{Z}_p)^{\times}$ discutidos anteriormente.

Troca de chaves com ECC

Um dos principais usos da ECC é no protocolo de troca de chaves conhecido como Diffie-Hellman de curvas elípticas (ECDH). No ECDH, cada parte gera um par de chaves privada-pública e então troca as chaves públicas. Cada parte usa sua própria chave privada e a chave pública da outra parte para calcular um segredo compartilhado, que pode ser usado como chave para criptografia simétrica.

Embora seja relativamente fácil realizar a adição de pontos em uma curva elíptica e derivar uma chave pública a partir de uma chave privada, é computacionalmente inviável reverter esse processo e derivar uma chave privada a partir de uma chave pública. Esse comportamento de "mão única" garante a segurança da troca de chaves ECDH.

Aqui, vamos ilustrar um exemplo de como realizar uma troca de chaves ECDH usando Python e a biblioteca cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Assinaturas digitais com ECC

A ECC também pode ser usada para gerar assinaturas digitais por meio do Algoritmo de Assinatura Digital de Curva Elíptica (ECDSA). No ECDSA, o assinante cria uma assinatura usando sua chave privada, e outros podem verificar a assinatura usando a chave pública do assinante. Assim como no ECDH, a segurança do ECDSA depende do ECDLP. É computacionalmente inviável para alguém falsificar uma assinatura sem ter acesso à chave privada do assinante.

A seguir, temos um exemplo de uma transação simples de assinar e verificar usando ECDSA com Python e cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

No código acima, se a mensagem for modificada após ter sido assinada, a verificação falhará, garantindo autenticidade e integridade para a mensagem.

Quebrando o ECDH e o ECDSA

De forma análoga ao problema do logaritmo discreto inteiro, o ECDLP se revela difícil em computadores clássicos, mas tem uma solução eficiente em computadores quânticos, novamente via algoritmo de Shor. Remetemos o leitor à literatura recente para uma discussão sobre a generalização do algoritmo de Shor para o caso do ECDLP.

Resumo

Nesta lição, começamos examinando as principais características da criptografia de chave assimétrica (AKC) e discutimos as considerações básicas de segurança que sustentam os criptossistemas assimétricos. Em particular, introduzimos as duas principais aplicações da AKC — a troca de chaves e as assinaturas digitais — ambas componentes essenciais da comunicação moderna baseada na internet.

Em seguida, examinamos o criptossistema RSA, que desde a década de 1970 tem se mostrado de imenso valor para proteger as comunicações digitais modernas, viabilizando a troca de chaves e as assinaturas digitais dentro de um framework simples e versátil. A segurança criptográfica do RSA em relação à computação clássica é baseada na dificuldade de fatorar inteiros grandes e requer tamanhos de chave na faixa de 2048 bits para garantir que os inteiros usados em aplicações práticas sejam grandes o suficiente para resistir à fatoração.

Em seguida, examinamos a troca de chaves Diffie-Hellman (DH) e o Algoritmo de Assinatura Digital (DSA). A segurança desses esquemas está fundamentada no problema do logaritmo discreto inteiro (PLD), sendo a chave privada computacionalmente difícil de extrair a partir da chave pública, sem solução em tempo polinomial em computadores clássicos. O uso de chaves aleatórias e únicas confere segurança adicional contra ataques. Tanto as variantes de campo finito inteiro quanto as de curva elíptica dos protocolos DH e DSA atualmente têm uso generalizado em muitos protocolos modernos de comunicação digital, como TLS, SSH, entre outros.

Por fim, examinamos a criptografia de curvas elípticas. Com seu tamanho de chave eficiente e fortes propriedades de segurança, ela representa atualmente uma excelente escolha para muitas aplicações criptográficas, desde a troca de chaves até as assinaturas digitais.

Todos esses algoritmos estão expostos a ataques de algoritmos quânticos, uma vez que é possível desenvolver soluções para os problemas matemáticos que serviram como premissa em seu design. Um exemplo é o algoritmo de Shor. Portanto, eles precisarão ser substituídos por criptossistemas assimétricos seguros contra computadores quânticos, que sejam mais resistentes a ataques quânticos — e que ao mesmo tempo mantenham a segurança frente a algoritmos clássicos. Os problemas matemáticos nos quais se baseiam podem ser resolvidos eficientemente por computadores quânticos, tornando necessário o desenvolvimento de criptossistemas assimétricos seguros contra ataques quânticos que resistam a ataques quânticos e mantenham a segurança clássica.