Лабораторный практикум. 
Криптографические методы защиты информации

Лабораторная работа 2.1 Генерация псевдослучайных чисел

Задание

Изучить процедуру генерации случайных чисел методом Блюм — Блюма — Шуба.

Технология выполнения задания

Задание 1. Сгенерировать 8-битовую псевдослучайную последовательность.

1. Выбрать значения параметров BBS-генератора р, q и случайное число s из табл. 2.26 согласно номеру варианта (от 1 до 5). Сформировать псевдослучайную последовательность аналогично рассмотренному ниже примеру.

Таблица 2.26

Варианты задания.

Пример 2.13.

Заданы параметры BBS-генератора р = 407, q = 599, выбрано случайное число s = 3612. Сформировать псевдослучайную 8-битовую последовательность, используя один младший бит чисел «г., формируемых BBS-генератором.

2. В приложении MS Excel создать новую книгу, на первом листе ввести значения р, q, вычислить число Блюма п как их произведение, например =В1*В2 (рис. 2.66). Ниже ввести значение случайного числа х.

Рис. 2.66. Вычисление последовательности x_t BBS-генератора.

• 3. Рассчитать элементы ряда х'.
• • пронумеровать ячейки первого столбца от 0 до 7;
• • в первую ячейку второго столбца ввести формулу для вычисления х₀ по формуле х₀ = s'² mod и, например =ОСТАТ (В4^Л2;$В$ 3) (см. рис. 2.66);
• • скопировать формулу на весь ряд.
• 4. Вычислить младшие биты чисел х_г Значение младшего бита определяется остатком от деления числа на 2, поэтому для вычисления можно использовать функцию ОСТАТ (рис. 2.67), например =ОСТАТ (В5;2) для числа х₀. Скопировать формулу на все ячейки диапазона.

Рис. 2.67. Вычисление значений младших битов.

5. Сформировать результирующую битовую псевдослучайную последовательность с помощью операции &, например =С5&С6&С7&С8&С9&С10& С11&С12, или функции СЦЕПИТЬ из группы Текстовые, например =СЦЕПИТЬ (С5;С6;С7;С8;С9;С10;С11;С12). Значение результирующей последовательности: 11 101 111 (см. рис. 2.67).

Задание 2. Расшифровать криптограмму, полученную наложением на шифруемый текст псевдослучайной последовательности, сформированной эффективной реализацией BBS-генератора.

6. Выбрать из табл. 2.27 согласно номеру варианта (от 1 до 5) значения числа Блюма п, секретного ключа — случайного числа s и шифротекста, представленного последовательностью ASCII-кодов символов. Провести расшифрование (получить открытый текст) аналогично рассмотренному ниже примеру.

Таблица 2.27

Варианты задания.

Пример 2.13.

С помощью BBS-генератора получена псевдослучайная последовательность, которая затем наложена на открытый текст. Известно, что использована аффективная реализация BBS-генератора, т. е. при формировании псевдослучайной последовательности используется максимально возможное число младших битов чисел Хр не нарушающее стойкости последовательности. Известны числа Блюма п = 243 793 и случайное число s = 48 914, использованные для генерации. Требуется расшифровать текст, заданный последовательностью ASCII-кодов: 16, 182,219, 83.

7. Занести значения п и s на лист MS Excel, ниже в столбец занести значения ASCII-кодов, составляющих криптограмму (рис. 2.68). Перевести десятичные значения ASCII-кодов в двоичный вид, используя функцию ДЕС.В.ДВ из группы Инженерные. Поскольку символы в таблице ASCII кодируются одним байтом (восемью битами), указать разрядность 8. Например, =ДЕС.В.ДВ (А4;8).

Рис. 2.68. Перевод десятичных кодов в двоичный вид.

• 8. Ниже с помощью операции & или функции СЦЕПИТЬ (например, =СЦЕПИТЬ (В4;В5;В6;В7)) сформировать соответствующую шифротексту битовую последовательность (см. рис. 2.68).
• 9. Определить максимально допустимое для использования в BBS-генераторе число младших битов (рис. 2.69):
  • • определить минимальное число битов, необходимое для кодирования п. Рядом со значением п вычислить двоичный логарифм значения п + 1. Для этого следует использовать функцию LOG, задав значение второго параметра равным двум, например =LOG (Bl+l;2). Получено значение 17,8953;
  • • округлить полученное значение вверх до целого, для чего следует использовать функцию ОКРУГЛВВЕРХ, задав число десятичных разрядов равным нулю, например =ОКРУГЛВВЕРХ (С1;0). Получено значение 18;

Рис. 2.69. Расчет максимально допустимого числа младших битов таким образом, для кодирования числа п = 243 793 требуется не менее 18 двоичных разрядов.

Замечание: округление вверх можно произвести также с помощью функций ОКРВВЕРХ или ОКРВВЕРХ. ТОЧН, в этом случае значение второго параметра (точность) следует установить равным единице;

• • взять двоичный логарифм от полученного значения, например =LOG (Dl;2). Получено значение 4,1699;
• • округлить полученное значение вниз с помощью функции О КРУГЛ ВНИЗ, задав число десятичных разрядов равным нулю, например =ОКРУГЛВНИЗ (Е1;0). Получено значение «4», таким образом, в BBS-генераторе допустимо использовать не более четырех младших битов.

