42735

Разработка и использование ActiveX ФОРМ

Лабораторная работа

Информатика, кибернетика и программирование

Шифр скитала многократно совершенствовался в последующие времена Шифрующие таблицы С начала эпохи Возрождения конец XIV столетия начала возрождаться и криптография. В разработанных шифрах перестановки того времени применяются шифрующие таблицы которые в сущности задают правила перестановки букв в сообщении В качестве ключа в шифрующих таблицах используются' размер таблицы; слово или фраза задающие перестановку особенности структуры таблицы. Одним из самых примитивных табличных шифров перестановки является простая перестановка для...

Русский

2013-10-30

552 KB

7 чел.

РАЗРАБОТКА и ИСПОЛЬЗОВАНИЕ  ActiveX ФОРМ

Цель работы: Разработка  компонента ActiveX на любом языке программирования и использование его в Windows Form C#.

ПРИМЕР СОЗДАНИЯ КОМПОНЕНТА ActiveX В СРЕДЕ DELPHI:

Создайте элемент ActiveX, в окне которого выводится движущаяся строка. Программа должна иметь возможность изменять скорость движения.

Разрабатываемая форма ActiveX изображена на рис.1.

 Рисунок -1.

Для разработки приложения выполните следующие действия:

  1.  Создайте приложение AxtiveX Form. Для этого выполните команду File New | Other и на странице ActiveX Депозитария выберите пиктограмму ActiveX Form. Будет создан новый проект, который сохраните под каким-то именем, например, ActiveMoveX.
  2.  Перенесите на форму компоненты, приведенные в таблице 1.

Таблица 1

Компоненты, размещаемые на форме

Компонент

Класс

Описание

Label1

TLabel

Метка «Бегущая строка»

Label2

TLabel

Метка «Интервал движения»

Edit1

TEdit

Окно вывода бегущей строки

Edit2

TEdit

Окно ввода интервала времени

Button1

TButton

Кнопка «Пуск»

Button2

TButton

Кнопка «Стор»

Timer1

TTimer

Таймер, отсчитывающий интервал вывода очередного символа (Страница System палитры компонентов)

  1.  Определение глобальных переменных.  В начале программного модуля Создайте  блок  VAR и определите две глобальные переменные: s – бегущая строка, I – номер очередного символа бегущей строки.

uses ComObj, ComServ;

{$R *.DFM}

{ TActiveMoveX }

VAR s: String;

         i:Integer;

  1.  Для события OnCreate форма запишите следующий программный код:

procedure TActiveMoveX.ActiveFormCreate(Sender: TObject);

begin

 s:='Hello World!';

 i:=1;

 Timer1.Enabled:=False;

 Edit1.Text:='';

end;

Данный код задает начальные условия.

  1.  Для события OnClick кнопки «Пуск» запишите следующий программный код:

procedure TActiveMoveX.Button1Click(Sender: TObject);

begin

 Timer1.Enabled:=False;

 Edit1.Text:='';

 s:='Hello World!';  

 i:=1;

 Timer1.Interval:=StrToInt(Edit2.Text);

 Timer1.Enabled:=True;

end;

Данный программный код запускает таймер

  1.  Для события OnTimer таймера запишите следующий программный код:

procedure TActiveMoveX.Timer1Timer(Sender: TObject);

begin

If i<=Length(s) then Edit1.Text:=s[i]+Edit1.Text

                else Edit1.Text:=' '+Edit1.Text;

 i:=i+1;

end;

Данный программный код выводит на экран очередной символ бегущей строки.

  1.  Для события OnClick кнопки «Стор» запишите следующий программный код:

procedure TActiveMoveX.Button2Click(Sender: TObject);

begin

 Timer1.Enabled:=False;

end;

Данный программный код останавливает работу таймера

  1.  Откомпилируйте разработанное приложение. Project | Build All Projects
  2.  Зарегистрируйте созданную форму ActiveX. Run | Register ActiveX Server.
  3.   Проверьте работу созданного приложения, вставив его в html-страницу (данный пункт задания выполнять не обязательно, можно перейти сразу в пункту 11). Для этого выполните следующие действия:
    1.  Запустите Microsoft FrontPage
    2.  Создайте новую страницу
    3.  Вставьте разработанную форму: Вставка | Веб компонент.  В появившемся диалоговом окне выберите «Дополнительные элементы», «Элемент ActiveX» (см. рис.2.)

 

Рисунок -2.

  1.  Нажмите кнопку «Далее». В появившемся диалоговом окне (рис.3.) выберите кнопку «Настройка».

 

Рисунок -3.

  1.  В появившемся диалоговом окне выберите созданный вами компонент ActiveX. В данном случае ActiveMoveX Control (см. рис. 4) 

 

Рисунок -4

  1.  Проверьте работу созданного компонента.
    1.  Добавьте к созданному компоненту возможность изменения цвета и размера выводимых символов. А также предоставьте пользователю возможность изменять выводимую строку.

  1.  Используйте разработанный компонент ActiveX   в приложении, написанном на C#.  Для этого выполните следующие действия:
    1.  Создайте в среде C#  проект Windows Forms;
    2.  добавьте созданный элемент управления ActiveX в панель инструментов, чтобы его можно было использовать также как элементы управления Windows (см. рисунок 5);  

