Teoria_chisel_i_kriptozashita

λ=1. Тогда формула (10.17) показывает, что минимум Е(ро ) располага-

ется около значений А= К0,5 .

Хотя формула (10.12) является приближенным решением задачи, она является производящей функцией точного решения. Пусть е(К) означает точное ожидаемое значение po , когда число ключей равно К. В отличие

от е(К), уравнение (10.12) обеспечивает

∑(λА2 )К−1 exp( −λA2 )е(К), К (К −1)!

т.е. сумма членов е(К), взвешенных по вероятности так, что испытания Пуассона дают К – 1 ключей дополнительно к ключу 1. В принципе, мож-

но умножить сумму в выражении (10.19) на exp(λλ2 ), разложить в степенной ряд и представить коэффициент λК−1 как А2(К−1)е(К)/(К −1)!.

Этот результат для е(К) нежелателен, а уравнение (10.12) является достаточно точным. В эксперименте по оценке е(64) было проделано 2000 ис-

пытаний для каждого λ= 14 ,1, 4. Дробными значениями испытаний, ко-

торые были для В успешными, являются следующие: 0,31; 0,30; 0,37.

Т а б л и ц а 1

Е(ро ) для случайных конструкций

Теперь рассмотрим систематические коды с большим N с помощью другого обобщения кода — проективной плоскости. В отличие от случайного кодирования, когда N считается свободным параметром, эти коды определяют N. Этот недостаток компенсируется за счет малой величины Е(ро ) идругимидостоинствами, которыебудутизложенывданномразделе.

81

Для поля Галуа GF(q) можно создать проективное пространство PG(M,q) размерности М, в котором точки являются классами эквивалентности ненулевых векторов, теперь имеющих М + 1 компонент. Количество

Каждое множество точек, удовлетворяющее системе M – D независимых линейных однородных уравнений является подмножеством PG(D,q) размерности D, содержащем f(D) точек PА(M, q). Число подпространств размерности D в PG(M, q) будет

Выберем особое подпространство S размерности М–1, служащее в качестве «экватора». Идентифицируем файлы х с подпространством S. S имеет подпространства размерности 0, 1,..., М – 2, и таким образом, мы можем определить размерность s файлов как другой параметр конструкции. Рассмотрим случай s = 0; иной код может иметь s = 1. Для данных M,

Ключ m (точка) и файл х (размерности s) определяют единственное пространство размерности (s + 1), которое представляет у. Так как у содержит f (s + 1) точек и f (s) из них принадлежат S, то у содержит

Для нахождения po рассмотрим матрицу, соответствующую особой

паре х,х' . Следует заметить, что qs+1 ключей в выбранном столбце у не

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

(s+1) c х,х' . Если х и х' между собой пересекаются х∩ х' в пространст-

82

ве размерности r, то ячейка содержит qr+1 ключей пространств размерности (r + 1) через х∩ х' . В должен выбрать одну строку из qs+1 / qr+1 = qs −r ;

где h(r) — вероятность того, что случайно выбранный х' пересекает особый х в пространстве размерности r. В выражении (10.26) диапазоном суммирования будет 2s+1− М ≤ r ≤ s −1, обеспечивая 2s+1 ≥ М . Но

если 2s+1< М , то пересечение х∩ х' будет пустым. В этом случае

сумма (10.26) превосходит −1 ≤ r ≤ s −1. Теперь покажем, что формула

совместно с выражениями (10.21) и (10.26) дает po .

Коэффициент g( r,s )в (10.27) является числом различных подпространств х размерности r. Достаточно показать, что остальные члены вы-

ражения (10.27) дают вероятность того, что произвольно выбранный х' пересекает х в особом пространстве Н размерности r. Для данного х и подпространства Н мы можем найти М базисных векторов ео ,е1 ,...,еМ для S таких, что ео ,е1 ,...,еr расширяют Н, а ео ,е1 ,...,еs расширяют х. Каждое

х' содержит Н и, таким образом, имеет базис, состоящий из ео ,е1 ,...,еr .

Остальные s – r базисных вектора х' могут иметь следующий вид:

пересечению х в пространстве большей размерности, чем r. Это требование эквивалентно условию, что частичная сумма

из vi была бы линейно независима. Тогда viо расширяло бы подпространство хо размерности (М − s − 2 ) за счет еs+1 ,...,еМ . Коэффициент

83

А(r – s – 1, M – s – 2) в формуле (10.20) является числом путей для вы-

r — размерного пересечения с х, а знаменатель является числом N – 1 по-

