Πεπερασμένα σώματα: το αριθμητικό σύστημα στο οποίο ζει η κρυπτογραφία

Πρωτότυπη έρευνα από Annkkitaaa

Γιατί η «επανάληψη από την αρχή» είναι το μυστικό θεμέλιο του Zcash

Σειρά: Zcash από τις πρώτες αρχές . Άρθρο 1 . Πεπερασμένα σώματα Κοινό: Νέοι χρήστες. Υποθέτουμε μόνο συνηθισμένη σχολική αριθμητική (πρόσθεση, πολλαπλασιασμός, διαίρεση). Δεν απαιτείται προηγούμενη γνώση κρυπτογραφίας ή ανώτερων μαθηματικών. Τι θα έχεις κατανοήσει: Μια διαισθητική και σωστή κατανόηση των πεπερασμένων σωμάτων, του γιατί τα χρησιμοποιούν οι κρυπτογράφοι και του πού εμφανίζονται μέσα στο Zcash.

Στο Άρθρο 0 γνωρίσαμε πέντε χαρακτήρες: το note, το commitment, το δέντρο commitment των note, το nullifier και την απόδειξη μηδενικής γνώσης. Αφήσαμε μια εκκρεμότητα: από πού προέρχονται πραγματικά όλα τα κλειδιά και οι μυστικές συνταγές; Προέρχονται από αριθμούς. Όχι όμως από τους συνηθισμένους αριθμούς με τους οποίους μεγάλωσες. Προέρχονται από ένα ειδικό, αυτοτελές αριθμητικό σύστημα που ονομάζεται πεπερασμένο σώμα, και σχεδόν κάθε κομμάτι της κρυπτογραφίας στο Zcash είναι χτισμένο πάνω σε αυτό.

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

1. Γιατί να σε ενδιαφέρει;

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

Σκέψου τι συμβαίνει όταν ένας αριθμός γίνεται μεγαλύτερος. Αν σου πω ότι ένας μυστικός υπολογισμός παρήγαγε 8,142,067, ξέρεις ήδη αρκετά: είναι επταψήφιος αριθμός, είναι περιττός, είναι «αρκετά μεγάλος». Το μέγεθος είναι στοιχείο. Και τα στοιχεία είναι ακριβώς όσα ένα σύστημα ιδιωτικότητας δεν μπορεί να επιτρέψει να διαρρεύσουν.

Η κρυπτογραφία θέλει ένα αριθμητικό σύστημα όπου:

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

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

2. Η διαίσθηση: ένα ρολόι

Χρησιμοποιείς ήδη ένα πεπερασμένο σώμα κάθε μέρα. Είναι το ρολόι στον τοίχο σου.

Σε ένα 12ωρο ρολόι, οι αριθμοί επιστρέφουν στην αρχή. Ξεκίνα στις 10, πρόσθεσε 5 ώρες και δεν καταλήγεις στις «15 η ώρα», αλλά στις 3 η ώρα. Το ρολόι έχει μόνο δώδεκα θέσεις, και η μέτρηση μετά την κορυφή απλώς επιστρέφει στην αρχή.

Μόλις συνέβησαν τρία πράγματα που αποτελούν όλο το νόημα αυτού του άρθρου:

1. Ο κόσμος είναι πεπερασμένος. Υπάρχουν ακριβώς δώδεκα θέσεις, ανεξάρτητα από το πόσο καιρό μετράς.
2. Η πρόσθεση συνεχίζει να λειτουργεί. Μπορείς να προσθέτεις ώρες όλη μέρα· πάντα καταλήγεις σε μια έγκυρη θέση του ρολογιού.
3. Το μέγεθος έπαψε να έχει σημασία. Η «3 η ώρα» δεν σου λέει αν μέτρησες 3 ώρες ή 15 ή 27. Η επιστροφή στην αρχή έσβησε την πληροφορία μεγέθους. Αυτό το σβήσιμο είναι ακριβώς η ιδιότητα φιλική προς την ιδιωτικότητα που θέλαμε.

Αυτή η αριθμητική επανάληψης έχει επίσημο όνομα: αρθρωτή αριθμητική. Το ρολόι λειτουργεί «modulo 12», γραμμένο mod 12. Οι μαθηματικοί προτιμούν να μετρούν τις θέσεις ξεκινώντας από το 0, επομένως ένα «ρολόι mod 12» έχει πραγματικά τις θέσεις 0, 1, 2, ..., 11. Ένα ρολόι mod 7 θα είχε θέσεις από 0 έως 6.

