Современные информационные технологии/ 4. Информационная безопасность

 

к.т.н. В.Г.Ткаченко, к.ф.-м.н. О.В.Синявский

Одесская национальная академия связи им. А.С.Попова, Украина

КРИПТОСИСТЕМА НА ОСНОВЕ ОТОБРАЖЕНИЯ ТИПОВ МОНОТОННЫХ БУЛЕВЫХ ФУНКЦИЙ (МБФ) НА МНОЖЕСТВО НАТУРАЛЬНЫХ ЧИСЕЛ.

 

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

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

Однако в [6] передача ключей (типы монотонных булевых функций) имеют сложную структуру, поэтому усложняется передача ключа и снижается надёжность криптосистемы.

Назовем вектор Т = (a0, a1,…,ai,…,an) из n + 1 компоненты, которые нумеруются слева направо от 0 до n, типом МБФ, если i-я компонента вектора ai равна числу подмножеств из i элементов в соответствующем данной МБФ семействе подмножеств Шпернера. При этом одновременно i-я компонента вектора ai равна числу минимальных входных наборов данной   МБФ, лежащих на слое n – i булевого куба ранга n.

Назовем число n рангом типа Т, число v ненулевых компонент назовем весом типа Т, номер i первой слева ненулевой компоненты назовем левой границей типа Т, номер j первой справа ненулевой компоненты правой границей типа Т, сумму m всех компонент типа Т назовём мощностью типа. Тип Т называется максимальным, если при увеличении любой его компоненты на 1, полученный вектор не будет являться типом.

Будем считать, что тип МБФ Т1 больше типа Т2 МБФ если каждая компонента типа Т1 не меньше соответствующей компоненты типа Т2.

Построим графическое представление этого множества. Точкам будут соответствовать типы МБФ. Два типа будут соединены тогда и только тогда, когда тип . Далее, каждому типу МБФ поставим в соответствие число, в каноническом разложении которого степени простых будут соответствовать компонентам типа. Например, типу ранга 5  соответствует число .

ПРИМЕР. Построим такое представление для типов МБФ ранга 5 с таким набором простых чисел: 11, 5, 2, 3, 7, 13. Располагаем простые по порядку их номеров в натуральном ряду и начинаем от центральной компоненты типа. Вершины пронумеруем.

Описание: image001

Рис. 1. Структура типов МБФ ранга 5.

Каждой вершины соответствует натуральное число и такой тип МБФ:

1) 1      (0,0,0,0,0,0)

2) 11    (1,0,0,0,0,0)

3) 5      (0,1,0,0,0,0)

4) 25    (0,2,0,0,0,0)

5) 125  (0,3,0,0,0,0)

6) 625  (0,4,0,0,0,0)

7) 3125 (0,5,0,0,0,0)

8) 2      (0,0,1,0,0,0)

9) 10    (0,1,1,0,0,0)

10) 50  (0,2,1,0,0,0)

11) 250  (0,3,1,0,0,0)

12) 4      (0,0,2,0,0,0)

13) 20    (0,1,2,0,0,0)

14) 100  (0,2,2,0,0,0)

15) 8      (0,0,3,0,0,0)

16) 40    (0,1,3,0,0,0)

17) 200  (0,2,3,0,0,0)

18) 16    (0,0,4,0,0,0)

19) 80    (0,1,4,0,0,0)

20) 32    (0,0,5,0,0,0)

21) 160  (0,1,5,0,0,0)

22) 64    (0,0,6,0,0,0)

23) 320  (0,1,6,0,0,0)

24) 128  (0,0,7,0,0,0)

25) 256  (0,0,8,0,0,0)

26) 512  (0,0,9,0,0,0)

27) 1024 (0,0,10,0,0,0)

28) 3      (0,0,0,1,0,0)

29) 15    (0,1,0,1,0,0)

30) 75    (0,2,0,1,0,0)

31) 6      (0,0,1,1,0,0)

32) 30    (0,1,1,1,0,0)

33) 12    (0,0,2,1,0,0)

34) 60    (0,1,2,1,0,0)

35) 24    (0,0,3,1,0,0)

36) 180  (0,1,3,1,0,0)

37) 48    (0,0,4,1,0,0)

38) 96    (0,0,5,1,0,0)

39) 192  (0,0,6,1,0,0)

40) 384  (0,0,7,1,0,0)

41) 9      (0,0,0,2,0,0)

42) 45    (0,1,0,2,0,0)

43) 18    (0,0,1,2,0,0)

44) 90    (0,1,1,2,0,0)

45) 36    (0,0,2,2,0,0)

46) 72    (0,0,3,2,0,0)

47) 144  (0,0,4,2,0,0)

