Tamanho da fonte:
Funções de Mão Única em Criptografia
Última alteração: 2012-11-14
Resumo
Introdução
Os fundamentos da Criptografia moderna estão relacionados à Probabilidade Discreta e à Complexidade de Algoritmos. Uma ferramenta criptográfica deve ser tal que possa ser usada eficientemente de maneira legítima, mas que seu uso ilegítimo seja intratável. Tanto quanto possível, tenta-se demonstrar esta intratabilidade, embora tais demonstrações sejam condicionadas à veracidade de conjecturas (como P não igual a NP ou a inexistência de algoritmo eficiente para fatorar inteiros). Um conceito primordial neste cenário é o de função de mão única.
Uma função é de mão única, ou unidirecional, se e é fácil de computar mas difícil de inverter.
A literatura sobre Criptografia traz diferentes exposições do assunto:
algumas com foco em implementação, outras de divulgação, técnicos que descrevem pormenores de algoritmos e alguns livros iniciam com uma introdução à Teoria de Números e descrevem o criptossistema RSA apenas, sem a pretensão de cobrir o resto da àrea da Criptografia. Há, particularmente em Inglês, uma grande quantidade de livros que tratam da Criptografia como um todo, incluindo seus fundamentos, mas são destinados a uma audiência com considerável maturidade matemática.
Objetivos
O projeto teve como objetivo o estudo de funções de mão única e a produção de uma descrição acessível deste fundamento da Criptografia, destinada a alunos iniciantes em Ciências Exatas.
Metodologia
Sendo o trabalho em área teórica, o método usado naturalmente resumiu-se a leitura.
Resultados
Os requisitos estudados foram complexidade computacional, probabilidade discreta, e tópicos selecionados de Álgebra e Teoria dos Números, usados nas construções candidatas a funções de mão única e
de ferramentas criptográficas básicas.
Duas funções (candidatas) de mão única foram estudadas: a exponenciação modular/logaritmo discreto e quadrado modular/raiz módulo n.
Usando quadrado módulo n obtém-se um sistema de transferência inconsciente permitindo que, por exemplo, Alice envie a Bob duas mensagens, sabendo que ele poderá decriptar uma delas, mas sem saber qual. Também é construído com quadrado modular o gerador pseudoaleatório de Blum-Micali, que produz números aleatórios adequados para Criptografia.
Com exponenciação modular desenvolve-se o esquema de Diffie-Hellman, que permite que dois interlocutores acordem um segredo usando comunicação em público. Também usa-se exponenciação modular na construção do criptossitema de Elgamal, com algoritmos para encriptação/decriptação e assinaturas digitais.
Conclusão
Fica claro o papel fundamental das funções de mão única na Criptografia Moderna, e o texto produzido constitui obra de leitura acessível a alunos ingressantes no Ensino Superior.
Os fundamentos da Criptografia moderna estão relacionados à Probabilidade Discreta e à Complexidade de Algoritmos. Uma ferramenta criptográfica deve ser tal que possa ser usada eficientemente de maneira legítima, mas que seu uso ilegítimo seja intratável. Tanto quanto possível, tenta-se demonstrar esta intratabilidade, embora tais demonstrações sejam condicionadas à veracidade de conjecturas (como P não igual a NP ou a inexistência de algoritmo eficiente para fatorar inteiros). Um conceito primordial neste cenário é o de função de mão única.
Uma função é de mão única, ou unidirecional, se e é fácil de computar mas difícil de inverter.
A literatura sobre Criptografia traz diferentes exposições do assunto:
algumas com foco em implementação, outras de divulgação, técnicos que descrevem pormenores de algoritmos e alguns livros iniciam com uma introdução à Teoria de Números e descrevem o criptossistema RSA apenas, sem a pretensão de cobrir o resto da àrea da Criptografia. Há, particularmente em Inglês, uma grande quantidade de livros que tratam da Criptografia como um todo, incluindo seus fundamentos, mas são destinados a uma audiência com considerável maturidade matemática.
Objetivos
O projeto teve como objetivo o estudo de funções de mão única e a produção de uma descrição acessível deste fundamento da Criptografia, destinada a alunos iniciantes em Ciências Exatas.
Metodologia
Sendo o trabalho em área teórica, o método usado naturalmente resumiu-se a leitura.
Resultados
Os requisitos estudados foram complexidade computacional, probabilidade discreta, e tópicos selecionados de Álgebra e Teoria dos Números, usados nas construções candidatas a funções de mão única e
de ferramentas criptográficas básicas.
Duas funções (candidatas) de mão única foram estudadas: a exponenciação modular/logaritmo discreto e quadrado modular/raiz módulo n.
Usando quadrado módulo n obtém-se um sistema de transferência inconsciente permitindo que, por exemplo, Alice envie a Bob duas mensagens, sabendo que ele poderá decriptar uma delas, mas sem saber qual. Também é construído com quadrado modular o gerador pseudoaleatório de Blum-Micali, que produz números aleatórios adequados para Criptografia.
Com exponenciação modular desenvolve-se o esquema de Diffie-Hellman, que permite que dois interlocutores acordem um segredo usando comunicação em público. Também usa-se exponenciação modular na construção do criptossitema de Elgamal, com algoritmos para encriptação/decriptação e assinaturas digitais.
Conclusão
Fica claro o papel fundamental das funções de mão única na Criptografia Moderna, e o texto produzido constitui obra de leitura acessível a alunos ingressantes no Ensino Superior.