Рисунок 5- Добавление элемента управления ActiveX  в панель инструментов.

  1.  В открывшемся диалоговом окне следует выбрать в категории  COM-Components элемент управления ActiveMoveX Control (рисунок 6). В итоге на панели инструментов появится новая пиктограмма.
    1.  Перетащить новую пиктограмму на поле визуального конструктора Windows Forms для создания сборки-оболочки для элемента управления ActiveX/

Рисунок 6 – Выбор элемента управления ActiveMoveX Control

  1.  Самостоятельно разработайте компонент ActiveX, выполняющий следующие действия:

Создание элемента ActiveX, в окне которого отображается строка, бегущая изнутри (например, пусть введена строка "АБВГ....ЭЮЯ", тогда последовательность отображения ее символов следующая: "АЯ", "АБЮЯ", "АБВЭЮЯ" и т.д.). Программа должна содержать меню, которое позволяет осуществлять выбор шрифта для отображения текста и вызывать диалоговое окно для ввода пользователем текста отображаемой строки и скорости вывода символов (задержка в миллисекундах).

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Составить приложение ActiveX для шифрования/дешифрирования по следующим методам:

  1.  Шифр перестановки «Скитала»
  2.  Шифрующих таблиц.
  3.  Шифрующих таблиц с ключевым словом.
  4.  Шифрующих таблиц. Двойная перестановка.
  5.  Магических квадратов
  6.  Полибианский квадрат (Только, пожалуйста, не используйте греческий алфавит)
  7.  Системы шифрования Цезаря (кому-то повезло!)
  8.  Аффинной системы подстановок Цезаря
  9.  Системы Цезаря с ключевым словом
  10.  Шифрующих таблиц Трисемуса
  11.  Биграммного шифра Плейфейра
  12.  Шифра Гронсфельда
  13.  Двойного квадрата Уитстона
  14.  Шифрование методом гаммирования
  15.  Программной реализации роторной машины.

ОПИСАНИЕ МЕТОДОВ ШИФРОВАНИЯ

Шифр перестановки «Скитала»

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

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

Н

А

С

Т

У

П

А

Й

Т

Е

Рис.1.

Сообщение НАСТУПАЙТЕ при размещении его по окружности стержня по три буквы дает шифртекст    НУТАПЕСА_ТЙ

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

Шифрующие таблицы

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

В качестве ключа в шифрующих таблицах используются'

размер таблицы;

слово или фраза, задающие перестановку,

особенности структуры таблицы.

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

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

записывается в таблицу поочередно по столбцам.  

Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 2.

Т

Н

П

В

Е

Г

Л

Е

А

Р

А

д

О

Н

Р

Т

И

Е

Ь

В

О

М

О

Б

Т

М

П

Ч

И

Р

Ы

С

О

О

Ь

Рис 2.  Заполнение таблицы из 5 строк и 7 столбцов

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

ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ

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

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

Применим в качестве ключа, например, слово ПЕЛИКАН, а текст сообщения возьмем из предыдущего примера. На рис. 3 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица- заполнению после перестановки.

Ключ

П

Е

Л

И

К

А

Н

А

Е

И

К

Л

Н

П

7

2

5

3

4

1

6

1

2

3

4

5

6

7

Т

Н

П

В

Е

Г

Л

Г

Н

В

Е

П

Л

Т

Е

А

Р

А

Д

О

Н

0

А

А

Д

Р

Н

Е

Р

Т

И

Е

Ь

В

О

В

Т

Е

Ь

И

О

Р

М

О

Б

Т

М

П

Ч

П

0

Т

М

Б

Ч

М

И

Р

Ы

С

О

О

Ь

О

Р

С

О

Ы

Ь

И

До перестановки                   После перестановки

Рис 3. Таблицы, заполненные ключевым словом и текстом сообщения

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

При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение:

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ

Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.

Пример выполнения шифрования методом двойной перестановки показан на рис. 4.

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

ТЮАЕ ООГМ РЛИП ОЬСВ

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

4

1

3

2

1

2

3

4

1

2

3

4

3

П

Р

И

Л

3

Р

Л

И

П

1

Т

Ю

А

Е

1

Е

Т

А

Ю

1

Т

Ю

А

Е

2

О

О

Г

М

4

В

О

С

Ь

4

О

Ь

С

В

3

Р

Л

И

П

2

М

О

Г

О

2

О

О

Г

М

4

О

Ь

С

В

Исходная таблица          Перестановка столбцов          Перестановка строк

Рис. 4. Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

для таблицы 3х3    36 вариантов;

для таблицы 4х4   576 вариантов;

для таблицы 5х5 14400 вариантов.

Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

Применение магических квадратов

В средние века для шифрования перестановкой применялись и магические квадраты.

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

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

Пример магического квадрата и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО  показан на рис. 5..

16

3

2

13

О

И

Р

М

5

10

11

8

Е

О

С

Ю

9

6

7

12

В

Т

А

Ь

4

15

14

1

Л

Г

О

П

Рис 5. Пример магического квадрата 4х4 и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО

Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид:

ОИРМ ЕОСЮ ВТАЪ ЛГОП

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000.

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

ШИФРЫ ПРОСТОЙ ЗАМЕНЫ

При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.

Полибианский квадрат

Одним из первых шифров простой замены считается так называемый "полибианский квадрат".  За два века до нашей эры греческий писатель и историк Полибий изобрел для целей шифрования  квадратную таблицу размером 5x5, заполненную буквами греческого алфавита в случайном порядке. (Рис.6.)

Рис.6.  Полибианский квадрат, заполненный случайным образом  24 буквами греческого алфавита и пробелом.

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

Например, для слова   получается шифртекст  .

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