Ο ένας κανόνας: Για να υπολογίσεις οτιδήποτε «mod p», κάνε τη συνηθισμένη αριθμητική, έπειτα διαίρεσε με p και κράτησε μόνο το υπόλοιπο. Παράδειγμα mod 7: 5 + 4 = 9, και το 9 αφήνει υπόλοιπο 2 μετά τη διαίρεση με 7, άρα 5 + 4 = 2 (mod 7).

3. Από ένα ρολόι σε ένα σώμα

Ένα ρολόι μάς επιτρέπει να προσθέτουμε. Ένα σώμα είναι η αναβάθμιση: ένα αριθμητικό σύστημα όπου συμπεριφέρονται σωστά και οι τέσσερις πράξεις, συμπεριλαμβανομένης της δύσκολης, της διαίρεσης.

Ανεπίσημα, ένα σώμα είναι οποιαδήποτε συλλογή «αριθμών» όπου μπορείς να προσθέτεις, να αφαιρείς, να πολλαπλασιάζεις και να διαιρείς (με οτιδήποτε εκτός από το μηδέν), και όλοι οι οικείοι κανόνες συνεχίζουν να ισχύουν: η σειρά δεν έχει σημασία στην πρόσθεση ή στον πολλαπλασιασμό, οι παρενθέσεις μπορούν να ομαδοποιηθούν ξανά, υπάρχει ένα 0 και ένα 1, και κάθε αριθμός έχει έναν αρνητικό και (εκτός από το 0) έναν αντίστροφο.

Οι ρητοί αριθμοί είναι σώμα. Οι πραγματικοί αριθμοί είναι σώμα. Αυτό που θέλουμε είναι ένα πεπερασμένο σώμα.

Να το βασικό αποτέλεσμα, και είναι όμορφο:

Πάρε τους ακέραιους αριθμούς 0, 1, ..., p-1 και κάνε όλη την αριθμητική mod p. Αν το p είναι πρώτος αριθμός, το αποτέλεσμα είναι ένα πεπερασμένο σώμα. Το γράφουμε F_p (διαβάζεται «F υπο p»).

Άρα το F_7 = {0, 1, 2, 3, 4, 5, 6} με αριθμητική τύπου ρολογιού mod 7 είναι ένα γνήσιο πεπερασμένο σώμα. Ας το δούμε να λειτουργεί.

Πολλαπλασιασμός στο F_7 (επαληθευμένος)

Κάθε καταχώριση είναι (row x column) mod 7:

Κοίτα τις σειρές από 1 έως 6: καθεμία περιέχει κάθε μη μηδενική τιμή 1..6 ακριβώς μία φορά. Αυτό το μοτίβο «χωρίς επαναλήψεις, χωρίς ελλείψεις» είναι το ορατό αποτύπωμα ενός σώματος.

Διαίρεση: η μαγεία που χρειάζεται έναν πρώτο

Η διαίρεση είναι απλώς «πολλαπλασιασμός με τον αντίστροφο». Στο F_7, ο αντίστροφος (ή αντίστροφο στοιχείο) ενός αριθμού a είναι η τιμή a^(-1) για την οποία ισχύει a x a^(-1) = 1. Διαβάζοντάς τα απευθείας από τον πίνακα:

Έλεγξε ένα: 2 x 4 = 8 = 1 (mod 7). Επομένως, το «διαίρεσε με 2» στο F_7 σημαίνει «πολλαπλασίασε με 4». Κάθε μη μηδενικό στοιχείο έχει έναν σύντροφο. Αυτό είναι που κάνει το F_7 σώμα.

4. Γιατί το μέτρο πρέπει να είναι πρώτο

Αυτή είναι η σημαντικότερη ιδέα του άρθρου, οπότε ας την κάνουμε συγκεκριμένη αντί για αφηρημένη.

Δες τι χαλάει αν προσπαθήσουμε αφελώς να χτίσουμε ένα «σώμα» mod 6 (και το 6 δεν είναι πρώτο):

