Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-11T19:14:06Z No. of bitstreams: 1 mariacristinaantuneslana.pdf: 1037473 bytes, checksum: dcfefa8fcafe1532991a72a13734904e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-18T13:00:12Z (GMT) No. of bitstreams: 1 mariacristinaantuneslana.pdf: 1037473 bytes, checksum: dcfefa8fcafe1532991a72a13734904e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-18T13:01:10Z (GMT) No. of bitstreams: 1 mariacristinaantuneslana.pdf: 1037473 bytes, checksum: dcfefa8fcafe1532991a72a13734904e (MD5) / Made available in DSpace on 2017-04-18T13:01:10Z (GMT). No. of bitstreams: 1 mariacristinaantuneslana.pdf: 1037473 bytes, checksum: dcfefa8fcafe1532991a72a13734904e (MD5) Previous issue date: 2016-08-25 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho tem como objetivo apresentar aos alunos do 3o ano do ensino médio, uma aplicaçãodamatemáticaàcriptografiaatravésdecurvaselípticas,comointuitodereforçar alguns conteúdos já estudados tais como: funções, construção de gráficos, polinômios e equações algébricas, geometria analítica. Criptografia é um tema atual e de grande relevância, visto que é amplamente utilizada na web para: segurança ao autenticar os usuários ao lhes fornecer acesso, na proteção de transações financeiras e em redes de comunicação. Acreditamos que, ao introduzir o conceito de criptografia através de curvas elípticasdemaneirasimpleseintuitiva,osalunossesentirãoentusiasmadosaoperceberque a matemática estudada por eles é de grande importância para a aplicação em fenômenos próximos a eles no dia a dia. / This paper aims to introduce students to the 3rd year of high school, a math application to encryption using elliptic curves, for the purpose of increasing some studies such as: functions,graphicsconstructions,polynomialsandalgebraicequations,analyticalgeometry. Encryption is a current topic of great importance, since it is widely used on the web for: securitybyidentifyingusersbyprovidingthemaccess,financialtransactionsprotectionand network communication. We believe that through introducing the concept of encryption using elliptic curves in a simple and intuitive way, the students feel excited to realize that mathematics studied by them is a great importance to the application in situations near them on a daily basis.

