NTRUEncrypt

NTRUEncrypt é um método de criptografia assimétrica que foi desenvolvido em 1996 pelos matemáticos Jeffrey Hoffstein , Jill Pipher e Joseph H. Silverman . É vagamente baseado em problemas de rede que são considerados inquebráveis mesmo com computadores quânticos . No entanto, NTRUEncrypt ainda não foi tão bem pesquisado quanto os métodos mais comuns (por exemplo, RSA).

O algoritmo é patenteado nos EUA; as patentes expirarão em 2021. NTRUEncrypt é padronizado pelo IEEE P1363.1. É usado z. B. das empresas americanas WiKID, Echosat e yaSSL.

Descrição do procedimento

Apenas o algoritmo principal é descrito abaixo. Sozinho, é suscetível a certos ataques; consulte a seção Pré e Pós-processamento .

Salvo indicação em contrário, todos os cálculos ocorrem no anel , ou seja, H. o grau do polinômio nunca excede . A multiplicação “*” é um módulo de convolução cíclico : O produto de dois polinômios e é . ${\ displaystyle R = \ mathbb {Z} _ {q} [X] / (X ^ {N} -1)}$${\ displaystyle N}$${\ displaystyle q}$${\ displaystyle f = [f_ {0}, f_ {1}, \ ldots, f_ {N-1}]}$${\ displaystyle g = [g_ {0}, g_ {1}, \ ldots, g_ {N-1}]}$${\ displaystyle f * g = \ sum _ {i + j \ equiv k \ mod N} f_ {i} \ cdot g_ {j} \ mod q}$

Geração de chave

1. Selecione os parâmetros com .${\ displaystyle N, p, q}$${\ displaystyle q> p, \ operatorname {ggT} (p, q) = 1}$
2. Escolhendo um polinômio aleatório cujos coeficientes estão em {−1, 0, 1}. Os inversos (o módulo inverso ) e (o módulo inverso ) devem existir.${\ displaystyle f}$${\ displaystyle f_ {p}}$${\ displaystyle p}$${\ displaystyle f_ {q}}$${\ displaystyle q}$
3. Geração de um polinômio aleatório cujos coeficientes estão em {−1, 0, 1}.${\ displaystyle g}$
4. ${\ displaystyle h \ equiv f_ {q} * g \ mod q}$é a chave pública, a chave secreta. (Para uma descriptografia mais rápida, ele também pode ser incluído na chave secreta.)${\ displaystyle f}$${\ displaystyle f_ {p}}$

Encriptação

1. Conversão do texto simples em polinômio .${\ displaystyle m}$
2. Escolha de um polinômio aleatório com coeficientes pequenos.${\ displaystyle r}$
3. O polinômio é o texto cifrado.${\ displaystyle e \ equiv pr * h + m \ mod q}$

Decifrar

1. Cálculo de com escolha dos representantes dos coeficientes de no intervalo .${\ displaystyle a \ equiv f * e \ mod q}$${\ displaystyle a}$${\ displaystyle [-q / 2, q / 2)}$
2. Cálculo de .${\ displaystyle c \ equiv f_ {p} * a \ mod p}$
3. O texto simples é obtido convertendo o polinômio na representação de texto.${\ displaystyle c}$

correção

Para polinomial se aplica: . Como os coeficientes são todos pequenos, essa equação também existe no anel . Portanto, a segunda etapa está correta. ${\ displaystyle a}$${\ displaystyle a \ equiv f * e \ equiv f * pr * h + f * m \ mod q = f * pr * f_ {q} * g + f * m \ mod q = pr * g + f * m \ mod q}$${\ displaystyle R}$${\ displaystyle c = f_ {p} * pr * g + f_ {p} * f * m \ mod p = m \ mod p}$

Eficiência

