Saúde

Criptossistema de McEliece

Texto da Wikipédia (pt), licença CC BY-SA. O BETARUBI mostra o verbete inteiro nesta página — a leitura não continua fora do site.

Na criptografia, o criptossistema de McEliece é um algoritmo de criptografia assimétrica desenvolvido em 1978 por Robert McEliece.^[1] Foi o primeiro esquema desse tipo a usar aleatorização no processo de criptografia. O algoritmo nunca ganhou muita aceitação na comunidade criptográfica, mas é um candidato para a "criptografia pós-quântica", pois é imune a ataques usando o Algoritmo de Shor e – de forma mais geral – à medição de estados de classes laterais (cosets) usando amostragem de Fourier.^[2]

O algoritmo baseia-se na dificuldade de decodificar um código linear genérico (problema que se sabe ser NP-difícil^[3]). Para a descrição da chave privada, um código de correção de erros é selecionado, para o qual se conhece um algoritmo de decodificação eficiente, e que seja capaz de corrigir $t$ erros. O algoritmo original usa códigos de Goppa binários (códigos de subcorpos de códigos de geometria algébrica de uma curva de gênero 0 sobre corpos finitos de característica 2); esses códigos podem ser decodificados eficientemente, graças a um algoritmo de autoria de Patterson.^[4] A chave pública é derivada da chave privada disfarçando o código selecionado como um código linear genérico. Para isso, a matriz geradora $G$ do código é perturbada por duas matrizes invertíveis selecionadas aleatoriamente, $S$ e $P$ (veja abaixo).

Existem variantes deste criptossistema que utilizam diferentes tipos de códigos. A maioria deles provou ser menos segura; foram quebrados por decodificação estrutural.

O McEliece com códigos de Goppa tem resistido à criptoanálise até o momento. Os ataques mais eficazes conhecidos usam algoritmos de decodificação de conjunto de informações. Um artigo de 2008 descreve tanto um ataque quanto uma correção.^[5] Outro artigo mostra que, para a computação quântica, os tamanhos de chave devem ser aumentados por um fator de quatro devido a melhorias na decodificação de conjunto de informações.^[6]

O criptossistema de McEliece tem algumas vantagens sobre, por exemplo, o RSA. A criptografia e a descriptografia são mais rápidas.^[7] Durante muito tempo, pensou-se que o McEliece não poderia ser usado para produzir assinaturas digitais. No entanto, um esquema de assinatura pode ser construído com base no esquema de Niederreiter, a variante dual do esquema de McEliece. Uma das principais desvantagens do McEliece é que as chaves pública e privada são matrizes grandes. Para uma seleção padrão de parâmetros, a chave pública tem 512 kilobits de comprimento.

Definição do esquema

O McEliece consiste em três algoritmos: um algoritmo probabilístico de geração de chaves que produz uma chave pública e uma chave privada, um algoritmo de criptografia probabilística e um algoritmo de descriptografia determinístico.

Todos os usuários numa implantação do McEliece compartilham um conjunto de parâmetros de segurança comuns: $n,k,t$ .

Geração de chaves

O princípio é que Alice escolhe um código linear $C$ de alguma família de códigos para a qual ela conhece um algoritmo de decodificação eficiente, e torna $C$ de conhecimento público, mas mantém o algoritmo de decodificação em segredo. Tal algoritmo de decodificação requer não apenas conhecer $C$ , no sentido de conhecer uma matriz geradora arbitrária, mas requer que se conheça os parâmetros usados ao especificar $C$ na família de códigos escolhida. Por exemplo, para códigos de Goppa binários, essa informação seria o polinômio de Goppa e os localizadores do código. Portanto, Alice pode publicar uma matriz geradora de $C$ adequadamente ofuscada.

Mais especificamente, as etapas são as seguintes:

Alice seleciona um código linear binário $(n,k)$ $C$ capaz de corrigir (eficientemente) $t$ erros a partir de alguma família grande de códigos, ex. códigos de Goppa binários. Esta escolha deve dar origem a um algoritmo de decodificação eficiente $A$ . Seja também $G$ qualquer matriz geradora para $C$ . Qualquer código linear tem muitas matrizes geradoras, mas muitas vezes há uma escolha natural para essa família de códigos. Conhecer isso revelaria $A$ , portanto deve ser mantido em segredo.
Alice seleciona uma matriz não singular binária aleatória $S$ de dimensão $k\times k$ .
Alice seleciona uma matriz de permutação aleatória $P$ de dimensão $n\times n$ .
Alice calcula a matriz ${\hat {G}}=SGP$ de dimensão $k\times n$ .
A chave pública de Alice é $({\hat {G}},t)$ ; sua chave privada é $(S,P,A)$ . Note que $A$ pode ser codificado e armazenado como os parâmetros usados para selecionar $C$ .

