Κρυπτογραφία — Εξεταστική Ιουνίου 2020¶
2-3-4.pdf¶
Κρυπτογραφία¶
Εξεταστική Ιουνίου 2020
Ερώτημα 2) (10%) Ποιο είναι το αποτέλεσμα της ύψωσης 22343875656 mod13;
Ερώτημα 3) (5%) Είναι το πρωτόκολλο ElGamal malleable και γιατί;
Ερώτημα 4) (5%) Δώστε παράδειγμα hash συνάρτησης που να παράγει σύνοψη μεγέθους το πολύ 3 bits.
Διάρκεια 20 λεπτά¶
Δεν επιτρέπεται η χρήση αριθμομηχανης, υπολογιστή, χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν με το χέρι. Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος.
5.pdf¶
Κρυπτογραφία¶
Εξεταστική Ιουνίου 2020
Ερώτημα 5) (70%) Διάρκεια 40 λεπτά
Στο πρωτόκολλο Merkle-Hellman, η Αλίκη εχει επιλέξει b = (1, 4, 9, 18, 36, 71), w και N=293 ως το ιδιωτικό της κλειδί. To w=20+x , όπου x είναι το τελευταίο ψηφίο του ΑΜ (αριθμού μητρώου) σας.
a. (10%) Υπολογίστε το δημόσιο κλειδί της Αλίκης.
b. (20%) Εσείς επιλέγετε να της στείλετε κρυπτογραφημένο μήνυμα m . Το m αποτελείται από τα 12 τελευταία bits του ΑΜ σας. (Όσοι έχετε 7ψήφιο ΑΜ πάρτε τα 4 τελευταία ψηφία του ΑΜ σας.) Yπολογίστε αναλυτικά το κρυπτοκείμενο c που θα στείλετε στην Αλίκη. c. (40%) Δείξτε αναλυτικά πως η Αλίκη αποκρυπτογραφεί το κρυπτοκείμενο c που της στείλατε και ανακτά το αρχικό σας μήνυμα m .
Δεν επιτρέπεται η χρήση αριθμομηχανης, υπολογιστή, χειρόγραφων σημειώσεων. Όλες οι πράξεις πρέπει να γίνουν με το χέρι. Επιτρέπονται μόνο ανοιχτά βιβλία και οι διαφάνειες του μαθήματος.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):../other/unknown_6.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Αφού \(2^{12}\equiv 1 \pmod{13}\) (Fermat), αρκεί ο εκθέτης mod \(12\): [ 2343875656 \equiv 4 \pmod{12}. ] Άρα [ 2^{2343875656}\equiv 2^4=16\equiv 3 \pmod{13}. ] Αποτέλεσμα: \(\boxed{3}\).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ναι, το κλασικό ElGamal είναι malleable. Αν [ E(m;r)=(g^r,\; m h^r), ] τότε για δύο κρυπτοκείμενα πολλαπλασιάζοντας τις συνιστώσες έχουμε [ (g^{r_1},m_1h^{r_1})(g^{r_2},m_2h^{r_2}) =(g^{r_1+r_2},\; m_1m_2h^{r_1+r_2}), ] που είναι έγκυρο κρυπτοκείμενο του \(m_1m_2\). Επίσης, από ένα κρυπτοκείμενο \((c_1,c_2)\) μπορεί να παραχθεί \((c_1, t c_2)\), που αποκρυπτογραφείται σε \(t m\). Άρα είναι πολλαπλασιαστικά malleable και όχι CCA-secure χωρίς πρόσθετη προστασία ακεραιότητας.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Παράδειγμα: πάρτε τις 3 τελευταίες μονάδες bit του SHA-256, δηλαδή ορίστε [ H(m)=\operatorname{SHA256}(m) \bmod 8 \in {0,1,\dots,7}. ] Η έξοδος έχει μέγεθος \(3\) bits. (Προφανώς λόγω μόλις 3 bits υπάρχουν πολλές συγκρούσεις· δεν είναι ασφαλής κρυπτογραφική σύνοψη.)
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Έστω \(x\) το τελευταίο ψηφίο του ΑΜ, άρα [ w=20+x,\qquad x\in{0,1,\dots,9}. ] Το ιδιωτικό κλειδί είναι [ b=(1,4,9,18,36,71),\quad N=293. ] Επειδή \(71>1+4+9+18+36=68\), και ομοίως σε κάθε βήμα, το \(b\) είναι υπεραυξητικό, οπότε το άθροισμα υποσυνόλου λύνεται άπληστα.
a. Το δημόσιο κλειδί είναι [ a_i\equiv w b_i \pmod{293},\qquad i=1,\dots,6. ] Δηλαδή \(a=w(1,4,9,18,36,71)\bmod 293\). Για κάθε δυνατό \(x\):
b. Έστω \(m=(m_1,\dots,m_6)\in\{0,1\}^6\) ένα τμήμα 6 bits του μηνύματος. Το κρυπτοκείμενο αυτού του τμήματος είναι [ c=\sum_{i=1}^{6} m_i a_i ] (ως ακέραιος· ισοδύναμα για την αποκρυπτογράφηση μπορεί να κρατηθεί \(c\bmod 293\)). Για μήνυμα 12 bits, το χωρίζουμε σε δύο τμήματα 6 bits, \(m^{(1)},m^{(2)}\), και στέλνουμε [ c^{(j)}=\sum_{i=1}^{6} m_i^{(j)} a_i,\qquad j=1,2. ] Ισοδύναμα, πριν την αναγωγή mod \(293\), [ c^{(j)}=w\sum_{i=1}^{6} m_i^{(j)} b_i. ] Αντικαθιστούμε το \(w=20+x\) και τα bits του ΑΜ για να προκύψουν τα αριθμητικά \(c^{(1)},c^{(2)}\).
c. Η Αλίκη υπολογίζει πρώτα [ c'^{(j)}\equiv w^{-1}c^{(j)}\pmod{293}. ] Χρειάζονται τα αντίστροφα: [ \begin{array}{c|c|c} x&w&w^{-1}\bmod 293\ \hline 0&20&44\ 1&21&14\ 2&22&40\ 3&23&51\ 4&24&232\equiv -61\ 5&25&211\equiv -82\ 6&26&124\ 7&27&76\ 8&28&157\equiv -136\ 9&29&192\equiv -101 \end{array} ] Επειδή [ c'^{(j)}\equiv w^{-1}\sum_i m_i^{(j)}(w b_i)\equiv \sum_i m_i^{(j)}b_i\pmod{293}, ] και επειδή \(\sum_i b_i=139<293\), το \(c'^{(j)}\) ισούται ακριβώς με το άθροισμα υποσυνόλου. Έπειτα η Αλίκη λύνει άπληστα από το μεγαλύτερο προς το μικρότερο: [ 71,\;36,\;18,\;9,\;4,\;1. ] Για κάθε βάρος \(b_i\): αν το τρέχον υπόλοιπο είναι \(\ge b_i\), θέτει \(m_i^{(j)}=1\) και αφαιρεί \(b_i\), αλλιώς θέτει \(m_i^{(j)}=0\). Με τον τρόπο αυτό ανακτά το 6-bit τμήμα \(m^{(j)}\). Επαναλαμβάνει για τα δύο τμήματα των 12 bits και τα συνενώνει, ανακτώντας το αρχικό \(m\).