Псевдослучайность

Случайности не случайны кто такие семейства псевдослучайных функций (PRFs)

07.12.2020 02:05:58 |

Автор: admin

В 1984 году Голдрайх, Голдвассер и Микали в своей статье формализовали концепцию псевдослучайных функций и предложили реализацию PRF, основанную на псевдослучайном генераторе (PRG) с удвоением длины. С тех пор псевдослучайные функции показали себя чрезвычайно важной абстракцией, которая нашла применение в различных сферах, например, в аутентификации сообщений и в доказательствах теорем. В этой статье я расскажу:

Что из себя представляют случайные функции (RF)
Что из себя представляют псевдослучайные функции (PRF)
Кто же такие эти ваши семейства
PRF vs. PRG
При чём тут блочные шифры

Случайность

Уже из названия становится понятно, что псевдослучайная функция это нечто выглядящее как случайная функция. Ну а что такое случайная функция в нашем случае? Для начала ограничим нашу область рассмотрения функциями отображающими строку из нулей и единиц длиной в строку из нулей и единиц такой же длины , то есть

$\underbrace{1110...0010}_{n} \rightarrow \underbrace{0100...0011}_{n} \Leftrightarrow \{0,1\}^n \rightarrow \{0,1\}^n$

Этого, вообще говоря, можно и не делать, и рассматривать отображения строк одной длины в строки другой длины, но в этом случае придётся уделять внимание различиям в размерности. Далее введём множество всех функций, выполняющих отображение $\{0,1\}^n \rightarrow \{0,1\}^n$ и обозначим его $\text{Func}_n$ .

Рассмотрим мощность этого множества. Очевидно, что $|{\text{Func}_n}| = 2^{n2^n}$ .

Если всё-таки не очевидно

$\text{Всего различных строк длины } n \space - \space 2^n.$ $\text{ Чтобы хранить } 2^n \text{ строк понадобится } n2^n \text{ бит.}$ $\text{Эти } n2^{n} \text{ бит и будут задавать искомое отображение } 2^n \text{ строк.}$ $\text{И всего таких отображений будет } 2^{n2^n}.$

Теперь мы можем определить случайную функцию. Случайная функция это любая случайно выбранная функция из $\text{Func}_n$ . Проще говоря, мы берём наши 2^n строк и каждой сопоставляем какую-то из тех же 2^n строк. Причем сопоставление происходит с равномерным распределением, то есть

$P(f(x)=y_0)=2^{-n}$

Где функция из $\text{Func}_n$ , а y_0 фиксированная точка.

Псевдослучайность

Интуитивно, псевдослучайность это что-то выглядящее, как случайность. И формальное определение так и вводится, только похожесть псевдослучайной функции на случайную определяется строго.

Давайте выпишем несколько равенств, верных для случайной функции:

$P(f(x) \in \{ \forall y:первый \space бит = 1 \}) = \frac{1}{2}$

Почти то же самое, но для наших целей вполне сгодится:

$P(f(x) \in \{ \forall y:последний \space бит = 1 \}) = \frac{1}{2}$

Для чётных можно выписать следующее:

$P(f(x) \in \{ \forall y:число \space нулей= число \space единиц \}) = \frac{1}{2^n} \begin{pmatrix} n \\ n/2 \end{pmatrix}$

Где $\begin{pmatrix} n \\ n/2 \end{pmatrix}$ число сочетаний из по n/2 (нужно выбрать n/2 позиций из возможных).

Подобных равенств можно выписать очень много. Скажем, к примеру, что мы придумали 20 таких равенств. Назовём их тестами и обозначим следующим образом:

Тогда можно определить псевдослучайною функцию, как функцию, которая удовлетворяет тестам с заданной точностью $\varepsilon$ :

$|P(A_i(f(x))=1)-P(A_i(F(x))=1)| < \varepsilon$

Где f(x) случайная функция, а F(x) функция, которую мы тестируем.

Но у такого определения есть существенный минус. Что если у кул-хацкера, который пытается вытащить полезную информацию из результата работы псевдослучайной функции, есть тест, которого нет у нас? Вероятно, для него эта функция окажется не такой уж и случайной. Поэтому введём несколько иное определение псевдослучайной функции.

