Εισαγωγή

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

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

Αυτό το άρθρο θα σας δώσει μια εισαγωγή στις αρχές πίσω από τα κρυπτοσυστήματα δημόσιου κλειδιού και θα σας παρουσιάσει στο Santana Rocha-Villas Boas (SRVB) , ένα κρυπτοσύστημα που αναπτύχθηκε από τον συγγραφέα του άρθρου και τον καθηγητή Daniel Santana Rocha. Τη στιγμή της σύνταξης, οι συντάκτες του αλγορίθμου προετοιμάζουν μια καμπάνια που περιλαμβάνει μια οικονομική επιβράβευση σε όποιον καταφέρει να σπάσει τον κώδικα. Δεδομένου ότι το άρθρο θα καλύπτει λεπτομερώς τη λειτουργικότητα του αλγορίθμου, αυτό είναι το καλύτερο μέρος για να ξεκινήσετε την αναζήτηση του βραβείου. Περισσότερες πληροφορίες είναι διαθέσιμες στο Ιστότοπος SRVB .

Τι είναι το Cryptosystem;

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

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

Προκειμένου ένα κρυπτοσύστημα (δεδομένη τεχνική κρυπτογραφίας) να θεωρείται ασφαλές από τους χρήστες του, πρέπει να λάβει την έγκριση της διεθνούς κοινότητας εμπειρογνωμόνων, και επομένως να είναι γνωστό στο κοινό, το οποίο είναι γνωστό ως Αρχή του Kerckhoffs . Ωστόσο, αυτή η ίδια κατάσταση εκθέτει το σύστημα σε έλεγχο από την παγκόσμια κοινότητα κρυπτοανάλυσης, η οποία θα προσπαθήσει να επινοήσει τρόπους συστηματικής διακοπής των κρυπτογράφησης.

Πώς μπορεί κάποιος να κάνει μια δεδομένη διαδικασία κρυπτογράφησης αρκετά μυστική ώστε μόνο οι επιδιωκόμενοι πράκτορες μπορούν να την αποκρυπτογραφήσουν, ενώ ταυτόχρονα είναι αρκετά δημόσια ώστε η κοινότητα κρυπτοανάλυσης του κόσμου να μπορεί να πιστοποιήσει την ανθεκτικότητά της; Η απάντηση είναι ένα στοιχείο που αποτελεί βασικό στοιχείο της Κρυπτολογίας: το κλειδί. Ένα κλειδί ενός κρυπτοσυστήματος είναι μια παράμετρος είτε για τους αλγόριθμους κρυπτογράφησης ή αποκρυπτογράφησης είτε και για τους δύο. Κρατώντας τις παραμέτρους μυστικές, παρά την οικογένεια αλγορίθμων, μπορούν να επιτευχθούν και οι δύο αντιφατικές απαιτήσεις. Υπό την προϋπόθεση ότι η οικογένεια των παραμέτρων είναι αρκετά μεγάλη (πιθανώς άπειρη) και κάθε ένα από τα συστατικά της μπορεί να αποδειχθεί ότι έχει επαρκείς ιδιότητες, δεν θα είναι εφικτό για τους επιτιθέμενους να καθορίσουν τις παραμέτρους μόνο με επιθεώρηση.

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

Ένας αλγόριθμος δημιουργίας κλειδιών δεν πρέπει να δημιουργεί προβλέψιμη / αναπαραγώγιμη έξοδο ως αποτέλεσμα τυπικής χρήσης. Δεδομένου ότι οι αλγόριθμοι εκτελούν διαδικασίες χωρίς καμία έξυπνη διαδικασία, το ερώτημα γίνεται πώς μπορεί να γίνει αυτό. Η απάντηση μετατρέπει τους αλγόριθμους δημιουργίας κλειδιών σε χάρτες που μετατρέπουν ένα μεγάλο αριθμό πραγματικά τυχαίων bit σε κλειδιά. Πραγματικά τυχαία bit μπορούν να αποκτηθούν από το λειτουργικό σύστημα, το οποίο τα δημιουργεί από αβεβαιότητα στο σύμπαν. Ορισμένες πηγές θα ήταν η κίνηση του ποντικιού σας, οι καθυστέρηση πακέτων δικτύου ή ακόμη και αποκλειστικό υλικό, ανάλογα με την εφαρμογή.

---

Κρυπτοσυστήματα δημόσιου κλειδιού

Ετοιμαστείτε να εκπλαγείτε ξανά, γιατί τώρα θα εισαγάγουμε μια ιδέα που φαίνεται να έρχεται σε αντίθεση με αυτό που μόλις είπαμε: το δημόσιο κλειδί.

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

Ας υποθέσουμε ότι η Αλίκη συνεργάζεται με τον Μπομπ και θέλουν να διατηρήσουν τις αλληλεπιδράσεις εργασίας τους ασφαλείς χρησιμοποιώντας κρυπτογράφηση. Μπορούν να συναντηθούν και να ανταλλάξουν τα κλειδιά κρυπτογράφησής τους, δίνοντας ο ένας στον άλλο μια μονάδα flash USB με τα κλειδιά τους. Τι γίνεται όμως αν η Άλις και ο Μπομπ βρίσκονται σε διαφορετικές ηπείρους. Πώς να δημιουργήσετε ένα ασφαλές κανάλι όπου δεν υπάρχουν;

Η αποστολή κλειδιών μέσω email δεν θα ήταν επιλογή, καθώς ο ανταγωνιστής τους Eve μπορεί να παρακολουθήσει την ανταλλαγή και να χρησιμοποιήσει τα κλειδιά για να διαβάσει όλα τα κρυπτογραφημένα δεδομένα μετά. Εάν είχαν οποιοδήποτε άλλο ψηφιακό κανάλι μέσω του οποίου θα μπορούσαν να μεταδώσουν αυτά τα ευαίσθητα δεδομένα, τότε δεν θα χρειαζόταν κρυπτογράφηση και, επομένως, κλειδιά, στην πρώτη θέση. Η αποστολή του κλειδιού μέσω φυσικής αλληλογραφίας θα μπορούσε επίσης να υποκλαπεί, γιατί απαιτεί την ανταλλαγή ευαίσθητων πληροφοριών για να ξεκινήσετε. Αποστολή α steganographed κλειδί κρύβοντας μέσα σε άλλα δεδομένα θα ήταν έξυπνο, αλλά άχρηστο, εκτός εάν ο αποστολέας είναι σίγουρος ότι ο παραλήπτης, και ο παραλήπτης μόνος του, γνωρίζει την ύπαρξη ενός τέτοιου μηνύματος και ξέρει πώς να το εξαγάγει. Όπως συμβαίνει, η συνειδητοποίηση της ύπαρξης ενός μηνύματος μαζί με την περιγραφή του τρόπου εξαγωγής του κλειδιού από τα δεδομένα είναι ένας τύπος κλειδιού από μόνο του, που μας φέρνει πίσω στο τετράγωνο.

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

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

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

Η απάντηση βρίσκεται στον τομέα των μαθηματικών που σχετίζεται στενότερα με τον προγραμματισμό, το υπολογιστική πολυπλοκότητα . Όποιος έχει ερευνήσει αρκετά βαθιά σε μαθηματικά προβλήματα έχει ακούσει για μετασχηματισμούς που είναι εύκολο να γίνουν με έναν τρόπο, αλλά δύσκολο να γίνει το αντίστροφο. Στο λογισμό, για παράδειγμα, η εύρεση ενός παραγώγου εγχειριδίου είναι συνήθως μια απλή άσκηση, ενώ κάνετε το αντίστροφο (όπως η επίλυση κάπως μη ασήμαντου ακέραιου ή φυσικού βιβλίου ΩΔΗ ή PDE , για παράδειγμα) απαιτεί μια πιο διερευνητική διαδικασία πρώτων υποθετικών οικογενειών συναρτήσεων που είναι εγγυημένες (ή τουλάχιστον εύλογες) για να περιέχουν τις λύσεις και να επιλύουν αντίστροφα προβλήματα για να βρουν λύσεις από αυτές τις οικογένειες.