Система шифрования Цезаря

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

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

Таблица 1

Одно-алфавитные подстановки (К = 3, m = 26)

A

D

J

M

S

V

B

E

K

N

T

W

C

F

L

O

U

X

D

G

M

Р

V

Y

E

H

N

Q

W

Z

F

I

O

R

X

A

G

J

Р

S

Y

B

H

K

Q

T

Z

C

I

L

R

U

Например, послание Цезаря: VENI VIDI VICI

(в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL

Аффинная система подстановок Цезаря

В системе шифрования Цезаря использовались только аддитивные свойства множества целых Zm . Однако символы множества Zm можно также умножать по модулю m. Применяя одновременно операции сложения и умножения по модулю m над элементами множества Zm, можно получить систему подстановок, которую называют аффинной системой подстановок Цезаря.

Определим преобразование в такой системе:

Ea,b  : ZmZm

Ea,b : tEa,b(t)

Ea.b(t) = at + b (mod m), где a, b - целые числа, 0<a,b<m,   НОД(а,m) = 1.

В данном преобразовании буква, соответствующая числу t, заменяется на букву, соответствующую числовому значению (at + b) по модулю m.

Следует заметить, что преобразование Eab(t) является взаимно однозначным отображением на множестве Zm только в том случае, если наибольший общий делитель чисел а и m, обозначаемый как НОД (а, m), равен единице, т.е. а и m должны быть взаимно простыми числами.

Например, пусть m = 26, а = 3, b = 5. Тогда, очевидно,
НОД (3,26) = 1, и мы получаем следующее соответствие между
числовыми кодами букв: .

t

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

3t+5

5

8

11

14

17

20

23

0

3

6

9

12

15

18

21

24

1

4

7

10

13

16

19

22

25

2

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

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

T

U

V

W

X

Y

Z

F

I

L

O

R

U

X

А

D

G

J

М

Р

S

V

Y

В

Е

Н

K

N

Q

Т

W

Z

C

Исходное сообщение   НОРЕ    преобразуется в шифртекст   AVYR

Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, Ь). Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря.

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

Система Цезаря с ключевым словом

Система шифрования Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки .

Выберем некоторое число k, 0 < k < 25 , и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число k = 5.

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

0 1  2  3  4  5             10                15             20                25

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке:

                  5

A B  C D E F G H I J  K  L M N O P Q R S T U V W X Y Z

V W X Y Z D I P L O M A T  B C E  F G H J K N Q R  S  U

Теперь мы имеем подстановку для каждой буквы произ-'
вольного сообщения.

Исходное сообщение    SEND MORE MONEY

шифруется как    HZBY TCGZ   TCBZS 

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

КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН и число k = 3 порождают следующую таблицу подстановок:

0         3

А Б  ВГ Д ЕЖ З ИЙКЛ МНОПРСТУ ФХЦЧШЩЬЫЪЭЮЯ

ЪЭЮКА ДЫМОТЕ Ч СВНЛИП РЯ  БГЖЗЙ  У Ф X ЦШЩ  Ь

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

Шифрующие таблицы Трисемуса

В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием "Полиграфия". В  этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнилась не вошедшими в нее буквами алфавита по порядку.

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

Пример.  Для русского алфавита шифрующая таблица может иметь размкр 4х8. Ключевое слово – БАНДЕРОЛЬ. Шифрующая таблица с таким ключом имеет следующий вид.

Б

А

Н

Д

Е

Р

О

Л

Ь

В

Г

Ж

З

И

И

Л

М

П

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ы

Ъ

Э

Ю

Я

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

Например, при шифровании с помощью этой таблицы сообщения

ВЫЛЕТАЕМПЯТОГО

получаем шифртекст

ПДКЗЫВЗЧШЛЫЙСЙ

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

Биграммный шифр Плейфейра

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

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

Процедура шифрования включает следующие шаги.

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

2. Последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы в последовательность биграмм шифртекста по следующим правилам:

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

2.2. Если обе буквы биграммы открытого текста принадлежат одному столбцу таблицы, то буквами шифртекста считаются буквы, которые лежат под ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при этом буква открытого текста находится в нижней строке, то для шифртекста берется соответствующая буква из верхней строки того же столбца. (Например, биграмма ВШ дает битрамму шифртекста ПА.)

  2.3. Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами шифртекста считаются буквы, которые лежат справа от них. (Например, биграмме НО дает биграмму шифртекста ДЛ.) Если при этом буква открытого текста находится в крайнем правом столбце, то для шифра берут соответствующую букву из левого столбца той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.) Зашифруем текст

ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ

Разбиение этого текста на биграммы дает

ВС   ЕТ  АЙ   НО   ЕС   ТА    НЕ   ТЯ     ВН   ЫМ

Данная последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы  в следующую последовательность биграмм шифртекста

ГП   ДУ ОВ   ДЛ   НУ   ПД   ДР   ЦЫ   ГА   ЧТ

При расшифровании применяется обратный порядок действий.

Следует отметить, что шифрование биграммами резко повышает стойкость шифров к вскрытию. Хотя книга И.Трисемуса "Полиграфия" была относительно доступной, описанные в ней идеи получили признание лишь спустя три столетия. По всей вероятности, это было обусловлено плохой осведомленностью криптографов о работах богослова и библиофила Трисемуса в области криптографии.

Система омофонов

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

