Κρυπτογραφία — Εξεταστική Σεπτεμβρίου 2020¶
2.pdf¶
Κρυπτογραφία¶
Εξεταστική Σεπτεμβρίου 2020
Θέμα 2) (60%) Διάρκεια 75 λεπτά Στο πρωτόκολλο RSA, η Αλίκη έχει επιλέξει p = 11 και q = 13 . Επίσης επιλέγει το eA ως εξής:
eA=7 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 1, eA=11 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 2, eA=13 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 3, eA=17 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 4, eA=19 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 5, eA=23 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 6, eA=29 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 7, eA=31 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 8, eA=37 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 9, eA=41 όταν το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας είναι 0.
a. (10%) Υπολογίστε το ιδιωτικό κλειδί της Αλίκης.
b. (20%) Εσείς επιλέγετε να της στείλετε κρυπτογραφημένο μήνυμα m . Έστω ότι το ΑΜ σας αποτελείται από τα ψηφία α1α2α3α4α5α6α7. Το μήνυμα είναι το εξής: m ={α3α7, α5α6}. Yπολογίστε αναλυτικά το κρυπτοκείμενο c που θα στείλετε στην Αλίκη.
c. (30%) Έστω ότι η Αλίκη λαμβάνει το κρυπτοκείμενο c΄ = {α3α6, α6α5} από εσάς. Υπολογίστε αναλυτικά το αρχικό σας μήνυμα m’ .
Σημειώσεις:
-
1) Δεν επιτρέπεται η χρήση αριθμομηχανής, υπολογιστή και χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν ρητά με το χέρι και να παρουσιάζονται στο γραπτό.
-
2) Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος.
-
3) Θα χρησιμοποιήσετε τα νέα 7ψήφια ΑΜ σας.
-
4) Για πρακτικούς λογούς, η εκφώνηση χρησιμοποιεί πολύ μικρούς ακεραίους αριθμούς. Η απάντηση σας θα πρέπει να βασίζεται σε αλγόριθμους πολυωνυμικού χρόνου.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):../other/2.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Το ΑΜ δεν δίνεται, οπότε δεν προκύπτει μοναδικό αριθμητικό αποτέλεσμα. Δίνω την πλήρη λύση συναρτήσει των ψηφίων \(\alpha_1,\ldots,\alpha_7\) του ΑΜ· για αριθμητικό αποτέλεσμα αντικαθιστούμε τα ψηφία.
α. Είναι [ n=pq=11\cdot 13=143,\qquad \varphi(n)=(11-1)(13-1)=10\cdot12=120. ] Το ιδιωτικό κλειδί είναι \((n,d)=(143,d)\), όπου [ d\equiv e_A^{-1}\pmod{120},\qquad 1\le d<120. ] Ανάλογα με το τελευταίο ψηφίο \(\alpha_7\) του ΑΜ: [ \begin{array}{c|c|c} \alpha_7 & e_A & d=e_A^{-1}\bmod 120\\hline 0&41&41\ 1&7&103\ 2&11&11\ 3&13&37\ 4&17&113\ 5&19&19\ 6&23&47\ 7&29&29\ 8&31&31\ 9&37&13 \end{array} ] Π.χ. για \(\alpha_7=1\), \(7\cdot103=721=6\cdot120+1\), άρα \(d=103\).
β. Ερμηνεύουμε το \(\alpha_i\alpha_j\) ως διψήφιο δεκαδικό αριθμό, δηλαδή \(\alpha_i\alpha_j=10\alpha_i+\alpha_j\). Θέτουμε [ B_1=10\alpha_3+\alpha_7,\qquad B_2=10\alpha_5+\alpha_6. ] Με δημόσιο εκθέτη \(e_A=e_A(\alpha_7)\), το κρυπτοκείμενο είναι [ c={c_1,c_2}, ] όπου [ c_1\equiv B_1^{e_A}\pmod{143},\qquad c_2\equiv B_2^{e_A}\pmod{143}, ] με \(0\le c_1,c_2<143\). Για χειροκίνητο υπολογισμό μπορούμε να χρησιμοποιήσουμε CRT: [ r_{11}\equiv B^{e_A}\pmod{11},\qquad r_{13}\equiv B^{e_A}\pmod{13}, ] και [ c\equiv r_{11}+11k\pmod{143},\quad k\equiv 6(r_{13}-r_{11})\pmod{13}. ]
γ. Εδώ [ C_1=10\alpha_3+\alpha_6,\qquad C_2=10\alpha_6+\alpha_5. ] Η αποκρυπτογράφηση γίνεται με το \(d\) της Αλίκης από τον πίνακα του (α), βάσει του \(\alpha_7\): [ m'_1\equiv C_1^{d}\pmod{143},\qquad m'_2\equiv C_2^{d}\pmod{143}. ] Άρα [ m'={m'_1,m'_2}, ] όπου \(0\le m'_1,m'_2<143\). Ισοδύναμα, για κάθε συνιστώσα \(C\) υπολογίζουμε [ C^d\bmod 11,\qquad C^d\bmod 13 ] και συνδυάζουμε με τον ίδιο τύπο CRT. Αν το αποτέλεσμα ερμηνευτεί ως διψήφιο block, γράφεται με δύο δεκαδικά ψηφία και τυχόν αρχικό μηδέν διατηρείται· αν βγει τιμή \(\ge100\), τότε το δοσμένο \(c'\) δεν αντιστοιχεί σε διψήφιο block υπό αυτήν την κωδικοποίηση.