Το κρυπτοσύστημα NTRU και επιθέσεις επί του ιδιωτικού κλειδιού
Creators: name: Σαλβάνος, Ανδρέας Αναστασίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2018
Subjects: Κρυπτογραφία δημοσίου κλειδιού
Μετακβαντική κρυπτογραφία
Πλέγματα
Πολυωνυμικοί δακτύλιοι
Public key cryptography
Post-quantum cryptography
Lattices
Polynomial rings

description: Η παρούσα διπλωματική εργασία έχει ως θέμα το κρυπτοσύστημα δημοσίου κλειδιού NTRU, καθώς και τις κυριότερες επιθέσεις στο ιδιωτικό του κλειδί. To NTRU αναπτύχθηκε από τους μαθηματικούς J. Hoffstein, J. Pipher και J. Silverman το 1996. Τόσο το ιδιωτικό όσο και το δημόσιο κλειδί είναι πολώνυμα με ακέραιους συντελεστές και οι διαδικασίες κρυπτογράφησης και αποκρυπτογράφησης περιλαμβάνουν πράξεις σε πολυωνυμικούς δακτυλίους πηλίκο. Επίσης, η ασφάλεια του NTRU βασίζεται σε δύσκολα υπολογιστικά προβλήματα των πλεγμάτων (lattices), όπως το SVP, το CVP και το BDD. Γι’ αυτό το λόγο, θεωρείται ότι είναι ασφαλές απέναντι στους κβαντικούς υπολογιστές και ανήκει στην κατηγορία της μετακβαντικής κρυπτογραφίας (post-quantum cryptography). Η δομή της εργασίας έχει ως εξής: Αρχικά, παρουσιάζουμε κάποιες προκαταρκτικές έννοιες από τη θεωρία των πλεγμάτων, οι οποίες είναι απαραίτητες για την ανάλυση της ασφάλειας του κρυπτοσυστήματος (Κεφ. 2). Στη συνέχεια αναλύουμε το NTRU. Συγκεκριμένα, παρουσιάζουμε τις διαδικασίες παραγωγής των κλειδιών, κρυπτογράφησης και αποκρυπτογράφησης, καθώς και το κόστος τους (Κεφ. 3). Τέλος, αναφέρουμε τα τρία βασικά είδη επιθέσεων στο ιδιωτικό κλειδί. Πρώτον, ορίζουμε το NTRU πλέγμα και δείχνουμε πώς η επίλυση συγκεκριμένων υπολογιστικών προβλημάτων σε αυτό μπορεί να φανερώσει το ιδιωτικό κλειδί. Δεύτερον, αναφέρουμε την επίθεση meet-in-the-middle, η οποία είναι μια σημαντική βελτίωση της εξαντλητικής αναζήτησης στο ιδιωτικό κλειδί. Τρίτον, αναφέρουμε την υβριδική επίθεση (hybrid attack), η οποία συνδυάζει τις παραπάνω δύο επιθέσεις (Κεφ. 4,5,6)
description: In the present thesis we present the NTRU public key cryptosystem as well as the main attacks on its private key. The NTRU was invented by J. Hoffstein, J. Pipher and J. Silverman in 1996. The private and public keys are polynomials with integer coefficients and the encryption and decryption procedures involve operations in polynomial quotient rings. Also, the security of NTRU is based on hard computational problems on lattices, such as SVP, CVP and BDD. That is why it is considered to be a quantum resistant public key cryptosystem and belongs to the area of post-quantum cryptography. The thesis is structured as follows. Initially, we present some preliminary notions and definitions from lattice theory, which are necessary in the security analysis of the system (Chapter 2). Then, we analyze the cryptosystem. In particular, we present the key generation, encryption and decryption procedures and we estimate their cost (Chapter 3). Finally, we discuss the main three types of attacks on the private key. First, we refer to the lattice attacks. We define the NTRU lattice and we show how the solution of suitable computational lattice problems on it, can reveal the private key. The second type of attack is the meet-in-the-middle attack, which is a significantly improved version of the brute force search on the private key. The third one is the hybrid attack, which is a combination of the above two attacks (Chapters 4,5,6)