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

 

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

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Hardware Attacks >> Software Attacks

 

 

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

 

 

 

 

 

 

Symmetric-key cipher και Elliptic Curve Method

 

 

1.    Ερευνα για k-bit symmetric-key cipher = Eρευνα για 2k-bit key elliptic curve method

 

 

2.    Oι symmetric-key cipher και Pollard είναι παραλλελήσημοι με γραμμική επιτάχυνση.

 

 

3.    Βήμα ECM >> Bήμα S-k cipher

 

 

4.    Το σπάσιμο του κώδικα έχει το ίδιο αποτέλεσμα.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Επιλογές σωμάτων και ελλειπτικών καμπυλών

 

 

 

 

1.          Επιλογή πεπερασμένου σώματος

 

 

Πολυπλοκότητα () = Πολυπλοκότητα (F)

 

όπου

 

(προς το παρόν)

 

 

2.          Παρουσίαση

 

 

α. Optimal normal basis representation

 

β. Polynomial basis representation

 

Μέσω των πινάκων αλλαγής βάσης τα α. και β. Είναι ισοδύναμα άρα δεν επηρεάζουν την πολυπλοκότητα του κρυπτοσυστήματος.

 

 

 

3.          Επιλογή της ελλειπτικής καμπύλης

 

 

 

ΟΧΙ ιδιόρρυθμες ή ανώμαλες ελλειπτικές καμπύλες

 

ΠΡΟΣΟΧΗ με τις καμπύλες του Koblitz για τα μικρά μεγέθη

 

 

 

 

 

 

 

 

 

 

 

 

Γενικό Συμπέρασμα

 

 

Το κρυπτοσύστημα των ελλειπτικών καμπυλών είναι πολυπλοκότερο

από τα κρυπτοσυστήματα του ΙFP (Integer Factorization Problem)

και DLP (Discrete Logarithm Problem)

άρα και πιο ασφαλές.