Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T21:50:46Z (GMT). No. of bitstreams: 1 Castro_RafaelDantasde_M.pdf: 1379597 bytes, checksum: 3b065d6b67c5440dc00b0e4663d170d3 (MD5) Previous issue date: 2009 / Resumo: Nesta tese é apresentada uma visão do campo de Assinaturas de Chave Pública sem Certificados (CL-PKC), resultado final de pesquisa empreendida durante o mestrado do autor na Universidade Estadual de Campinas. A abordagem aqui contida tem como principal base a Segurança Demonstrável; analisamos os modelos de segurança de CL-PKC, os esquemas já propostos na literatura, e suas demonstrações de segurança. Contribuímos também alguns novos resultados para a área, especificamente: o estudo da aplicabilidade do Lema da Bifurcação 'a esquemas de CL-PKC (§ 4.3.3); o algumas pequenas otimizações a esquemas seguros (§ 4.4.1); o demonstração de segurança para um esquema cuja segurança ainda era um problema em aberto (§ 4.4.2); o explicação de falhas em demonstrações de segurança de alguns esquemas (§ 4.4.4, § 4.4.5, § 4.4.7); o um ataque desconhecido a um esquema anteriormente suposto seguro (§ 4.4.4); o proposta de um modelo de segurança para agregação de assinaturas no modelo CLPKC (§ 5.4); o proposta de um novo esquema de assinaturas CL-PKC que permite agregação, assim como sua prova de segurança (§ 5.2) / Abstract: In this thesis is presented a broad view of the field of Certificateless Public Key Signatures (CL-PKC), final result of the research undertaken by the author during his masters at the Campinas State University. Our approach is strongly based on the ideas behind Provable Security; we analyze the security models for CL-PKC, all schemes available in the literature, and their security proofs. We also contribute a few novel results, namely: o applicability of the Forking Lemma in the CL-PKC paradigm (§ 4.3.3); o small optimizations to secure schemes (§ 4.4.1); o security proof for a scheme whose security was an open problem (§ 4.4.2); o investigation of the problems in the security proofs of a few schemes (§ 4.4.4, § 4.4.5, § 4.4.7); o an attack on a scheme previously thought to be secure (§ 4.4.4); o proposal of a security model for aggregation of signatures in the CL-PKC paradigm (§ 5.4); o proposal of a new scheme for Certificateless Signatures that allows aggregation, along with its security proof (§ 5.2) / Mestrado / Sistemas de Computação / Mestre em Ciência da Computação

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T08:29:26Z (GMT). No. of bitstreams: 1 Juliato_MarcioRogerio_M.pdf: 2212870 bytes, checksum: a0f8b09f80dbc648772b9b3160c6fd8f (MD5) Previous issue date: 2006 / Resumo: O aumento na comunicação utilizando-se sistemas eletrônicos tem demandado a troca de informações cifradas, permitindo a comunicação entre dois sistemas desconhecidos através de um canal inseguro (como a Internet). Criptografia baseada em curvas elípticas (ECC) é um mecanismo de chave pública que requer apenas que as entidades, que desejam se comunicar, troquem material de chave que é autêntico e possuem a propriedade de ser computacionalmente infactível descobrir a chave privada somente com informações da chave pública. A principal operação de sistemas ECC é a multiplicação de ponto (kP) que gasta 90% de seu tempo de execução na multiplicação em corpos finitos. Assim, a velocidade de um sistema ECC é altamente dependente do desempenho das operações aritméticas em corpos finitos. Nesse trabalho, estudamos a especialização de um processador NIOS2 para aplicações criptográficas em curvas elípticas. Mais precisamente,implementamos operações em corpos finitos e a multiplicação de pontos sobre F2163 como instruções especializadas e periféricos do NIOS2, e as analisamos em termos de área e speedup. Determinamos também, quais implementações s¿ao mais apropriadas para sistemas voltados a desempenho e para ambientes restritos. Nossa melhor implementação em hardware da multiplicação de pontos é capaz de acelerar o cálculo de kP em 2900 vezes, quando comparado com a melhor implementação em software executando no NIOS2. De acordo com a literatura especializada, obtivemos a mais rápida implementação da multiplicação de pontos sobre F2163 , comprovando que bases normais Gaussianas s¿ao bastante apropriadas para implementações em hardware / Abstract: The increase in electronic communication has lead to a high demand for encrypted information exchange between unfamiliar hosts over insecure channels (such as the Internet). Elliptic curve cryptography (ECC) is a public-key mechanism that requires the communicating entities exchange key material that is authentic and has the property of being computationally infeasible to determine the private key from the knowledge of the public key. The fundamental ECC operation is the point multiplication (kP), which spends around 90% of its running time in the finite field multiplication. Therefore, the speed of an ECC scheme is highly dependent on the performance of its underlying finite field arithmetic. In this work, we studied the specialization of the NIOS2 processor for ECC applications. More precisely, we implemented the finite field operations and the point multiplication over F2163 as NIOS2 custom instructions and peripherals, and thus, we analyzed them in terms of area and speedup. We also determined which implementations are best suited for performance-driven and area-constrained environments. Our best hardware implementation of the point multiplication is capable of accelerating the kP computation in 2900 times, when compared to the best software implementation running in the NIOS2. According to the literature, we obtained the fastest point multiplier in hardware over F2163 , proving that Gaussian normal bases are quite appropriate for hardware implementations / Mestrado / Arquitetura e Sistemas de Computação / Mestre em Ciência da Computação

