Identy based cryptography has been, for a few recent years, the most active area of research and currently is of a great interest to the researchers groups. In general case the root of ID based cryptography is that user identifying data is used like a public key and so is no need of certificates for the user authentification. In this work we survey a few basic the most influent cryptoschemes. We attempt to answer what is needed for constructing an efficient IBE scheme. There are trustworthy cryptoschemes that uses elliptic curves and bilinear pairings in nowadays. We use these mathematical implements for efficient cryptoscheme too. And finally, there is a pilot software realization for this scheme.

In this thesis, the work of Menezes on the isomorphism classes of elliptic curves over finite fields of characteristic two is studied. Basic definitions and some facts of the elliptic curves required in this context are reviewed and group structure of elliptic curves are constructed. A fairly detailed investigation is made for the isomorphism classes of elliptic curves due to Menezes and Schoof. This work plays an important role in Elliptic Curve Digital Signature Algorithm. In this context, those isomorphism classes of elliptic curves recommended by National Institute of Standards and Technology are listed and their properties are discussed.

Made available in DSpace on 2014-06-11T19:27:09Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-11-18Bitstream added on 2014-06-13T18:55:35Z : No. of bitstreams: 1 flose_vbs_me_rcla.pdf: 506170 bytes, checksum: ee89356ded1c14f6f5c21428bb68671a (MD5) / Com o crescimento da comunicação nos dias atuais, a segurança na troca de informa- ções tem se tornado cada vez mais importante o que tem dado destaque a Criptografia. A criptografia consiste de técnicas baseadas em conceitos matemáticos que tem por objetivo transmitir informações sigilosas forma segura através de canais monitorados por terceiros. Um ramo da Criptografia que vem crescendo está ligado ao estudo de curvas elípticas, que é uma das áreas mais ricas da matemática. O nome curvas elípticas é de certa forma enganoso, pois diferente do sentido literal da palavra, que leva a pensar em elipses, se trata de equações relacionadas a um determinado tipo de curva algébrica. Neste trabalho, as curvas elípticas serão estudadas do ponto de vista da álgebra e da teoria dos números com o objetivo de conhecer a Criptografia de Curvas Elípticas que é uma variação do Problema do Logaritmo Discreto / With the growth of communication these days, security in exchange for information has become increasingly important what has given prominence to Cryptography. Encryption techniques is based on concepts mathematical aims to transmit sensitive information securely through channels monitored by third parties. A branch of cryptography that has growing up is connected to the study of elliptic curves, which is one of the most rich mathematics. The name elliptic curves is somewhat misleading, as di erent from the literal sense of the word, which makes one think of ellipses if equations is related to a certain type of algebraic curve. in this work, elliptic curves are studied from the viewpoint of algebra and of number theory in order to know the Curve Cryptography Elliptic is a variation of the discrete logarithm problem

De nombreuses applications imposent des contraintes de sécurité élevées (notamment au sens confidentialité et intégrité des informations manipulées). Ma thèse s'intéresse à l'accélération matérielle du système de cryptographie asymétrique basé sur les courbes elliptiques (ECC). L'environnement des systèmes visés étant rarement maîtrisé, je prends en compte l'existence potentielle d'attaquants avec un accès physique au circuit.C’est dans ce contexte qu’un crypto-processeur très flexible, compatible aussi bien avec des cibles ASIC que FPGA, a été développé. Dans le but de choisir des protections contre les attaques dites matérielles (analyse de consommation, génération de fautes, etc.), j’évalue la sécurité vis-à-vis des attaques par canaux cachés et le coût de la contre-mesure basée sur l'unification des opérations élémentaires sur des courbes elliptiques. En montant une nouvelle attaque contre un circuit mettant en œuvre des courbes quartiques de Jacobi, je montre qu’il est possible de détecter la réutilisation d’opérandes. Des expérimentations réelles m’ont permis de retrouver le secret en exploitant seulement quelques traces de puissance consommée. Je présente aussi une nouvelle protection permettant de choisir un compromis entre le niveau de sécurité, les performances et le coût. Elle est basée sur une accélération par fenêtrage aléatoire et l'utilisation optimisée d'opérations fictives. / Many applications require achieving high security level (confidentiality or integrity). My thesis is about hardware acceleration of asymmetric cryptography based on elliptic curves (ECC). These systems are rarely in a controlled environment. With this in mind, I consider potential attackers with physical access to the cryptographic device.In this context, a very flexible crypto-processor was developed that can be implemented as an ASIC or on FPGAs. To choose protections against physical attacks (power consumption analysis, fault injection, etc), I evaluate the security against side-channel attacks and the cost of the counter-measure based on operation unification. By mounting a new attack against a chip using Jacobi quartic curves, I show that re-using operands is detectable. By exploiting only some power consumption traces, I manage to recover the secret. I present also a new counter-measure allowing finding a compromise between security level, performances, and overheads. It uses random windows to accelerate computation, mixed to an optimized usage of dummy operations.