Назовём функцию $(t,\varepsilon)$ -псевдослучайной, если для любого теста с полиномиальной сложностью, выполнение которого занимает времени не более чем верно

$|P(A(f(x))=1)-P(A(F(x))=1)| < \varepsilon$

Семейства

Окей, мы поняли, что такое случайная функция, что такое псевдослучайная функция, но никаких семейств так и не видно. На самом деле они уже здесь, нам достаточно взять некоторое количество псевдослучайных функций, удовлетворяющих нашим условиям, обозвать их F_k и семейство готово:

Семейство псевдослучайных функций это эффективно вычислимая функция двух переменных F_k(x)=F(k,x) , такая, что $\{0,1\}^m \times \{0,1\}^n \rightarrow \{0,1\}^l$ , где каждая из F_k является псевдослучайной. Переменная называется ключом функции.

Положим далее m=l=n .

Стоит отметить, что выбор конкретного эквивалентен выбору конкретной функции из семейства.

В начале статьи мы обсудили множество всех функций выполняющих отображение $\{0,1\}^n \rightarrow \{0,1\}^n$ и обозначили его $\text{Func}_n$ . Так вот, получается что семейство F_k задаёт распределение над множеством $\text{Func}_n$ .

Определение, данное выше, можно переформулировать в более привычный вид, в котором оно в основном встречается в статьях и учебниках:

F_k называется семейством псевдослучайных функций, если для случайного ни один эффективный алгоритм с полиномиальной временной сложностью не сможет отличить F_k от $f \in \text{Func}_n$ .

Наглядное пояснение

Вероятно, так будет проще осознать, что же в конечном итоге представляет из себя это семейство. Пусть есть две черных коробки, которые могут принимать на вход битовые строки и в ответ выдавать какие-то другие битовые строки. Примем, что на входе и на выходе коробок строки имеют определённую одинаковую длину. Отмечу, что выход этих коробок определяется только строкой на входе. То есть не может быть такого, что мы подали на вход какой-то коробки x_0 и на выходе получили y_0 , а потом, через некоторое время, мы снова подали на вход x_0 , но на выходе получили $y_1 \neq y_0$ . Пусть также есть злой хацкер, которому позарез нужно понять, какая из этих двух коробок скрывает в себе труЪ-случайную функцию, а какая просто притворяется. Этот хацкер может делать с этими коробками всё, что угодно. То есть подавать строки и считывать. Так вот, если тот, кто придумывал F_k , сделал всё правильно, то при случайно выбранном у хацкера ничего не выйдет (за вменяемое время).

PRF vs. PRG

PRG это псевдослучайный генератор. Звучат названия достаточно похоже, но путать их не стоит. Эти два понятия можно связать, получив из PRG PRF, а из PRF PRG. Почитать подробно, что такое PRG, можно тут. Если вкратце, то PRG это эффективно вычислимая функция (алгоритм), принимающая на вход случайную битовую строку длины (seed) и выдающая псевдослучайную битовую строку длины m>n . Почитать про то, как получить из PRG семейство псевдослучайных функций с доказательством того, что полученная конструкция действительно PRF можно в работе, упомянутой в самом начале статьи. А вот в обратную сторону всё намного проще. Достаточно положить

Где операция конкатенации, и мы получим простейший пример получения PRG из PRF. Очевидно, что подобных примеров можно придумать очень много. Отсюда напрашивается логичный вывод, что PRF понятие более мощное, нежели PRG.

Про блочные шифры

Наделив нашу PRF F_k парой дополнительных свойств мы получим ещё одну интересную абстракцию, называемою псевдослучайными перестановками. Для того, чтобы стать семейством псевдослучайных перестановок, F_k должна быть биективной и эффективно вычислимой в обоих направлениях для всех значений . То есть задача вычисления $F^{-1}(y)$ должна иметь единственный верный ответ и не должна составлять для нас особого труда.

Здесь уже можно догадаться, причём же тут блочные шифры. По сути, псевдослучайная перестановка представляет из себя ядро блочного шифра: мы берём исходное сообщение, разбиваем его на блоки длины , применяем к каждому из блоков F_k , где известно и отправителю и получателю, и затем отправляем наше сообщение, которое на данном этапе выглядит как набор случайных (псевдослучайных) битов.