Ένα παράδειγμα που χρησιμοποιείται πραγματικά στο Κρυπτοσύστημα RSA πολλαπλασιάζει τα μεγάλα prime έναντι του factoring του προκύπτοντος προϊόντος χωρίς να γνωρίζει ήδη τους παράγοντες. Το να κάνετε πολλαπλασιασμό είναι ασήμαντο, αλλά το factoring απαιτεί να κάνετε τυχαία ^[2] μαντέψτε τους πρωταρχικούς παράγοντες, που έχουν εκατοντάδες ψηφία. Μια σημαντική ιδιότητα της επιχείρησης είναι η ανάγκη να κλιμακωθεί καλά. Η προσθήκη μερικών ψηφίων στο μέγεθος των πρωταρχικών αριθμών στο RSA θα έχει ως αποτέλεσμα ένα κλειδί που απαιτεί χιλιάδες φορές περισσότερες λειτουργίες για να σπάσει ενώ προσθέτει μια μικρή αύξηση της πολυπλοκότητας στη διαδικασία κρυπτογράφησης. Σε γενικές γραμμές, το προϊόν των πρωταρχικών αριθμών χρησιμοποιείται για κρυπτογράφηση, ενώ το ζεύγος πρωταρχικών παραγόντων χρησιμοποιείται για την αποκρυπτογράφηση.

Με όλα αυτά κατά νου, ας ρίξουμε μια ματιά στον τρόπο λειτουργίας του κρυπτοσυστήματος SRVB.

Ο Υποκείμενος Αλγόριθμος - Εξετάζοντας το SRVB

Το πρόβλημα αθροίσματος υποσυνόλου

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

Δεδομένου του ακέραιου $ w $ και $ v_1, cdot cdot cdot, v_N in Z $ βρείτε την ακολουθία $ b_1, cdot cdot cdot, b_N in {0,1} $, έτσι ώστε $ sum_ {i = 1} ^ {N} v_i b_i = w $.

Είναι σαφές ότι αυτό το πρόβλημα μπορεί να δημιουργηθεί επιλέγοντας τυχαία N ακέραιους αριθμούς, επιλέγοντας τυχαία ένα υποσύνολο αυτών και αθροίζοντας αυτό το υποσύνολο - το οποίο είναι ασήμαντο.

Μια αναζήτηση brute-force θα είχε μια πολυπλοκότητα $ O (N * 2 ^ N) $, υπολογίζοντας για κάθε συνδυασμό τιμών των $ b $ s. Μια πιο αποτελεσματική προσέγγιση δόθηκε από Horowitz και Sahni το 1972 , με πολυπλοκότητα $ O (N * 2 ^ {N / 2}) $. Το πρόβλημα είναι τουλάχιστον τόσο δύσκολο αν αντικαταστήσουμε τα $ b $ s και $ w $ με $ k $ -διάστατα διανύσματα ακεραίων. Το βασίλειο όπου πρέπει να αντιμετωπιστεί αυτό το πιο δύσκολο πρόβλημα, πρέπει επίσης να έχει ισομορφισμός με δαχτυλίδι όπου συμβαίνει μια ευκολότερη έκδοση του ίδιου προβλήματος, όπως θα δούμε παρακάτω. Για το λόγο αυτό, το SRVB εκμεταλλεύεται το πρόβλημα αθροίσματος υποσυνόλου Γκάους ακέραιοι , όπου $ k = 2 $.