Esta dissertação apresenta o desenvolvimento de um novo algoritmo de criptografia de chave pública. Este algoritmo apresenta duas características que o tornam único, e que foram tomadas como guia para a sua concepção. A primeira característica é que ele é semanticamente seguro. Isto significa que nenhum adversário limitado polinomialmente consegue obter qualquer informação parcial sobre o conteúdo que foi cifrado, nem mesmo decidir se duas cifrações distintas correspondem ou não a um mesmo conteúdo. A segunda característica é que ele depende, para qualquer tamanho de texto claro, de uma única premissa de segurança: que o logaritmo no grupo formado pelos pontos de uma curva elíptica de ordem prima seja computacionalmente intratável. Isto é obtido garantindo-se que todas as diferentes partes do algoritmo sejam redutíveis a este problema. É apresentada também uma forma simples de estendê-lo a fim de que ele apresente segurança contra atacantes ativos, em especial, contra ataques de texto cifrado adaptativos. Para tanto, e a fim de manter a premissa de que a segurança do algoritmo seja unicamente dependente do logaritmo elíptico, é apresentada uma nova função de resumo criptográfico (hash) cuja segurança é baseada no mesmo problema. / This dissertation presents the development of a new public key algorithm. This algorithm has two key features, which were taken to be a goal from the start. The first feature is that it is semantically secure. That means that no polynomially bounded adversary can extract any partial information about the plaintext from the ciphertext, not even decide if two different ciphertexts correspond to the same plaintext. The second feature of the algorithm is that it depends on only one security assumption: that it is computationally unfeasible to calculate the logarithm on the group formed by the points of a prime order elliptic curve. That is achieved by ensuring that all parts of the algorithm are reducible to that problem. Also, it is presented a way to extend the algorithm so that it the resists attacks of an active adversary, in special, against an adaptive chosen-ciphertext attack. In order to do that, and attain to the assumption that only the assumption of the logarithm is necessary, it is introduced a new hash function with strength based of the same problem.