Данные о распределениях вероятностей букв в русском тексте приведены в таблице. Буквы в таблицах указаны в порядке убывания вероятности их появления в тексте. Например, русская буква Е встречается в 36 раз чаще, чем буква Ф, а английская буква Е встречается в 123 раза чаще, чем буква Z.

Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (часто называемые омофонами) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G - по 16 номеров, а буквам J и Z - по 1 номеру. Если омофоны (замены) присваиваются случайным образом различные появления одной и той же буквы, тогда каждый омофон появляется в щифртексте равномерно.

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

Распределение вероятностей букв в русских текстах

Буква

Вероятн.

Буква

Вероятн

Буква

Вероятность

Буква

Вероятность

Пробел

0,175

Р

0,040

Я

0,018

X

0.009

О

о;оэо

В

0,038

Ы

0.016

Ж

0,007

Е

0,072

Л

0,035

3

0,016

Ю

0.006

А

0,062

К

0,028

Ъ

0,014

Ш

0,006

И

0,062

М

0,026

Б

0,014

Ц

0.004

Н

0,053

Д

0,025

Г

0,013

Щ

0,003

Т

0,053

П

0,023

Ч

0,012

Э

0,003

С

0,045

У

0,021

Й

0,010

Ф

0,002

ШИФРЫ СЛОЖНОЙ ЗАМЕНЫ

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

При r-алфавитной подстановке символ хо исходного сообщения заменяется символом уо из алфавита Во, символ x1 -символом y1 из алфавита B1, и так далее, символ Хг-1 заменяется символом ум из алфавита Вг-1, символ хг заменяется символом уг снова из алфавита Во, и т.д.

Общая схема многоалфавитной подстановки для случая г = 4 показана на рис. 5.7

Входной символ

X0

X1

X2

X3

X4

X5

X6

X7

X8

X9

Алфавит подстановки

B0

B1

B2

B3

B0

B1

B2

B3

B0

B1

Схема г-алфавитной подстановки для случая г = 4

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

Многоалфавитные шифры замены предложил и ввел в практику криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Его книга "Трактат о шифре", написанная в 1566 г., представляла собой первый в Европе научный труд по криптологии. Кроме шифра многоалфавитной замены, Альберти также подробно описал устройства из вращающихся колес для его реализации. Криптологи всего мира почитают Л.Альберти основоположником криптологии.

Шифр Гронсфельда