Υπάρχει μια ειδική περίπτωση όπου αυτό το πρόβλημα γίνεται εύκολο να υπολογιστεί μέσω της χρήσης ενός άπληστου αλγορίθμου. Αν ταξινομήσουμε τους συντελεστές κλιμάκωσης ακολουθίας $ v_1, cdot cdot cdot, v_N $ στον οποίο κάθε ακέραιος αριθμός στην ακολουθία είναι μεγαλύτερος από το άθροισμα όλων των ακεραίων που προηγήθηκαν ($ forall i, sum_ {j = 1} ^ {i-1} v_jυπερσυμπληρωματική ακολουθία .

Ακολουθεί μια απλή περιγραφή της άπληστης λύσης για αυτήν την περίπτωση:

1. Ξεκινήστε με $ i = N $, τον τρέχοντα παρατηρούμενο παράγοντα και $ w ’= w $, το υπόλοιπο $ w $

2. Εάν ο τρέχων συντελεστής κλιμάκωσης είναι πολύ μεγάλος για να χωρέσει σε αυτό που απομένει από $ w $, που σημαίνει $ v_i> w ’$, ορίστε $ b_i = 0 $ και συνεχίστε στο επόμενο βήμα. Διαφορετικά γνωρίζουμε ότι ο συντελεστής κλιμάκωσης πρέπει να είναι στη σειρά (αφού οι υπόλοιποι παράγοντες είναι μικρότεροι από $ v_i $) και ορίζουμε $ b_i = 1 $.

3. $ w ’ Leftarrow w’ - v_i * b_i $, $ i Leftarrow i - 1 $. Εάν $ i> 0 $, επιστρέψτε στο βήμα 2.

4. Βεβαιωθείτε ότι, τώρα, $ w ’== 0 $, διαφορετικά το πρόβλημα ήταν κατεστραμμένο

Αυτό λειτουργεί επειδή γνωρίζουμε ότι όλοι οι πολλαπλασιαστές μικρότεροι από τον τρέχοντα παρατηρούμενο δεν μπορούν να καλύψουν συλλογικά το μεγαλύτερο μέρος του (υπο) αθροίσματος $ w ’$ όσο ο τρέχων πολλαπλασιαστής μπορεί. Έτσι, εάν το υπόλοιπο ποσό είναι μεγαλύτερο από τον τρέχοντα συντελεστή, γνωρίζουμε με βεβαιότητα ότι όλοι οι ακόλουθοι παράγοντες μαζί θα αποτύχουν να αθροιστούν χωρίς τη βοήθεια του τρέχοντος παράγοντα. Από την άλλη πλευρά, δεδομένου ότι όλοι οι πολλαπλασιαστές είναι θετικοί, εάν ο τρέχων συντελεστής $ v_i $ είναι μεγαλύτερος από το υπόλοιπο άθροισμα $ w ’$, η προσθήκη οποιουδήποτε άλλου παράγοντα θα έκανε το αποτέλεσμα να ξεπεράσει το $ w’ $ ακόμη περισσότερο.

Ας δημιουργήσουμε μια σημείωση για το υπόλοιπο άρθρο. Επιλέγουμε $ v_1, cdot cdot cdot, v_n $ και $ w $ ως τους παράγοντες και το άθροισμα της αλληλουχίας υπέρβασης, ενώ $ u_1, cdot cdot cdot, u_n $ και $ y $ θα είναι δημόσια διαθέσιμες παράμετροι που παρέχονται για την ανάκτηση $ b_1, cdot cdot cdot, b_n $.

Με μια ακολουθία $ u_1, cdot cdot cdot, u_n $ επιλεγμένη, έτσι ώστε να μην αυξάνεται υπερβολικά και ο αριθμός $ y $ να είναι δημόσια διαθέσιμος, δεν παρέχονται δημόσια αρκετές πληροφορίες για την ανάκτηση της ακολουθίας $ b_1, cdot cdot cdot , b_n $. Ωστόσο, εάν υπάρχει μια υπεραπλουστευμένη ακολουθία $ v_1, cdot cdot cdot, v_n $ που θα μπορούσε να αντικαταστήσει την ακολουθία $ u_1, cdot cdot cdot, u_n $, θα μπορούσε κανείς να χρησιμοποιήσει αυτήν την ακολουθία για να λύσει το πρόβλημα με μια άπληστη προσέγγιση.

Παρακάτω θα δείξουμε πώς λειτουργεί.

Χρήση αθροισμάτων υποσυνόλου σε προηγούμενο κρυπτοσύστημα

Σε 1978, Ralph Merkle και Martin Helman , επινόησε έναν τρόπο εκμετάλλευσης αυτών των δύο παραδειγμάτων σακιδίων και του γραμμικότητα της λειτουργίας συντελεστή για την οικοδόμηση της σύνδεσης μεταξύ των δύο ακολουθιών που περιγράφονται στην προηγούμενη ενότητα - συνεπώς σύλληψη ενός Κρυπτοσυστήματος Public-Key. Η ιδέα ήταν να μεταμορφωθεί το εύκολο σακίδιο (αυτό που αποτελείται από τον υπερσυγκρότημα φορέα ακέραιων) στον σκληρό (αυτόν που δεν διαθέτει αυτήν την ιδιότητα) μέσω γραμμικής λειτουργίας (ο συντελεστής) με μυστικούς τελεστές. Ο μετασχηματισμός συνίσταται στον πολλαπλασιασμό κάθε $ v_i $ με $ theta $ και το υπόλοιπο αυτού του προϊόντος με $ alpha $, όπου $ alpha gt sum_ {i = 1} ^ N v_i $ και $ gcd ( alpha, theta) = 1 $ (δύο περιορισμοί που θα δικαιολογηθούν σύντομα). Το αποτέλεσμα, η ακολουθία $ u_1, ldots, u_N $, δεν αυξάνεται πλέον και μπορεί να θεωρηθεί σκληρό σακίδιο .

Μια τυχαία παραλλαγή της ακολουθίας $ u_1, ldots, u_N $ θα δοθεί στο συμβαλλόμενο μέρος που θέλει να κρυπτογραφήσει και να μας στείλει ένα μήνυμα. Η παραλλαγή γίνεται έτσι ώστε ένα τρίτο μέρος να δυσκολεύεται να μαντέψει ποια είναι η αρχική υπερσυμπίεση ακολουθία. Τα μπλοκ bit ενός μηνύματος χρησιμοποιούνται ως συντελεστές $ b_1, ldots, b_N $. Η κρυπτογράφηση γίνεται πολλαπλασιάζοντας την ακολουθία κλειδιών με αυτήν την ακολουθία συντελεστών και αθροίζοντας τους πολλαπλασιασμούς σε ένα αποτέλεσμα, που θα ονομάσουμε $ y $. Μόνο ο κάτοχος του ιδιωτικού κλειδιού μπορεί να μετατρέψει $ y $ στα αντίστοιχα $ w $ που θα αποκτηθούν εάν αυτά τα ίδια μπλοκ $ b_1, ldots, b_N $ θα πολλαπλασιαστούν με το εύκολοι ακέραιοι (η ακολουθία $ v_1, ldots, v_N $). Αυτό γίνεται πολλαπλασιάζοντας το $ y $ με το $ theta ^ {- 1} $, το πολλαπλασιαστικό αντίστροφο $ $ theta $ modulus $ alpha $ (του οποίου η ύπαρξη εξαρτάται από αυτήν την κατάσταση $ gcd ( alpha, theta) = 1 $). Με άλλα λόγια, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. Μετά από αυτό, υπολογίζουμε $ w = (y * theta ^ {- 1}) bmod a $. Ο λόγος για τον οποίο αυτό είναι εγγυημένο να λειτουργεί είναι το γραμμικότητα του συντελεστή , δηλαδή, ότι ο γραμμικός συνδυασμός των υπολειμμάτων ισούται με το υπόλοιπο του γραμμικού συνδυασμού.

Εάν εφαρμόσουμε διαδοχικά τον ορισμό του $ u $, του δακτυλίου πηλίκου και της ιδιότητας γραμμικότητας του τελεστή συντελεστή, βλέπουμε την αντιστοιχία:

$ begin {align} y & = sum_ {i = 1} ^ N b_iu_i newline & = sum_ {i = 1} ^ N b_i (v_i * theta bmod alpha) newline & = sum_ { i = 1} ^ N b_i * v_i * theta bmod alpha newline & = left [ sum_ {i = 1} ^ N b_i * v_i * theta right] bmod alpha newline & = αριστερά [ sum_ {i = 1} ^ N b_i * v_i δεξιά] * theta bmod alpha newline & = w * theta bmod alpha end {align} $

Και έτσι το εύκολο ποσό $ w $ μπορεί να ανακτηθεί πολλαπλασιάζοντας και τις δύο πλευρές με $ theta ^ {- 1} $ και λαμβάνοντας το συντελεστή με $ alpha $. Για να γίνει αυτό, πρέπει να γνωρίζουμε και τα $ alpha $ και $ theta $ (που επιτρέπουν σε κάποιον να υπολογίσει εύκολα $ theta ^ {- 1} $), τα οποία πρέπει να παραμείνουν ιδιωτικά ως μέρη του ιδιωτικού κλειδιού.

Ένας μοναδικός περιορισμός, $ alpha gt sum_ {i = 1} ^ N v_i $, αφέθηκε αδικαιολόγητος και ακολουθεί η εξήγηση για αυτό: Η ισότητα μεταξύ της δεύτερης και της τρίτης γραμμής αποτελείται από μια ισότητα μεταξύ τάξεις καταλοίπων απο πηλίκο δαχτυλίδι ακέραιων modulo $ alpha $. Με άλλα λόγια, δηλώνει την ισότητα των υπολοίπων μελών μόνο όταν διαιρείται με $ alpha $, που δεν είναι επαρκής προϋπόθεση για την ισότητα των ίδιων των μελών . Ως αποτέλεσμα, περισσότερα από ένα διάνυσμα αξιών $ b $ θα μπορούσαν να αντιστοιχιστούν σε ένα μόνο $ y $, το οποίο εμποδίζεται περιορίζοντας το μέγιστο δυνατό υποσύνολο (δηλαδή το άθροισμα όλων των δεμάτων $ v_i $) $ w_ {max} $ σε να είναι μικρότερο από $ alpha $ για οποιονδήποτε συνδυασμό τιμών $ b $.

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

---

Το κρυπτοσύστημα Santana Rocha - Villas Boas (SRVB)

Το 2016, μετά από μερικές καταιγίδες με τον συγγραφέα αυτού του άρθρου σχετικά με διαφορετική έμπνευση ^[3] δυνατότητες ενός κρυπτοσυστήματος, ο Daniel Santana Rocha είχε την ιδέα να αντικαταστήσει $ theta $ και $ alpha $ από τον Gaussian Integers. Για περισσότερους τεχνικούς λόγους, αυτή η προσέγγιση οδηγεί στην αντίσταση ενάντια στην προαναφερθείσα επίθεση Shamir.

Συνέλαβε επίσης ένα μπλοκ bit που αποτελείται από πολλά βήματα του γραμμικού συνδυασμού του a που περιγράφηκε προηγουμένως σκληρό σακίδιο . Σε καθένα από αυτά, ένας νέος (Gaussian) ακέραιος, ισοδύναμος με έναν, υψηλότερος από το άθροισμα όλων των προηγούμενων θα προστέθηκε στο τέλος της ακολουθίας, ενώ το τρέχον μικρότερο θα πέσει.

Ισχύει διαφορετικός αλλά κομψός ανάλογος περιορισμός για $ alpha $, ο οποίος είναι πλέον ακέραιος αριθμός Gauss. Χρειαζόμαστε $ w_ {max} leq vert alpha vert ^ 2 $. Ο λόγος είναι πολύ δύσκολο να τυποποιηθεί, αλλά ευτυχώς μπορεί εύκολα να διαισθηθεί από μια κομψή περιγραφή:

Φανταστείτε ένα τετράγωνο δικτυωτό πλέγμα στο επίπεδο των πολύπλοκων αριθμών, του οποίου η πλευρά είναι μια υπόταση ενός δεξιού τριγώνου καθετί a και b, παράλληλα με τους πραγματικούς και φανταστικούς άξονες. Ένα παράδειγμα τέτοιου πλέγματος δίνεται παρακάτω. Guassian integers modulo $ alpha = a + bi $ μπορεί να αναπαρασταθεί από σημεία που βρίσκονται μέσα σε ένα τέτοιο πλέγμα. Μέσα σε ένα τέτοιο πλέγμα υπάρχουν $ vert alpha vert ^ 2 $ διακριτά σημεία. Εάν διαλέξουμε ένα αρκετά μεγάλο $ alpha $, μπορούμε να ταιριάξουμε όλους τους γραμμικούς συνδυασμούς του εύκολου σακιδίου.

Αυτή είναι η γραφική παράσταση του ισομορφισμού $ f: Z / n rightarrow Z [i] / ( alpha) $, όπου $ n = 13 $ και $ alpha = a + bi = 3 + 2i $ (σημειώστε ότι $ n $ και $ alpha $ ικανοποιούν πράγματι $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $ όπως απαιτείται). Οι κουκκίδες αντιπροσωπεύουν τους Gaegian Integers, δηλαδή τους σύνθετους αριθμούς $ a + bi $, όπου $ a $ και $ b $ είναι ακέραιοι. Ως συνήθως, ο οριζόντιος άξονας αντιπροσωπεύει το πραγματικό μέρος, ενώ ο κάθετος αντιπροσωπεύει το φανταστικό μέρος. Έτσι, η μετακίνηση μιας κουκκίδας προς τα δεξιά ή προς τα αριστερά ισοδυναμεί με την προσθήκη +1 ή -1 στην τρέχουσα τιμή του, αντίστοιχα. Ομοίως, η μετακίνηση μιας κουκκίδας προς τα πάνω ή προς τα κάτω αντιστοιχεί στην προσθήκη + i ή -i, αντίστοιχα.

Οι κόκκινες κουκκίδες είναι αυτές που ισοδυναμούν με $ 0 bmod ( alpha) $. Εκτός από αυτά, χρωματίσαμε επίσης 4 ακόμη ζεύγη κουκκίδων.

Χρώμα	Equivalent to … mod α
Πορτοκάλι	$ 1 $
Πράσινος	$ i $
Μπλε	$ -1-i $
Βιολέτα	$ 1-i $

Ο ισομορφισμός $ f $ ορίζεται από τον μετασχηματισμό του στοιχείου $ i $ th της κυκλικής ακολουθίας $ (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ στο στοιχείο $ i $ th της επίσης κυκλικής ακολουθίας κουκίδων στο σχήμα, που τηρεί τους ακόλουθους κανόνες:

1. Ξεκινά από την κόκκινη κουκκίδα της πρώτης σειράς.
2. Ακολουθεί τα οριζόντια δεξιά βέλη. εκτός από
3. Όταν ακολουθείτε τα βέλη οδηγεί την ακολουθία έξω από το πλέγμα, θα έφτανε σε ένα από τα μη μαύρα σημεία. Αντί να πηγαίνει σε αυτό το σημείο, μεταβαίνει στο ίδιο χρωματιστό σημείο (δηλαδή, το ισοδύναμο σημείο modulo $ alpha $) μέσα στο ίδιο τετράγωνο. και τελικά
4. Όταν αυτό το μη μαύρο σημείο τυχαίνει να είναι κόκκινο (το οποίο συμβαίνει αφού περάσουν όλα τα άλλα χρώματα), η ακολουθία μεταβαίνει στην πάνω κόκκινη κουκκίδα, ενεργοποιώντας έτσι τον κύκλο.

Για να χαρτογραφήσετε τουλάχιστον $ Y $ φυσικούς ακέραιους, πρέπει να πάρετε ένα τετράγωνο με την περιοχή $ vert alpha vert ^ 2 $ (όπου $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ είναι, από Πυθαγόρειο θεώρημα , το μέτρο της πλευράς του) τουλάχιστον τόσο υψηλό.

Παρατηρήστε ότι κάθε 'άλμα' αλλάζει τον αριθμό σειράς $ r $ σε $ r leftarrow (r + b) (mod a + b) $ αν κάποιος μετρήσει τις σειρές από πάνω προς τα κάτω και, ισοδύναμα, σε $ r αριστερό βέλος (r + a) (mod a + b) $ εάν μετράει από κάτω προς τα πάνω. Ως εκ τούτου, η απαραίτητη και επαρκής συνθήκη για κάθε σειρά (και τελεία) για περιαγωγή ακριβώς μία φορά σε κάθε κύκλο είναι ότι το μέγεθος των άλματος είναι συμπιεσμένο με τον αριθμό των σειρών ή, με άλλα λόγια, $ gcd (a, a + b) = gcd (b, a + b) = 1 $. Λόγω ιδιοτήτων του μεγαλύτερου κοινού χειριστή διαιρέτη, και τα δύο είναι ισοδύναμα με $ gcd (a, b) = 1 $.

Ο Y. S. Villas Boas παρατήρησε την ανάγκη για συντροφικότητα $ $ $ και $ b $. Προκειμένου να διατηρηθεί η υπέρταση, κάθε νέος ακέραιος $ w $ που προστίθεται στο τέλος της ακολουθίας πρέπει να ξεπεράσει το άθροισμα όλων των τρεχόντων ($ w> sum_ {i = 1} ^ k v_i $). Παρατήρησε ότι για να επιτευχθεί αυτό, οι πολλαπλασιαστικοί συντελεστές τους $ b_i $ θα πρέπει να είναι τουλάχιστον 1, και έτσι, κάθε bit δεν θα μπορούσε να αντιστοιχιστεί στους συντελεστές 0 και 1. Εάν οι συντελεστές ήταν 0 και 1, μόνο το μπλοκ αποτελούμενο μόνο από αυτά θα ικανοποιούσε την υπέρταση. Για το λόγο αυτό, τα bit 0 και 1 χαρτογραφήθηκαν αντίστοιχα στους πολλαπλασιαστικούς συντελεστές 1 και 2.

sum_ {i = 1} ^ k v_i $ και μελλοντικές εξισώσεις $ sum $, δεν μπορώ να καταλάβω πώς να κάνω τα επάνω και κάτω μέρη να βρίσκονται στην πραγματικότητα πάνω και κάτω από το σύμβολο αθροίσματος. Ο σύζυγός μου μου λέει ότι είναι εντάξει, αλλά το αφήνω σε εσένα. ->

Τέλος, και λιγότερο ασήμαντα: κατά τη διάρκεια κάθε βήματος της αποκωδικοποίησης, ένας νέος ακέραιος $ v_1 $ θα βρεθεί ως λύση της εξίσωσης $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} b_i v_i $, όπου όλα τα $ v_i $ και $ b_i $ είναι γνωστά για $ 1

Μια τελική τεχνική προς επίλυση είναι η περίπτωση κατά την οποία το μέγεθος σε byte του μηνύματος δεν είναι πολλαπλάσιο του μεγέθους του μπλοκ. Με άλλα λόγια, τι να κάνετε με τα πιθανά εναπομείναντα byte του τελευταίου μπλοκ δεδομένων έτσι ώστε, μόλις ανακτηθούν τα μπλοκ δεδομένων, να διατηρηθούν όλα τα byte του αρχικού περιεχομένου, αλλά όχι περισσότερο από αυτά; Αυτό το επιλύσαμε επαναλαμβάνοντας μία φορά το τελευταίο byte του μηνύματος. Αυτό το αντίγραφο, στη συνέχεια, ακολουθείται από μια τυχαία ακολουθία στην οποία κάθε στοιχείο απαιτείται μόνο να είναι διαφορετικό από το προηγούμενο. Έτσι, όταν ανακτώνται τα μπλοκ δεδομένων, το τελευταίο από αυτά ή, στη χειρότερη περίπτωση, αυτή πριν από την τελευταία περικόπτεται στην τελευταία επανάληψη των byte. ^[4]

Ας δείξουμε τώρα ένα παράδειγμα του κρυπτοσυστήματος SRVB.

Ξεκινάμε με τις παραμέτρους:

$ k = $ 4;

$ m = 4 $;

που αποδίδει μήκος μπλοκ $ l = 4 * 4 = 16 $ και μια ακολουθία υπέρτασης $ k + 1 = 5 $ φυσικούς ακέραιους, που λειτουργεί— δηλαδή, γραμμικά συνδυασμένος, προσαρτημένος με το αποτέλεσμα αυτού του γραμμικού συνδυασμού και μειώθηκε στα τελευταία $ k + 1 $ στοιχεία του - $ m = 4 $ φορές.

Για λόγους απλότητας, αφήστε τα ακόλουθα να είναι το (υπέρυθρη) διάνυσμα του $ v_i $:

$ (1,2,4,8,16) $

Πράγματι, η ακολουθία των πέντε πρώτων δυνάμεων του 2, απλώς και μόνο επειδή αυτή είναι η υπερσυμπίεση ακολουθία με πέντε στοιχεία και τις μικρότερες αυστηρά θετικές τιμές (αποφεύγοντας έτσι ένα 0 στο δημόσιο κλειδί, το οποίο θα δώσει ασήμαντα τον ανταποκριτή 0 του ομολόγου του ).

Όπως είπαμε νωρίτερα, για $ alpha = a + bi $, οι ακέραιοι αριθμοί $ a $ και $ b $ πρέπει να είναι coprime και σύμφωνα με τον νέο περιορισμό που αναφέραμε, πρέπει να ζητήσουμε $ a ^ 2 + b ^ 2 = vert alpha vert ^ 2 geq W $. Ένας γρήγορος υπολογισμός αποδίδει $ W = 1590 $. Επειδή $ sqrt {1590} simeq 39,8 $, ένα πολύ βολικό $ alpha $ που θα επιλεγεί θα είναι $ alpha = 39 + 40i $, γιατί είναι αρκετά μεγάλο για να φιλοξενήσει έναν ισομορφισμό με ένα δακτύλιο ακέραιων με στο τουλάχιστον 1590 στοιχεία, ενώ ταυτόχρονα ικανοποιεί $ gcd (a, b) = 1 $. Επίσης, πρέπει να διαλέξουμε $ theta $ έτσι ώστε $ gcd (a, theta) = 1 $ ^[5] και κατά προτίμηση αυτό δεν είναι πολύ χαμηλό, έτσι ώστε $ (a_1 * theta) \% alpha neq v_1 * theta $, (επίσης για να αποφύγετε τη διανομή πληροφοριών). $ theta = 60 $ κάνει τη δουλειά, αποδίδοντας:

$ -19-1i, 1 + 38i, 3-3i, 6-6i, 12-12 $ ^[6]

Ας βρώσουμε λοιπόν τα χέρια μας βρώμικα. Λάβετε το μήνυμα b. Αρχικά το χαρτογραφούμε σε μια σειρά byte σύμφωνα με ASCII και η σύμβασή μας για περικοπή μπλοκ δεδομένων:

Hello ApeeScape!

Δεδομένου ότι το μπλοκ δεδομένων μας έχει μήκος 16 bits = 2 byte και το μήνυμά μας έχει 13 χαρακτήρες, καταλήγουμε με 7 μπλοκ δεδομένων των 2 byte το καθένα, όπου το τελευταίο περιέχει δύο φορές την αναπαράσταση bit του χαρακτήρα «!». Ας κρυπτογραφήσουμε το πρώτο μπλοκ βήμα προς βήμα. Δώστε ιδιαίτερη προσοχή γιατί τα bit κάθε byte λαμβάνονται κατά σειρά από τη σημασία τους.

$ m = 01001000 01100101 $

• Πρώτο nibble του πρώτου byte: $ (0,0,0,1) rightarrow (1,1,1,1,2) cdot (-19-1i, 1 + 38i, 3-3i, 6-6i, 12 -12i) = 15 + 4i $
• Δεύτερο nibble του πρώτου byte: $ (0,0,1,0) rightarrow (1,1,1,2,1) cdot (1 + 38i, 3-3i, 6-6i, 12-12i, 15 + 4) = 49 + 9i $
• Πρώτο nibble του δεύτερου byte: $ (0,1,0,0) rightarrow (1,1,2,1,2) cdot (3-3i, 6-6i, 12-12i, 15 + 4i, 49 + 9i) = 106-10i $
• Δεύτερο nibble του δεύτερου byte: $ (0,1,1,0) rightarrow (1,1,2,2,1) cdot (6-6i, 12-12i, 15 + 4i, 49 + 9i, 106- 10i) = 252-2i $

Και έτσι, μόλις χαρτογραφήσαμε

'Αυτός' $ Rightarrow (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) $

Το υπόλοιπο του κρυπτογραφημένου μηνύματος έχει ως εξής:

'Ll' $ Rightarrow (12-12i, 21-2i, 61-3i, 185-31i, 367-59i) $

'O' $ Rightarrow (12-12i, 25 + 33i, 65 + 32i, 111 + 44i, 244 + 124i) $

'To' $ Rightarrow (12-12i, 9 + 10i, 46 + 12i, 149 + 5i, 277 + 31i) $

'Pt' $ Rightarrow (12-12i, 3 + 16i, 46 + 12i, 73 + 23i, 201 + 49i) $

'Al' $ Rightarrow (12-12i, 4 + 54i, 44 + 53i, 117 + 193i, 231 + 389i) $

'!!' $ Rightarrow (12-12i, 4 + 54i, 32 + 65i, 63 + 92i, 121 + 247i) $

Τώρα, για την αποκρυπτογράφηση, έχουμε $ theta ^ {- 1} = 60 ^ {- 1} = 27 + i $:

$ ($ 'He' $ Rightarrow) $ $ (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) * theta ^ {- 1} \% alpha = (16,47 , 93.223.527) $

Τώρα, έρχεται ο άπληστος αλγόριθμος:

Πρώτον, αφαιρούμε κάθε συντελεστή που πολλαπλασιάζεται με έναν, επειδή είναι γνωστό ότι έχουν συνεισφέρει τουλάχιστον μία φορά για το τελευταίο, αποδίδοντας:

• Δεύτερο nibble του δεύτερου byte:

$ T leftarrow (527-233-93-47-16) = 148 $

$ (T geq 223) = (148 geq 223) = false Rightarrow b_1 = 0; T αριστερό βέλος (T - 0 * 223) = 148 $

$ (T geq 93) = (148 geq 93) = true Rightarrow b_2 = 1; T αριστερό βέλος (T - 1 * 93) = 55 $

$ (T geq 47) = 55 geq 47) = true Rightarrow b_3 = 1; T αριστερό βέλος (T - 1 * 47) = 8 $

