Στις μέρες μας, η ασφαλής διακίνηση πληροφοριών και δεδομένων αποτελεί ένα μείζον ζήτημα. Προς αυτή την κατεύθυνση, τα σύγχρονα συστήματα ασφαλείας χρησιμοποιούν κρυπτογραφικούς αλγορίθμους για να παρέχουν εμπιστευτικότητα, ακεραιότητα και αυθεντικότητα των δεδομένων. Αυτό έχει σαν αποτέλεσμα τα τελευταία χρόνια η επιστήμη της κρυπτογραφίας να αποτελεί ένα τομέα με μεγάλο ερευνητικό ενδιαφέρον. Πιο συγκεκριμένα, η κρυπτογραφία δημοσίου κλειδιού παρουσιάζει γρήγορη ανάπτυξη και εφαρμόζεται ευρύτατα καθώς παρέχει μεγάλο βαθμό προστασίας των δεδομένων. Αυτό το χαρακτηριστικό επιτυγχάνεται χάρη στην υψηλή υπολογιστική πολυπλοκότητα που παρουσιάζουν οι χρησιμοποιούμενοι αλγόριθμοι κατά την προσπάθεια επίλυσής τους. Επιπλέον, αυτού του τύπου η κρυπτογραφία αποφεύγει το πρόβλημα της διανομής και διαχείρισης κλειδιών μέσα σε ένα μη ασφαλές κανάλι επικοινωνίας που παρουσιάζει η κρυπτογραφία ιδιωτικού κλειδιού. Παρόλα αυτά, η κρυπτογραφία δημοσίου κλειδιού εμφανίζει, και αυτή με τη σειρά της, το μειονέκτημα πως κατά την κρυπτογράφηση-αποκρυπτογράφηση απαιτούνται δαπανηρές αριθμητικές πράξεις (π.χ. modulo πολλαπλασιασμός, αντιστροφή). Το πρόβλημα αυτό επιβαρύνεται από το γεγονός πως το μήκος των κλειδιών σε αυτού του τύπου την κρυπτογραφία έχει πολύ μεγάλο μέγεθος έτσι ώστε να διασφαλιστεί ένα υψηλό επίπεδο ασφαλείας. Λύση στα παραπάνω προβλήματα αποτελεί η βελτιστοποίηση σχεδιασμού των αριθμητικών πράξεων που απαιτούνται σε ένα σύστημα δημοσίου κλειδιού καθώς και η χρήση ελλειπτικών καμπυλών αφού με αυτό τον τρόπο γίνεται χρήση μικρότερου μήκους κλειδιών για την επίτευξη του ίδιου επιπέδου ασφαλείας. Στην Κρυπτογραφία Ελλειπτικών Καμπυλών, ο Βαθμωτός Πολλαπλασιασμός αποτελεί την κύρια μαθηματική πράξη και περιλαμβάνει μια σειρά από άλλες λειτουργίες πάνω στα σημεία της καμπύλης οι οποίες αυξάνουν τη συνολική υπολογιστική πολυπλοκότητα του συστήματος. Οι χρησιμοποιούμενοι, λοιπόν, βαθμωτοί πολλαπλασιαστές αποτελούν τον κύριο στόχο των φυσικών επιθέσεων (επιθέσεων υλικού) οι οποίες έχουν ως σκοπό να αποκομίσουν σημαντικές πληροφορίες κατά τη διάρκεια εκτέλεσης ενός βαθμωτού πολλαπλασιασμού. Οι πιο ευρέως γνωστές τέτοιες επιθέσεις είναι οι επιθέσεις σφάλματος (Fault Attacks - FA) και οι επιθέσεις πλάγιου μονοπατιού (Side Channel Attacks - SCA). Η χρήση αντίμετρων, όμως, για αυτά τα είδη επιθέσεων κατά την υλοποίηση ενός βαθμωτού πολλαπλασιαστή δεν είναι μια απλή διαδικασία. Ο συνδυασμός διάφορων αντίμετρων σε μια ενιαία αρχιτεκτονική μπορεί να δημιουργήσει νέα τρωτά σημεία σε αυτό το σύστημα τα οποία μπορεί να εκμεταλλευτεί ένας επιτιθέμενος. Λόγω αυτού του γεγονότος και δεδομένου ότι το κόστος κάθε αντίμετρου στη συνολική απόδοση δεν είναι αμελητέο, είναι ιδιαιτέρως σημαντική η προσεκτική επιλογή του σχήματος προστασίας για την αρχιτεκτονική ενός βαθμωτού πολλαπλασιαστή. Στα πλαίσια αυτής της διπλωματικής εργασίας μελετήθηκε η κρυπτογραφία δημοσίου κλειδιού η οποία βασίζεται στις Ελλειπτικές Καμπύλες με στόχο να προταθεί και να υλοποιηθεί ένα αποδοτικό κρυπτογραφικό σύστημα, τόσο από πλευράς ταχύτητας και απαιτούμενης επιφάνειας όσο και από πλευράς ασφάλειας. Σε αυτή τη μεθοδολογία σχεδιασμού δόθηκε μεγάλο βάρος στην προσπάθεια χρήσης μιας νέας μορφής Ελλειπτικών Καμπυλών, τις iv Καμπύλες Edwards, οι οποίες παρουσιάζουν σημαντικά πλεονεκτήματα έναντι των συμβατικών ελλειπτικών καμπυλών (π.χ. Weierstrass), καθώς οι πράξεις πάνω στην καμπύλη μπορούν να υλοποιηθούν πιο αποτελεσματικά ενώ έχουν και ένα εγγενή μηχανισμό προστασίας ενάντια στις επιθέσεις πλάγιου μονοπατιού. Λόγω του γεγονότος πως οι καμπύλες αυτές ορίζεται πάνω σε ένα πεπερασμένο σώμα ( ), οι πράξεις μεταξύ των σημείων της καμπύλης βασίζονται στην αριθμητική πεπερασμένων σωμάτων. Για να αυξηθεί το προτεινόμενο επίπεδο προστασίας και η συνολική αποδοτικότητα χρησιμοποιήθηκε το Αριθμητικό Σύστημα Υπολοίπων (Residue Number System - RNS), το οποίο αντικαθιστά μια πράξη με δεδομένα μεγάλου μεγέθους με υπολογισμούς σε παράλληλα μονοπάτια μικρότερου μεγέθους. Επίσης, το σύστημα RNS λόγω της αναπαράστασης των αριθμών οι οποίοι βασίζονται σε αριθμητικά υπόλοιπα, έχει μια εγγενή προστασία ενάντια σε επιθέσεις σφάλματος καθώς οποιοδήποτε εισαχθέν σφάλμα σε μια μεταβλητή κατά τη διάρκεια ενός RNS υπολογισμού, διαδίδεται σε όλες τις άλλες μεταβλητές και καθιστά το αποτέλεσμα μη-χρησιμοποιήσιμο (αρχή μολυσματικού υπολογισμού). Για την περαιτέρω αύξηση του μηχανισμού προστασίας, ένας αλγόριθμος για το βαθμωτό πολλαπλασιασμό βασιζόμενος στο Montgomery Power Ladder υιοθετήθηκε ο οποίος χρησιμοποιεί τυχαιοποίηση και έλεγχο συνοχής σε μια προσπάθεια το προτεινόμενο σύστημα να παρουσιάζει αντοχή και ανθεκτικότητα ενάντια σε FA και SCA επιθέσεις χωρίς να δημιουργηθούν νέα τρωτά σημεία. / Nowadays, the secure transmission of information and data is a major issue. Towards this end, modern security systems use cryptographic algorithms to provide confidentiality, integrity and authenticity of data. As a result, in recent years the science of cryptography has become an area with a large scientific interest. In particular, public-key cryptography is being developed very fast and is widely applied as it provides a large degree of data protection. This characteristic is being achieved thanks to the high computational complexity of the used algorithms when trying to attack them. Moreover, this type of cryptography avoids the problem of distribution and key management in an insecure communication channel that is presented in private-key cryptography. However, public-key cryptography has the disadvantage that during encryption and decryption, costly arithmetic operations are required (e.g. modulo multiplication, inversion). This problem is aggravated by the fact that the length of the keys in this type of cryptography is very large in order to ensure a high level of security. A solution to the above problems is the design optimization of arithmetic operations required in a public key system and the use of elliptic curves due to the fact that shorter keys are used to achieve the same level of security. In the Elliptic Curve Cryptography, Scalar Multiplication constitutes the main mathematic operation and involves a series of other point operations that add up to the computational complexity of Elliptic Curve cryptography as a whole. Furthermore, scalar multipliers are the main target of physical, hardware, attacks aiming at extracting sensitive information during one scalar multiplication execution. The most widely used such attacks are fault injection attacks (FA) and side channel attacks (SCA). However, integrating FA and SCA countermeasures into a scalar multiplier implementation is not a straightforward task. Combining different countermeasures into a single architecture may create new vulnerabilities on this system that an attacker can exploit. Due to the above fact and since the performance cost of each FA-SCA countermeasure is not negligible, choosing the protection scheme for a scalar multiplier architecture must be done very carefully. In this thesis, public-key cryptography based on elliptic curves was studied aiming to propose and implement an efficient cryptographic system, both in terms of speed and space requirements and in terms of security. In this design methodology, great focus is given to the use of a new form of elliptic curves, Edwards Curves, which have significant advantages over conventional elliptic curves (e.g. Weierstrass), since the Edwards Curve operations can be more efficiently implemented and have an inherent protection mechanism against SCA. Due to the fact that these curves are defined over a finite field ( ), the operations between the points of the curve are based on arithmetic of finite fields. To enhance the proposed protection level and to increase performance efficiency, Residual Number System (RNS) was used, which replaces an operation of large data size with calculations on parallel paths of smaller size. Moreover, RNS due to its modulo basis number representation has inherent protection against fault injection attacks since any introduced fault in an involved variable during some RNS calculation, propagates to all the other variables and renders the result unusable (infective computing vii principle). To further enhance this protection mechanism, a Montgomery Power Ladder based scalar multiplication algorithm was adopted that employs randomization and check coherence in an effort to provide FA and SPA resistance against a wide range of attacks without introducing new vulnerabilities.

