Πραγματικά απεχθάνομαι όλους αυτούς τους γρίφους CAPTCHA, και ειδικά αυτούς που μου ζητούν να βρω τα κρυμμένα φανάρια ή τις διαβάσεις πεζών – στη Μεγάλη Βρετανία τις ονομάζουμε διαβάσεις Ζέβρα, και δε μοιάζουν τόσο, με αυτές των ΗΠΑ. Οπότε τις πρόάλλες χάρηκα ιδιαίτερα, όταν συνδέθηκα σε μία συνδιάσκεψη κρυπτογραφίας και είδα το εξής:
Δηλαδή, μετά από περισσότερα από 40 χρόνια, ο RSA ζει και βασιλεύει. Στο άρθρο αυτό, θα σας δώσω ένα μήνυμα κρυπτογραφημένο από τον RSA και -ελπίζω να- το λύσετε και να βρείτε το ροκ συγκρότημα:
Μπορείτε να βρείτε το ροκ συγκρότημα; N=879509040449463763008386484793372267, cipher=850431005415590313843011081245086829
Για μένα, ο αλγόριθμος RSA έχει μια σπάνια ομορφιά. Για περισσότερα από 40 χρόνια, προστατεύει τους χρήστες από το κυβερνοέγκλημα περισσότερο από οτιδήποτε άλλο. Ο RSA βρίσκεται ακόμα στην κορυφή της «Υποδομής Δημοσίου Κλειδιού» (Public Key Infrastructure – PKI) και προστατεύει τους χρήστες από τις ψεύτικες ιστοσελίδες, αποδεικνύει τη γνησιότητά τους και σταματάει την ηλεκτρονική κατασκοπεία μεταξύ χρηστών. Παρόλο που οι ελλειπτικές καμπύλες νικούν τον RSA στα περισσότερα σημεία, αυτός είναι ακόμα εκεί, και πρωτοστατεί.
Γνωρίστε τον πρωταθλητή
Τον Αύγουστο του 1977, οι Stranglers βρίσκονταν στα charts με το “Something Better Change” και πραγματικά κάτι άλλαζε, κάτι επρόκειτο δηλαδή να αλλάζει τον κόσμο για πάντα. Ήταν ο μήνας που ο Martin Gardner, στη στήλη του στο επιστημονικό περιοδικό Scientific American, δημοσίευσε μία εφαρμογή ενός αλγορίθμου που άντεξε στο πέρασμα του χρόνου: τον RSA.
Είχε σχέση με τη δουλειά των R(ivest), S(hamir) και A(dleman) και ήταν ένας γρίφος σχετικός με την ανακάλυψη μίας μεθόδου που επέτρεπε τη δημιουργία δύο κλειδιών, από τα οποία, το ένα κρυπτογραφούσε, το άλλο αποκρυπτογραφούσε. Η δουλειά τους βασιζόταν σε μία εισήγηση των Whitfield Diffie και Martin Hellman πάνω στις συναρτήσεις “καταπακτή” (trapdoor functions) που μπορούν να χρησιμοποιηθούν για να κατασκευάσουν το ζευγάρι κλειδιών.
Για να εξηγήσει τη λογική του RSA, ο Martin παρείχε ένα υπόβαθρο της μεθόδου Diffie-Hellman, για την οποία έγραψε:
Τότε, το 1975 ένα νέο είδος κρυπτογραφήματος προτάθηκε που άλλαξε ριζικά την κατάσταση, παρέχοντας έναν νέο ορισμό του “αδιαρρήκτου”, έναν ορισμό που προέρχεται από ένα παρακλάδι της επιστήμης των υπολογιστών, γνωστό ως θεωρία της πολυπλοκότητας. Τα νέα αυτά κρυπτογραφήματα δεν είναι απολύτως αδιάρρηκτα με την έννοια του σημειωματαρίου μιας χρήσης – one-time pad – OTP, αλλά πρακτικά είναι αδιάρρηκτα με μια πολύ ισχυρότερη έννοια από κάθε άλλο κρυπτογράφημα που σχεδιάστηκε στο παρελθόν για μαζική χρήση. Κατ’ αρχήν, τα νέα αυτά κρυπτογραφήματα μπορούν να σπάσουν, αλλά μόνο από υπολογιστικά προγράμματα που τρέχουν εκατομμύρια χρόνια!
Γενικά, η μέθοδος Diffie-Hellman τα πήγε πολύ καλά, αλλά τα τελευταία χρόνια, που η επεξεργαστική ισχύς των υπολογιστών ολοένα και αυξάνεται, δεν μπορεί να αντεπεξέλθει. Η εκτίμηση των εκατομμυρίων χρόνων υπολογισμών δεν ισχύει στη σημερινή εποχή, μιας και τα αρχικά κρυπτογραφήματα μπορούν εύκολα να «σπάσουν» με τους πιο απλούς υπολογιστές μέσα σε λίγα μόνο λεπτά μόνο!
Για τη μέθοδο RSA, ο Martin Gardner έγραψε:
Το έργο τους, που υποστηρίζεται από επιχορηγήσεις από το NSF και το Γραφείο Ναυτικής Έρευνας, εμφανίζεται στο On Digital Signatures and Public-Key Cryptosystems (Technical Memo 82. April. 1977) που εκδόθηκε από το Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge Mass, 02139.
Η έρευνα αυτή, είναι προσβάσιμη σε όλους, αρκεί να γράψετε στον Rivest στην παραπάνω διεύθυνση, σε έναν φάκελο 9-επί-12-ίντσες με το όνομα και την διεύθυνσή σας.
Ως απάντηση, οι αιτούντες έλαβαν τελικά (σε πολλές περιπτώσεις χρειάστηκαν πάνω από τέσσερις μήνες) ένα πολύτιμο-ιστορικό πια-αντίτυπο του έργου:
Στις μέρες μας μοιάζει απίστευτο, αλλά οι αρχικές μέθοδοι βασίζονταν σε δύο 63-ψήφιους πρώτους αριθμούς που πολλαπλασιάζονταν και έδιναν μία 126-ψήφια τιμή:
Συγκρίνετε αυτό με τη δυσκολία εύρεσης των δύο πρώτων παραγόντων ενός 125- ή 126-ψήφιου αριθμού, που προκύπτει πολλαπλασιάζοντας δύο 63-ψήφιους πρώτους. Εάν χρησιμοποιηθεί ο καλύτερος γνωστός αλγόριθμος και οι ταχύτεροι σημερινοί υπολογιστές, ο Rivest εκτιμά ότι ο απαιτούμενος χρόνος εκτέλεσης θα είναι 40 τετράκις εκατομμύρια χρόνια!
Ένας αριθμός 256-bit, στο μέγιστο, δημιουργεί 78 ψηφία [δείτε εδώ]:
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936
Τα 40 τετράκις εκατομμύρια χρόνια δεν ισχύουν πλέον, αφού κλειδιά των 512 bits σπάνε εύκολα στο Cloud. Εάν σας ενδιαφέρει, εδώ είναι μία ακέραια τιμή 512-bit που έχει 148 ψηφία, όπως [παράδειγμα]:
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,5 92,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,9 03,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096
Η αναζήτηση πρώτων αριθμών γίνεται, επίσης, ολοένα εντονότερη από το 1977, και μέχρι το 2014, έχει ανακαλυφθεί 17.425.170-ψήφιος πρώτος αριθμός. Η ανακάλυψη πρώτων αριθμών κάνει την εύρεσή τους στη μέθοδο RSA πολύ ευκολότερη.
Έτσι, η μέθοδος RSA δέχεται επίθεση εδώ και χρόνια, λόγω τόσο της ανακάλυψης πρώτων αριθμών, όσο και των παραγοντοποιήσεων τους. Παράλληλα, η υπολογιστική ισχύς των σημερινών υπολογιστών έχει αυξηθεί κατακόρυφα. Σκεφτείτε ότι από τότε έχουν περάσει 40 χρόνια, και δείτε ότι η υπολογιστική ισχύς κάθε χρόνο διπλασιάζεται:
1977 4 τετράκις εκατομμύρια χρόνια (4,000,000,000,000,000) 1978 2 τετράκις εκατομμύρια χρόνια 1979 1 τετράκις εκατομμύριο χρόνια ... 2015 3,637 χρόνια
Εάν πάρουμε δε μία κάρτα NVIDIA με 4.000 επεξεργαστές, μειώνουμε τον χρόνο σε λιγότερο από ένα έτος, και αν ομαδοποιήσουμε μερικές από αυτές, τον εκμηδενίζουμε σε λιγότερο από μία μέρα! Η ευπάθεια FREAK (Factoring RSA Export Keys) προκλήθηκε από τον περιορισμό των κλειδιών RSA, λόγω των ελέγχων εξαγωγών των ΗΠΑ, σε 512-bits [δείτε εδώ].
Η έρευνα του RSA έχει γίνει μία από τις πιο αναφερόμενες έρευνες σε ολόκληρη την επιστήμη υπολογιστών – με 22.019 αναφορές [δείτε εδώ]:
Για να δούμε αν μπορούμε να λύσουμε αυτόν τον γρίφο κρυπτογράφησης RSA…
Τα βασικά του RSA
Η βασική λογική του RSA είναι η εξής: Έχουμε δύο τυχαίους πρώτους αριθμούς p και q) και δημιουργούμε το γινόμενό τους (N):
Έπειτα υπολογίζουμε τη συνάρτηση του Euler φ:
Τώρα επιλέγουμε μία τιμή για το κλειδί κρυπτογράφησης (e) που δεν έχει κοινό παράγοντα με τον αριθμό φ. Εάν επιλέξουμε έναν μικρό πρώτο αριθμό, θα μπορούμε να επιλέξουμε οποιαδήποτε τιμή, αλλά η πιο συνηθισμένη είναι το 65.537. Το κλειδί κρυπτογράφησης είναι το (e,N), και κρυπτογραφούμε με:
Για να υπολογίσουμε την τιμή του κλειδιού αποκρυπτογράφησης (d), βρίσκουμε:
Η τιμή του d μπορεί να βρεθεί με τον αντίστροφο του e mod N. Ο κώδικας αποκρυπτογράφησης όταν γνωρίζουμε την τιμή του κρυπτογραφήματος (cipher, c) και τα p και q [δείτε εδώ]:
https://asecuritysite.com/encryption/rsa12_2
from Crypto.Util.number import long_to_bytes
import libnum
import sys
p=954354002755510667
q=801297755486859913
c=607778777406675887172756406181993732
#N=764721720347891218098402268606191971
n = p*q
PHI=(p-1)*(q-1)
e=65537
d=(libnum.invmod(e, PHI))
res=pow(c,d, n)
print ("Cipher: ",c)
print ("p: ",p)
print ("q: ",q)
print ("\n=== Calc ===")
print ("d=",d)
print ("n=",n)
print ("Decrypt: %s" % ((long_to_bytes(res))))
Άρα, η δυσκολία έγκειται στην παραγοντοποίηση του N, ενώ αν έχουμε χρησιμοποιήσει σχετικά μικρούς πρώτους αριθμούς – όπως αριθμούς μικρότερους των 128 bits – τότε μπορούμε εύκολα να παραγοντοποιήσουμε το N, σε p και q, και έπειτα να αποκρυπτογραφήσουμε τα δεδομένα.
Εάν έχουμε το εξής πρόβλημα:
Μπορείτε να βρείτε την πόλη της Αγγλίας; N=826382916071823972711332001902568877 cipher=511617430183577168370958189976920833
Μπορούμε να χρησιμοποιήσσουμε ένα πρόγραμμα παραγοντοποίησης [δείτε εδώ] για να παραγοντοποιήσουμε το N:
Και μετά να αντιγράψουμε και να επικολλήσουμε τις τιμές:
Οπότε, το κρυπτογράφημά μας γίνεται: “york”.
Συμπεράσματα
Ζω και εργάζομαι σε μία πανέμορφη πόλη – το Εδιμβούργο – αλλά για μένα, η μέθοδος RSA παραμένει εξαιρετικά όμορφη!
Για να δούμε αν έχουμε κατανοήσει το βασικό τρόπο που «δουλεύει» ο αλγόριθμος,
άρα, ποιο είναι το ροκ συγκρότημα;
N=879509040449463763008386484793372267, cipher=850431005415590313843011081245086829
Γράφει ο: Prof Bill Buchanan OBE, Professor of Cryptography
Επιμέλεια-μετάφραση: Χρήστος Λοΐζος, Χρήστος Κατσανδρής
Πηγή: medium.com