$ (T geq 16) = 8 geq 16) = false Rightarrow b_4 = 0; T αριστερό βέλος (T - 0 * 16) = 8 $

Αποτέλεσμα: 0110;

Υπόλοιπο: 8 (προστέθηκε στην αρχή της ακολουθίας ως νέο χαμηλότερο στοιχείο).

Πτώση 527 από το τελικό της τρέχουσας ακολουθίας.

• Πρώτο nibble του δεύτερου byte:

$ T leftarrow (233-93-47-16-8) = 59 $

$ (T geq 93) = (59 geq 93) = false Rightarrow b_1 = 0; T αριστερό βέλος (T - 0 * 93) = 59 $

$ (T geq 47) = (59 geq 47) = true Rightarrow b_2 = 1; T αριστερό βέλος (T - 1 * 47) = 12 $

$ (T geq 16) = (12 geq 16) = false Rightarrow b_3 = 0; T αριστερό βέλος (T - 0 8 16) = 12 $

$ (T geq 8) = (12 geq 8) = true Rightarrow b_4 = 1; T αριστερό βέλος (T - 0 * 12) = 4 $

Αποτέλεσμα: 0101;

Υπόλοιπο: 4 (προστέθηκε στην αρχή της ακολουθίας ως νέο χαμηλότερο στοιχείο).

