Κρυπτογράφηση / αποκρυπτογράφηση RSA

Δύο πρώτοι αριθμοί και μια παγίδα. Ένα κλειδί RSA ξεκινά από δύο μεγάλους τυχαίους πρώτους αριθμούς p και q· το γινόμενό τους n (το modulus, εξ ου και «κλειδί 2048 bit») δημοσιεύεται στο δημόσιο κλειδί μαζί με τον εκθέτη e (σχεδόν πάντα 65537). Το ιδιωτικό κλειδί είναι το ζεύγος d, ο αντίστροφος modulo του e − υπολογισμένος από τα p και q — συν συντομεύσεις που προκύπτουν από τους πρώτους και επιταχύνουν τις πράξεις ιδιωτικού κλειδιού έως 4×.

Η κρυπτογράφηση και η υπογραφή είναι η ίδια εκθετική πράξη. Η κρυπτογράφηση ενός μπλοκ μηνύματος m σημαίνει υπολογισμό του m^e mod n· η αποκρυπτογράφηση είναι το c^d mod n. Η υπογραφή ενός προ-μορφοποιημένου μπλοκ με τον ιδιωτικό εκθέτη και η επαλήθευση με τον δημόσιο είναι η ίδια πράξη προς την αντίθετη κατεύθυνση. Όλα τα υπόλοιπα σε αυτή τη σελίδα — OAEP, PSS, PKCS#1 — αφορούν την ασφαλή μορφοποίηση αυτού του μπλοκ, ώστε η ωμή εκθετική πράξη να μην εκτίθεται ποτέ.

Γιατί είναι αργό. Μια πράξη RSA σε κλειδί 2048 bit κοστίζει της τάξης του ενός εκατομμυρίου φορές περισσότερο CPU από την κρυπτογράφηση ενός μπλοκ με AES. Γι' αυτό το TLS χρησιμοποιεί RSA (ή ECC) μόνο για να συμφωνήσει σε ένα τυχαίο κλειδί AES, και έπειτα αλλάζει. Ο ίδιος κανόνας ισχύει για οτιδήποτε κατασκευάζεται: RSA για το κλειδί, AES για τα δεδομένα.

Μέγεθος κλειδιού. Το μήκος του modulus είναι ο μοχλός ασφάλειας: το 1024 bit έχει καταστεί μη αποδεκτό από πολιτική (η παραγοντοποίηση είναι εντός εμβέλειας κρατών), το 2048 bit ≈ 112 bit συμμετρικής ισχύος, το 3072 bit ≈ 128 bit, και το 15360 bit θα αντιστοιχούσε σε κλειδί AES 256 bit. Σημείωση για την μετακβαντική εποχή: ο αλγόριθμος του Shor σπάει το RSA πλήρως σε μεγάλο κβαντικό υπολογιστή — ένας ακόμη λόγος να περιορίζεται η διάρκεια ζωής των κλειδιών.

Το πρόβλημα του ωμού RSA. Το RSA του σχολικού βιβλίου (m^e mod n στο ωμό μήνυμα) είναι ντετερμινιστικό και ευκίνητο: ίδια μηνύματα κρυπτογραφούνται ίδια, ένας επιτιθέμενος μπορεί να πολλαπλασιάσει ένα κρυπτογράφημα με την κρυπτογράφηση του 2 για να διπλασιάσει το απλό κείμενο, και τα σύντομα μηνύματα πέφτουν με επίθεση meet-in-the-middle. Δεν πρέπει ποτέ να χρησιμοποιείται απευθείας.

