Ένας ψευδοτυχαίος αριθμός είναι ένας ειδικός αριθμός που δημιουργείται από μια ειδική γεννήτρια. Η Deterministic Random Bit Generator (PRNG), γνωστή και ως Deterministic Random Bit Generator (DRBG), είναι ένας αλγόριθμος για τη δημιουργία μιας ακολουθίας αριθμών των οποίων οι ιδιότητες προσεγγίζουν τα χαρακτηριστικά των ακολουθιών τυχαίων αριθμών. Η παραγόμενη ακολουθία PRNG δεν είναι πραγματικά τυχαία, καθώς καθορίζεται εξ ολοκλήρου από μια τιμή σπόρων που ονομάζεται σπόρος PRNG, η οποία μπορεί να περιλαμβάνει πραγματικά τυχαίες τιμές. Αν και ακολουθίες που είναι πιο κοντά στο τυχαίο μπορούν να δημιουργηθούν χρησιμοποιώντας γεννήτριες τυχαίων αριθμών υλικού, οι γεννήτριες ψευδοτυχαίων αριθμών είναι σημαντικές στην πράξη για την ταχύτητα δημιουργίας αριθμών και την αναπαραγωγιμότητά τους.
Αίτηση
Τα
Τα PRNG είναι κεντρικά σε εφαρμογές όπως η προσομοίωση (π.χ. για το Μόντε Κάρλο), τα ηλεκτρονικά παιχνίδια (π.χ. για τη διαδικαστική δημιουργία) και η κρυπτογραφία. Οι κρυπτογραφικές εφαρμογές απαιτούν ότι η έξοδοςτα δεδομένα δεν ήταν προβλέψιμα από προηγούμενες πληροφορίες. Απαιτούνται πιο περίπλοκοι αλγόριθμοι που δεν κληρονομούν τη γραμμικότητα απλών PRNG.
Όροι και Προϋποθέσεις
Οι καλές στατιστικές ιδιότητες αποτελούν κεντρική απαίτηση για την απόκτηση ενός PRNG. Γενικά, απαιτείται προσεκτική μαθηματική ανάλυση για να βεβαιωθείτε ότι το RNG δημιουργεί αριθμούς που είναι αρκετά κοντά στο τυχαίο ώστε να είναι κατάλληλοι για την προβλεπόμενη χρήση.
Ο John von Neumann προειδοποίησε ενάντια στην παρερμηνεία του PRNG ως μια πραγματικά τυχαία γεννήτρια και αστειεύτηκε ότι "Όποιος εξετάζει αριθμητικές μεθόδους για τη δημιουργία τυχαίων αριθμών είναι σίγουρα σε κατάσταση αμαρτίας."
Χρήση
Το
PRNG μπορεί να ξεκινήσει από μια αυθαίρετη αρχική κατάσταση. Θα δημιουργεί πάντα την ίδια ακολουθία όταν αρχικοποιείται με αυτήν την κατάσταση. Η περίοδος PRNG ορίζεται ως εξής: μέγιστη σε όλες τις αρχικές καταστάσεις του μήκους του προθέματος της μη επαναλαμβανόμενης ακολουθίας. Η περίοδος περιορίζεται από τον αριθμό των καταστάσεων, που συνήθως μετρώνται σε bit. Επειδή το μήκος της περιόδου δυνητικά διπλασιάζεται με κάθε bit "κατάστασης" που προστίθεται, είναι εύκολο να δημιουργηθούν PRNG με περιόδους αρκετά μεγάλες για πολλές πρακτικές εφαρμογές.
Εάν η εσωτερική κατάσταση του PRNG περιέχει n bit, η περίοδός του δεν μπορεί να είναι μεγαλύτερη από 2n αποτελέσματα, είναι πολύ μικρότερη. Για ορισμένα PRNG, η διάρκεια μπορεί να υπολογιστεί χωρίς να παρακαμφθεί ολόκληρη η περίοδος. Οι καταχωρητές μετατόπισης γραμμικής ανάδρασης (LFSR) είναι συνήθωςεπιλέγονται έτσι ώστε να έχουν περιόδους ίσες με 2n − 1.
Οι γραμμικές συναινετικές γεννήτριες έχουν περιόδους που μπορούν να υπολογιστούν χρησιμοποιώντας παραγοντοποίηση. Αν και η ΣΔΙΤ θα επαναλάβει τα αποτελέσματά της αφού φτάσουν στο τέλος της περιόδου, ένα επαναλαμβανόμενο αποτέλεσμα δεν σημαίνει ότι έχει επιτευχθεί το τέλος της περιόδου, καθώς η εσωτερική της κατάσταση μπορεί να είναι μεγαλύτερη από την παραγωγή. αυτό είναι ιδιαίτερα εμφανές για PRNG με έξοδο ενός bit.
Πιθανά σφάλματα
Τα σφάλματα που εντοπίζονται από ελαττωματικά PRNG κυμαίνονται από διακριτικά (και άγνωστα) έως προφανή. Ένα παράδειγμα είναι ο αλγόριθμος τυχαίων αριθμών RANDU, ο οποίος χρησιμοποιείται σε μεγάλους υπολογιστές για δεκαετίες. Ήταν μια σοβαρή έλλειψη, αλλά η ανεπάρκειά της πέρασε απαρατήρητη για μεγάλο χρονικό διάστημα.
Σε πολλούς τομείς, οι ερευνητικές μελέτες που έχουν χρησιμοποιήσει τυχαία επιλογή, προσομοιώσεις Monte Carlo ή άλλες μεθόδους που βασίζονται σε RNG είναι πολύ λιγότερο αξιόπιστες από ό,τι θα μπορούσε να είναι αποτέλεσμα κακής ποιότητας GNPG. Ακόμη και σήμερα, μερικές φορές απαιτείται προσοχή, όπως αποδεικνύεται από την προειδοποίηση στη International Encyclopedia of Statistical Science (2010).
Επιτυχής μελέτη περίπτωσης
Για παράδειγμα, λάβετε υπόψη την ευρέως χρησιμοποιούμενη γλώσσα προγραμματισμού Java. Από το 2017, η Java εξακολουθεί να βασίζεται στη Linear Congruential Generator (LCG) για το PRNG της.
Ιστορία
Το πρώτο PRNG που αποφεύγει σοβαρά προβλήματα και εξακολουθεί να τρέχει αρκετά γρήγορα,ήταν το Mersenne Twister (συζητείται παρακάτω), το οποίο δημοσιεύτηκε το 1998. Έκτοτε, έχουν αναπτυχθεί και άλλα υψηλής ποιότητας PRNG.
Αλλά η ιστορία των ψευδοτυχαίων αριθμών δεν τελειώνει εκεί. Στο δεύτερο μισό του 20ου αιώνα, η τυπική κατηγορία αλγορίθμων που χρησιμοποιήθηκαν για PRNG περιελάμβανε γραμμικές συμβατές γεννήτριες. Η ποιότητα του LCG ήταν γνωστό ότι ήταν ανεπαρκής, αλλά δεν υπήρχαν καλύτερες μέθοδοι. Οι Press et al (2007) περιέγραψαν το αποτέλεσμα ως εξής: "Εάν όλες οι επιστημονικές εργασίες των οποίων τα αποτελέσματα αμφισβητούνται λόγω [LCG και σχετικών] εξαφανίζονταν από τα ράφια της βιβλιοθήκης, θα υπήρχε ένα κενό στο μέγεθος της γροθιάς σας σε κάθε ράφι."
Το κύριο επίτευγμα στη δημιουργία ψευδοτυχαίων γεννητριών ήταν η εισαγωγή μεθόδων που βασίζονται στη γραμμική αναδρομή σε ένα πεδίο δύο στοιχείων. τέτοιοι ταλαντωτές συνδέονται με καταχωρητές μετατόπισης γραμμικής ανάδρασης. Χρησιμοποίησαν ως βάση για την εφεύρεση των ψευδοτυχαίων αισθητήρων αριθμών.
Συγκεκριμένα, η εφεύρεση του 1997 από τον Mersen Twister απέφυγε πολλά από τα προβλήματα με προηγούμενες γεννήτριες. Το Mersenne Twister έχει περίοδο 219937−1 επαναλήψεων (≈4,3 × 106001). Έχει αποδειχθεί ότι κατανέμεται ομοιόμορφα σε (έως) 623 διαστάσεις (για τιμές 32 bit) και τη στιγμή της εισαγωγής του ήταν ταχύτερη από άλλες στατιστικά υγιείς γεννήτριες που παράγουν ψευδοτυχαίες ακολουθίες αριθμών.
Το 2003, ο George Marsaglia εισήγαγε μια οικογένεια γεννητριών xorshift βασισμένη επίσης σε γραμμική επανάληψη. Αυτές οι γεννήτριες είναι εξαιρετικάείναι γρήγορες και - σε συνδυασμό με μια μη γραμμική πράξη - περνούν αυστηρούς στατιστικούς ελέγχους.
Το 2006, αναπτύχθηκε η οικογένεια γεννητριών WELL. Οι γεννήτριες ΚΑΛΑ κατά μία έννοια βελτιώνουν την ποιότητα του Twister Mersenne, το οποίο έχει υπερβολικά μεγάλο χώρο κατάστασης και πολύ αργή ανάκτηση από αυτές, δημιουργώντας ψευδοτυχαίους αριθμούς με πολλά μηδενικά.
Κρυπτογραφία
Το
PRNG κατάλληλο για κρυπτογραφικές εφαρμογές ονομάζεται κρυπτογραφικά ασφαλές PRNG (CSPRNG). Η απαίτηση για ένα CSPRNG είναι ότι ένας εισβολέας που δεν γνωρίζει το seed έχει μόνο ένα οριακό πλεονέκτημα στη διάκριση της ακολουθίας εξόδου της γεννήτριας από μια τυχαία ακολουθία. Με άλλα λόγια, ενώ ένα PRNG απαιτείται μόνο για να περάσει ορισμένες στατιστικές δοκιμές, ένα CSPRNG πρέπει να περάσει όλες τις στατιστικές δοκιμές που περιορίζονται σε πολυωνυμικό χρόνο σε μέγεθος σπόρων.
Αν και η απόδειξη αυτής της ιδιότητας είναι πέρα από το τρέχον επίπεδο της θεωρίας της υπολογιστικής πολυπλοκότητας, μπορούν να παρασχεθούν ισχυρές αποδείξεις μειώνοντας το CSPRNG σε ένα πρόβλημα που θεωρείται δύσκολο, όπως η παραγοντοποίηση ακεραίων. Σε γενικές γραμμές, ενδέχεται να απαιτούνται χρόνια επανεξέτασης για να μπορέσει ένας αλγόριθμος να πιστοποιηθεί ως CSPRNG.
Έχει αποδειχθεί ότι είναι πιθανό η NSA να εισήγαγε μια ασύμμετρη πίσω πόρτα στη γεννήτρια ψευδοτυχαίων αριθμών Dual_EC_DRBG με πιστοποίηση NIST.
Ψευτοτυχαίοι αλγόριθμοιαριθμοί
Οι περισσότεροι αλγόριθμοι PRNG παράγουν αλληλουχίες που κατανέμονται ομοιόμορφα με οποιαδήποτε από τις διάφορες δοκιμές. Αυτό είναι ένα ανοιχτό ερώτημα. Είναι ένα από τα κεντρικά στη θεωρία και την πρακτική της κρυπτογραφίας: υπάρχει τρόπος να διακρίνουμε την έξοδο ενός PRNG υψηλής ποιότητας από μια πραγματικά τυχαία ακολουθία; Σε αυτήν τη ρύθμιση, ο επιλύτης γνωρίζει ότι είτε χρησιμοποιήθηκε ένας γνωστός αλγόριθμος PRNG (αλλά όχι η κατάσταση με την οποία είχε αρχικοποιηθεί), είτε χρησιμοποιήθηκε ένας πραγματικά τυχαίος αλγόριθμος. Πρέπει να διακρίνει μεταξύ τους.
Η ασφάλεια των περισσότερων κρυπτογραφικών αλγορίθμων και πρωτοκόλλων που χρησιμοποιούν PRNG βασίζεται στην υπόθεση ότι είναι αδύνατο να γίνει διάκριση μεταξύ της χρήσης ενός κατάλληλου PRNG και της χρήσης μιας πραγματικά τυχαίας ακολουθίας. Τα απλούστερα παραδείγματα αυτής της εξάρτησης είναι οι κρυπτογραφήσεις ροής, οι οποίοι συνήθως λειτουργούν παραλείποντας ή στέλνοντας το μήνυμα απλού κειμένου με έξοδο PRNG, παράγοντας το κρυπτογραφημένο κείμενο. Ο σχεδιασμός κρυπτογραφικά επαρκών PRNG είναι εξαιρετικά δύσκολος καθώς πρέπει να πληρούν πρόσθετα κριτήρια. Το μέγεθος της περιόδου του είναι ένας σημαντικός παράγοντας για την κρυπτογραφική καταλληλότητα ενός PRNG, αλλά όχι ο μοναδικός.
Ένας πρώιμος υπολογιστής PRNG που προτάθηκε από τον John von Neumann το 1946 είναι γνωστός ως μέθοδος των μέσων τετραγώνων. Ο αλγόριθμος είναι ο εξής: πάρτε οποιονδήποτε αριθμό, τον τετραγωνίστε, αφαιρέστε τα μεσαία ψηφία του προκύπτοντος αριθμού ως "τυχαίο αριθμό" και, στη συνέχεια, χρησιμοποιήστε αυτόν τον αριθμό ως αρχικό αριθμό για την επόμενη επανάληψη. Για παράδειγμα, ο τετραγωνισμός του αριθμού 1111 δίνει1234321, που μπορεί να γραφτεί ως 01234321, ένας 8ψήφιος αριθμός είναι το τετράγωνο ενός τετραψήφιου αριθμού. Αυτό δίνει το 2343 ως "τυχαίο" αριθμό. Το αποτέλεσμα της επανάληψης αυτής της διαδικασίας είναι 4896, και ούτω καθεξής. Ο Von Neumann χρησιμοποίησε 10ψήφιους αριθμούς, αλλά η διαδικασία ήταν η ίδια.
Μειονεκτήματα του "μεσαίου τετραγώνου"
Το πρόβλημα με τη μέθοδο "μέσο τετράγωνο" είναι ότι όλες οι ακολουθίες τελικά επαναλαμβάνονται, μερικές πολύ γρήγορα, για παράδειγμα: 0000. Ο Von Neumann γνώριζε για αυτό, αλλά βρήκε μια προσέγγιση επαρκή για τους σκοπούς του και ανησυχούσε ότι η οι μαθηματικές "διορθώσεις" απλώς θα έκρυβαν τα λάθη αντί να τα αφαιρέσουν.
Ο Von Neumann διαπίστωσε ότι οι γεννήτριες τυχαίων και ψευδοτυχαίων αριθμών υλικού είναι ακατάλληλες: εάν δεν καταγράψουν το παραγόμενο αποτέλεσμα, δεν μπορούν να ελεγχθούν για σφάλματα αργότερα. Εάν επρόκειτο να καταγράψουν τα αποτελέσματά τους, θα εξαντλούσαν την περιορισμένη διαθέσιμη μνήμη του υπολογιστή και συνεπώς την ικανότητα του υπολογιστή να διαβάζει και να γράφει αριθμούς. Εάν οι αριθμοί ήταν γραμμένοι σε κάρτες, θα χρειαζόταν πολύ περισσότερος χρόνος για να γραφτούν και να διαβαστούν. Στον υπολογιστή ENIAC χρησιμοποίησε τη μέθοδο του «μεσαίου τετραγώνου» και πραγματοποίησε τη διαδικασία λήψης ψευδοτυχαίων αριθμών αρκετές εκατοντάδες φορές πιο γρήγορα από την ανάγνωση αριθμών από διάτρητες κάρτες.
Το μέσο τετράγωνο έκτοτε αντικαταστάθηκε από πιο σύνθετες γεννήτριες.
Καινοτόμος μέθοδος
Μια πρόσφατη καινοτομία είναι ο συνδυασμός του μέσου τετραγώνου με την ακολουθία Weil. Αυτή η μέθοδος εξασφαλίζει προϊόντα υψηλής ποιότητας εντόςμεγάλη περίοδος. Βοηθά να αποκτήσετε τους καλύτερους τύπους ψευδοτυχαίων αριθμών.
