авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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


ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА

2009 Математические основы криптографии №2(4)

МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОГРАФИИ

УДК 519.7

50 ЛЕТ КРИПТОГРАФИИ

В ТОМСКОМ ГОСУДАРСТВЕННОМ УНИВЕРСИТЕТЕ

Г. П. Агибалов

Томский государственный университет, г. Томск, Россия

E-mail: agibalov@isc.tsu.ru

Реферативный обзор результатов криптографических исследований научной шко лы прикладной дискретной математики Томского государственного университета за последние 50 лет.

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

Введение В 50-летней истории криптографии в Томском государственном университете (ТГУ) можно выделить три периода, назвав их условно военным, переходным и граж данским.

В первый период (1960-е годы) исследования по криптографии в ТГУ проводились по заказу оборонного предприятия и носили закрытый характер. Они велись, что на зывается, с чистого листа, в отсутствие какой-либо литературы по этому предмету, опираясь в основном на собственные представления задач криптографии и волю заказ чика. В значительной степени это были наивные исследования, но в их процессе было уяснено главное: создание стойких криптосистем, говоря современным языком, невоз можно без их тщательного криптоанализа. Именно алгоритмы криптоанализа неко торых поточных шифров и полученные с их помощью оценки стойкости последних и стали основными достижениями наших исследований этого периода. Именно таким путём мы доказали тогда непригодность линейных автономных автоматов в качестве генераторов ключевого потока. Некоторые результаты тех исследований, в частности относящиеся к генераторам нормальных рекуррентных последовательностей и к авто матным генераторам ключевого потока с функцией выхода в качестве ключа, до сих пор не превзойдены и по-прежнему актуальны.

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

Второй период развития криптографии в ТГУ (1970 – 1980-е годы) был периодом осмысления полученных результатов, их легализации и обобщения в рамках теории 50 лет криптографии в ТГУ экспериментов с автоматами [16] и приобщения к ним студентов. С позиций чистой криптографии это был вялотекущий период, протекавший в отсутствие заказчика и стимулов с его стороны, но в этот период нами была разработана применяемая и ныне технология решения комбинаторно-логических задач [15], каковыми собствен но и являются задачи анализа и синтеза криптоалгоритмов, а также была развита теория декомпозиции конечных автоматов [17] одного из инструментов создания со временных конечно-автоматных криптосистем с открытым ключом. Монография [17] остаётся до сих пор единственной отечественной книгой по декомпозиции автоматов.

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

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

1. Наша военная криптография 1.1. Ш и ф р у ю щ и е а в т о м а т ы А. Д. З а к р е в с к о г о В научной школе прикладной дискретной математики ТГУ криптографические ис следования занимают важное место на протяжении всех 50-ти лет её существования.

Впервые автор этой статьи прочитал научную работу по криптографии ещё в году, будучи студентом 4 курса университета. Это была рукопись статьи основателя школы, моего научного руководителя Аркадия Дмитриевича Закревского, посвящён ная применению конечных автоматов для шифрования с закрытым ключом. В ней для этой цели был предложен класс автоматов, называемых ныне шифрующими, в которых функция выходов биективна в каждом состоянии. К сожалению, А. Д. За кревский не принадлежит к числу тех, кому в ту пору было позволено заниматься криптографией, и его рукопись никогда не была опубликована под тем предлогом, высказанным чёрным рецензентом, что её результаты совершенно секретны. Для восстановления исторической справедливости мы впервые публикуем её в этом номере без каких-либо купюр и редакторской правки (см. [57]).

1.2. К р и п т о а н а л и з л и н е й н о г о а в т о н о м н о г о а в т о м а т а Тремя годами позже мне, уже аспиранту, было предложено участвовать в выпол нении закрытого хоздоговора для предприятия,известного ныне как ЦКБ Алмаз, по которому, с подачи А. Д. Закревского, мне предстояло исследовать класс шифров, в от крытой отечественной литературе известных теперь как шифры гаммирования и вхо дящих в класс современных поточных шифров. Как потом выяснилось, аналогичный договор заказчик уже имел с МВТУ им. Н. Э. Баумана, в котором в качестве генера тора гаммы (ключевого потока) предлагалось использовать двоичный регистр сдвига с линейной обратной связью максимального периода (LFSR). В первом же нашем от чёте заказчику было показано, что такой генератор не обладает никакой стойкостью к криптоанализу. Более того, мы показали, что столь же слабым генератором гаммы является всякий инициальный линейный автономный автомат над любым конечным 106 Г. П. Агибалов полем, а именно: любой такой автомат с размерностью состояния n эквивалентен LFSR длины n и восстанавливается (с точностью до эквивалентности) по отрезку его выход ной последовательности длиной не более 2n.

Конечный инициальный линейный автономный автомат над полем F = GF (q) за дается пятеркой объектов L = (S, Z, A, B, s0 ), где S = F n и Z = F m для некоторых натуральных n и m суть множества соответственно состояний и выходных символов его матрицы переходов и выходов размеров n n и n m со автомата, A и B ответственно с элементами в F и s0 S начальное состояние автомата. Число n называется размерностью автомата L. Он порождает последовательность выходных символов z = z0 z1..., где для любого целого t 0 символ zt вычисляется по прави лам: zt = st B и st+1 = st A. В его применении в роли генератора гаммы ключ шифра составляют матрицы A, B и начальное состояние s0, а гамму последовательность z.

В его криптоанализе предполагается известной верхняя граница N для размерности n.

Целью криптоанализа является раскрытие алгоритма генерации гаммы, а именно: с известным N и неизвестными A, B и s0 требуется построить (если возможно) некий алгоритм, который точно воспроизводит весь ключевой поток z по заданному конечно му его отрезку z0 z1... zl1. Ниже показывается, как такой алгоритм можно построить, если l 2N.

В самом деле, в последовательности состояний s0 s1..., где st+1 = st A для t 0, век тор sN является линейной комбинацией векторов s0, s1,..., sN 1, т. е. sN = N 1 cj sj j= для некоторых c0,..., cN 1 в F. После умножения последнего равенства на Ai для N каждого i 0 получим sN +i = j=0 cj si+j для всех i 0. После умножения, в свою очередь, этих равенств на B получим рекуррентные соотношения zN +i = N 1 cj zi+j j= 0. Решая систему первых N из них, т. е. для i = 0, 1,..., N 1, относитель для i но неизвестных c0,..., cN 1, получаем алгоритм вычисления из начального отрезка z0 z1... zN 1 последовательности z остальных ее членов zN +i, i 0, по рекуррентной N формуле zN +i = j=0 cj zi+j.

Это был 1964 год. Начались поиски стойких генераторов ключевого потока в классе нелинейных автономных автоматов. Так мы вышли на автоматные генераторы с функ цией выхода в качестве ключа и на генераторы нормальных рекуррентных последова тельностей (НРП) регистры сдвига с нелинейной обратной связью максимального периода. Для них мы разработали оптимальные алгоритмы криптоанализа и полу чили экспериментальные оценки их теоретической стойкости, или расстояния един ственности наименьшей длины отрезка последовательности на выходе генератора, достаточной для восстановления его ключа. Оптимальность алгортма как раз и озна чает тот факт, что он находит ключ генератора по отрезку ключевого потока длиной, равной расстоянию единственности.

1.3. К р и п т о а н а л и з а в т о м а т н о г о г е н е р а т о р а с ключевой функцией выхода Генератор ключевого потока, который мы здесь рассматриваем, представляет собой произвольный инициальный конечный автономный автомат G = (Q, Z, f, g, q(0)) с мно жеством состояний Q = {0, 1}n, множеством выходных символов Z = {0, 1}, с началь ным состоянием q(0), функцией переходов f : Q Q и функцией выходов g : Q Z, зависящей существенно от k переменных для некоторого k n. Последнее означает, что существуют функция h : {0, 1}k Z и натуральные i1 i2 · · · ik в {1, 2,..., n}, такие, что g(q1, q2,..., qn ) = h(qi1, qi2,..., qik ) для всех наборов (q1 q2... qn ) Q;

в этом случае i1, i2,..., ik суть номера существенных переменных функции g. Предполагает 50 лет криптографии в ТГУ ся, что ключом генератора G служит его функция g. Это значит, что криптоаналитику известны все атрибуты в G, кроме g. Ключевой поток z = z0 z1... на выходе G вы числяется по следующим рекуррентным уравнениям: zi = g(q(i)), q(i + 1) = f (q(i)), i 0. Он является периодической последовательностью с периодом не больше 2n. За дача криптоанализа генератора G заключается в определении его ключа по отрезку z0 z1... zl1 его ключевого потока. Наименьшее l, при котором это возможно, назы вается теоретической стойкостью генератора G. Предполагается, что длина l отрезка ключевого потока в задаче криптоанализа не превышает периода всего потока, так как иначе надобности в решении этой задачи не возникает.

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

Оба алгоритма построены по следующей общей схеме.

На вход алгоритма символ за символом поступает ключевой поток с генератора G.

После поступления символа z0 алгоритм располагает начальным состоянием q(0) и значением z0 = g(q(0)) искомой ключевой функции g на нем. В момент поступления очередного символа zi для i 1 алгоритм уже имеет состояния q(j) генератора и значения zj = g(q(j)) функции g на них для j = 0, 1,..., i 1, вычисляет очередное состояние q(i) генератора, получает значение zi = g(q(i)) функции g на нем, строит множество M покомпонентных разностей q(r) q(s) для всех таких векторов q(r), q(s) в {q(0), q(1),..., q(i)}, для которых zr = zs, и отбирает в M подмножество inf M всех минимальных по порядку векторов. Далее действия алгоритмов A и B расходятся.

В алгоритме A выясняется, единственно ли покрытие из k столбцов матрицы || inf M ||, строками в которой являются все векторы в inf M, и если нет, то на блюдается очередной символ ключевого потока. Это продолжается до тех пор, пока не будет получена матрица || inf M || с единственным покрытием (строк столбцами) мощ ности k. Номера столбцов последнего являются номерами существенных аргументов функции g.

В алгоритме B, в отличие от A, ключевой поток наблюдается до той поры, пока не выполнится условие единственности: все покрытия (строк) не более k0 столбца ми матрицы || inf M || образуют звезду, т. е. имеют общее пересечение ядро;

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

С нахождением существенных аргументов ключевой функции g оба алгоритма де лают одно и то же следующим образом. Пусть к этому моменту в алгоритм поступил отрезок ключевого потока длиной m. Тогда находится наименьшее l m, такое, что в наборах q(0), q(1),..., q(l 1) содержатся все наборы значений существенных пере менных функции g, после чего равная ей функция h на произвольном наборе значений ее существенных переменных определяется как h(qi1, qi2,..., qik ) = zj, где j находится из условий 0 j l 1 и q(j) = q1 q2... qn.

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

108 Г. П. Агибалов 1.4. К р и п т о а н а л и з г е н е р а т о р а нормальной рекуррентной последовательности В рамках договора с ЦКБ Алмаз были разработаны также оптимальный ал горитм криптоанализа генератора НРП и алгоритм вычисления его теоретической стойкости. Эти исследования базировались на классической работе Н. М. Коробова по нормальным периодическим системам (Изв. АН СССР, сер. матем. 1951. Т. 15. №1.

С. 17–46).

Для натуральных k 2иn 1 нормальная рекуррентная последователь ность значности k и порядка n, или сокращённо НРП(k, n), это такая последо вательность s = s0 s1..., в которой si E = {0, 1,..., k 1} для каждого i 0и n n n {si si+1... si+n1 : i = 0, 1,..., k 1} = E. Она периодическая с периодом k и обо значается как s0 s1... skn 1. Функция f : E n E, определяемая равенствами f (si si+1... si+n1 ) = si+n для i = 0, 1,..., k n 1, называется её генератором. При заданном начальном состоянии s0 s1... sn1 генератор f порождает НРП(k, n) s как решение системы рекуррентных уравнений si+n = f (si si+1... si+n1 ), i 0. В слу чае k = 2 генератор f любой НРП(k, n) представляется в виде f (x0, x1,..., xn1 ) = = x0 g(x1,..., xn1 ), где функция g(x1,..., xn1 ) = f (0, x1,..., xn1 ) называется по рождающей функцией этой последовательности.

Для начального отрезка s = s0 s1... sl1 некоторой НРП(k, n) s, имеющего дли ну l в границах n l k n, определяется область запрета как подмножество всех слов a1 a2... an в E n, в которых an есть символ в s, примыкающий справа к слову a1 a2... an1, когда оно в s встречается t-й раз, считая слева направо, и 1 t k.

Подмножество из q = k n1 1 слов в E n i1 i2... in (i = 1, 2,..., q) (1) называется особой системой, если все слова 12 13... 1n, i1 i2... in1 (i = 1, 2,..., q) различны, и возможно такое упорядочение слов в ней, при котором для любого j слово j2 j3... jn совпадает с одним из слов 12 13... 1n, i1 i2... in1 (i = 1, 2,..., j1). Особая система (1) называется соответствующей отрезку s, если 11 12... 1n = = 11 s0 s1... sn2 и её пересечение с областью запрета для s пустое.

Доказана теорема, согласно которой с отрезка s начинается единственная НРП(k, n), если и только если единственна особая система, соответствующая этому отрезку, и любое слово из E n1 по крайней мере (k 2) раз содержится среди слов si+1 si+2... si+n1 для i = 0, 1,..., l n.

Доказано также, что все НРП(k, n), начинающиеся с отрезка s, и только их, можно построить следующим методом.

Метод A3. Выбираем произвольную особую систему (1), соответствующую отрез ку s. Первые l знаков последовательности выписываем совпадающими соответственно со знаками данного отрезка. Выписывание остальных знаков, начиная с (l + 1)-го, про изводим по следующему индуктивному правилу: пусть уже выписаны l + j знаков s0 s1... sl+j1, (2) j 0;

выбираем такой знак sl+j E, что слово sl+jn+1 sl+jn+2... sl+j не встречается в последовательности (2) и совпадает с одним из слов выбранной особой системы лишь в случае, если все остальные слова вида sl+jn+1 sl+jn+2... sl+j1 z, где z = sl+j, в (2) уже встречаются, и приписываем его справа к (2). Построение заканчивается с 50 лет криптографии в ТГУ получением последовательности длиной k n. Это будет периодическая часть некоторой НРП(k, n).

Необходимые для метода A3 особые системы, соответствующие отрезку s, строятся следующим методом.

Метод B1. В первой строке выписываем любое слово 11 12... 1n = 11 s0 s1... sn2, не все знаки которого одинаковы и которое не принадлежит области запрета для s.

Все остальные строки, начиная со второй, строим по следующему индуктивному пра вилу. Пусть уже выписаны j 1 строк i1 i2... in (i = 1, 2,..., j 1) для j 2. Тогда в j-й строке выписываем любое такое слово j1 j2... jn E n, не принадлежащее об ласти запрета для s, для которого слово j1 j2... jn1 отлично от каждого из слов 12 13... 1n, i1 i2... in1 (i = 1, 2,..., j 1) и слово j2 j3... jn содержится среди них.

Построение методом B1 заканчивается с построением q строк.

Доказано, что методом B1 можно построить все особые системы, соответствующие заданному отрезку s, и только их.

Оптимальный алгоритм криптоанализа генератора НРП(k, n) выглядит следую щим образом: последовательность на выходе генератора наблюдается до тех пор, пока не будет получен её отрезок, удовлетворяющий условиям единственности его продол жения, после чего вся НРП, порождаемая генератором, восстанавливается методом A3.

Длина этого отрезка фиксируется как расстояние единственности (теоретическая стой кость) данной НРП.

Зкспериментальные исследования алгоритма на компьютере показали, что расстоя ние единственности для НРП(2, n) лежит в пределах от 2n1 1 до 2n 1, что свиде тельствует о высокой стойкости их генератора.

Это был 1965 год последний год нашего сотрудничества с ЦКБ Алмаз в этой области. К сожалению, по моему человеческому простодушию, в отношения нас с за казчиком вмешался генерал Козлов, и заказчику было запрещено прибегать к нашим криптографическим услугам. Через 40 лет история повторится, но это будет уже в дру гой стране, с другим заказчиком и при другом генерале.

2. Переходный период 2.1. П о д в ы в е с к о й э к с п е р и м е н т о в с а в т о м а т а м и Наши дальнейшие криптографические исследования проводились без ориентации на какого-либо заказчика, носили чисто научный характер и вплоть до признания за криптографией права защищать информацию в интересах не только государства, но и его граждан, касались, главным образом, теории экспериментов с автоматами, име ющей очевидный криптографический окрас и в то же время не ограниченной теми запретами, которые сопровождают практическую криптографию. Именно как резуль таты этой теории, хотя и с большой задержкой, были опубликованы приведённые выше алгоритмы криптоанализа и оценки теоретической стойкости линейного автономного автомата [4, 6], автоматного генератора с ключевой функцией выхода [2, 4, 7] и гене ратора НРП [3, 4, 8, 10].

В [12] показано, что любой инициальный линейный автомат над конечным полем с размерностью входного символа k и состояния n можно восстановить простым экс периментом длиной не больше 2n + k(n + 1).

Решена задача синтеза конечного автомата с минимальным числом состояний, ко торому присущ заданный кратный эксперимент [14, 16].

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

Дальнейшие теоретические исследования генератора НРП привели к построению аналитического выражения для точной верхней оценки его расстояния единственно сти [13]. Для k-значной последовательности порядка n она равна 2n 2, если k = 2 и n = 2, 3, 4, и равна k n 1 в остальных случаях. К сожалению, точная нижняя оценка для этой характеристики генератора НРП до сих пор не установлена. В эксперимен те на компьютере исследована сложность булевых функций, порождающих двоичные НРП [9], и показано, что среди таких функций с любым числом переменных n до с небольшим существуют функции, представимые в бесповторной ДНФ [17, 46]. Гипо теза автора о том, что это верно для любого натурального n, к сожалению, пока не доказана.

2.2. Д е к о м п о з и ц и я к о н е ч н ы х а в т о м а т о в Здесь мы дадим краткий обзор наших результатов из монографии [17], подразуме вая под декомпозицией автомата его представление автоматной сетью без обратных связей. Вместе с последней декомпозиция бывает каскадной, последовательной, парал лельной и параллельно-последовательной. Рассматриваются задачи характеризации (описания) всевозможных декомпозиций того или иного вида для заданного автомата, оценки их сложности и задачи соответствующей приводимости автоматов по состояни ям, входам, представлению и полугруппе. Для натуральных m 2 и k 1 автомат A называется каскадно m-приводимым по состояниям и k-приводимым по входам, если он представим каскадной сетью автоматов, каждый из которых имеет не более m состо яний и не более k входных символов соответственно. Автомат A каскадно приводим по представлению, если он допускает каскадную декомпозицию на компоненты, не представляющие в отдельности автомат A. Он каскадно приводим по полугруппе, если для него существует каскадная декомпозиция на компоненты, полугруппы которых не делятся его полугруппой. Аналогично определяются все эти виды последовательной, параллельной и параллельно-последовательной приводимости автомата.

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

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

Известно (H. P. Zeiger), что любой конечный автомат можно разложить в каскад ную сеть из перестановочно-возвратных (ПВ-) автоматов. Нами доказано, что в такой 50 лет криптографии в ТГУ сети, построенной для автомата с n 3 состояниями методом Зейгера, гарантиру ющим делимость полугруппы автомата группами компонент сети, число последних может достигать 2n1 1. Показано также, что без требования групповой делимости всякий автомат с n состояниями разлагается в каскадную сеть из ПВ-компонент, число которых не первышает n1. С применением аппарата СНУП доказано, что эта оценка точная.

Автомат с n 2 состояниями каскадно приводим по представлению, если и только если он не является константным автоматом 2-го порядка.

Автомат каскадно m-приводим по состояниям, если и только если каждый простой делитель его полугруппы изоморфен группе подстановок степени m.

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

Автомат параллельно m-приводим по состояниям, если и только если его полугруп па делит прямое произведение полугрупп преобразований множества {1,..., m 1}, взятых в степенях, показатели которых не превосходят их порядков в степени nn.

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

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

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

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

Генераторы НРП интересны не только как источники ключевого потока, но и, по добно LFSR, как компоненты других более сложных криптоалгоритмов. В этой связи представляет интерес наше утверждение, доказанное конструктивно в [17], о том, что для любых натуральных m и n m любой конечный автомат c m состояниями можно разложить в каскадную сеть из триггеров и генераторов НРП порядка n.

Исследуя автономные автоматы как генераторы ключевого потока, мы выяснили в [17], при каких необходимых и достаточных условиях для заданных натуральных m и k произвольный автономный автомат с m состояниями можно представить каскадной или параллельной сетью автоматов с числом состояний меньше m и числом входных символов меньше k в каждом. В случае каскадной сети и k 2, m 2 это возможно, если и только если m p, где p наибольший простой делитель периода полугруп пы автомата, а в случае параллельной сети и k 1, m 2 если и только если a a m max(r, p ), где r индекс полугруппы автомата и p наибольший сомножитель в каноническом разложении её периода.

112 Г. П. Агибалов 2.3. Р а з в и т и е а л г о р и т м и ч е с к о й б а з ы для компьютерной криптографии Эти исследования являются частью общего направления нашей научной школы в ТГУ автоматизации решения комбинаторных задач прикладной дискретной ма тематики. Это значит, что конечными результатами исследований в этом направлении должны быть алгоритмы решения комбинаторных дискретно-математических задач, аттестованные в эксперименте на электронной вычислительной машине (ЭВМ, или по-современному компьютере). Фактически уже тогда речь шла о создании нового направления в математике компьютерной дискретной математики. Первые кирпи чи в фундамент этой науки заложил А. Д. Закревский [11], предложивший системы подмножеств конечных множеств представлять в ЭВМ при помощи булевых и троич ных матриц и разработавший иерархическую систему математических операций над такими матрицами и эффективные алгоритмы их выполнения. Система охватывает широкий спектр операций от простейших (нахождение минимального столбца и максимальной строки) до предельно сложных (кратчайшее покрытие булевой матри цы или минимальное разбиение множества ее столбцов на совместимые подмножества, например). Фундаментальное и прикладное значение этой системы состоит в том, что через операции в ней легко выражаются алгоритмы решения многих задач как в самой дискретной математике, так и в ее приложениях и не только к синтезу дискретных автоматов, но и к математической логике и криптографии.

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

поисковые когда в конечном множе стве требуется найти хотя бы один комбинаторный объект (если он есть) с задан ным свойством;

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

Отличительными особенностями всех этих задач являются:

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

2) дискретность данных, исключающая возможность приближённых вычислений и применения традиционных методов вычислительной математики;

3) высокая вычислительная сложность, часто исключающая существование эффек тивного решения задачи в общем случае;

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

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

Формально эта технология решения комбинаторных задач изложена в книге [15], где можно найти и алгоритмы решения многих конкретных задач, разработанные с её применением. На момент разработки они были лучшими среди известных алгоритмов решения тех же задач.

В дальнейшем обход дерева поиска с возвращением был распараллелен для выпол нения на многопроцессорной вычислительной системе кластерного типа, о чём см. в от дельной статье [56] этого номера.

3. Наша гражданская криптография С развитием в стране гражданской криптографии наши криптографические ис следования испытали второе рождение. Оно случилось на стыке двух тысячелетий в непосредственной связи с открытием в ТГУ специальности Компьютерная безопас ность со специализацией криптографической направленности. Научная школа при кладной дискретной математики ТГУ стала базой для подготовки кадров по новой специальности. Криптографию в ТГУ мы начали преподавать ещё раньше и задолго до того, как в стране появилась первая книжка по этому предмету. Именно резуль таты наших собственных научных исследований в области криптографии прошлых лет стали основой для постановки в ТГУ и криптографических дисциплин, и крипто графической специализации в целом. Ныне в этом деле, наряду с фундаментальными теоремами криптографии [30], значимое место занимает и научная продукция наших современных криптографических исследований, проводимых с активным участием мо лодёжи, в том числе студентов и аспирантов.

Предмет этих исследований составляют кодовые шифрсистемы [20], системы поли номиальных уравнений над конечным полем и их применение в криптоанализе сим метричных шифров [21, 23, 26, 27, 36, 37, 39, 45, 47, 52], криптографические прото колы [19, 22], булевы функции с криптографическими свойствами и их применение в синтезе поточных шифров [24, 34, 35, 40], вероятностные схемы поточного шиф рования [31, 43, 49], инволютивные шифры [32, 42], теоретико-числовые алгоритмы, применяемые в анализе и синтезе криптосистем с открытым ключом, [19, 33, 38, 48], генераторы ключевого потока [25, 41, 46, 54], шифрующие автоматы [51], итератив ные блочные шифры с аддитивным раундовым ключом [52], схемы разделения секре та [50, 53], параллельная генерация сочетаний, перестановок и разбиений для крипто графических применений [28, 44] и др.