Υπάρχει κάποιο x με 2 x x = 1 (mod 6); Ελέγχοντάς τα όλα: 2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4. Η απάντηση 1 δεν εμφανίζεται ποτέ. Επομένως το 2 δεν έχει αντίστροφο mod 6. Ακόμη χειρότερα, 2 x 3 = 6 = 0 (mod 6): δύο μη μηδενικοί αριθμοί πολλαπλασιάστηκαν και έδωσαν μηδέν.

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

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

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

5. Η μία φόρμουλα που αξίζει να γνωρίσεις: πώς οι υπολογιστές βρίσκουν αντίστροφους

Διαβάσαμε τους αντίστροφους από έναν πίνακα για το F_7, αλλά ο πρώτος του Zcash έχει εκατοντάδες ψηφία· κανένας πίνακας δεν είναι δυνατός. Υπάρχει μια κλασική συντόμευση, και είναι η μόνη φόρμουλα σε αυτό το άρθρο.

Το Μικρό Θεώρημα του Fermat λέει ότι για έναν πρώτο p και οποιοδήποτε μη μηδενικό a:

a^(p-1) = 1   (mod p)

Αναδιάταξέ το (αφαίρεσε έναν παράγοντα του a) και παίρνεις τον αντίστροφο δωρεάν:

a^(-1) = a^(p-2)   (mod p)

Δοκίμασέ το στο F_7 (p = 7, άρα p - 2 = 5): ο αντίστροφος του 2 θα πρέπει να είναι 2^5 = 32 = 4 (mod 7). Και πράγματι, ο πίνακάς μας έλεγε 2^(-1) = 4. Οι υπολογιστές υψώνουν σε μεγάλες δυνάμεις εξαιρετικά γρήγορα, επομένως αυτό μετατρέπει το «βρες τον αντίστροφο» σε γρήγορο, ακριβή υπολογισμό ακόμη και για γιγάντιους πρώτους.

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

6. Γιατί η κρυπτογραφία ερωτεύτηκε τα πεπερασμένα σώματα

Συνδυάζοντας τη διαίσθηση, εδώ είναι όλη η υπόθεση σε μία σελίδα.

Ένα πεπερασμένο σώμα είναι, σε μία φράση, μια απόλυτα κλειστή, απόλυτα ακριβής, απόλυτα τεράστια παιδική χαρά για την αριθμητική. Όλα τα υπόλοιπα στο Zcash χτίζονται παίζοντας μέσα σε αυτό.

7. Πού βρίσκεται αυτό στο Zcash

Δεν χρειάζεται να δεχτείς με πίστη ότι «το Zcash χρησιμοποιεί πεπερασμένα σώματα». Να ο συγκεκριμένος χάρτης (οι βαθύτεροι μηχανισμοί είναι για επόμενα άρθρα· εδώ απλώς δείχνουμε ότι τα αποτυπώματα είναι πραγματικά).

• Το Sapling (ένα παλαιότερο θωρακισμένο σχέδιο) χτίζει τις αποδείξεις του πάνω σε μια καμπύλη που ονομάζεται BLS12-381, της οποίας το βασικό σώμα χρησιμοποιεί έναν πρώτο μήκους 381 bit. Κάθε συντεταγμένη, κλειδί και στοιχείο απόδειξης είναι στοιχείο ενός πεπερασμένου σώματος χτισμένου πάνω σε αυτόν τον πρώτο.
• Το Orchard (το τρέχον θωρακισμένο σχέδιο) χρησιμοποιεί ένα ζεύγος καμπυλών που ονομάζονται Pallas και Vesta (οι καμπύλες «Pasta»), των οποίων τα σώματα χρησιμοποιούν πρώτους μήκους περίπου 255 bit.
• Το commitment ενός note, το nullifier και οι αριθμοί μέσα σε μια απόδειξη μηδενικής γνώσης από το Άρθρο 0 είναι όλα, στον πυρήνα τους, στοιχεία ενός από αυτά τα πεπερασμένα σώματα. Όταν το πρωτόκολλο λέει «υπολόγισε αυτό το commitment», εννοεί «κάνε αυτή την αριθμητική mod εκείνον τον πρώτο».

Άρα η απάντηση στο ανοιχτό ερώτημα του Άρθρου 0, «από πού προέρχονται οι μυστικές συνταγές;», αρχίζει εδώ: όλα ξεκινούν ως αριθμητική σε ένα πεπερασμένο σώμα. Στο επόμενο άρθρο θα πάρουμε αυτό το σώμα και θα χτίσουμε τα πραγματικά αντικείμενα, σημεία πάνω σε μια ελλειπτική καμπύλη, που γίνονται κλειδιά και commitments.

