Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον
Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2010
|
| Θέματα: | |
| Διαθέσιμο Online: | http://nemertes.lis.upatras.gr/jspui/handle/10889/3734 |
| id |
nemertes-10889-3734 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Παραγοντοποίηση ακεραίων Αλγόριθμος παραγοντοποίησης Κρυπτογραφία Number field sieve General number field sieve Cryptography Factoring Algebraic number theory RSA 003.54 |
| spellingShingle |
Παραγοντοποίηση ακεραίων Αλγόριθμος παραγοντοποίησης Κρυπτογραφία Number field sieve General number field sieve Cryptography Factoring Algebraic number theory RSA 003.54 Μπακογιάννης, Χρήστος Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| description |
Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος RSA, η ασφάλεια του οποίου βασίζεται στο γεγονός ότι είναι πολύ δύσκολο να παραγοντοποιήσουμε έναν «μεγάλο» αριθμό στους πρώτους παράγοντές του. Ο RSA αλγόριθμος θεωρείται αρκετά ασφαλής, αν βέβαια χρησιμοποιούμε κατάλληλο, για τα σημερινά δεδομένα, μέγεθος κλειδιού. Παρόλα αυτά, σε περίπτωση που βρεθεί κάποιος αποδοτικός αλγόριθμος που να μπορεί σε «λογικό» χρόνο να παραγοντοποιήσει οποιονδήποτε μεγάλο ακέραιο, τότε αυτομάτως η ασφάλεια του αλγορίθμου αυτού έχει παραβιαστεί και θα πρέπει να στραφούμε σε εναλλακτικές μεθόδους προστασίας της πληροφορίας.
Ο πιο αποδοτικός σήμερα αλγόριθμος παραγοντοποίησης μεγάλων ακεραίων είναι ο Number Field Sieve. Η έρευνα που έχει γίνει πάνω σε αυτόν τον αλγόριθμο, έχει οδηγήσει σε σημαντική πρόοδο και έχει καταστήσει, πλέον, εφικτή την παραγοντοποίηση ακεραίων που υπό άλλες προϋποθέσεις θα απαιτούσε χιλιάδες χρόνια από cpu time σε supercomputers. Αν και ακόμη και σήμερα υπάρχουν αρκετά σημεία που θα μπορούσαν να βελτιωθούν στον αλγόριθμο, κάνοντάς τον ακόμη πιο αποδοτικό, ωστόσο η πολυπλοκότητά του αποτρέπει αρκετούς να ασχοληθούν με την βελτίωσή του. Με την εργασία αυτή θα προσπαθήσουμε αρχικά να διασαφηνίσουμε όλες τις πληροφορίες που απαιτούνται για την σωστή κατανόηση της λειτουργίας του αλγορίθμου. Θα γίνει λεπτομερής περιγραφή των διαφόρων βημάτων του αλγορίθμου και θα δοθεί αναλυτικό παράδειγμα παραγοντοποίησης. Τέλος, θα παρουσιαστεί η παράλληλη υλοποίησή του αλγορίθμου, η οποία μπορεί να εκτελεστεί τόσο σε supercomputer, όσο και σε cluster υπολογιστών που επικοινωνούν μεταξύ τους με χρήση του MPI. |
| author2 |
Σπυράκης, Παύλος |
| author_facet |
Σπυράκης, Παύλος Μπακογιάννης, Χρήστος |
| format |
Thesis |
| author |
Μπακογιάννης, Χρήστος |
| author_sort |
Μπακογιάννης, Χρήστος |
| title |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| title_short |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| title_full |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| title_fullStr |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| title_full_unstemmed |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| title_sort |
υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον |
| publishDate |
2010 |
| url |
http://nemertes.lis.upatras.gr/jspui/handle/10889/3734 |
| work_keys_str_mv |
AT mpakogiannēschrēstos ylopoiēsētēsmethodouparagontopoiēsēsakeraiōnarithmōnnumberfieldsieveseparallēloypologistikoperiballon AT mpakogiannēschrēstos implementationoftheintegerfactorizationalgorithmnumberfieldsievenfsonparallelcomputers |
| _version_ |
1771297183264407552 |
| spelling |
nemertes-10889-37342022-09-05T09:41:22Z Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον Implementation of the integer factorization algorithm number field sieve (NFS) on parallel computers Μπακογιάννης, Χρήστος Σπυράκης, Παύλος Σπυράκης, Παύλος Κακλαμάνης, Χρήστος Σταματίου, Ιωάννης Bakogiannis, Christos Παραγοντοποίηση ακεραίων Αλγόριθμος παραγοντοποίησης Κρυπτογραφία Number field sieve General number field sieve Cryptography Factoring Algebraic number theory RSA 003.54 Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος RSA, η ασφάλεια του οποίου βασίζεται στο γεγονός ότι είναι πολύ δύσκολο να παραγοντοποιήσουμε έναν «μεγάλο» αριθμό στους πρώτους παράγοντές του. Ο RSA αλγόριθμος θεωρείται αρκετά ασφαλής, αν βέβαια χρησιμοποιούμε κατάλληλο, για τα σημερινά δεδομένα, μέγεθος κλειδιού. Παρόλα αυτά, σε περίπτωση που βρεθεί κάποιος αποδοτικός αλγόριθμος που να μπορεί σε «λογικό» χρόνο να παραγοντοποιήσει οποιονδήποτε μεγάλο ακέραιο, τότε αυτομάτως η ασφάλεια του αλγορίθμου αυτού έχει παραβιαστεί και θα πρέπει να στραφούμε σε εναλλακτικές μεθόδους προστασίας της πληροφορίας. Ο πιο αποδοτικός σήμερα αλγόριθμος παραγοντοποίησης μεγάλων ακεραίων είναι ο Number Field Sieve. Η έρευνα που έχει γίνει πάνω σε αυτόν τον αλγόριθμο, έχει οδηγήσει σε σημαντική πρόοδο και έχει καταστήσει, πλέον, εφικτή την παραγοντοποίηση ακεραίων που υπό άλλες προϋποθέσεις θα απαιτούσε χιλιάδες χρόνια από cpu time σε supercomputers. Αν και ακόμη και σήμερα υπάρχουν αρκετά σημεία που θα μπορούσαν να βελτιωθούν στον αλγόριθμο, κάνοντάς τον ακόμη πιο αποδοτικό, ωστόσο η πολυπλοκότητά του αποτρέπει αρκετούς να ασχοληθούν με την βελτίωσή του. Με την εργασία αυτή θα προσπαθήσουμε αρχικά να διασαφηνίσουμε όλες τις πληροφορίες που απαιτούνται για την σωστή κατανόηση της λειτουργίας του αλγορίθμου. Θα γίνει λεπτομερής περιγραφή των διαφόρων βημάτων του αλγορίθμου και θα δοθεί αναλυτικό παράδειγμα παραγοντοποίησης. Τέλος, θα παρουσιαστεί η παράλληλη υλοποίησή του αλγορίθμου, η οποία μπορεί να εκτελεστεί τόσο σε supercomputer, όσο και σε cluster υπολογιστών που επικοινωνούν μεταξύ τους με χρήση του MPI. The recent advances in computer science, in combination with the proliferation of computers in home and businesses and the explosive growth rate of the internet transactions, have increased the needs for secure electronic communications. One of the dominant systems of secure data transactions is the RSA algorithm. RSA’ s security relies on the fact that it is computationally difficult to factor a “large” integer into its component prime integers. RSA is considered secure as long as we use proper key length. However, if an efficient algorithm is developed that can factor any arbitrarily large integer in a “reasonable” amount of time, then the whole security of the algorithm will be broken, and we will have to use alternative methods to secure our systems. Today, the fastest known method for factoring large integers is the General Number Field Sieve algorithm. Research and development of the algorithm has enabled the factorization of integers that were once thought to require thousands of years of CPU time to accomplish. While there are still many possible optimizations that could increase the algorithm’s efficiency, however the complexity of the algorithm prevents many researchers from attempting to improve it. In this master thesis we present the information needed to understand the principles upon which the algorithm is based. The discrete steps of the algorithm are described in full detail, as well as a detailed factorization example, in order to enlighten the way each step works. Finally a parallel implementation is presented, able to be executed on a supercomputer or a computer cluster, with the use of MPI. 2010-09-21T07:59:22Z 2010-09-21T07:59:22Z 2010-06-08 2010-09-21T07:59:22Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/3734 gr Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