3.1. К р и п т о а н а л и з к о д о в ы х ш и ф р с и с т е м [20] Рассматриваются кодовые шифрсистемы над полем GF(2). Они строятся на осно ве двоичных кодов, исправляющих ошибки, и, как все шифрсистемы, делятся на два класса симметричные, или с закрытым ключом, и несимметричные, или с откры 114 Г. П. Агибалов тым ключом. Для первых предложен вероятностный алгоритм криптоанализа с целью нахождения ключа при возможности выбора сообщений, для вторых детерминиро ванный алгоритм криптоанализа с целью нахождения сообщения при известных от крытом ключе и криптограмме.

Шифрование в симметричной кодовой шифрсистеме описывается уравнением y = xG e, (3) где x булев вектор с k компонентами, являющийся сообщением;

y булев век тор с n компонентами, являющийся криптограммой;

G булева матрица размера kn, которая является закрытым ключом и представляет собой порождающую матри цу некоторого двоичного линейного (n, k)-кода, исправляющего ошибки кратности до t 1;

e случайный булев вектор ошибки с n компонентами, который содержит не более t единиц. Задача криптоанализа, решаемая в этом случае, так выбрать значе ния вектора x, чтобы по ним и соответствующим значениям вектора y = xG e при случайных и неизвестных значениях вектора e можно было найти матрицу G.

Выберем в качестве значений x единичные векторы длиной k, беря каждый из них некоторое число s 3 раз. Тогда рассматриваемая задача криптоанализа сводит ся к решению k раз следующей частной задачи: пусть булевы векторы g, y1,..., ys, e1,..., es длины n удовлетворяют системе уравнений yi = g ei, i = 1,..., s, где в j-й раз для j = 1,..., k вектор g есть j-я строка искомой матрицы G и векторы e1,..., es случайные веса t;

требуется, зная y1,..., ys, найти вектор g = g1...gn.

Эта частная задача решается следующим образом: пусть yi = yi1 yi2... yin для i = 1,..., s;

тогда для каждого j = 1,..., n подсчитываем вес wj вектора y1j y2j... ysj и полагаем gj = 1, если wj s/2, и gj = 0 в противном случае;

вектор g = g1... gn принимаем за решение. Если t n/2, s = 2r + 1, r 1иp вероятность принятия компонентой векторов ei значения 1, то вероятность совпадения g с искомым g равна P = r Cs pi (1 p)si. Например, при n = 19, s = 29 и t 4 имеем P = 0, 999.

i i= В эксперименте на компьютере построены зависимости от n и t максимального и среднего арифметического значений числа s, при котором g = g. Из них следует, что с ростом n отношение s/n убывает. Например, при t = n/4 и n = 32, 64, 128, 256, среднее значение такого s равно 4, 5, 5, 6, 8 соответственно.

В случае несимметричной кодовой шифрсистемы в уравнении шифрования (3) мат рица G является открытым ключом, и решаемая задача криптоанализа в этом слу чае состоит в решении уравнения (3) с известными G и y относительно неизвестного x = x1 x2... xk при неизвестном булевом векторе e веса, не превосходящего заданно го числа t. Это есть задача декодирования для кода, порождённого матрицей G, и в общем случае (для произвольной матрицы G) не решаема за полиномиальное время.

Булев вектор = a1 a2... ai, где i k, называется её частичным решением, если не превышает величины t вес вектора e() = y a1 g1 · · · ai gi, где gj для j = 1,..., k есть j-я строка матрицы G;

в этом случае вектор x = 0ki есть (полное) решение задачи.

Поиск частичного решения осуществляется обходом дерева поиска с возвращени ем, в котором последовательно порождаются в качестве кандидатов на место префикса в нём булевы векторы длиной не больше k. Это делается при помощи алгоритма ветв ления, выбирающего вслед за вектором a1 a2... ai1 поочерёдно всевозможные векторы a1 a2... ai, и условия возвращения, при котором выбранный вектор = a1 a2... ai для i k не может быть префиксом частичного решения. Последнее выполняется, если 50 лет криптографии в ТГУ истинен оценочный предикат t0 + t t, где t0 есть число номеров одновременно еди ничных компонент вектора e() и нулевых столбцов матрицы H, равной матрице G без первых i строк, и t вычисляется следующим образом. Пусть m есть число клас сов равных ненулевых столбцов в H, и s-й из них, s = 1,..., m, состоит из столбцов с номерами r1,..., rp. Обозначим ts0 и ts1 количество нулей и единиц соответственно среди компонент вектора e(), имеющих номера r1,..., rp. Пусть ts = min(ts0, ts1 ).

Тогда t = m ts.

s= Эффективость этого алгоритма в значительной степени зависит от порядка компо нент в векторе x. Его оптимизация в каждом конкретном случае является отдельной задачей.

3.2. С и с т е м ы у р а в н е н и й н а д к о н е ч н ы м п о л е м Возможность применения решений систем алгебраических уравнений в крипто анализе шифров обусловлена возможностью описания ими (системами) зависимостей в шифрах между символами известных открытого и шифртекстов и неизвестного за крытого ключа. В криптоанализе генераторов ключевого потока в поточных шиф рах система уравнений связывает известные символы потока с неизвестными сим волами ключа. Основными средствами в решении систем уравнений над конечным полем в наших исследованиях служат дерево поиска с возвращением и метод его со кращённого обхода, составляющие основу созданной нами ранее технологии решения комбинаторно-логических задач [15]. Таким путём построены, в частности, алгоритмы криптоанализа сжимающего и самосжимающего генераторов ключевого потока [23], а для сжимающего генератора, кроме того, получены экспериментальные оценки его теоретической стойкости [26]. Эффективность этой технологии применительно к дру гим (не криптографическим) комбинаторным задачам демонстрируется в обзорной статье [55] этого номера.

Обход дерева поиска допускает эффективные процедуры распараллеливания на многопроцессорных вычислительных системах кластерного типа [29]. Как это делается в общем виде, а также для конкретных комбинаторных задач, имеющих криптогра фические применения, в том числе и для решения систем уравнений над конечным полем, демонстрируется в ещё одной обзорной статье [56] данного номера.

Для решения систем уравнений над конечным полем предложен метод линеари зационного множества [21, 39]. Последнее это подмножество переменных систе мы со свойством: при фиксации любых их значений система уравнений превращается в линейную. Метод состоит в поочерёдной подстановке в систему всевозможных набо ров значений переменных линеаризационного множества и в решении получающейся в каждом случае линейной системы методом Гаусса. Его сложность оценивается экспо нентой от числа переменных в линеаризационном множестве. Предложен алгоритм по строения линеаризационного множества наименьшей мощности обходом дерева поиска с возвращением;

разработаны, реализованы и исследованы параллельные алгоритмы решения этой задачи и задачи решения системы линейных уравнений [27, 36, 37, 47, 56].

3.3. Л и н е а р и з а ц и о н н а я а т а к а Определение неизвестного ключа криптоалгоритма как решение его системы уравнений методом линеаризационного множества назвается линеаризационной ата кой [21]. В двоичном случае её вычислительная сложность оценивается числом 2k, где k мощность используемого линеаризационного множества. Так, для генератора ключевого потока Gee линеаризационное множество образуют компоненты ключа, составляющие начальное состояние одного из его регистров, и k совпадает с длиной 116 Г. П. Агибалов этого регистра. Это значит, что фактическим ключом генератора Gee является состо яние только одного его регистра. Эти утверждения верны и для ряда других генерато ров ключевого потока, в том числе для генераторов с альтернативным управлением, скалярного умножения и мультиплексорного. Известно, что корреляционная атака на генератор Gee с длинами регистров n1, n2, n3 имеет сложность 2n1 + 2n2 + 2n3, в то время как сложность линеаризационной атаки на него равна одному из слагае мых последней суммы. Показано также, что сложность линеаризационной атаки на пороговый генератор ключевого потока не превосходит 2m, где m его расстояние единственности.

