Πώς οι υπολογιστές παράγουν τυχαίους αριθμούς

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

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

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

Τι τυχαίοι αριθμοί χρησιμοποιούνται για

Τυχαίοι αριθμοί έχουν χρησιμοποιηθεί για πολλές χιλιάδες χρόνια. Είτε σπρώχνει ένα νόμισμα ή τράβηγμα ζάρια, ο στόχος είναι να αφήσει το τελικό αποτέλεσμα μέχρι τυχαία ευκαιρία. Οι τυχαίες γεννήτριες αριθμών σε έναν υπολογιστή είναι παρόμοιες - πρόκειται για μια προσπάθεια να επιτευχθεί ένα απρόβλεπτο, τυχαίο αποτέλεσμα.

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

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

Αληθινοί τυχαίοι αριθμοί

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

Γενικά ομαδοποιούμε τους τυχαίους αριθμούς που παράγουν οι υπολογιστές σε δύο τύπους, ανάλογα με τον τρόπο που παράγονται: "Αληθινά" τυχαίοι αριθμοί και ψευδοτυχαίοι αριθμοί.

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

Για ένα πιο καθημερινό παράδειγμα, ο υπολογιστής θα μπορούσε να βασιστεί στον ατμοσφαιρικό θόρυβο ή απλά να χρησιμοποιήσει την ακριβή ώρα που πατάτε τα πλήκτρα του πληκτρολογίου σας ως πηγή απρόβλεπτων δεδομένων ή εντροπίας. Για παράδειγμα, ο υπολογιστής σας μπορεί να παρατηρήσει ότι πατήσατε ένα πλήκτρο ακριβώς 0,23423523 δευτερόλεπτα μετά τις 2 μ.μ. ... Αρπάξτε αρκετούς από τους συγκεκριμένους χρόνους που σχετίζονται με αυτά τα πλήκτρα και θα έχετε μια πηγή εντροπίας που μπορείτε να χρησιμοποιήσετε για να δημιουργήσετε ένα "αληθινό" τυχαίο αριθμός. Δεν είστε μια προβλέψιμη μηχανή, οπότε ένας εισβολέας δεν μπορεί να μαντέψει την ακριβή στιγμή που πατάτε αυτά τα πλήκτρα. Η / dev / τυχαία συσκευή στο Linux, η οποία παράγει τυχαίους αριθμούς, "μπλοκάρει" και δεν επιστρέφει αποτέλεσμα μέχρι να συγκεντρώσει αρκετή εντροπία για να επιστρέψει έναν πραγματικά τυχαίο αριθμό.

Αριθμοί ψευδοτυχαίων αριθμών

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

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

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

Η NSA και η γεννήτρια τυχαίων αριθμών υλικού της Intel

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

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

Αυτό αποτελεί σοβαρό πρόβλημα. Τον Δεκέμβριο του 2013, οι προγραμματιστές του FreeBSD απέσυραν την υποστήριξη για τη χρήση του RdRand απευθείας ως πηγή τυχαίων στοιχείων, λέγοντας ότι δεν μπορούσαν να το εμπιστευτούν. [Source] Η έξοδος της συσκευής RdRand θα τροφοδοτηθεί σε έναν άλλο αλγόριθμο που προσθέτει πρόσθετη εντροπία, εξασφαλίζοντας ότι οποιαδήποτε backdoors στη γεννήτρια τυχαίων αριθμών δεν θα είχε σημασία. Το Linux έχει ήδη δουλέψει με αυτόν τον τρόπο, τυχαιοποιώντας τα τυχαία δεδομένα που προέρχονται από το RdRand, έτσι ώστε να μην είναι προβλέψιμο ακόμα και αν υπήρχε backdoor. [Source] Σε πρόσφατο AMA ("Ask Me Anything") στην Reddit, ο Διευθύνων Σύμβουλος της Intel, Brian Krzanich, δεν απάντησε σε ερωτήσεις σχετικά με αυτές τις ανησυχίες. [Πηγή]

Φυσικά, αυτό πιθανό δεν είναι μόνο ένα πρόβλημα με τα μάρκες της Intel. Οι προγραμματιστές του FreeBSD ονόμασαν και τις μάρκες της Via. Αυτή η διαμάχη δείχνει γιατί η δημιουργία τυχαίων αριθμών που είναι πραγματικά τυχαίοι και δεν είναι προβλέψιμοι είναι τόσο σημαντικός.

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

Image Credit: recre89 στο Flickr, Lisa Brewster στο Flickr, Ryan Somma στο Flickr, huangjiahui στο Flickr