Σύγκριση ECDSA έναντι RSA

Εισαγωγή

Τον τελευταίο καιρό, έχουν γίνει πολλές συζητήσεις σχετικά με τα υπέρ και τα κατά RSA[01]
και ECDSA[02], στην κοινότητα κρυπτογράφησης. Για τους άγνωστους, είναι δύο
τους πιο ευρέως χρησιμοποιούμενους αλγορίθμους ψηφιακής υπογραφής, αλλά ακόμη και για την πιο τεχνολογία
καταλαβαίνω, μπορεί να είναι αρκετά δύσκολο να συμβαδίζουμε με τα γεγονότα. Αυτό το άρθρο είναι ένα
προσπάθεια απλοποίησης της σύγκρισης των δύο αλγορίθμων. Ωστόσο, αυτό δεν είναι
ένα βαθιά τεχνικό δοκίμιο, ο πιο ανυπόμονος αναγνώστης μπορεί να ελέγξει το τέλος του
άρθρο για έναν γρήγορο πίνακα TL; DR με τη σύνοψη της συζήτησης.

ECDSA έναντι RSA

Το ECDSA και το RSA είναι αλγόριθμοι που χρησιμοποιούνται από κρυπτογραφία δημόσιου κλειδιού[03] συστήματα,
να παρέχει έναν μηχανισμό για πιστοποίηση. Η κρυπτογραφία δημόσιου κλειδιού είναι η
επιστήμη του σχεδιασμού κρυπτογραφικών συστημάτων που χρησιμοποιούν ζεύγη κλειδιών: α δημόσιο
κλειδί (εξ ου και το όνομα) που μπορεί να διανεμηθεί ελεύθερα σε οποιονδήποτε, μαζί με ένα
αντίστοιχος ιδιωτικό κλειδί, το οποίο είναι γνωστό μόνο στον ιδιοκτήτη του. Αυθεντικοποίηση
αναφέρεται στη διαδικασία επαλήθευσης ότι ένα μήνυμα, υπογεγραμμένο με ιδιωτικό κλειδί, ήταν
δημιουργήθηκε από τον κάτοχο ενός συγκεκριμένου ιδιωτικού κλειδιού. Αλγόριθμοι που χρησιμοποιούνται για
ο έλεγχος ταυτότητας είναι συλλογικά γνωστοί ως ψηφιακοί αλγόριθμοι υπογραφής [04].

Τέτοιοι αλγόριθμοι βασίζονται σε πολύπλοκα μαθηματικά προβλήματα που είναι σχετικά απλά
να υπολογίσει έναν τρόπο, αν και αρκετά πρακτικό να αντιστραφεί. Αυτό σημαίνει ότι για
ένας εισβολέας να σφυρηλατήσει μια ψηφιακή υπογραφή, χωρίς καμία γνώση του ιδιωτικού
κλειδί, πρέπει να επιλύσουν δυσάρεστα μαθηματικά προβλήματα, όπως ακέραιος
παραγοντοποίηση, για την οποία δεν υπάρχουν γνωστές αποτελεσματικές λύσεις [05].

Σε αυτόν τον λογαριασμό, καθώς δεν υπάρχουν διαθέσιμες αποτελεσματικές λύσεις για το
υποκείμενα μαθηματικά προβλήματα, η αξιολόγηση των κρυπτογραφικών αλγορίθμων μπορεί
συμβαίνει μόνο σε σχέση με τις λεπτομέρειες εφαρμογής τους σε συνδυασμό με το
επίπεδο ασφάλειας που παρέχουν. Για το σκοπό αυτό, αυτή η ενότητα παρουσιάζει ένα
σύγκριση των RSA και ECDSA χρησιμοποιώντας πέντε (ή έξι) ποσοτικές μετρήσεις. Κάθε μέτρηση
εισάγεται στο δικό του τμήμα, μαζί με τη σημασία του για οποιονδήποτε είναι
προσπαθώντας να αποφασίσουμε μεταξύ των δύο αλγορίθμων.

Υιοθεσία