Para acelerar a multiplicação, os polinômios e podem ser escolhidos de forma que muitos coeficientes sejam zero. Para este efeito, os parâmetros são selecionados e na seleção de são coeficientes iguais a 1, coeficientes iguais a -1 e o resto definido como 0. Se você escolher , os coeficientes são iguais a 1, coeficientes iguais a −1 e o restante igual a 0 (Nota: o número de unidades não deve ser igual ao número de unidades menos, caso contrário, o polinômio não pode ser invertido). ${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle d_ {f}, d_ {g}}$${\ displaystyle f}$${\ displaystyle d_ {f}}$${\ displaystyle d_ {f} -1}$${\ displaystyle g}$${\ displaystyle d_ {g}}$${\ displaystyle d_ {g} -1}$

A descriptografia se torna mais eficiente quando o polinômio de acordo com a fórmula com formas. Desde então se aplica, o cálculo do módulo inverso é omitido . Ao escolher os parâmetros, no entanto, é importante garantir que o nível de segurança desejado seja mantido, uma vez que um invasor agora pode pesquisar o conjunto de .${\ displaystyle f}$${\ displaystyle f = 1 + p \ cdot f_ {1}}$${\ displaystyle f_ {1} \ in \ mathbb {Z} _ {p} [X]}$${\ displaystyle f_ {p} ^ {- 1} = 1}$${\ displaystyle p}$${\ displaystyle f_ {1}}$