Criptografia de mensagem

Suponha que Bob deseje enviar uma mensagem $m$ para Alice, cuja chave pública é $({\hat {G}},t)$ :

Bob codifica a mensagem $m$ como uma cadeia (string) binária de comprimento $k$ .
Bob calcula o vetor $c^{\prime }=m{\hat {G}}$ .
Bob gera um vetor aleatório $z$ de $n$ bits contendo exatamente $t$ uns (um vetor de comprimento $n$ e peso $t$ ).^[1]
Bob envia a Alice o texto cifrado calculado como $c=c^{\prime }+z$ .

Descriptografia de mensagem

Ao receber $c$ , Alice executa as seguintes etapas para descriptografar a mensagem:

Alice calcula a inversa de $P$ (isto é, $P^{-1}$ ).
Alice calcula ${\hat {c}}=cP^{-1}$ .
Alice usa o algoritmo de decodificação $A$ para decodificar ${\hat {c}}$ em ${\hat {m}}$ .
Alice calcula $m={\hat {m}}S^{-1}$ .

Demonstração da descriptografia da mensagem

Note que ${\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}$ , e que $P$ é uma matriz de permutação, logo $zP^{-1}$ tem peso $t$ .

O código de Goppa $G$ pode corrigir até $t$ erros, e a palavra $mSG$ está a uma distância de no máximo $t$ de $cP^{-1}$ . Portanto, a palavra-código correta ${\hat {m}}=mS$ é obtida.

Multiplicar pela inversa de $S$ fornece $m={\hat {m}}S^{-1}=mSS^{-1}$ , que é a mensagem em texto claro original.

Tamanhos de chave

Como há uma livre escolha na matriz $S$ , é comum expressar ${\hat {G}}$ na "forma sistemática" para que as últimas $k$ colunas correspondam à matriz identidade ${\hat {G}}=({\tilde {G}}|I)$ . Isso reduz o tamanho da chave para $(n-k)\times k$ .^[8]^[9] Originalmente, McEliece sugeriu parâmetros de segurança de tamanhos $n=1024,k=524,t=50$ ,^[1] resultando num tamanho de chave pública de 524 × (1024 − 524) = 262000 bits. Análises recentes sugerem parâmetros de tamanho $n=2048,k=1751,t=27$ para $80$ bits de segurança ao usar a decodificação algébrica padrão, ou $n=1632,k=1269,t=34$ ao usar a decodificação em lista para o código de Goppa, originando tamanhos de chave pública de 520047 e 460647 bits, respectivamente.^[5] Para resiliência contra computadores quânticos, foram propostos os tamanhos de $n=6960,k=5413,t=119$ com o código de Goppa, resultando no tamanho de chave pública de 8373911 bits.^[10] Na sua submissão da rodada 3 para a padronização pós-quântica do NIST, o nível mais alto de segurança (nível 5) é dado para os conjuntos de parâmetros 6688128, 6960119 e 8192128. Os parâmetros são $n=6688,k=5024,t=128$ ; $n=6960,k=5413,t=119$ ; e $n=8192,k=6528,t=128$ , respectivamente.

Ataques

Um ataque consiste em um adversário, que conhece a chave pública $({\hat {G}},t)$ mas não a chave privada, deduzir o texto simples a partir de algum texto cifrado interceptado $y\in \mathbb {F} _{2}^{n}$ . Tais tentativas devem ser impraticáveis.

Existem dois ramos principais de ataques para o McEliece:

Força bruta / ataques não estruturados

O invasor conhece ${\hat {G}}$ , a matriz geradora de um código $(n,k)$ ${\hat {C}}$ que é combinatorialmente capaz de corrigir $t$ erros. O invasor pode ignorar o fato de que ${\hat {C}}$ é na verdade a ofuscação de um código estruturado escolhido a partir de uma família específica e, em vez disso, usar apenas um algoritmo para decodificação genérica com qualquer código linear. Vários algoritmos do tipo existem, como testar cada palavra-código do código, decodificação por síndrome ou decodificação de conjunto de informações.

No entanto, sabe-se que a decodificação de um código linear genérico é NP-difícil,^[3] e todos os métodos mencionados acima têm tempo de execução exponencial.

Em 2008, Bernstein, Lange e Peters^[5] descreveram um ataque prático ao criptossistema de McEliece original, usando o método de decodificação de conjunto de informações de Stern.^[11] Usando os parâmetros originalmente sugeridos por McEliece, o ataque pôde ser realizado em $2^{60.55}$ operações de bits. Como o ataque é embaraçosamente paralelo (não é necessária comunicação entre os nós), ele pode ser executado em dias em clusters de computadores modestos.

