Χρήστης:Vevek/Πρόχειρο

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Θέματα ασφάλειας[Επεξεργασία | επεξεργασία κώδικα]

Η ασφάλεια των κρυπτοσυστημάτων που βασίζονται στις ελλειπτικές καμπύλες έγκειται στη δυσεπιλυσημότητα του προβλήματος του διακριτού λογαρίθμου σ'αυτές (ECDLP). Το πρόβλημα είναι το εξής. Έστω μια ελλειπτική καμπύλη πάνω στο πεπερασμένο σώμα . Αν δύο σημεία της καμπύλης, όπου το P είναι τάξης n, να βρεθεί ένας ακέραιος Δεν μπόρεσε να γίνει ανάλυση του όρου. (SVG (Η MathML μπορεί να ενεργοποιηθεί μέσω μιας προσθήκης στο πρόγραμμα περιήγησης): Μη αποδεκτή απάντηση ("Math extension cannot connect to Restbase.") από τον εξυπηρετητή "http://localhost:6011/el.wikipedia.org/v1/":): {\displaystyle 1 \leq l < n} ώστε , αν υπάρχει.


Αν ο n είναι σύνθετος, ο αλγόριθμος Pohlig-Hellman ανάγει το πρόβλημα στην εύρεση του διακριτού λογαρίθμου modulo τους πρώτους παράγοντες του. Επομένως, για μεγαλύτερη ασφάλεια, οπρέπει να είναι πρώτος αριθμός.

Με κάποιες τροποποιήσεις στον αλγόριθμο Rho του Pollard, χρειάζονται περίπου προσθέσεις για την επίλυση του ECDLP. Μάλιστα, αν χρησιμοποιηθούν παράλληλα r επεξεργαστές, ο καθένας τους χρειάζεται προσθέσεις. Ακόμα, αν η ελλειπτική καμπύλη ορίζεται πάνω σε ένα υποσώμα του , τότε ο παραλληλοποιημένος αλγόριθμος χρειάζεταιπροσθέσεις σε κάθε έναν από τουςεπεξεργαστές.

Η καμπύλη λέγεται ανώμαλο πρώτο σώμα (prime field anomalous) αν . Τότε, υπάρχει αποδοτικός αλγόριθμος για τον υπολογισμό ισομορφισμού μεταξύ της ομάδας των σημείων της καμπύλης και του προσθετικού σώματος . Έτσι το πρόβλημα μπορεί να λυθεί πολυωνυμικά. Τέλος, η καμπύλη μπορεί να ενσωματωθεί στο αν και μόνο αν , για κάποιο . Αν ικανοποιείται η συνθήκη αυτή, το ECDLP ανάγεται στο DLP και μπορεί να χρησιμοποιηθεί ο αλγόριθμος index-calculus, που χρειάζεται υποεκθετικό χρόνο.

Πέρα από τα παραπάνω, δεν υπάρχουν περαιτέρω λόγοι ανησυχίας για την ασφάλεια ενός κρυπτοσυστήματος ελλειπτικής καμπύλης. Σύμφωνα με τον Miller, δεν υπάρχουν ελπίδες για την εφαρμογή του index-calculus στις ελλειπτικές καμπύλες. Έχουν γίνει βέβαια μελέτες σε θέματα συγγενή με το ECDLP. Έχει αναπτυχθεί υποεκθετικός αλγόριθμος για το DLP στην ιακωβιανή μιας υπερελλειπτικής καμπύλης μεγάλου γένους, ορισμένης πάνω σε πεπερασμένο σώμα. Παρόλ'αυτά όμως, στην περίπτωση των ελλειπτικών καμπύλων (όπου το γένος είναι 1) η χρονική πολυπλοκότητα του αλγόριθμου αυτού είναι χειρότερη από την εξαντλητική μέθοδο. Επίσης, το DLP για real quadratic congruence function fields (μετάφραση?) γένους 1 είναι ισοδύναμο με το ECDLP, αλλά δεν είναι γνωστός κανένας υποεκθετικός αλγόριθμος για την επίλυση του πρώτου.

Επιθέσεις λογισμικού: Υποθέτουμε ότι ένα million-instructions-per-second (MIPS) μηχάνημα μπορεί να κάνει 40.000 προσθέσεις σε ελλειπτικές καμπύλες ανά δευτερόλεπτο. Ο όρος MIPS έτη αναφέρεται στην υπολογιστική δύναμη σε έτη, ενός MIPS επεξεργαστή. Ο πίνακας παρακάτω δείχνει την απαιτούμενη υπολογιστική δύναμη για διάφορες τιμές του, για τον υπολογισμό ενός διακριτού λογαρίθμου με τον αλγόριθμο Rho του Pollard. Για παράδειγμα, αν διατίθενται 10.000 επεξεργαστές των 1.000 MIPS ο καθένας, τότε για ο υπολογισμός ενός διακριτού λογαρίθμου θα πάρει 85.000 χρόνια!