Τι είναι η κρυπτογράφηση RSA και πώς να λύσουν τα αριθμητικά τους;

Το RSA (RIVEST-SHAMIR-ADLEMAN) είναι ένα ευρέως χρησιμοποιούμενο κρυπτοσυστήματα δημόσιου κλειδιού. Βασίζεται στην πρακτική δυσκολία του παράγοντα του προϊόντος δύο μεγάλων πρωταρχικών αριθμών. Εδώ είναι μια κατανομή:

Πώς λειτουργεί το RSA:

1. Γενιά κλειδιών:

*Επιλέξτε δύο ξεχωριστούς πρώτους αριθμούς, *P *και *Q *. Όσο μεγαλύτερα είναι αυτά, τόσο πιο ασφαλής είναι η κρυπτογράφηση.

* Υπολογίστε * n =p * q *. * n* είναι το μέτρο.

* Υπολογίστε φ (n) =(p-1) (q-1). Αυτή είναι η ολική λειτουργία του Euler, που αντιπροσωπεύει τον αριθμό των ακεραίων λιγότερο από το *N *που είναι σχετικά πρωταρχικοί στο *n *.

* Επιλέξτε έναν ακέραιο * e * (δημόσιο εκθέτη) έτσι ώστε να είναι COPRIME). Μια κοινή επιλογή είναι 65537 (2 16 + 1).

* Υπολογίστε * d * (ιδιωτικός εκθέτης) έτσι ώστε * d * * e ≡ 1 (mod φ (n)). Αυτό σημαίνει * d * * * e * αφήνει ένα υπόλοιπο 1 όταν διαιρείται με φ (n). Αυτό γίνεται συνήθως χρησιμοποιώντας τον εκτεταμένο αλγόριθμο ευκλείδειος.

2. Δημόσιο κλειδί: Το δημόσιο κλειδί είναι το ζευγάρι (*n*,*e*). Αυτό μοιράζεται δημοσίως.

3. Ιδιωτικό κλειδί: Το ιδιωτικό κλειδί είναι το ζευγάρι (*n*,*d*). Αυτό πρέπει να παραμείνει μυστικό.

4. Κρυπτογράφηση: Για να κρυπτογραφήσετε ένα μήνυμα *m *(αντιπροσωπεύεται ως αριθμός μικρότερος από *n *):

* Ciphertext * c * =* m e *(mod *n *)

5. Αποκρυπτογράφηση: Για να αποκρυπτογραφήσετε το κρυπτογράφημα *C *:

* Plaintext * m * =* c d *(mod *n *)

Γιατί λειτουργεί: Το θεώρημα του Euler δηλώνει ότι εάν *a *και *n *είναι coprime, τότε *a φ (n) ≡ 1 (mod n)*. Η επιλογή του * d * και της αρθρωτής αριθμητικής εξασφαλίζει ότι η αποκρυπτογράφηση ανακτά σωστά το αρχικό μήνυμα. Το σπάσιμο RSA βασίζεται στο factoring *n *σε *p *και *q *, το οποίο είναι υπολογιστικά ανέφικτο για επαρκώς μεγάλες αρχές.

Επίλυση αριθμητικών RSA:

Η δυσκολία επίλυσης των αριθμητικών προβλημάτων RSA εξαρτάται από τις πληροφορίες που δίνονται. Ακολουθούν παραδείγματα τυπικών προβλημάτων και πώς να τα λύσετε:

Παράδειγμα 1:κρυπτογράφηση

* Πρόβλημα: Δεδομένου ότι * p * =11, * q * =13, * e * =7 και μήνυμα * m * =5, κρυπτογραφήστε το μήνυμα.

* Λύση:

1. Υπολογίστε * n * =* p * * * q * =11 * 13 =143

2. Υπολογίστε φ (n) =(11-1) (13-1) =120

3. Βεβαιωθείτε ότι το GCD (7, 120) =1 (είναι coprime)

4. Encrypt:*c *=*m e *(mod *n *) =5 7 (Mod 143)

* 5 7 =78125

* 78125 ÷ 143 ≈ 546 με υπόλοιπο 67

* Επομένως, * C * =67

Παράδειγμα 2:αποκρυπτογράφηση

* Πρόβλημα: Δεδομένου ότι * p * =11, * q * =3, * e * =7 και ciphertext * c * =10, αποκρυπτογραφήστε το κρυπτογράφημα.

* Λύση:

1. Υπολογίστε * n * =* p * * * q * =11 * 3 =33

2. Υπολογίστε φ (n) =(11-1) (3-1) =20

3. Βρείτε * d * έτσι ώστε * d * * * e * ≡ 1 (mod φ (n)) Αυτό σημαίνει 7 * * d * ≡ 1 (mod 20). Μπορείτε να το λύσετε χρησιμοποιώντας τον εκτεταμένο αλγόριθμο της Ευκλείουσας ή με δοκιμή και σφάλμα. * d * =3 λειτουργεί επειδή (7 * 3) =21 ≡ 1 (mod 20).

4. Αποκλεισμός:*m *=*c d *(mod *n *) =10 3 (Mod 33)

* 10 3 =1000

* 1000 ÷ 33 ≈ 30 με ένα υπόλοιπο των 10

* Επομένως, * m * =10

Παράδειγμα 3:εύρεση d (ιδιωτικός εκθέτης)

Η εύρεση του «D» απαιτεί συχνά τον εκτεταμένο αλγόριθμο της Ευκλείδευσης, ο οποίος είναι πέρα από το πεδίο εφαρμογής μιας απλής εξήγησης εδώ. Ωστόσο, για μικρότερους αριθμούς, η δοκιμή και το σφάλμα μπορεί να λειτουργούν. Ψάχνετε για έναν αριθμό «D» που ικανοποιεί την συμμόρφωση * d * * e ≡ 1 (mod φ (n)).

Σημαντικές εκτιμήσεις:

* Μεγάλοι αριθμοί: Το πραγματικό RSA χρησιμοποιεί εξαιρετικά μεγάλους πρώτους αριθμούς (εκατοντάδες ή χιλιάδες bits). Οι χειροκίνητοι υπολογισμοί είναι αδύνατοι. Απαιτείται εξειδικευμένο λογισμικό.

* αρθρωτή αριθμητική: Η κατανόηση της αρθρωτής αριθμητικής είναι ζωτικής σημασίας για τη συνεργασία με την RSA. Πολλές αριθμομηχανές και γλώσσες προγραμματισμού έχουν ενσωματωμένες λειτουργίες για αρθρωτή εκτίμηση.

* Ασφάλεια: Η ασφάλεια του RSA εξαρτάται εξ ολοκλήρου από τη δυσκολία να παραγοντώσει μεγάλους αριθμούς. Καθώς αυξάνεται η υπολογιστική ισχύς, το μέγεθος των αρχικών που χρησιμοποιούνται πρέπει επίσης να αυξηθεί για να διατηρηθεί η ασφάλεια.

Αυτά τα παραδείγματα απεικονίζουν τις βασικές αρχές. Για πιο προηγμένα προβλήματα, πιθανότατα θα χρειαστεί να χρησιμοποιήσετε υπολογιστικά εργαλεία και μια βαθύτερη κατανόηση της θεωρίας των αριθμών.