Ο Αλγόριθμος RSA (rsa - 50 Μονάδες)
Κάθε φορά που συνδεόμαστε σε μια υπηρεσία (ssh, webmail, instagram) τα bytes του κωδικού μας ταξιδεύουν στο δίκτυο, και η κρυπτογραφία φροντίζει να μην μπορεί να τα διαβάσει οποιοσδήποτε. Σε αυτήν την άσκηση, θα ασχοληθούμε με έναν από τους πιο φημισμένους αλγορίθμους κρυπτογραφίας, τον αλγόριθμο RSA (Rivest-Shamir-Adleman, 1977). Χρειαζόμαστε: (1) μια συνάρτηση encrypt που να “κρύβει” το μήνυμά μας ώστε να μην μπορεί κάποιος άλλος να το διαβάσει καθώς το στέλνουμε και (2) μια συνάρτηση decrypt η οποία να παίρνει το κρυπτογραφημένο μήνυμά μας και να το μετατρέπει (αποκρυπτογραφεί) στο αρχικό.
Πως όμως μπορούμε να “κρύψουμε” το μήνυμά μας; Η βασική ιδέα του RSA είναι η εξής: έστω ότι το μήνυμα που θέλουμε να στείλουμε είναι ένας ακέραιος \(m\). Τότε για να κρύψουμε το μήνυμά μας αρκεί να το υψώσουμε σε μια μεγάλη δύναμη: \(m^x\). Η αποκρυπτογράφηση μπορεί να γίνει εξίσου απλά, αρκεί να βρούμε έναν αριθμό \(y\) έτσι ώστε \(\left(m^x\right)^y = m\). Βλέποντας αυτό το παράδειγμα, ίσως σκέφτεστε ότι \(x = 2\) και \(y = \frac{1}{2}\) είναι μια πιθανή λύση στο πρόβλημά μας. Η σκέψη σας είναι σωστή, αλλά επειδή οποιοσδήποτε μπορεί να υπολογίσει την τετραγωνική ρίζα ενός αριθμού δεν μπορούμε να χρησιμοποιήσουμε αυτές τις πράξεις και αριθμούς για ασφαλή κρυπτογράφηση. Για να δούμε ποιους αριθμούς και πράξεις μπορούμε να χρησιμοποιήσουμε, χρειαζόμαστε πρώτα κάποιους ορισμούς:
Ορισμός 3. Ένας φυσικός αριθμός p μεγαλύτερος του 1 ονομάζεται πρώτος (prime) όταν έχει σαν μόνους διαιρέτες (το υπόλοιπο της διαίρεσης είναι 0) το 1 και το p. Για παράδειγμα, το 17 είναι πρώτος αριθμός, ενώ το 42 δεν είναι, αφού έχει σαν διαιρέτες το 2, το 3 και το 7, εκτός από τους 1 και 42. Μπορείτε να επιβεβαιώσετε ότι οι πρώτοι αριθμοί που είναι μικρότεροι από το 100 είναι οι εξής:
\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\]Μαθηματικοί στο παρελθόν έχουν ασχοληθεί με πολλά γνωστά προβλήματα όπως η κατανομή τους. Μέχρι σήμερα, δεν έχει βρεθεί μια συνάρτηση που να παράγει τους πρώτους αριθμούς αποδοτικά.
Ορισμός 4. Δύο ακέραιοι \(a\) και \(b\) είναι πρώτοι μεταξύ τους ή σχετικά πρώτοι (coprime) όταν ο μέγιστος κοινός διαιρέτης τους είναι το 1, δηλαδή \(\text{gcd}(a, b) = 1\). Για παράδειγμα, οι αριθμοί 8 και 9 είναι coprime εφόσον το \(\text{gcd}(8, 9) = 1\) παρόλο που κανείς από τους δυο τους δεν είναι ο ίδιος πρώτος.
Ορισμός 5. Η συνάρτηση \(\phi : \mathbb{N} \rightarrow \mathbb{N}\) του Euler (γνωστή και ως totient function) δέχεται έναν φυσικό αριθμό n και επιστρέφει το πλήθος των φυσικών αριθμών που είναι μικρότεροι του n και comprime με το n. Για παράδειγμα, \(\phi(9) = 6\), εφόσον υπάρχουν ακριβώς έξι coprime με το 9: 1, 2, 4, 5, 7 και 8. Η συνάρτηση \(\phi\) έχει την πολλαπλασιαστική ιδιότητα, δηλαδή για κάθε δύο φυσικούς \(a\), \(b\) με \(\text{gcd}(a, b) = 1\) ισχύει ότι \(\phi(a\cdot b) = \phi(a)\cdot \phi(b)\). Επίσης, αν ο αριθμός \(a\) είναι πρώτος, τότε ισχύει πως \(\phi(a) = a - 1\). Για παράδειγμα: \(\phi(5) = 4\), εφόσον οι αριθμοί 1, 2, 3, 4 είναι coprime ως προς το 5.
Έχοντας τους παραπάνω ορισμούς, μπορούμε επιτέλους να ορίσουμε τους περιορισμούς για να λειτουργήσει σωστά ο αλγόριθμος RSA:
Με βάση τους παραπάνω περιορισμούς, μπορούμε πλέον να ορίσουμε την συνάρτηση κρυπτογράφησης encrypt ως:
\[encrypt(m) = m^e \bmod N\]Αντίστοιχα αν μας δώσουν έναν ακέραιο \(c\) (\(=m^e \bmod N\)) που είναι το κρυπτογραφημένο μήνυμα, μπορούμε να το αποκρυπτογραφήσουμε, χρησιμοποιώντας την συνάρτηση decrypt:
\[decrypt(c) = c^d \bmod N\]Το γιατί η παραπάνω πράξη μας δίνει το αρχικό μας μηνύμα είναι μεγάλη ιστορία (\(c^d \bmod N = \left(m^e\right)^d\bmod N = m^{e\cdot d}\bmod N = m^{1 + k\phi(N)} \bmod N = m \bmod N\)) αλλά μπορείτε να βρείτε όλα τα βήματα της απόδειξης στην Wikipedia.
Φτάσαμε επιτέλους στο ζητούμενο αυτής της άσκησης: να γράψετε ένα πρόγραμμα το οποίο να μπορεί να κρυπτογραφεί και να αποκρυπτογραφεί μηνύματα χρησιμοποιώντας τον παραπάνω αλγόριθμο RSA.
./rsa op e d p q. Tο πρώτο op επιτρέπεται να είναι “enc” (για encryption) και
“dec” για decryption. Τα υπόλοιπα ορίσματα θα είναι ακέραιοι αριθμοί και θα είναι
στο εύρος \([-10^{18}, 10^{18}]\). Αν το πρόγραμμα εκτελεστεί με ορίσματα που δεν
ακολουθούν τις παραπάνω προδιαγραφές, πρέπει να εκτυπώσει αντίστοιχο μήνυμα όπως στα
παρακάτω παραδείγματα και να επιστρέφει με κωδικό εξόδου (exit code) 1.gcc -O3 -Wall -Wextra -Werror -pedantic -o rsa rsa.cΠαρακάτω παραθέτουμε αλληλεπιδράσεις με μια ενδεικτική λύση. Ας δοκιμάσουμε να στείλουμε το μήνυμα “42” (\(m = 42\)) χρησιμοποιώντας το μυστικό “257 257 173 193” (\(e = 257\), \(d = 257\), \(p = 173\), \(q = 193\)):
$ echo 42 | ./rsa enc 257 257 173 193
6990
$ echo $?
0
Άρα το κρυπτογραφημένο μήνυμα που μπορούμε να στείλουμε είναι ο αριθμός \(c = 6990\). Είναι σωστός; Πρέπει να κάνουμε την πράξη \(42^{257}\bmod (173 \cdot 193)\) το οποίο όντως αν χρησιμοποιήσουμε ένα online calculator φαίνεται σωστό (αντίστοιχα μπορείτε να κάνετε πειράματα με τους δικούς σας συνδυασμούς αριθμών). Για να δούμε αν μπορούμε να αποκρυπτογραφήσουμε το αρχικό μας μήνυμα:
$ echo 6990 | ./rsa dec 257 257 173 193
42
$ echo $?
0
Πήραμε όντως πίσω το αρχικό μας μήνυμα! Παρακάτω δοκιμάζουμε να κρυπτογραφήσουμε και να αποκρυπτογραφήσουμε διάφορους συνδυασμούς που καλύπτουν τις προδιαγραφές παραπάνω:
$ ./rsa
Usage: ./rsa enc|dec <exp_exp> <priv_exp> <prime1> <prime2>
$ echo $?
1
$ ./rsa pop 1 2 3 4
First argument must be 'enc' or 'dec'
$ echo $?
1
$ ./rsa enc 1 2 -3 4
Negative numbers are not allowed
$ echo $?
1
$ ./rsa enc 1 2 3 4
p and q must be prime
$ echo $?
1
$ ./rsa enc 3 6 17 19
e is not coprime with phi(N)
$ echo $?
1
$ ./rsa enc 5 6 17 19
e * d mod phi(N) is not 1
$ echo $?
1
$ echo 500 | ./rsa enc 5 173 17 19
Message is larger than N
$ echo $?
1
$ echo -42 | ./rsa enc 5 173 17 19
Negative numbers are not allowed
$ echo $?
1
$ echo 42 | ./rsa enc 5 173 17 19
264
$ echo 42 | ./rsa enc 17 26153 131 229
27187
$ echo 27187 | ./rsa dec 257 257 173 193
5343
$ echo 27187 | ./rsa dec 17 26153 131 229
42
$ echo 117 | ./rsa enc 17 26153 131 229 | ./rsa dec 17 26153 131 229
117
$ echo 43434343 | ./rsa enc 65537 2278459553 62971 38609 |
./rsa dec 65537 2278459553 62971 38609
43434343
$ echo 42 | ./rsa enc 65537 2278459553 62971 38609 > enc_msg
$ cat enc_msg
741088023
$ time ./rsa dec 65537 2278459553 62971 38609 < enc_msg
42
real 0m0.011s
user 0m0.004s
sys 0m0.008s
Καθώς οι εκθέτες του μυστικού στον οποίο υψώνουμε το μήνυμα γίνονται μεγαλύτεροι, είναι πιθανό πως το πρόγραμμά σας θα αρχίσει να παίρνει όλο και περισσότερο χρόνο για να τερματίσει. Αν παρατηρήσετε πως κάτι τέτοιο συμβαίνει και στον δικό σας αλγόριθμο, μπορείτε να δοκιμάσετε βελτιωμένους αλγόριθμους υπολογισμού της δύναμης ενός ακεραίου (Repeated Squaring, Modular Exponentiation).
Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης.
Μην υπολογίσετε ποτέ ολόκληρο το \(m^e\): παίρνετε το υπόλοιπο mod \(N\) μετά από κάθε πολλαπλασιασμό και, για μεγάλους εκθέτες, χρησιμοποιείτε ύψωση σε δύναμη με επαναλαμβανόμενο τετραγωνισμό (λογαριθμικά βήματα). Προσοχή στην υπερχείλιση: το γινόμενο δύο υπολοίπων κοντά στο \(N\) μπορεί να μη χωρά σε 64 bits. Κάντε τους ελέγχους με τη σειρά που δείχνουν τα παραδείγματα (ορίσματα, αρνητικοί, πρώτοι, coprime, αντίστροφοι, μέγεθος μηνύματος) και επαναχρησιμοποιήστε τον ΜΚΔ της άσκησης gcd.
Αριθμός στον οδηγό: Α11.21
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: hw-2024-hw1-rsa ·
Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2024-hw1-rsa.html ·
Markdown (GitHub)