Τι είναι μια γεννήτρια τυχαίων αριθμών;
Μια γεννήτρια τυχαίων αριθμών (RNG) είναι ένα σύστημα που παράγει τυχαίους ή ψευδοτυχαίους αριθμούς. Το αν ο επόμενος αριθμός μπορεί πραγματικά να προβλεφθεί εξαρτάται από το είδος της γεννήτριας. Ορισμένες βασίζονται σε μια φυσική διαδικασία, άλλες υπολογίζουν αριθμούς με έναν αλγόριθμο, και ορισμένοι αλγόριθμοι είναι σχεδιασμένοι έτσι ώστε ακόμη και αν κάποιος γνωρίζει τις προηγούμενες τιμές τους, να μην μπορεί να προβλέψει τι ακολουθεί. Το να φαίνεται κάτι τυχαίο και το να είναι απρόβλεπτο αποτελούν δύο διαφορετικές ιδιότητες, και σε αυτή τη διάκριση εστιάζει το μεγαλύτερο μέρος αυτού του άρθρου.
Γεννήτριες τυχαίων αριθμών υλικού
Μια γεννήτρια τυχαίων αριθμών υλικού (HRNG), που συχνά ονομάζεται γεννήτρια πραγματικά τυχαίων αριθμών (TRNG), αντλεί τους αριθμούς της από μια φυσική διαδικασία. Οι παλαιότερες λειτουργούν μπροστά στα μάτια μας: ένα νόμισμα που ρίχνεται στον αέρα, ένα ζάρι, ένας τροχός ρουλέτας. Οι νόμοι της φυσικής περιγράφουν πλήρως καθεμία από αυτές, ωστόσο ένας καλοφτιαγμένος τροχός είναι απρόβλεπτος στην πράξη, επειδή ανεπαίσθητες διαφορές στην αρχή κάθε περιστροφής εξελίσσονται σε εντελώς διαφορετικά αποτελέσματα.
Οι σύγχρονες γεννήτριες υλικού μετρούν αντ' αυτού μικροσκοπικά φαινόμενα: θόρυβο βολής και θερμικό θόρυβο σε ηλεκτρονικά κυκλώματα, ατμοσφαιρικό θόρυβο, κβαντικά φαινόμενα. Αυτές είναι καλές πηγές εντροπίας — μετρήσιμης απροβλεψιμότητας —, αλλά μια φυσική πηγή δεν είναι από τη φύση της τέλεια: μπορεί να παρουσιάζει αποκλίσεις, να μεταβάλλεται με την πάροδο του χρόνου ή να αστοχήσει. Γι' αυτό η ποιότητά της πρέπει να αξιολογείται και να παρακολουθείται, και οι τιμές της να υπόκεινται σε επεξεργασία όταν χρειάζεται, όπως ακριβώς περιγράφουν πρότυπα όπως το NIST SP 800-90B. Οι πηγές υλικού χρησιμοποιούνται εκεί όπου η ποιότητα της τυχαιότητας έχει τη μεγαλύτερη σημασία — κυρίως στην κρυπτογραφία, όπου παρέχουν την απρόβλεπτη πρώτη ύλη για τα κλειδιά από τα οποία εξαρτώνται πρωτόκολλα όπως το Transport Layer Security (TLS).
Γεννήτριες ψευδοτυχαίων αριθμών
Η εναλλακτική λύση σε μια φυσική συσκευή είναι ένας αλγόριθμος. Μια γεννήτρια ψευδοτυχαίων αριθμών (PRNG) παράγει μια ακολουθία που μοιάζει τυχαία, αλλά καθορίζεται πλήρως από μια αρχική τιμή (seed). Αν δώσετε στον ίδιο αλγόριθμο την ίδια αρχική τιμή, θα παράγει την ίδια ακριβώς ακολουθία κάθε φορά. Αυτό αποτελεί αδυναμία όταν ένα αποτέλεσμα πρέπει να είναι απρόβλεπτο και η αρχική τιμή ή η εσωτερική κατάσταση μπορεί να μαντευτεί ή να ανακατασκευαστεί· αποτελεί όμως πλεονέκτημα όταν ένα αποτέλεσμα πρέπει να είναι αναπαραγώγιμο, ώστε μια προσομοίωση ή μια δοκιμή να μπορεί να επαναληφθεί πανομοιότυπα. Οι PRNG είναι επίσης γρήγορες, οικονομικές και απλές στην υλοποίηση, γι' αυτό και το μεγαλύτερο μέρος του λογισμικού βασίζεται σε αυτές. Στους γνωστούς αλγορίθμους περιλαμβάνονται η γραμμική γεννήτρια υπολοίπων (LCG), οι γεννήτριες xorshift και ο Mersenne Twister.
Mersenne Twister
Ο αλγόριθμος Mersenne Twister, που δημοσιεύτηκε το 1997 από τους Makoto Matsumoto και Takuji Nishimura, είναι μία από τις πιο διαδεδομένες PRNG και η προεπιλογή σε πολλές γλώσσες προγραμματισμού. Το όνομά του προέρχεται από την περίοδό του — το μήκος της ακολουθίας προτού επαναληφθεί —, η οποία στην τυπική παραλλαγή MT19937 είναι ο πρώτος αριθμός Mersenne 219937 − 1. Περνά τα περισσότερα στατιστικά τεστ τυχαιότητας και αποδίδει εξαιρετικά σε προσομοιώσεις. Ωστόσο, δεν σχεδιάστηκε για την προστασία απορρήτων: από 624 διαδοχικές τιμές των 32 bit, ο οποιοσδήποτε μπορεί να ανακατασκευάσει την εσωτερική του κατάσταση και να προβλέψει κάθε μελλοντικό αριθμό. Δεν πρέπει ποτέ να χρησιμοποιείται για κλειδιά, κωδικούς πρόσβασης ή οτιδήποτε άλλο οφείλει να παραμείνει απρόβλεπτο.
Κρυπτογραφικά ασφαλείς γεννήτριες και εντροπία
Πολλές εφαρμογές χρειάζονται και τα δύο ταυτόχρονα: την ταχύτητα ενός αλγορίθμου και την απροβλεψιμότητα μιας φυσικής πηγής. Η λύση είναι μια κρυπτογραφικά ασφαλής γεννήτρια ψευδοτυχαίων αριθμών (CSPRNG). Μια CSPRNG εξακολουθεί να είναι μια PRNG, αλλά είναι σχεδιασμένη έτσι ώστε η γνώση οποιουδήποτε μέρους των τιμών της να μην επιτρέπει σε έναν εισβολέα να προβλέψει τα υπόλοιπα, ενώ λαμβάνει αρχική τιμή από μια πηγή πραγματικής εντροπίας που ανανεώνεται τακτικά. Μια αρχική τιμή από φυσική πηγή δεν καθιστά ασφαλή μια συνηθισμένη PRNG· ο ίδιος ο αλγόριθμος πρέπει να είναι σχεδιασμένος για αυτόν τον σκοπό. Μια φυσική πηγή, όπως ο θερμικός θόρυβος ή ο χρονισμός συμβάντων υλικού, παρέχει μια μικρή ποσότητα πραγματικής τυχαιότητας, και η CSPRNG τη μετατρέπει σε μια μακρά ακολουθία τιμών που παράγονται πολύ πιο γρήγορα. Αυτός ο συνδυασμός είναι που παρέχει ένα λειτουργικό σύστημα στα προγράμματα που εκτελούνται σε αυτό, και στην πράξη αυτό εννοείται σήμερα όταν γίνεται λόγος για «γεννήτρια τυχαίων αριθμών». Μια τέτοια γεννήτρια παράγει κλειδιά κρυπτογράφησης, διακριτικά συνεδρίας και κωδικούς πρόσβασης.
Τυχαίοι αριθμοί στο πρόγραμμα περιήγησης
Η JavaScript παρέχει σε μια ιστοσελίδα δύο ενσωματωμένους τρόπους για τη λήψη τυχαίων τιμών, οι οποίοι ανήκουν σε διαφορετικές κατηγορίες. Η συνάρτηση Math.random() είναι μια συνηθισμένη PRNG: το πρότυπο της JavaScript αφήνει την επιλογή του αλγορίθμου στο πρόγραμμα περιήγησης, χωρίς καμία εγγύηση κρυπτογραφικής ασφάλειας — κατάλληλη για μια κίνηση γραφικών, ακατάλληλη για μια κλήρωση που κάποιος θα μπορούσε να αμφισβητήσει. Ο άλλος τρόπος είναι το Web Crypto API. Η μέθοδός του, crypto.getRandomValues(), επιστρέφει κρυπτογραφικά ασφαλείς τυχαίες τιμές από μια CSPRNG που τροφοδοτείται με εντροπία από το λειτουργικό σύστημα.
Η γεννήτρια τυχαίων αριθμών μας χρησιμοποιεί το Web Crypto API για κάθε κλήρωση, και οι αριθμοί παράγονται στο πρόγραμμα περιήγησής σας, όχι σε διακομιστή. Η ίδια πηγή τροφοδοτεί και τις υπόλοιπες γεννήτριες αυτού του ιστότοπου, είτε κάνετε ρίψη ζαριών, είτε ρίψη νομίσματος είτε δημιουργία κωδικού πρόσβασης.
Από τα τυχαία bit σε έναν αριθμό εντός εύρους
Μια κρυπτογραφικά ασφαλής γεννήτρια είναι μόνο το ένα μισό μιας δίκαιης κλήρωσης. Παράγει ακατέργαστα bit, και το πρόγραμμα πρέπει να τα μετατρέψει σε έναν αριθμό εντός του εύρους που ζητήσατε — και εδώ είναι που μπορεί να εισχωρήσει μεροληψία. Ας υποθέσουμε ότι η πηγή παράγει τιμές από 0 έως 9 με ίση πιθανότητα και εσείς χρειάζεστε έναν αριθμό από 0 έως 5. Το να πάρετε το υπόλοιπο της διαίρεσης με το 6 φαίνεται προφανές, αλλά το 0, το 1, το 2 και το 3 μπορούν να προκύψουν το καθένα με δύο τρόπους, ενώ το 4 και το 5 μόνο με έναν. Έτσι, καθένας από τους αριθμούς 0 έως 3 έχει πιθανότητα 20%, ενώ το 4 και το 5 έχουν μόνο 10% ο καθένας. Η απόρριψη των τιμών που δεν διαιρούνται ομοιόμορφα είναι ένας τρόπος εξάλειψης της μεροληψίας· οι οδηγοί για τη γεννήτρια τυχαίων αριθμών περιγράφουν αυτή τη διαδικασία αναλυτικά.
Δύο ακόμη σημεία συχνά εκπλήσσουν τους χρήστες σχετικά με τις παραγόμενες τιμές. Οι επαναλήψεις είναι φυσιολογικές: σε ανεξάρτητες κληρώσεις από το 1 έως το 10 όπου κάθε αριθμός είναι εξίσου πιθανός, ο αριθμός που μόλις κληρώθηκε έχει την ίδια πιθανότητα 1 στις 10 να κληρωθεί ξανά με οποιονδήποτε άλλον. Μια κλήρωση χωρίς επαναλήψεις είναι ένα διαφορετικό είδος κλήρωσης, όχι ένα πιο τυχαίο. Και μια δίκαιη γεννήτρια δεν εξασφαλίζει από μόνη της μια δίκαιη επιλογή: η λίστα των συμμετεχόντων και ο αριθμός των προσπαθειών έχουν εξίσου μεγάλη σημασία — δείτε το άρθρο μας για το πώς να επιλέξετε έναν τυχαίο νικητή.