Τα κρυπτογραφικά συστήματα που βασίζονται στις ελλειπτικές καμπύλες, αποτελούν ένα πολύ σημαντικό κομμάτι της κρυπτογραφίας δημόσιου κλειδιού και τα τελευταία χρόνια όλο και περισσότεροι επιστήμονες ασχολούνται με τη μελέτη τους. Το πλεονέκτημα των συστημάτων αυτών σε σχέση με τα συμβατικά κρυπτογραφικά συστήματα (π.χ. RSA) είναι ότι χρησιμοποιούν μικρότερες παραμέτρους και κλειδιά, προσφέροντας τα ίδια επίπεδα ασφάλειας. Για το λόγο αυτό, τα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών προτιμούνται σε συσκευές περιορισμένων πόρων, όπως οι έξυπνες κάρτες (smart cards) και τα κινητά τηλέφωνα. Ένα από τα πιο θεμελιώδη προβλήματα στα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών, είναι η γένεση ελλειπτικών καμπυλών, κατάλληλων να προσφέρουν την ασφάλεια που απαιτείται από τις κρυπτογραφικές εφαρμογές. Η πιο αποδοτική μέθοδος γένεσης ελλειπτικών καμπυλών, ορισμένων πάνω σε πρώτα, πεπερασμένα σώματα, είναι η μέθοδος του Μιγαδικού Πολλαπλασιασμού ή εν συντομία η μέθοδος CM. Η μέθοδος αυτή απαιτεί την εύρεση των ριζών ορισμένων πολυωνύμων, που ονομάζονται πολυώνυμα κλάσεως. Τα πολυώνυμα που χρησιμοποιούνται συνήθως είναι τα πολυώνυμα Hilbert και τα πολυώνυμα Weber. Τα πρώτα μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM, αλλά η κατασκευή τους είναι πολύ χρονοβόρα. Από την άλλη, τα πολυώνυμα Weber κατασκευάζονται πολύ πιο αποδοτικά αλλά δεν μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM. Για να γίνει αυτό, πρέπει οι ρίζες τους να μετασχηματιστούν στις ρίζες των αντίστοιχων πολυωνύμων Hilbert. Η παρούσα διδακτορική διατριβή στοχεύει σε τρεις κύριες κατευθύνσεις. Η πρώτη αφορά στη βελτίωση της απόδοσης της στη μεθόδου CM και στην εισαγωγή σε αυτή των πολυωνύμων Weber. Η δεύτερη, στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Η χρήση αυτών των ελλειπτικών καμπυλών εγγυάται τη σθεναρότητα των συστημάτων που τις χρησιμοποιούν απέναντι σε όλες τις πιθανές επιθέσεις. Η τρίτη αφορά στη δημιουργία μιας βιβλιοθήκης λογισμικού που να μπορεί να χρησιμοποιηθεί σε περιβάλλοντα περιορισμένων πόρων και η οποία να περιλαμβάνει όλους τους αλγορίθμους και τα πρωτόκολλα που απαιτούνται για την κατασκευή ενός ολοκληρωμένου κρυπτογραφικού συστήματος ελλειπτικών καμπυλών. Η πρώτη συνεισφορά της παρούσας διδακτορικής διατριβής αφορά σε μια νέα παραλλαγή της μεθόδου CM, η οποία βασίζεται στα πολυώνυμα Weber. Παρουσιάζεται το σύνολο των μετασχηματισμών των ριζών τους στις ρίζες των αντίστοιχων πολυωνύμων Hilbert και δίνεται ένα θεωρητικό άνω φράγμα για την ακρίβεια που απαιτείται για την κατασκευή τους. Επιπλέον, παρουσιάζεται μια εκτενής πειραματική μελέτη, με την οποία συγκρίνεται η χρήση των πολυωνύμων Hilbert με αυτή των πολυωνύμων Weber στη μέθοδο CM, καταδεικνύοντας τα πλεονεκτήματα των τελευταίων. Πειραματικά αποτελέσματα επίσης, αποδεικνύουν ότι το άνω φράγμα της ακρίβειας κατασκευής των πολυωνύμων Weber που παρουσιάστηκε στη διδακτορική διατριβή, είναι πολύ κοντά στην πραγματική ακρίβεια που απαιτείται για την κατασκευή τους. Η δεύτερη συνεισφορά αφορά στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Στην περίπτωση αυτή, αποδεικνύεται ότι τα πολυώνυμα Weber έχουν τρεις φορές μεγαλύτερο βαθμό από τον βαθμό των αντίστοιχων πολυωνύμων Hilbert, και μάλιστα τα συγκεκριμένα πολυώνυμα δεν έχουν ρίζες στα πρώτα πεπερασμένα σώματα (F_p), αλλά σε μια επέκτασή τους (F_{p^3}). Επιπλέον, παρουσιάζονται οι μετασχηματισμοί των ριζών των πολυωνύμων Weber (που ανήκουν τώρα στο F_{p^3}) στις ρίζες των αντίστοιχων πολυωνύμων Hilbert (που ανήκουν στο F_p). Ορίζονται επίσης κάποια νέα πολυώνυμα κλάσεως και μέσω μιας εκτενούς πειραματικής μελέτης συγκρίνεται η χρήση τους στη μέθοδο CM με αυτή των πολυωνύμων Weber, αποδεικνύοντας ότι ανάλογα με τις απαιτήσεις κάθε συστήματος, πρέπει να επιλέγεται διαφορετική κλάση πολυωνύμων. Επιπλέον, αναλύεται η αποδοτικότητα ενός σημαντικού βήματος της μεθόδου χρησιμοποιώντας τέσσερις διαφορετικούς αλγορίθμους και αποδεικνύεται ότι ο αλγόριθμος που προτείνεται στη διδακτορική διατριβή είναι ο δεύτερος καλύτερος ως προς τον χρόνο, αλλά έχει λιγότερες απαιτήσεις χώρου από τον γρηγορότερο. Τέλος, όσον αφορά στον τρίτο στόχο που τέθηκε στα πλαίσια της διδακτορικής διατριβής, παρουσιάζεται η υλοποίηση μιας βιβλιοθήκης λογισμικού που μπορεί να χρησιμοποιηθεί για την ανάπτυξη κρυπτογραφικών συστημάτων ελλειπτικών καμπυλών σε περιβάλλοντα περιορισμένων πόρων. Η βιβλιοθήκη είναι οργανωμένη σε διάφορα, καθαρά διαχωρίσιμα μεταξύ τους τμήματα, έτσι ώστε να μπορεί έυκολα να τροποποιηθεί ανάλογα με τις ανάγκες και τις απαιτήσεις κάθε χρήστη. / Elliptic curve cryptography (ECC) has gained an increasing popularity over the years, as it emerges as a fundamental and efficient technological alternative for building secure public key cryptosystems. This stems from the fact that elliptic curves (ECs) give rise to algebraic structures that offer a number of distinct advantages (smaller key sizes and highest strength per bit) over more customary algebraic structures used in various cryptographic applications (e.g., RSA). These characteristics make ECC suitable for software as well as for hardware implementations. The latter is of particular importance, since (under certain circumstances) it involves devices with limited resources such as cell phones and Smartcards. One of the fundamental issues in ECC is the generation of elliptic curves suitable for use in various cryptographic applications. The most efficient method for generating elliptic curves over prime fields is the {\em Complex Multiplication} (CM) method. This method requires the use of the roots of certain polynomials, called class polynomials. The most commonly used polynomials are the {\em Hilbert} and {\em Weber} ones. The former can be used to generate directly the elliptic curve, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not construct directly the desired elliptic curve. This can be achieved if one provides transformations of their roots to the roots of the corresponding Hilbert polynomials. The goals of this PhD thesis are the following: (i) to improve the CM method by incorporating in it Weber polynomials; (ii) to provide an efficient method for the generation of prime order ECs; and (iii) to develop a flexible and portable software library that will include all the necessary primitives and protocols required for the construction of an elliptic curve cryptosystem, especially in resource limited environments. The current thesis makes a host of new contributions towards the goals set above. In particular, to address the first goal, we present a variant of the CM method that generates elliptic curves of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of a Weber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical upper bound of the precision required for the computation of Weber polynomials for all values of the discriminant. We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with our theoretical bounds. Our experiments show the superiority of Weber polynomials and that the actual precision requirements for the construction of these polynomials are close to the theoretical estimate we provide. To address the second goal, we consider the use of a new variant of the CM method for the construction of {\em prime order} elliptic curves. The Weber polynomials that are used for the construction of prime order elliptic curves have degree three times larger than the degree of their corresponding Hilbert polynomials. We show that, these Weber polynomials do not have roots in the field $\mathbb{F}_p$, but do have roots in the extension field $\mathbb{F}_{p^3}$. We present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^3}$ to the roots of their corresponding Hilbert polynomials in $\mathbb{F}_p$. We also show how a new class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_p$), can be used in the CM method to generate prime order elliptic curves. We compare experimentally the efficiency of using this new class against the use of the aforementioned Weber polynomials and show that the type of polynomial that one should use depends on the particular application. We further investigate the time efficiency of the new CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them. Finally, we present an implementation of an elliptic curve cryptographic library, which includes not only the aforementioned algorithms, but also several cryptographic protocols. We provide a fully-equipped library of portable source code with clearly separated modules that allows for easy development of EC cryptographic protocols, and which can be readily tailored to suit different requirements and user needs. The small size of the library makes it appropriate for use in resource limited devices.