Το RSA είναι το βιομηχανικό πρότυπο για την κρυπτογραφία δημόσιου κλειδιού για πολλά χρόνια
τώρα. Τα περισσότερα SSL /TLS τα πιστοποιητικά υπογράφηκαν (και εξακολουθούν να) με κλειδιά RSA.
Αν και οι περισσότερες ΑΠ έχουν, μέχρι τώρα, εφαρμόσει υποστήριξη για ECDSA
πιστοποιητικά, αυτή η μακροχρόνια υιοθέτηση οδήγησε σε πολλά συστήματα παλαιού τύπου μόνο
υποστήριξη της RSA. Επομένως, εάν ένας πωλητής απαιτεί συμβατότητα προς τα πίσω με παλιά
λογισμικό πελάτη, αναγκάζονται να χρησιμοποιούν πιστοποιητικά υπογεγραμμένα με RSA. Στην εποχή μας,
Ωστόσο, οι περισσότεροι σύγχρονοι πελάτες έχουν εφαρμόσει υποστήριξη για το ECDSA, το οποίο θα το κάνει
πιθανώς να καταργήσετε αυτόν τον περιορισμό συμβατότητας στο εγγύς μέλλον.

Τυπική ωριμότητα

Το RSA τυποποιήθηκε για πρώτη φορά για SSL /TLS το 1994 [06], ενώ το ECDSA εισήχθη
στην προδιαγραφή του TLS v1.2 το 2008 [07]. Αυτή η διαφορά ηλικίας δείχνει ένα
διαφορά στην ωριμότητα των προτύπων που περιγράφουν τις βέλτιστες πρακτικές για
κάθε αλγόριθμος. Παρόλο που, τα πρότυπα RSA έχουν διερευνηθεί εκτενώς και
ελεγχθεί, το ECDSA δεν έχει δει τόσο μεγάλη προσοχή. Πρόσφατα, υποστηρίζει αυτό
αλγόριθμος από μεγάλες CA και την υιοθέτησή του στα πιο σύγχρονα SSL /TLS οι πελάτες έχουν
είχε ως αποτέλεσμα τη δημοσίευση εκτενέστερης έρευνας, αλλά παραμένει
σχετικά νέο σχήμα. Αυτό αφήνει περιθώρια για ανεκπλήρωτα ελαττώματα σχεδιασμού ή
λανθασμένες υλοποιήσεις που θα αποκαλυφθούν στο μέλλον.

Αναλογία μεγέθους κλειδιού προς επίπεδο ασφάλειας

Επίπεδο ασφαλείας [08] είναι μια μέτρηση στην κρυπτογραφία, που αναφέρεται στην ισχύ
ενός κρυπτογραφικού πρωτόγονου ή συνάρτησης. Συνήθως μετριέται σε "bits"
δηλώνει τον αριθμό των επιχειρήσεων που πρέπει να εκτελέσει ένας εισβολέας για να θέσει σε κίνδυνο το δικό του
ασφάλεια. Αυτή η μέτρηση μπορεί να παρέχει μια μέθοδο ποσοτικοποίησης για τη σύγκριση της αποτελεσματικότητας
διαφόρων κρυπτοσυστημάτων. Πρέπει να τονιστεί ότι το μέγεθος του δημόσιου κλειδιού είναι επίσης
μετρούνται σε bits, αλλά είναι μια εντελώς διαφορετική έννοια, που αναφέρεται στο
φυσικό μέγεθος του κλειδιού.