В качестве примера блочного шифра, использующего псевдослучайные перестановки, можно привести AES.

Конец

На этом я закончу свою статью. Спасибо большое всем, кто дочитал.

P.S. Случайности не случайны. Случайностей вообще нет, развитие вселенной было определено ещё на момент её появления. Не воспринимайте это в серьёз, пожалуйста c:

P.P.S. Кто нашёл пасхалку большой молодец.

Материалы

How to Construct Random Functions тык

Pseudorandom Functions: Three Decades Later тык

Introduction to Modern Cryptography тык

Pseudorandom Functions and Block Ciphers тык

Подробнее..

Категории: Информационная безопасность , Научно-популярное , Математика , Случайность , Псевдослучайность , Блочный шифр , Псевдослучайные генераторы

Blum-Blum-Shub generator и его применение

23.12.2020 20:04:15 |

Автор: admin

Введение

В настоящее время случайные числа используются в различных областях науки. Например, для моделирования различных реальных процессов зачастую нужно учитывать не только поведение исследуемой величины, но и влияние различных непредсказуемых явлений. Кроме того, в некоторых методах анализа данных, полученных в результате эксперимента, также используются случайные числа. В теории игр случайность также играет большую роль. Ну и конечно в криптографии. Многие алгоритмы шифрования или электронной подписи используют случайные числа.

Но как же получить случайное число? В природе существует много различных случайных явлений, на основе которых придумали генераторы. Аппаратные генераторы случайных чисел могут быть основаны на макроскопических случайных процессах с использованием таких предметов, как монетка, игральная кость или колесо рулетки. Но такие генераторы являются очень медленными и не подходят для решения задач. Для более быстрого получения случайных чисел могут использоваться физические явления, имеющие квантовую природу, например шум в электрических цепях. Но главным минусом аппаратных генераторов случайных чисел является их ненадежность, связанная с частыми сбоями в работе. Чтобы избежать ненадежности, стали использовать заранее полученные таблицы случайных чисел. Однако и они имели большой минус - занимали много памяти.

Так как ни аппаратный метод, ни таблицы случайных чисел не удовлетворяли потребность в быстром и надежном получении случайных чисел, ученые начали искать алгоритмические методы получения случайных чисел. Очевидно, что полученная в результате таких методов последовательность уже не является случайной, так как полностью определяется некоторой формулой и начальными данными. Но если начальное значение хранится в секрете, а алгоритм стойкий (стойким считается алгоритм, успешная атака на который требует от атакующего обладания недостижимым на практике объёмом вычислительных ресурсов), то результаты, которые выдает генератор будут непредсказуемыми. Такой алгоритм получения последовательности чисел, свойства которой аппроксимируют последовательность случайных чисел, называют генератором псевдослучайных чисел.

Один из таких генераторов - генератор BBS (Blum-Blum-Shub generator) - и будет рассмотрен в этой статье.

Основные определения

Для описания генератора BBS понадобятся следующие понятия:

Случайное число - число, представляющее собой реализацию случайной величины
Детерминированный алгоритм алгоритм, который возвращает те же выходные значения при тех же входных значениях
Псевдослучайное число число, полученное детерминированным алгоритмом, используемое в качестве случайного числа
Генератор псевдослучайных бит (ГПСБ) - детерминированный алгоритм, который получает на вход бинарную последовательность длины n и выдает на выходе бинарную последовательность длины l(n), которая кажется случайной. Входное значение ГПСБ называется начальным вектором, а выход называется псевдослучайной последовательностью бит

Поясним, что же такое кажется случайной. В данном случае это означает, что последовательность, сгенерированная ГПСБ, не является случайной, однако она неотличима от истинно случайной последовательности такой же длины. Ниже приведем два определения криптографической безопасности генератора, а затем покажем, что они эквивалентны.
Целое число x из мультипликативной группы по модулю n называется квадратичным вычетом по модулю n, если существует такое y, что $y^2 \equiv x \ mod \ n$ . В противном случае x - квадратичный невычет по модулю n.
Простое число p такое, что $p \equiv 3 \ mod \ 4$ , называется простым числом Блюма.

Следующие 2 определения являются эквивалентными:

