Κρυπτογραφία ελλειπτικών καμπυλών και ο αλγόριθμος ΧΕΔΝΙ του Silverman
Creators: name: Μαλικιώσης, Ρωμανός-Διογένης Ιωάννη
Publisher: name: Aristotle University of Thessaloniki
Year: 2007
Subjects: Ελλειπτικές καμπύλες
Διακριτός λογάριθμος
Κρυπτογραφία
Xedni calculus
Elliptic curve cryptosystems
Discrete logarithm problem

description: Ο σκοπός της διπλωματικής είναι η ανάλυση του αλγορίθμου ΧΕΔΝΙ του Sivlerman, ο οποίος αποτελεί την πιο σοβαρή αντιμετώπιση του προβλήματος του Διακριτκού Λογαρίθμου Ελλειπτικών Καμπυλών (ECDLP). Στο πρώτο κεφάλαιο αναλύονται όλες οι σχετικές έννοιες με τη θεωρία ελλειπτικών καμπυλών που είναι απαραίτητες για την κατανόηση του αλγορίθμου. Στο δεύτερο κεφάλαιο παρουσιάζονται κρυπτοσυστήματα βασισμένα στην μη επιλυσιμότητα του ECDLP. Στο τρίτο κεφάλαιοα αναλύεται εκτενώς ο αλγόρισθμος ΧΕΔΝΙ του Silverman
description: The scope of the present thesis is the analysis of the XEDNI Calculus algorithm, developed by Silverman, which is considered to be one of the most serious attacks of the Elliptic Curve Discrete Logarithm Problem (ECDLP).The statement of the above problem is the following: given two points on an elliptic curve, find an integer such that ,STmSmT= (assuming that such an integer exists). There is no algorithm of polynomial or subexponential time solving ECDLP. XEDNI Calculus uses some techniques from Analytic Number Theory and Arithmetic Geometry, in particular, it makes use of the Birch and Swinnerton-Dyer conjecture through Mestre΅¦s method. This is the obstacle for computing efficiently the running time of the algorithm, and it has not been proved if the running time is polynomial, subexponential or even exponential!It is confirmed that this algorithm is not practical, only through experiments, as it is stated in the research that was conducted in the University of Waterloo (for more details, see [JKSST]).The security of modern cryptosystems is based on the intractability of the ECDLP, and in particular, the ElGamal cryptosystem. Initially, this cryptosystem implemented finite fields instead of elliptic curves. In this case we have the Discrete Logarithm Problem (DLP) on the finite field (p∗ƒΚƒΚ, which is also intractable. The most efficient algorithm is the Index Calculus by Adleman, whose running time is subexponential.XEDNI Calculus is in fact a better version of the Index Calculus, since there is no efficient way to implement the Index Calculus algorithm on elliptic curves. Silverman reverses some steps of the Index Calculus, in order to make this algorithm efficient for elliptic curves as well. This is the reason for naming this algorithm ΅§XEDNI΅¨, which is just the word ΅§Index΅¨ in reverse.The cryptosystems based on the intractability of the ECDLP are stronger than those based on the DLP, since there are a wider variety of groups relevant to elliptic curves, with very rich structure. One of the consequences is that elliptic curve cryptosystems require smaller keys than the cryptosystems based on the DLP, without being less secure.The structure of the present thesis is as follows: in the first chapter we will present the basic theory of elliptic curves necessary for the purpose of understanding the techniques used in XEDNI Calculus, as well as the analysis of Mestre΅¦s method and its relation with the Birch and Swinnerton-Dyer conjecture. In the second chapter we will analyze elliptic curve cryptosystems and in particular, ElGamal΅¦s cryptosystem. Furthermore, we will show all the necessary information relative to the security provided by the intractability of ECDLP, as well as a brief analysis of cryptosystems based on ECDLP. Finally, in the third chapter we will extensively analyze the XEDNI Calculus algorithm. In the Appendix, we will state any proposition from Algebra is necessary for understanding the details of the algorithm.