Πώς μια μέθοδος του Fermat απειλεί τη σημερινή ασφάλεια; 🔐

Πριν από σχεδόν 380 χρόνια, ο Πιερ ντε Φερμά (Pierre de Fermat) ανέπτυξε μία μέθοδο παραγοντοποίησης αριθμών σε πρώτους.

Σήμερα, αυτή η μέθοδος – η μέθοδος παραγοντοποίησης του Fermat – μπορεί, σε συγκεκριμένες περιπτώσεις, να απειλήσει την ασφάλεια των ψηφιακών μας δεδομένων.

Η βάση της σύγχρονης κρυπτογράφησης

Η κρυπτογράφηση RSA, που χρησιμοποιείται για την ασφαλή επικοινωνία υπολογιστών και εκτυπωτών, στηρίζεται σε ένα φαινομενικά απλό γεγονός:

Είναι εύκολο να πολλαπλασιάσεις δύο μεγάλους πρώτους αριθμούς.

Είναι εξαιρετικά δύσκολο να βρεις αυτούς τους πρώτους, αν γνωρίζεις μόνο το γινόμενό τους.

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

---

Το αδύνατο σημείο

Το 2022, ο ερευνητής Hanno Böck ανακάλυψε ότι κάποιοι κατασκευαστές εκτυπωτών χρησιμοποιούσαν πρώτους αριθμούς με μικρή τυχαιότητα.

Αυτό σημαίνει ότι οι δύο πρώτοι που χρησιμοποιούνται στο RSA είναι πολύ κοντά μεταξύ τους – και τότε η μέθοδος του Fermat γίνεται επικίνδυνα αποτελεσματική!

---

Πώς λειτουργεί η μέθοδος του Fermat

Η μέθοδος είναι πανέξυπνη και πανάρχαια απλή:

1. Παίρνουμε έναν μεγάλο σύνθετο αριθμό n, που είναι το γινόμενο δύο πρώτων.

2. Βρίσκουμε τον ακέραιο $a$ που είναι το μικρότερο μεγαλύτερο από τη ​$\sqrt{n}$.

3. Υπολογίζουμε τη διαφορά $a^2 - n$.

4. Αν η διαφορά είναι τέλειο τετράγωνο $b^2$, τότε

   $$n=(a-b)(a+b)$$

   και έχουμε βρει τους δύο πρώτους παράγοντες.

5. Αν όχι, αυξάνουμε το $a$ κατά 1 και επαναλαμβάνουμε.

Αν οι δύο πρώτοι αριθμοί είναι κοντά μεταξύ τους, η διαδικασία βρίσκει γρήγορα λύση.

---

Παράδειγμα του Fermat

Ο Fermat έδειξε τη μέθοδό του στον αριθμό:

$$n=\mathrm{2.027.651.281}$$

Η τετραγωνική ρίζα είναι περίπου 45.029,45, άρα ξεκινάμε με $a = 45.030$.
Δοκιμάζοντας διαδοχικά:

• $a = 45.030$ → διαφορά $= 49.619$(όχι τετράγωνο)

• $a = 45.031$ → διαφορά $= 139.680$ (όχι τετράγωνο)

• …

• $a = 45.041$ → διαφορά $= 1.040.400 = 1.020^2$ ✅

Έτσι,

$$n = (45.041-1.020)\times(45.041+1.020)$$

Η παραγοντοποίηση ολοκληρώθηκε!

---

Γιατί μας αφορά σήμερα

Η μέθοδος αυτή αποδεικνύει ότι αν τα κλειδιά RSA δημιουργηθούν με απρόσεκτο τρόπο, η ασφάλεια μπορεί να καταρρεύσει, ακόμη κι αν τα νούμερα είναι τεράστια.

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