Orientador: Julio César López Hernández / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:18:34Z (GMT). No. of bitstreams: 1 Gouvea_ConradoPortoLopes_D.pdf: 3342900 bytes, checksum: b3a072bdbc369f1a1fffd95e1c1f4365 (MD5) Previous issue date: 2013 / Resumo: A implementação eficiente e segura de esquemas criptográficos é um aspecto importante da criptografia aplicada. Neste trabalho, foca-se na implementação em software de algoritmos relevantes da criptografia de curvas elípticas (CCE), criptografia baseada em emparelhamentos (CBE), e de cifração autenticada (CA). Duas plataformas computacionais modernas foram utilizadas: o microcontrolador MSP430, bastante utilizado em redes de sensores sem fio, e o processador ARM, amplamente empregado por dispositivos móveis como smartphones e tablets que estão se tornando cada vez mais populares. Técnicas para a melhoria de desempenho em software utilizando conjuntos de instruções, periféricos e melhorias algorítmicas são descritas. A implementação segura, cujo objetivo é prevenir certos ataques de canais secundários, também é estudada e novas técnicas são providas para reduzir seu impacto na velocidade em processadores ARM. Tais resultados contribuem para a construção eficiente e segura de sistemas criptográficos em sensores sem fio e processadores móveis / Abstract: The efficient and secure implementation of cryptographic schemes is an important aspect of practical cryptography. In this work, we focus on the software implementation of relevant algorithms in elliptic curve cryptography (ECC), pairing-based cryptography (PBC) and in authenticated encryption (AE). Two modern computational platforms were targeted: the MSP430 microcontroller often used in wireless sensor networks, and the ARM processor, widely employed in mobile devices such as smartphones and tablets which are increasingly becoming ubiquitous. Techniques for improving the software performance by taking advantage of instruction sets, peripherals and algorithmic enhancements are described. The secure implementation, which aims at thwarting common side-channel attacks, is also studied and new techniques are provided for improving its efficiency on ARM processors. These results contribute to the building of efficient and secure cryptographic systems on wireless sensors and mobile processors / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Les couplages sont des outils mathématiques introduits par André Weil en 1948. Ils sont un sujet très en vogue depuis une dizaine d'années en cryptographie asymétrique. Ils permettent en effet de réaliser des opérations cryptographiques impossible à réaliser simplement autrement tel que la signature courte et la cryptographie basée sur l'identité. Ces dernières années, le calcul des couplages est devenu plus facile grâce à l'introduction de nouvelles méthodes de calculs mathématiques particulièrement efficaces sur les courbes elliptiques dites les courbes bien adaptées aux couplages. Aujourd'hui, nous sommes au stade de transfert de cette technologie, de la théorie vers la mise en œuvre pratique, sur des composants électroniques. Ce transfert soulève de nombreuses problématiques qui s'avèrent difficile à surmonter à cause de la différence de culture scientifique entre mathématiciens et micro-électroniciens. Dans le présent document, en premier lieu, nous avons étudié le problème de l'implémentation du couplage dans des environnements restreints. En effet, le calcul du couplage de Tate, ou aussi de l'une de ses variantes, nécessite plusieurs variables pour être implémenté, par conséquent, il nécessite une bonne partie de la mémoire du composant électronique sur lequel nous souhaitons implémenter un tel couplage.Dans ce contexte, en faisant des optimisations mathématiques, nous avons pu implémenté ces couplages dans des environnements retreints. Le deuxième problème que nous avons traité dans cette thèse est celui de la sécurité des protocoles cryptographiques basés sur les couplages. Dans ce contexte, puisque les couplages sur les courbes elliptiques sont censés d'être matériellement attaqués, nous devons le protéger contre ces attaques. Nous avons étudié les attaques sur les couplages et nous avons proposé une contre-mesure. / Les couplages sont des outils mathématiques introduits par André Weil en 1948. Ils sont un sujet très en vogue depuis une dizaine d'années en cryptographie asymétrique. Ils permettent en effet de réaliser des opérations cryptographiques impossible à réaliser simplement autrement tel que la signature courte et la cryptographie basée sur l'identité. Ces dernières années, le calcul des couplages est devenu plus facile grâce à l'introduction de nouvelles méthodes de calculs mathématiques particulièrement efficaces sur les courbes elliptiques dites les courbes bien adaptées aux couplages. Aujourd'hui, nous sommes au stade de transfert de cette technologie, de la théorie vers la mise en œuvre pratique, sur des composants électroniques. Ce transfert soulève de nombreuses problématiques qui s'avèrent difficile à surmonter à cause de la différence de culture scientifique entre mathématiciens et micro-électroniciens. Dans le présent document, en premier lieu, nous avons étudié le problème de l'implémentation du couplage dans des environnements restreints. En effet, le calcul du couplage de Tate, ou aussi de l'une de ses variantes, nécessite plusieurs variables pour être implémenté, par conséquent, il nécessite une bonne partie de la mémoire du composant électronique sur lequel nous souhaitons implémenter un tel couplage.Dans ce contexte, en faisant des optimisations mathématiques, nous avons pu implémenté ces couplages dans des environnements retreints. Le deuxième problème que nous avons traité dans cette thèse est celui de la sécurité des protocoles cryptographiques basés sur les couplages. Dans ce contexte, puisque les couplages sur les courbes elliptiques sont censés d'être matériellement attaqués, nous devons le protéger contre ces attaques. Nous avons étudié les attaques sur les couplages et nous avons proposé une contre-mesure.

