🔐 Κρυπτογράφηση RSA
Ο αλγόριθμος RSA περιγράφηκε το 1977 από τους Ron Rivest, Adi Shamir και Len Adleman στο MIT (το όνομά του προκύπτει από τα αρχικά τους). Χρησιμοποιεί δύο κλειδιά: ένα δημόσιο, που μοιράζεται ελεύθερα, και ένα ιδιωτικό, που παραμένει μυστικό.
Κατασκευάζουμε \(N=p\cdot q\), γινόμενο δύο μεγάλων πρώτων, και \(\varphi(N)=(p-1)(q-1)\). Επιλέγουμε \(e\) με \(\gcd(e,\varphi(N))=1\), και υπολογίζουμε το αντίστροφό του \(d\), τέτοιο ώστε \(e\cdot d\equiv1\pmod{\varphi(N)}\). Το δημόσιο κλειδί είναι \((e,N)\), το ιδιωτικό \((d,N)\):
Επαληθεύσαμε με πλήρες αριθμητικό παράδειγμα: για \(p=61\), \(q=53\) (\(N=3233\), \(\varphi(N)=3120\)), \(e=17\), βρίσκουμε \(d=2753\). Το μήνυμα \(M=65\) κρυπτογραφείται σε \(C=2790\), και αποκρυπτογραφείται σωστά πίσω σε \(65\). Η ασφάλεια του RSA στηρίζεται στη δυσκολία παραγοντοποίησης του \(N\) στους πρώτους παράγοντές του.
🔑 Κρυπτογράφηση ElGamal
Ο αλγόριθμος ElGamal, βασισμένος στην ανταλλαγή κλειδιών Diffie-Hellman, περιγράφηκε το 1984 από τον Taher Elgamal, και χρησιμοποιείται σήμερα στο GNU Privacy Guard (GPG) και σε εκδόσεις του PGP. Ο παραλήπτης επιλέγει έναν μεγάλο πρώτο \(p\) και γεννήτορα \(g\), καθώς και ιδιωτικό κλειδί \(x\), με \(0
Ο αποστολέας επιλέγει τυχαίο \(k\), με \(\gcd(k,p-1)=1\), και υπολογίζει:
στέλνοντας το ζεύγος \((r,s)\). Ο παραλήπτης αποκρυπτογραφεί μέσω \(M=s\cdot r^{-x}\bmod p\). Επαληθεύσαμε με αριθμητικό παράδειγμα (\(p=467\), \(g=2\), \(x=127\)): το μήνυμα \(M=100\) κρυπτογραφείται σωστά και ανακτάται στο τέλος ακριβώς. Η ασφάλεια εδώ στηρίζεται σε ένα εντελώς διαφορετικό δύσκολο πρόβλημα: τον υπολογισμό διακριτών λογαρίθμων.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου