Aλγόριθμος RSA

Ένας αλγοριθμος κρυπτογράφησης που χρησιμοποιείται στο ssh είναι ο rsa. Γι'αυτό θα προσπαθήσω να εξηγήσω πως λειτουργεί αυτός ο αλγόριθμος. Καταρχήν ας δούμε πως λειτουργεί η δημιουργία κλειδιού (η εντολή είναι ssh-keygen)

Αρχικά χρειαζόμαστε δύο μεγάλους πρώτους αριθμούς. Πρώτοι δηλαδή να διαιρούνται μόνο με τον εαυτό τους και τη μονάδα. Μεγάλοι για να είναι πιο δύσκολη η αποκρυπτογράφηση. Στο παράδειγμα όμως θα περιοριστούμε με μικρούς για να διευκολύνουμε τις πράξεις. Ας υποθέσουμε ότι έχουμε τους αριθμούς p = 19 και q = 7. Και οι δύο διαιρούνται μόνο με τον εαυτό τους και το 1.

Έπειτα υπολογίζουμε το γινόμενό τους n = p q = 19 * 7 = 133, o οποίος φυσικά δεν είναι πρώτος γιατί είναι το γινόμενο δύο άλλων αριθμών.

Το τρίτο βήμα είναι να υπολογίσουμε το γινόμενο φ(n) = (p-1)(q-1) = (19-1)*(7-1) = 18 * 6 = 108.

Μετά πρέπει να επιλέξουμε έναν αριθμό e, τέτοιο ώστε να είναι μεγαλύτερος του 1 και μικρότερος του φ(n) =108. Δηλαδή 1 < e < φ(n). Επιπλέον δεν πρέπει να έχει κοινά πολλαπλάσια με τον φ(n), δηλαδή με το 108. Γι'αυτό πρέπει να αναλύσουμε τον 108 στα πολλαπλάσιά του, 108 = 2 * 2 *3 * 3* 3. Άρα ο e δε μπορεί να είναι 2, 3, 4, 6, 12, 18, 27, 36, 54, 108 (ελπίζω να βρήκα όλους τους συνδυασμούς, αν κάνω λάθος διορθώστε με). Ας διαλέξουμε το 5 για να είμαστε σίγουροι. Το ε = 5 είναι το δημόσιο κλειδί (public key) που αποθηκεύεται ώς ~/.ssh/id_rsa.pub.

Tέλος, ψάχνουμε για έναν αριθμό d, τέτοιος ώστε αν πολλαπλασιάσουμε το d με το e και μετά διαιρέσουμε με το φ(n) το υπόλοιπο της διαίρεσης να είναι 1. Ένας τέτοιος αριθμός είναι το 65, γιατί 65*5=325 = 1 + 3*108 που αφήνει υπόλοιπο 1. Ο αριθμός d = 65 είναι το ιδιωτικό κλειδί (private key) που αποθηκεύεται ως ~/.ssh/id_rsa.