Cette thèse traite de deux problèmes dont le lien n’est pas apparent (1) A` quoi ressemble l’abélianisé AK du groupe de Galois absolu d’un corps quadratique imaginaire K, comme groupe topologique? (2) A` quoi ressemble le groupe des points adéliques d’une courbe elliptique sur Q, comme groupe topologique? Pour la première question, la restriction au groupe de Galois abélianisé nous permet d’utiliser la théorie du corps de classes pour analyser AK . Les travaux précédents dans ce domaine, qui remontent à Kubota et Onabe, décrivent le dual de Pontryagin de AK en termes de familles in- finies d’invariants de Ulm à chaque premier p, très indirectement. Notre approche directe par théorie du corps de classes montre que AK con- tient un sous-groupe UK d’indice fini isomorphe au groupe des unités Oˆ* de la complétion profinie Oˆ de l’anneau des entiers de K, et décrit explicitement le groupe topologique UK , essentiellement indépendamment du corps quadratique imaginaire K. Plus précisément, pour tout corps quadratique imaginaire différent de Q(i) et Q(v-2),on a UK ∼= U = Zˆ2 × Y Z/nZ. (n=1) Le caractère exceptionnel de Q(v-2) n’apparaît pas dans les travaux de Kubota et Onabe, et leurs résultats doivent être corrigés sur ce point.Passer du sous-groupe universel UK à AK revient à un problème d’extension pour des groupes adéliques qu’il est possible de résoudre en passant à une extension de quotients convenables impliquant le quotient Zˆ-libre maximal UK/TK de UK . Par résoudre , nous entendons que, pour chaque K suffisamment petit pour permettre des calculs de groupe de classes explicites, nous obtenons un algorithme praticable décidant le comportement de cette extension. Si elle est totalement non-scindée, alors AK est isomorphe comme groupe topologique au groupe universel U . Réciproquement, si l’extension tensorisée par Zp se scinde pour un premier p impair, alors AK n’est pas isomorphe à U . Pour le premier 2, la situation est particulière, mais elle reste contrôlée grâce à l’abondance de résultats sur la 2-partie des groupes de classes de corps quadratiques.Nos expérimentations numériques ont permis de mieux comprendre la distribution des types d’isomorphismes de AK quand K varie, et nous conduisent à des conjectures telles que pour 100% des corps quadratiques imaginaires K de nombre de classes premier, AK est isomorphe au groupe universel U .Pour notre deuxième problème, qui apparaît implicitement dans [?, Section 9, Question 1] (dans le but de reconstruire le corps de nombres K à partir du groupe des points adéliques E(AK ) d’une courbe elliptique convenable sur K), nous pouvons appliquer les techniques usuelles pour les courbes elliptiques sur les corps de nombres, en suivant les mêmes étapes que pour déterminer la structure du groupe Oˆ* rencontré dans notre premier problème. Il s’avère que, dans le cas K = Q que nous traitons au Chapitre 4, le groupe des points adéliques de presque toutes les courbes elliptiques sur Q est isomorphe à un groupe universel E = R/Z × Zˆ × Y Z/nZ (n=1)de nature similaire au groupe U . Cette universalité du groupe des points adéliques des courbes elliptiques provient de la tendance qu’ont les représentations galoisiennes attachées (sur le groupe des points de torsion à valeurs dans Q) à être maximales. Pour K = Q, la représentation galoisienne est maximale si est seulement si la courbe E est une courbe de Serre, et Nathan Jones [?] a récemment démontré que presque toutes les courbes elliptiques sur Q sont de cette nature. En fait, l’universalité de E(AK ) suit d’hypothèses bien plus faibles, et il n’est pas facile de construire des familles de courbes elliptiques dont le groupe des points adéliques n’est pas universel. Nous donnons un tel exemple à la fin du Chapitre 4. / The present thesis focuses on two questions that are not obviously related. Namely,(1) What does the absolute abelian Galois group AK of an imaginary quadratic number field K look like, as a topological group?(2) What does the adelic point group of an elliptic curve over Q look like, as a topological group?For the first question, the focus on abelian Galois groups provides us with class field theory as a tool to analyze AK . The older work in this area, which goes back to Kubota and Onabe, provides a description of the Pontryagin dual of AK in terms of infinite families, at each prime p, of so called Ulm invariants and is very indirect. Our direct class field theoretic approach shows that AK contains a subgroup UK of finite index isomorphic to the unit group Oˆ∗ of the profinite completion Oˆ of the ring of integers of K, and provides a completely explicit description of the topological group UK that is almost independent of the imaginary quadratic field K. More precisely, for all imaginary quadratic number fields different from Q(i) and Q(√−2), we have UK ∼= U = Zˆ2 × Y Z/nZ. (n=1)The exceptional nature of Q(√−2) was missed by Kubota and Onabe, and their theorems need to be corrected in this respect.Passing from the ‘universal’ subgroup UK to AK amounts to a group extension problem for adelic groups that may be ‘solved’ by passing to a suitable quotient extension involving the maximal Zˆ-free quotientUK/TK of UK . By ‘solved’ we mean that for each K that is sufficiently small to allow explicit class group computations for K, we obtain a practical algorithm to compute the splitting behavior of the extension. In case the quotient extension is totally non-split, the conclusion is that AK is isomorphic as a topological group to the universal group U . Conversely, any splitting of the p-part of the quotient extension at an odd prime p leads to groups AK that are not isomorphic to U . For the prime 2, the situation is special, but our control of it is much greater as a result of the wealth of theorems on 2-parts of quadratic class groups.Based on numerical experimentation, we have gained a basic under- standing of the distribution of isomorphism types of AK for varying K, and this leads to challenging conjectures such as “100% of all imagi- nary quadratic fields of prime class number have AK isomorphic to the universal group U ”.In the case of our second question, which occurs implicitly in [?, Section 9, Question 1] with a view towards recovering a number field K from the adelic point group E(AK ) of a suitable elliptic curve over K, we can directly apply the standard tools for elliptic curves over number fields in a method that follows the lines of the determination of the structure of Oˆ∗ we encountered for our first question.It turns out that, for the case K = Q that is treated in Chapter 4, the adelic point group of ‘almost all’ elliptic curves over Q is isomorphic to a universal groupE = R/Z × Zˆ × Y Z/nZ (n=1)that is somewhat similar in nature to U . The reason for the universality of adelic point groups of elliptic curves lies in the tendency of elliptic curves to have Galois representations on their group of Q-valued torsion points that are very close to being maximal. For K = Q, maximality of the Galois representation of an elliptic curve E means that E is a so-called Serre-curve, and it has been proved recently by Nathan Jones [?] that ‘almost all’ elliptic curves over Q are of this nature. In fact, universality of E(AK ) requires much less than maximality of the Galois representation, and the result is that it actually requires some effort to construct families of elliptic curves with non-universal adelic point groups. We provide an example at the end of Chapter 4.