сылок (отличных от х), из которых нарушитель выбирает х' .

Теперь q, M и s определяют N,K, A, pо . Таблица 2 дает некоторые конструкции, полученные выбором q = 2. Значения в таблице 2 выбраны для М = 2s + 2, так что К / А2 =1, как следует из выражений (10.16) и (10.17). Для данного К наименьшее значение po всегда достигается при

К / А2 =1. Подобное явление наблюдалось в случайных конструкциях, имеющих λ=1 (сравните с уравнением (10.17)). В то же время po равня-

ется приближенно 2 К−0,5 , что сравнимо с тем, что получено на проективной плоскости кода.

До настоящего времени нарушитель не контролировал выбор х' . Мы

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

конкретного х' ; он, по крайней мере, хочет ввести в заблуждение А заме-

ной х на пригодное ложное послание х' . Оптимальной стратегией для нарушителя должно быть стремление снова добиться (10.7), но он будет вы-

бирать х' , чтобы максимизировать ро(х, у,х' ) для каждого данного х, у.

Код с малым po , для случайно выбранного х' , в настоящее время выглядит достаточно убогим. Таблица 3 раскрывает более подробно особенности кода с q = 2, М = 12, s = 5, приведенного в таблице 2. Этот код имеет po = 0,0308, как следует из вычислений по формуле (10.23). Но не-

которые ложные послания х' пересекают хв пространстве размерности r = 4; если нарушитель подставит одно из них, его шанс успеха будет 0,5

(уравнение (10.25)). Код хорош для случайно выбранного х' только благодаря тому, что нарушитель обычно имеет посылку х' с r = –1 или 0.

84

ро(х, у,х' ) равномерно, а не в среднем. Систематический код достигает этого, если q велико. Согласно формуле (10.25), ро(х, у,х' ) ≤1/ q . К со-

жалению для А увеличение q приводит к снижению N. Тогда нужно искать

компромисс, выбирая q достаточно малым, чтобы получить N достаточно большим, а чтобы нарушитель имел достаточный шанс на успех, необходимо, чтобы 1/q было достаточно мало. В таблице 4 приведен типовой выбор между N и 1/q. Для таблицы 4 все элементы имеют приблизительно одинаковый размер ключа К = 216. Таблица 4 показывает обе вероятности успеха для нарушителя: 1/q, если нарушитель делает r = s – 1 и получает

усредненное значение (10,26), если он выбирает х' случайно. Если нару-

85

шитель игнорирует конструкцию с К / А2 ≠1, то средняя вероятность сильно не меняется. При снижении 1/q от 0,5 до 0,1 уменьшается размер logN с коэффициентом 3.

Т а б л и ц а 4

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

86

Библиография

1.Айерлэнд К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен. — М. : Мир, 1987. — 416 с.

2.Воронков Б. Н. Методическое пособие по разработке средств защиты информации в вычислительных сетях / Б. Н. Воронков, В. И. Тупота. — Воронеж : ЛОП ВГУ, 2000. — 112 с.

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

4.Математические и компьютерные основы криптологии : учеб. пособие / Ю. С. Харин [и др.]. — Минск : Новое знание, 2003. — 382 с.

5.Основы криптографии : учеб. пособие / А. П. Алферов [и др.]. — М. :

Гелиос АРВ, 2001. — 480 с.

6.Питерсон У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. —

М. : Мир, 1976. — 594 c.

7.Холл М. Комбинаторика / М. Холл. — М. : Мир, 1970. — 424 c.

8.Bauer R. C. A key distribution protocol using event markers / R. C. Bauer,

T.A. Berson, R. J. Feiertag // ACM Trans. Comput. Syst. — 1983. — Vol. 1, № 5. — P. 249 — 255.

9.Diffie W. New directions in cryptography / W. Diffie, M. Hellman // IEEE Trans. Inf. Theory, 1976. — Vol. 22, № 11. — P. 644 — 654.

10.Giblin P. J. Primes and Programming : An Introduction to Number Theory with Computing / P. J. Giblin. – Cambridge : Cambridge University Press, 1993. — 237 c.

11.Matyas S. M. Generation, distribution and instalation of criptografic keys /

S.M. Matyas, C. H. Meyer // IBM Syst. J. — 1978. — Vol.17, № 2. —

P.125 —137.

12.Needham R. M. Using encription for autentification in large networks for computers / R. M. Needham, M. D. Schroeder // Commun. ACM. — 1978. — Vol. 21. — P. 993 — 999.

87