Public key cryptography - σπιτική συνταγή

Παίρνουμε δύο πρώτους αριθμούς p και q.

έστω p = 3, q = 11

Βρίσκουμε το γινόμενο τους n = p*q .

n = 33

Βρίσκουμε κάτι που ονομάζεται totient function και είναι ίσο με φ(n) = (p-1)*(q-1).

φ(33) = 20

Βρίσκουμε αριθμό e που δεν έχει κοινό διαιρέτη με το φ(n) - εκτός φυσικά του 1.

π.χ. e = 7, αφού το 7 δεν έχει κοινούς διαιρέτες με το 20.

Βρίσκουμε αριθμό d ώστε να μας δίνει (d*e) mod φ(n) = 1.

με λίγο ψάξιμο βρίσκουμε d = 3, διότι
3*7 = 21 και
21 mod 20 = 1

Αυτή την στιγμή, μπορούμε να χρησιμοποιήσουμε το ζεύγος (e, n) για κρυπτογράφηση και το (d, n) για αποκρυπτογράφηση. Κλειδιά κρυπτογράφησης σα να λέμε... ;)

Κρυπτογράφηση μηνύματος m:

c = m^e mod n

Για m = 5:

c = 5^7 mod 33 = 14

Αποκρυπτογράφηση κωδικοποιημένου μηνύματος c:

m = c^d mod n

m = 14^3 mod 33 = 5

Απλό; Συγχαρητήρια, μόλις υλοποιήσατε τον αλγόριθμο RSA. 

Ανάλογα με την χρήση που θέλετε να κάνετε, το public key είναι το (e, n) ή το (d, n), ενώ φυσικά αυτό που θα μείνει είναι το private key. Η μαγκιά του αλγόριθμου βασίζεται ότι, έχοντας διαλέξει πρώτους αριθμούς p και q μεγέθους γύρω στα 256bits, είναι ΠΟΛΥ δύσκολο να πάρεις το public key και να κάτσεις να κάνεις ανάποδα την διαδικασία ώστε να βρεις τα p και q και στην συνέχεια το private key.

Οι έχοντες απορίες, μπορούν να ψάξουν σε σχετική βιβλιογραφία. Η περιγραφή που ανέφερα βασίζεται στα γραφόμενα του  "Network Security - Private Communications in a Public World" (Kaufman/Perlman/Speciner).

ΥΓ: Άτιμη Perlman, μας έχεις φάει το συκώτι...