Sistemas criptográficos como o RSA e o Diffie-Hellman sobre Curvas Elípticas (DHCE) têm fundamento em problemas computacionais considerados difíceis, por exemplo, o problema do logaritmo (PLD) e o problema da fatoração de inteiros (PFI). Diversos trabalhos têm relacionado a segurança desses sistemas com os problemas subjacentes. Também é investigada a segurança do LSB (bit menos significativo) da chave secreta no DHCE (no RSA é o LSB da mensagem) com relação à segurança de toda a chave. Nesses trabalhos são apresentados algoritmos que conseguem inverter os sistemas criptográficos citados fazendo uso de oráculos que predizem o LSB. Nesta dissertação, fazemos a implementação de dois desses algoritmos. Identificamos parâmetros críticos e mudamos a amostragem do formato original. Com essa mudança na amostragem conseguimos uma melhora significativa nos tempos de execução. Um dos algoritmos (ACGS), para valores práticos do RSA, era mais lento que a solução para o PFI, com nosso resultado passou a ser mais veloz. Ainda, mostramos como provas teóricas podem não definir de maneira precisa o tempo de execução de um algoritmo. / Cryptographic systems like RSA and Elliptic Curve Diffie-Hellman (DHCE) is based on computational problems that are considered hard, e.g. the discrete logarithm (PLD) and integer factorization (PFI) problems. Many papers investigated the relationship between the security of these systems to the computational difficulty of the underlying problems. Moreover, they relate the bit security, actually the LSB (Least Significant Bit), of the secret key in the DHCE and the LSB of the message in the RSA, to the security of the whole key. In these papers, algorithms are presented to invert these cryptographic systems making use of oracles that predict the LSB. In this dissertation we implement two of them. Critical parameters are identified and the original sampling is changed. With the modified sampling we achieve an improvement in the execution times. For practical values of the RSA, the algorithm ACGS becomes faster than the PFI. Moreover, we show how theoretical proofs may lead to inaccurate timing estimates.

E. Bombieri et J. Pila ont introduit une méthode qui donne les bornees sur le nombre de points entiers qui sont appartiennent d'un arc donné (sous les plusieurs hypothèses).Dans la partie algébrique nous généralisons la méthode de Bombieri Pila pour le cas des champs de fonction de genre $0$ avec une variable. Ensuite, nous appliquons le résultat pour calculer le nombre de courbes elliptiques qui sont dans la même classe d'isomorphisme avec leurs coefficients dans une petite boîte.Une fois que nous avons prouvé ça, la question naturelle est de savoir si nous pouvons l'améliorer dans certains cas particuliers. Nous allons étudier le cas des courbes elliptiques en utilisant la partie de conjecture par Birch Swinnerton-Dyer, les propriétés des fonctions de hauteur bien avec les empilements compacts.Après, dans une partie analytique nous donnons la version explicite du théorème de Bombieri Vinogradov. Ce théorème est un résultat important concerne le terme d'erreur dans le théorème de Dirichlet sur les progressions arithmétiques, pris en moyenne sur les modules $q$ variant jusqu'à $Q$. Notre but est d'améliorer les résultats existant de cette façon (voir cite{Akbary2015}), donc nous pouvons réduire la puissance du facteur logarithmique en utilisant l'inégalité de grand crible et l'identité de Vaughan. / E.Bombieri and J.Pila introduced a method to bound the number of integral points in a small given box (under some conditions). In algebraic part we generalise this method to the case of function fields of genus $0$ in ove variable. Then we apply the result to count the number of elliptic curves falling in the same isomorphic class with coefficients lying in a small box.Once we are done the natural question is how to improve this bound for some particular families of curves. We study the case of elliptic curves and use the fact that the necessary part of Birch Swinnerton-Dyer conjecture holds over function fields. We also use the properties of height functions and results about sphere packing.In analytic part we give an explicit version of Bombieri-Vinogradov theorem. This theorem is an important result that concerns the error term in Dirichlet's theorem in arithmetic progressions averaged over moduli $q$ up to $Q$. We improve the existent result of such type given in cite{Akbary2015}. We reduce the logarithmic power by using the large sieve inequality and Vaughan identity.

