Χρήστης:Vevek/Πρόχειρο: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Vevek (συζήτηση | συνεισφορές) |
Vevek (συζήτηση | συνεισφορές) Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1:
==Θέματα ασφάλειας==
Η ασφάλεια των κρυπτοσυστημάτων που βασίζονται στις ελλειπτικές καμπύλες έγκειται στη δυσεπιλυσημότητα του προβλήματος του διακριτού λογαρίθμου σ'αυτές (ECDLP). Το πρόβλημα είναι το εξής. Έστω <math>E(F_q)</math> μια ελλειπτική καμπύλη πάνω στο πεπερασμένο σώμα <math>F_q</math>. Αν<math>P, Q \in E(F_q)</math> δύο σημεία της καμπύλης, όπου το P είναι τάξης n, να βρεθεί ένας ακέραιος <math>1 \leq l < n</math> ώστε <math>Q = lP</math>, αν υπάρχει.
Αν ο n είναι σύνθετος, ο αλγόριθμος Pohlig-Hellman ανάγει το πρόβλημα στην εύρεση του διακριτού λογαρίθμου modulo τους πρώτους παράγοντες του. Επομένως, για μεγαλύτερη ασφάλεια, οπρέπει να είναι πρώτος αριθμός.
Με κάποιες τροποποιήσεις στον αλγόριθμο Rho του Pollard, χρειάζονται περίπου <math>\sqrt{\pi n}/2</math> προσθέσεις για την επίλυση του ECDLP. Μάλιστα, αν χρησιμοποιηθούν παράλληλα r επεξεργαστές, ο καθένας τους χρειάζεται <math>\sqrt{\pi n}/(2r)</math> προσθέσεις. Ακόμα, αν η ελλειπτική καμπύλη ορίζεται πάνω σε ένα υποσώμα <math>F_{2^k}</math> του <math>F_{2^m}</math>, τότε ο παραλληλοποιημένος αλγόριθμος χρειάζεται<math>\sqrt{\pi n k}/(2mr)</math>προσθέσεις σε κάθε έναν από τουςεπεξεργαστές.
| |||