To protect against brute force attacks, modern password-based authentication systems usually employ mechanisms known as Password Hashing Schemes (PHS). Basically, a PHS is a cryptographic algorithm that generates a sequence of pseudorandom bits from a user-defined password, allowing the user to configure the computational costs involved in the process aiming to raise the costs of attackers testing multiple passwords trying to guess the correct one. Traditional schemes such as PBKDF2 and bcrypt, for example, include a configurable parameter that controls the number of iterations performed, allowing the user to adjust the time required by the password hashing process. The more recent scrypt and Lyra algorithms, on the other hand, allow users to control both processing time and memory usage. Despite these advances, there is still considerable interest by the research community in the development of new (and better) alternatives. Indeed, this led to the creation of a competition with this specific purpose, the Password Hashing Competition (PHC). In this context, the goal of this research effort is to propose a superior PHS alternative. Specifically, the objective is to improve the Lyra algorithm, a PHS built upon cryptographic sponges whose project counted with the authors\' participation. The resulting solution, called Lyra2, preserves the security, efficiency and flexibility of Lyra, including: the ability to configure the desired amount of memory and processing time to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings important improvements when compared to its predecessor: (1) it allows a higher security level against attack venues involving time-memory trade-offs; (2) it includes tweaks for increasing the costs involved in the construction of dedicated hardware to attack the algorithm; (3) it balances resistance against side-channel threats and attacks relying on cheaper (and, hence, slower) storage devices. Besides describing the algorithm\'s design rationale in detail, this work also includes a detailed analysis of its security and performance in different platforms. It is worth mentioning that Lyra2, as hereby described, received a special recognition in the aforementioned PHC competition. / Para proteger-se de ataques de força bruta, sistemas modernos de autenticação baseados em senhas geralmente empregam algum Esquema de Hash de Senhas (Password Hashing Scheme - PHS). Basicamente, um PHS é um algoritmo criptográfico que gera uma sequência de bits pseudo-aleatórios a partir de uma senha provida pelo usuário, permitindo a este último configurar o custo computacional envolvido no processo e, assim, potencialmente elevar os custos de atacantes testando múltiplas senhas em paralelo. Esquemas tradicionais utilizados para esse propósito são o PBKDF2 e bcrypt, por exemplo, que incluem um parâmetro configurável que controla o número de iterações realizadas pelo algoritmo, permitindo ajustar-se o seu tempo total de processamento. Já os algoritmos scrypt e Lyra, mais recentes, permitem que usuários não apenas controlem o tempo de processamento, mas também a quantidade de memória necessária para testar uma senha. Apesar desses avanços, ainda há um interesse considerável da comunidade de pesquisa no desenvolvimento e avaliação de novas (e melhores) alternativas. De fato, tal interesse levou recentemente à criação de uma competição com esta finalidade específica, a Password Hashing Competition (PHC). Neste contexto, o objetivo do presente trabalho é propor uma alternativa superior aos PHS existentes. Especificamente, tem-se como alvo melhorar o algoritmo Lyra, um PHS baseado em esponjas criptográficas cujo projeto contou com a participação dos autores do presente trabalho. O algoritmo resultante, denominado Lyra2, preserva a segurança, eficiência e flexibilidade do Lyra, incluindo a habilidade de configurar do uso de memória e tempo de processamento do algoritmo, e também a capacidade de prover um uso de memória superior ao do scrypt com um tempo de processamento similar. Entretanto, ele traz importantes melhorias quando comparado ao seu predecessor: (1) permite um maior nível de segurança contra estratégias de ataque envolvendo trade-offs entre tempo de processamento e memória; (2) inclui a possibilidade de elevar os custos envolvidos na construção de plataformas de hardware dedicado para ataques contra o algoritmo; (3) e provê um equilíbrio entre resistância contra ataques de canal colateral (\"side-channel\") e ataques que se baseiam no uso de dispositivos de memória mais baratos (e, portanto, mais lentos) do que os utilizados em computadores controlados por usuários legítimos. Além da descrição detalhada do projeto do algoritmo, o presente trabalho inclui também uma análise detalhada de sua segurança e de seu desempenho em diferentes plataformas. Cabe notar que o Lyra2, conforme aqui descrito, recebeu uma menção de reconhecimento especial ao final da competição PHC previamente mencionada.