Από αυτήν την άποψη, ένα κοινό δημόσιο κλειδί RSA 2048-bit παρέχει επίπεδο ασφάλειας
112 bits. Ωστόσο, το ECDSA απαιτεί μόνο δημόσια κλειδιά μεγέθους 224-bit για την παροχή του
ίδιο επίπεδο ασφάλειας 112-bit. Αυτή η εντυπωσιακή διαφορά στο μέγεθος κλειδιού έχει δύο
σημαντικές επιπτώσεις. Τα μικρότερα μεγέθη κλειδιών απαιτούν μικρότερο εύρος ζώνης για τη ρύθμιση ενός
SSL /TLS ροή, που σημαίνει ότι τα πιστοποιητικά ECDSA είναι ιδανικά για κινητά
εφαρμογές. Επιπλέον, τέτοια πιστοποιητικά μπορούν να αποθηκευτούν σε συσκευές με πολλά
πιο περιοριστικοί περιορισμοί μνήμης, γεγονός που επιτρέπει m /TLS στοίβες
εφαρμοστεί σε συσκευές IoT χωρίς να διαθέσει πολλούς πόρους. Που δημοσιεύθηκε
έρευνα, ακόμη και δείχνει ότι το ECDSA είναι πιο αποτελεσματικό [09] για εφαρμογή σε ενσωματωμένο
συσκευές.

Απόδοση & πολυπλοκότητα χρόνου

Οι αλγόριθμοι είναι αφηρημένες συνταγές που περιγράφουν μια μέθοδο για την επίτευξη ενός συγκεκριμένου στόχου.
Στην επιστήμη των υπολογιστών, η απόδοσή τους μετράται μετρώντας τον αριθμό
στοιχειώδεις λειτουργίες που είναι απαραίτητες για την επίτευξη αυτού του προκαθορισμένου τερματισμού
κατάσταση. Αυτή η μέτρηση ονομάζεται χρονική πολυπλοκότητα. Από διαφορετική είσοδο
τα μεγέθη απαιτούν διαφορετικό αριθμό εργασιών, η πολυπλοκότητα του χρόνου είναι συνήθως
εκφράζεται ως συνάρτηση του μεγέθους εισόδου.

Και οι δύο εν λόγω αλγόριθμοι, έχουν περίπου το ίδιο χρονοβόρο
μαθηματικές λειτουργίες, όπως διαιρέσεις και πολλαπλασιασμούς. Έτσι, το μέγεθος εισόδου
(το οποίο σε αυτήν την περίπτωση είναι το μέγεθος των κλειδιών τους) παραμένει το πιο σημαντικό
παράγοντας που επηρεάζει την απόδοσή τους. Πρέπει να γίνει σύγκριση των δύο αλγορίθμων
διακρίνεται μεταξύ της υπογραφής ενός μηνύματος και της επαλήθευσης μιας υπογραφής. Στα περισσότερα
πρακτικές υλοποιήσεις, το RSA φαίνεται να είναι σημαντικά ταχύτερο από το ECDSA το XNUMX
επαλήθευση υπογραφών, αν και είναι πιο αργή κατά την υπογραφή.

Τα πράγματα περιπλέκονται για υψηλότερα επίπεδα ασφάλειας. Για παράδειγμα, στα περισσότερα
κοινή διαμόρφωση ενός επιπέδου ασφαλείας 112 bit, το RSA απαιτεί 2048-bit
έναντι του ECDSA που χρειάζονται κλειδιά 224-bit. Στο επόμενο κοινό επίπεδο των 128 bit, RSA
απαιτεί ένα κλειδί 3072-bit, ενώ το ECDSA μόνο 256 bit. Αυτό οδηγεί σε RSA's
η απόδοση θα μειωθεί δραματικά, ενώ το ECDSA επηρεάζεται ελαφρώς. Οπως και
συνέπεια αυτού του ζητήματος κλιμάκωσης, παρόλο που η RSA φαίνεται πιο αποτελεσματική στο
στιγμή, η συνεχής αύξηση των απαιτήσεων ασφαλείας θα μπορούσε να αποδώσει πολύ καλά
ECDSA η de-facto λύση στο μέλλον.

Μετα-κβαντική αντίσταση

