Κρυπτογραφία — Εξεταστική Ιουνίου 2022¶
IMG_20220826_190039.jpg¶
Κρυπτογραφία Εξεταστική Ιουνίου 2022
Θέμα 1) (50%) a) (20%) Ποιο είναι το αποτέλεσμα της ύψωσης \(2^{2343875656} \pmod{13}\); b) (10%) Είναι το πρωτόκολλο ElGamal malleable και γιατί; c) (20%) Έστω το παρακάτω πρωτόκολλο απόδειξης μηδενικής γνώσης που λειτουργεί πάνω σε μια κυκλική ομάδα \(G = \langle g \rangle\) τάξης \(q\). Η Α διαλέγει μυστικό \(w\) τέτοιο ώστε \(h=g^w\) για κάποιο \(h\) στο \(\langle g \rangle\). Το πρωτόκολλο αποτελείται από τα εξής βήματα: a. Η Α διαλέγει \(t\) και στέλνει στον Β το \(y = g^t\) b. Ο Β διαλέγει μια πρόκληση \(c\) και την στέλνει στην Α c. Η Α υπολογίζει το \(s \equiv t + wc \pmod q\) και στέλνει το \(s\) στον Β. Επαλήθευση: Ο Β δέχεται ότι η Α ξέρει το \(w\) αν ισχύει \(g^s = y h^c\) Δείξτε ότι το πρωτόκολλο λειτουργεί σωστά και ότι ο Β μπορεί να εμπιστευθεί την Α.
Θέμα 2) (50%) Στο πρωτόκολλο ElGamal, η Αλίκη έχει επιλέξει \(p = 11\), \(a = 2\) και \(b = [(\text{AM} \bmod 10) \bmod 8] + 2\). Επίσης επιλέγει το \(k\) ως εξής: \(k=3\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 0. \(k=7\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 1, \(k=9\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 2, \(k=3\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 3, \(k=7\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 4, \(k=9\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 5, \(k=3\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 6, \(k=7\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 7, \(k=9\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 8, \(k=9\) όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 9. a. (10%) Υπολογίστε το δημόσιο και ιδιωτικό κλειδί της Αλίκης. b. (20%) Η Αλίκη υπογράφει το μήνυμα \(m\). Έστω ότι το ΑΜ σας αποτελείται από τα ψηφία \(a_1 a_2 a_3 a_4 a_5 a_6 a_7\). Το μήνυμα είναι το εξής: \(m = \{a_4 a_3 a_6\}\) και έστω ότι η Αλίκη χρησιμοποιεί την σύνοψη \(h(m) = m \bmod a_3 a_7\). Υπολογίστε αναλυτικά την υπογραφή που θα σας στείλει η Αλίκη για το μήνυμα \(m\). c. (20%) Επαληθεύστε αν η υπογραφή που λάβατε από την Αλίκη είναι έγκυρη. Να δειχθεί αναλυτικά η διαδικασία επαλήθευσης της υπογραφής.
Σημειώσεις: 1) Δεν επιτρέπεται η χρήση αριθμομηχανής, υπολογιστή και χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν ρητά με το χέρι και να παρουσιάζονται στο γραπτό. 2) Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος. 3) Θα χρησιμοποιήσετε τα νέα 7ψήφια ΑΜ σας. 4) Για πρακτικούς λογούς, η εκφώνηση χρησιμοποιεί πολύ μικρούς ακεραίους αριθμούς. Η απάντηση σας θα πρέπει να βασίζεται σε αλγόριθμους πολυωνυμικού χρόνου.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2022-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
a) Αφού \(\gcd(2,13)=1\) και \(\varphi(13)=12\), ισχύει \(2^{12}\equiv 1\pmod{13}\). Υπολογίζω τον εκθέτη modulo \(12\): [ 2343875656=12\cdot 195322971+4 \quad\Rightarrow\quad 2343875656\equiv 4\pmod{12}. ] Άρα [ 2^{2343875656}\equiv 2^4=16\equiv 3\pmod{13}. ] Το αποτέλεσμα είναι \(\boxed{3}\).
b) Ναι, το κρυπτοσύστημα ElGamal είναι malleable. Αν έχουμε κρυπτογράφημα [ (c_1,c_2)=(g^k,\, m h^k), ] όπου \(h=g^x\) είναι το δημόσιο κλειδί, τότε για οποιοδήποτε γνωστό \(\Delta\) μπορούμε να σχηματίσουμε το έγκυρο κρυπτογράφημα [ (c_1,\, c_2 g^\Delta). ] Κατά την αποκρυπτογράφηση παίρνουμε [ \frac{c_2 g^\Delta}{c_1^x} = \frac{m h^k g^\Delta}{g^{kx}} = m g^\Delta, ] δηλαδή το αρχικό μήνυμα πολλαπλασιασμένο με γνωστό παράγοντα, χωρίς να είναι γνωστό το μυστικό κλειδί. Άρα ένας αντίπαλος μπορεί να αλλοιώσει το κρυπτογράφημα ώστε το αποκρυπτογραφημένο μήνυμα να αλλάξει με προβλέψιμο τρόπο.
c) Έστω \(h=g^w\).
Πληρότητα: Αν η Α ακολουθεί το πρωτόκολλο, τότε [ g^s=g^{t+wc}=g^t(g^w)^c=yh^c, ] άρα ο Β δέχεται πάντα. Άρα το πρωτόκολλο λειτουργεί σωστά.
Εγκυρότητα/γνώση του \(w\): Έστω ότι η Α μπορεί να απαντήσει σε δύο διαφορετικές προκλήσεις \(c_1\neq c_2\) για το ίδιο \(y\), δίνοντας \(s_1,s_2\) τέτοια ώστε [ g^{s_1}=yh^{c_1},\qquad g^{s_2}=yh^{c_2}. ] Διαιρώντας κατά μέλη, [ g^{s_1-s_2}=h^{c_1-c_2}. ] Αν το \(c_1-c_2\) είναι αντιστρέψιμο modulo \(q\) (π.χ. \(q\) πρώτος και \(c_1\not\equiv c_2\pmod q\)), τότε [ h=g^{(s_1-s_2)(c_1-c_2)^{-1}\bmod q}, ] οπότε εξάγεται το μυστικό \(w=(s_1-s_2)(c_1-c_2)^{-1}\bmod q\). Επομένως, όποιος δεν γνωρίζει το \(w\) μπορεί να απαντήσει σωστά το πολύ σε μία πρόκληση για δεδομένο \(y\). Αν ο Β επιλέγει τυχαία \(c\) από σύνολο μεγέθους \(q\), η πιθανότητα επιτυχίας ενός απατεώνα είναι το πολύ \(1/q\), άρα για μεγάλο \(q\) είναι αμελητέα και ο Β μπορεί να εμπιστευτεί την Α.
Επιπλέον, το πρωτόκολλο είναι μηδενικής γνώσης: ένας προσομοιωτής μπορεί να επιλέξει τυχαία \(c,s\) και να θέσει \(y=g^s h^{-c}\)· τότε το \((y,c,s)\) ικανοποιεί την επαλήθευση \(g^s=yh^c\) και έχει ίδια κατανομή με πραγματική συνομιλία, άρα δεν αποκαλύπτεται πληροφορία για το \(w\).
Θέμα 2¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: λείπει ο αριθμός μητρώου (ΑΜ), από τον οποίο ορίζονται το \(b\), το \(k\), το μήνυμα \(m\) και η σύνοψη \(h(m)\)· επομένως τα ζητούμενα δημόσιο/ιδιωτικό κλειδί και η υπογραφή δεν έχουν μοναδική αριθμητική απάντηση.