- PVSM.RU - https://www.pvsm.ru -

Канадский эксперт по ГПСЧ критикует власти за использование древних алгоритмов Excel для розыгрыша виз

Канадский эксперт по ГПСЧ критикует власти за использование древних алгоритмов Excel для розыгрыша виз - 1

Программа воссоединения семей (Family Reunification Program или Family sponsorship) — одна из трёх основных канадских программ помощи мигрантам. Она позволяет как недавно прибывшим иммигрантам, так и давно устоявшимся канадцам воссоединиться с членами своих семей. В соответствии с положениями об иммиграции и защите беженцев (Immigration and Refugee Protection Regulations), проживающие за рубежом семьи получают финансовую помощь, также как проживающие в Канаде родственники мигранта. На финансовую помощь могут рассчитывать супруги, дети, родители, внуки, усыновлённые дети и т. д.

Проблема в том, что Канада не может сразу предоставить гражданство всем родственникам всех мигрантов. Раньше их ставили в очередь, а рассмотрения заявки приходилось ожидать годами. Чтобы ускорить процесс, либералы предложили проводить лотерею. Так что с 2017 года в Канаде разыгрывается лотерея по типу американской Green Card. Среди примерно 100 000 заявок случайным образом выбирают 10 000. Благодаря официальному ответу на запрос по Закону доступа к информации [1] канадскому изданию The Globe an Mail стали известны некоторые технические детали [2], как проводится лотерея.

Оказывается, федеральное правительство выбирает победителей с помощью программы Microsoft Excel. Вот как выглядит вся процедура в деталях.

  • Шаг 1. Бюро по иммиграции, защите беженцев и гражданству (Immigration, Refugees and Citizenship Canada, IRCC) с помощью Microsoft Excel присваивает каждому заявлению номер по порядку.
  • Шаг 2. Каждому заявлению с порядковым номером присваивается случайный номер от 100 000 до 9 999 999 с помощью функции RANDOMBETWEEN в программе Microsoft Excel.
  • Шаг 3. Таблица Excel сортируется по колонке со случайными номерами от меньшего к большему — и выбирается 10 000 первых записей в качестве победителей лотереи.

Такая схема вызвала критику у некоторых специалистов. Известнейший эксперт по генерации случайных чисел профессор Пьер Л'Экюйе [3] (Pierre L’Ecuyer), из Монреальского университета, автор множества научных работ по ГСЧ, называет этот подход очень плохим: «Это очень старый генератор, его действительно нельзя назвать современным», — говорит он. Исследование профессора Л'Экюйе показало, что генератор псевдослучайных чисел Excel не проходит определённые статистические тесты. Хотя для данного применения его вполне достаточно, но ничего не мешает IRCC просто взять и использовать нормальный современный ГПСЧ.

Excel использует в качестве ГПСЧ математические алгоритмы с детерминированным результатом, которые зависят от одного начального числа (seed). В случае Excel это начальное значение создается автоматически приложением. Если знаете одно число на первом шаге, можно вычислить все остальные числа в последовательности. И нечто подобное случалось ранее, пишет канадская газета. В 1994 году IT-консультант Даниэль Корриво (Daniel Corriveau) обнаружил такой шаблон в игре Keno — и выиграл 600 тыс. CAD за один вечер в монреальском игорном заведении Casino de Montréal. Он трижды подряд угадал 19 из 20 выигрышных чисел [4].

Проведённое расследование показало, что в казино использовался такой же древний ГПСЧ, как в Excel. В начале каждого дня выбиралось одно случайное значение, а дальнейшие цифры в течение дня являлись числами из этой предсказуемой последовательности.

Тогда же в 1994 году профессор Л'Экюйе предложил [5] для детерминированных ГПСЧ структуру $(mathcal{S}, mu, f, mathcal{U}, g)$, где $mathcal{S}$ — это конечный набор состояний, $mu$ — вероятностное распределение в пространстве состояний $mathcal{S}$, используемое для выбора начального состояния $mathcal{s_{0}}$(seed), $f:mathcal{S}rightarrow mathcal{S}$ — функция перехода, $mathcal{U}$ — пространство выходных значений, $g:mathcal{S}rightarrow mathcal{U}$.

Обычно $mathcal{U}=(0,1)$, а состояние генератора задается рекуррентной формулой $s_{i}=f  (s_{i-1})$ для $i geq 1$. Выходное значение генератора $u_{i}=g  (s_{i}) in mathcal{U}$; $u_{0},  u_{1},  u_{2}  ...$ — последовательность псевдослучайных чисел. Это периодическая последовательность, а «периодом» называется минимальное положительное $j$.

Среди ГПСЧ наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью. Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1) и равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в пяти измерениях), а также быстрая генерация случайных чисел.

Профессор Л'Экюйе считает, что власти поступают очень глупо, используя ГПСЧ из Excel, ведь надёжные криптографические ГПСЧ легко доступны и ничего не стоят: «Криптографические генераторы бесплатны. Они есть в интернете, — сказал профессор. — Просто выберите один и всё. Это совсем не сложно».

Однако государственная комиссия IRCC, кажется, удовлетворена использованием Excel. В заявлении по электронной почте пресс-секретарь Шеннон Кер (Shannon Ker) написала: «Мы поддерживаем этот рандомизированный процесс отбора как достаточное средство равных возможностей для всех, кто хочет выразить заинтересованность в спонсировании своих родителей, бабушек и дедушек».

Автор: Анатолий Ализар

Источник [6]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/kriptografiya/282481

Ссылки в тексте:

[1] запрос по Закону доступа к информации: https://www.theglobeandmail.com/files/editorial/News/nw-na-immigration-procedure-0528/A-2017-19317.pdf

[2] некоторые технические детали: https://www.theglobeandmail.com/canada/article-anything-would-be-better-critics-warn-ottawas-family-reunification/

[3] Пьер Л'Экюйе: https://www.iro.umontreal.ca/~lecuyer/

[4] трижды подряд угадал 19 из 20 выигрышных чисел: http://www.blackjackforumonline.com/content/how_to_beat_keno.htm

[5] предложил: https://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB#%D0%94%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%93%D0%9F%D0%A1%D0%A7

[6] Источник: https://habr.com/post/413767/?utm_source=habrahabr&utm_medium=rss&utm_campaign=413767