Το επόμενο βήμα είναι να γενικευτεί το τετραγωνικό υπόλοιπο στην εξίσωση με τη γενική μορφή ax ≡ y mod p. Η εξίσωση αυτή είναι εκθετικής μορφής και κλασικά λύνεται λογαριθμίζοντας. Εδώ όμως υπάρχουν μόνο φυσικοί αριθμοί και επομένως οι λογάριθμοι είναι διακριτοί.
Η επίλυση αυτών των εξισώσεων είναι εξαιρετικά δύσκολη. Μπορεί να αντιμετωπιστεί με την τακτική της αναζήτησης.
Η αναζήτηση του διακριτού λογαρίθμου αν γίνει με τη μέθοδο της εξαντλητικής αναζήτησης ax ≡y mod p στην περίπτωση του μεγάλου p είναι εξαιρετικά χρονοβόρα.
Για παράδειγμα το x που ικανοποιεί τη σχέση 2x= 1194 mod 2357 είναι 951. Πόσο δύσκολο είναι να υπολογιστεί; Δοκιμάστε το !!
Έχοντας τη γνώση αυτή ο αποδέκτης μηνύματος, μπορεί να γνωστοποιεί την τριάδα (2,1194,2357) και να κρατά ως δική του μυστική πληροφορία το 951. Ο αποστολέας μηνύματος γνωρίζοντας την τριάδα του αποδέκτη κρυπτογραφεί το μήνυμά του με βάση αυτή και το αποστέλλει στον παραλήπτη. Αυτός επειδή γνωρίζει τη λύση (951) μπορεί εύκολα να αποκρυπτογραφήσει το μήνυμα που παρέλαβε. Οποιοσδήποτε τρίτος θα χρειαζόταν πολύ χρόνο να το αποκρυπτογραφήσει.
Διακριτός λογάριθμος 2/2
Πιο κάτω δίνεται η περίπτωση της εξαντλητικής αναζήτησης για την επίλυση της εξίσωσης
Αν για παράδειγμα πρέπει να επιλυθεί η 2x = 12 mod 29 απαιτούνται 7 βήματα ενώ για την 2x = 15 mod 29 χρειάζονται 27 βήματα. Η πολυπλοκότητα της μεθόδου είναι Ο(p), δηλαδή για πολύ μεγάλους αριθμούς p καταλήγει να είναι χρονοβόρα. Δοκιμάστε την 5x= 3 mod 2017.
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
Η επίλυση αυτών των εξισώσεων είναι εξαιρετικά δύσκολη. Μπορεί να αντιμετωπιστεί με την τακτική της αναζήτησης.
Η αναζήτηση του διακριτού λογαρίθμου αν γίνει με τη μέθοδο της εξαντλητικής αναζήτησης ax ≡y mod p στην περίπτωση του μεγάλου p είναι εξαιρετικά χρονοβόρα.
Για παράδειγμα το x που ικανοποιεί τη σχέση 2x= 1194 mod 2357 είναι 951. Πόσο δύσκολο είναι να υπολογιστεί; Δοκιμάστε το !!
Έχοντας τη γνώση αυτή ο αποδέκτης μηνύματος, μπορεί να γνωστοποιεί την τριάδα (2,1194,2357) και να κρατά ως δική του μυστική πληροφορία το 951. Ο αποστολέας μηνύματος γνωρίζοντας την τριάδα του αποδέκτη κρυπτογραφεί το μήνυμά του με βάση αυτή και το αποστέλλει στον παραλήπτη. Αυτός επειδή γνωρίζει τη λύση (951) μπορεί εύκολα να αποκρυπτογραφήσει το μήνυμα που παρέλαβε. Οποιοσδήποτε τρίτος θα χρειαζόταν πολύ χρόνο να το αποκρυπτογραφήσει.
Διακριτός λογάριθμος 2/2
Πιο κάτω δίνεται η περίπτωση της εξαντλητικής αναζήτησης για την επίλυση της εξίσωσης
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 8:01 π.μ.