Esta dissertação apresenta o desenvolvimento de um novo algoritmo de criptografia de chave pública. Este algoritmo apresenta duas características que o tornam único, e que foram tomadas como guia para a sua concepção. A primeira característica é que ele é semanticamente seguro. Isto significa que nenhum adversário limitado polinomialmente consegue obter qualquer informação parcial sobre o conteúdo que foi cifrado, nem mesmo decidir se duas cifrações distintas correspondem ou não a um mesmo conteúdo. A segunda característica é que ele depende, para qualquer tamanho de texto claro, de uma única premissa de segurança: que o logaritmo no grupo formado pelos pontos de uma curva elíptica de ordem prima seja computacionalmente intratável. Isto é obtido garantindo-se que todas as diferentes partes do algoritmo sejam redutíveis a este problema. É apresentada também uma forma simples de estendê-lo a fim de que ele apresente segurança contra atacantes ativos, em especial, contra ataques de texto cifrado adaptativos. Para tanto, e a fim de manter a premissa de que a segurança do algoritmo seja unicamente dependente do logaritmo elíptico, é apresentada uma nova função de resumo criptográfico (hash) cuja segurança é baseada no mesmo problema. / This dissertation presents the development of a new public key algorithm. This algorithm has two key features, which were taken to be a goal from the start. The first feature is that it is semantically secure. That means that no polynomially bounded adversary can extract any partial information about the plaintext from the ciphertext, not even decide if two different ciphertexts correspond to the same plaintext. The second feature of the algorithm is that it depends on only one security assumption: that it is computationally unfeasible to calculate the logarithm on the group formed by the points of a prime order elliptic curve. That is achieved by ensuring that all parts of the algorithm are reducible to that problem. Also, it is presented a way to extend the algorithm so that it the resists attacks of an active adversary, in special, against an adaptive chosen-ciphertext attack. In order to do that, and attain to the assumption that only the assumption of the logarithm is necessary, it is introduced a new hash function with strength based of the same problem.

Esta dissertação apresenta o desenvolvimento de um novo algoritmo de criptografia de chave pública. Este algoritmo apresenta duas características que o tornam único, e que foram tomadas como guia para a sua concepção. A primeira característica é que ele é semanticamente seguro. Isto significa que nenhum adversário limitado polinomialmente consegue obter qualquer informação parcial sobre o conteúdo que foi cifrado, nem mesmo decidir se duas cifrações distintas correspondem ou não a um mesmo conteúdo. A segunda característica é que ele depende, para qualquer tamanho de texto claro, de uma única premissa de segurança: que o logaritmo no grupo formado pelos pontos de uma curva elíptica de ordem prima seja computacionalmente intratável. Isto é obtido garantindo-se que todas as diferentes partes do algoritmo sejam redutíveis a este problema. É apresentada também uma forma simples de estendê-lo a fim de que ele apresente segurança contra atacantes ativos, em especial, contra ataques de texto cifrado adaptativos. Para tanto, e a fim de manter a premissa de que a segurança do algoritmo seja unicamente dependente do logaritmo elíptico, é apresentada uma nova função de resumo criptográfico (hash) cuja segurança é baseada no mesmo problema. / This dissertation presents the development of a new public key algorithm. This algorithm has two key features, which were taken to be a goal from the start. The first feature is that it is semantically secure. That means that no polynomially bounded adversary can extract any partial information about the plaintext from the ciphertext, not even decide if two different ciphertexts correspond to the same plaintext. The second feature of the algorithm is that it depends on only one security assumption: that it is computationally unfeasible to calculate the logarithm on the group formed by the points of a prime order elliptic curve. That is achieved by ensuring that all parts of the algorithm are reducible to that problem. Also, it is presented a way to extend the algorithm so that it the resists attacks of an active adversary, in special, against an adaptive chosen-ciphertext attack. In order to do that, and attain to the assumption that only the assumption of the logarithm is necessary, it is introduced a new hash function with strength based of the same problem.

No description available.

