Οδηγίες
Δημιούργησε μια υλοποίηση του affine cipher, ενός αρχαίου συστήματος κρυπτογράφησης που δημιουργήθηκε στη Μέση Ανατολή.
Ο affine cipher είναι ένα είδος μονοαλφαβητικού κρυπτοσυστήματος αντικατάστασης.
Κάθε χαρακτήρας αντιστοιχίζεται στο αριθμητικό του ισοδύναμο, κρυπτογραφείται με μια μαθηματική συνάρτηση και έπειτα μετατρέπεται στο γράμμα που αντιστοιχεί στη νέα αριθμητική του τιμή.
Αν και όλα τα μονοαλφαβητικά κρυπτοσυστήματα είναι αδύναμα, ο affine cipher είναι πολύ πιο ισχυρός από τον Atbash cipher, επειδή έχει πολύ περισσότερα κλειδιά.
Κρυπτογράφηση
Η συνάρτηση κρυπτογράφησης είναι:
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 είναι το πολλαπλασιαστικό αντίστροφο modulo (MMI) του a mod m
- το πολλαπλασιαστικό αντίστροφο modulo υπάρχει μόνο αν τα
a και m είναι πρώτα μεταξύ τους.
Το MMI του a είναι το x για το οποίο το υπόλοιπο της διαίρεσης του ax με το m είναι 1:
ax mod m = 1
Περισσότερες πληροφορίες για το πώς βρίσκουμε ένα πολλαπλασιαστικό αντίστροφο modulo και τι σημαίνει υπάρχουν στο σχετικό άρθρο της 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 δεν είναι πρώτα μεταξύ τους
Παράδειγμα εύρεσης πολλαπλασιαστικού αντιστρόφου modulo (MMI)
Εύρεση του MMI για a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, δηλαδή 105 mod 26 = 1
- Το
7 είναι το MMI του 15 mod 26