Πτώση 233 από το τελικό της τρέχουσας ακολουθίας.

• Δεύτερο nibble του πρώτου byte:

$ T leftarrow (93 - 47 - 16 - 8 - 4) = 18 $

$ (T geq 47) = (18 geq 47) = false Rightarrow b_1 = 0; T αριστερό βέλος (T - 0 * 47) = 18 $

$ (T geq 16) = (18 geq 16) = true Rightarrow b_2 = 1; T αριστερό βέλος (T - 1 * 16) = 2 $

$ (T geq 8) = (2 geq 8) = false Rightarrow b_3 = 0; T αριστερό βέλος (T - 0 * 8) = 2 $

$ (T geq 4) = (2 geq 4) = false Rightarrow b_4 = 0; T αριστερό βέλος (T - 0 * 4) = 2 $

Αποτέλεσμα: 0100;

Υπόλοιπο: 2 (προστέθηκε στην αρχή της ακολουθίας ως νέο χαμηλότερο στοιχείο).

Πτώση 93 από το τελικό της τρέχουσας ακολουθίας.

• Πρώτο nibble του πρώτου byte:

$ T leftarrow (47-16-8-4-2) = 17 $

$ (T geq 16) = (17 geq 16) = true Rightarrow b_1 = 1; T αριστερό βέλος (T - 1 * 16) = 1 $

