Κρυπτογραφία — Εξεταστική Ιουνίου 2023¶
C71ADC4E-7BC0-43D5-9E5B-11C8ED6EC597.jpg¶
Κρυπτογραφία Εξεταστική Ιουνίου 2023
Θέμα 1) (50%) a. (10%) Ποιο είναι το αποτέλεσμα της ύψωσης \(2^{2343875656} \pmod{13}\); b. (20%) Αν γνωρίζουμε την κρυπτογράφηση RSA των μηνυμάτων \(m, m+1, m+2\) όταν το \(e=3\), πως μπορούμε να βρούμε το \(m\) σε πολυωνυμικό χρόνο; c. (20%) Έστω το παρακάτω πρωτόκολλο απόδειξης μηδενικής γνώσης που λειτουργεί πάνω σε μια κυκλική ομάδα \(G = \langle g \rangle\) τάξης \(q\). Η Α διαλέγει μυστικό \(w\) τέτοιο ώστε \(h=g^w\) για κάποιο \(h\) στο \(\langle g \rangle\). Το πρωτόκολλο αποτελείται από τα εξής βήματα: 1. Η Α διαλέγει \(t\) και στέλνει στον Β το \(y = g^t\) 2. Ο Β διαλέγει μια πρόκληση \(c\) και την στέλνει στην Α 3. Η Α υπολογίζει το \(s \equiv t + wc \pmod q\) και στέλνει το \(s\) στον Β. Επαλήθευση: Ο Β δέχεται ότι η Α ξέρει το \(w\) αν ισχύει \(g^s = y h^c\) Δείξτε ότι το πρωτόκολλο λειτουργεί σωστά και ότι ο Β μπορεί να εμπιστευθεί την Α.
Θέμα 2) (50%) Στο πρωτόκολλο ElGamal, η Αλίκη έχει επιλέξει \(p = 13\), \(a = 2\), \(b = 6\) και \(k=7\) a. (10%) Υπολογίστε το δημόσιο και ιδιωτικό κλειδί της Αλίκης. b. (20%) Η Αλίκη υπογράφει το μήνυμα \(m\). Το μήνυμα είναι το εξής: \(m = \{759\}\) και έστω ότι η Αλίκη χρησιμοποιεί την σύνοψη \(h(m) = m \bmod 54\). Υπολογίστε αναλυτικά την υπογραφή που θα σας στείλει η Αλίκη για το μήνυμα \(m\). c. (20%) Επαληθεύστε αν η υπογραφή που λάβατε από την Αλίκη είναι έγκυρη. Να δειχθεί αναλυτικά η διαδικασία επαλήθευσης της υπογραφής.
Σημειώσεις: 1) Δεν επιτρέπεται η χρήση αριθμομηχανής, υπολογιστή και χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν ρητά με το χέρι και να παρουσιάζονται στο γραπτό. 2) Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος. 3) Για πρακτικούς λογούς, η εκφώνηση χρησιμοποιεί πολύ μικρούς ακεραίους αριθμούς. Η απάντηση σας θα πρέπει να βασίζεται σε αλγόριθμους πολυωνυμικού χρόνου.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
a. Αφού \(2^{12}\equiv 1 \pmod{13}\) (Fermat), αρκεί ο εκθέτης modulo \(12\): [ 2343875656 \equiv 4 \pmod{12}. ] Άρα [ 2^{2343875656}\equiv 2^4=16\equiv 3 \pmod{13}. ] Το αποτέλεσμα είναι \(\boxed{3}\).
b. Έστω [ c_0\equiv m^3 \pmod N,\quad c_1\equiv (m+1)^3 \pmod N,\quad c_2\equiv (m+2)^3 \pmod N. ] Τότε [ c_0-2c_1+c_2 \equiv m^3-2(m+1)^3+(m+2)^3 \equiv 6(m+1)\pmod N. ] Επειδή για RSA με \(e=3\) συνήθως \(\gcd(6,N)=1\), υπολογίζουμε το \(6^{-1}\pmod N\) με Ευκλείδειο αλγόριθμο και [ m\equiv \bigl(c_0-2c_1+c_2\bigr)6^{-1}-1 \pmod N. ] Άρα το \(m\) βρίσκεται σε πολυωνυμικό χρόνο. Αν \(\gcd(6,N)>1\), το gcd δίνει παραγοντοποίηση ή αντιμετωπίζεται με CRT, πάλι σε πολυωνυμικό χρόνο.
c. - Ορθότητα (πληρότητα): Αν η Α γνωρίζει \(w\) και ακολουθήσει το πρωτόκολλο, τότε [ g^s=g^{t+wc}=g^t(g^w)^c=yh^c, ] άρα ο Β δέχεται.
-
Soundness / απόδειξη γνώσης: Αν η Α μπορούσε να απαντήσει σωστά σε δύο διαφορετικές προκλήσεις \(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}=g^{w(c_1-c_2)}. ] Επειδή \(g\) έχει τάξη \(q\), [ w\equiv (s_1-s_2)(c_1-c_2)^{-1}\pmod q. ] Άρα από δύο έγκυρες απαντήσεις εξάγεται το μυστικό \(w\). Χωρίς γνώση του \(w\), η πιθανότητα επιτυχίας για μία τυχαία πρόκληση είναι το πολύ \(1/q\)· με επανάληψη γίνεται αμελητέα.
-
Μηδενική γνώση: Ένας προσομοιωτής χωρίς το \(w\) μπορεί να διαλέξει τυχαία \(c,s\) και να θέσει [ y=g^s h^{-c}. ] Τότε ισχύει \(g^s=yh^c\), και η κατανομή \((y,c,s)\) είναι ίδια με την πραγματική, αφού στο πραγματικό πρωτόκολλο το \(t\) είναι ομοιόμορφο τυχαίο. Άρα δεν αποκαλύπτεται πληροφορία για το \(w\).
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ερμηνεύω με τη συνήθη σύμβαση ElGamal υπογραφής: \(a=2\) είναι ο γεννήτορας, \(b=6\) το ιδιωτικό κλειδί και \(k=7\) ο τυχαίος εκθέτης υπογραφής.
a. Το ιδιωτικό κλειδί είναι [ b=6. ] Το δημόσιο κλειδί είναι [ y=a^b \bmod p=2^6\bmod 13=64\bmod 13=12. ] Άρα [ \boxed{\text{ιδιωτικό κλειδί } b=6,\qquad \text{δημόσιο κλειδί } (p,a,y)=(13,2,12).} ]
b. Η σύνοψη είναι [ h(m)=759\bmod 54=3, ] αφού \(54\cdot 14=756\) και \(759-756=3\).
Υπολογίζουμε [ r=a^k\bmod p=2^7\bmod 13. ] Είναι \(2^6=64\equiv 12\pmod{13}\), άρα [ r=2^7\equiv 12\cdot 2=24\equiv 11\pmod{13}. ] Χρειάζεται [ s\equiv (h(m)-b r)k^{-1}\pmod{p-1}, ] δηλαδή modulo \(12\). Είναι [ b r=6\cdot 11=66\equiv 6\pmod{12}, ] άρα [ h(m)-br=3-6=-3\equiv 9\pmod{12}. ] Επίσης [ 7^{-1}\equiv 7\pmod{12}, ] διότι \(7\cdot 7=49\equiv 1\pmod{12}\). Άρα [ s\equiv 9\cdot 7=63\equiv 3\pmod{12}. ] Η υπογραφή είναι [ \boxed{(r,s)=(11,3).} ]
c. Για επαλήθευση ελέγχουμε αν [ y^r r^s\equiv a^{h(m)}\pmod p. ] Έχουμε \(y=12\), \(r=11\), \(s=3\), \(h(m)=3\): [ y^r=12^{11}\equiv (-1)^{11}\equiv 12\pmod{13}. ] Επίσης [ r^s=11^3\pmod{13}. ] Είναι \(11^2=121\equiv 4\pmod{13}\), άρα [ 11^3\equiv 4\cdot 11=44\equiv 5\pmod{13}. ] Άρα [ y^r r^s\equiv 12\cdot 5=60\equiv 8\pmod{13}. ] Από την άλλη, [ a^{h(m)}=2^3=8\pmod{13}. ] Επειδή [ y^r r^s\equiv 8\equiv a^{h(m)}\pmod{13}, ] η υπογραφή είναι έγκυρη.