<div><div><div><p>It is well-known that the sum of reciprocals of twin primes converges or is a finite sum.</p><p>In the same spirit, Samuel Wagstaff proved in 2021 that the sum of reciprocals of primes p</p><p>such that ap + b is prime also converges or is a finite sum for any a, b where gcd(a, b) = 1</p><p>and 2 | ab. Wagstaff gave upper and lower bounds in the case that ab is a power of 2. Here,</p><p>we expand on his work and allow any a, b satisfying gcd(a, b) = 1 and 2 | ab. Let Πa,b be the</p><p>product of p−1 over the odd primes p dividing ab. We show that the upper bound of these p−2</p><p>sums is Πa,b times the upper bound found by Wagstaff and provide evidence as to why we cannot hope to do better than this. We also give several examples for specific pairs (a, b).</p><p><br></p><p>Next, we turn our attention to elliptic Carmichael numbers. In 1987, Dan Gordon defined the notion of an elliptic Carmichael number as a composite integer n which satisfies a Fermat- like criterion on elliptic curves with complex multiplication. More recently, in 2018, Thomas Wright showed that there are infinitely such numbers. We build off the work of Wright to prove that there are infinitely many elliptic Carmichael numbers of the form a (mod M) for a certain M, using an improved lower bound due to Carl Pomerance. We then apply this result to comment on the infinitude of strong pseudoprimes and strong Lucas pseudoprimes.</p><p><br></p><p>Finally, we consider the problem of classifying for which k does one have Φk(x) | Φn(x)−1, where Φn(x) is the nth cyclotomic polynomial. We provide a motivating example as to how this can be applied to primality proving. Then, we complete the case k = 8 and give a partial characterization for the case k = 16. This leads us to conjecture necessary and sufficient conditions for when Φk(x) | Φn(x) − 1 whenever k is a power of 2.</p></div></div></div>

In this thesis we review bilinear maps and their usage in modern cryptography, i.e. the theoretical framework of pairing-based cryptography including the underlying mathematical hardness assumptions. The theory is based on algebraic structures, elliptic curves and divisor theory from which explicit constructions of pairings can be defined. We take a closer look at the more commonly known Weil pairing as an example. We also elaborate on pairings in practice and give numerical examples of how pairing-friendly curves are defined and how different type of cryptographical schemes works.

We provide explicit equations for moduli spaces of Drinfeld shtukas over the projective line with Γ(N), Γ_1(N) and Γ_0(N) level structures, where N is an effective divisor on P^1 . If the degree of N is big enough, these moduli spaces are relative surfaces. We study how the moduli space of shtukas over P^1 with Γ_0(N) level structure, Sht^{2,tr}(Γ_0(N)), can be used to provide a notion of motivic modularity for elliptic curves defined over function fields. Elliptic curves over function fields are known to be modular in the sense of admitting a parametrization from a Drinfeld modular curve, provided that they have split multiplicative reduction at one place. We conjecture a different notion of modularity that should cover the curves excluded by the reduction hypothesis. We use our explicit equations for Sht^{2,tr}(Γ_0(N)) to verify our modularity conjecture in the cases where N = 2(0) + (1) + (∞) and N = 3(0) + (∞).

In this paper, we present a study of elliptic curves, focusing on theirunderlying mathematical concepts, properties and applications in numbertheory. We begin by introducing elliptic curves and their unique features,discussing their algebraic structure, and exploring their group law, pro-viding examples and geometric interpretations. The core of our studyfocuses on the Elliptic Curve Method (ECM) for integer factorization.We present the motivation behind ECM and compare it to Pollard’s (p-1) method. A discussion on pseudocurves and the choice of an ellipticcurve and bound B is provided. We also address the differences betweenECM and Pollard’s (p-1) method and propose optimization techniques forECM, including the calculation of the least common multiple (LCM) ofthe first B integers using the Sieve of Eratosthenes.

Let K be an imaginary quadratic field with class number one and let [Special characters omitted.] be a degree one prime ideal of norm p not dividing 6 d K . In this thesis we generalize an algorithm of Schoof to compute the class number of ray class fields [Special characters omitted.] heuristically. We achieve this by using elliptic units analytically constructed by Stark and the Galois action on them given by Shimura's reciprocity law. We have discovered a very interesting phenomena where p divides the class number of [Special characters omitted.] . This is a counterexample to the elliptic analogue of a well-known conjecture, namely the Vandiver's conjecture.