$ (T geq 8) = (1 geq 8) = false Rightarrow b_2 = 0; T αριστερό βέλος (T - 0 * 8) = 1 $

$ (T geq 4) = (1 geq 4) = false Rightarrow b_3 = 0; T αριστερό βέλος (T - 0 * 4) = 1 $

$ (T geq 2) = (1 geq 4) = false Rightarrow b_4 = 0; T αριστερό βέλος (T - 0 * 2) = 1 $

Αποτέλεσμα: 1000;

Υπόλοιπο: 1 (προστέθηκε στην αρχή της ακολουθίας ως νέο χαμηλότερο στοιχείο).

Πτώση 47 από το τελικό της τρέχουσας ακολουθίας.

Ως αποτέλεσμα, έχουμε ανακτήσει το μπλοκ δεδομένων: '01001000 01100101' που περιέχει τους δύο πρώτους χαρακτήρες 'Αυτός', του μηνύματός μας. Όχι μόνο αυτό, έχουμε επίσης ανακτήσει σωστά την ακολουθία superincreasing ιδιωτικού κλειδιού $ (1,2,4,8,16) $.

Οι άλλοι χάρτες μπλοκ δεδομένων πηγαίνουν με τον ίδιο τρόπο.

---

Σύγκριση με τα κύρια κρυπτοσυστήματα δημόσιου κλειδιού

Το SRVB είναι:

1. Εντελώς δωρεάν και κοινό.

2. Πολύ απλούστερο και ευκολότερο να κατανοηθεί και να εφαρμοστεί ΚΑΙ ΤΑ ΛΟΙΠΑ ^[7] ;

3. Άφθονο σε πλήκτρα και ως εκ τούτου σχεδόν χωρίς κόστος, αντίθετα, για παράδειγμα RSA , που βασίζεται σε πρώτους αριθμούς, που είναι ακριβά .

Μπορούμε ήδη να συνοψίσουμε τις πιο πιθανές ευπάθειες. Δεδομένου ότι το SRVB κατεβαίνει από το MH, είναι εύκολο να υποπτευόμαστε ότι θα ήταν ευάλωτο σε μια γενίκευση του Επίθεση Shamir ή κάποιο άλλο που το σπάει. Αν και ο συγγραφέας είχε λόγους να πιστεύει ότι αυτό δεν θα συνέβαινε, δεν έχει γίνει ακόμη επιβεβαίωση (κάτι που είναι πολύ χαρακτηριστικό όταν ασχολείται με κρυπτοσυστήματα).

---

Τι έπεται?

Ο Rocha παρατήρησε μερικές γενικεύσεις για τους δακτυλίους πηλίκου που θα μπορούσαν να οδηγήσουν σε αύξηση της πολυπλοκότητας της κρυπτοανάλυσης. Θα διερευνήσουμε επίσης αυτές τις δυνατότητες.

Η Γραμμική Αλγεβρική Απόκρυψη

Όπως συμβαίνει, κατά τη διάρκεια της ανάπτυξης και της τεκμηρίωσης του SRVB, το Villas Boas βρήκε μια ακόμη προσέγγιση για τη βελτίωση της έννοιας του κρυπτοσυστήματος δημόσιου κλειδιού που δεν θα εξηγηθεί με πολλές λεπτομέρειες εδώ, προκειμένου αυτό το άρθρο να μην γίνει πολύ μεγάλο και κουραστικό, αλλά εδώ είναι μια αδυναμία. Εάν δεν καταφέρετε να το καταλάβετε, μην ανησυχείτε, απλώς μείνετε συντονισμένοι για την κυκλοφορία του επόμενου άρθρου μας, στο οποίο θα εξετάσουμε λεπτομερέστερα τις λεπτομέρειες: Δείτε το υποσύνολο $ y $, του, ας πούμε, Στοιχεία δακτυλίου πηλίκου $ N $ $ u_i $ (που αντιστοιχούν ισομορφικά στους θετικούς ακέραιους $ v_i $ της εξαιρετικά αυξανόμενης ακολουθίας, όπως πριν) ως πολλαπλασιασμός ενός διανύσματος σειράς αυτών των $ u_i $ από ένα διάνυσμα στήλης $ B $ ( για δυαδικά) μηδενικών και αυτών ^[8] .

$ y = sum_ {i = 1} ^ n u_i b_i = (u_1, cdot cdot cdot, u_n) ^ T cdot (b_1, cdot cdot cdot, b_n) $ = UB,

όπου $ b_i σε {0,1} $