8. Μια ειλικρινής διευκρίνιση

Για να παραμείνουμε φιλικοί προς νέους χρήστες, απλοποιήσαμε μερικά αληθινά πράγματα. Τα πεπερασμένα σώματα δεν υπάρχουν μόνο στη μορφή F_p· μπορείς επίσης να χτίσεις σώματα με p^n στοιχεία (ονομάζονται σώματα επέκτασης), και αυτά έχουν σημασία για τα «ζευγαρώματα» στα οποία βασίζεται το σύστημα αποδείξεων του Sapling. Παραλείψαμε επίσης τον πλήρη κατάλογο των αξιωμάτων του σώματος και προσπεράσαμε τον τρόπο με τον οποίο επιλέγονται και επαληθεύονται πρώτοι αυτού του μεγέθους. Τίποτα από αυτά δεν αλλάζει τη διαίσθηση που έχεις τώρα· την εξειδικεύει. Θα επαναφέρουμε την ακρίβεια, με επισημάνσεις, όταν τη χρειάζεται κάποιο μεταγενέστερο άρθρο.

9. Σύνοψη

• Η κρυπτογραφία χρειάζεται ένα αριθμητικό σύστημα που είναι πεπερασμένο, ακριβές, αδιάφορο ως προς το μέγεθος, πλήρως αντιστρέψιμο και τεράστιο. Αυτό το σύστημα είναι ένα πεπερασμένο σώμα.
• Η διαίσθηση είναι ένα ρολόι: αριθμητική που επιστρέφει στην αρχή (αρθρωτή αριθμητική), η οποία βολικά σβήνει το «μέγεθος» ενός αριθμού.
• Η αριθμητική με τους αριθμούς 0..p-1 mod έναν πρώτο p δίνει ένα πραγματικό σώμα F_p, όπου μπορείς επίσης να διαιρείς επειδή κάθε μη μηδενικό στοιχείο έχει αντίστροφο.
• Το μέτρο πρέπει να είναι πρώτο: ένα σύνθετο μέτρο δημιουργεί διαιρέτες του μηδενός (όπως 2 x 3 = 0 mod 6) και χαλάει τη διαίρεση.
• Οι υπολογιστές βρίσκουν αντίστροφους γρήγορα μέσω του Μικρού Θεωρήματος του Fermat (a^(-1) = a^(p-2)).
• Στο Zcash, κάθε κλειδί, commitment, nullifier και στοιχείο απόδειξης είναι τελικά στοιχείο ενός μεγάλου πεπερασμένου σώματος (σώματα Pasta 255-bit για το Orchard, σώμα 381-bit για το BLS12-381 του Sapling).

Γλωσσάριο

Συχνές ερωτήσεις

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

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

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

Γιατί αυτοί οι συγκεκριμένοι πρώτοι (255-bit, 381-bit) στο Zcash; Επιλέγονται ώστε οι καμπύλες που χτίζονται πάνω τους να έχουν τη σωστή δομή και αποδοτικότητα για το σύστημα αποδείξεων. Αυτή η «σωστή δομή» είναι το θέμα των επόμενων δύο άρθρων.

Δοκίμασε τη διαίσθησή σου

Στο F_7, πόσο είναι 5 - 6; (Θυμήσου: μείνε μέσα στο {0,...,6} επιστρέφοντας στην αρχή.) (Απάντηση παρακάτω.)

Τι ακολουθεί

Άρθρο 2 . Ελλειπτικές καμπύλες: παίρνουμε το πεπερασμένο σώμα που μόλις χτίσαμε και το χρησιμοποιούμε για να σχεδιάσουμε ένα παράξενο είδος καμπύλης, της οποίας τα σημεία μπορούν να «προστεθούν» μεταξύ τους. Αυτά τα σημεία γίνονται τα κλειδιά και τα commitments του Zcash, και κρύβουν μια μονόδρομη καταπακτή που καθιστά δυνατό ολόκληρο το σύστημα ιδιωτικότητας. Πρώτα η διαίσθηση, όπως πάντα.

Μέρος της σειράς Zcash από τις πρώτες αρχές για το ZecHub. Με άδεια CC BY-SA 4.0.