Le sujet de ma thèse s’inscrit dans le domaine des preuves formelleset de la vérification des algorithmescryptographiques. L’implémentation des algorithmes cryptographiquesest souvent une tâche assez compliquée, parce qu’ils sont optimiséspour être efficaces et sûrs en même temps. Par conséquent, il n’estpas toujours évident qu’un programme cryptographique en tant quefonction, corresponde exactement à l’algorithme mathématique,c’est-à-dire que le programme soit correct. Les erreurs dans lesprogrammes cryptographiques peuvent mettre en danger la sécurité desystèmes cryptographiques entiers et donc, des preuves de correctionsont souvent nécessaires. Les systèmes formels et les assistants depreuves comme Coq et Isabelle-HOL sont utilisés pour développer despreuves de correction des programmes. Les courbes elliptiques sontlargement utilisées en cryptographie surtout en tant que groupecryptographique très efficace. Pour le développement des preuvesformelles des algorithmes utilisant les courbes elliptiques, unethéorie formelle de celles-ci est nécessaire. Dans ce contexte, nousavons développé une théorie formelle des courbes elliptiques enutilisant l’assistant de preuves Coq. Cette théorie est par la suiteutilisée pour prouver la correction des algorithmes de multiplicationscalaire sur le groupe des points d’une courbe elliptique.Plus précisément, mes travaux de thèse peuvent être divisées en deuxparties principales. La première concerne le développement de lathéorie des courbes elliptiques en utilisant l'assistant des preuvesCoq. Notre développement de plus de 15000 lignes de code Coqcomprend la formalisation des courbes elliptiques données par uneéquation de Weierstrass, la théorie des corps des fonctionsrationnelles sur une courbe, la théorie des groupes libres et desdiviseurs des fonctions rationnelles sur une courbe. Notre résultatprincipal est la formalisation du théorème de Picard; une conséquencedirecte de ce théorème est l’associativité de l’opération du groupedes points d’une courbe elliptique qui est un résultat non trivial àprouver. La seconde partie de ma thèse concerne la vérification del'algorithme GLV pour effectuer la multiplication scalaire sur descourbes elliptiques. Pour ce développement, nous avons vérifier troisalgorithmes indépendants: la multiexponentiation dans un groupe, ladécomposition du scalaire et le calcul des endomorphismes sur unecourbe elliptique. Nous avons également développé une formalisationdu plan projectif et des courbes en coordonnées projectives et nousavons prouvé que les deux représentations (affine et projective) sontisomorphes.Notre travail est à la fois une première approche à la formalisationde la géométrie algébrique élémentaire qui est intégré dans lesbibliothèques de Ssreflect mais qui sert aussi à la certification devéritables programmes cryptographiques. / This thesis is in the domain of formalization of mathematics and ofverification of cryptographic algorithms. The implementation ofcryptographic algorithms is often a complicated task becausecryptographic programs are optimized in order to satisfy bothefficiency and security criteria. As a result it is not alwaysobvious that a cryptographique program actually corresponds to themathematical algorithm, i.e. that the program is correct. Errors incryprtographic programs may be disastrous for the security of anentire cryptosystem, hence certification of their correctness isrequired. Formal systems and proof assistants such as Coq andIsabelle-HOL are often used to provide guarantees and proofs thatcryptographic programs are correct. Elliptic curves are widely usedin cryptography, mainly as efficient groups for asymmetriccryptography. To develop formal proofs of correctness forelliptic-curve schemes, formal theory of elliptic curves is needed.Our motivation in this thesis is to formalize elliptic curve theoryusing the Coq proof assistant, which enables formal analysis ofelliptic-curve schemes and algorithms. For this purpose, we used theSsreflect extension and the mathematical libraries developed by theMathematical Components team during the formalization of the FourColor Theorem. Our central result is a formal proof of Picard’stheorem for elliptic curves: there exists an isomorphism between thePicard group of divisor classes and the group of points of an ellipticcurve. An important immediate consequence of this proposition is theassociativity of the elliptic curve group operation. Furthermore, wepresent a formal proof of correctness for the GLV algorithm for scalarmultiplication on elliptic curve groups. The GLV algorithm exploitsproperties of the elliptic curve group in order to acceleratecomputation. It is composed of three independent algorithms:multiexponentiation on a generic group, decomposition of the scalarand computing endomorphisms on algebraic curves. This developmentincludes theory about endomorphisms on elliptic curves and is morethan 5000 lines of code. An application of our formalization is alsopresented.