3.4. В е р о я т н о с т н ы е с х е м ы симметричного поточного шифрования Предложены два класса вероятностных схем симметричного поточного шифрова ния над конечным полем [31]. Генератор ключевого потока в них функционирует как фильтрующий генератор на основе LFSR максимального периода. В схемах первого класса в качестве функции фильтрации выступает комбинация линейной и нелиней ной функций так, что первые n символов ключевого потока, где n длина регистра, являются значениями линейной функции, а остальные символы значениями нели нейной функции (на соответствующих состояниях регистра). Линейная функция слу жит ключом шифра (или определяется по нему), а начальное состояние s0 регистра случайным параметром шифрования. Расшифрование сводится к нахождению s путем решения системы линейных уравнений и воспроизведению ключевого потока, а дешифрование требует для этого решения системы нелинейных уравнений. В схе мах второго класса, в отличие от первого, случайное начальное состояние генератора ключевого потока складывается покомпонентно с ключом шифра, как в одноразовом блокноте.

Дано общее определение вероятностной поточной шифрсистемы PSC [43], охва тывающее все известные шифрсистемы этого класса. В её составе ключевая система и блоки рандомизации и шифрования. Первая предназначена для выработки ключей инициализации, свидетельства и генератора. Блок рандомизации состоит из источни ка (множества) рандомизаторов и узлов свидетельства и инициализации. Формально узел свидетельства является некоторым шифром и предназначен для создания сви детельства рандомизатора в зависимости от ключа свидетельства. Формально узел инициализации является функцией и предназначен для выработки вектора инициали зации для блока шифрования в зависимости от рандомизатора и ключа инициализа ции. Блок шифрования состоит из конечно-автоматного генератора ключевого потока, создаваемого в зависимости от ключа генератора и вектора инициализации, и шифра, предназначенного для зашифрования открытого текста и расшифрования шифртек ста по ключевому потоку. При фиксированных ключах системы процесс шифрования выполняется в следующем порядке: выбирается случайно рандомизатор и последо вательно вычисляются его свидетельство, вектор инициализации, ключевой поток и шифртекст. В канал связи передаются свидетельство рандомизатора и шифртекст.

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

В литературе по криптографии самосинхронизирующиеся поточные шифры пред ставлены только примерами так называемых регистровых шифров, в которых свойство 50 лет криптографии в ТГУ самосинхронизации достигается за счет использования в генераторе ключевого пото ка (ГКП) регистра сдвига, через который пропускается шифртекст, и нет определения самосинхронизирующегося поточного шифра в общем виде, что, понятно, служит тор мозом в развитии теории таких шифров. В работе [49], для преодоления этого недо статка, формализовано понятие самосинхронизирующегося с задержкой поточного (коротко: с/п- ) шифра, в котором на каждом ключе в роли ГКП служит конечный автомат Мура, и доказано, что в случае сильной связности последнего всякий такой шифр функционально неотличим от некоторого регистрового шифра (с/п- )-шифра на регистре сдвига длиной. Регистровый шифр определён так, что может исполь зоваться как вероятностный (с/п- )-шифр. В этом случае шифртекст вычисляется в нём как функция ключа и случайного состояния регистра и передаётся вместе с этим состоянием получателю, который получает открытый текст после отбрасывания первых символов из результата расшифрования принятого сообщения по ключу и любому состоянию регистра дешифратора.

3.5. Б у л е в ы ф у н к ц и и с к р и п т о г р а ф и ч е с к и м и с в о й с т в а м и Показано, каким образом можно построить все булевы функции, сохраняющие ли нейную сложность произвольной линейной рекуррентной последовательности (ЛРП) над полем из двух элементов, и оценивается их число, которое для m-последователь ности порядка n равно 2(2n 1)(2n 1)/n [24]. Доказано, что булевы функции, тож дественные своим переменным или отличающиеся от них только на нулевом наборе значений их всех, сохраняют линейную сложность любой двоичной ЛРП, а линейные булевы функции, не тождественные нулю и своим переменным, и функции, отлича ющиеся от них только на нулевом наборе, сохраняют линейную сложность всякой m-последовательности над полем из двух элементов [34].

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

предложен графический тест на отсутствие у булевой функции запрета заданной дли ны l, и на его основе сформулированы алгоритмы порождения всех запретов длины l данной функции и всех функций без запрета данной длины l [35].

Доказана теорема о связи порядка устойчивости булевой функции с порядками устойчивости коэффициентов её разложения Шеннона, и на её основе сформулиро ван рекурсивный метод построения булевых функций от заданного числа переменных с заданным максимальным порядком устойчивости [40].

3.6. Т е о р е т и к о - ч и с л о в ы е а л г о р и т м ы в к р и п т о г р а ф и и Исследованы два варианта реализации алгоритма Адлемана дискретного логариф мирования в Z для простого p [33]. В первом варианте в систему сравнений для ло p гарифмов простых чисел из факторной базы не включаются сравнения с ненулевыми необратимыми в Z коэффициентами на диагонали треугольной матрицы системы, p так что система имеет единственное решение, а во втором в систему включают ся все возможные сравнения, но из её многочисленных решений отбирается только то, которое состоит из всех требуемых логарифмов. Варианты сравнивались по ско рости логарифмирования на компьютере при разных размерах модуля и факторной базы. Эксперименты показали в пользу второго варианта. Доказана корректность ал горитма Адлемана для дискретного логарифмирования по простому модулю p в любой циклической подгруппе G группы Z с факторной базой, не обязательно целиком со p держащейся в G. В действительности факторная база в этом случае вместе с элементом x Z может содержать и все корни s-й степени из xs по модулю p, где s находится из p 118 Г. П. Агибалов условий: p = sq + 1 и q простое число. Такое расширение факторной базы упрощает применяемое в алгоритме разложение чисел в Z на множители из факторной базы и p не увеличивает размерности решаемой системы сравнений.

В эксперименте на компьютере исследовались [19] следующие алгоритмы фактори зации чисел RSA n = pq: Div1 последовательным делением n на простые числа от до n1/2, Div2 последовательным делением n на простые числа от n1/2 до 2, Olv методом Дж. Г. Олвея и Fer методом Ферма. Установлено, что на числах длиной до 64 бит среди этих алгоритмов наиболее медленный алгоритм Olv и наиболее быстрые Fer и Div2, и, кроме того, время работы каждого из последних двух растёт линейно с ростом |p q|.

В [19] представлены также результаты экспериментального исследования на персо нальном компьютере прошлого века длительности некоторых известных атак на шифр RSA с общим модулем, циклической и обобщённой циклической, с малой экспонен той шифрования и адаптивной атаки с выбором шифртекста. Как показал экспери мент, последние две атаки выполняются за пренебрежимо малое машинное время, первая на числах длиной до 1500 бит за время в пределах нескольких минут, а цик лические атаки нередко приводят к результату за приемлемое машинное время (на числах длиной в несколько десятков бит в пределах от долей секунд до получаса).

Предложены параллельные реализации на суперкомпьютере кластерного типа двух -метода Полларда и квадратичного решета [38].

алгоритмов факторизации чисел В обоих случаях распараллеливается процедура порождения последовательности необ ходимых пар чисел, а именно: каждый процессор, кроме управляющего, порождает свою подпоследовательность независимо от других. Кроме того, в первом случае про цессор осуществляет разложение порождаемых им вторых чисел по факторной ба зе и результат разложения вместе с порождёнными парами отсылает управляющему процессору. Для обоих алгоритмов произведено сравнение последовательных и парал лельных реализаций на кластере с 9 двухпроцессорными компьютерами, работающими с тактовой частотой 650 МГц. Обнаружено, что ускорение (отношение времени рабо ты последовательной программы ко времени работы параллельной) с ростом числа процессоров заметно отстаёт от него. Самое большое число, которое удалось фактори зовать по -методу Полларда параллельной программой на 12-процессорном кластере, имеет длину 128 бит. На это ушло 103 часа машинного времени.