Este documento apresenta o Lyra, um novo esquema de derivação de chaves, baseado em esponjas criptográficas. O Lyra foi projetado para ser estritamente sequencial, fornecendo um nível elevado de segurança mesmo contra atacantes que utilizem múltiplos núcleos de processamento, como uma GPU ou FPGA. Ao mesmo tempo possui uma implementação simples em software e permite ao usuário legítimo ajustar o uso de memória e tempo de processamento de acordo com o nível de segurança desejado. O Lyra é, então, comparado ao scrypt, mostrando que esta proposta fornece um nível se segurança mais alto, além de superar suas deficiências. Caso o atacante deseje realizar um ataque utilizando pouca memória, o tempo de processamento do Lyra cresce exponencialmente, enquanto no scrypt este crescimento é apenas quadrático. Além disto, para o mesmo tempo de processamento, o Lyra permite uma utilização maior de memória, quando comparado ao scrypt, aumentando o custo de ataques de força bruta. / This document presents Lyra, a password-based key derivation scheme based on cryptographic sponges. Lyra was designed to be strictly sequential, providing strong security even against attackers that use multiple processing cores, such as FPGAs or GPUs. At the same time, it is very simple to implement in software and allows legitimate users to tune its memory and processing costs according to the desired level of security. We compare Lyra with scrypt, showing how this proposal provides a higher security level and overcomes limitations of scrypt. If the attacker wishes to perform a low-memory attack against the algorithm, the processing cost grwos expontetialy, while in scrypt, this growth is only quadratic. In addition, for an identical processing time, Lyra allows for a higher memory usage than its counterparts, further increasing the cost of brute force attacks.

Hash-based signature schemes are a class of post-quantum algorithms that usually consist of hash-trees built upon OTS solutions. These schemes have small key sizes, eficient processing and are simple to implement, while their security properties rely basically on the pre-image or collision resistance of the their underlying hash function. Despite such advantages, however, they have relatively large signature sizes compared to traditional signature algorithms. One way of tackling this issue is to reduce the sizes of their underlying OTS algorithms. Besides that, in applications where signature verifications are done much more frequently than signature generation (e.g. trusted software distribution), it is desirable that signature verification has less overhead than signature generation. In this work, two contributions are presented to tackle these issues. The first one is a probabilistic technique that, with negligible processing overhead, allows reductions in the underlying OTS signature sizes; namely, up to 12.5% average size reduction can be achieved depending on the w parameter chosen for the signature (however, for w = 4 the reduction is only 0.2%). The second contribution is a novel OTS scheme which has all advantages of W-OTS and W-OTS+ and yet has much faster signature verification times at the cost of slightly slower signature generation times. / Esquemas de assinaturas baseadas em hash são uma classe de algoritmos pós-quânticos que basicamente consistem em árvores de hash construídas em cima de soluções de assinaturas unitárias (OTS). Tais esquemas possuem tamanhos pequenos de chaves, processamento eficiente e são simples de se implementar, enquanto que a segurança desses esquemas baseia-se na resistência à pré-imagem ou à colisão das funções de hash utilizadas. Apesar dessas vantagens, eles possuem tamanhos de assinaturas relativamente grandes comparados aos algoritmos tradicionais de assinatura. Nesse caso, uma forma de lidar com essa questão é reduzir os tamanhos de assinatura das OTS utilizadas. Além disso, em aplicações em que se faz muito mais verificações de assinatura do que gerações de assinatura, é desejável que a vericação seja significativamente mais rápida do que a geração. Nesse trabalho, duas contribuições são apresentadas para mitigar os problemas acima mencionados. A primeira é uma técnica probabilística que permite a redução do tamanho das assinaturas nas OTS utilizadas com custo adicional de processamento desprezível, isto é, pode-se alcançar uma redução média de até 12.5% dependendo do valor de w escolhido para a assinatura (no entanto, para w = 4 a redução é de apenas 0.2%). A segunda contribuição é um esquema inovador de assinatura digital que possui todas as vantagens do W-OTS e do W-OTS+, além de possuir verificação bem mais rápida do que estes em troca de uma geração de assinatura um pouco mais lenta.

