Elementos de criptologia: uma aplicação da álgebra

Abstract

Nesta monografia, procuramos fazer um estudo sobre alguns sistemas criptográficos. Esta está dividida em seis capítulos. No primeiro capítulo, efectuamos uma abordagem histórica da Criptologia bem como referimos algumas das suas aplicações num passado recente. No segundo capítulo, enunciamos definições e alguns resultados básicos de Teoria dos Números, Álgebra e Álgebra Linear que serão usados nos capítulos 3, 4 e 5. No terceiro capítulo, são estudados sistemas criptográficos clássicos ou simétricos, bem como a sua criptanálise. Estes possibilitam a troca de mensagens secretas entre duas entidades em que é necessário haver, previamente, uma distribuição da chave para manter a segurança da comunicação. Também é necessário que a função de encriptação seja injectiva para que a decifração seja efectuada de forma inequívoca. No quarto capítulo, são estudados sistemas criptográficos de chave pública ou assimétricos, nomeadamente o RSA e o ElGamal, sendo também feita uma breve referência à aritmética das Curvas Elípticas e sua aplicação ao ElGamal. A segurança destes sistemas reside na construção de funções "de sentido único" baseadas na dificuldade de resolução de problemas matemáticos que até ao momento são considerados "computacionalmente inviáveis". É o caso do problema da factorizacão de inteiros, utilizado no RSA, e do problema do logaritmo discreto, utilizado no ElGamal. Neste capítulo também são analisados algoritmos necessários para a implementação dos sistemas. No RSA, analisaremos testes de primalidade probabilística, algoritmos de factorização e possíveis ataques ao sistema; no ElGamal, analisaremos algoritmos de resolução do problema do logaritmo discreto. No quinto capítulo, são estudados sistemas de assinaturas digitais. Apenas nos debruçaremos sobre a assinatura digital RSA - com uma breve alusão às funções "hash" – e na assinatura ElGamal. É de salientar a utilização deste método de autenticação em grande escala na internet, nomeadamente a assinatura utilizando a função "hash" SHA-1, com encriptação RSA. Qualquer assinatura digital envolve dois algoritmos: um para assinar e outro para verificar. Nos capítulos 3, 4 e 5 serão apresentados vários exemplos para ilustrar o funcionamento dos algoritmos. Por último, serão apresentadas algumas conclusões e considerações, enfatizando alguns problemas que continuam em aberto.

In this monograph, our goal is to write about some cryptographic systems. It is divided into six chapters. In chapter one, not only do we develop a historical approach to Cryptology, but also enumerate some of its applications in the recent past. In chapter two, we present several definitions and basic results of Number Theory, Algebra and Linear Algebra, which shall be used on chapters 3, 4 e 5. In chapter three, classical or symmetrical cryptosystems, as well as their cryptanalysis, are subject to a study. These systems enable the exchange of secret messages between two entities, which requires that a previous distribution of the key has taken place, in order to maintain the security of the communication. It is also necessary that the encryption function is one-to-one, so that the decryption shall be taken forth leaving no room for mistake. In chapter four, public-key or asymmetrical cryptosystems are studied, namely RSA and ElGamal. The arithmetic of the Elliptic Curves and its applications to the ElGamal system are also briefly referred to. The security of these systems lies on the elaboration of one-way functions, based on the difficulty in solving mathematical problems that until this moment are considered "computationally infeasible". That is the case of the integers factorization problem, used in RSA, and the discrete logarithm, used in ElGamal. Throughout this chapter, we also analyse some algorithms necessary to the systems' implementation. Concerning RSA, we shall analyse probabilistic primality tests, factorization algorithms and possible attacks to the systems; regarding ElGamal, we will analyse algorithms that provide the solution for the discrete logarithm problem. In chapter five, digital signature systems are studied. We shall lean solely upon the RSA digital signature - with a brief mention to "hash" functions - and the ElGamal signature. This method of authentication has been largely applied on the internet, particularly the signature that uses the "hash" SHA-1 function, with RSA encryption. Any digital signature involves two algorithms: one to sign and another to verify. In chapters 3, 4 e 5 several examples will be laid out, in order to illustrate the outcome of algorithms. Finally, some conclusions and comments are presented, emphasizing some of the problems that remain open.