Σκεφτείτε ένα σενάριο όπου πρέπει να εξασφαλίσετε ένα τραπεζικό θησαυροφυλάκιο. Θεωρείται απολύτως απόρθητο χωρίς κλειδί, το οποίο σας δίνεται την πρώτη μέρα εργασίας. Ο στόχος σας είναι να αποθηκεύσετε με ασφάλεια το κλειδί.
Ας υποθέσουμε ότι αποφασίζετε να έχετε το κλειδί μαζί σας ανά πάσα στιγμή, παρέχοντας πρόσβαση στο θησαυροφυλάκιο όπως απαιτείται. Αλλά γρήγορα θα συνειδητοποιήσετε ότι μια τέτοια λύση δεν έχει καλή κλίμακα στην πράξη, γιατί κάθε φορά που χρειάζεται να είστε φυσικά παρόντες για να ανοίξετε το θησαυροφυλάκιο. Τι γίνεται με τις διακοπές που σου υποσχέθηκαν; Επιπλέον, το ερώτημα είναι ακόμη πιο τρομακτικό: τι θα γινόταν αν χάσατε το μοναδικό κλειδί;
Με την ιδέα των διακοπών, αποφασίζετε να δημιουργήσετε ένα αντίγραφο του κλειδιού και να το εμπιστευτείτε σε άλλον υπάλληλο. Ωστόσο, καταλαβαίνετε ότι και αυτό δεν είναι ιδανικό. Διπλασιάζοντας τον αριθμό των κλειδιών, έχετε επίσης διπλασιάσει τις πιθανότητες κλοπής κλειδιού.
Απελπισμένοι, καταστρέφετε το αντίγραφο και αποφασίζετε να χωρίσετε το αρχικό κλειδί στη μέση. Τώρα, πιστεύετε ότι δύο έμπιστα άτομα με θραύσματα κλειδιών πρέπει να είναι φυσικά παρόντα για να παραλάβουν το κλειδί και να ανοίξουν το θησαυροφυλάκιο. Αυτό σημαίνει ότι ο κλέφτης πρέπει να κλέψει δύο θραύσματα, κάτι που είναι δύο φορές πιο δύσκολο από το να κλέψει ένα κλειδί. Ωστόσο, σύντομα συνειδητοποιείτε ότι αυτό το σχήμα δεν είναι πολύ καλύτερο από ένα μόνο κλειδί, γιατί εάν κάποιος χάσει το μισό κλειδί, το πλήρες κλειδί δεν μπορεί να ανακτηθεί.
Το πρόβλημα μπορεί να λυθεί με μια σειρά από πρόσθετα κλειδιά και κλειδαριές, αλλά αυτή η προσέγγιση θα απαιτήσει γρήγορα много κλειδιά και κλειδαριές. Αποφασίζετε ότι το ιδανικό σχέδιο είναι να μοιραστείτε το κλειδί, έτσι ώστε η ασφάλεια να μην βασίζεται αποκλειστικά σε ένα άτομο. Επίσης, συμπεραίνεις ότι πρέπει να υπάρχει κάποιο όριο για τον αριθμό των θραυσμάτων, έτσι ώστε αν χαθεί ένα κομμάτι (ή εάν το άτομο πάει διακοπές), ολόκληρο το κλειδί παραμένει λειτουργικό.
Πώς να μοιραστείτε ένα μυστικό
Αυτός ο τύπος σχήματος βασικής διαχείρισης σκέφτηκε ο Adi Shamir το 1979 όταν δημοσίευσε το έργο του . Το άρθρο εξηγεί εν συντομία το λεγόμενο 
σχήμα κατωφλίου για την αποτελεσματική διαίρεση μιας μυστικής τιμής (για παράδειγμα, ένα κρυπτογραφικό κλειδί) σε εξαρτήματα. Τότε, πότε και μόνο όταν τουλάχιστον του τα μέρη συναρμολογούνται, μπορείτε εύκολα να αποκαταστήσετε το μυστικό .
Από την άποψη της ασφάλειας, μια σημαντική ιδιότητα αυτού του συστήματος είναι ότι ένας εισβολέας δεν πρέπει να μάθει απολύτως τίποτα εάν δεν έχει τουλάχιστον εξαρτήματα. Ακόμα και η παρουσία τα μέρη δεν πρέπει να δίνουν καμία πληροφορία. Αυτό το ακίνητο το ονομάζουμε σημασιολογική ασφάλεια.
Πολυωνυμική παρεμβολή
Πρόγραμμα κατωφλίου Shamir χτισμένο γύρω από την ιδέα πολυωνυμική παρεμβολή. Εάν δεν είστε εξοικειωμένοι με αυτήν την έννοια, είναι στην πραγματικότητα πολύ απλή. Γενικά, αν έχετε σχεδιάσει ποτέ σημεία σε ένα γράφημα και μετά τα έχετε συνδέσει με γραμμές ή καμπύλες, το έχετε ήδη χρησιμοποιήσει!
Μέσα από δύο σημεία, μπορείτε να σχεδιάσετε απεριόριστο αριθμό πολυωνύμων βαθμού 2. Για να επιλέξετε το μόνο από αυτά, χρειάζεστε ένα τρίτο σημείο. Απεικόνιση:
Θεωρήστε ένα πολυώνυμο με βαθμό ένα, . Αν θέλετε να σχεδιάσετε αυτή τη συνάρτηση σε ένα γράφημα, πόσα σημεία χρειάζεστε; Λοιπόν, γνωρίζουμε ότι αυτή είναι μια γραμμική συνάρτηση που σχηματίζει μια γραμμή και επομένως χρειαζόμαστε τουλάχιστον δύο σημεία. Στη συνέχεια, θεωρήστε μια πολυωνυμική συνάρτηση με βαθμό δύο, . Αυτή είναι μια τετραγωνική συνάρτηση, επομένως απαιτούνται τουλάχιστον τρία σημεία για τη σχεδίαση του γραφήματος. Τι θα λέγατε για ένα πολυώνυμο με βαθμό τρία; Τουλάχιστον τέσσερις τελείες. Και ούτω καθεξής και ούτω καθεξής.
Το πραγματικά ωραίο με αυτή την ιδιότητα είναι ότι, δεδομένου του βαθμού της πολυωνυμικής συνάρτησης και τουλάχιστον σημεία, μπορούμε να εξαγάγουμε επιπλέον σημεία για αυτήν την πολυωνυμική συνάρτηση. Ονομάζουμε την παρέκταση αυτών των πρόσθετων σημείων πολυωνυμική παρεμβολή.
Κάνοντας ένα μυστικό
Ίσως έχετε ήδη καταλάβει ότι εδώ μπαίνει στο παιχνίδι το έξυπνο σχέδιο του Shamir. Ας υποθέσουμε ότι το μυστικό μας - Είναι . Μπορούμε να γυρίσουμε μέχρι το σημείο του γραφήματος και να καταλήξουμε σε μια πολυωνυμική συνάρτηση με βαθμό , που ικανοποιεί αυτό το σημείο. Θυμηθείτε ότι θα είναι το κατώφλι των απαιτούμενων θραυσμάτων, οπότε αν ορίσουμε το όριο σε τρία τμήματα, πρέπει να επιλέξουμε μια πολυωνυμική συνάρτηση με βαθμό δύο.
Το πολυώνυμο μας θα έχει τη μορφή Όπου и είναι τυχαία επιλεγμένοι θετικοί ακέραιοι αριθμοί. Απλώς χτίζουμε ένα πολυώνυμο με ένα βαθμό , όπου ο ελεύθερος συντελεστής - Αυτό είναι το μυστικό μας , και καθένα από τα επόμενα όροι είναι ένας τυχαία επιλεγμένος θετικός συντελεστής. Επιστρέφοντας στο αρχικό παράδειγμα και υποθέτοντας ότι , τότε παίρνουμε τη συνάρτηση .
Σε αυτό το σημείο, μπορούμε να δημιουργήσουμε θραύσματα συνδέοντας μοναδικοί ακέραιοι αριθμοί σε Όπου (γιατί είναι το μυστικό μας). Σε αυτό το παράδειγμα, θέλουμε να διανείμουμε τέσσερα θραύσματα με όριο τριών, επομένως δημιουργούμε τυχαία σημεία και στείλτε έναν πόντο σε καθένα από τα τέσσερα έμπιστα άτομα, τους φύλακες του κλειδιού. Το λέμε και στους ανθρώπους , καθώς θεωρείται δημόσια πληροφορία και είναι απαραίτητη για ανάκτηση .
Μυστική Ανάκτηση
Έχουμε ήδη συζητήσει την έννοια της πολυωνυμικής παρεμβολής και τον τρόπο με τον οποίο βασίζεται στο σχήμα κατωφλίου του Shamir. . Όταν οι τρεις στους τέσσερις διαχειριστές θέλουν να αποκαταστήσουν , χρειάζονται μόνο παρεμβολή με τα μοναδικά τους σημεία. Για να γίνει αυτό, μπορούν να ορίσουν τα σημεία τους και να υπολογίσετε το πολυώνυμο παρεμβολής Lagrange χρησιμοποιώντας τον ακόλουθο τύπο. Εάν ο προγραμματισμός είναι πιο ξεκάθαρος για εσάς από τα μαθηματικά, τότε το pi είναι ουσιαστικά ένας τελεστής for, που πολλαπλασιάζει όλα τα αποτελέσματα, και το σίγμα είναι forπου αθροίζει τα πάντα.
Στο μπορούμε να το λύσουμε ως εξής και να επιστρέψουμε την αρχική μας πολυωνυμική συνάρτηση:
Αφού το ξέρουμε , ανάκτηση γίνεται απλά:
Χρήση μη ασφαλούς αριθμητικής ακεραίων
Αν και έχουμε εφαρμόσει με επιτυχία τη βασική ιδέα του Shamir , έχουμε μείνει με ένα πρόβλημα που μέχρι τώρα αγνοούσαμε. Η πολυωνυμική συνάρτησή μας χρησιμοποιεί μη ασφαλή αριθμητική ακέραιων αριθμών. Σημειώστε ότι για κάθε επιπλέον σημείο που λαμβάνει ένας εισβολέας στο γράφημα συνάρτησής μας, υπάρχουν λιγότερες δυνατότητες για άλλα σημεία. Μπορείτε να το δείτε με τα μάτια σας όταν σχεδιάζετε έναν αυξανόμενο αριθμό σημείων για μια πολυωνυμική συνάρτηση χρησιμοποιώντας ακέραια αριθμητική. Αυτό είναι αντιπαραγωγικό ως προς τον στόχο ασφαλείας που έχουμε δηλώσει, επειδή ένας εισβολέας δεν πρέπει να γνωρίζει απολύτως τίποτα μέχρι να το μάθει τουλάχιστον θραύσματα.
Για να δείξετε πόσο αδύναμο είναι το αριθμητικό σχήμα ακεραίων, εξετάστε ένα σενάριο στο οποίο ο εισβολέας έλαβε δύο βαθμούς και γνωρίζει τις δημόσιες πληροφορίες ότι . Από αυτές τις πληροφορίες, μπορεί να συμπεράνει , ίσο με δύο, και συνδέστε τις γνωστές τιμές στον τύπο и .
Ο εισβολέας μπορεί στη συνέχεια να βρει , μετρώντας :
Αφού έχουμε ορίσει ως τυχαία επιλεγμένοι θετικοί ακέραιοι αριθμοί, υπάρχει περιορισμένος αριθμός δυνατών . Με αυτές τις πληροφορίες, ένας εισβολέας μπορεί να συμπεράνει , γιατί οτιδήποτε μεγαλύτερο από 5 θα κάνει αρνητικός. Αυτό αποδεικνύεται αλήθεια, αφού το έχουμε αποφασίσει
Ο εισβολέας μπορεί στη συνέχεια να υπολογίσει τις πιθανές τιμές αντικαθιστώντας в :
Με περιορισμένες επιλογές για γίνεται σαφές πόσο εύκολο είναι να συλλέξετε και να ελέγξετε τιμές . Υπάρχουν μόνο πέντε επιλογές εδώ.
Επίλυση του προβλήματος με μη ασφαλή ακέραια αριθμητική
Για να διορθωθεί αυτή η ευπάθεια, ο Shamir προτείνει τη χρήση αρθρωτής αριθμητικής με αντικατάσταση επί Όπου и είναι το σύνολο όλων των πρώτων αριθμών.
Ας θυμηθούμε γρήγορα πώς λειτουργεί η αρθρωτή αριθμητική. Τα ρολόγια χειρός είναι μια γνωστή έννοια. Χρησιμοποιεί ένα ρολόι δηλαδή . Μόλις ο ωροδείκτης περάσει δώδεκα, επιστρέφει στο ένα. Μια ενδιαφέρουσα ιδιότητα αυτού του συστήματος είναι ότι κοιτάζοντας μόνο το ρολόι, δεν μπορούμε να συμπεράνουμε πόσες στροφές έχει κάνει ο ωροδείκτης. Ωστόσο, αν γνωρίζουμε ότι ο ωροδείκτης έχει περάσει 12 τέσσερις φορές, μπορούμε να προσδιορίσουμε πλήρως τον αριθμό των ωρών που έχουν περάσει με έναν απλό τύπο Όπου είναι ο διαιρέτης μας (εδώ ), - αυτός είναι ο συντελεστής (πόσες φορές ο διαιρέτης χωρίς υπόλοιπο μπαίνει στον αρχικό αριθμό, εδώ ), και είναι το υπόλοιπο, το οποίο συνήθως επιστρέφει μια κλήση στον χειριστή του modulo (εδώ ). Η γνώση όλων αυτών των τιμών μας επιτρέπει να λύσουμε την εξίσωση για , αλλά αν παραλείψουμε τον συντελεστή, δεν θα μπορέσουμε ποτέ να επαναφέρουμε την αρχική τιμή.
Μπορούμε να δείξουμε πώς αυτό βελτιώνει την ασφάλεια του κυκλώματος μας εφαρμόζοντας το κύκλωμα στο προηγούμενο παράδειγμά μας και χρησιμοποιώντας . Η νέα μας πολυωνυμική συνάρτηση , και τα νέα σημεία . Τώρα οι φύλακες κλειδιών μπορούν και πάλι να χρησιμοποιήσουν πολυωνυμική παρεμβολή για να ανακατασκευάσουν τη συνάρτησή μας, μόνο που αυτή τη φορά οι πράξεις πρόσθεσης και πολλαπλασιασμού πρέπει να ακολουθούνται από αναγωγή συντελεστών. (π.χ ).
Χρησιμοποιώντας αυτό το νέο παράδειγμα, ας υποθέσουμε ότι ο εισβολέας έχει μάθει δύο από αυτά τα νέα σημεία, , και ενημέρωση του κοινού . Αυτή τη φορά, ο εισβολέας, με βάση όλες τις πληροφορίες που έχει, εμφανίζει τις παρακάτω λειτουργίες, όπου είναι το σύνολο όλων των θετικών ακεραίων και αντιπροσωπεύει τον συντελεστή συντελεστή .
Τώρα ο εισβολέας μας ξαναβρίσκει , υπολογισμός :
Μετά προσπαθεί ξανά να αποσυρθεί αντικαθιστώντας в :
Αυτή τη φορά έχει σοβαρό πρόβλημα. Λείπουν τιμές από τον τύπο , и . Δεδομένου ότι υπάρχει άπειρος αριθμός συνδυασμών αυτών των μεταβλητών, δεν μπορεί να λάβει πρόσθετες πληροφορίες.
Θέματα ασφαλείας
Το μυστικό σχέδιο κοινής χρήσης του Shamir προτείνει ασφάλεια πληροφοριών. Αυτό σημαίνει ότι τα μαθηματικά είναι ισχυρά ακόμη και απέναντι σε έναν εισβολέα με απεριόριστη υπολογιστική ισχύ. Ωστόσο, το σχήμα εξακολουθεί να περιέχει αρκετά γνωστά ζητήματα.
Για παράδειγμα, το σχήμα Shamir δεν δημιουργεί θραύσματα προς έλεγχο, δηλαδή, οι άνθρωποι είναι ελεύθεροι να παρουσιάζουν ψεύτικα θραύσματα και να παρεμβαίνουν στην ανάκτηση του σωστού μυστικού. Ένας εχθρικός φύλακας θραυσμάτων με αρκετές πληροφορίες μπορεί ακόμη και να δημιουργήσει ένα άλλο θραύσμα αλλάζοντας κατά την κρίση σας. Αυτό το πρόβλημα λύνεται με επαληθεύσιμα συστήματα κοινής χρήσης μυστικών, όπως το σχήμα Feldman.
Ένα άλλο πρόβλημα είναι ότι το μήκος οποιουδήποτε θραύσματος είναι ίσο με το μήκος του αντίστοιχου μυστικού, επομένως το μήκος του μυστικού είναι εύκολο να προσδιοριστεί. Αυτό το πρόβλημα λύνεται από τα ασήμαντα υλικό παραγεμίσματος μυστικό με αυθαίρετους αριθμούς μέχρι ένα σταθερό μήκος.
Τέλος, είναι σημαντικό να σημειωθεί ότι οι ανησυχίες μας για την ασφάλεια ενδέχεται να υπερβαίνουν το ίδιο το σύστημα. Για πραγματικές κρυπτογραφικές εφαρμογές, υπάρχει συχνά ο κίνδυνος επιθέσεων πλευρικού καναλιού, όταν ένας εισβολέας προσπαθεί να εξάγει χρήσιμες πληροφορίες από το χρόνο εκτέλεσης της εφαρμογής, την προσωρινή αποθήκευση, τα σφάλματα κ.λπ. Εάν αυτό είναι ανησυχητικό, θα πρέπει να εξετάσετε προσεκτικά τη χρήση διασφαλίσεων κατά την ανάπτυξη, όπως συναρτήσεις και αναζητήσεις σταθερού χρόνου, να αποτρέψετε την αποθήκευση μνήμης στο δίσκο και να εξετάσετε ορισμένα άλλα πράγματα που δεν εμπίπτουν στο πεδίο εφαρμογής αυτού του άρθρου.
Демо
Επί υπάρχει μια διαδραστική επίδειξη του σχεδίου μυστικής κοινής χρήσης του Σαμίρ. Η επίδειξη έγινε με βάση τη βιβλιοθήκη , το οποίο είναι από μόνο του μια θύρα JavaScript ενός δημοφιλούς προγράμματος . Σημειώστε ότι ο υπολογισμός μεγάλων τιμών , и μπορεί να χρειαστεί λίγη ώρα.
Πηγή: www.habr.com