Ataques estruturais

Como alternativa, o invasor pode tentar recuperar a "estrutura" de $C$ , recuperando assim o algoritmo de decodificação eficiente $A$ ou outro algoritmo de decodificação suficientemente forte e eficiente.

A família de códigos da qual $C$ é escolhido determina completamente se isso é possível para o atacante. Muitas famílias de códigos foram propostas para o McEliece, e a maioria delas foi completamente "quebrada" no sentido de que foram encontrados ataques que recuperam um algoritmo de decodificação eficiente, a exemplo dos códigos de Reed-Solomon.

Os códigos de Goppa binários, originalmente propostos, permanecem como uma das poucas famílias de códigos sugeridas que resistiram amplamente às tentativas de elaboração de ataques estruturais.

Candidato a criptografia pós-quântica

Uma variante deste algoritmo combinada com o NTS-KEM^[12] foi inscrita e selecionada durante a terceira rodada da competição de criptografia pós-quântica do NIST.^[13]

Referências

1 2 3 McEliece, Robert J. (1978). «A Public-Key Cryptosystem Based on Algebraic Coding Theory» (PDF). DSN Progress Report. 44: 114–116. Bibcode:1978DSNPR..44..114M
↑ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip, ed. McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks. Advances in cryptology—CRYPTO 2011. Lecture Notes in Computer Science. 6841. Heidelberg: Springer. pp. 761–779. ISBN 978-3-642-22791-2. MR 2874885. doi:10.1007/978-3-642-22792-9_43
1 2 Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk C.A. (1978). «On the Inherent Intractability of Certain Coding Problems». IEEE Transactions on Information Theory. IT-24 (3): 384–386. MR 0495180. doi:10.1109/TIT.1978.1055873
↑ N. J. Patterson (1975). «The algebraic decoding of Goppa codes». IEEE Transactions on Information Theory. IT-21 (2): 203–207. doi:10.1109/TIT.1975.1055350
1 2 3 Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 de agosto de 2008). «Attacking and Defending the McEliece Cryptosystem». Post-Quantum Cryptography. Col: Lecture Notes in Computer Science. 5299. [S.l.: s.n.] pp. 31–46. CiteSeerX 10.1.1.139.3548. ISBN 978-3-540-88402-6. doi:10.1007/978-3-540-88403-3_3
↑ Bernstein, Daniel J. (2010). Sendrier, Nicolas, ed. Grover vs. McEliece (PDF). Post-quantum cryptography 2010. Lecture Notes in Computer Science. 6061. Berlin: Springer. pp. 73–80. ISBN 978-3-642-12928-5. MR 2776312. doi:10.1007/978-3-642-12929-2_6
↑ «eBATS: ECRYPT Benchmarking of Asymmetric Systems». bench.cr.yp.to. 25 de agosto de 2018. Consultado em 1 de maio de 2020
↑ Classic McEliece Team (23 de outubro de 2022). «Classic McEliece: conservative code-based cryptography: cryptosystem specification» (PDF). Round 4 NIST Submission Overview
↑ Tanja Lange (23 de fevereiro de 2021). «Code-based cryptography III - Goppa codes: definition and usage». YouTube
↑ Daniel Augot; et al. (7 de setembro de 2015). «Initial recommendations of long-term secure post-quantum systems» (PDF). PQCRYPTO: Post-Quantum Cryptography for Long-Term Security
↑ Jacques Stern (1989). «A method for finding codewords of small weight». Coding Theory and Applications. Col: Lecture Notes in Computer Science. 388. [S.l.]: Springer Verlag. pp. 106–113. ISBN 978-3-540-51643-9. doi:10.1007/BFb0019850
↑ «NTS-KEM». 29 de dezembro de 2017. Consultado em 9 de dezembro de 2020. Cópia arquivada em 29 de dezembro de 2017
↑ «Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process» (PDF). NISTIR. 31 páginas

Ligações externas

Alfred J. Menezes; Scott A. Vanstone; A. J. Menezes; Paul C. van Oorschot (1996). «Chapter 8: Public-Key Encryption». Handbook of Applied Cryptography. [S.l.]: CRC Press. ISBN 978-0-8493-8523-0
Rahmschmid, Claudia; Adams, David (2023). McEliece Messaging: Smoke Crypto Chat - The first mobile McEliece-Messenger published as a stable prototype worldwide. [S.l.]: Article TK Info Portal
«Quantum Computers? Internet Security Code of the Future Cracked». Science Daily. Eindhoven University of Technology. 1 de novembro de 2008
«Classic McEliece» (Submissão para o projeto de Padronização de Criptografia Pós-Quântica do NIST)

A carregar…