Εισαγωγή
Στο Cairo, μία από τις βασικές έννοιες που θα συναντήσεις είναι ο τύπος felt252, γνωστός και ως στοιχείο σώματος.
Αυτός ο τύπος αναπαριστά ακεραίους μέσα σε ένα συγκεκριμένο εύρος που ορίζεται από έναν μεγάλο πρώτο αριθμό $P$.
Σε αυτή την άσκηση, θα δουλέψεις αποκλειστικά με τον τύπο felt252, ο οποίος είναι ουσιαστικό μέρος του προγραμματισμού σε Cairo.
Ο τύπος felt252 στο Cairo είναι ένας βαθμωτός τύπος που χρησιμοποιείται για την αναπαράσταση ακεραίων από το 0 έως και το $P - 1$, όπου $P$ είναι ένας μεγάλος πρώτος αριθμός που αυτή τη στιγμή έχει οριστεί σε $( 2^{251} + 17 \cdot 2^{192} + 1 )$.
Αυτός ο τύπος εξασφαλίζει ότι όλες οι αριθμητικές πράξεις εκτελούνται modulo $P$, γεγονός που τον κάνει διαφορετικό από τους τυπικούς τύπους ακεραίων που μπορεί να συναντήσεις σε άλλες γλώσσες προγραμματισμού.
Το Cairo παρέχει υποστήριξη για βασικές αριθμητικές πράξεις σε τιμές felt252:
-
Πρόσθεση (
+): Προσθέτει δύο τιμές felt252.
Αν το αποτέλεσμα υπερβαίνει το $P$, ανάγεται modulo $P$.
-
Αφαίρεση (
-): Αφαιρεί μία τιμή felt252 από μία άλλη.
Αν το αποτέλεσμα είναι αρνητικό, προσαρμόζεται ώστε να παραμείνει εντός του εύρους προσθέτοντας ένα πολλαπλάσιο του $P$.
-
Πολλαπλασιασμός (
*): Πολλαπλασιάζει δύο τιμές felt252, με το αποτέλεσμα να υπολογίζεται modulo $P$.
-
Διαίρεση (
/): Διαιρεί μία τιμή felt252 με μία άλλη, εξασφαλίζοντας ότι το αποτέλεσμα ικανοποιεί την εξίσωση $( \frac{x}{y} \cdot y = x \mod P)$.
Οδηγίες
Σε αυτή την άσκηση, θα βοηθήσεις έναν κρυπτογράφο να διαχειρίζεται και να επαληθεύει ένα ασφαλές σύστημα επικοινωνίας.
Το σύστημα βασίζεται σε μεγάλο βαθμό σε στοιχεία σώματος, συγκεκριμένα στον τύπο felt252 της Cairo, ώστε να διασφαλίζεται ότι όλες οι αριθμητικές πράξεις παραμένουν μέσα σε ένα καθορισμένο εύρος.
1. Υπολόγισε το άθροισμα δύο μηνυμάτων
Δύο κρυπτογραφημένα μηνύματα, το καθένα από τα οποία παριστάνεται ως felt252, πρέπει να προστεθούν μεταξύ τους για να δημιουργηθεί ένα ενιαίο μήνυμα.
Ωστόσο, λόγω της κρυπτογράφησης, κάθε αποτέλεσμα που ξεπερνά τη μέγιστη τιμή $P - 1$ πρέπει να αναδιπλώνεται χρησιμοποιώντας το modulo $P$.
Υλοποίησε μια συνάρτηση που δέχεται δύο τιμές felt252 και επιστρέφει το άθροισμά τους, διασφαλίζοντας ότι το αποτέλεσμα παραμένει μέσα στο έγκυρο εύρος:
add_messages(3618502788666131213697322783095070105623107215331596699973092056135007822949, 987654321)
// => 123456789
Σημείωση: Η τιμή επιστροφής πρέπει να είναι felt252.
2. Υπολόγισε τη διαφορά δύο μηνυμάτων
Μερικές φορές, τα μηνύματα πρέπει να αφαιρεθούν για να ανακτηθούν τα αρχικά δεδομένα.
Αν το αποτέλεσμα της αφαίρεσης είναι αρνητικό, το σύστημα προσαρμόζει αυτόματα το αποτέλεσμα προσθέτοντας $P$, ώστε να το επαναφέρει μέσα στο εύρος μιας έγκυρης τιμής felt252.
Υλοποίησε μια συνάρτηση που δέχεται δύο τιμές felt252 και επιστρέφει τη διαφορά τους, διασφαλίζοντας ότι το αποτέλεσμα παραμένει μέσα στο έγκυρο εύρος:
subtract_messages(123456789, 987654321)
// => 3618502788666131213697322783095070105623107215331596699973092056135007822949
Σημείωση: Η τιμή επιστροφής πρέπει να είναι felt252.
3. Υπολόγισε ένα έγκυρο γινόμενο δύο μηνυμάτων
Για να διασφαλίζεται η ακεραιότητα των κρυπτογραφημένων δεδομένων, το κρυπτογραφικό σύστημα συχνά πολλαπλασιάζει δύο μηνύματα (felt252) για να βεβαιωθεί ότι το γινόμενό τους παραμένει μέσα σε ένα έγκυρο εύρος.
Το αποτέλεσμα πρέπει να υπολογίζεται με modulo $P$, ώστε να παραμένει μέσα στο έγκυρο εύρος.
Υλοποίησε μια συνάρτηση που δέχεται δύο τιμές felt252 και επιστρέφει το γινόμενό τους, διασφαλίζοντας ότι το αποτέλεσμα παραμένει μέσα στο έγκυρο εύρος:
multiply_messages(382927772233671078546147897004315551461400594453673204174697055647611, 9449570)
// => 123456789
Σημείωση: Η τιμή επιστροφής πρέπει να είναι felt252.
Άσκηση εκμάθησης