The conventional digital signature schemes widely used today may have their security threatened with the possibility of the rising of a large quantum computer. Moreover, such schemes are not entirely suitable for utilization on very constrained-resource platforms. Therefore, there is a need to look at alternatives that present reasonable security in the medium and long term, in addition to attaining acceptable performance when few resources are available. This work provides more efficient multivariate and hash-based post-quantum digital signatures and targets the deployment in scenarios like Internet of Things and Wireless Sensor Networks where the typical devices are very resource-constrained. In the context of multivariable quadratic digital signatures we describe a new technique that attempts to minimize the main drawbacks of these schemes, the large key sizes. The new technique explores certain structures compact matrix rings. Some of the analyzed matrix rings are not secure (one of the attacks runs in polynomial time). Other less compact matrix rings are investigated and they apparently do not suffer a polynomial time attack, but unfortunately are still far from deployment on very constrained platforms. On the other hand, this work describes a method for hash-based signatures providing a 2/3 reduction of the signature sizes in the Merkle-Winternitz multi-time signature scheme. In fact, the signature sizes constitute the main bottleneck of these schemes. The improvement also leads to a 2/3 reduction in the run times (key generation, signing and verifying) and in energy consumption for all these operations on an AVR ATmega128L microcontroller, typically found in Wireless Sensor Networks. This result is much more promising for the deployment in an IoT scenario. / Os esquemas convencionais de assinatura digital mais usados na atualidade têm sua segurança ameaçada com a possibilidade da construção de um computador quântico de grande porte. Ademias, tais esquemas não têm se mostrado completamente adequados para uso em plataformas com recursos computacionais extremamente escassos. Surge então a necessidade da busca por alternativas que satisfaçam as condições de segurança a médio e longo prazo, além de apresentarem desempenho razoável quando poucos recursos computacionais estão disponíveis. Este trabalho obtém assinaturas digitais pós-quânticas multivariadas quadráticas e baseadas em hash mais eficientes e tem o intuito de torna-las práticas em cenários como Internet das Coisas e Redes de Sensores Sem Fio (RSSF), caracterizados por apresentarem dispositivos com recursos computacionais limitados. No contexto de assinaturas multivariadas quadráticas, descreve-se uma nova técnica que tenta minimizar o principal gargalo desses esquemas, o grande tamanho de chaves. A nova técnica explora certos anéis matriciais com estrutura compacta. Mostra-se que alguns dos anéis analisados não são seguros (um dos ataques apresenta tempo polinomial), enquanto outros anéis menos compactos aparentam não sofrer ataque polinomial, mas infelizmente ainda não são adequados para uso em dispositivos muito restritos. Por outro lado, descreve-se um método para obter assinaturas digitais baseadas em hash que fornece redução das assinaturas para 2/3 do tamanho original do esquema multi-time Merkle-Winternitz. De fato, o tamanho das assinaturas constitui o principal gargalo desses esquemas, A melhoria também acarreta uma redução em 2/3 nos tempos de execução (geração de chave, geração de assinaturas e verificação de assinatura) e no consumo de energia para essas operações quando executadas em um microcontrolador AVR tipicamente usado em Redes de Sensores Sem Fio, o AT-mega 128L. Este resultado torna-se promissor para implantação de assinaturas baseadas em hash no cenário de Internet das Coisas.