Αλγόριθμος Shor [10] είναι ένας πολύ γνωστός αλγόριθμος για τη διακοπή της χρήσης κλειδιών RSA
κβαντικοί υπολογιστές. Δεδομένου ότι δεν υπάρχουν (δημόσιες) πρακτικές υλοποιήσεις ενός
ένα τέτοιο μηχάνημα, το ακόλουθο είναι μια εικασία για το μέλλον του δημόσιου κλειδιού
κρυπτογράφηση. Τη στιγμή αυτού του γραψίματος, η καλύτερη εφαρμογή του Shor's
αλγόριθμος μπορεί να νικήσει μια κρυπτογράφηση RSA κλειδιού 15-bit. Αν και αυτό δεν ακούγεται
σχετικά με, καθώς όλο και περισσότερη έρευνα κατευθύνεται προς την κβαντική πληροφορική, RSA
θα μπορούσε να αντιμετωπίζει σοβαρό πρόβλημα ανά πάσα στιγμή.

Οι υποστηρικτές του ECDSA δεν πρέπει να γιορτάζουν γρήγορα, επειδή είναι ελλειπτικοί
κρυπτογραφία καμπύλης είναι επίσης ευάλωτο [11] σε μια τροποποιημένη έκδοση του Shor's
αλγόριθμος. Κατά συνέπεια, εάν και οι δύο κρυπτογράφοι μπορούν να σπάσουν από έναν κβαντικό υπολογιστή,
η μόνη αντικειμενική μέτρηση είναι η πολυπλοκότητα που απαιτείται για την εφαρμογή ενός τέτοιου
επίθεση. Σύμφωνα με δημόσια έρευνα, τα κλειδιά RSA 2048-bit απαιτούν 4098 qubits
(και 5.2 τρισεκατομμύρια πύλες Tofolli) να νικήσει, ενώ τα κλειδιά ECDSA 256-bit
απαιτούν μόνο 2330 qubit (και 126 δισεκατομμύρια πύλες Tofolli). Ως εκ τούτου, το RSA είναι περισσότερο
ακριβό να σπάσει, χρησιμοποιώντας μια θεωρητική κβαντική μηχανή.

Συμπέρασμα

Αν και αυτή η σύγκριση δεν είναι καθόλου ολοκληρωμένη, είναι προφανές ότι
Η RSA έχει δικαίως αποκτήσει τη θέση της ως η κορυφαία ψηφιακή υπογραφή
αλγόριθμος για τις περισσότερες εφαρμογές πιστοποιητικών. Ωστόσο, δεδομένου ότι η τεχνολογία είναι πάντα
προχωρώντας με πιο απρόβλεπτους τρόπους, η ευαισθητοποίηση σχετικά με την ασφάλεια και οι ανάγκες είναι επίσης
αυξάνεται. Πριν από περισσότερα από δέκα χρόνια, η ενσωματωμένη ασφάλεια συσκευών ήταν
μυθοπλασία και σήμερα ασφαλείς επικοινωνίες είναι απαραίτητο για κάθε πραγματικό κόσμο
εφαρμογή. Ως αποτέλεσμα, ακόμη και αν το ECDSA είναι σχετικά νεαρό, είναι δικό του
μαντέψτε αν θα αντικαταστήσει το RSA ως πρότυπο για έλεγχο ταυτότητας σε SSL /TLS
υλοποιήσεις.

Εάν εσείς, ο αναγνώστης, δεν μπορείτε ακόμα να αποφασίσετε ποιος αλγόριθμος θα επιλέξετε, υπάρχουν
λύσεις για την υποστήριξη τόσο του ECDSA όσο και του RSA (ως εναλλακτικός μηχανισμός), έως το
η κοινότητα κρυπτογράφησης κερδίζει έναν νικητή Ανατρέξτε στην ενότητα αυτού του άρθρου για το μέλλον
πώς να καθοδηγήσετε.

TL; DR πίνακας

αναφορές

• [01] Αλγόριθμος RSA
• [02] Αλγόριθμος ECDSA
• [03] Κρυπτογραφία δημόσιου κλειδιού
• [04] Ψηφιακοί αλγόριθμοι υπογραφής
• [05] NP πολυπλοκότητα
• [06] SSL v.0.0 RFC
• [07] TLS v.1.2 RFC
• [08] Επίπεδο ασφαλείας
• [09] RSA vs ECC για ενσωματωμένα συστήματα
• [10] Αλγόριθμος του Shor
• [11] Κβαντικές εκτιμήσεις πόρων για ECDL