Говорят, что ГПСБ проходит все полиномиальные по времени статистические тесты, и поэтому может рассматриваться как криптографически безопасный ГПСБ, если никакой полиномиальный по времени алгоритм не может различить выходную последовательность генератора и истинно случайную последовательность с вероятностью превышающей 1/2.
Говорят, ГПСБ проходит битовый тест, если нет полиномиального по времени алгоритма, который на основе первых rl(n)1 бит выходной последовательности sможет предсказать (r+1)-ый бит s с вероятностью большей1/2.

Алгоритм работы генератора BBS (Blum-Blum-Shub generator)

Генерируем два различных простых больших числа Блюма p и q
$n := p \cdot q$
Генерируем случайное число $s \in Z_n^*$ (мультипликативная группа по модулю n)
$x_0 := s^2 \ mod \ n$
Последовательность определяется как $x_i := x_{i-1}^2 \ mod \ n$ и $b_i := x_i \ mod \ 2$
Последовательность на выходе:

Приведу пример работы данного алгоритма:

Пусть $n = p \cdot q = 7 \cdot 19 = 133$ и s = 100 . Тогда мы имеем $x_0 = 100^2 \equiv 25 \ mod \ 133$ . Получаем последовательность: $x_1 = 25^2 \equiv 93 \ mod \ 133$ и $b_1 = 93 \equiv 1 \ mod \ 2$ , $x_2 = 93^2 \equiv 4 \ mod \ 133$ и $b_2 = 4 \equiv 0 \ mod \ 2$ , $x_3 = 4^2 = 16 \ mod \ 133$ и $b_3 = 16 \equiv 0 \ mod \ 2$ , $x_4 = 16^2 \equiv 123 \ mod \ 133$ и $b_4 = 123 \equiv 1 \ mod \ 2$

На выходе получили последовательность 1,0,0,1.

Последовательность, полученная на выходе генератора BBS, является периодичной, причем период равен $\lambda (\lambda (x))$ , где $\lambda(n) = \{\min{m}: a^m \equiv 1 \mod n \}$ - функция Кармайкла.

Интересной особенностью генератора BBS является то, что при знании разложения числа n на множители он допускает эффективное прямое определение любого бита последовательности. Равенство

позволяет рационально вычислить i-ый элемент последовательности, если даны x_0 , n, $\lambda(n)$ .

Безопасность генератора BBS

Криптографически стойким считается алгоритм, успешная атака на который требует от атакующего обладания недостижимым на практике объёмом вычислительных ресурсов или перехваченных открытых и зашифрованных сообщений либо настолько значительных затрат времени на раскрытие, что к его моменту защищённая информация утратит свою актуальность.

Криптографическая стойкость генератора BBS основана на проблеме определения квадратичного вычета, которая формулируется следующим образом:

Задача определения квадратичного вычета состоит в том, чтобы решить является ли $x \in Z_n^*$ квадратичным вычетом или нет.
- алгоритм, который решает эту задачу, выдает 1 тогда и только тогда, когда x является квадратичным вычетом и 0 в противном случае.

Решение данной задачи является вычислительно сложной задачей.

В своей статье изобретатели генератора доказали, что ГПСБ BBS является непредсказуемым (криптографически стойким) генератором.

Применение

В статье Выборновой Ю.Д приведено исследование средней скорости работы различных реализаций генератора BBS. Было получено, что скорость работы данного генератора во много раз ниже скорости работы современных симметричных алгоритмов блочного шифрования. Генератор BBS сравнивался с алгоритмами блочного шифрования, потому что алгоритмы блочного шифрования используются для построения криптографически стойких генераторов псевдослучайных последовательностей

Из этого следует, что данный алгоритм может использоваться только для генерации данных, если необходима непредсказуемость и криптографическая стойкость, а скорость генерации не имеет не имеет значения. А именно: для генерации ключей в асимметричных системах, таких как RSA, в качестве генератора имитовставки (средство обеспечения имитозащиты в протоколах аутентификации с доверяющими друг другу участниками), генератора ключей для имитовставки, а также в некоторых реализациях криптографических протоколов аутентификации и шифрования. Однако, стоит заметить, что низкая скорость не всегда является недостатком. В криптографии существуют задачи, в которых специально используются медленные алгоритмы. Одной из таких задач является генерация ключа на основе пароля.