The Collaborative Authentication (co-authentication) system is an authentication system that relies on some or all members of a pre-registered set of secure hardware tokens being concurrently present to an authentication server at the moment of authentication. Previous researchers have compared various embodiments of the co-authentication system to each other including using Quick Response (QR) codes/cellphone cameras and Near Field Communication (NFC) between tokens. This thesis concerns the initial design and implementation of empirical comparative testing mechanisms between one embodiment of the co-authentication system and other commonly used authentication systems. One contribution is the simulated standard user ID and password login in a computer browser and a simulated RSA SecureID ® one time password (OTP) and login with embedded usability testing mechanisms. Another contribution is the development and implementation of a new Bluetooth communication functionality between tokens. A third contribution is the addition of usability testing mechanisms to two versions of this new functionality.

Dans cette thèse, nous nous intéressons à la sécurité de générateurs pseudo-aléatoires et d'implémentations de schémas de signature. Concernant les schémas de signature, nous proposons, dans le cas d'une implémentation répandue de RSA, différentes attaques par injection de faute effectives quelque soit l'encodage du message. Nous présentons par ailleurs une contre-mesure infective prouvée sûre pour protéger le schéma RSA--PSS contre un certain nombre de fautes non aléatoires. Nous étudions également le schéma ECDSA couplé aux techniques d'accélération GLV/GLS. En fonction des implémentations, nous prouvons soit la bonne distribution du nonce utilisé, soit qu'il présente un biais permettant une attaque. Enfin, nous élaborons un outil qui recherche automatiquement des attaques par faute à partir d'une implémentation et d'une politique de faute, outil appliqué avec succès sur des implémentations de RSA et de ECDSA. Concernant les générateurs pseudo-aléatoires algébriques, nous étudions les générateurs non-linéaires et améliorons certaines attaques en diminuant l'information donnée à l'adversaire. Nous nous intéressons également à la sécurité du générateur Micali-Schnorr à travers quelques attaques et une étude statistique de son hypothèse de sécurité. Finalement nous proposons une cryptanalyse de tout schéma à clé publique basé sur la factorisation ou le logarithme discret dont la clé secrète est générée à partir d'un générateur linéaire. / In this thesis, we are interested in the security of pseudorandom number generators and of implementations of signature schemes. Regarding the signature schemes, we propose, in the case of a widespread implementation of RSA, various fault attacks which apply to any padding function. In addition we present a proven secure infective countermeasure to protect the RSA--PSS scheme against some non-random faults. Furthermore we study the ECDSA scheme coupled with the GLV/GLS speed-up techniques. Depending on the implementations, we prove either the good distribution of the used nonce, or that it has a bias, thereby enabling an attack. Finally we develop a tool for automatically finding fault attacks given an implementation and a fault policy, which is successfully applied to some RSA and ECDSA implementations. Regarding pseudorandom number generators, we study the nonlinear ones and improve some attacks by reducing the information available to the adversary. We also are interested in the security of the Micali-Schnorr generator through various attacks and a statistical study of its security assumption. Finally we propose a cryptanalysis of any public-key scheme based on the factorization or the discrete logarithm when the secret key is generated using a linear generator.

