A contribution to the cryptanalysis of cryptographic schemes (EC)DSA and NTRU

Abstract

In this thesis, we examine the NTRU cryptosystem and the DSA signature and provide new lattice theory-based attacks against them. We start by introducing the two systems and outlining the prior attacks against them. Then we present the most significant findings from the theory of lattices. Τhese attacks heavily rely on lattice theory. Next, we introduce an attack on(EC)DSA that reduces the problem of finding the secret key to a CVP problemfor a specific lattice and makes use of Babai’s algorithm. Continuing with(EC)DSA, we present an attack that uses Kannan’s enumeration algorithm and takes as its hypothesis that a number of ephemeral keys share specificbits. The last attack on the (EC)DSA is a case when the secret and ephemeral keys are quite small. We present an algorithm in this direction, and we give two applications, one of which refers to bitcoin. Finally, we study the NTRU cryptosystem and show how the problem of finding the plaintext message isrelated to a CVP problem for a specific lattice. Then, using Babai’s algorithm, we find the plaintext message. For all the previous attacks, we present the results of experiments that show the effectiveness of these attacks.

Στην παρούσα εργασία εξετάζουμε το κρυπτοσύστημα NTRU και την ψηφιακή υπογραφή (EC)DSA, και παρουσιάζουμε καινούργιες επιθέσεις που βασίζονται στα δικτυωτά. Αρχικά παρουσιάζουμε τα δύο συστήματα και σχολιάζουμε τις προηγούμενες επιθέσεις σε αυτά. Έπειτα παρουσιάζουμε τα πιο σημαντικά αποτελέσματα από την θεωρία των δικτυωτών. Στην συνέχεια περιγράφουμε μία επίθεση στην ψηφιακή υπογραφή (EC)DSA, η οποία ανάγει το πρόβλημα της εύρεσης του μυστικού κλειδιού στο CVP για ένα συγκεκριμένο δικτυωτό, και στην συνέχεια εφαρμόζουμε τον αλγόριθμο του Babai. Συνεχίζοντας με το (EC)DSA, παρουσιάζουμε μία επίθεση η οποία χρησιμοποιεί τον αλγόριθμο απαρίθμησης του Kannan παίρνοντας ως δεδομένο ότι κάποια από τα εφήμερα κλειδιά έχουν κοινά bits σε κάποιες συγκεκριμένες θέσεις. Η τελεταία επίθεση στο (EC)DSA, είναι μία ειδική περίπτωση όπου τα κλειδιά είναι αρκετά μικρά. Παρουσιάζουμε έναν αλγόριθμο σε αυτή την κατεύθυνση και δίνουμε δύο εφαρμογές όπου η μία αφορά το bitcoin. Τέλος μελετάμε το κρυπτοσύστημα NTRU και δείχνουμε ότι το πρόβλημα της εύρεσης του καθαρού κειμένου ανάγεται στο CVP για ένα συγκεκριμένο δικτυωτό. ΄Επειτα εφαρμόζοντας τον αλγόριθμο του Babai βρίσκουμε το καθαρό κείμενο. Σε όλες τις επιθέσεις παρουσιάζουμε τα πειραματικά δεδομένα για να δείξουμε την αποτελεσματικότητά τους.