Генераторы псевдослучайных последовательностей. Задания для дистанционного обучения.

Последнее изменение: 29/04/2020 19:17:25

1. Линейные конгруэнтные генераторы. (23.03.2020)

Упражнения.

1.1. Привести пример линейного конгруэнтного генератора X[n+1]=(aX[n]+c) mod 10 такого, что X[0] появляется в последовательности только один раз.

1.2. Привести пример линейного конгруэнтного генератора X[n+1]=(aX[n]+c) mod m такого, что X[0]=X[6].

1.3. Существуют ли a, c и m такие, что X[0]=X[3] для X[n+1]=(aX[n]+c) mod m и X[0]=X[2] для X[n+1]=(aX[n]-c) mod m. Если ответ положительный, привести пример. Дать обоснование в случае отрицательного ответа.

Литература.

Д. Кнут. Искусство программирования, Том 2. Вильямс, 2017. (Глава 3.2.1, 3.2.2)

Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Издательство Триумф, 2002. (Глава 16.1)

2. Регистры сдвига с линейной обратной связью. (06.04.2020)

Упражнения.

2.1. Построить пример 4-битового РСЛОС с периодом 4.

2.2. Чему равен период 4-битового РСЛОС, заданного начальными значениями b[0]=0, b[1]=1, b[2]=0, b[3]=1.

2.3. Чему равен период 4-битового РСЛОС Галуа, заданного начальными значениями b[0]=0, b[1]=1, b[2]=1, b[3]=1.

Литература.

Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Издательство Триумф, 2002. (Глава 16.2)

3. Потоковые шифры на основе РСЛОС. (13.04.2020)

Упражнения.

3.1. Построить пример генератора Геффе с периодом 7.

3.2. Построить пример обобщенного генератора Геффе с периодом 3.

3.3. Построить пример генератора "старт-стоп" Бета - Пайпера с периодом 4.

Литература.

Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Издательство Триумф, 2002. (Глава 16.3, 16.4)

4. Закрепление тем 1 и 2. (20.04.2020)

Упражнения.

4.1. Существует ли серия линейных конгруэнтных генераторов X[n+1]=(aX[n]+c) mod m (с фиксированными a, c и m) такая, что для любого значения X[0] последовательность чисел одна и та же (возможно, начинающаяся с разных позиций). Если существует, то привести пример. Если не существует, то дать обоснование.

4.2. Существует ли серия линейных конгруэнтных генераторов X[n+1]=(aX[n]+c) mod m (с фиксированными a, c и m) такая, что для всех значений X[0] последовательности чисел различны. Если существует, то привести пример. Если не существует, то дать обоснование.

4.3. Существует ли набор начальных значений b[0], b[1], b[2], b[3] 4-битового РСЛОС такой, что для всех топологий отводов генерируется одна и та же последовательность чисел. Если существует, то привести пример. Если не существует, то дать обоснование.

5. Аддитивные генераторы. (27.04.2020)

Упражнения.

5.1. Привести пример аддитивного генератора с периодом строго меньше 2^n-1.

5.2. Для указанных Б. Шнайером генераторов А и В привести пример ключа, обеспечивающего один и тот же результат шифрования для Fish и Mush.

5.3. В книге Б. Шнайера утверждается, что генератор Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия. Представить объяснение этому факту (учитывая, что количество действий всегда целое).

Литература.

Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Издательство Триумф, 2002. (Глава 16.9)

6.1. Множественные рекурсивные генераторы (Multiple recursive generators).

Упражнения.

6.1.1. Привести пример множественного рекурсивного генератора (m=3, k=4) такого, что X[0] появляется в последовательности только один раз.

6.1.2. Привести пример множественного рекурсивного генератора (m=3, k=4) такого, что X[0]=X[6].

Литература.

Christophe Dutang and Diethelm Wuertz. A note on random number generation, 2009. (пункт 2.1.2.)

6.2. Вихрь Мерсенна

Упражнения.

6.2.1. Существует ли вихрь Мерсенна с периодом 3? Если существует, то привести пример. Если - нет, то дать обоснование.

Литература.

Christophe Dutang and Diethelm Wuertz. A note on random number generation, 2009. (пункт 2.1.3.)

7. Алгоритм М.

Упражнения.

7.1. Пусть X[n] - последовательность чисел, полученная при помощи алгоритма М, где prngA - линейный конгруэнтный генератор Y[n+1]=(3Y[n]+2) mod 5 такой, что Y[0]=1, prngB - линейный конгруэнтный генератор Z[n+1]=(2Z[n]+1) mod 3 такой, что Z[0]=2. Найти X[4].

7.2. Пусть X[n] - последовательность чисел, полученная при помощи алгоритма М, где prngA - линейный конгруэнтный генератор Y[n+1]=(aY[n]+b) mod m такой, что Y[0]=1, prngB - линейный конгруэнтный генератор Z[n+1]=(cZ[n]+d) mod n такой, что Z[0]=1. Существуют ли значения a, b, m, c, d, n такие, что все энементы последовательности X[n] попарно различны.

7.3. Пусть X[n] - последовательность чисел, полученная при помощи алгоритма М, где prngA - линейный конгруэнтный генератор Y[n+1]=(aY[n]+b) mod m такой, что Y[0]=1, prngB - линейный конгруэнтный генератор Z[n+1]=(cZ[n]+d) mod n такой, что Z[0]=1. Существуют ли значения a, b, m, c, d, n такие, что X[2]=X[3], а остальные энементы последовательности X[n] попарно различны.

Литература.

Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Издательство Триумф, 2002. (Глава 16.11)