Η τελευταίες στιγμές του RSA. Η κβαντική υπολογιστές σπάνε το RSA.

Κρυπτοαναλιτες σε όλο τον κόσμο ανησυχούν για το τι θα συμβαίνει όταν οι κβαντική υπολογιστές τελειοποιηθούν, διότι θα μπορούσαν να αποκρυπτογραφούσαν σε σύντομο χρονικό διάστημα οιονδήποτε σημερινό πολυχρησιμοποιημένο αλγόριθμο κρυπτογραφήσεις. πραγματικά.
Ομοσς ενας Κρυπτογραφικός αλγόριθμος από το 1978 αντιστέκεται στους κβαντικούς υπολογιστές!. Ερευνητές από το Πανεπιστήμιο του Connecticut θα μπορούσε να αποδείξει ότι τώρα ο RSA αλγόριθμο που σήμερα είναι μία από τις ασφαλέστερες διαδικασίες, γρήγορα μπορεί να παραβιαστεί με την χρηση κβαντικον υπολογιστων. Ωστόσο, θα μπορούσε να εφαρμοστή μια παλαιότερη και ελάχιστα γνωστή κρυπτογραφικό τρόπο, Μια μέθοδος κρυπτογράφησης που αναπτύχθηκε από τον μαθηματικό Robert McEliece το 1978. 

To Κρυπτογραφικό σύστημα McEliece είναι ασυμμετρικός. Οι χρήσεις αλγορίθμου Κώδικες Goppa, τα οποία είναι ένας τύπος κώδικας λάθος-διόρθωσης (δείτε θεωρία κωδικοποίησης). Ο αλγόριθμος μεταμφιέζει έναν κώδικα Goppa που γίνεται από το plaintext ως γενικός γραμμικός κώδικας. Οι κώδικες Goppa είναι εύκολο να αποκωδικοποιηθούν, αλλά η διάκριση τους από έναν γενικό γραμμικό κώδικα είναι σκληρή. Αυτό είναι σκληρό πρόβλημα McEliece.

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

Οι προσπάθειες έχουν γίνει στο cryptanalyze McEliece, αλλά κανένα δεν είναι επιτυχές. Εντούτοις, ο αλγόριθμος χρησιμοποιείται σπάνια στην πράξη λόγω των ογκωδών κλειδιών. Μια εξαιρετική περίπτωση ότι οι χρήσεις McEliece για την κρυπτογράφηση είναι Ελεύθερο δίκτυο- όπως την εφαρμογή Εντροπία (ανώνυμο κατάστημα στοιχείων).

Καθορισμός σχεδίου

 

Το McEliece αποτελείται από τρεις αλγορίθμους: ένας πιθανολογικός βασικός αλγόριθμος παραγωγής που παράγει ένα κοινό και ένα ιδιωτικό κλειδί, έναν πιθανολογικό αλγόριθμο κρυπτογράφησης, και έναν αιτιοκρατικό αλγόριθμο αποκρυπτογράφησης.
Όλοι οι χρήστες σε μια επέκταση McEliece μοιράζονται ένα σύνολο κοινών παραμέτρων ασφάλειας: ν,τ,Κ. Οι συνιστώμενες τιμές για αυτές τις παραμέτρους είναι ν = 1024,τ = 38,Κ = 644 (πηγή: Εγχειρίδιο του εφαρμοσμένου συστήματος κρυπτογραφίας).

 

Βασική παραγωγή

 

1. Οι χρήστες επιλέγουν ένα δυαδικό (ν,Κ)- γραμμικός κώδικας Γ ικανός τ λάθη. Αυτός ο κώδικας πρέπει να κατέχει έναν αποδοτικό αλγόριθμο αποκωδικοποίησης.
2. Η Alice παράγει το α μήτρα γεννητριών Γ για τον κώδικα Γ.
3. Επιλέξτε έναν τυχαίο δυαδική non-singular μήτρα S.
4. Επιλέξτε έναν τυχαίο μήτρα Σελ. μεταλλαγής.
5. Υπολογίστε μήτρα .
6. Το δημόσιο κλειδί της Alice είναι ; το ιδιωτικό κλειδί της είναι (S,Γ,Π).

Κρυπτογράφηση μηνυμάτων

 

Υποθέστε τις επιθυμίες βαριδιών να σταλεί ένα μήνυμα μ στη Alice το της οποίας δημόσιο κλειδί είναι :

1. Κωδικοποιήστε το μήνυμα ως δυαδική σειρά του μήκους Κ.
2. Υπολογίστε το διάνυσμα .
3. Παράγετε έναν τυχαίο ν- διάνυσμα κομματιών ζ να περιάσχει το πολύ-πολύ τ αυτοί.
4. Υπολογίστε το κρυπτογράφημα όπως . «+» είναι ο χειριστής XOR

Αποκρυπτογράφηση μηνυμάτων

 

1. Υπολογίστε το αντίστροφο Π, Π − 1.
2. Υπολογίστε .
3. Χρησιμοποιήστε τον αλγόριθμο αποκωδικοποίησης για τον κώδικα Γ για να αποκωδικοποιήσει .
4. Υπολογίστε .

Αναφορές


Alfred J. Menezes, Scott Α. Vanstone, Α. J. Menezes και Paul C. van Oorschot, εγχειρίδιο του εφαρμοσμένου συστήματος κρυπτογραφίας.
 
http://www.technologyreview.com/blog/arxiv/25629/