O sistema de televisão é considerado o principal meio de comunicação e entretenimento no Brasil. Com o início das transmissões do sistema de televisão digital brasileiro no final de 2007, os principais impactos da digitalização do sistema de TV são: a alta definição de imagens e som, a mobilidade e a portabilidade. Com o tempo, outras funcionalidades serão incorporadas: a multiprogramação (mais de um programa no mesmo canal) e a interatividade. E é a partir da TV interativa que passa a ser possível o oferecimento de serviços para a população. Este trabalho tem como objetivo sistematizar as questões relacionadas com segurança no âmbito da televisão digital terrestre, além de propor e avaliar contribuições para uma arquitetura de segurança considerando o cenário expandido da televisão digital brasileira; especialmente no que tange a proteção de direitos autorais em TV aberta e a autenticação de aplicativos e serviços para TV interativa. A pesquisa realizada considera a realidade brasileira, suas necessidades específicas e as tecnologias disponíveis mais adequadas a elas, viabilizando o uso de serviços com alto valor agregado. Para atingir estes objetivos, foi realizado um amplo levantamento de tecnologias e sistemas existentes relacionados com o tema de segurança em TV digital. Com base neste levantamento, o trabalho apresenta uma sistematização da segurança para a televisão digital terrestre e aberta no Brasil na qual são identificados casos de uso e requisitos. É proposto o SPDA-BR, um sistema de proteção de direitos autorais adequado ao parque de televisores nacional e com menor impacto no custo de receptores; é proposto também o AUTV, um mecanismo de autenticação de aplicativos flexível (que possa ser utilizada para atualização de software, instalação de drivers, aplicativos interativos), compatível com padrões abertos e com a ICP Brasil. Esta dissertação forneceu subsídios para a escrita da norma de segurança para o Sistema Brasileiro de Televisão Digital, gerou publicações de artigos científicos e técnicos, e a comprovação de viabilidade, tanto do SPDA-BR como do AUTV, através de simulações e prova de conceito, respectivamente. / In Brazil, the television system is considered an important source of communication and entertainment. The Brazilian digital transmissions started on December 2007 and first offered functionalities were the high definition, mobility and portability. In a later moment other functionalities will be added: multiprogramming (more than one service per channel) and interactivity. With the interactivity it is possible to offer digital services to the public. This work goals are to present a systematic DTV security issues overview, to propose and analyze DTV security issues contributions; specifically to the digital rights protection, considering free to air DTV, and the services and applications to interactive TV. This research considers the Brazillian requirements and identifies the most suitable technologies to these requirements, allowing high value services integration to the television system. In order to achieve these goals, it was done a wide state of the art research and the DTV security use cases identification and its requirements specification. The SPDA-BR and AUTV were proposed. The SPDA-BR is a digital rights protection system suitable to the Brazilian scenario with the minimum cost impact. The AUTV is a flexible authentication mechanism (that can be applied to software update, driver installation and interactive DTV applications), compatible to the open standards and to the Brazilian Public Key Cryptographic Infrastructure. This text contributed to the DTV Brazilian system, generated scientific and technical publications, and specified as well as proved the feasibility of both SPDA-BR and AUTV, through simulation and proof of concept, respectively.