Проведено экспериментальное сравнение двух алгоритмов генерации доказуемо простых чисел алгоритма Маурера и алгоритма из Российского стандарта элек тронной цифровой подписи (ГОСТ Р34.10-94) и выявлен следующий недостаток обо их: иногда они ошибочно пропускают простые числа как не прошедшие проверку по основанию 2, но признаваемые простыми проверкой по основанию 3 [48]. Кроме того, в [19] установлено, что алгоритм из стандарта ГОСТ Р34.10-94 несколько проигрывает по скорости алгоритму генерации сильных простых чисел Гордона, что объясняется применением в последнем более быстрой процедуры проверки числа на простоту по вероятностному алгоритму Миллера Рабина.

3.7. Г е н е р а т о р ы к л ю ч е в о г о п о т о к а Представлены два варианта системы логических уравнений сжимающего генера тора [25]. Уравнения в первом варианте рекуррентные, во втором моделируют алго ритм сортировки пузырёк. В эксперименте на компьютере исследованы различные варианты программной реализации генератора Fish. Наиболее быстрый вариант, в ко тором обращение к массивам регистров генератора осуществляется через указатели 50 лет криптографии в ТГУ без использования смещения, на компьютере с частотой 700 МГц порождает ключе вой поток длиной 100 Мбит за 0,441 с.

В экспериментах на современных компьютерах более тщательно исследована [41] эффективность алгоритмов A и B криптоанализа конечно-автоматного генератора G ключевого потока с функцией выхода в качестве ключа (см. п. 1.3). Выяснено, в част ности, что при известном числе k существенных переменных ключевой функции длина отрезка ключевого потока, требуемого для ее определения, сравнительно не велика, в то время как при известной только верхней границе k0 для k длина требуемого от резка ключевого потока много больше первой и быстро растет с ростом k0. Это объяс няется тем, что во втором случае, особенно если k0 k, велико количество ложных ключей, для отсева которых как раз и требуется длинный отрезок ключевого пото ка. Кроме того, в этом случае возможны эквивалентные ключи, и тогда проверяемое алгоритмом B условие единственности не выполняется при любой длине ключевого потока. Этот недостаток алгоритма B преодолевается в следующем алгоритме C, ре шающем задачу криптоанализа G в тех же предположениях, что и B. Его применение предваряется этапом предвычислений, на котором в компьютерном эксперименте с генератором G c заданными параметрами n и k = 1, 2,..., k0 определяется ожидае мое максимальное значение l(n, k) длины кратчайшего отрезка ключевого потока, по которому алгоритм A находит решение своей задачи ключевую функцию g при из вестном числе k ее существенных аргументов. Затем алгоритм C определяет ключевую функцию g применением алгоритма B к отрезку ключевого потока длиной l(n, k) + для небольшого 0: сначала в предположении, что k = k0, затем в предположении, что k = k0 1, и так далее. Если при очередном предполагаемом k алгоритм B не находит g по отрезку ключевого потока длиной l(n, k) +, то k уменьшается на 1.

Экспериментальные результаты компьютерного моделирования алгоритма C свиде тельствуют о том, что алгоритм C в десятки раз эффективнее алгоритма B и по длине требуемого ключевого потока, и по времени выполнения.

Предложен алгоритм с вычислительной сложностью O(2n /n), позволяющий по за даваемым значениям параметра (ключа) путем склеивания циклов, порожденных цик лически минимальными числами, строить двоичные нормальные рекуррентные после довательности порядка n так, что при разных значениях ключа с равной вероятностью строятся попарно неэквивалентные последовательности из множества большой мощ ности [54]. В случае простого n последняя равна числу m=1 mCm /n, а длина ключа n n в битах числу ((2n 2)[log(n1)]/(n1). Основной инструмент в этом построении циклически минимальное число определяется как всякое такое целое неотрицатель ное число, которое не уменьшается при любом циклическом сдвиге влево его двоичного представления.

3.8. И н в о л ю т и в н ы е ш и ф р ы [32, 42] Инволютивный шифр определяется как пара C = (X, Q), где X конечное мно жество сообщений и криптограмм и Q подмножество множества инволюций на X, т. е. подстановок q : X X со свойством q(q(x)) = x для каждого x X. В нём каж дая инволюция q Q является одновременно ключом и операциями шифрования и расшифрования по ключу q.

Известно, что любая инволюция разлагается в произведение независимых циклов длиной не более 2. Кроме того, доказано, что количество rp всех инволюций на множе стве X мощности p подсчитывается по рекуррентной формуле rp = rp1 + (p 1)rp2, где r1 = 1, r2 = 2.

120 Г. П. Агибалов Подмножество Z X называется тестом для q Q, если для любого s Q {q} найдётся z Z, что q(z) = s(z). Его можно получить, взяв по одному элементу из каждого цикла длины 2 в разложении q. Его мощность не более |X|/2.

Тест для каждого q Q называется тестом для C. Тест c наименьшим числом элемен тов называется кратчайшим. Такой тест для C можно построить как подмножество в X наименьшей мощности, которое пересекается с каждым циклом длины 2 в любой инволюции из Q. Эта задача решается как задача о кратчайшем покрытии булевой матрицы [11].

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

Пусть 4|p = |X|, эквивалентность на X со всеми двухэлементными классами и C = (X, Q ) инволютивный шифр, где для инволюции q на X q Q x, y X(xy (q(x) = x q(y) = y q(x)q(y))).

Доказано, что число всех инволюций в C равно r = (p/2)!/(p/4)! и что мощность теста для любой из них равна p/4.

Произвольная инволюция q Q индуцирует на множестве X/ всех классов эк вивалентности инволюцию q по правилу q ({x, y}) = {q(x), q(y)}. Тест для C мож но построить, выбрав по одному классу из каждого цикла в подстановке q для всех q Q и взяв из каждого выбранного класса по одному элементу. Этот тест будет крат чайшим при наименьшем числе различных выбранных классов. Такой выбор можно осуществить опять же как решение задачи о кратчайшем покрытии булевой матрицы.

Пусть далее X = An для некоторых натурального n и алфавита A и для всех q Q и i {1, 2,..., n} определены функции qi : X A так, что q(x) = q1 (x)q2 (x)... qn (x) для любого x X. Пусть также B = {i1,..., ik } {1, 2,..., n}, i1 · · · ik и qB (x) = qi1 (x)... qik (x). Инволюции q и s на X называют B-неотличимыми и пишут q B s, если qB (x) = sB (x) для всех x X. Говорят, что инволюция q Q определяется в C множеством B однозначно, или B-определима в C, если s Q(s B q s = q).

Смысл последних понятий следующий. Если V есть число всех инволюций в Q, B-неотличимых от q Q, то 1/V есть вероятность, с которой ключ q шифра C опре деляется своими компонентами с номерами в B. Ключ q можно считать слабым в C, если найдётся подмножество B, при котором число V близко к 1, в частности когда B определяет q в C однозначно.

Таким образом, встают задачи: 1) найти V для заданных Q, q Q и B {1,..., n};

2) найти (если возможно) хотя бы одно B {1,..., n}, для которого B-определим в C ключ q Q;

3) для заданного B оценить число всех B-определимых в C ключей q Q в зависимости от параметров шифра и мощности B. Решения этих задач для шифра, содержащего всевозможные инволюции на множестве сообщений, и для шифра со всеми инволюциями, разложимыми в произведение циклов длины 2, представлены в работе [42].

3.9. С х е м ы р а з д е л е н и я с е к р е т а Предложена схема разделения секрета, в которой в качестве секретов использу ются инволюционные подстановки на декартовой степени конечного множества, опре деляемые однозначно проекциями последней, включающими авторизованные группы участников, представленных своими номерами, а в качестве долей секрета проекции набора функций, которыми задается секрет [50].

50 лет криптографии в ТГУ Базовые понятия (структура доступа сд, схема разделения секрета срс, совер шенная срс, скорость срс, идеальная срс, сд и срс Брикелла и др.), а также основопо лагающие теоремы теории совершенных схем разделения секрета (о связи идеальных совершенных срс с матроидами, об условиях реализуемости сд схемой Брикелла, о соотношении между параметрами пороговой сд и реализующей ее схемы Брикелла и др.) вместе с оригинальными доказательствами систематизированы в [53].

