Der kanadische PRNG-Experte kritisiert Behörden für die Verwendung alter Excel-Algorithmen zum Zeichnen von Visa

Das Programm zur Familienzusammenführung (Programm zur Familienzusammenführung) ist eines der drei wichtigsten kanadischen Programme zur Unterstützung von Migranten. Es ermöglicht sowohl kürzlich angekommenen Einwanderern als auch langjährigen Kanadiern, sich mit ihren Familienmitgliedern wieder zu vereinen. In Übereinstimmung mit den Einwanderungs- und Flüchtlingsschutzbestimmungen erhalten im Ausland lebende Familien ebenso wie in Kanada lebende Verwandte mit Migrationshintergrund finanzielle Unterstützung. Ehepartner, Kinder, Eltern, Enkelkinder, Adoptivkinder usw. können auf finanzielle Unterstützung zählen.

Das Problem ist, dass Kanada nicht allen Angehörigen aller Migranten sofort die Staatsbürgerschaft gewähren kann. Zuvor wurden sie in die Warteschlange gestellt, und die Prüfung des Antrags musste jahrelang erwartet werden. Um den Prozess zu beschleunigen, schlugen die Liberalen eine Lotterie vor. Seit 2017 wird in Kanada eine Lotterie wie die American Green Card gespielt. Unter den rund 100.000 Anträgen werden 10.000 nach dem Zufallsprinzip ausgewählt. Dank einer offiziellen Antwort auf eine Anfrage nach dem Gesetz über den Zugang zu Informationen hat die kanadische Veröffentlichung The Globe an Mail einige technische Details zur Durchführung der Lotterie veröffentlicht.

Es stellt sich heraus, dass die Bundesregierung die Gewinner mit Microsoft Excel auswählt. So sieht der gesamte Vorgang im Detail aus.

• Schritt 1 Das Büro für Einwanderung, Flüchtlinge und Staatsbürgerschaft (Immigration, Refugees and Citizenship Canada, IRCC) weist Microsoft Excel unter Verwendung von Microsoft Excel eine Nummer in der angegebenen Reihenfolge zu.
• Schritt 2 Jeder Anwendung mit einer Seriennummer wird mithilfe der Funktion RANDOMBETWEEN in Microsoft Excel eine Zufallszahl von 100.000 bis 9.999.999 zugewiesen.
• Schritt 3 Die Excel-Tabelle ist nach Spalten mit Zufallszahlen vom niedrigsten zum höchsten sortiert - und die ersten 10.000 Einträge werden als Lottogewinner ausgewählt.

Dieses Schema wurde von einigen Experten kritisiert. Der bekannteste Experte für die Generierung von Zufallszahlen, Professor Pierre L'Ecuyer von der Universität Montreal, der Autor vieler wissenschaftlicher Arbeiten zu RNG, nennt diesen Ansatz sehr schlecht: "Dies ist ein sehr alter Generator, der wirklich nicht als modern bezeichnet werden kann", sagt er er ist. Eine Studie von Professor L'Ecuille zeigte, dass der Excel-Pseudozufallszahlengenerator bestimmte statistische Tests nicht besteht. Für diese Anwendung ist es zwar völlig ausreichend, aber nichts hindert das IRCC daran, einfach ein normales modernes PRNG zu verwenden.

Excel verwendet mathematische Algorithmen mit einem deterministischen Ergebnis als PRNG, die von einem einzelnen Startwert abhängen. Bei Excel wird dieser Anfangswert automatisch von der Anwendung erstellt. Wenn Sie im ersten Schritt eine Zahl kennen, können Sie alle anderen Zahlen in der Sequenz berechnen. Und etwas Ähnliches sei schon einmal passiert, schreibt eine kanadische Zeitung. 1994 entdeckte der IT-Berater Daniel Corriveau dieses Muster in Keno - und gewann in einer Nacht im Montreal Casino de Montréal 600.000 CAD. Er erriet dreimal hintereinander 19 von 20 Gewinnzahlen .

Eine Untersuchung ergab, dass das Casino das gleiche alte PRNG wie in Excel verwendete. Zu Beginn eines jeden Tages wurde ein zufälliger Wert ausgewählt, und weitere Ziffern während des Tages waren Zahlen aus dieser vorhersagbaren Sequenz.

1994 schlug Professor L'Ecouillet eine Struktur für deterministische PRNGs vor $$$(\ mathcal {S}, \ mu, f, \ mathcal {U}, g)$wo $$$\ mathcal {S}$Ist eine endliche Menge von Zuständen, $$$\ mu$- Wahrscheinlichkeitsverteilung im Zustandsraum $$$\ mathcal {S}$wird verwendet, um den Anfangszustand auszuwählen $$$\ mathcal {s_ {0}}$(Samen) $$$f: \ mathcal {S} \ rightarrow \ mathcal {S}$- Übergangsfunktion, $$$\ mathcal {U}$- Raum der Ausgabewerte, $$$g: \ mathcal {S} \ rightarrow \ mathcal {U}$.

In der Regel $$$\ mathcal {U} = (0,1)$und der Zustand des Generators ist durch die Wiederholungsformel gegeben $$$s_ {i} = f \ (s_ {i-1})$für $$$i \ geq 1$. Generatorausgangswert $$$u_ {i} = g \ (s_ {i}) \ in \ mathcal {U}$;; $$$u_ {0}, \ u_ {1}, \ u_ {2} \ ...$- eine Folge von Pseudozufallszahlen. Dies ist eine periodische Sequenz, und die "Periode" wird als minimales Positiv bezeichnet $$$j$.

Unter den PRNGs sind die linearen kongruenten Methoden, die Fibonacci-Methode mit Verzögerungen, das Schieberegister mit linearer Rückkopplung und das Schieberegister mit verallgemeinerter Rückkopplung am häufigsten. Von den modernen PRNGs war auch der 1997 von Matsumoto und Nishimura vorgeschlagene Mersenna-Wirbel weit verbreitet. Seine Vorteile sind eine kolossale Periode (2 ¹⁹⁹³⁷ −1) und eine gleichmäßige Verteilung in 623 Dimensionen (die lineare kongruente Methode ergibt eine mehr oder weniger gleichmäßige Verteilung in maximal fünf Dimensionen) sowie die schnelle Erzeugung von Zufallszahlen.

Professor L'Ecuille glaubt, dass die Behörden mit dem PRNG aus Excel sehr dumm handeln, weil zuverlässige kryptografische PRNGs leicht zugänglich sind und nichts kosten: „Kryptografische Generatoren sind kostenlos. Sie sind im Internet “, sagte der Professor. "Wählen Sie einfach alle aus." Es ist überhaupt nicht schwierig. "

Die IRCC-Regierungskommission scheint jedoch mit der Verwendung von Excel zufrieden zu sein. In einer E-Mail-Erklärung schrieb Sprecherin Shannon Ker: „Wir unterstützen diesen randomisierten Auswahlprozess als ausreichendes Instrument zur Chancengleichheit für alle, die Interesse an einer Patenschaft für ihre Eltern und Großeltern bekunden möchten.“