Κρυπτογραφία — Εξεταστική Ιουνίου 2025¶
IMG_4256.jpg¶
Κρυπτογραφία¶
Εξεταστική Ιουνίου 2025
| Ονοματεπώνυμο: | |
|---|---|
| ΑΜ (7ψήφιος): | |
| Έτος: |
Θέμα 1) (50%)¶
a. (10%) Ποιο είναι το αποτέλεσμα της ύψωσης \(3^{887654321} \bmod 13\);
b. (20%) Δείξτε ότι \(\gcd(2^s-1, 2^t-1) = 1\) αν και μόνο αν \(\gcd(s,t) = 1\).
c. (20%) Έστω \(n=pq\), όπου \(p, q\) περιττοί πρώτοι αριθμοί, διαφορετικοί μεταξύ τους. Έστω ότι \(\lambda(n) = \frac{(p-1)(q-1)}{\gcd(p-1, q-1)}\). Υποθέτουμε πως τροποποιούμε το πρωτόκολλο RSA έτσι ώστε το ιδιωτικό κλειδί \(d\) να υπολογίζεται από την \(ed \equiv 1 \bmod \lambda(n)\). Έστω \(\lambda\)-RSA το όνομα του τροποποιημένου πρωτοκόλλου. Οι συναρτήσεις (από)κρυπτογράφησης του \(\lambda\)-RSA είναι όμοιες με του RSA. Δείξτε ότι το τροποποιημένο πρωτόκολλο \(\lambda\)-RSA λειτουργεί ορθά.
Θέμα 2) (50%)¶
Στο πρωτόκολλο RSA, η Αλίκη έχει επιλέξει \(p = 7\), \(q = 19\) και \(e_A = 23\).
a. (10%) Υπολογίστε το ιδιωτικό κλειδί της Αλίκης.
b. (20%) Εσείς επιλέγετε να της στείλετε κρυπτογραφημένο το μήνυμα \(m = \{94, 45\}\). Υπολογίστε αναλυτικά το κρυπτοκείμενο \(c\) που θα στείλετε στην Αλίκη.
c. (20%) Έστω ότι θέλετε να στείλετε κρυπτογραφημένο το μήνυμα \(m'\) στην Αλίκη. Η Αλίκη λαμβάνει το κρυπτοκείμενο \(c' = \{58, 95\}\) από εσάς. Υπολογίστε αναλυτικά το αρχικό σας μήνυμα \(m'\).
Σημειώσεις:¶
1) Δεν επιτρέπεται η χρήση αριθμομηχανής, υπολογιστή και χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν αποκλειστικά με το χέρι και να παρουσιάζονται στο γραπτό. 2) Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος. 3) Για πρακτικούς λογούς, η εκφώνηση χρησιμοποιεί πολύ μικρούς ακεραίους αριθμούς. Η απάντησή σας θα πρέπει να βασίζεται σε αλγορίθμους πολυωνυμικού χρόνου.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2025-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
a. Επειδή \(\gcd(3,13)=1\) και \(\varphi(13)=12\), από το μικρό θεώρημα Fermat έχουμε \(3^{12}\equiv 1\pmod{13}\). Υπολογίζουμε [ 887654321\equiv 5\pmod{12}, ] άρα [ 3^{887654321}\equiv 3^5=243\equiv 243-18\cdot 13=9\pmod{13}. ] Επομένως το αποτέλεσμα είναι \(9\).
b. Θα δείξουμε την ταυτότητα [ \gcd(2^s-1,2^t-1)=2^{\gcd(s,t)}-1. ] Έστω \(s=qt+r\) με \(0\le r<t\). Αφού \(2^t\equiv 1\pmod{2^t-1}\), έχουμε [ 2^s-1=2^{qt+r}-1\equiv 2^r-1\pmod{2^t-1}. ] Άρα [ \gcd(2^s-1,2^t-1)=\gcd(2^t-1,2^r-1). ] Επαναλαμβάνοντας το ίδιο βήμα σύμφωνα με τον Ευκλείδειο αλγόριθμο στους εκθέτες \(s,t\), καταλήγουμε στο [ \gcd(2^s-1,2^t-1)=2^{\gcd(s,t)}-1. ] Συνεπώς [ \gcd(2^s-1,2^t-1)=1 \iff 2^{\gcd(s,t)}-1=1 \iff 2^{\gcd(s,t)}=2 \iff \gcd(s,t)=1. ]
c. Έστω \(n=pq\) με \(p\ne q\) περιττούς πρώτους και [ \lambda(n)=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}=\operatorname{lcm}(p-1,q-1). ] Υποθέτουμε ότι \(\gcd(e,\lambda(n))=1\) και ότι το ιδιωτικό κλειδί \(d\) ικανοποιεί [ ed\equiv 1\pmod{\lambda(n)}. ] Τότε υπάρχει ακέραιος \(k\) ώστε [ ed=1+k\lambda(n). ] Για οποιοδήποτε μήνυμα \(m\) με \(0\le m<n\), η κρυπτογράφηση είναι \(c\equiv m^e\pmod n\) και η αποκρυπτογράφηση δίνει [ c^d\equiv (m^e)^d=m^{ed}\pmod n. ] Αρκεί να δείξουμε ότι \(m^{ed}\equiv m\pmod n\). Επειδή \(n=pq\) και \(\gcd(p,q)=1\), ελέγχουμε modulo \(p\) και modulo \(q\).
Για το modulo \(p\): αν \(p\nmid m\), από Fermat ισχύει \(m^{p-1}\equiv 1\pmod p\). Επειδή \(p-1\mid \lambda(n)\) και \(ed-1=k\lambda(n)\), έπεται ότι \(ed-1\) είναι πολλαπλάσιο του \(p-1\), άρα [ m^{ed}=m\cdot m^{ed-1}\equiv m\pmod p. ] Αν \(p\mid m\), τότε και τα δύο μέλη είναι \(0\pmod p\). Άρα \(m^{ed}\equiv m\pmod p\).
Ομοίως, επειδή \(q-1\mid \lambda(n)\), προκύπτει \(m^{ed}\equiv m\pmod q\). Από το Κινεζικό Θεώρημα Υπολοίπων, [ m^{ed}\equiv m\pmod{pq}, ] δηλαδή \(m^{ed}\equiv m\pmod n\). Άρα η αποκρυπτογράφηση επιστρέφει σωστά το αρχικό μήνυμα και το \(\lambda\)-RSA λειτουργεί ορθά.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Δίνονται \(p=7\), \(q=19\), άρα [ n=pq=7\cdot 19=133,\qquad \varphi(n)=(7-1)(19-1)=6\cdot 18=108. ]
a. Πρέπει \(e_A d_A\equiv 1\pmod{\varphi(n)}\), δηλαδή [ 23d_A\equiv 1\pmod{108}. ] Εφαρμόζουμε τον Ευκλείδειο αλγόριθμο: [ 108=4\cdot 23+16, ] [ 23=1\cdot 16+7, ] [ 16=2\cdot 7+2, ] [ 7=3\cdot 2+1. ] Αντιστρέφοντας: [ 1=7-3\cdot 2 =7-3(16-2\cdot 7) =7\cdot 7-3\cdot 16 ] [ =(23-16)\cdot 7-3\cdot 16 =7\cdot 23-10\cdot 16 ] [ =7\cdot 23-10(108-4\cdot 23) =47\cdot 23-10\cdot 108. ] Άρα [ 23\cdot 47\equiv 1\pmod{108}, ] οπότε το ιδιωτικό κλειδί είναι [ (d_A,n)=(47,133). ]
b. Για κάθε τμήμα του μηνύματος υπολογίζουμε \(c\equiv m^{23}\pmod{133}\). Χρησιμοποιούμε το Κινεζικό Θεώρημα Υπολοίπων modulo \(7\) και \(19\).
Για \(m_1=94\): [ 94\equiv 3\pmod 7,\qquad 94\equiv -1\equiv 18\pmod{19}. ] Άρα [ c_1\equiv 3^{23}\pmod 7. ] Επειδή \(23\equiv 5\pmod 6\), [ c_1\equiv 3^5=243\equiv 5\pmod 7. ] Επίσης, [ c_1\equiv (-1)^{23}\equiv -1\equiv 18\pmod{19}. ] Λύνουμε \(c_1\equiv 5\pmod 7\), \(c_1\equiv 18\pmod{19}\). Γράφουμε \(c_1=5+7k\). Τότε [ 5+7k\equiv 18\pmod{19} \implies 7k\equiv 13\pmod{19}. ] Επειδή \(7^{-1}\equiv 11\pmod{19}\), [ k\equiv 13\cdot 11=143\equiv 10\pmod{19}. ] Άρα \(c_1=5+7\cdot 10=75\).
Για \(m_2=45\): [ 45\equiv 3\pmod 7,\qquad 45\equiv 7\pmod{19}. ] Άρα [ c_2\equiv 3^{23}\equiv 5\pmod 7. ] Για το modulo \(19\), αφού \(23\equiv 5\pmod{18}\), [ c_2\equiv 7^5\pmod{19}. ] Υπολογίζουμε: [ 7^2=49\equiv 11\pmod{19}, ] [ 7^4\equiv 11^2=121\equiv 7\pmod{19}, ] [ 7^5\equiv 7\cdot 7=49\equiv 11\pmod{19}. ] Άρα \(c_2\equiv 5\pmod 7\) και \(c_2\equiv 11\pmod{19}\). Γράφουμε \(c_2=5+7k\). Τότε [ 5+7k\equiv 11\pmod{19} \implies 7k\equiv 6\pmod{19}, ] [ k\equiv 6\cdot 11=66\equiv 9\pmod{19}. ] Άρα \(c_2=5+7\cdot 9=68\).
Επομένως το κρυπτοκείμενο είναι [ c={75,68}. ]
c. Δίνεται \(c'=\{58,95\}\). Αποκρυπτογραφούμε με \(d=47\), δηλαδή υπολογίζουμε \(m\equiv c^{47}\pmod{133}\).
Για \(c_1'=58\): [ 58\equiv 2\pmod 7,\qquad 58\equiv 1\pmod{19}. ] Επειδή \(47\equiv 5\pmod 6\), [ m_1'\equiv 2^{47}\equiv 2^5=32\equiv 4\pmod 7. ] Επίσης, [ m_1'\equiv 1^{47}\equiv 1\pmod{19}. ] Λύνουμε \(m_1'\equiv 4\pmod 7\), \(m_1'\equiv 1\pmod{19}\). Γράφουμε \(m_1'=4+7k\). Τότε [ 4+7k\equiv 1\pmod{19} \implies 7k\equiv -3\equiv 16\pmod{19}. ] Άρα [ k\equiv 16\cdot 11=176\equiv 5\pmod{19}, ] οπότε \(m_1'=4+7\cdot 5=39\).
Για \(c_2'=95\): [ 95\equiv 4\pmod 7,\qquad 95\equiv 0\pmod{19}. ] Επειδή \(47\equiv 5\pmod 6\), [ m_2'\equiv 4^{47}\equiv 4^5\pmod 7. ] Έχουμε \(4^2\equiv 2\pmod 7\), άρα \(4^4\equiv 4\pmod 7\) και [ 4^5\equiv 4\cdot 4=16\equiv 2\pmod 7. ] Επίσης, [ m_2'\equiv 0^{47}\equiv 0\pmod{19}. ] Λύνουμε \(m_2'\equiv 2\pmod 7\), \(m_2'\equiv 0\pmod{19}\). Γράφουμε \(m_2'=19k\). Τότε [ 19k\equiv 2\pmod 7 \implies 5k\equiv 2\pmod 7. ] Επειδή \(5^{-1}\equiv 3\pmod 7\), [ k\equiv 6\pmod 7. ] Άρα \(m_2'=19\cdot 6=114\).
Επομένως το αρχικό μήνυμα είναι [ m'={39,114}. ]