Κρυπτανάλυση με Lattices:
Creators: name: Φουτζοπούλου, Μαρία Ιωάννη
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Κρυπτανάλυση
Δικτυωτά
Μικρές ρίζες
Cryptanalysis
Lattices
Small roots

description: Το 1978, οι Rivest, Shamir και Adleman πρότειναν το πρώτο κρυπτοσύστημα δημόσιου κλειδιού, που ονομάζεται σχήμα RSA. Στο RSA, κάθε χρήστης χρειάζεται μόνο ένα ζεύγος κλειδιών για να επικοινωνήσει με τους άλλους στο δίκτυο: το ζεύγος δημόσιο κλειδί/ιδιωτικό κλειδί. Η αντιστροφή της συνάρτησης κρυπτογράφησης του RSA ανάγεται στο πρόβλημα παραγοντοποίησης του N. Σκοπός μας είναι να σχεδιάσουμε αλγορίθμους που παραγοντοποιούν το N σε πολυωνυμικό χρόνο σε σχέση με το μήκος του. Η κύρια μέθοδος που χρησιμοποιούμε στο σχεδιασμό αυτών των αλγορίθμων είναι η μέθοδος Coppersmith για την εύρεση μικρών ριζών modular πολυωνυμικών εξισώσεων. Αυτή η προσέγγιση με τη σειρά της βασίζεται στον LLL-αλγόριθμο των Lestra, Lestra και Lovacs για την εύρεση μικρών διανυσμάτων lattice. Για να εφαρμόσουμε τη μέθοδο Coppersmith πρέπει να κατασκευάσουμε μια lattices βάση. Δεν είναι ξεκάθαρο ποια επιλογή της βάσης είναι βέλτιστη. Παρουσιάζουμε μια μέθοδο βελτιστοποίησης lattice βάσεων, που μπορεί κανείς να τη δει ως εναλλακτική της μεθόδου geometrically progressive matrices που πρότειναν οι Boneh και Durfee το 1999. Στη συνέχεια παρουσιάζουμε μια στοιχειώδη μέθοδο κατασκευής βελτιστοποιημένων lattices που χρησιμοποιούνται στην εύρεση μικρών ριζών πολυωνυμικών εξισώσεων. Προηγούμενες μέθοδοι πρώτα κατασκεύαζαν ένα μεγάλο lattice από ένα πολυώνυμο f και μετά το βελτιστοποιούσαν βρίσκοντας sublattices μικρότερης διάστασης. Οι Herrmann και May πρώτα βελτιστοποιούν το πολυώνυμο f, το οποίο άμεσα οδηγεί σε βελτιστοποιημένο lattice μικρής διάστασης. Με τη μέθοδο αυτή κατασκευάζουν και την πρώτη (στοιχειώδη) απόδειξη της επίθεσης των Boneh και Durfee στο RSA με μικρό μυστικό εκθέτη d. Στο κεφάλαιο 4 ασχολούμαστε με το πιο βασικό πρόβλημα που αφορά τον RSA: Η γνώση του ζεύγους (e,d) δίνει την παραγοντοποίηση του N σε πολυωνυμικό χρόνο; Είναι γνωστό ότι υπάρχει probabilistic αλγόριθμος πολυωνυμικού χρόνου που με είσοδο την τριάδα (N,e,d) δίνει την παραγοντοποίηση του N. Οι Coron και May παρουσιάζουν τον πρώτο deterministic αλγόριθμο πολυωνυμικού χρόνου που παραγοντοποιεί το N όταν είναι γνωστό ότι το ζεύγος (e,d). Πρόκειται για εφαρμογή της τεχνικής Coppersmith που βρίσκει μικρές ρίζες modular πολυωνύμων μιας μεταβλητής.
description: In 1978, Rivest, Shamir and Adleman invented the first public key cryptosystem, called the RSA scheme. In RSA, every user needs only one pair of keys in order to communicate to each other in the network: the public key/secret key pair. Inverting the RSA encryption function can be reduced to the problem of factoring N. Due to its importance and its beautiful, simple structure the RSA scheme has also attracted many cryptanalysts. Our goal is to design algorithms that factor an RSA modulus N in time polynomial in the bit-size of N. There are interesting special cases for which the factoring problem turns out to be efficiently solvable. The main method that we use in order to design our algorithms is the Coppersmith's method for finding small roots of modular polynomial equations. This approach in turn is based on the famous LLL-algorithm by Lestra, Lestra and Lovacs for finding short lattice vectors. In order to apply Coppersmith's method, one has to construct a lattice basis. It is not clear, choice of the lattice basis is optimal. We present a method for optimizing lattices bases that can be seen as an alternative method to the so-called geometrically progressive matrices that were introduced by Boneh and Durfee in 1999. Then we present an elementary method to construct optimized lattices that are used for finding small roots of polynomial equations. Former methods first construct some large lattice from a polynomial f and then optimize via finding suitable smaller dimensional sublattices. In contrast, this method focuses on optimizing f first which then directly leads to an optimized small dimensional lattice. Using this method, we construct the first elementary proof of the Boneh-Durfee attack for small RSA secret exponents with d. Does the knowledge of the RSA public and secret key pair (e,d) yield the factorization of N in polynomial time? We present the first deterministic polynomial time algorithm that factors N given (e,d). This approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.