Made available in DSpace on 2016-12-23T14:00:40Z (GMT). No. of bitstreams: 1 FACE.pdf: 89333 bytes, checksum: 9fe2d3791aae56820ee8b6646c8b46fd (MD5) Previous issue date: 2003-06-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Trata-se de uma abordagem teórica sobre Propriedade Intelectual com ênfase em Trade Secrets como barreira à entrada. Os avanços em criptologia no campo da matemática podem vir a se somar aos esforços teóricos desenvolvidos em Microeconomia em Organização Industrial. Neste contexto, a criptologia é resgatada historicamente e são apresentadas suas principais funções na Propriedade Intelectual, em especial no Trade Secrets. Questiona-se aqui: Por que as empresas criptografam seus processos produtivos? A propriedade intelectual em especial os Trade Secrets tem desempenhado importante papel, enquanto barreira à entrada na economia contemporânea? Como a criptologia e seus respectivos desenvolvimentos na matemática podem contribuir para o fortalecimento do segredo industrial? Percebe-se que apesar da presença marcante da criptografia e dos bens incorpóreos na Economia Contemporânea, ainda são escassas as análises teóricas, os estudos de caso e os bancos de dados sobre Propriedade Intelectual e principalmente, sobre Trade Secrets. Contribui ao explicitar seus conceitos e alertar para a importância de intensificação de pesquisa científica sobre o tema possibilitando, dessa forma, uma melhor compreensão da dinâmica econômica empresarial na atualidade. / This work presents a theoretical approach on intellectual property with emphasis in trade secrets as entry barriers. Progress in cryptology in the field of the mathematics can be added to the theoretical efforts developed in microeconomics in industrial organization. In this context, cryptology is rescued historically and its main functions are presented in the intellectual property, especially in trade secrets. This research questions: Why do the firms cryptograph their productive processes? Has intellectual property, especially trade secrets, been playing an important role as a barrier to entry in the contemporary economy? How can cryptology and its respective developments in mathematics contribute to the strengthening of the industrial secret? It is noticed that in spite of the outstanding presence of cryptography and of the incorporeal goods in the contemporary economy, the theoretical analyses are still scarce, as are case studies and databases on intellectual property and mainly, on trade secrets. This research contributes to explication of its concepts and warns about the importance of intensification of scientific research on this topic, in order to reach a better understanding of managerial economical dynamics at the present time.

O sistema de televisão é considerado o principal meio de comunicação e entretenimento no Brasil. Com o início das transmissões do sistema de televisão digital brasileiro no final de 2007, os principais impactos da digitalização do sistema de TV são: a alta definição de imagens e som, a mobilidade e a portabilidade. Com o tempo, outras funcionalidades serão incorporadas: a multiprogramação (mais de um programa no mesmo canal) e a interatividade. E é a partir da TV interativa que passa a ser possível o oferecimento de serviços para a população. Este trabalho tem como objetivo sistematizar as questões relacionadas com segurança no âmbito da televisão digital terrestre, além de propor e avaliar contribuições para uma arquitetura de segurança considerando o cenário expandido da televisão digital brasileira; especialmente no que tange a proteção de direitos autorais em TV aberta e a autenticação de aplicativos e serviços para TV interativa. A pesquisa realizada considera a realidade brasileira, suas necessidades específicas e as tecnologias disponíveis mais adequadas a elas, viabilizando o uso de serviços com alto valor agregado. Para atingir estes objetivos, foi realizado um amplo levantamento de tecnologias e sistemas existentes relacionados com o tema de segurança em TV digital. Com base neste levantamento, o trabalho apresenta uma sistematização da segurança para a televisão digital terrestre e aberta no Brasil na qual são identificados casos de uso e requisitos. É proposto o SPDA-BR, um sistema de proteção de direitos autorais adequado ao parque de televisores nacional e com menor impacto no custo de receptores; é proposto também o AUTV, um mecanismo de autenticação de aplicativos flexível (que possa ser utilizada para atualização de software, instalação de drivers, aplicativos interativos), compatível com padrões abertos e com a ICP Brasil. Esta dissertação forneceu subsídios para a escrita da norma de segurança para o Sistema Brasileiro de Televisão Digital, gerou publicações de artigos científicos e técnicos, e a comprovação de viabilidade, tanto do SPDA-BR como do AUTV, através de simulações e prova de conceito, respectivamente. / In Brazil, the television system is considered an important source of communication and entertainment. The Brazilian digital transmissions started on December 2007 and first offered functionalities were the high definition, mobility and portability. In a later moment other functionalities will be added: multiprogramming (more than one service per channel) and interactivity. With the interactivity it is possible to offer digital services to the public. This work goals are to present a systematic DTV security issues overview, to propose and analyze DTV security issues contributions; specifically to the digital rights protection, considering free to air DTV, and the services and applications to interactive TV. This research considers the Brazillian requirements and identifies the most suitable technologies to these requirements, allowing high value services integration to the television system. In order to achieve these goals, it was done a wide state of the art research and the DTV security use cases identification and its requirements specification. The SPDA-BR and AUTV were proposed. The SPDA-BR is a digital rights protection system suitable to the Brazilian scenario with the minimum cost impact. The AUTV is a flexible authentication mechanism (that can be applied to software update, driver installation and interactive DTV applications), compatible to the open standards and to the Brazilian Public Key Cryptographic Infrastructure. This text contributed to the DTV Brazilian system, generated scientific and technical publications, and specified as well as proved the feasibility of both SPDA-BR and AUTV, through simulation and proof of concept, respectively.

