Factorization of a 768-bit RSA

[Open Proskopos]

The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"

Το paper, με την ανάλυση της παραγοντοποίησης του κλειδιού των 768 bit,
βρίσκεται εδώ

Αν θεωρήσουμε, πώς "κάποιοι" βρίσκονται μερικά χρόνια μπροστά από ότι γνωρίζουμε εμείς, τότε λογικά σε ~5 χρόνια, το κλειδί των 1024bit θα είναι μη αξιόπιστο.. Πλέον η λύση είναι κλειδιά 2048+...

[TNT]

The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"

Το paper, με την ανάλυση της παραγοντοποίησης του κλειδιού των 768 bit,
βρίσκεται εδώ

Αν θεωρήσουμε, πώς "κάποιοι" βρίσκονται μερικά χρόνια μπροστά από ότι γνωρίζουμε εμείς, τότε λογικά σε ~5 χρόνια, το κλειδί των 1024bit θα είναι μη αξιόπιστο.. Πλέον η λύση είναι κλειδιά 2048+...

Ναι, αν ο καθένας σπίτι του ή η εκάστοτε επιχείρηση μπορεί να αποκτήσει και από ένα Υπερυπολογιστή τότε το 1024bit κλειδί δεν θα είναι αξιόπιστο!

[c00kiemon5ter]

Use the cloud

[Jester]

Για όποιον δε μπήκε στον κόπο να διαβάσει το paper, ορίστε κάτι που αξίζει να αναφερθεί :

The following effort was involved. We spent half a year on 80 processors on polynomial selection.
This was about 3% of the main task, the sieving, which was done on many hundreds of
machines and took almost two years. On a single core 2.2 GHz AMD Opteron processor with
2 GB RAM per core, sieving would have taken about fifteen hundred years. This included a
generous amount of oversieving, to make the most cumbersome step, the matrix step, more
manageable. Preparing the sieving data for the matrix step took a couple of weeks on a few
processors, the final step after the matrix step took less than half a day of computing, but
took about four days of intensive labor because a few bugs had to be fixed.

It turned out that we had done about twice the sieving strictly necessary to obtain a usable
matrix, and that the extra data allowed generation of a matrix that was quite a bit easier than
anticipated at the outset of the project. Although we spent more computer time on the sieving
than required, sieving is a rather laid back process that, once running, does not require much
care beyond occasionally restarting a machine. The matrix step, on the other hand, is a more
subtle affair where a slight disturbance easily causes major trouble, in particular if the problem
is by its sheer size stretching the available resources. Thus, our approach to overspend on an
easygoing part of the computation led to a matrix that could be handled relatively smoothly,
thereby saving us considerable headaches. More importantly, and another reason behind the
oversieving, the extra sieving data allow us to conduct various experiments aimed at getting
a better understanding about the relation between sieving and matrix efforts and the effect
on NFS feasibility and overall performance. This is ongoing research, the results of which will
be reported elsewhere. All in all, the extra sieving cycles were well spent.

[Open Proskopos]

Ναι, αν ο καθένας σπίτι του ή η εκάστοτε επιχείρηση μπορεί να αποκτήσει και από ένα Υπερυπολογιστή τότε το 1024bit κλειδί δεν θα είναι αξιόπιστο!

Μα αυτός που θα θέλει να αποκτήσει πρόσβαση στα δεδομένα σου, δεν θα είναι ο γείτονας σου... θα είναι κάποιος που αναζητά μαζικά κλειδιά πολλών χρηστών... Και σε περιπτώσεις επιχειρήσεων, αν νομίζεις οτι ειναι σπάνιο τότε κάνεις μεγάλο λάθος... Οχι, ο μαναβης της γειτονιάς δεν κινδυνεύει, αλλά μεγάλες επιχειρήσεις που βασίζονται σε μεθόδους, όπως είπε ο Ιησούς, Cloud computing, τότε οι κίνδυνοι είναι πολλοί..

[gasparosoft]

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

[TNT]

Δεν μίλησα ούτε για γείτονες ούτε για μανάβηδες! Το cloud δεν μου λέει κάτι, ούτε αυτοί που το πρωτοέφτιαξαν δεν ξέρουν ακόμα τι είναι και πως θα λειτουργήσει.

"Κάποιος που αναζητά μαζικά κλειδιά πολλών χρηστών" δεν μπαίνει στον κόπο να σπάσει 768, 1024, ++ bit κλειδία, αναζητά πιο εύκολους τρόπους γιατί απλά δεν θέλει να το κάνει. Ξέρει ότι πάντα υπάρχουν άλλοι τρόποι πιο εύκολοι για να διεισδύσει. Δεκάδες τρόποι με δεκάδες παραλλαγές. Πάντα αναζητάς τον πιο εύκολο τρόπο.

Ακόμα και στη βιομηχανική κατασκοπεία αυτό γίνεται. Δεν δίνει άλλος 2.000.000 ευρώ πχ για μηχανήματα για να έχεις κέρδος 1.000.000 ευρώ "χτυπώντας" τα μηχανήματα ανταγωνιστή. Και οι εταιρείες αυτή τη στιγμή στην πλειοψηφία τους χρησιμοποιούν 128, 256bit κλειδία κρυπτογράφησης. Ρωτήστε και θα δείτε (βλέπε πχ Aladdin, AES 128bit χρησιμοποιεί). Άσε που οι περισσότερες εταιρείες όχι κρυπτογράφηση αλλά ούτε κωδικούς δεν χρησιμοποιούν.

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

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

Και η NSA δεν πιστεύω πως κάθεται να σπάει αλγορίθμους ζητά από προγραμματιστές και μαθηματικούς να αφήνουν backdoors στους αλγορίθμους(γιατί απλά είναι η NSA). Κάτι τέτοιο έχει συμβεί στο παρελθόν.

[Open Proskopos]

Δεν διαφωνώ σε αυτό που λες, ωστόσο, δεν εχει σχέση τι άλλες μεθόδους ασφαλείας θα εχει κάποιος, για να μπορεί ο κρυπταναλυτής να επιλέξει τον πιο ευκολο... Συγκεκριμένα για το κείμενο σχολίασα και για το κλειδί 768.. Επίσης οι άλλες μέθοδοι δεν είναι απαραίτητα υλοποιήσιμοι σε μερικές περιπτώσεις και η μόνη ασφάλεια παρέχεται από κρυπτογράφηση...
Όμως ας σκεφτούμε και το εξής... Σήμερα χρειάστηκαν 10 χρόνια για να σπάσουν το κλειδί.. Δεν σημαίνει οτι και σε 2 χρόνια, ο χρόνος κρυπτανάλυσης θα θέλει άλλα 10..
Θα έχουν βρεθεί ταχύτεροι αλγόριθμοι, άλλωστε για τώρα σημασία εχει οτι ανακαλύφθηκε ο τρόπος δημιουργίας των κλειδιών 768. (ίσως κάνω λάθος σε αυτό, αλλα έτσι νομίζω)...

Δεν δίνει άλλος 2.000.000 ευρώ πχ για μηχανήματα για να έχεις κέρδος 1.000.000 ευρώ "χτυπώντας" τα μηχανήματα ανταγωνιστή.

Αυτό είναι προφανές, αλλά μην γενικεύεις, διότι υπάρχουν περιπτώσεις που η αναλογιά είναι αντίστροφή από αυτήν που γράφεις... Και δεν ειναι καθόλου σπάνιο κιολας... σκέψου εταιρίες μεγαλύτερου βεληνικούς (google - microsoft)..