Этот шифр сложной замены, называемый шифром Гронсфельда, представляет собой модификацию шифра Цезаря числовым ключом. Для этого под буквами исходного сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Например, применяя в качестве ключа группу из четырех начальных цифр числа е (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:

Сообщение

В

О

С

Т

О

Ч

Н

Ы

Й

Э

К

С

П

Р

Е

С

С

Ключ

2

7

1

8

2

7

1

8

2

7

1

8

2

7

1

8

2

Шифртекст

Д

Х

Т

Ь

Р

Ю

О

Г

Л

Д

Л

Щ

С

Ч

Ж

Щ

У

Чтобы зашифровать первую букву сообщения В, используя первую цифру ключа 2 , нужно отсчитать вторую по порядку букву от В в алфавите В-Г-Д; получается первая буква шифр текста Д.

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

Система шифрования Вижинера

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

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

Таблица Вижинера для английского алфавита

ключ

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

0

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

1

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

2

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

3

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

4

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

5

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

6

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

7

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

8

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

9

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

10

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

11

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

12

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

13

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

14

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

15

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

16

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

17

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

18

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

19

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

20

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

21

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

22

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

23

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

24

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

25

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

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

Последовательность ключей обычно получают из числовых значений букв ключевого слова.

При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очередную букву исходного текста и в левом столбце очередное значение ключа. Очередная буква шифртекста находится на пересечении столбца, определяемого шифруемой буквой, и строки, определяемой числовым значением ключа.

Рассмотрим пример получения шифртекста с помощью таблицы Вижинера. Пусть выбрано ключевое слово АМБРОЗИЯ. Необходимо зашифровать сообщение ПРИЛЕТАЮ СЕДЬМОГО.

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

Сообщение     П Р И Л Е Т А Ю     С Е Д Ь М О Г О

Ключ               А М Б Р О З И Я      А М Б Р О З И  Я

Шифртекст     П Ъ Й ЫУЩ И Э     С С  Е К Ь ХЛ  Н

Шифр "двойной квадрат" Уитстона

В 1854 г. англичанин Чарльз Уитстон разработал новый метод шифрования биграммами, который называют "двойным квадратом". Свое название этот шифр получил по аналогии с полибианским квадратом. Шифр Уитстона открыл новый этап в истории развития криптографии. В отличие от полибианского шифр "двойной квадрат" использует сразу две таблицы, размещенные по одной горизонтали, а шифрование идет биграммами, как в шифре Плейфейра. Эти не столь сложные модификации привели к появлению на свет качественно новой криптографической системы ручного шифрования. Шифр "двойной квадрат" оказался очень надежным и удобным и применялся Германией даже в годы второй мировой войны.

Ж

Щ

Н

Ю

Р

И

Ч

Г

Я

Т

И

Т

Ь

Ц

Б

,

Ж

Ь

М

О

Я

М

Е

.

С

З

Ю

Р

В

Щ

В

Ы

П

Ч

Ц

:

П

Е

Л

:

Д

У

О

К

Ъ

А

Н

.

Х

З

Э

Ф

Г

Ш

Э

К

С

Ш

Д

Х

А

,

Л

Ъ

Б

Ф

У

Ы

Пример процедуры шифрования данным методом:

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

Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке 2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифртекста ОВ.

Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифртекста берут из этой же строки. Первую букву биграммы шифртекста берут из левой таблицы в столбце, соответствующем второй букве биграммы сообщения. Вторая же буква биграммы шифртекста берется из правой таблицы в столбце, соответствующем первой букве биграммы сообщения. Поэтому би-грамма сообщения ТО превращается в биграмму шифртекста ЖБ. Аналогичным образом шифруются все биграммы сообщения:

Сообщение       ПР   ИЛ   ЕТ    АЮ   _Ш   ЕС   ТО    ГО

Шифртекст       ПЕ   ОБ   ЩН  ФМ   ЕШ   РФ   БЖ   ДЦ

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

Роторные машины

В 20-х годах ХХ века были изобретены электромеханические устройства шифрования, автоматизирующие процесс шифрования. Принцип работы таких машин на многоалфавитной хамене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Большинство из них – американская машина SIGABA (M-134), английская TYPEX, немецкая ENIGMA, японская  PURPLE были роторными машинами.

Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками внутри. Ротор имеет форму диска (размером с хоккейную шайбу).На каждой стороне диска расположены равномерно по окружности m электрических контактов, где m – число знаков алфавита  (в случае английского алфавита m=26). Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней.  Например, ротор можно закоммутировать проволочными перемычками для подстановки G вместо А, U вместо В,  L вместо С  и т.д.

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

T = Cj  C-j .

где  - подстановка, реализуемая ротором в его начальлом положении; С - циклический сдвиг на одну позицию; Сj - циклический сдвиг на j позиций.

Например, если начальная подстановка ротора (А) = G и ротор сдвигается на три позиции (j = 3), то открытый текст D будет против того контакта ротора, который используется для представления открытого текста А, а шифрованный текст J окажется против того контакта ротора, который используется для представления шифрованного текста G , и результирующая подстановка Т (D)=G при j = 3. Алгебраически это записывается в виде

Т (D) = С3  С-3 (D) = С3 (А) = С3 (G) = J.

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

Т = Сj1 1 С-j1 Сj2 2 С-j2 ….Сj n-1 n-1 С-jn-1 Сj n n С-jn =

= Сj1 1  Сj2-j1 2  ….n-1  Сj n-jn-1 n С-jn.

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

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

Простейшее из возможных движений ротора - это движение по принципу одометра; оно использовалось в немецкой машине Enigma во время второй мировой войны. При шифровании одного знака правое крайнее колесо поворачивается на одну позицию. Когда это (и любое другое) колесо переместится на m позиций и совершит полный оборот, колесо, расположенное слева от него, передвинется на одну позицию, и процесс будет повторяться. Этот процесс проведет банк роторов сквозь все его возможные положения, прежде чем цикл повторится. Поскольку все роторы перемещаются с разными скоростями, период n-роторной машины составляет 26" (при m = 26).

Для закона движения ротора желательны следующие характеристики:

  •  период должен быть большим;
  •  после шифрования каждого знака все роторы или большая их часть должны повернуться друг относительно друга.

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

Другое решение заключается в ограничении числа допустимых остановочных мест для каждого ротора за счет введения внешнего фиксирующего кольца, на котором определенным способом зафиксированы места остановок. При использовании латинского алфавита можно заставить машины поворачиваться и останавливаться следующим образом. Первому колесу разрешается останавливаться в каждой из 26 позиций, второму колесу - только в 25 позициях, третьему колесу - только в 23 позициях, и так далее до шестого колеса, которому разрешается останавливаться только в 17 позициях. Период такой роторной машины теперь составляет 101 млн, а не 266  309 млн, как в случае движения по принципу одометра. Потеря в длине периода с успехом окупается полученной сложностью движения роторов. Теперь второе требование удовлетворяется довольно хорошо, поскольку каждое из колес перемещается после шифрования каждого знака и многие колеса могут двигаться друг относительно друга.          

Роторная машина может быть настроена по ключу  изменением любых ее переменных:

  •  порядка расположения роторов;                                                 
  •  числа мест остановки на колесо;
  •  характера движения и т.д.                                                           

Поскольку перекоммутировать роторы трудно, то обычно на практике машины обеспечивали комплектом роторов, в котором находилось больше роторов, чем можно одновременно поместить в машину. Первичная настройка по ключу производилась выбором роторов, составляющих комплект. Вторичная настройка по ключу производилась выбором порядка расположения роторов в машине и установкой параметров, управляющих, движением машины. С целью затруднения расшифрования шифртекстов противником роторы ежедневно переставляли местами или заменяли. Большая часть ключа определяла начальные положения роторов (263 = 17576 возможных установок) и конкретные перестановки на коммутационной доске, с помощью которой осуществлялась начальная перестановка исходного текста до его шифрования (26! = = 4*1026 возможностей).

Роторные машины были самыми важными криптографическими устройствами во время второй мировой войны и доминировали по крайней мере до конца 50-х годов.

ШИФРОВАНИЕ МЕТОДОМ ГАММИРОВАНИЯ

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

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

Следует отметить, что перед зашифрованием открытые данные разбивают на блоки Т0(i) одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков Гш(i) аналогичной длины.

Уравнение зашифрования можно записать в виде

Тш(i) = Гш(i)  T0(i) ,     i = 1 ... М

где Тш(i) - i-й блок шифртекста; Гш(i) - i-й блок гаммы шифра; Т0(i) -
i-й блок открытого текста; М - количество блоков открытого текста.

Процесс расшифрования сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение расшифрования имеет вид

Т0(i) = Гш(i)  Tш(i) 

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

Методы генерации псевдослучайных последовательностей чисел

При шифровании методом гаммирования в качестве ключа используется случайная строка битов, которая объединяется с открытым текстом, также представленным в двоичном виде (например, А = 00000, В = 00001, С = 00010 и т.д.), с помощью побитового сложения по модулю 2, и в результате получается шифрованный текст. Генерирование непредсказуемых двоичных последовательностей большой длины является одной из важных проблем классической криптографии. Для решения этой проблемы широко используются генераторы двоичных псевдослучайных последовательностей.

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

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

К криптографически стойкому генератору псевдослучайной последовательности чисел (гаммы шифра) предъявляются три основных требования:

  1.  период гаммы должен быть достаточно большим для шифрования сообщений различной длины;
  2.  гамма должна быть практически непредсказуемой, что означает невозможность предсказать следующий бит гаммы, даже если известны тип генератора и предшествующий кусок гаммы;
  3.  генерирование гаммы не должно вызывать больших технических сложностей.

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

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

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

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

Из известных процедур генерации последовательности псевдослучайных целых чисел наиболее часто применяется так называемый линейный конгруэнтный генератор. Этот генератор вырабатывает последовательность псевдослучайных чисел Y1, Y2, ..., Yi-1, Yi, ..., используя соотношение

Yi = (a*Yi-1 + b) mod m,
где
Yi - i-e (текущее) число последовательности; Yi-1 - предыдущее число последовательности; а, Ь и m - константы; m - модуль;
а - множитель (коэффициент);
b - приращение; Y0 - порождающее
число (исходное значение).

Текущее псевдослучайное число Yi получают из предыдущего числа Yi-1 умножением его на коэффициент а, сложением с приращением b и вычислением остатка от деления на модуль m. Данное уравнение генерирует псевдослучайные числа с периодом повторения, который зависит от выбираемых значений параметров а, Ь и m и может достигать значения m. Значение модуля m берется равным 2n либо равным простому числу, например m=231-1. Приращение b должно быть взаимно простым с m, коэффициент а должен быть нечетным числом.

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

Существует способ генерации последовательностей псевдослучайных чисел на основе линейных рекуррентных соотношений.

Рассмотрим рекуррентные соотношения и их разностные уравнения:

k

 hj *ai+j=0

j=0

        k-1

ai+k=- hj *ai+j

        j=0

где h00, hk=1   и каждое hi  принадлежит полю GF(q).

Решением этих уравнений является последовательность элементов а012,... поля GF(q). Соотношение  определяет правило вычисления ak по известным значениям величин a0,a1,a2,...,ak-1. Затем по известным значениям a0,a1,a2,...,ak находят ak+1 и т.д. В результате по начальным значениям a0,a1,a2,...,ak-1 можно построить бесконечную последовательность, причем каждый ее последующий член определяется из k предыдущих. Последовательности такого вида легко реализуются на компьютере, при этом реализация получается особенно простой, если все hi и аi, принимают значения 0 и 1 из поля GF(2).

На рис. показана линейная последовательная переключательная схема, которая может быть использована для вычисления суммы  и, следовательно, для вычисления значения ak по значениям k предыдущих членов последовательности. Исходные величины a0,a1,a2,...,ak-1 помещаются в разряды сдвигового регистра, последовательные сдвиги содержимого которого соответствуют вычислению последовательных символов, при этом выход после   i-ro сдвига равен   аi. Данное устройство генератором  последовательности  чисел,   построенным  на  базе сдвигового регистра с линейной обратной связью.

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

h(X)= hjXj,

где X - формальная переменная; hj - коэффициент при Xj, принимающий значение 0 или 1; h0 0, hk= 1, и пусть n - наименьшее целое положительное число, для которого многочлен Хn - 1 делится на h(X).

Кроме того, многочлен g(x)=(Xn-1)/h(X)

Тогда решения рекуррентных соотношений

k

 hj *ai+j=0

j=0

в виде последовательности элементов а01i,...an-1  периодичны с периодом n и совокупность, составленная из первых периодов всех возможных решений, рассматриваемых как многочлены по модулю (Хn-1),т.е.

 a(X)= а0*Xn-1+ а1*Xn-2 + ….+аn-2*X+ аn-1.

совпадает с идеалом, порожденным многочленом g (X) в алгебре многочленов по модулю (Хn - 1). Доказательство этой теоремы можно найти  в книге Питерсон У, Уэлдон Э.  «Коды, исправляющие ошибки».

Заметим, что если при таком определении многочлена а(Х) элементы а012,... вычисляются в порядке возрастания номеров, то коэффициенты многочлена а(Х) вычисляются, начиная с коэффициентов при степенях высших порядков. Следует также отметить, что вид многочлена  

 k

                                      h(X)= hj *xj=0

j=0

определяет конфигурацию обратных связей (отводов) hj в генераторе со сдвиговым регистром. Другими словами, если у многочлена h(X) коэффициент hj= 1, это означает, что отвод hj в схеме генератора присутствует, если же у многочлена h(X) коэффициент hj = 0, то отвод hj в схеме генератора отсутствует. В [Питерсон У, Уэлдон Э.  «Коды, исправляющие ошибки»] показано, что в качестве h(Х) необходимо выбирать неприводимый примитивный многочлен. При таком выборе многочлена h(X) со старшей степенью m генератор обеспечивает выдачу псевдослучайной последовательности двоичных чисел с максимально возможным периодом 2m - 1 .

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

h(Х) = X3 + X2 + 1,

где коэффициенты h3=1, h2 = 1,  h1 = 0, h0=1.

Пусть ключом является 101. Регистр начинает работать с этого состояния; последовательность состояний регистра приведена на рис.

Регистр проходит через все семь ненулевых состояний и снова возвращается в свое исходное состояние 101. Это - наиболее длинный период данного регистра с линейной обратной связью. Такая последовательность называется последовательностью максимальной длины для сдвигового регистра (Maximal Lenght Shift Register Sequence - MLSRS). Питерсон и Уэлдон  показали, что при любом целом m существует m-битовая последовательность MLSRS с периодом 2m - 1. В частности, при m =100 последовательность будет иметь период 2100 - 1 и не повторится 1016 лет при передаче ее по линии связи со скоростью 1 Мбит/с.

В данном примере выходной последовательностью (гаммой шифра) Гш сдвигового регистра с обратной связью является последовательность 1010011, которая циклически повторяется. В этой последовательности имеется четыре единицы и три нуля, и их распределение настолько близко к равномерному, насколько это возможно в последовательности, имеющей длину 7. Если рассмотреть пары последовательных битов, то пары 10 и 01 появляются по два раза, а пары 00 и 11 - один раз, что опять оказывается настолько близким к равномерному распределению, насколько это возможно. В случае последовательности максимальной длины для m-разрядного регистра это свойство равнораспределенности распространяется на тройки, четверки и т.д. битов, вплоть до m-битовых групп. Благодаря такой близости к равномерному распределению последовательности максимальной длины часто используются в качестве псевдослучайных последовательностей в криптографических системах, которые имитируют работу криптостойкой системы одноразового шифрования.

Хотя такая криптографическая система осуществляет имитацию заведомо криптостойкой системы одноразового шифрования, сама она не отличается стойкостью и может быть раскрыта за несколько секунд работы компьютера при условии наличия известного открытого текста [Диффи У. Хеллман М.Э. «Защищенность и имитостойкость. Введение в криптографию»].

Если отводы регистра с обратной связью зафиксированы, то для нахождения начального состояния регистра достаточно знать m битов открытого текста. Чтобы найти m битов ключевого потока, m битов известного открытого текста складывают по мо: дулю 2 с соответствующими m битами шифртекста. Полученные m битов дают состояние сдвигового регистра с обратной связью в обратном направлении на некоторый момент времени. Затем, моделируя работу регистра назад, можно определить его исходное состояние.

Если отводы регистра с обратной связью не фиксированы, а являются частью ключа, то достаточно 2m битов известного открытого текста, чтобы сравнительно быстро определить расположение отводов регистра и его начальное состояние. Пусть S(i) -вектор-столбец, состоящий из m символов 0 и 1, который определяет состояние регистра в i-й момент времени. Тогда

S(i + 1) = A*S(i) mod 2,

где А — матрица размером m x m, определяющая положение отводов регистра с обратной связью.

Для трехразрядного регистра

                                             |  1 0      1    |

                          А = | 1          0       0  |

                                 |  1 0      1    |

Матрица А всегда имеет следующую структуру: в ее первой строке отражена последовательность отводов в регистре, непосредственно под главной диагональю располагаются единицы, а в остальных позициях располагаются нули.

2m битов известного открытого текста позволяют вычислить 2т последовательных битов ключевого потока. Для упрощения обозначений предположим, что это - первые 2 m   битов ключевого потока. Следовательно,

•   S(1) - первая группа m известных битов ключевого, потока;

•   S(2) - следующая   группа (начиная с номера 2) из   m   известных битов ключевого потока;

•   S(m+1) - последняя группа из   m   известных битов ключевой потока.

Далее можно образовать две матрицы размером m x m:

X(1) = [S(1), S(2), ... S(m)]

X(2) = [S(2), S(3), ..., S(m+1)]

которые связаны соотношением  X(2) = A*X(1)mod2.

Можно показать, что для любой последовательности максимальной длины матрица Х(1) всегда несингулярна, поэтому матрицу А можно вычислить как

А = Х(2)[Х(1)]-1 mod 2.

Обращение матрицы Х(1) требует (самое большее) порядка m3 операций, поэтому легко выполняется при любом разумном значении m.

Для криптографии последовательности максимальной длины MLSRS можно сделать более криптостойкими, используя нелинейную логику. В частности, предложен вариант [Диффи У. Хеллман М.Э. «Защищенность и имитостойкость. Введение в криптографию»], в котором в качестве ключевого потока используется нелинейно "фильтрованное" содержимое сдвигового регистра, а для получения последовательности максимальной длины - линейная обратная связь (см. рис.).

Функция f должна выбираться так, чтобы обеспечить хороший баланс между нулями и единицами, а фильтрованная последовательность имела распределение, близкое к равномерному. Необходимо также, чтобы фильтрованная последовательность имела большой период. Если (2m - 1) является простым числом (как в примере: при m = 3 имеем 23 - 1 = 7), то фильтрованная последовательность может иметь период (2m - 1) (при выборе структуры сдвигового регистра в соответствии с неприводимым примитивным многочленом h(Х) степени m).

К таким значениям m относятся, в частности, следующие: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, а полученные таким образом простые числа называются простыми числами Мерсенна.

Несмотря на то, что фильтрованную выходную последовательность обычно нельзя получить с помощью m-разрядного сдвигового регистра с линейной обратной связью, ее всегда можно получить с помощью сдвигового регистра большей длины с линейной обратной связью [Месси Дж. П. «Введение в современную криптологию»]. Регистр длиной (2m - 1) всегда позволит это сделать, а иногда пригоден и более короткий регистр.

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


Вход

  А

     G

Выход

0

1

n

         

Банк роторов

T (D) = J

A B C D E F G H I J K L M N O P Q R S T U V W Z Y S

A B C D E F G H I J K L M N O P Q R S T U V W Z Y S

Ротор

J=3               (A) =G   

Схема формирования подстановки при сдвиге ротора j=3

Обозначения

 Выходной бит

ai+k-1

ai+k-2

ai+2

ai+1

ai

hk-2

h2

h1

h0

hk-1

Сумматор по модулю 2

hk-1

Цепь (отвод) с коэффициентом передачи h, h=0  или 1

ai

Запоминающая ячейка, хранящая  а, т.е. на выходе ячейки а=0 или а=1

Генератор с регистром сдвига

C=Гш М

Трехразрядный регистр сдвига с обратными связями (генератор гаммы шифра Гш)

h3=1

h2=1   h1=0      h0=1

M

Ключевой поток

Гш=1010011

3-битовый ключ

1 0 1

0 1 0

0 0 1

1 0 0

1 1 0

1 1 1

0 1 1

Гш

                               f

h3=1

h2=1                    h0=1

Гш           С=ГшМ

Линейный сдвиговый регистр с нелинейными логическими цепями на входе


 

А также другие работы, которые могут Вас заинтересовать

38985. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СОЛНЕЧНЫХ КОЛЛЕКТОРОВ С ВАКУУМИРОВАННЫМИ СТЕКЛОПАКЕТАМИ 2.09 MB
  ИССЛЕДОВАНИЕ ПЛОСКИХ СОЛНЕЧНЫХ КОЛЛЕКТОРОВ С ВАКУУМИРОВАННЫМИ СТЕКЛОПАКЕТАМИ Методика расчета солнечного коллектора с вакуумированным стеклопакетом Тепловой баланс солнечного коллектора с вакуумированным стеклопакетом Зависимость коэффициента теплопроводности разреженного газа от давления в вакуумном зазоре ВСП Расчет характеристик вакуумированных стеклопакетов обеспечивающих повышение эффективности солнечных коллекторов Экспериментальное исследование макета солнечного коллектора с...
38989. Численные методы 2.17 MB
  Из полученных данных видно, что метод подобластей имеет наилучший результат вычислений из всех остальных методов. Во-первых, даже при небольшом количестве разбиений он дал точность на 2 порядка лучше, чем второй по полученной точности метод Галеркина. Во-вторых, точность при количестве дискрет n=12 уже не укладывалась в разрядную сетку персонального компьютера.
38990. Икона Рождества Христова 33 KB
  Зубок с указкой в руке стоит у доски показывая на иллюстрации Рождественских событий Зубок: Ребята сегодня я буду учителем. Отвечайте на мои вопросы: Кто изображен на этом рисунке Родившийся МладенецХристос Зубок: Кто явился пастухам на поле Ангел Зубок: Какую весть принес ангел Что родился Бог в пещере Зубок: Кто едет на верблюдах по пустыне Звездочеты с дарами Зубок: Что привезли волхвы в подарок Иисусу Христу Золото ладан и смирну Зубок: Здорово мне нравиться быть учителем Матильда Леонардовна: Здравствуйте ребята...
38991. Совинформ. Праздник Крещения Господня – Богоявление 33 KB
  Беседа жителей Шишкиного леса Шуня раскладывает сувенирчики Енот Енотович приносит баночки с водой. Шуня: Какая я счастливая сколько мне подарков на святках подарили Енот Енотович: А ты Шунечка дарила другим радость в эти святые дни Шуня: Да конечно только не могу вам рассказать что и кому а то Матильда Леонардовна говорит что я все свои добрые дела растеряю. Шуня: Здорово что есть Господь которому можно доверить все свои тайны А что это у вас в руках за тайна такая Енот Енотович: Никакая это ни тайна а просто вода. Шуня: А...
38992. Притча о неразумном богаче. Советы Енота Енотовича. Думай о других 35.5 KB
  Советы Енота Енотовича. Оборудование: иллюстрации к притчам о добром самарянине неразумном богаче куклы котенка Коксика Енота Енотовича. Чему же хотел научить нас Господь Был ли жадным богач Какое решение он принял когда собрал большой урожай Смог ли он насладиться своим богатством что случилось с ним Советы Енота Енотовича: Думай о других. Коксик: Енот Енотыч Енот Енотыч – закричал котенок вбегая в комнату.
38993. Сретение Господне 35 KB
  Шуня: Тетушка Матильда что еще сделать Матильда Леонардовна: Вещи все сложила на место Шуня: Да. Матильда Леонардовна: Игрушки все убрала Шуня: Конечно. Матильда Леонардовна: Пыль везде вытерла Шуня: Вездевезде Матильда Леонардовна: Тогда принеси мне пожалуйста связку свечей из тумбочки. Зубок: Ухты как у нас чисто и красиво А что у нас завтра праздник какойто Может день рождения у когото Шуня: А вот и нет а вот и не угадал Совсем не день рождения Зубок: А к чему это вы так готовитесь Матильда Леонардовна: Открываем...