The conventional digital signature schemes widely used today may have their security threatened with the possibility of the rising of a large quantum computer. Moreover, such schemes are not entirely suitable for utilization on very constrained-resource platforms. Therefore, there is a need to look at alternatives that present reasonable security in the medium and long term, in addition to attaining acceptable performance when few resources are available. This work provides more efficient multivariate and hash-based post-quantum digital signatures and targets the deployment in scenarios like Internet of Things and Wireless Sensor Networks where the typical devices are very resource-constrained. In the context of multivariable quadratic digital signatures we describe a new technique that attempts to minimize the main drawbacks of these schemes, the large key sizes. The new technique explores certain structures compact matrix rings. Some of the analyzed matrix rings are not secure (one of the attacks runs in polynomial time). Other less compact matrix rings are investigated and they apparently do not suffer a polynomial time attack, but unfortunately are still far from deployment on very constrained platforms. On the other hand, this work describes a method for hash-based signatures providing a 2/3 reduction of the signature sizes in the Merkle-Winternitz multi-time signature scheme. In fact, the signature sizes constitute the main bottleneck of these schemes. The improvement also leads to a 2/3 reduction in the run times (key generation, signing and verifying) and in energy consumption for all these operations on an AVR ATmega128L microcontroller, typically found in Wireless Sensor Networks. This result is much more promising for the deployment in an IoT scenario. / Os esquemas convencionais de assinatura digital mais usados na atualidade têm sua segurança ameaçada com a possibilidade da construção de um computador quântico de grande porte. Ademias, tais esquemas não têm se mostrado completamente adequados para uso em plataformas com recursos computacionais extremamente escassos. Surge então a necessidade da busca por alternativas que satisfaçam as condições de segurança a médio e longo prazo, além de apresentarem desempenho razoável quando poucos recursos computacionais estão disponíveis. Este trabalho obtém assinaturas digitais pós-quânticas multivariadas quadráticas e baseadas em hash mais eficientes e tem o intuito de torna-las práticas em cenários como Internet das Coisas e Redes de Sensores Sem Fio (RSSF), caracterizados por apresentarem dispositivos com recursos computacionais limitados. No contexto de assinaturas multivariadas quadráticas, descreve-se uma nova técnica que tenta minimizar o principal gargalo desses esquemas, o grande tamanho de chaves. A nova técnica explora certos anéis matriciais com estrutura compacta. Mostra-se que alguns dos anéis analisados não são seguros (um dos ataques apresenta tempo polinomial), enquanto outros anéis menos compactos aparentam não sofrer ataque polinomial, mas infelizmente ainda não são adequados para uso em dispositivos muito restritos. Por outro lado, descreve-se um método para obter assinaturas digitais baseadas em hash que fornece redução das assinaturas para 2/3 do tamanho original do esquema multi-time Merkle-Winternitz. De fato, o tamanho das assinaturas constitui o principal gargalo desses esquemas, A melhoria também acarreta uma redução em 2/3 nos tempos de execução (geração de chave, geração de assinaturas e verificação de assinatura) e no consumo de energia para essas operações quando executadas em um microcontrolador AVR tipicamente usado em Redes de Sensores Sem Fio, o AT-mega 128L. Este resultado torna-se promissor para implantação de assinaturas baseadas em hash no cenário de Internet das Coisas.