Τι κάνει το OAEP. Το OAEP (PKCS#1 v2, RFC 8017) αναμειγνύει το μήνυμα με έναν τυχαίο σπόρο μέσω ενός δικτύου Feistel βασισμένου σε κατακερματισμό, πριν από την εκθετική πράξη. Το αποτέλεσμα: η κρυπτογράφηση είναι τυχαιοποιημένη (το ίδιο απλό κείμενο δίνει διαφορετικό κρυπτογράφημα κάθε φορά — η εκτέλεση του δείγματος OAEP δύο φορές και η σύγκριση των αποτελεσμάτων το δείχνει), η παραποίηση ανιχνεύεται κατά την αποκρυπτογράφηση, και το μήνυμα πρέπει να χωράει μέσα στο modulus με χώρο για τον κατακερματισμό — το όριο k−2·hashLen−2 που αναγράφεται παραπάνω.

Η ετικέτα. Μια προαιρετική δημόσια συμβολοσειρά που δένεται στη συμπλήρωση. Και οι δύο πλευρές πρέπει να δώσουν την ίδια ακριβώς ετικέτα, διαφορετικά η αποκρυπτογράφηση αποτυγχάνει — όπως το AAD στο AES-GCM, επιτρέπει τη σύνδεση του κρυπτογραφήματος με το πλαίσιο (ένα όνομα αρχείου, ένα αναγνωριστικό αλγορίθμου). Η κενή τιμή είναι το συνηθισμένο.

Η συμπλήρωση PKCS#1 v1.5 για κρυπτογράφηση απουσιάζει σκόπιμα. Η συμπλήρωση της εποχής του 1993 δεν έχει ακεραιότητα και διαρρέει πληροφορίες μέσω της συμπεριφοράς σφαλμάτων αποκρυπτογράφησης (η επίθεση του Bleichenbacher το 1998 μετατρέπει ένα «oracle» συμπλήρωσης σε πλήρη αποκρυπτογράφηση με λίγα εκατομμύρια κατασκευασμένα κρυπτογραφήματα· εξακολουθεί να σπάει πραγματικά συστήματα ως ROBOT, 2017). Το WebCrypto αρνείται να την υλοποιήσει· το ίδιο κάνει και αυτή η σελίδα.

Υπογραφή = κατακερματισμός, μετά συμπλήρωση, μετά εκθετική πράξη. Και τα δύο σχήματα κατακερματίζουν το μήνυμα (SHA-256/384/512 εδώ), μορφοποιούν το αποτύπωμα σε μπλοκ και εφαρμόζουν τον ιδιωτικό εκθέτη. Η επαλήθευση ξαναμορφοποιεί το μπλοκ με το δημόσιο κλειδί και συγκρίνει. Η διαφορά βρίσκεται στη μορφοποίηση:

Ποιο να επιλεγεί. Για νέα σχέδια: PSS. Για διαλειτουργικότητα με υπάρχοντα πιστοποιητικά, JWT (RS256) ή παλαιούς συνεργάτες: v1.5. Και τα δύο είναι ασφαλή ως σχήματα υπογραφής — η ιστορία καταστροφής του v1.5 αφορά τη συμπλήρωση *κρυπτογράφησης*, μια διαφορετική κατασκευή παρά το παρόμοιο όνομα.

Το PEM είναι απλώς DER τυλιγμένο σε base64. Ένα αρχείο PEM είναι μια ετικέτα συν το base64 μιας δομής DER (δυαδικό ASN.1). Η ετικέτα δείχνει ποια δομή — και αυτή είναι η ολόκληρη διαφορά ανάμεσα στις τέσσερις μορφές που παράγει αυτή η σελίδα:

Το ίδιο κλειδί, διαφορετικά περιτυλίγματα. Και τα τέσσερα πλαίσια παραπάνω μετά τη Δημιουργία περιέχουν το ίδιο ζεύγος κλειδιών — τα δημόσια SPKI και PKCS#1 περιέχουν τα ίδια n, e· τα ιδιωτικά PKCS#8 και PKCS#1 περιέχουν τις ίδιες ιδιωτικές τιμές. Η σελίδα μετατρέπει ανάμεσά τους χωρίς απώλειες στο πρόγραμμα περιήγησης (το αυτοτεστ της κάνει κύκλους μετατροπών). Η σύγχυση των μορφών είναι η συνηθέστερη αιτία σφαλμάτων «άκυρο κλειδί» όταν επικολλώνται κλειδιά μεταξύ εργαλείων.

Κρυπτογραφημένα PEM (-----BEGIN ENCRYPTED PRIVATE KEY-----) είναι PKCS#8 με στρώμα κρυπτογράφησης βασισμένο σε κωδικό πρόσβασης. Αυτή η σελίδα δεν τα δέχεται — αποκρυπτογραφούνται εκτός σύνδεσης (openssl pkcs8 -in enc.pem -out plain.pem) πρώτα.

• Κρυπτογράφηση μαζικών δεδομένων με RSA. Πέρα από το αυστηρό όριο μεγέθους του OAEP είναι απίστευτα αργό. Το μοτίβο είναι: δημιουργία τυχαίου κλειδιού AES, κρυπτογράφηση του κλειδιού AES με RSA-OAEP, κρυπτογράφηση των δεδομένων με AES-GCM, αποστολή και των δύο τμημάτων.
• Αποστολή του ιδιωτικού κλειδιού επειδή «είναι δοκιμή». Τα δείγματα κλειδιών που είναι ενσωματωμένα στα διανύσματα αυτής της σελίδας δημοσιεύονται σκόπιμα — μπορούν να υπογράψουν μόνο δοκιμαστικά δεδομένα. Τα πραγματικά κλειδιά δεν είναι τέτοια.
• Επαλήθευση με το ιδιωτικό κλειδί. Συνήθως «δουλεύει» μαθηματικά και κάποια εργαλεία το επιτρέπουν, αλλά η διανομή ιδιωτικού κλειδιού σε επαληθευτές ακυρώνει ολόκληρο το μοντέλο. Η επαλήθευση γίνεται με το δημόσιο κλειδί (αυτό το επιβάλλει η σελίδα).
• Σύγκριση υπογραφών byte προς byte για έλεγχο κώδικα. Οι PSS (και OAEP) είναι τυχαιοποιημένες: δύο σωστές εκτελέσεις παράγουν διαφορετικές εξόδους. Η σύγκριση γίνεται με επαλήθευση, όχι με ισότητα — μόνο οι υπογραφές v1.5 είναι ντετερμινιστικές.
• Κλειδιά 1024 bit «επειδή είναι γρηγορότερα». Είναι επίσης εντός εμβέλειας καλά χρηματοδοτούμενης παραγοντοποίησης. Το επιχείρημα της ταχύτητας έπεσε με την υβριδική κρυπτογράφηση: το RSA εκτελείται μία φορά ανά συνεδρία, όχι ανά byte.
• Ενσωμάτωση σταθερού μήκους salt διαφορετικού από το μήκος κατακερματισμού για PSS. Ο επαληθευτής πρέπει να συμφωνεί· το μήκος κατακερματισμού (η επιλογή αυτής της σελίδας και το -sigopt rsa_pss_saltlen:32 του OpenSSL) είναι η διαλειτουργική προεπιλογή.

Γιατί απέτυχε η αποκρυπτογράφηση με το μήνυμα «λάθος κλειδί, λάθος κατακερματισμός ή αλλοιωμένο κρυπτογράφημα»; Η αποκρυπτογράφηση OAEP αποτυγχάνει όταν: δεν πρόκειται για το αντίστοιχο ιδιωτικό κλειδί, ο κατακερματισμός διαφέρει από την πλευρά της κρυπτογράφησης, η ετικέτα διαφέρει, ή αλλάχθηκε ένα byte του κρυπτογραφήματος. Το σφάλμα είναι σκόπιμα ίδιο για όλες τις περιπτώσεις — η αποκάλυψη του ποιος έλεγχος απέτυχε αποτελεί από μόνη της διαρροή μέσω «oracle» συμπλήρωσης.

Μπορεί να προκύψει το δημόσιο κλειδί από το ιδιωτικό; Ναι — οι ιδιωτικές μορφές περιέχουν και τα n και e. Η σελίδα εμφανίζει και τα δύο μετά τη Δημιουργία· το OpenSSL το κάνει με openssl pkey -in priv.pem -pubout.

Γιατί 65537 ως εκθέτης; Είναι πρώτος αριθμός, έχει μόνο δύο bit ίσα με 1 (γρήγορη εκθετική πράξη), και είναι αρκετά μεγάλος ώστε να αποφεύγονται οι επιθέσεις χαμηλού εκθέτη που πλήττουν το e=3. Είναι η τυπική επιλογή από τη δεκαετία του 1990· ένας «παράξενος» εκθέτης συνήθως σημαίνει αδύναμο ή μη τυπικό κλειδί.

Έχει πεθάνει το RSA εξαιτίας των κβαντικών υπολογιστών; Όχι ακόμη — δεν υπάρχει μηχανή που να μπορεί να εκτελέσει τον αλγόριθμο του Shor σε modulus 2048 bit. Τα δεδομένα όμως που πρέπει να παραμείνουν μυστικά μέχρι τη δεκαετία του 2030 και μετά ήδη μεταναστεύουν· τα υβριδικά σχήματα PQC είναι η μηχανική απάντηση.

Τι γίνεται με το openssl rsautl; Είναι ο παρωχημένος πρόγονος του pkeyutl. Χρησιμοποιεί εξ ορισμού συμπλήρωση κρυπτογράφησης v1.5 — ένας ακόμη λόγος που αποσύρθηκε.