Рассмотрим более подробно задачу генерации ключа на основе пароля. Пароль это строка символов, которая используется для аутентификации пользователя и предоставления ему доступа к системе. Чаще всего пароли выбираются пользователями. Поскольку большинство самостоятельно выбранных пользователями недостаточно случайны, такие пароли не рекомендуется использовать непосредственно в качестве криптографических ключей. Однако, во многих системах при защите данных в устройствах хранения пароль может быть единственным способом защиты. Следовательно, во избежание атак на такие системы необходимо применение дополнительных мер по их защите.

Функция генерации ключа на основе пароля (Password-Based Key Derivation Function, PBKDF) это детерминированный алгоритм, который применяется для получения криптографической ключевой информации из какого-либо секретного значения. Таким образом, такая функция позволяет из легко запоминающегося пароля пользователя получить криптографически стойкий ключ заданной длины, называемый мастер-ключом.

В основе алгоритма PBKDF лежит псевдослучайная функция. Обозначим ее PRF. На вход подается число С, которое определяет, сколько раз нужно запустить псевдослучайную функцию. Также на вход подается пароль Р , соль S - не секретная строка символов, уникальная для каждого пароля, и желаемая длина мастер-ключа MK_Length.

Обозначим мастер-ключ MK , тогда $MK = PBKDF_{(PRF, C)}(P, S, MK \_ Length)$

Благодаря применению уникальной соли для каждого пользователя, даже если несколько пользователей при регистрации ввели одинаковый пароль, значение ключа в базе будет разным, и злоумышленник не сможет догадаться, у каких пользователей пароли совпадают. То есть основное назначение соли - сделать возможной генерацию большого количества ключей для каждого пароля при фиксированном C. Для каждого пароля число возможных ключей составит $2^{Salt \_ Length}$ , где Salt_Length - длина соли в битах.

Разработанный алгоритм генерации ключа на основе пароля имеет следующий вид:

Холостыми назовем первые Dummy _ Bits _ Number бит, порожденных генератором BBS, которые не будут учитываться при создании мастер-ключа. Полезными назовем те биты, порожденные генератором BBS, которые будут принимать участие в генерации ключа. Мастер-ключ будем генерировать блоками. Общее количество блоков обозначимa.

Создадим два временных массива T и U и для каждого блока i выполним следующее: обнулим ячейку T_i , в U_0 запишем результат конкатенации соли S и номера блока i, переведенного в бинарный вид функцией Binary(). Затем будем запускать BBS генератор и складывать результат со значением T_i пока не обнулится счетчик итераций C. Мастер-ключ является результатом конкатенации всех блоков. Последний блок заменяется на первые r бит этого блока.

Заключение

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

Источники

Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.
Pascal Junod, Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator, August 1999
Слеповичев И.И.; ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНХ ЧИСЕЛ, 2017
A. C. Yao. Theory and application of trapdoor functions. In Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 8091, Chicago, 1982. IEEE.
M. Blum and S. Micali. How to generate cryptographically strong se- quences of pseudo-random bits. SIAM J. Computing, 13(4):850863, November 1984.
Lenore Blum, Manuel Blum, and Michael Shub. Comparison of two pseudo-random number generators. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 6178, New York, 1983. Plenum Press.
A. J. (Alfred J.) Menezes, Paul C. Van Oorschot, and Scott A. Van- stone. Handbook of applied cryptography. The CRC Press series on discrete mathematics and its applications. CRC Press, 2000 N.W. Cor- porate Blvd., Boca Raton, FL 33431-9868, USA, 1997.
E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.
S. Goldwasser and S. Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proc. 14th ACM Symp. on Theory of Computing, pages 365377, San Francisco, 1982. ACM.
Выборнова, Ю.Д. Реализация генератора Blum-Blum-Shub и исследование его основных характеристик / Ю.Д. Выборнова // IN SITU.
Брассар, Дж. Современная криптология / Дж. Брассар. Москва: Полимед, 1999. 107 с.
Ю.Д. Выборнова, Разработка функции генерации ключа на основе пароля в качестве приложения генератора Blum-Blum-Shub, Новая техника, 2017
Turan, M. Recommendation for password-based key derivation / M. Turan, E. Barker, W. Burr, L. Chen NIST, 2010. 18 p.