Este trabalho revisita a teoria do escopo formulada por Katharina Reiß e Hans Vermeer em Grundlegung einer allgemeinen Translationstheorie (1984) a fim de investigar como os conceitos de “tradução comunicativa” e “tradução equivalente” podem ser aplicados a uma nova tradução do criptograma presente em “The Gold-Bug” (1843), de Edgar Allan Poe. Embora o conto tenha mais de vinte traduções diferentes para o português brasileiro, a necessidade de uma nova tradução justifica-se pela insuficiência de todas aquelas existentes no que diz respeito ao tratamento literário dos problemas especiais suscitados pelo criptograma e pela decifração deste no interior da narrativa. A importância da criptologia na gênese, na recepção e na posterior influência de “The Gold- Bug” é demonstrada através de exemplos e argumentos, e a seguir uma nova tradução do criptograma é proposta com o objetivo de produzir em português brasileiro um texto dotado das mesmas qualidades literárias e raciocinativas que resultaram na imensa popularidade do conto e na elevação de Poe ao status de gênio ainda no século XIX. / This paper presents a brief summary of the Skopostheorie proposed by Katharina Reiß and Hans Vermeer in Grundlegung einer allgemeinen Translationstheorie (1984) in order to assess the way in which the concepts of “communicative translation” and “equivalent translation” could be applied to a new translation of the cryptogram found in Edgar Allan Poe’s short-story, “The Gold-Bug” (1843). There are over twenty translations of the story into Brazilian Portuguese, but a new effort is nonetheless in order in view of the insufficiency of all existing translations with regard to the literary treatment of the special problems posed by the cipher and Legrand’s decipherment. The important role played by cryptology in the genesis, reception and later influence of “The Gold-Bug” is demonstrated by means of examples and arguments, and finally a new translation of the cryptogram is proposed with the aim of producing, in Brazilian Portuguese, a text with the same literary and ratiocinative qualities which eventually led to the tale’s immense popularity and Poe’s rise to the status of “genius” still in the 19th century.

Orientador: Prof. Dr. Jerônimo Cordoni Pellegrini / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2017. / Esse trabalho tem como objetivo mostrar como problemas de difícil solução, em especial o problema dos resíduos quadráticos, podem ser usados para desenvolver criptossistema com segurança demonstrável, com algumas aplicações que podem ser desenvolvidas com alunos de ensino fundamental e médio. Faz-se um resumo da história da criptografia, desde a Cifra de César e passando por diversos criptossistemas historicamente famosos, até chegar ao sigilo perfeito do one-time pad. São trabalhados também alguns conceitos matemáticos necessários, como as funções de mão única e uma breve explicação de algumas funções conjecturadas de mão única, que podem ser usadas em sistemas criptográficos seguros. Em seguida, apresenta-se os geradores de números pseudo-aleatórios, em especial o de Blum-Blum-Shub por empregar resíduos quadráticos. A seguir, há uma breve apresentação das funções de hash e do problema do aniversário associado a elas, com uma função de hash construída baseada no gerador de Blum-Blum-Shub. Também importante é a aplicação na encriptação com chave pública, em especial o criptossistema de Rabin, que também é usado para estabelecer um sistema de votação com base no homomorfismo apresentado por esse sistema. Para finalizar, fala-se sobre as provas de conhecimento zero e como as raízes quadradas módulo N podem ser utilizadas para isso, em particular com o Protocolo de Feige-Fiat-Shamir. Uma aplicação para a sala de aula é dada na forma de um leilão, utilizando o conceito da dificuldade da raiz quadrada modular. / The main objective of this work is to show how hard to solve problems, specially the problem of quadratic residuality, can be used to create cryptographic algorithms with provable security. Some applications could be done with students from elementary and high school. We will start with a brief history of cryptography, from Cesar Cipher and going through several famous cryptosystems until the perfect secrecy of the one-time pad. We will work in a few basic concepts, such as one-way functions and a succinct explanation on some functions that are conjectured to be one-way and can be used in provably secure cryptographic systems. We choose the modular squaring to show on the following chapters how one-way functions are used to build several algorithms (pseudo-random number generators, hash functions, public key encryption, a voting system based on a homomorphic cryptosystem and, at last, zero-knowledge proofs). We will provide a classroom example in the ways of an auction, using the difficulty of the modular square root.