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

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

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

Στο πρώτο μέρος της διάλεξης κάνουμε μια ολική παρουσίαση της μεθόδου παραγοντοποίησης μέσω των ελλειπτικών καμπυλών, εξετάζοντας όλες τις περιπτώσεις στο κλασικό και πεπερασμένο επίπεδο. Μετά την παρατήρηση του 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 θεωρητικά εφυκτές

Υπολογισμός (Δυαδικό κόλπο)

P = (1, 1), 2P = (2, 2), 4P = 2(2P) = (0, 2), 8P = 2(4P) = (1, 4)

και 9P = 8P+P = (1,4)+(1,1) = O (ουδέτερο σημείο)

Ιδέα : 2P, 4P,…, P και τελική πρόσθεση

Παράδειγμα παραγοντοποίησης του 35 με το 5

Εστω a=1 και b=-1 τότε ≡ 4+27 ≡ 310 mod 35

Επιλογή του k (εξήγηση) k=9

Υπολογισμός του 9P

P= (2, 2), 2P = (0, 22), 4P = (16, 19), 8P = (7, 13)

και 9P = 8P+P= (7, 13) + (2, 2)

υπολογισμός του λ : 7-2≡5 mod 35

όμως το 5 δεν έχει αντίστροφο ως προς το 35 συνεπώς 5 | 35

Εξήγηση

|E(p)|=9 και 5 διαιρέτης του 35

Εις άτοπο επαγωγή

Προβολή mod 5

Υπολογισμός του λ Ουδέτερο στοιχείο (Lagrange)

Πεπερασμένες συντεταγμένες Απειρες συντεταγμένες

Ατοπο

Παρατήρηση : ο χρόνος του υπολογισμού εξαρτάται από το μέγεθος του διαιρέτη.

ΡΕΚΟΡ

	digits	factor	from	B1/B2	sigma	date	who
1	58	3213162276640339413566047915418064969550383692549981333701	8*10^141-17	3897500	2735675386	2003-Nov-01	R. Backstrom
2	57	167560816514084819488737767976263150405095191554732902607	2^997-1	44e6	6329517009540700	2003-Jun-22	B. Dodson
3	56	69787377067722881486602094502761253930262932578924438539	2^827+1	43e6	4029008539	2003-Dec-26	K. Aoki
4	55	7230880127526821693925059508972082952702133004552346281	629^59-1	45e6	267937500	2001-Oct-06	M. Izumi
5	55	5214992488521222360623470091045256749679250526710700189	V(54,1,73)	43e6	3836151505	2003-Dec-10	D. Broadhurst
6	55	1139151258261034615880135106860446479526482959089061629	XY(93,56)	30e6	556090596	2002-Dec-13	P. Gaudry
7	54	484061254276878368125726870789180231995964870094916937	(6^43-1)^42+1 [*]	15e6	599841120	1999-Dec-26	Lygeros/Mizony
8	54	477350833522476258826705274670317082147893737193497151	3^577-1	43e6	1939606094	2004-May-10	K. Aoki
9	54	133936702795612545033253138872863276649299468089582417	C(341,141)+1	11e6	1335265706	2002-Mar-19	C. Casey
10	54	113944651856655107794996103150041939333993926230123191	(3^64-1)^63+1	15e6	718797804	2000-Mar-21	Lygeros/Mizony

Public-key

Από το 1976 που εφευρέθηκε η public-key κρυπτογραφία από τους W. Diffie και M. Hellman, τα κρυπτοσυστήματα βασίζονται πάνω στη δυσκολία επίλυσης ενός μαθηματικού προβλήματος. Με τα χρόνια όμως πολλά από αυτά τα κρυπτοσυστήματα απεδείχτηκαν μη σίγουρα ή μη πρακτικά. Τώρα μόνο τρία είναι πλέον ανταγωνιστικά.

1. Integer factorization problem (IFP)

2. Discrete logarithm problem (DLP)

3. Elliptic curve discrete logarithm problem (ECDP)

Πρέπει να επιημάνουμε ότι κανένα από αυτά τα κρυπτοσυστήμαα δεν αποδείχτηκε προς το παρόν <<άτρωτο>> με την έννοια ότι δεν μπορεί να λυθεί με αποτελεσματικό τρόπο. Ενώ αυτό γίνεται μέσω των κβαντικών υπολογιστών (θεώρημα του Shor 1994).

Επιθέσεις των κρυπτοσυστημάτων

Οι ειδικές επιθέσεις εκμεταλλεύονται τα χαρακτηριστικά των αριθμών.

Οι γενικές επιθέσεις εξαρτόνται μόνο από το μέγεθος των αριθμών.

Ο αλγόριθμος των ελλειπτικών καμπυλών εξαρτάται από το μέγεθος των πρώτων παραγόντων του αριθμού και τείνει να βρίσκει πρώτους αριθμούς μικρού μεγέθους. (εώς 60 ψηφία)

Το πρόβλημα του διακριτού λογάριθμου των ελλειπτικών καμπυλών

Εστω μια ελλειπτική καμπύλη Ε πάνω στο πεπερασμένο σώμα F ( ή ), σημείο τάξης n, και ένα σημείο, να βρείτε τον ακέραιο l, που να ικανοποιεί Q=lP όταν υπάρχει.

Με βάση τη δυσκολία αυτού του προβλήματος οι Ν. Koblitz και V. Miller ανέπτυξαν το 1985 ένα προτόκολο κρυπτοσυστήματος.

Ο Pohlig και ο Hellman απέδειξαν ότι η εύρεση του αριθμού l μπορεί να γίνει μέσω των πρώτων παραγόντων του n. Άρα για να είναι πιο ασφαλές το κρυπτοσύστημα πρέπει να επιλέξουμε έναν αριθμό n που να είναι πρώτος αριθμός.

Ο καλύτερος αλγόριθμος για την επίλυση του προβλημάτος είναι η Pollard ρ-μέθοδος. Οι Gallant, Lambert και Vanstone με τους Wiener και Zuccherato έδειξαν ότι έχει βήματα όπου ένα βήμα είναι μια πρόσθεση στις ελλειπτικές καμπύλες.

Το 1993, οι van Oorschot και Wiener απέδειξαν ότι η Pollard ρ-μέθοδος μπορεί να μετατραπεί σε παράλληλο αλγόριθμο.

Κριτικές ελλειπτικές καμπύλες

Όπως το 1991, οι Menezes, Okamoto και Vanstone απέδειξαν ότι το πρόβλημα μπορεί να απλοποιηθεί με τις υπεριδιόρρυθμες ελλειπτικές καμπύλες μέσω του δείκτη υπολογισμού, αποφεύγουμε να τις χρησιμοποιούμε στα κρυπτοσυστήματά μας.

Το ίδιο ισχύει και με τις ανώμαλες ελλειπτικές καμπύλες, οι οποίες έχουν ακριβώς q σημεία πάνω στο . Και όπως με τις ιδιόρρυθμες υπάρχει για τις ανώμαλες, ένα εύκολο τες εντοπισμού της ιδιότητας αυτής.

Για τις καμπύλες του Koblitz μια ειδική κλάση ελλειπτικών καμπυλών πάνω στο με συντελεστές που ανήκουν στο μπορεί να βρεθεί ένας γρηγορότερος αλγόριθμος επίλυσης του προβλημάτος. Αν όμως είναι αρκετά μεγάλος (m>160) τότε η επιτάχυνση είναι σχετικά ασήμαντη.