Η μέθοδος και το κρυπτοσύστημα των ελλειπτικών καμπυλών

 

Νίκος Λυγερός

 

 

 

 

 

Στο πρώτο μέρος της διάλεξης κάνουμε μια ολική παρουσίαση της μεθόδου παραγοντοποίησης μέσω των ελλειπτικών καμπυλών, εξετάζοντας όλες τις περιπτώσεις στο κλασικό και πεπερασμένο επίπεδο. Μετά την παρατήρηση του Lagrange, παρουσιάζουμε το θεώρημα του Hasse και αναλύουμε με παραδείγματα την εφαρμογή της μεθόδου του Lenstra και τα καλύτερα αποτελέσματα των Curry, Lygeros & Mizony, Izumi, Dodson και Backstrom. Στο δεύτερο μέρος μελετούμε τις ειδικές και τις γενικές επιθέσεις των κρυπτοσυστημάτων του τύπου Diffie και Hellman  που βασίζονται στις επιλύσεις των προβλημάτων IFP, DLP και ECDLP έτσι ώστε να εντοπίσουμε τους κινδύνους όσον αφορά την ασφάλεια της κρυπτογράφισης ειδικά για το πρόβλημα του διακριτού λογάριθμου των ελλειπτικών καμπυλών με τη ρ-μέθοδο του Pollard.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Εισαγωγή

 

 

 

Το 1985 ο Lenstra ανακάλυψε έναν αλγόριθμο παραγοντοποίησης που χρησιμοποιεί τις ελλειπτικές καμπύλες.

 

 

 

 

 

Ελλειπτικές καμπύλες

 

 

 

Σύνολο των σημείων του επιπέδου από το οποίο οι συντεταγμένες ικανοποιούν την εξίσωση:

.

 

Οι παράμετροι α και b είναι ακέραιοι αριθμοί του τύπου  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ιδιότητες

 

 

 

Πρόσθεση σημείων:   και

 

Παρατήρηση :   θα είναι

 

Έστω  μια ελλειπτική καμπύλη και  και  δύο σημεία της ελλειπτικής καμπύλης.

 

Η ευθεία που περνά από τα σημεία   και  είναι 

όπου  και  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


\

 

 

 

 

Εκφυλισμένη περίπτωση

 

 

 

Εάν   =  τότε  

 

 

Αρκεί ο υπολογισμός της παραγώγου και εξίσωση της εφαπτόμενης της ελλειπτικής καμπύλης

 

 

 

 

 

 

Γενική περίπτωση

 

 

 

 Εάν    τότε  διότι          

 

 

Παρατήρηση:  (πρόσθεση του Newton)

 

Εδώ λ=α (παράμετρος του υπολογισμού) συνεπώς

και

 διότι παίρνουμε το συμμετρικό σημείο σε σχέση με τον άξονα των πραγματικών.

 

Επιπλέον προσθέτουμε το ουδέτερο στοιχείο Ο το οποίο έχει άπειρες συντεταγμένες.

 

 

 

 

 

 

 

 

 

 

Modular Calculus

 

 

 

  mod p και  mod p

 

Παράδειγμα: εάν  p=5,  a=1,   b= -1 και  και  τότε

 

Το σύνολο Ε(p) των σημείων της ελλειπτικής καμπύλης modulo p είναι πεπερασμένο.

 

Εύκολο:  |Ε(p)|≤

 

Δύσκολο:  (Θεώρημα του Hasse)

 

Παράδειγμα: εάν α=1, b=4 τότε Ε(5) έχει 9 σημεία

 

(3,3),  (3,2), (0,3), (0,2), (1,4), (1,1), (2,3), (2,2) και Ο

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Παρατήρηση  του Lagrange

 

Εάν προσθέσουμε n (τάξη της πεπερασμένης ομάδας) φορές ένα στοιχείο της ομάδας με τον ευατό του τότε καταλήγουμε στο ουδέτερο στοιχείο

π.χ. x = (0,3) , x+x, x+x+x, …

 

(0,3) è (1,1)è (3,3) è (2,2) è (2,3) è (3,2) è (1,4) è (0,2) è O  (κύκλος)

 

Σύνολο των ελλειπτικών καμπυλών E(p)

 

Παράδειγμα : p=5  20 ελλειπτικές καμπύλες για 25 θεωρητικά εφυκτές