Ο αλγόριθμος RSA έπαψε να είναι ασφαλής

[mandarinos]

Η είδηση εδώ.

Πρέπει όλοι να κατανοήσουν (ναι, και οι πολιτικοί που μας τα πρήξανε με την δήθεν ασφάλεια συστημάτων, κυρίως αυτοί!  ) πως πρόκειται γιά αλυσίδα: βρίσκεται (κρυπτογραφικό) κλειδί / βρίσκεται αντικλείδι / βρίσκεται το επόμενο κλειδί / βρίσκεται το επόμενο αντικλείδι / και ούτω καθ' εξής, ad infinitum.

[pgrontas]

Clickbait.

Μπορείς να 'σπάσεις' το RSA και με το χέρι αν υπάρχει αρκετός χρόνος.
Από τη στιγμή που η σύγχρονη κρυπτογραφία έχει θεμελιωθεί στην υπολογιστική πολυπλοκότητα, δηλαδή σε προβλήματα που πιστεύουμε ότι είναι υπολογιστικά δύσκολα (αλλά παρ'όλα αυτά έχουν brute force λύση), η λογική του άρθρου δεν ευσταθεί.

Αυτό φυσικά δε σημαίνει ότι ο αλγόριθμος του Shor (γνωστός από δεκαετία 90) και οι κβαντικοί υπολογιστές δεν αποτελούν ιδιαίτερη απειλή για τα τρέχοντα (ασύμμετρα) συστήματα. Όμως, υπάρχει ήδη από το 2016 διαδικασία αντικατάστασης (από το NIST - κυβερνητικός οργανισμός)  με post quantum secure πρωτόκολλα, η οποία αν δεν κάνω λάθος έχει ορίζοντα εφαρμογής το 2035.

Δεν είναι κάτι καθόλου απλό, για δύο λόγους:

1. Υπάρχει τεράστιος όγκος κώδικα που ήδη λειτουργεί και δεν μπορείς να αντικαταστήσεις μια και έξω (ας μην ξεχνάμε ότι το IPv6 είναι λειτουργικό από το 1998 τουλάχιστον και μόνο τα τελευταία χρόνια έχει αρχίσει να εφαρμόζεται μαζικά και όχι παντού ακόμα).

2. Tα προβλήματα RSA και διακριτού λογαρίθμου έχουν μελετηθεί εδώ και 50 χρόνια και η κοινότητα είναι αρκετά σίγουρη ότι δεν κινδυνεύουν από τους κλασικούς τουλάχιστον υπολογιστές. Από την άλλη τα post quantum δεν έχουν μελετηθεί τόσο. Για παράδειγμα, μία από τις προτάσεις του NIST για post quantum ασφαλή κρυπτογραφία, το SIKE, έσπασε το 2022 από κλασικό αλγόριθμο (σε μία ώρα υπολογισμού σε κοινό laptop αν θυμάμαι καλά).

[pgrontas]

Μιας και τέθηκε σαν θέμα βάζω ένα πρόσφατο επικό paper-τρολάρισμα στους διάφορους ισχυρισμούς για παραγοντοποιήσεις από κβαντικούς υπολογιστές.

https://eprint.iacr.org/2025/1237.pdf

Σε αυτό οι συγγραφείς παρατηρούν ότι όλες οι ισχυριζόμενες παραγοντοποιήσεις από κβαντικούς υπολογιστές αφορούν στην πραγματικότητα αριθμούς όπου είναι είτε τετριμμένοι, είτε ειδικές περιπτώσεις π.χ οι πρώτοι διαφέρουν μόνο κατά μερικά λιγότερο σημαντικά bits (εντελώς ακατάλληλοι για το RSA), είτε μπορούν με επεξεργασία να μετατραπούν σε ειδικές περιπτώσεις (όμως αυτό είναι γνωστό εκ των προτέρων).
Με βάση αυτό παραγοντοποιούν αριθμούς που ισχυρίζονται ότι έχουν παραγοντοποιηθεί από κβαντικούς υπολογιστές χρησιμοποιώντας έναν υπολογιστή με λέξη 8bit που δεν υποστηρίζει πολλαπλασιασμό ή διαίρεση, με έναν άβακα και ένα σκύλο...

Το τρολάρισμα είναι επικό με ατάκες όπως:

As has been previously pointed out, the 2001 and 2012 quantum factorisation records may be easily matched with a dog trained to bark three times [31]. We verified this by taking a recently-calibrated reference dog, Scribble, depicted in Figure 6, and having him bark three times, thus simultaneously factorising both 15 and 21. This process wasn't as simple as it first appeared because Scribble is very well behaved and almost never barks. Having him perform the quantum factorisation required having his owner play with him with a ball in order to encourage him to bark. It was a special performance just for this publication, because he understands the importance of evidence-based science. The process was then repeated to have him bark five times, factorising the number 35 and thereby exceeding the capabilities of the quantum factorisation physics experiments mentioned earlier.

Το σημαντικό είναι αυτό που αναφέρεται στην αρχή του paper:

New technologies, when introduced, are typically given names that overstate their capabilities, usually by equating them with existing familiar systems or technological artefacts. For example the first computers in the 1940s and 1950s, often little more than glorified electric adding machines, were nevertheless described as "electronic brains". More recently, large language models (LLMs) have been touted as "artificial intelligence", and complex physics experiments have been touted as "quantum computers".

Disclaimer: Αυτό το τρολάρισμα φυσικά δεν αφορά το αποτέλεσμα του Shor ότι ως πρόβλημα η παραγοντοποίηση είναι πιο εύκολη με κβαντικούς υπολογιστές, αλλά τους διάφορους ισχυρισμούς από εμπορικές επιχειρήσεις ή επιστήμονες που ψάχνουν χρηματοδότηση, ότι είναι κάτι που ήδη γίνεται.