3.10. Ш и ф р у ю щ и е а в т о м а т ы В эксперименте на компьютере исследована стойкость автоматного шифра с зак рытым ключом к атакам на основе шифртекста, с известным открытым текстом и с выбором открытого текста [51]. Атаки применяются к шифрам 1-го типа, где клю чом служит только начальное состояние автомата, и к шифрам 2-го типа, где в ключ входят одновременно начальное состояние и некоторое подмножество переходов в ав томате. Первые две атаки осуществляются грубой силой, третья атака на автоматы 1-го типа проводится как простой безусловный диагностический эксперимент, а на ав томаты 2-го типа как простой безусловный установочный эксперимент над прямым произведением доопределений заданного частичного автомата с последующим про ведением диагностического эксперимента, как в предыдущем случае. Компьютерное моделирование данных атак демонстрирует нестойкость шифров 1-го типа к атакам с выбором открытого текста по той простой причине, что почти все шифрующие автоматы допускают короткую диагностическую последовательность.

3.11. Д и ф ф е р е н ц и а л ь н ы й к р и п т о а н а л и з Среди научных достижений последних 15 – 20 лет в области криптоанализа важ ное место занимает дифференциальный криптоанализ. Применительно к шифрам он используется для построения атак с выбором открытого текста, имеющих целью (пол ное или частичное) раскрытие ключа шифра. Его название происходит от английско го dierence разность и связано с тем, что в нем рассматриваются зависимости не между открытыми и шифртекстами, но между разностями пар открытых текстов и разностями пар соответствующих шифртекстов при фиксированном неизвестном клю че. Со времени выхода в свет первых работ по дифференциальному криптоанализу появились десятки, если не сотни, публикаций, в которых предлагаются конкретные атаки на конкретные шифры (или другие криптосистемы), разработанные на основе этой его идеи. К сожалению, среди них нет или слишком мало работ теоретического характера, которые содержали бы изложение дифференциального криптоанализа как метода в общем виде, а именно так, как это принято в вычислительной математи ке с определением основных его понятий, с формулировкой и доказательством его базовых теорем, с определением классов шифров, к которым он применим, с форму лировкой его алгоритма для какого-либо из этих классов или, хотя бы, четких правил (технологии) разработки такого алгоритма. Ничего подобного, к сожалению, на дан ный момент в криптографии нет. Известные атаки дифференциального криптоанализа на конкретные шифры носят совершенно частный характер и не применимы к другим шифрам, даже близким по классу.

В работе [52] предпринимается попытка хотя бы частично восполнить этот пробел.

В ней дифференциальный криптоанализ рассматривается применительно к произволь ным итеративным блочным шифрам, в которых блок открытого текста преобразуется в блок шифртекста за несколько раундов с применением на каждом раунде одной и той же операции преобразования, осуществляемой в зависимости от аддитивного раундового ключа. Изложению метода в общем виде предшествуют введение необхо 122 Г. П. Агибалов димых элементов теории функций на конечных абелевых группах, определение класса рассматриваемых шифров, их классификация по свойствам раундовой функции, уста новление необходимых вспомогательных предложений, а также формулировка аль тернативного метода для одного частного случая, а именно для шифров с функцией раунда, разделимой по Фейстелю. Этот частный метод основан на теореме об адди тивном раундовом ключе и фактически повторяет классический подход дифферен циального криптоанализа к DES с присущими ему недостатками. Общий же метод дифференциального криптоанализа, сформулированный как алгоритм для всех ите ративных блочных шифров с аддитивным раундовым ключом, в своей основе сводится к решению системы полиномиальных уравнений над конечным полем для последнего раунда шифра с известными значениями на его выходе, с известной с ненулевой веро ятностью разностью значений на его входе, с неизвестными компонентами раундового ключа и с неизвестными значениями на его входе. Для r-раундового шифра разность на входе r-го раунда берется из (r 1)-раундовой дифференциальной характеристики этого шифра. Все построения общего характера проиллюстрированы на примере DES, взятого без операций начальной и заключительной перестановок и без расписания ра ундовых ключей.

3.12. К р и п т о г р а ф и ч е с к и е п р о т о к о л ы идентификации и цифровых денег Показано [19], что в протоколе Фиата Шамира доказывающий проходит иден тификацию перед проверяющим, не зная закрытого ключа (s1,..., sk ) последнего, ес ли выполнено следующее условие некорректности: в открытом ключе проверяюще го (v1,..., vk ) есть такое число vj, что u2 vj mod n = c2 для некоторых натураль ных u и c, и, кроме того, ответ проверяющего является единичным вектором с в j-й компоненте. Равенство в условии некорректности выполняется, например, если usj mod n [0, n] [n n, n] и c = u2 vj mod n для некоторого u.

На базе криптографического протокола цифровых денег Шаума разработана пла тёжная компьютерная система для проведения расчётов между продавцом, покупа телем и банком посредством электронной наличности в режиме реального времени через Internet с гарантией неотслеживаемости действий покупателя и невозможности повторного использования электронных денег участниками платежа [22].

4. Организационные мероприятия В настоящее время исследования по криптографии в ТГУ служат научной базой для подготовки математиков по специальности 090102 Компьютерная безопасность со специализацией Математические методы защиты информации. В ТГУ эта спе циальность открыта приказом МОПО РФ № 1219 от 18 мая 1998 г. Содержание под готовки специалистов по ней с перечнем преподаваемых дисциплин можно найти на сайте fpmk.tsu.ru.

Организацию учебного процесса по специальности и преподавание её дискретно математических, общепрофессиональных и специальных дисциплин осуществляет ка федра защиты информации и криптографии, созданная для этой цели приказом рек тора ТГУ от 7 апреля 1999 г.

Результаты проводимых научных исследований апробируются на Сибирской на учной школе-семинаре с международным участием Компьютерная безопасность и криптография SibeCrypt, которую кафедра, начиная с 2002 г., ежегодно проводит в сентябре в различных городах Сибири. В ней регулярно участвуют до 70 учёных, 50 лет криптографии в ТГУ студентов и аспирантов из учебных и научных учреждений России, Украины, Бела руси.

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

ЛИТЕРАТУРА 1. Агибалов Г. П. САК-ЛЯПАС система алгоритмов теории кодирования на основе языка ЛЯПАС // Логический язык для представления алгоритмов синтеза релейных устройств / Под ред. М. А. Гаврилова и А. Д. Закревского. М.: Наука, 1966. С. 326–341.

2. Агибалов Г. П., Левашников А. А. Статистическое исследование задачи опознания буле вых функций одного класса // Тез. докл. к предстоящему Всесоюзному коллоквиуму по автоматизации синтеза дискретных вычислительных устройств, 20 – 25 сентября 1966 г., Новосибирск, 1966. С. 40–45.

3. Агибалов Г. П., Левашников А. А. Программа синтеза регистров сдвига, порождающих нормальные периодические последовательности // Тез. докл. к предстоящему Всесоюз ному коллоквиуму по автоматизации синтеза дискретных вычислительных устройств, 20 – 25 сентября 1966 г., Новосибирск, 1966. С. 28–31.

4. Агибалов Г. П. Распознавание операторов, реализуемых в автономных автоматах // Конф. по теории автоматов и искусственному интеллекту. Аннотации докладов и про грамма. М.: ВЦ АН СССР, 1968. С. 7–8.

5. Agibalov G. P. SAK-LYaPAS a system of coding theory algorithms in LYaPAS // LYaPAS, a Programming Language for Logic and Coding Algorithms. New York;

London: Academic Press, 1969. P. 690–720.

6. Агибалов Г. П. Распознавание операторов, реализуемых в линейных автономных автома тах // Изв. АН СССР. Техническая кибернетика. 1970. № 3. С. 99–108.

7. Агибалов Г. П. О некоторых доопределениях частичной булевой функции // Труды Си бирского физико-технического института. Проблемы кибернетики. Вып 49. Томск: Изд во Том. ун-та, 1970. С. 12–19.

8. Агибалов Г. П. Отождествление нормальных периодических последовательностей на чальными отрезками // Труды Сибирского физико-технического института. Проблемы кибернетики. Вып 49. Томск: Изд-во Том. ун-та, 1970. С. 20–37.

9. Агибалов Г. П., Левашников А. А. Статистические оценки сложности булевых функций, порождающих нормальные периодические последовательности // Труды Сибирского физико-технического института. Проблемы кибернетики. Вып 51. Томск: Изд-во Том.

ун-та, 1970. С. 6–8.

10. Агибалов Г. П. Распознавание операторов, вычисляющих нормальные периодиче ские последовательности // Изв. АН СССР. Техническая кибернетика. 1971. № 6.

С. 165–173.

11. Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.

