Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-05-19T15:20:50Z No. of bitstreams: 2 arquivototal.pdf: 1103922 bytes, checksum: fee5e8830b60905917fc3ab1fb8c2aae (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-05-19T15:21:56Z (GMT) No. of bitstreams: 2 arquivototal.pdf: 1103922 bytes, checksum: fee5e8830b60905917fc3ab1fb8c2aae (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) / Made available in DSpace on 2015-05-19T15:21:56Z (GMT). No. of bitstreams: 2 arquivototal.pdf: 1103922 bytes, checksum: fee5e8830b60905917fc3ab1fb8c2aae (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) Previous issue date: 2013-08-13 / The encryption algorithm written by Egyptian Taher ElGamal computes discrete logarithms with elements of a finite group G Cyclical. These elements have properties that during the study Chapter 1. Knowing the definitions and some properties studied, we can define and compute discrete logarithms, using knowledge of arithmetic and congruence of Remains and Theorem Remainder of Chinese. We will study public key algorithms, in particular the algorithm written by ElGamal, seeking to understand the diffculties presented by it and show its applications in the field of cryptography. We present a sequence of activities, aimed at students of the first grade of high school, targeting the learning of some subjects covered at work. / O algoritmo de criptografia escrito pelo egípcio Taher ElGamal calcula logaritmos discretos com elementos de um Grupo Cíclico finito G. Esses elementos possuem propriedades que estudaremos no decorrer do capítulo 1. Conhecendo as definições e algumas propriedades estudadas, poderemos definir e calcular logaritmos discretos, utilizando conhecimentos da Aritmética dos Restos e Congruências, bem como o Teorema Chinês dos Restos. Vamos estudar algoritmos de chave pública, em particular o algoritmo escrito por ElGamal, buscando entender as dificuldades apresentadas por ele e mostrar suas aplicações no campo da Criptografia. Apresentaremos uma sequencia de atividades, voltadas para estudantes do primeiro ano do Ensino Médio, visando o aprendizado de alguns assuntos abordados no trabalho.

Os sistemas criptográficos de chave pública amplamente utilizados hoje em dia tem sua segurança baseada na suposição da intratabilidade dos problemas de fatoração de inteiros e do logaritmo discreto, sendo que ambos foram demonstrados inseguros sob o advento dos computadores quânticos. Sistemas criptográficos baseados em Multivariáveis Quadráticas (MQ) utilizam como base o problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito. O problema MQ foi provado como sendo NP-completo e até hoje não se conhece algoritmo, nem mesmo quântico, de tempo polinomial que possa resolver o problema, fazendo com que sistemas criptográficos baseados nesta primitiva mereçam ser investigados e desenvolvidos como reais candidatos a proverem nossa criptografia pós-quântica. Durante a CRYPTO\'2011 Sakumoto, Shirai e Hiwatari introduziram dois novos protocolos de identificação baseados em polinômios multivariáveis quadráticos, os quais chamamos de MQID-3 e MQID-5, e que em especial e pela primeira vez, tem sua segurança reduzida apenas ao problema MQ. Baseados nestas propostas iremos apresentar uma versão aprimorada do protocolo MQID-3 na qual teremos uma redução da comunicação necessária em aproximadamente 9%. / The public-key cryptography widely used nowadays have their security based on the assumption of the intractability of the problems of integer factorization and discrete logarithm, both of which were proven unsafe in the advent of quantum computers. Cryptographic systems based on Multivariate Quadratic polynomials (MQ) are based on the MQ problem, which consists in solve a system of multivariate quadratic polynomials over a finite field. The MQ problem has been proven NP-complete and so far no polynomial time algorithm is known, not even quantum, which would resolve this problem, making worthwhile to be investigated and developed as a real candidate to provide post-quantum cryptography. In CRYPTO\'2011 Sakumoto, Shirai and Hiwatari introduced two new identification protocols based on multivariate quadratic polynomials, which we call MQID-3 and MQID-5, in particular, for the first time, their security is based only on the MQ problem. Using these proposals, we will present an improved version of the protocol MQID-3 that reduces communication by approximately 9%.

Sob o modelo de criptografia de chave pública baseada em identidades (ID-PKC), a própria identidade dos usuários é usada como chave pública, de modo a dispensar a necessidade de uma infra-estrutura de chaves públicas (ICP), na qual o gerenciamento de certificados digitais é complexo. Por outro lado, sistemas nesse modelo requerem uma entidade capaz de gerar chaves secretas. Essa entidade é conhecida por PKG (Private Key Generator); ela possui uma chave-mestra e mantém custódia das chaves secretas geradas a partir dessa chave-mestra. Naturalmente, a custódia de chaves é indesejável em muitas aplicações. O conceito de Criptografia de Chave Pública sem Certificado, ou Certificateless Public Key Cryptography (CL-PKC), foi proposto para que a custódia de chaves fosse eliminada, mantendo, porém, as características de interesse: a não necessidade de uma ICP e a eliminação de certificados digitais. CL-PKC deixa de ser um sistema baseado em identidades, pois é introduzida uma chave pública, gerada a partir de uma informação secreta do usuário. Nesta dissertação, apresentamos a construção de dois esquemas, um CL-PKE e um CL-PKS, baseados em emparelhamentos bilineares sobre curvas elípticas. Ambas propostas: (1) eliminam custódia de chaves; (2) dispensam certificados digitais; (3) são mais eficientes, sob certos aspectos, que esquemas anteriormente publicados; (4) e são seguros contra ataques adaptativos de texto cifrado escolhido (em CL-PKE) e contra ataques adaptativos de mensagem escolhida (em CL-PKS), sob o modelo de oráculos aleatórios. / Under the model of Identity Based Cryptography (ID-PKC), the public key can be the user's identity, therefore it does not require a Public Key Infrastructure (PKI) with its complex management of Digital Certificates. On the other hand, this system requires a Private Key Generator (PKG), a trusted authority who is in possession of a master key and can generate any of the private keys. In this way, PKG can exercise the so-called key escrow, which is undesirable in many applications. The concept of Certificateless Public Key Cryptography (CL-PKC) was proposed in order to remove the key escrow characteristic of IBC, while it does not require PKI neither Digital Certificates to certify the public keys. CL-PKC is no more an IBC because public keys are introduced, to bind the identities with its secret keys. In this thesis we construct two schemes, one CL-PKE and one CL-PKS, based on bilinear pairing functions which: (1) does not allow key escrow by the PKG; (2) does not require Digital Certificates; (3) is more efficient, in some aspects, than previously published CL-PKE and CL-PKS schemes; (4) and is secure in the sense that it is strong against adaptive chosen ciphertext attacks (in CL-PKE) and adaptive chosen message attacks (in CL-PKS), under Random Oracle Model.

Sob o modelo de criptografia de chave pública baseada em identidades (ID-PKC), a própria identidade dos usuários é usada como chave pública, de modo a dispensar a necessidade de uma infra-estrutura de chaves públicas (ICP), na qual o gerenciamento de certificados digitais é complexo. Por outro lado, sistemas nesse modelo requerem uma entidade capaz de gerar chaves secretas. Essa entidade é conhecida por PKG (Private Key Generator); ela possui uma chave-mestra e mantém custódia das chaves secretas geradas a partir dessa chave-mestra. Naturalmente, a custódia de chaves é indesejável em muitas aplicações. O conceito de Criptografia de Chave Pública sem Certificado, ou Certificateless Public Key Cryptography (CL-PKC), foi proposto para que a custódia de chaves fosse eliminada, mantendo, porém, as características de interesse: a não necessidade de uma ICP e a eliminação de certificados digitais. CL-PKC deixa de ser um sistema baseado em identidades, pois é introduzida uma chave pública, gerada a partir de uma informação secreta do usuário. Nesta dissertação, apresentamos a construção de dois esquemas, um CL-PKE e um CL-PKS, baseados em emparelhamentos bilineares sobre curvas elípticas. Ambas propostas: (1) eliminam custódia de chaves; (2) dispensam certificados digitais; (3) são mais eficientes, sob certos aspectos, que esquemas anteriormente publicados; (4) e são seguros contra ataques adaptativos de texto cifrado escolhido (em CL-PKE) e contra ataques adaptativos de mensagem escolhida (em CL-PKS), sob o modelo de oráculos aleatórios. / Under the model of Identity Based Cryptography (ID-PKC), the public key can be the user's identity, therefore it does not require a Public Key Infrastructure (PKI) with its complex management of Digital Certificates. On the other hand, this system requires a Private Key Generator (PKG), a trusted authority who is in possession of a master key and can generate any of the private keys. In this way, PKG can exercise the so-called key escrow, which is undesirable in many applications. The concept of Certificateless Public Key Cryptography (CL-PKC) was proposed in order to remove the key escrow characteristic of IBC, while it does not require PKI neither Digital Certificates to certify the public keys. CL-PKC is no more an IBC because public keys are introduced, to bind the identities with its secret keys. In this thesis we construct two schemes, one CL-PKE and one CL-PKS, based on bilinear pairing functions which: (1) does not allow key escrow by the PKG; (2) does not require Digital Certificates; (3) is more efficient, in some aspects, than previously published CL-PKE and CL-PKS schemes; (4) and is secure in the sense that it is strong against adaptive chosen ciphertext attacks (in CL-PKE) and adaptive chosen message attacks (in CL-PKS), under Random Oracle Model.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Given the evolution of the data communication field, and the resulting increase of the information flow in data, networks security became a major concern. Modern cryptographic methods are mathematically reliable. However their implementation in hardware leaks confidential information through side-channels like power consumption and electromagnetic emissions. Although performance issues are crucial for a hardware design, aspects of robustness against attacks based on side-channel informations have gained much attention in recent years. This work focuses on hardware architectures based on the RSA public-key algorithm, originally proposed in 1977 by Rivest, Shamir and Adleman. This algorithm has the modular exponentiation as its main operation and it is performed through successive modular multiplications. Because the RSA involves integers of 1024 bits or more, the inherent division of modular multiplications became the main concern. The Montgomery algorithm, proposed in 1985, is a largely used method for hardware designs of modular multiplications, because it avoids divisions and all operations are performed in a multiple-precision context with all terms represented in a numerical base, generally, a power of two. This dissertation proposes a systolic architecture able to perform the Montgomery modular multiplication with multiple-precision arithmetic. Following, an improvement to the systolic architecture is presented, through an architecture that computes the Montgomery multiplication by multiplexing the multi-precision arithmetic processes. The multiplexed architecture is employed in the left-to-right square-and-multiply and square-and-multiply always modular exponentiation methods and is subjected to SPA (Simple Power Analysis) and SEMA (Simple Electromagnetic Analysis) side-channel attacks and robustness aspects are analysed. Different word sizes (numerical bases) are applied as well as different input operands. As an improvement to SPA and SEMA attacks, the power consumption and electromagnetic traces are demodulated in amplitude to eliminate the clock harmonics influence in the acquired traces. Finally, interpretations, conclusions and countermeasure propositions to the multiplexed architecture against the implemented side-channel attacks are presented. / Com a expansão da área de comunicação de dados e o consequente aumento do fluxo de informações, a segurança tem se tornado uma grande preocupação. Apesar dos métodos criptográficos modernos serem matematicamente seguros, sua implementação em hardware tende a apresentar fugas de informações confidenciais por canais laterais, tais como consumo de potência e emissões eletromagnéticas. Embora questões de desempenho sejam cruciais para um projeto de hardware, aspectos de robustez contra ataques baseados em fugas de informações por canais laterais tem ganhado maior atenção nos últimos anos. Neste trabalho, explora-se arquiteturas em hardware voltadas para o algoritmo de chave pública RSA, originalmente proposto em 1977 por Rivest, Shamir e Adleman. Este algoritmo possui como principal operação a exponenciação modular, e esta é calculada através de sucessivas multiplicações modulares. Sendo que o RSA envolve números inteiros da ordem de 1024 bits ou mais, a operação de divisão inerente em multiplicações modulares torna-se o principal problema. O algoritmo de Montgomery, proposto em 1985, é um método bastante utilizado na implementação da multiplicação modular em hardware, pois além de evitar divisões, trabalha em um contexto de precisão múltipla com termos representados por bases numéricas, geralmente, potências de dois. Dentro deste contexto, propõe-se inicialmente uma arquitetura sistólica, baseada nas propriedades de aritmética de precisão múltipla do Algoritmo de Montgomery. Em seguida, apresenta-se uma melhoria para a arquitetura sistólica, através de uma arquitetura que realiza a multiplicação modular de Montgomery voltada à multiplexação dos processos aritméticos. A arquitetura multiplexada é empregada nos métodos de exponenciação modular left-to-right square-and-multiply e square-and-multiply always e é submetida a ataques por canais laterais SPA (Simple Power Analysis) e SEMA (Simple Electromagnetic Analysis) e aspectos de robustez da arquitetura multiplexada são analisados para diversos tamanhos de palavras (base numérica do algoritmo de Montgomery). Como proposta de melhoria aos ataques por canais laterais simples, os traços de consumo de potência e emissão eletromagnética são demodulados em amplitude de modo a eliminar a influência das harmônicas do sinal de clock sobre os traços coletados. Por fim, interpretações e conclusões dos resultados são apresentados, assim como propostas de contra-medidas para a arquitetura multiplexada com relação aos ataques por canais laterais realizados.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The expansion of the data communication, due to the large ow of information that pass through these systems has meant that the security becomes an item of constant concern. Even when considering the efficient encryption systems that exists today, which present relevant mathematical protection, some implementations in hardware of these systems will favor the leak of confidential information through side channels attacks, such as power consumption and electromagnetic radiation. Performance issues have fundamental importance in the design of a physical system, however aspects which make the system robust against side channel attacks has gotten more attention nowadays.This work focuses on hardware architectures based on the RSA public key algorithm, proposed by Rivest, Shamir and Adleman in 1977, which presents the modular exponentiation operation, calculated from several modular multiplications, as main operation. The RSA algorithm involves integers in order of 1024 or 2048 bits, so the division inherent in modular multiplications can become a major problem. In order to avoid these divisions, the Montgomery algorithm, proposed in 1985, appears as an efficient alternative. On this context, this dissertation presents a multiplexed architecture based on the properties of the Montgomery's algorithm. Forwarding, an improvement to this architecture is presented, implemented with the randomization of internal memories accesses, in order to increase system robustness against specialized side-channel attacks. Thus, the implemented architecture is exposed to side channels SPA (Simple Power Analysis) and SEMA (Simple Electromagnetig Analysis) and the aspects of security and robustness of the implemented system are evaluated and presented. / A constante expansão dos sistemas de comunicação de dados devido ao grande fluxo de informações que trafegam por estes sistemas tem feito com que a segurança se torne um item de constante preocupação. Mesmo ao considerar-se os eficientes sistemas de criptografia atuais, os quais apresentam relevante proteção matemática, a implementação em hardware destes sistemas tende a propiciar a fuga de informações confidenciais através de ataques por canais laterais, como consumo de potência e emissão eletromagnética. Mesmo sabendo-se que questões de desempenho tem fundamental importância no projeto de um sistema físico, aspectos que tornem o sistema robusto frente a ataques por canais laterais tem obtido maior atenção nos últimos anos. Neste trabalho apresentam-se arquiteturas implementadas em hardware para o cálculo do algoritmo de chave pública RSA, proposto por Rivest, Shamir e Adleman em 1977, o qual tem como principal operarção a exponenciação modular, calculada a partir de várias multiplicações modulares. Sabendo-se que o algoritmo RSA envolve números inteiros da ordem de 1024 ou 2048 bits, a divisão inerente em multiplicações modulares pode tornar-se o grande problema. A fim de que se evite estas divisões, o algoritmo de Montgomery, proposto em 1985, aparece como uma boa alternativa por também trabalhar em um contexto de precisão múltipla e com números na base numérica de potência de dois. Neste contexto apresenta-se inicialmente uma arquitetura multiplexada, baseada nas propriedades de execução do algoritmo de Montgomery. A seguir apresenta-se uma melhoria a esta arquitetura com a implementação da randomização dos acessos as memórias internas, com o objetivo de aumentar a robustez do sistema frente a ataques por canais laterais especializados. Sendo assim, a arquitetura implementada é submetida a ataques por canais laterais SPA (Simple Power Analysis) e SEMA (Simple Electromagnetig Analysis) e os aspectos de segurança e robustez do sistema implementado são analisados e apresentados.

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais. / Certificateless public key cryptography is an alternative model to traditional asymmetric key cryptography, because the public key authentication occurs implicitly during a protocol run, with no need of digital certificates management and distribution. It has the potential to reduce computing costs, and it allows a higher security level than the one in the identity-based model. In this PhD thesis, formal security models for certificateless authenticated key agreement are improved with two independent objectives: (1) to increase the trust level for the partial secret key generating authority on which users rely, and (2) to enable computationally efficient protocols, with significant security properties, such as resistance against attacks from adversaries with full control of the communication channel, and from adversaries who are able to replace users\' public keys by any chosen value. In order to demonstrate that these improvements made are feasible and achieve the objectives, new protocols are proposed in the two-party case. These protocols are proved secure by using reduction techniques for provable security.

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais. / Certificateless public key cryptography is an alternative model to traditional asymmetric key cryptography, because the public key authentication occurs implicitly during a protocol run, with no need of digital certificates management and distribution. It has the potential to reduce computing costs, and it allows a higher security level than the one in the identity-based model. In this PhD thesis, formal security models for certificateless authenticated key agreement are improved with two independent objectives: (1) to increase the trust level for the partial secret key generating authority on which users rely, and (2) to enable computationally efficient protocols, with significant security properties, such as resistance against attacks from adversaries with full control of the communication channel, and from adversaries who are able to replace users\' public keys by any chosen value. In order to demonstrate that these improvements made are feasible and achieve the objectives, new protocols are proposed in the two-party case. These protocols are proved secure by using reduction techniques for provable security.