Οδηγίες
Δημιούργησε μια υλοποίηση του αφινικού κρυπτογράφου, ενός αρχαίου συστήματος κρυπτογράφησης που δημιουργήθηκε στη Μέση Ανατολή.
Ο αφινικός κρυπτογράφος είναι ένα είδος μονοαλφαβητικού κρυπτογράφου αντικατάστασης.
Κάθε χαρακτήρας αντιστοιχίζεται στο αριθμητικό του ισοδύναμο, κρυπτογραφείται με μια μαθηματική συνάρτηση και έπειτα μετατρέπεται στο γράμμα που αντιστοιχεί στη νέα αριθμητική του τιμή.
Αν και όλοι οι μονοαλφαβητικοί κρυπτογράφοι είναι αδύναμοι, ο αφινικός κρυπτογράφος είναι πολύ ισχυρότερος από τον κρυπτογράφο Atbash, επειδή έχει πολλά περισσότερα κλειδιά.
Κρυπτογράφηση
Η συνάρτηση κρυπτογράφησης είναι:
E(x) = (ai + b) mod m
Όπου:
- Το
i είναι η θέση του γράμματος από το 0 έως το μήκος του αλφαβήτου μείον 1.
- Το
m είναι το μήκος του αλφαβήτου.
Για το ρωμαϊκό αλφάβητο, το m είναι 26.
- Τα
a και b είναι ακέραιοι που αποτελούν το κλειδί κρυπτογράφησης.
Οι τιμές a και m πρέπει να είναι πρώτες μεταξύ τους (ή, σχετικά πρώτες) για να πετύχει η αυτόματη αποκρυπτογράφηση, δηλαδή έχουν τον αριθμό 1 ως μοναδικό κοινό παράγοντα (περισσότερες πληροφορίες μπορείς να βρεις στο άρθρο της Wikipedia για τους πρώτους μεταξύ τους ακέραιους).
Σε περίπτωση που τα a και m δεν είναι πρώτα μεταξύ τους, το πρόγραμμά σου θα πρέπει να δείξει ότι αυτό είναι σφάλμα.
Διαφορετικά, θα πρέπει να κρυπτογραφεί ή να αποκρυπτογραφεί με το κλειδί που δίνεται.
Για τις ανάγκες αυτής της άσκησης, τα ψηφία είναι έγκυρα ως είσοδος, αλλά δεν κρυπτογραφούνται.
Τα κενά και τα σημεία στίξης εξαιρούνται.
Το κρυπτογραφημένο κείμενο γράφεται σε ομάδες σταθερού μήκους που χωρίζονται με κενό, με το παραδοσιακό μέγεθος ομάδας να είναι 5 γράμματα.
Αυτό γίνεται για να είναι πιο δύσκολο να μαντέψει κανείς το κρυπτογραφημένο κείμενο με βάση τα όρια των λέξεων.
Αποκρυπτογράφηση
Η συνάρτηση αποκρυπτογράφησης είναι:
D(y) = (a^-1)(y - b) mod m
Όπου:
- Το
y είναι η αριθμητική τιμή ενός κρυπτογραφημένου γράμματος, δηλαδή y = E(x)
- είναι σημαντικό να σημειωθεί ότι το
a^-1 είναι ο πολλαπλασιαστικός αντίστροφος (MMI) του a mod m
- ο πολλαπλασιαστικός αντίστροφος υπάρχει μόνο αν τα
a και m είναι πρώτα μεταξύ τους.
Το MMI του a είναι το x για το οποίο το υπόλοιπο της διαίρεσης του ax με το m είναι 1:
ax mod m = 1
Περισσότερες πληροφορίες για το πώς βρίσκουμε έναν πολλαπλασιαστικό αντίστροφο και τι σημαίνει μπορείς να βρεις στο σχετικό άρθρο της Wikipedia.
Γενικά παραδείγματα
- Η κρυπτογράφηση του
"test" δίνει "ybty" με το κλειδί a = 5, b = 7
- Η αποκρυπτογράφηση του
"ybty" δίνει "test" με το κλειδί a = 5, b = 7
- Η αποκρυπτογράφηση του
"ybty" δίνει "lqul" με το λάθος κλειδί a = 11, b = 7
- Η αποκρυπτογράφηση του
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" δίνει "thequickbrownfoxjumpsoverthelazydog" με το κλειδί a = 19, b = 13
- Η κρυπτογράφηση του
"test" με το κλειδί a = 18, b = 13 είναι σφάλμα, επειδή τα 18 και 26 δεν είναι πρώτα μεταξύ τους
Παράδειγμα εύρεσης πολλαπλασιαστικού αντιστρόφου (MMI)
Εύρεση του MMI για a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, δηλαδή 105 mod 26 = 1
- Το
7 είναι το MMI του 15 mod 26
