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

в 6:50, , рубрики: Excel, ГПСЧ, Канада, криптография

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

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

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

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

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

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

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

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

Тогда же в 1994 году профессор Л'Экюйе предложил для детерминированных ГПСЧ структуру $(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) написала: «Мы поддерживаем этот рандомизированный процесс отбора как достаточное средство равных возможностей для всех, кто хочет выразить заинтересованность в спонсировании своих родителей, бабушек и дедушек».

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

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js