Подробнее..

Категории: Информационная безопасность , Безопасность , Криптография , Генератор , Псевдослучайность , Генерация ключей

Тестирование псевдослучайной последовательностью

14.01.2021 20:16:39 |

Автор: admin

Как конечные пользователи канала связи мы должны были принять участие в испытаниях доработанной системы связи. Собственно говоря, наше участие было простое принести ноутбук и блок сопряжения, подключить к системе и непрерывно выдавать из компьютера любые информационные кадры как некоторую полезную нагрузку.

Разработчики должны были гонять систему в разных режимах, а затем телеметристы выдать нам принятый массив данных. После этого мы должны были проверить контрольные суммы (пардон, циклически избыточный код) каждого кадра и, если найдем ошибки, внести их число в протокол испытаний.

Поэтому надо было подготовить простую программу (в смысле ПО) для испытаний. И встал вопрос, что выдавать в качестве информации? Решили все-таки не тривиальную решетку AA55, а псевдослучайную последовательность с помощью примитивного полинома Галуа.

Алгоритм там действительно очень простой:

;---- ВДАЧА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ----ПСП:  MOV       EBX,ЗНАЧЕНИЕ   ;ПЕРВОНАЧАЛЬНО ВСЕ ЕДИНИЦ      MOV       CX,ДЛИНА_ПСП   ;НОМЕРА ОТВОДОВ ОБРАТНОЙ СВЯЗИ;---- ВСТАВЛЯЕМ ПОЗИЦИЮ ОТВОДА ОБРАТНОЙ СВЯЗИ ----M1:   MOV       EAX,1      XCHG      CH,CL      SHL       EAX,CL      XCHG      CH,CL;---- ОБРАБАТВАЕМ ОЧЕРЕДНОЙ БИТ ----      ROR       EBX,1      JNB       M2;---- ОЧЕРЕДНОЙ БИТ - ЕДИНИЦА ----      AND       EAX,EBX ;ВДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ      MOV       EAX,1      JNZ       @      SHL       EAX,CL      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСВАЕМ 1      JMPS      M4@:    SHL       EAX,CL      NOT       EAX      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСВАЕМ 0      JMPS      M4;---- ОЧЕРЕДНОЙ БИТ - НОЛЬ ----M2:   AND       EAX,EBX ;ВДЕЛЯЕМ СИГНАЛ ОБРАТНОЙ СВЯЗИ      MOV       EAX,1      JZ        @      SHL       EAX,CL      OR        EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=1, ДОПИСВАЕМ 1      JMPS      M3@:    SHL       EAX,CL      NOT       EAX      AND       EBX,EAX ;ЕСЛИ ОБРАТНАЯ СВЯЗЬ=0, ДОПИСВАЕМ 0;---- ВДАЧА НУЛЯ ----M3:  CLC     RCR       БАЙТ,1     JMPS      @;---- ВДАЧА ЕДИНИЦ ----M4:  STC     RCR       БАЙТ,1;---- ВДАЧА ОЧЕРЕДНОГО БАЙТА ПСП ----@:   DEC       БИТ    ;БАЙТ ЕЩЕ НЕ КОНЧИЛСЯ ?     JNZ       M1     MOV       БИТ,8  ;ОПЯТЬ 8 БИТ     MOV       ЗНАЧЕНИЕ,EBX ;ДЛЯ ПРОДОЛЖЕНИЯ ПСП     MOV       AL,БАЙТ ;ВДАЛИ ОЧЕРЕДНОЙ БАЙТ ПСП     RET

Эта подпрограмма выдает все возможные комбинации нулей и единиц (кроме комбинации из одних нулей) заданной длины в псевдослучайном порядке. В нашем случае для длины 32 бит получается полмиллиарда псевдослучайных байт до повторения данной последовательности заново. Очень просто и красиво.

Поскольку испытания были долгие, их разбили на 2 дня. В первый день мы подключили ноутбук и ушли, так как во время собственно испытаний нам делать нечего. Вечером обработали принятые данные, все в порядке.

Второй день испытаний. Опять все подключили и уже собирались уйти, как вдруг по громкоговорящей из аппаратной доклад: сигнал полезной нагрузки пропал!