Além disso, para acelerar a multiplicação, o polinômio pode ser formado de acordo com a fórmula , onde , e pode ser povoado de forma muito esparsa. Os três parâmetros , e , em seguida, tomar o lugar do parâmetro . O aumento na eficiência resulta do fato de que se aplica ( mas ainda tem coeficientes suficientes diferentes de zero) e pode, portanto, ser multiplicado por mais rápido do que por . ${\ displaystyle f}$${\ displaystyle f (x) = 1 + p (f_ {1} (x) * f_ {2} (x) + f_ {3} (x)}$${\ displaystyle f_ {1}}$${\ displaystyle f_ {2}}$${\ displaystyle f_ {3}}$${\ displaystyle d_ {f}}$${\ displaystyle d_ {f1}}$${\ displaystyle d_ {f2}}$${\ displaystyle d_ {f3}}$${\ displaystyle d_ {f1} + d_ {f2} + d_ {f3} <d_ {f}}$${\ displaystyle f_ {1} * f_ {2} + f_ {3}}$${\ displaystyle f_ {1} * f_ {2} + f_ {3}}$${\ displaystyle f}$

Finalmente, em vez de um número primo, um polinômio pode ser escolhido, sendo a escolha mais favorável. Esta variante só aparece na literatura mais antiga. ${\ displaystyle p}$${\ displaystyle p (x) = x + 2}$

segurança

Não há prova formal de segurança para NTRUEncrypt como há para outros métodos criptográficos, mas o método é considerado seguro para parâmetros suficientemente grandes. No início de 2011, foi publicado um trabalho dos criptologistas Damien Stehlé e Ron Steinfeld, no qual é fornecida uma prova de segurança para uma forma modificada de NTRUEncrypt.

Vários ataques em NTRUEncrypt são possíveis. O mais simples deles é experimentar todos os polinômios que são questionados para os parâmetros e . Um ataque mais eficaz é o meio ataque (ataque de encontro no meio ), no qual em vez de um polinômio de comprimento total, dois polinômios com apenas coeficientes são testados ao mesmo tempo. Como resultado, esse ataque precisa apenas da raiz quadrada do número de etapas envolvidas na tentativa e erro primitiva. A redução da grade é ainda mais eficaz , por ex. B. usando o algoritmo LLL . ${\ displaystyle f}$${\ displaystyle N}$${\ displaystyle d_ {f}}$${\ displaystyle N}$${\ displaystyle N / 2}$

Pré e pós-processamento

O algoritmo principal NTRUEncrypt não oferece nenhuma segurança contra invasores que manipulam os dados após a criptografia. Isso pode ser remediado por um preenchimento especial , que o destinatário pode usar para reconhecer cifras manipuladas.

Três desses métodos são conhecidos. SVES-1 e SVES-2 são mais antigos e vulneráveis ​​a ataques que exploram erros de descriptografia. O SVES-3 elimina esses pontos fracos e é descrito no padrão P1363.1 sob a designação SVES.

Parâmetros de nível de segurança de 256 bits

Originalmente, valores entre 167 e 503 eram recomendados para a duração , mas as recomendações foram ajustadas de acordo depois que vários ataques se tornaram conhecidos. Os seguintes parâmetros atendem a todos os ataques atualmente conhecidos (a partir de 9/2011): ${\ displaystyle N}$

Veja também

• Criptografia pós-quântica

Links da web

• Descrição do algoritmo e parâmetros recomendados (registro necessário)
• Descrição do algoritmo (acessível sem registro) (arquivo PDF; 315 kB)
• NTRUEncrypt como código-fonte Java
• Uma implementação NTRUEncrypt da TU Darmstadt está disponível via SVN com o comando svn co --username guest --password guest https://svn.cdc.informatik.tu-darmstadt.de/svn/repos/flexiprovider (O código NTRU está localizado no diretório flexiprovider / trunk / FlexiProvider / src / de / flexiprovider / pqc / ntru /).

Evidência individual

1. ↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: Um Anel Based Public Key Cryptosystem ( Memento do originais datados 30 jan 2013 na Internet Archive ) Info: O arquivo de ligação foi inserido automaticamente e ainda não foi marcada. Verifique o link original e o arquivo de acordo com as instruções e, em seguida, remova este aviso. . In Algorithmic Number Theory (ANTS III), Portland, OR, junho de 1998, JP Buhler (Ed.), Lecture Notes in Computer Science 1423, Springer-Verlag Berlin, 1998, 267-288. @ 1@ 2Modelo: Webachiv / IABot / www.securityinnovation.com
2. ↑ Patente US7031468 : Método e aparelho criptográfico com velocidade aprimorada. Arquivado em 24 de agosto de 2001 , publicado em 18 de abril de 2006 , cessionário: NTRU Cryptosystems, Inc., inventores: Jeffrey Hoffstein, Joseph H. Silverman. (Expiração do período de 20 anos em 24 de agosto de 2021)
3. ↑ dispositivos de autenticação Wikid ( Memento do originais de 14 de Dezembro de 2011 no Internet Archive ) Info: O arquivo de ligação foi inserido automaticamente e ainda não foi marcada. Verifique o link original e o arquivo de acordo com as instruções e, em seguida, remova este aviso. . @ 1@ 2Modelo: Webachiv / IABot / www.wikidsystems.com
4. ↑ Artigo sobre NTRU no Networkworld de 20 de abril de 2011  ( página não disponível , pesquisa em arquivos da web )  Informação: O link foi automaticamente marcado como defeituoso. Por favor, verifique o link de acordo com as instruções e remova este aviso. .@ 1@ 2Modelo: Dead Link / www.networkworld.com  
5. ↑ Biblioteca SSL incorporada CyaSSL .
6. ^ ^{A b c} Hoffstein e Silverman: Otimizações para NTRU .
7. ↑ Damien Stehlé e Ron Steinfeld: Tornando o NTRU tão seguro quanto o problema de pior caso sobre redes ideais . ( ens-lyon.fr [PDF]). 
8. ↑ O impacto das falhas de descriptografia na segurança da criptografia NTRU .
9. ↑ IEEE P1363.1 ( Memento do originais de 29 de junho de 2013 na Internet Archive ) Info: O arquivo de ligação foi inserido automaticamente e ainda não foi marcada. Verifique o link original e o arquivo de acordo com as instruções e, em seguida, remova este aviso. ( PDF ( Memento do originais de 30 de dezembro de 2016 na Internet Archive ) Info: O arquivo de ligação foi inserido automaticamente e ainda não foi verificado Verifique o link original e arquivo de acordo com as. Instruções e, em seguida, remover esta nota. De um esboço) @ 1@ 2Modelo: Webachiv / IABot / grouper.ieee.org @ 1@ 2Modelo: Webachiv / IABot / pdfs.semanticscholar.org