48) 288  (0,0,5,2,0,0)

49) 27    (0,0,0,3,0,0)

50) 135  (0,1,0,3,0,0)

51) 54    (0,0,1,3,0,0)

52) 108  (0,0,2,3,0,0)

53) 216  (0,0,3,3,0,0)

54) 432  (0,0,4,3,0,0)

55) 81    (0,0,0,4,0,0)

56) 405  (0,1,0,4,0,0)

57) 162  (0,0,1,4,0,0)

58) 324  (0,0,2,4,0,0)

59) 648  (0,0,3,4,0,0)

60) 1296  (0,0,4,4,0,0)

61) 243    (0,0,0,5,0,0)

62) 486    (0,0,1,5,0,0)

63) 972    (0,0,2,5,0,0)

64) 729    (0,0,0,6,0,0)

65) 1458  (0,0,1,6,0,0)

66) 2187  (0,0,0,9,0,0)

67) 4374  (0,0,1,7,0,0)

68) 6561  (0,0,0,8,0,0)

69) 19683  (0,0,0,9,0,0)

70) 59049  (0,0,0,10,0,0)

71) 7          (0,0,0,0,1,0)

72) 35        (0,1,0,0,1,0)

73) 14        (0,0,1,0,1,0)

74) 28        (0,0,2,0,1,0)

75) 56        (0,0,3,0,1,0)

76) 112      (0,0,4,0,1,0)

77) 21        (0,0,0,1,1,0)

78) 42        (0,0,1,1,1,0)

79) 84        (0,0,2,1,1,0)

80) 63        (0,0,0,2,1,0)

81) 126      (0,0,1,2,1,0)

82) 189      (0,0,0,3,1,0)

83) 378      (0,0,1,3,1,0)

84) 567      (0,0,0,4,1,0)

85) 1701    (0,0,0,5,1,0)

86) 5103    (0,0,0,6,1,0)

87) 49        (0,0,0,0,2,0)

88) 98        (0,0,1,0,2,0)

89) 147      (0,0,0,1,2,0)

90) 441      (0,0,0,2,2,0)

91) 1323    (0,0,0,3,2,0)

92) 343      (0,0,0,0,3,0)

93) 1029    (0,0,0,1,3,0)

94) 2401    (0,0,0,0,4,0)

95) 16807  (0,0,0,0,5,0)

96) 13        (0,0,0,0,0,1)

Такая структура является полурешёткой некоторой дистрибутивной решётки.

Получены следующие результаты.

Лемма 1. Структура типов МБФ изоморфна полурешётки натуральных чисел, упорядоченных по делимости.

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

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

Для построения последовательностей S и T будем использовать числа, находящиеся в узлах дерева типа МБФ (см. рис. 1). Для сокрытия периодичности ключа можно использовать при построении последовательностей S и T разные ранги типов МБФ. В работе [7] показано, что количество типов растёт экспоненциально с увеличением ранга. Это даёт возможность построения ключа равного по длине сообщения, что делает его достаточно криптостойким.

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

,

где  – символ шифротекста,  – символ открытого текста,  – длина алфавита.

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

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

Дешифрование будем проводить в обратном порядке.

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

 

Литература

1.       Гатчин Ю.А. Основы криптографических алгоритмов. Учебное пособие / Ю. А. Гатчин, А.Г. Коробейников– СПб: СПб ГИТМО (ТУ), 2002. – 29 с.

2.       Чмора А.Л. Современная прикладная криптография. 2-е изд. / А.Л. Чмора– М.:Гелиос АРВ, 2002. – 256 с. ил.

3.       Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях / М.А. Иванов– М.: КУДИЦ-ОБРАЗ, 2001. – 368 с.

4.       Коробейников А.Г. Математические основы криптографии. Учебное пособие / А. Г.  Коробейников–СПб: СПб ГИТМО (ТУ), 2002. – 41 с.

5.       Аграновский А.В. Классические шифры и методы их криптоанализа / А.В. Аграновский, А.В  Балакин, Р.А. Хади // М: Машиностроение: Информационные технологии, 2001 – № 10 – С. 40 – 45.

6.       Ткаченко В.Г. Деревья типов монотонных булевых функций и криптосистемы с блоками переменной длины / В.Г. Ткаченко, О.В.Синявский // Наукові праці ОНАЗ ім. О.С. Попова. – Одеса, 2009. – №2. – С. 32 – 42.

7.       Ткаченко В.Г. Перечисления типов монотонных булевых функций при синтезе цифровых схем / В.Г. Ткаченко // Наукові праці ОНАЗ ім. О.С. Попова. – Одеса, 2008. – №2. – С. 54 – 69.