Τώρα, φανταστείτε ότι, αντί αυτού του διανύσματος $ u_i $, έχετε, στα αριστερά ένα $ n $ από $ N $ (με $ n [9] n by n matrix R στα αριστερά, ορίζοντας το n by N matrix P:

P = RV

Η ιδέα είναι ότι ο Bob χρησιμοποιεί το P ως νέο δημόσιο κλειδί του. Λόγω της τυχαιότητας του R, του διανύσματος

$ Y = PB = RV B = RW $

έχει τις πληροφορίες $ w $ κρυμμένες από το θόρυβο σε άλλες σειρές του V. Ο Bob υπολογίζει επίσης εκ των προτέρων και αποθηκεύει το διάνυσμα γραμμής S που ικανοποιεί:

$ R ^ T S ^ T = e_1 $

Όταν, η Άλις στέλνει το Υ στον Μπομπ, βρίσκει απλά τον SY, επειδή:

$ SY = S (PB) = S ((RV) B) = SRVB = {e_1} ^ T R ^ {- 1} ((RV) B) = $

(μέχρι στιγμής μόνο ορισμοί)

$ {e_1} ^ T (V B) = {e_1} ^ T W = w $

(Τώρα, αξιοποιώντας το συσχέτιση για να ακυρώσετε το Rs)

και στη συνέχεια προχωρά όπως πριν για να εξαγάγετε το διάνυσμα $ b_i $ από $ w $ μέσω του άπληστου αλγορίθμου.

Έτσι, με μία λέξη, η Γραμμική Αλγεβρική Απόκρυψη εκμεταλλεύεται τη συσχέτιση του μητρικού πολλαπλασιασμού (το γεγονός ότι θα μπορούσαμε να επεκτείνουμε τους όρους και στη συνέχεια να λειτουργήσουμε τα συστατικά τους σε μια νέα σειρά, υπό την προϋπόθεση ότι διατηρούμε την ακολουθία όλων των τελεστών στη σειρά) σε « γραμμικά «ανακατέψτε» και μετά φιλτράρετε (στην κρυπτογράφηση και στην αποκρυπτογράφηση αντίστοιχα) θόρυβο προς / από $ w $. Και στην οριακή περίπτωση $ n = 1 $, το σύστημα επιστρέφει κομψά στο αρχικό στην προσέγγιση του Rocha.

Η εκστρατεία SRVB - μια πρόκληση βραβείων

Όπως εξηγήθηκε προηγουμένως, σύμφωνα με την αρχή του Kerckhoffs, η εμπειρία δείχνει ότι η αρχαιότητα ενός δημοσίως γνωστού αδιάσπαστου κρυπτοσυστήματος είναι η κύρια πηγή αξιοπιστίας αυτού, πολύ περισσότερο από οποιαδήποτε θεωρητική επιχειρηματολογία από τους ίδιους τους συγγραφείς, εκτός από οτιδήποτε άλλο, επειδή η οριστική απόδειξη Η αποτελεσματικότητα των αλγορίθμων συνήθως δεν είναι διαθέσιμη.

Και εδώ είναι η μεγάλη μας ευκαιρία να εφαρμόσουμε αυτές τις έννοιες στην πράξη για να κερδίσουμε ένα μεγάλο χρηματικό έπαθλο: Έχοντας επίγνωση αυτού του γεγονότος, ξεκινήσαμε τα προαναφερθέντα καμπάνια , το οποίο βασικά είναι ένα crowdfunding για ένα έπαθλο που απονέμεται αυτόματα στο πρώτο που καταφέρνει να σπάσει ένα μήνυμα. Τα χρήματα πρόκειται να μετατραπούν σε bitcoin σε ένα δεδομένο πορτοφόλι του οποίου το ιδιωτικό κλειδί θα είναι κρυπτογραφημένο και δημοσιευμένο σε SRVB, έτσι ώστε οποιοσδήποτε μπορεί να αποκρυπτογραφήσει μπορεί απλά να πάρει τα χρήματα ανώνυμα, χωρίς ερωτήσεις.

Ευχαριστίες

Αυτό το άρθρο ειδικότερα και ολόκληρο το έργο SRVB Crypto γενικά έχει βοηθήσει πολύ ο καθηγητής. Charles F. de Barros , επίκουρος καθηγητής στο Ομοσπονδιακό Πανεπιστήμιο του Σάο João Del Rei . Ο καθηγητής Barros μας παρείχε μια τεχνική ανασκόπηση του ίδιου του κρυπτοσυστήματος SRVB. Κρίνω απαραίτητο να υποταχθώ πριν τολμήσω να δημοσιεύσω, και ότι σίγουρα θα χρειαζόμουν πολύ περισσότερο να κάνω μόνος μου.

Επιπλέον, θα ήθελα επίσης να εκφράσω τη βαθιά ευγνωμοσύνη μου στον καθηγητή Adnan Ademovic για την εξαιρετικά διορατική, προσεκτική και υπομονετική του εργασία ως συντάκτης αυτού του άρθρου.

---

Γλωσσάριο

1. Κρυπτολογία / Κρυπτογραφία: Η επιστήμη / πρακτική της δημιουργίας ενός μηνύματος σχεδόν αδύνατο να ερμηνευτεί χωρίς ένα συγκεκριμένο σύνολο οδηγιών (σε αυτό το πλαίσιο, το λεγόμενο «κλειδί»), επιτρέποντας έτσι στους πράκτορες που μοιράζονται αυτές τις οδηγίες να επικοινωνούν με ασφάλεια, ακόμη και αν τα αγγίξουν τρίτοι.
2. Στεγνογραφία: Η επιστήμη / πρακτική της απόκρυψης ενός μηνύματος σε ένα άλλο μέσω της προσθήκης φαινομενικά αβλαβών τροποποιήσεων στο τελευταίο.
3. Δημιουργία κλειδιών: η χαρτογράφηση (αναμενόμενων) τυχαίων εισόδων σε (ως τυχαία) έγκυρα κλειδιά ·
4. Κρυπτογράφηση / Κωδικοποίηση: Η εύκολα υπολογιζόμενη χαρτογράφηση ενός εύκολα ερμηνεύσιμου μηνύματος σε ένα άλλο που είναι δύσκολο ή αδύνατο να ερμηνευτεί, μέσω ενός (όπως προσδιορίζεται τυχαία) στοιχείου ο ένας ανταποκριτής στο κλειδί μιας οικογένειας αλγορίθμων (από την αρχή του Kerckhoffs, δημόσια γνωστή και επικυρωμένη) ·
5. Αποκρυπτογράφηση / Αποκωδικοποίηση: Η εύκολη υπολογιστική χαρτογράφηση που αποτελείται από το αντίστροφο του προηγούμενου, επίσης καθορίζεται από ένα στοιχείο (όπως προσδιορίζεται τυχαία, και ως εκ τούτου, άγνωστο και δύσκολο να μαντέψει κανείς από τρίτους) στοιχείο _again, το οποίο αντιστοιχεί στο κλειδί_ του a (από το ίδια αρχή, συνήθως γνωστή) οικογένεια αλγορίθμων, που έτσι εξάγει το αρχικό μήνυμα όταν εισάγεται με το κρυπτογραφημένο.
6. Κρυπτοσύστημα: Μια τριάδα της οικογένειας των αλγορίθμων κωδικοποίησης, της οικογένειας των αντίστοιχων αλγορίθμων αποκρυπτογράφησης και ενός αλγορίθμου δημιουργίας κλειδιών.
7. Σύμμαχοι: Οι πράκτορες με τους οποίους προορίζεται η επικοινωνία και οι οποίοι αναμένεται να ενεργήσουν σύμφωνα με τους κανόνες του πρωτοκόλλου.
8. Εχθροί / τρίτα μέρη: Οι πράκτορες με τους οποίους η επικοινωνία δεν προορίζεται, αλλά προσπαθούν, εντούτοις, να παρακολουθήσουν την επικοινωνία και να παρακάμψουν την ασφάλεια που ενισχύεται από το κρυπτοσύστημα.
9. Ασφαλές κανάλι: Οποιοδήποτε πρωτόκολλο (διαδικασία) για επικοινωνία που είναι εύκολο στη χρήση, ενώ ταυτόχρονα αποτρέπει αποτελεσματικά τρίτα μέρη να ερμηνεύσουν εύλογα τι εννοούν οι χρήστες του.
10. Μη ασφαλές κανάλι: οποιοδήποτε κανάλι (δηλαδή, πρωτόκολλο ή διαδικασία) που, όπως υποδηλώνει το όνομα, δεν είναι ασφαλές κανάλι.
11. Σπάζοντας ένα κλειδί: Η διαδικασία ανακάλυψης ενός κλειδιού μέσω δημόσιων κομματιών πληροφοριών (όπως ένα κρυπτογραφημένο μήνυμα ή δημόσιο κλειδί) εκτός από το ίδιο το κλειδί που θα ανακαλυφθεί και η οποία δεν αναμενόταν να επιτρέψει εφικτά την ανακάλυψη του κλειδιού. Δεδομένου ότι οι πληροφορίες που προκύπτουν από αυτήν τη διαδικασία παρέχουν την αποκρυπτογράφηση των μηνυμάτων, αυτή είναι μια συγκεκριμένη περίπτωση…
12. Σπάζοντας / αποκρυπτογραφήστε ένα μήνυμα: Οποιοσδήποτε τρόπος για να εξαχθεί το αρχικό περιεχόμενο ενός κρυπτογραφημένου μηνύματος μόνο μέσω του ίδιου του κρυπτογραφημένου μηνύματος και άλλων πληροφοριών που δεν αναμενόταν να επαρκούν για την αφαίρεση του αρχικού περιεχομένου.
13. Σπάζοντας ένα Cryptosystem: Ανακάλυψη ενός συστηματικού τρόπου για να σπάσει εφικτά οποιοδήποτε μήνυμα είναι κρυπτογραφημένο με αυτήν τη μέθοδο κάτω από οποιαδήποτε παράμετρο.
14. Αρχή Kerckhoffs / Desideratum / Axiom / Νόμος: Μια κρυπτολογική αρχή που πήρε το όνομά της από τον ολλανδικό κρυπτογράφο Auguste Kerckhoffs , σύμφωνα με το οποίο, για να κριθεί ένα κρυπτοσύστημα ασφαλές, όλα σχετικά με αυτό εκτός από τα (ιδιωτικά) κλειδιά του πρέπει να είναι δημόσια γνώσης ·
15. Κλειδί: Μυστική παραμετροποίηση ενός κρυπτοσυστήματος που του επιτρέπει να είναι αδύνατο να μαντέψει (και κατά συνέπεια να σπάσει) από τρίτα μέρη, ενώ ταυτόχρονα επικυρώνεται από την κοινότητα των κρυπτοαναλυτών (σύμφωνα με την αρχή του Kerckhoffs) ·
16. Συμμετρικό Cryptosystem: Κάθε κρυπτοσύστημα στο οποίο αρκεί οποιαδήποτε παράμετρος για την κωδικοποίηση για εύκολη συναγωγή της παραμέτρου για αποκωδικοποίηση και, για αυτόν τον λόγο, πρέπει να παραμείνει ιδιωτικό. Μπορεί κανείς να το επαναδιατυπώσει λέγοντας ότι οι παράμετροι κρυπτογράφησης και αποκρυπτογράφησης είναι και οι δύο ισοδύναμες με το κλειδί.
17. Ασύμμετρη / Κρυπτοσύστημα δημόσιου κλειδιού: Οποιοδήποτε κρυπτοσύστημα για το οποίο υπάρχει τρόπος να εκφραστούν οι παράμετροι για την κωδικοποίηση που δεν αρκεί για να συναχθεί κατά νόμο η αντίστοιχη παράμετρος για την αποκωδικοποίηση, επιτρέποντάς της να αποσταλεί σε συμμάχους μέσω ενός μη ασφαλούς καναλιού, ή ακόμη και να δημοσιοποιηθεί, και δημιουργώντας έτσι μια ασφαλή κανάλι όπου δεν υπήρχε κανένα?
18. Δημόσιο κλειδί: Ένα στοιχείο ενός ασύμμετρου κρυπτοσυστήματος που αρκεί για την παραμετροποίηση της κρυπτογράφησης, αλλά δεν επαρκεί για τη δυνατότητα συμπερίληψης της παραμέτρου αποκρυπτογράφησης, δηλαδή του…
19. Ιδιωτικό κλειδί: Ένα στοιχείο ενός ασύμμετρου κρυπτοσυστήματος που αρκεί για την παραμετροποίηση της αποκρυπτογράφησης και έτσι πρέπει να φυλάσσονται ιδιωτικά και συνήθως αρκεί επίσης για την παραμετροποίηση της κρυπτογράφησης.

---

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

^[2] Αν και υπάρχουν τεχνικές για τη βελτίωση αυτού του μαντέρματος, παραμένει πολύ πιο δύσκολο να το ανακαλύψετε παρά να τον πολλαπλασιάσετε.

^[3] Η πρώτη έμπνευση ήταν να κοιτάξουμε το δέντρο της εικασίας tau , ένα άπειρο δέντρο ριζωμένο στον αριθμό 1, του οποίου οι άλλοι κόμβοι αποτελούνται από ακέραιους με αποτέλεσμα μια δυαδική λειτουργία αθροίσματος, αφαίρεσης ή πολλαπλασιασμού μεταξύ προηγούμενων κόμβων, πιθανώς ενός κόμβου που λειτουργεί με τον ίδιο. Ο στόχος της θεωρίας σχετίζεται με το βάθος, σε αυτό το δέντρο, στο οποίο εμφανίζεται κάθε ακέραιος. Είναι προφανές ότι είναι δύσκολο να βρεθείς μεγάλος αριθμός σε χαμηλά κλαδιά (ακόμα κι αν χαλαρώσουμε την ανάγκη για αυτό), αλλά είναι άμεσο να ελέγξουμε εάν μια δεδομένη σειρά λειτουργιών παράγει πράγματι ένα δεδομένο αποτέλεσμα.

^[4] Αυτή δεν είναι σίγουρα η πιο φυσική προσέγγιση, αλλά υιοθετώντας αυτήν, διασφαλίζεται ότι αυτή η πλήρωση byte (ονομάζεται υλικό παραγεμίσματος ) ...

1. Αποκρύπτει το μέγεθος της επένδυσης (διαφορετικά, για παράδειγμα κλοπή ciphertext ) και αποκρύπτει το τέλος του μηνύματος, αποδίδοντας έτσι επιλεγμένες-απλές επιθέσεις πιο δύσκολο;
2. Ενισχύει την κατανομή των bits όσο το δυνατόν πιο κοντά στο ομοιόμορφο.

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

^[5] Μην κάνετε λάθος: αυτός ο μεγαλύτερος κοινός διαιρέτης είναι ο Gaussian, ενώ ο προηγούμενος είναι πραγματικός.

^[6] … Το οποίο δεν είναι τέλειο, διότι δίνει εύκολα το γεγονός ότι τα τρία τελευταία στοιχεία είναι ανάλογα με τα 1, 2 και 4. Αλλά, πάλι, χάριν απλότητας, θα αγνοήσουμε αυτήν την λεπτομέρεια.

^[7] … Το οποίο είναι τόσο περίπλοκο που υπάρχουν μερικά διαβόητες περιπτώσεις αποτυχίας εφαρμογής και διατήρησης πρωτοκόλλων που βασίζονται σε αυτό .

^[8] Εδώ, δεν θα υιοθετήσουμε την προσέγγιση του Rocha για ένα μπλοκ πολλαπλών γραμμικών συνδυασμών, το οποίο μας επιτρέπει επίσης να μετατρέψουμε τυχαία το bis για να τα κρύψουμε ακόμη περισσότερο.

^[9] Αν και δεν είναι εντελώς τυχαίο. Η μεταφορά του πρέπει να εκτείνεται στον δευτερεύοντα χώρο που δημιουργείται από το διάνυσμα $ e_1 = (1,0,…, 0) $.