Digital signatures, which take the properties of classical signatures, are used to secure the actual content of documents, which can be modified during transmission over an insecure channel. The problems of security and protection of communicating participants are solved by cryptographic techniques. Identity verification, message integrity, credibility, the ownership of documents, and the secure transmission of information over an unsecured channel, are all dealt with in secure communications - Public Key Infrastructure, which uses digital signatures. Nowadays digital signatures are often used to secure data in communication over an unsecured channel. The aim of the following master’s thesis is to familiarize readers with the necessary technological aspects of digital signatures, as well as their advantages and disadvantages. By the time digital signatures are being used they will have to be improved and modified to be secure against more sophisticated attacks. In this paper, proposals of new efficient digital signature schemes and their comparison with current ones are described. Also are examined their implications for computationally weak devices, or deployment in low speed channel transmission systems. After an explanation of cryptography and a description of its basic subjects, digital signatures are introduced. The first chapter describes the possible formatting and architecture of the digital signature. The second part of this master’s thesis is about current digital signature schemes and their properties. Chapter 3 describes some proposals of new efficient digital signature schemes and their comparison to those currently in use. In the practical part, the implementations (in the environment .NET in C#) of two effective digital signature schemes as part of a client-server application are presented and described (Chapter 4). In the last chapter the comparison and analysis of the implemented signature schemes are provided.

En 1978, McEliece introduit un schéma de chiffrement à clé publique issu de la théorie des codes correcteurs d’erreurs. L’idée du schéma de McEliece est d’utiliser un code correcteur dont lastructure est masquée, rendant le décodage de ce code difficile pour toute personne ne connaissant pas cette structure. Le principal défaut de ce schéma est la taille de la clé publique. Dans ce contexte, on se propose d'étudier l'utilisation de codes dont on connaît une représentation compacte, en particulier le cas de codes quais-cyclique ou quasi-dyadique. Les deux familles de codes qui nous intéressent dans cette thèse sont: la famille des codes alternants et celle des sous--codes sur un sous--corps de codes géométriques. En faisant agir un automorphisme $sigma$ sur le support et le multiplier des codes alternants, on saitqu'il est possible de construire des codes alternants quasi-cycliques. On se propose alors d'estimer la sécurité de tels codes à l'aide du textit{code invariant}. Ce sous--code du code public est constitué des mots du code strictement invariant par l'automorphisme $sigma$. On montre ici que la sécurité des codes alternants quasi-cyclique se réduit à la sécurité du code invariant. Cela est aussi valable pour les sous—codes sur un sous--corps de codes géométriques quasi-cycliques. Ce résultat nous permet de proposer une analyse de la sécurité de codes quasi-cycliques construit sur la courbe Hermitienne. En utilisant cette analyse nous proposons des clés compactes pour la schéma de McEliece utilisant des sous-codes sur un sous-corps de codes géométriques construits sur la courbe Hermitienne. Le cas des codes alternants quasi-dyadiques est aussi en partie étudié. En utilisant le code invariant, ainsi que le textit{produit de Schur}et le textit{conducteur} de deux codes, nous avons pu mettre en évidence une attaque sur le schéma de McEliece utilisant des codes alternants quasi-dyadique de degré $2$. Cette attaque s'applique notamment au schéma proposé dans la soumission DAGS, proposé dans le contexte de l'appel du NIST pour la cryptographie post-quantique. / In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the em{invariant code}. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism $sigma$. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the em{Schur product} and the em{conductor} of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters.

No description available.

No description available.

We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks. / Ph. D.

A vast majority of popular communication protocols for the internet employ the use of TLS (Transport Layer Security) to secure communication. As a result, there have been numerous efforts including the introduction of Certificate Transparency logs and Free Automated CAs to improve the SSL certificate ecosystem. Our work highlights the effectiveness of these efforts using the Certificate Transparency dataset as well as certificates collected via full IPv4 scans. We show that a large proportion of invalid certificates still exists and outline reasons why these certificates are invalid and where they are hosted. Moreover, we show that the incorrect use of template certificates has led to incorrect SCTs being embedded in the certificates. Taken together, our results emphasize continued involvement for the research community to improve the web's PKI ecosystem. / Master of Science / Security and Privacy for communication over the internet is increasingly important. TLS (Transport Layer Security) is the most popular protocol used to secure communications over the internet today. This work explores how this protocol has evolved over the past 9 years and how effective the measures undertaken by the community have been to improve the adherence to best practices in the wild. TLS employs the use of certificates to initialize secure communication and make sure the other party is indeed who they say they are. We show that while security has improved over the years, a majority of certificates are invalid and outline reasons why. We also observe the growth of Certificate Transparency logs and show how the use of template certificates cause unexpected issues. Taken together, our results emphasize a continued involvement for the research community to improve the TLS certificate ecosystem.