Magistro darbe yra įrodyta diskreti universalumo teorema elipsinių kreivių L funkcijoms. / In the master work, we prove the universality of the L-function.

Elipsinių kreivių L funkcijų išvestinės universalumo teoremos įrodymas remiasi ribinėmis teoremomis analizinių funkcijų erdvėje, tikimybinio mato silpno konvergavimo prasme. / The proof of the universality of the derivatives of L-functions of elliptic curves is based on a limit theorem in the sense of weak convergence of probability measures in the space of analytic functions.

Let $a \in \mathbb{Z}$ be a non-zero integer. Let $p$ be a prime such that $p \nmid a$. Define the index of $a$ modulo $p$, denoted $i_{a}(p)$, to be the integer $i_{a}(p) := [(\mathbb{Z}/p\mathbb{Z})^{\ast}:\langle a \bmod{p} \rangle]$. Let $N_{a}(x) := \#\{p \le x:i_{a}(p)=1\}$. In 1927, Emil Artin conjectured that \begin{equation*} N_{a}(x) \sim A(a)\pi(x) \end{equation*} where $A(a)>0$ is a constant dependent only on $a$ and $\pi(x):=\{p \le x: p\text{ prime}\}$. Rewrite $N_{a}(x)$ as follows: \begin{equation*} N_{a}(x) = \sum_{p \le x} f(i_{a}(p)), \end{equation*} where $f:\mathbb{N} \to \mathbb{C}$ with $f(1)=1$ and $f(n)=0$ for all $n \ge 2$.\\ \indent We examine which other functions $f:\mathbb{N} \to \mathbb{C}$ will give us formul\ae \begin{equation*} \sum_{p \le x} f(i_{a}(p)) \sim c_{a}\pi(x), \end{equation*} where $c_{a}$ is a constant dependent only on $a$.\\ \indent Define $\omega(n) := \#\{p|n:p \text{ prime}\}$, $\Omega(n) := \#\{d|n:d \text{ is a prime power}\}$ and $d(n):=\{d|n:d \in \mathbb{N}\}$. We will prove \begin{align*} \sum_{p \le x} (\log(i_{a}(p)))^{\alpha} &= c_{a}\pi(x)+O\left(\frac{x}{(\log x)^{2-\alpha-\varepsilon}}\right) \\ \sum_{p \le x} \omega(i_{a}(p)) &= c_{a}^{\prime}\pi(x)+O\left(\frac{x\log \log x}{(\log x)^{2}}\right) \\ \sum_{p \le x} \Omega(i_{a}(p)) &= c_{a}^{\prime\prime}\pi(x)+O\left(\frac{x\log \log x}{(\log x)^{2}}\right) \end{align*} and \begin{equation*} \sum_{p \le x} d(i_{a}) = c_{a}^{\prime\prime\prime}\pi(x)+O\left(\frac{x}{(\log x)^{2-\varepsilon}}\right) \end{equation*} for all $\varepsilon > 0$.\\ \indent We also extend these results to finitely-generated subgroups of $\mathbb{Q}^{\ast}$ and $E(\mathbb{Q})$ where $E$ is an elliptic curve defined over $\mathbb{Q}$. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2011-08-03 10:45:47.408