12. Агибалов Г. П., Юфит Я. Г. О простых экспериментах для линейных инициальных ав томатов // Автоматика и вычислительная техника. 1972. № 2. С. 17–19.

13. Агибалов Г. П., Ванина Н. В. Точная верхняя оценка степени различимости произволь ной нормальной периодической последовательности // Изв. АН СССР. Техническая ки бернетика. 1973. № 1. С. 131–136.

124 Г. П. Агибалов 14. Агибалов Г. П. Синтез автоматов по конечно-определённым словарным функциям // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1979.

С. 160–164.

15. Агибалов Г. П., Беляев В. А. Технология решения комбинаторно-логических задач мето дом сокращённого обхода дерева поиска. Томск: Изд-во Том. ун-та, 1981. 125 с.

16. Агибалов Г. П., Оранов А. М. Лекции по теории конечных автоматов. Томск: Изд-во Том.

ун-та, 1984. 184 с.

17. Агибалов Г. П., Евтушенко Н. В. Декомпозиция конечных автоматов. Томск: Изд-во Том. ун-та, 1985. 128 с.

18. Евтушенко Н. В. О принадлежности последовательности множеству контрольных по следовательностей автомата // Алгоритмы решения задач дискретной математики.

Вып. 2. Томск: Изд-во Том. ун-та, 1987. С. 130 133.

19. Агибалов Г. П., Дирко Д. В., Казаков С. А., Коршиков Е. М., Компьютерное моделиро вание и исследование некоторых криптологических алгоритмов с открытым ключом // Новые информационные технологии в исследовании дискретных структур. Томск: ТНЦ СО РАН, Спектр, 2000. С. 64–70.

20. Пронина И. В., Агибалов Г. П. Некоторые алгоритмы криптоанализа для кодовых крип тосистем // Вестник Томского госуниверситета. Июнь 2000. № 271. С. 115–118.

21. Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского госуниверситета. Приложение. Сентябрь 2003. № 6. С. 31–41.

22. Михалёва М. А. Электронная платёжная система на базе криптографического протоко ла цифровых денег // Вестник Томского госуниверситета. Приложение. Сентябрь 2003.

№ 6. С. 42–49.

23. Агибалов Г. П. Логические уравнения в криптоанализе сжимающего и самосжимающего генераторов // Вестник Томского госуниверситета. Приложение. Август 2004. № 9(I).

С. 49–54.

24. Колегов Д. Н. О булевых функциях, сохраняющих линейную сложность линейной рекур рентной последовательности // Вестник Томского госуниверситета. Приложение. Август 2004. № 9(I). С. 18–20.

25. Стефанцов Д. А. Логическое и компьютерное моделирование криптоалгоритма Fish // Вестник Томского госуниверситета. Приложение. Август 2004. № 9(I). С. 82–84.

26. Тимошевская Н. Е. Экспериментальное исследование стойкости сжимающего генерато ра // Вестник Томского госуниверситета. Приложение. Август 2004. № 9(I). С. 84–88.

27. Тимошевская Н. Е. Параллельные вычисления в решении систем логических уравнений методом линеаризации // Материалы XV Междунар. школы-семинара Синтез и слож ность управляющих систем / Под ред. О. Б. Лупанова. Новосибирск: Изд-во Института математики, 2004. С. 97–102.

28. Тимошевская Н. Е. Параллельная генерация сочетаний и перестановок // Вторая Си бирская школа-семинар по параллельным вычислениям. Томск: Изд-во Том. ун-та, 2004.

С. 55–59.

29. Тимошевская Н. Е. Параллельные методы обхода дерева // Математическое моделиро вание. 2004. Т. 16. № 1. С. 105–114.

30. Агибалов Г. П. Избранные теоремы начального курса криптографии. Томск: Изд-во НТЛ, 2005. 116 с.

31. Агибалов Г. П. Вероятностные схемы симметричного поточного шифрования над ко нечным полем // Вестник Томского госуниверситета. Приложение. Август 2005. № 14.

С. 39–42.

50 лет криптографии в ТГУ 32. Андреева Л. Н. К криптоанализу шифров инволюционной подстановки // Вестник Том ского госуниверситета. Приложение. Август 2005. № 14. С. 43–44.

33. Белов А. Г. Исследование алгоритма дискретного логарифмирования Адлемана // Вест ник Томского госуниверситета. Приложение. Август 2005. № 14. С. 45–49.

34. Колегов Д. Н. О некоторых классах булевых функций, сохраняющих линейную слож ность линейных рекуррентных последовательностей // Вестник Томского госуниверси тета. Приложение. Август 2005. № 14. С. 57.

35. Колегов Д. Н. О булевых функциях без запрета // Вестник Томского госуниверситета.

Приложение. Август 2005. № 14. С. 58–60.

36. Тимошевская Н. Е. Задача о кратчайшем линеаризационном множестве // Вестник Том ского госуниверситета. Приложение. Август 2005. № 14. С. 79–83.

37. Тимошевская Н. Е. О линеаризационно эквивалентных покрытиях // Вестник Томского госуниверситета. Приложение. Август 2005. № 14. С. 84–91.

38. Худяшов И. И. Применение параллельных вычислений в методах факторизации // Вест ник Томского госуниверситета. Приложение. Август 2005. № 14. С. 96–98.

39. Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным по лем // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 4–9.

40. Панин А. Н. Генерация булевых функций зданного порядка устойчивости // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 47–52.

41. Агибалов Г. П., Сунгурова О. Г. Криптоанализ конечно-автоматного генератора ключе вого потока с функцией выходов в качестве ключа // Вестник Томского госуниверситета.

Приложение. Август 2006. № 17. С. 104–108.

42. Андреева Л. Н. К криптоанализу инволютивных шифров с частично известными инволю циями // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 109–112.

43. Колегов Д. Н. Общая схема вероятностной поточной шифрсистемы // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 109–112.

44. Тимошевская Н. Е. Параллельное перечисление разбиений множества методом нумера ции // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 260–264.

45. Худяшов И. И., Семёнов В. В. Применение параллельных вычислений для решения си стем логических уравнений методом линеаризационного множества // Вестник Томского госуниверситета. Приложение. Август 2006. № 17. С. 267–272.

46. Агибалов Г. П. Нормальные рекуррентные последовательности // Вестник Томского го суниверситета. Приложение. Август 2007. № 23. С. 4–11.

47. Тимошевская Н. Е. Оценки числа покрытий с линеаризационными множествами задан ной мощности // Вестник Томского госуниверситета. Приложение. Август 2007. № 23.

С. 60–64.

48. Белов А. Г., Панкратова И. А. Сравнительный анализ двух алгоритмов генерации про стых чисел // Вестник Томского госуниверситета. Приложение. Август 2007. № 23.

С. 77–80.

49. Панкратов И. В. К определению понятия самосинхронизирующегося поточного шиф ра // Вестник Томского госуниверситета. Приложение. Август 2007. № 23. С. 114–117.

50. Андреева Л. Н. Инволюционные схемы разделения секрета // Вестник Томского госуни верситета. Приложение. Август 2007. № 23. С. 99.

51. Тренькаев В. Н., Колесников Р. Г. Автоматный подход к атакам на симметричные шиф ры // Вестник Томского госуниверситета. Приложение. Август 2007. № 23. С. 77–80.

126 Г. П. Агибалов 52. Агибалов Г. П. Элементы теории дифференциального криптоанализа итеративных блоч ных шифров с аддитивным раундовым ключом // Прикладная дискретная математика.

2008. № 1. С. 34–42.

53. Парватов Н. Г. Совершенные схемы разделения секрета // Прикладная дискретная ма тематика. 2008. № 2. С. 50–57.

54. Поздеев А. Г. Построение нормальных периодических последовательностей из цикличес ки минимальных чисел // Прикладная дискретная математика. 2008. № 2. С. 15–17.

55. Андреева Л. Н. Технология решения задач кратчайшего разбиения // Прикладная дис кретная математика. 2009. № 2. С. 79–95.

56. Тимошевская Н. Е. Разработка и исследование параллельных комбинаторных алгорит мов // Прикладная дискретная математика. 2009. № 2. С. 96–103.

57. Закревский А. Д. Метод автоматической шифрации сообщений // Прикладная дискрет ная математика. 2009. № 2. С. 127–137.



 




 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.