Что за черт? Да тут всего один кабель в систему уходит. Перезапустили программу. Опять доклад: сигнал исчез. Полчаса, час пытаемся что-то исправить, хотя попытки большей частью сводятся к хождению вокруг стола с компьютером и пожиманию плечами.

Все повторяется: при включении компьютера аппаратная заявляет, что видит несущую (а это что? Нет у нас никакой несущей!), затем запускаем собственно программу и сигнал опять пропадает. Вдруг через час в переговоры с аппаратной вмешивается телеметрист: да нет никакого пропадания сигнала! Я все нормально принимаю, как и вчера.

Фу-ты, ну-ты. Вчера же действительно все было нормально!

Начинаем разбираться.

Оказывается, вчера в аппаратной дежурил молодой специалист. Его спросили, есть сигнал полезной нагрузки? Он глянул на осциллограф а там бежит наша шумоподобная псевдослучайная последовательность. Он же не знает, как должен выглядеть сигнал, поэтому спокойно докладывает: да, есть.

А сегодня дежурит опытный человек, много раз проводивший испытания. Но вот таких сигналов полезной нагрузки ему, похоже, никогда не давали. Включаем компьютер он докладывает, что видит несущую (это на самом деле выдача одних нулей). А когда программа начинает выдавать псевдослучайную последовательность, он вместо доклада вижу шумоподобный сигнал сразу делает ложный вывод: сигнал исчез, белый шум.

Таким образом, получилось не только тестирование канала связи псевдослучайной последовательностью, но и случайное тестирование самой псевдослучайной последовательности, убедительно подтвердившее ее случайность, ведь вполне опытный человек не смог отличить ее от белого шума.

Это заставило задуматься о математике вообще и о необычных людях, двигавших ее (а, заодно, и развитие всей науки) вперед. Мы использовали полином Галуа. Всего 20 лет жизни Эвариста Галуа и 4 года его занятие математикой оставили такое наследие, которым мы, не задумываясь, пользуемся до сих пор.

Конечно, работы Галуа появились не на пустом месте. Можно сказать, что он принял знамя из рук Нильса Абеля, тоже обидно рано ушедшего из жизни. И после нелепой смерти Галуа, на дуэли, да еще при мутных обстоятельствах, развитие математики, конечно, не остановилось. Например, уже через двадцать лет появились полиномы Чебышева, которыми мы пользуемся каждый раз, когда с помощью FPU считаем триногометрические функции.

Но все-таки личность математика тоже играет важную роль. Еще в античности философы, а заодно и математики, рассказывали друг другу шутку-софизм про Ахиллеса и черепаху. При этом они находились в шаге от великого математического открытия: сумма бесконечного числового ряда может быть конечной. Но тогда рядом не оказалось мальчишки со свежим взглядом, вроде Галуа, который бы вместо идиотского вывода Ахиллес никогда не догонит черепаху, сделал бы шаг в правильном направлении: Ахиллес никогда не догонит черепаху за заданное время, за первую секунду, но за вторую уже перегонит - значит, несмотря на бесконечное деление времени на части, сумма этих бесконечных частей конечна! Такого математика тогда не нашлось и ряды (которые мы не совсем правомерно называем рядами Тейлора) отодвинулись на тысячи лет.

Если бы Галуа не погиб в юном возрасте, сколько бы еще открытий мог бы сделать. А если бы он с Чарльзом Бэббиджем бы встретился, ну или бы с Адой Лавлейс, возможно, жили бы мы сейчас совсем в другом компьютерном мире

Подробнее..

Категории: Алгоритмы , Читальный зал , История it , Юмор , Псевдослучайность , Галуа

	Русский
	English

Псевдослучайность

Случайности не случайны кто такие семейства псевдослучайных функций (PRFs)

Случайность

Псевдослучайность

Семейства

Наглядное пояснение

PRF vs. PRG

Про блочные шифры

Конец

Blum-Blum-Shub generator и его применение

Введение

Основные определения

Алгоритм работы генератора BBS (Blum-Blum-Shub generator)

Безопасность генератора BBS

Применение

Заключение

Источники

Тестирование псевдослучайной последовательностью

Категории

Последние комментарии