Замечание: округление вниз можно также произвести с помощью функций ОКРВНИЗ или ОКРВНИЗ. ТОЧН, в этом случае значение второго параметра (точность) следует установить равным единице.

• 10. С помощью BBS-генератора сформировать псевдослучайную последовательность, которая была использована при шифровании. Это возможно, поскольку секретный параметр s известен:
  • • определить число членов ряда Х-, необходимых для формирования псевдослучайной последовательности достаточной для шифрования/рас — шифрования длины. Для этого число ASCII-кодов, задающих шифротскст, следует умножить на 8 и разделить на полученное максимально допустимое число младших битов. Для рассматриваемого примера получаем: 4 • 8/4 = 8, т. е. требуется сформировать восемь чисел ряда х;_у
  • • пронумеровать ячейки первого столбца от 0 до 7 (ниже сформированного шифротекста в двоичном виде). Во втором столбце ввести формулу для вычисления членов х₀ и х_{ с помощью функции ОСТАТ, например =ОСТАТ (В2^А2;$В$ 1) и =ОСТАТ (ВЮ^А2;$В$ 1) соответственно. Скопировать формулу для х_{ на остальные ячейки диапазона значений х_х (рис. 2.70);
  • • в третьем столбце сформировать значения четырех младших разрядов. Получить значения т младших разрядов числа в десятичном виде можно, взяв остаток от деления на 2^т. Это можно сделать с помощью функции ОСТАТ, например =ОСТАТ (ВЮ;16) для ps₀ (см. рис. 2.70).

Замечание: если максимально допустимое число младших битов равно трем, следует проводить деление по модулю 8 (значение второго параметр функции ОСТАТ следует задать равным восьми);

Рис. 2.70. Формирование псевдослучайной последовательности эффективного.

BBS-генератора.

• • скопировать формулу на остальные ячейки диапазона ps. В силу особенностей функций MS Excel, которые будут применены в дальнейших расчетах, переводить полученные десятичные значения в двоичный вид не имеет смысла.
• 11. Сформировать фрагменты шифротекста, которые будут расшифрованы полученной псевдослучайной последовательностью. Длина / формируемых фрагментов Y_t должна совпадать с длиной фрагментов последовательности ps (в рассматриваемом примере / = 4 бита):
  • • рядом с членами последовательности ps сформировать 4-битовые фрагменты Y_j с помощью функции ПСТР группы Текстовые. Функция ПСТР позволяет выделять из строки заданное количество символов, начиная с определенной позиции, символы строки нумеруются слева направо, начиная с единицы. В качестве начальной позиции следует задать значение г • / + 1, число выделяемых символов равно /, например =ПСТР ($В$ 8;А10*4+1;4) для У₀ (рис. 2.71);
  • • перевести полученные значения Y_{ в десятичный вид, используя функцию ДВ.В.ДЕС группы Инженерные, например =ДВ.В.ДЕС (Е10). Скопировать формулу на весь диапазон (см. рис. 2.71).^[1][2]

Рис. 2.71. Формирование фрагментов шифротекста.

Рис. 2.72. Формирование фрагментов открытого текста.

воспользоваться функцией ПСТР, задав значение начальной позиции равной i • 8 + 1, количество символов — равным восьми, 0 < i < 3 для рассматриваемого примера (если изначально шифротекст содержал три символа, то 0 < i < 2), например =ПСТР ($Н$ 18;А10*8+1;8) для фрагмента с номером «О» (рис. 2.73);

• • перевести полученные фрагменты в десятичный вид с помощью функции ДВ.В.ДЕС, например =ДВ.В.ДЕС (И0);
• • полученные десятичные значения ASCII-кодов перевести в символьный вид с помощью функции СИМВОЛ группы Текстовые, например =CHMB (XJI (J10). Критерием правильности расшифрования является получение осмысленного текста. Для рассматриваемого примера получено слово «коза» (см. рис. 2.73).

Рис. 2.73. Получение открытого текста

• [1] Расшифровать фрагменты Y;. • наложить на Yi фрагменты последовательности psi с помощью операции побитового XOR. В среде MS Excel 2013 это можно сделать с помощьюфункции БИТ. ИСКЛИЛИ группы Инженерные, операнды которой должны быть целыми числами, например =БИТ.ИСКЛИЛИ (С10;Е10) для вычисления значения Х0 (рис. 2.72). Примечание: в версиях MS Excel ниже 2013 функция БИТ. ИСКЛИЛИ не определена. В этом случае следует воспользоваться стандартным Windows-приложением Калькулятор, вид Инженерный, режим вычислений Dec, функция XOR; • перевести полученные фрагменты открытого текста X, в двоичный видс помощью функции ДЕС.В.ДВ, задав разрядность, равной четырем, например =ДЕС.В.ДВ (С10;4) для значения Х0 (см. рис. 2.72); • сформировать общую двоичную последовательность открытого текстас помощью операции & или функции СЦЕПИТЬ (см. рис. 2.72).
• [2] Получить символы открытого текста: • выделить из общей двоичной последовательности открытого текста8-битовые фрагменты, задающие ASCII-коды символов. Для этого следует