Orientador: Paulo Roberto Brumatti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T03:04:00Z (GMT). No. of bitstreams: 1 Sartori_KarinaKfouri_M.pdf: 722364 bytes, checksum: c380a542b9451e40e6788d0e8987b556 (MD5) Previous issue date: 2006 / Resumo: O objetivo central de estudo neste trabalho é introduzir o conceito de curvas elípticas. Tal assunto é clássico dentro da geometria algébrica e tem aplicações em Criptografia e Teoria dos Números. Neste trabalho descrevemos algumas delas: em Criptografia, apresentamos sistemas análogos aos de Diffie-Helman, Massey-Omura e ElGamal que são baseados no grupo abeliano finito de um curva elíptica definida sobre um corpo finito. Em Teoria dos Números descrevemos o método de Lenstra para descobrir fatores primos de um número inteiro, que, por sinal, também tem uma relação muito estreita com certo tipo de sistema criptográfico. Ainda em Teoria dos Números, apresentamos uma caracterização de números congruentes através da estrutura do grupo de uma determinada curva elíptica / Abstract: The central objective of study in this work is to introduce the concept of elliptic curves. Such subject is classic inside of algebraic geometry and has applications in Cryptography and Number Theory. In this work we describe some of them: in Cryptography, we present analogous systems to the ones of Diffie-Helman, Massey-Omura and ElGamal that are based on the finite abelian group of an elliptic curve defined over a finite field. In Number Theory, we describe the method of Lenstra to discover prime factors of a whole number, that, by the way, also has a very narrow relation with certain type of cryptosystem. Still in Number Theory, we present a characterization of congruentes numbers through the structure of the group of one determined elliptic curve / Mestrado / Algebra / Mestre em Matemática

Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T04:06:33Z (GMT). No. of bitstreams: 1 Morais_EduardoMoraesde_M.pdf: 1060073 bytes, checksum: 349e64f9f2a5456f3af935607dfa5e3d (MD5) Previous issue date: 2009 / Resumo: A criptografia baseada em identidades representa uma alternativa ao modelo de certificação digital, exigindo menor esforço para solucionar o problema de autenticidade da chave pública, mas perdendo a custódia da chave privada, que será gerada por uma autoridade de confiança. O modelo de criptografia sem certificados soluciona o problema da custódia da chave privada sem a utilização de certificados digitais. Neste modelo, o usuário tem a posse de uma parte da chave privada e com isso a chave pública passa a ser constituída de uma parte gerada pela autoridade de confiança e uma parte gerada pelo usuário. A cifrassinatura é uma primitiva criptográfica que reúne as vantagens do ciframento e da assinatura em uma única operação, permitindo maior eficiência e segurança. A literatura possui diversas propostas de ciframento sem certificados e assinatura sem certificados, mas não tem uma proposta genérica de cifrassinatura sem certificados. Este trabalho propõe um protocolo de cifrassinatura sem certificados eficiente, que pode ser implementado usando dois emparelhamentos bilineares. Considerando a importância de emparelhamentos bilineares para a construção do protocolo proposto, este trabalho apresenta os conceitos matemáticos necessários para a obtenção de emparelhamentos bilineares eficientes e resistentes a ataques ao problema do logaritmo discreto sobre a curva elíptica e sobre o corpo de extensão resultante do cálculo do emparelhamento bilinear. São apresentados também algoritmos eficientes para aritmética de precisão arbitrária, aritmética de curvas elípticas e cálculo de emparelhamentos. Além disso, são discutidos modelos formais de segurança, como por exemplo o modelo do oráculo aleatório. Finalmente, o modelo de criptografia baseada em identidades e o modelo de criptografia sem certificados são discutidos e com isso é possível apresentar a proposta de cifrassinatura sem certificados e argumentar que esta proposta _e segura e eficiente / Abstract: Identity based cryptography is an alternative to digital certification, which requires less computational effort to solve the problem of public key authenticity. On the other hand, identity based cryptography has the problem of key escrow, because the private key is generated by a trust authority. The certificateless cryptography model solves the key escrow problem without digital certificates. In this model, the user computes a parcial private key that is used to compose the entire private key. In the same way, the public key has two parts: one generated by the user and the other generated by the trust authority. Signcryption is a cryptographic primitive that has the advantages of encryption and signature together in a single operation, allowing the construction of secure and efficient protocols. The literature has many certificateless encryption and certificateless signature protocols, but there is no generic and efficient certificateless signcryption scheme. This work proposes an efficient certificateless signcryption protocol, that can be implemented with just two bilinear pairings. Considering the importance of bilinear pairings for the construction of the proposed protocol, this work presents the mathematical concepts for efficient bilinear pairings, that can resist against discrete logarithm atacks on the elliptic curve and on the extension field. This works also presents efficient algorithms for big number arithmetic, elliptic curve arithmetic and the Miller algorithm for pairings. It also presents formal security models, such as the random oracle model. Finally, identity based cryptography and certificateless cryptography models are defined and the proposed certificateless signcryption scheme is presented and we argue that it is secure and eficient, although no formal proof is given / Mestrado / Criptografia / Mestre em Ciência da Computação

Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-02-02T10:23:55Z No. of bitstreams: 2 Dissertação - Lucas Silva de Oliveira - 2017.pdf: 1595537 bytes, checksum: ebd223a4b2deb7987589b6a93497170d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Rejected by Luciana Ferreira (lucgeral@gmail.com), reason: Reveja o onde aparece "Curva Elíptica" a meu ver não é nome próprio. Observe a citação: OLIVEIRA, L.(falta um espaço)S. Curvas elípticas. 2017.(falta um espaço)65 f. Dissertação (Mestrado em Matemática) (Mestrado em Matemática em Rede Nacional) - Universidade Federal de Goiás, Jataí, 2017. on 2018-02-02T10:38:37Z (GMT) / Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-02-02T10:52:37Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Lucas Silva de Oliveira - 2017.pdf: 1595537 bytes, checksum: ebd223a4b2deb7987589b6a93497170d (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-02-02T10:57:16Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Lucas Silva de Oliveira - 2017.pdf: 1595537 bytes, checksum: ebd223a4b2deb7987589b6a93497170d (MD5) / Made available in DSpace on 2018-02-02T10:57:16Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Lucas Silva de Oliveira - 2017.pdf: 1595537 bytes, checksum: ebd223a4b2deb7987589b6a93497170d (MD5) Previous issue date: 2017-12-06 / This work is done through a brief explanation about elliptic curves bringing simple concepts about their algebra and geometry. In the geometric part,we characterize an elliptical curve with focus on a specific type: that are in the form of Weierstrass. We also draw the Bezout Theorem, which shows us not only how many points in common two elliptic curves can have, but any class of equivalence of polynomials, which can be interaction with straight lines, conic, cubic ... In the algebraic part, we demonstrate with the points are related to each other and some forms operations we can do with them. Bringing the proof that the set of rational points of an elliptic curve C form an abelian group. And still ways to find other points within the elliptical curves from one or two points to it. / Este trabalho se faz através de uma breve explanação a respeito de curvas elípticas trazendo conceitos simples sobre sua álgebra e geometria. Na parte geométrica, caracterizamos uma curva elíptica com enfoque em um tipo especifico: as que estão na forma de Weierstrass. Trazemos também o Teorema de Bézout, que nos mostra não só quantos pontos em comum duas curvas elípticas podem ter, mas quaisquer classe de equivalência de polinômios, podendo ser interação entre retas, cônicas, cubicas... Na parte algébrica, voltada a demonstrar como os pontos se relacionam entre si e algumas formas de operações que podemos fazer com eles. Trazendo a demonstração de que o conjunto de pontos racionais de uma curva elíptica C formam um grupo abeliano. E ainda formas de se encontrar outros pontos dentro das curvas elípticas a partir de um ou dois pontos a ela pertencentes.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2017-03-20T17:15:17Z No. of bitstreams: 2 Dissertação - Rigo Julian Osorio Angulo - 2017.pdf: 1795543 bytes, checksum: 4342f624ff7c02485e9e888135bcbc18 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-03-21T12:06:48Z (GMT) No. of bitstreams: 2 Dissertação - Rigo Julian Osorio Angulo - 2017.pdf: 1795543 bytes, checksum: 4342f624ff7c02485e9e888135bcbc18 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-21T12:06:48Z (GMT). No. of bitstreams: 2 Dissertação - Rigo Julian Osorio Angulo - 2017.pdf: 1795543 bytes, checksum: 4342f624ff7c02485e9e888135bcbc18 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / According to history, the main objective of cryptography was always to provide security in communications, to keep them out of the reach of unauthorized entities. However, with the advent of the era of computing and telecommunications, applications of encryption expanded to offer security, to the ability to: verify if a message was not altered by a third party, to be able to verify if a user is who claims to be, among others. In this sense, the cryptography of elliptic curves, offers certain advantages over their analog systems, referring to the size of the keys used, which results in the storage capacity of the devices with certain memory limitations. Thus, the objective of this work is to offer the necessary mathematical tools for the understanding of how elliptic curves are used in public key cryptography. / Segundo a história, o objetivo principal da criptografia sempre foi oferecer segurança nas comunicações, para mantê-las fora do alcance de entidades não autorizadas. No entanto, com o advento da era da computação e as telecomunicações, as aplicações da criptografia se expandiram para oferecer além de segurança, a capacidade de: verificar que uma mensagem não tenha sido alterada por um terceiro, poder verificar que um usuário é quem diz ser, entre outras. Neste sentido, a criptografia de curvas elípticas, oferece certas ventagens sobre seu sistemas análogos, referentes ao tamanho das chaves usadas, redundando isso na capacidade de armazenamento dos dispositivos com certas limitações de memória. Assim, o objetivo deste trabalho é fornecer ao leitor as ferramentas matemáticas necessá- rias para a compreensão de como as curvas elípticas são usadas na criptografia de chave pública.

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.