RSA
Αντί να υπογραφεί το μήνυμα ως έχει, προτιμάται η χρήση μιας συνάρτησης κατακερματοποίησης (hash function) Η: Ο παραλήπτης προβαίνει στη ίδια μέθοδο, αρκεί να γνωρίζει και ποία συνάρτηση κατακερματοποίησης χρησιμοποιήθηκε. Αν και ο αλγόριθμος θεωρείται ασφαλής, η κακή του χρήση μπορεί να οδηγήσει σε μεγάλες αδυναμίες ασφάλειας. Αν υποθέσουμε πως έχουμε στην κατοχή μας δυο κλειδιά του τύπου και (το ίδιο n), και δυο κρυπτογραφήσεις του ιδίου μηνύματος m με τα κλειδιά αυτά (π.χ. Αν ένας κακόβουλος χρήστης έχει ένα κρυπτογραφημένο μύνημα c με τελικό παραλήπτη τον Γιάννη, μπορεί να περδέψει τον τελευταίο έτσι ώστε να του το αποκρυπτογραφήσει ο ίδιος ο Γιάννης.Ο RSA είναι ένας κρυπταλγόριθμος ασύμμετρου κλειδιού, το όνομα του οποίου προέρχεται από τους δημιουργούς του, Ron Rivest, Adi Shamir and Len Adleman. Ο Γιάννης υπολογίζει: Το μήνυμα r.m δεν είναι κατανοητό, οπότε ο Γιάννης δεν μπορεί εύκολα να καταλάβει πως πέφτει θύμα απάτης και το στέλνει στον κακόβουλο χρήστη, ο οποίος υπολογίζει τον αριθμό r-1 mod n και μπορεί πλέον να διαβάσει το μήνυμα m. Για να αποφύγει το πρόβλημα αυτό, ο Γιάννης δεν πρέπει να χρησιμοποιεί το ίδιο κλειδί για την υπογραφή και για την αποκρυπτογράφηση μηνυμάτων, ούτε όμως και να υπογράφει ό,τι του ζητούν στα τυφλά . .
Αν θέλουμε να αποστείλουμε ένα υπογεγραμμένο μήνυμα, μπορούμε να το κάνουμε με τον εξής τρόπο (χρησιμοποιώντας το κρυφό κλειδί (n, d): Ο παραλήπτης του μηνύματος m και της υπογραφής s, υπολογίζει την τιμή se χάρη στο δημόσιο κλειδί (n, e) και την συγρίνει με το m. Αρκεί να διαλέξει έναν τυχαίο αριθμό r, πρώτο με το n και να ζητήσει από τον Γιάννη να του υπογράψει το μήνυμα m´ = re.c.
Ο κακόβουλος χρήστης έχει λοιπόν στην κατοχή του: Χάρη στο Κινέζικο Θεώρημα Υπολοίπων, μπορεί να υπολογίσει: και να βρει πια εύκολα το αρχικό μήνυμα m. Υποθέτουμε πως ο Γιάννης, το κρυφό (αντ. Το κρυπτογραφημένο μήνυμα υπολογίζεται με τον εξής τρόπο: Αφού ληφθεί ένα κρυπτογραφημένο μήνυμα , για να διαβάσουμε το αρχικό μήνυμα προβαίνουμε στον ακόλουθο υπολογισμό: Ξέρουμε πως e.d ≡ 1 (mod p-1) και e.d ≡ 1 (mod q-1), όποτε με το μικρό θεώρημα του Φερμά, έχουμε: και Οι αριθμοί p και q είναι πρώτοι μεταξύ τους, χρησιμοιποιώντας λοιπόν το Κινέζικο Θεώρημα Υπολοίπων, έχουμε: Ο RSA επιτρέπει την ψηφιακή υπογραφή μηνυμάτων.
Eίναι πολύ πιθανόν να έχουμε: οπότε και με το θεώρημα του Bézout: Για να βρούμε το αρχικό μήνυμα m, υπολογίζουμε λοιπόν: Ένα μήνυμα m κρυπτογραφείται κι αποστέλλεται από τρεις διαφορετικούς χρήστες με χρήση των δημοσίων κλειδιών , και . δημόσιο) κλειδί του οποίου είναι (n, d) (αντ.
Αυτή η λύση, αν και λειτουργεί, δεν χρησιμοιποιείται ποτέ, για λόγους ασφαλείας. RSA → 0x525341, όπου 0x52 είναι ο δεκαεξαδικός κωδικός ASCII του χαρακτήρα R, 0x53 του S και τέλος 0x41 του A).
Χρησιμοποιούνται δυο κλειδιά, ένα δημόσιο κατά την διάρκεια της κρυπτογράφησης και ένα κρυφό για την αποκρυπτογράφηση. Τα κλειδιά είναι τα εξής: Μπορούμε τώρα να δημοσιεύσουμε το πρώτο κλειδί, δίνοντας έτσι την δυνατότητα σε οποιονδήποτε να μας στείλει κρυπτογραφημένα μηνύματα που μόνο εμείς (χάρη στο κρυφό κλειδί) μπορούμε να αποκρυπτογραφήσουμε. Το μήνυμα μπορεί να αντιπροσωπευθεί από έναν αριθμό (π.χ. (n, e)), υπογράφει ότι μήνυμα του δώσουμε χωρίς δεύτερη σκέψη.
αν κρυφακούμε σε ένα δίκτυο): και μπορούμε να βρούμε το αρχικό μήνυμα m χωρίς να έχουμε πρόσβαση στα κρυφά κλειδιά. Επιτρέπει όχι μόνο την κωδικοποίηση μηνυμάτων αλλά μπορεί επίσης να χρησιμοποιηθεί και ως ψηφιακή υπογραφή. Ο RSA βασίζεται στην δυσκολία παραγοντοποίησης μεγάλων αριθμών (σήμερα, συνήθως της τάξης των 1024 με 2048 μπιτς).
