WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

«А. Г. Коробейников, Ю.А.Гатчин Математические основы криптологии Учебное пособие Санкт-Петербург 2004 2 2 УДК 511 Коробейников А. Г, Ю.А.Гатчин. Математические основы криптологии. ...»

-- [ Страница 2 ] --

Метод гаммирования становится бессильным, если злоумышленни ку становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок почти случайной последовательности (ПСП) и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылае мых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при созда нии реальных систем информационной безопасности. Ниже рассматрива ются наиболее распространенные методы генерации гамм, которые могут быть использованы на практике. Этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генери руемой на основе ключа.

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

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

Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдо случайных чисел T(i), описываемые соотношением T(i+1) = (AT(i)+C) mod m, где А и С - константы, Т(0) - исходная величина, выбранная в качестве по рождающего числа. Очевидно, что эти три величины и образуют ключ.

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

Значение m обычно устанавливается равным 2n, где n - длина машинного слова в битах. Датчик имеет максимальный период m до того, как генери руемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период m был мак симальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечет ное, и А mod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть вы бран ключ любого размера. Например, пусть ключ состоит из набора чи сел x(j) размерностью n, где j=1, 2,..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j).

Датчики М-последовательностей Популярность М-последовательностей объясняется относительно легкой их реализаций.

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

r1:=r0 r2:=r1... rk-1:=rk- r0:=a0 r1 a1 r2... ak-2 rk- Гi:= rk- Здесь r0 r1... rk-1 - k однобитных регистров, a0 a1... ak-1 – коэффици енты неприводимого двоичного полинома степени k-1. Гi - i-е значение выходной гаммы.

Период М-последовательности, исходя из ее свойств, равен 2k-1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для задан ного k. Эта характеристика приведена в таблице 3.

Таблица k Объем ансамбля 5 6 7 8 9 10 16 Очевидно, что такие объемы ансамблей последовательности непри емлемы. Поэтому на практике часто используют последовательности Гол да, образующиеся суммированием нескольких М-последовательностей.

Объем ансамблей этих последовательностей на несколько порядков пре восходят объемы ансамблей порождающих М-последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М-последовательности) до 388000.

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

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

5.6 Стандарт шифрования DES Одним из самых распространенных алгоритмов шифрования явля ется DES - алгоритм (Data Encryption Standart), разработанный в 1977 г. и рекомендованный Национальным бюро стандартов США совместно с АНБ в качестве основного средства криптографической защиты информа ции как в государственных, так и в коммерческих структурах. Однако в 1988 г. АНБ рекомендовало использовать DES только в системах элект ронного перевода. В последнее время, с учетом выявленных слабостей DES, появляются изменения в начальном варианте стандарта и новые ал горитмы, использующие в качестве основы DES - NewDes, TripleDES и др. Появление новых алгоритмов было обусловлено развитием за много летнее существование данного алгоритма большого количества атак на DES. Кроме того, бурное развитие производительности и быстродействия средств вычислительной и микропроцессорной техники привело к тому, что 56 битного ключа используемого в оригинальном варианте DES стало недостаточно, чтобы противостоять атаке методом грубой силы. Тем не менее, DES и на сегодняшний день он остается одним из самых применяе мых алгоритмов блочного шифрования в коммерческой сфере и в систе мах электронных расчетов.

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

Всего для получения блока зашифрованного сообщения проходит 16 раундов. В DES используется 16 раундов по следующим причинам:

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

DES предусматривает 4 режима работы:

• ECB (Electronic Codebook) электронный шифрблокнот;

• CBC (Cipher Block Chaining) цепочка блоков;

• CFB (Cipher Feedback) обратная связь по шифртексту;

• OFB (Output Feedback) обратная связь по выходу.

Говоря о DES невозможно было бы обойти стороной тему безопас ности данного алгоритма и возможных атак на него. Многолетний опыт эксплуатации DES и его открытость (исходные тексты алгоритма и доку ментацию на него можно встретить в открытых источниках) привели к тому, что DES стал одним из популярнейших алгоритмов с точки зрения криптоанализа. На сегодняшний день существует ряд атак на DES учиты вающих слабости алгоритма, которых за столь долгий срок эксплуатации было выявлено достаточное количество. Некоторые из атак реализуемы только в предположении, что атакующий обладает некоторыми возмож ностями и в ряде случаев атаки с точки зрения практической реализации можно смело отнести эти атаки к теоретически возможным. Хотя не ис ключено, что со временем они перейдут в разряд практически возможных.

Среди основных недостатков DES существенно снижающих уро вень безопасности при использовании данного алгоритма можно выделить следующие:

• наличие слабых ключей, вызванное тем, что при генерации ключе вой последовательности используются 2 регистра сдвига, которые работают независимо друг от друга. Примером, слабого ключа мо жет служить 1F1F1F1F 0E0E0E0E (с учетом битов контроля чет ности). В данном случае результатом генерации будут ключевые по следовательности одинаковые с исходным ключом во всех 16 раун дах. Существуют также разновидности слабых ключей, которые да ют при генерации всего лишь 2 (4) ключевые последовательности.

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

• небольшая длина ключа 56 бит (или 64 бита с контролем четности).

При современном уровне развития микропроцессорной средств дан ная длина ключа не может обеспечивать должный уровень защиты для некоторых типов информации. Применение тройного DES (TripleDES) не дают ощутимого результата хотя и используются разных ключа (К1, К2, К3). В конечном итоге эквивалентно зашиф рованию на другом ключе К4, т.е. для любых К1, К2, К3 найдется ключ К4 такой, что: ЕК3(DК2(ЕК1(Р)))=ЕК4(Р);

• наличие избыточности ключа, обусловленное контролем четности для каждого байта ключа отдельно. Бихам и Шамир предложили до статочно эффективную атаку на реализацию DES в смарт-картах или банковских криптографических модулях, использующих EEPROM память для хранения ключей. Данная атака демонстрирует очередную слабость DES, состоящую в наличие контроля четности каждого байта ключа, который создает избыточность ключа и позво ляет восстанавливать ключи, хранящиеся в памяти устройства, в случае сбоя в данном участке памяти;

• использование статических подстановок в S-боксах, что несмотря на большое количество раундов позволяет криптоаналитикам проводит атаки, учитывающие данный факт. Хотя на сегодняшний день автору не известно успешных атак на 16 раундовый DES, основан ных на данном факте. Но успешные атаки на неполнораундовые схемы DES имеют место быть. Так Мартин Хэллман предложил ата ку на 8 раундовый DES. Предложенная атака позволяет успешно восстанавливать 10 бит ключа за 10 сек. на рабочей станции SUN- и имеет вероятность успеха 80% в случае выбора 512 открытых текстов и 95% в случае выбора 768 открытых текстов. Восстановив 10 бит ключа можно воспользоваться алгоритмами перебора всех оставшихся вариантов, и свести таким образом задачу нахождения 56- битного ключа к нахождения 46-битного ключа Учитывая выше сказанное можно с уверенностью сказать, что ис пользование DES на сегодняшний день является опасным с точки зрения криптографической стойкости и обеспечения надежного функционирова ния систем криптографической защиты информации, использующих дан ный алгоритм.

5.7 Стандарт шифрования ГОСТ-28147- Важной задачей в обеспечении гарантированной безопасности ин формации в ИС является разработка и использования стандартных алго ритмов шифрования данных. Первым среди подобных стандартов стал американский алгоритм DES, представляющий собой последовательное использование замен и перестановок. В настоящее время все чаще говорят о неоправданной сложности и невысокой криптостойкости. На практике приходится использовать его модификации.

Более эффективным является отечественный стандарт шифрования данных ГОСТ-28147-89.

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

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

• AB - побитовое сложение по модулю 2;

• A[+]B - сложение по модулю 232;

• A{+}B - сложение по модулю 232-1;

.

Алгоритм криптографического преобразования предусматривает несколько режимов работы. Во всех режимах используется ключ W дли ной 256 бит, представляемый в виде восьми 32-разрядных чисел x(i):

W=x(7)x(6) x(5) x(4)x(3)x(2)x(1)x(0).

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

Самый простой из возможных режимов - замена.

Пусть открытые блоки разбиты на блоки по 64 бит в каждом, кото рые обозначим как T(j).

Очередная последовательность бит T(j) разделяется на две после довательности B и A по 32 бита (правый и левый блоки). Далее выполня ется итеративный процесс шифрования описываемый следующими фор мулами, вид который зависит от i:

• Для i=1, 2,..., 24, j=(i-1) mod 8;

A(i) = f(A(i-1) [+] x(j)) B(i-1) B(i) = A(i-1) • Для i=25, 26,..., 31, j=32-i;

A(i) = f(A(i-1) [+] x(j)) B(i-1) B(i) = A(i-1) • Для i= A(32) = A(31) B(32) = f(A(31) [+] x(0)) B(31).

Здесь i обозначает номер итерации. Функция f – функция шифрова ния, включающая две операции над 32-разрядным аргументом.

Первая операция является подстановкой K. Блок подстановки К со стоит из 8 узлов замены К(1)...К(8) с памятью 64 бита каждый. Поступаю щий на блок подстановки 32-разрядный вектор разбивается на 8 последо вательно идущих 4-разрядных вектора, каждый из который преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим из себя таблицу из 16 целых чисел в диапазоне 0...15. Входной вектор оп ределяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-разрядные векторы последовательно объединяются в 32-разрядный выходной.

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

Т=А(32)В(32).

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

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

Другой режим шифрования называется режимом гаммирования.

Открытые данные, разбитые на 64-разрядные блоки T(i) (i=1,2,...,m) (m определяется объемом шифруемых данных), зашифровыва ются в режиме гаммирования путем поразрядного сложения по модулю с гаммой шифра Гш, которая вырабатывается блоками по 64 бит, т.е.

Гш=(Г(1),Г(2),....,Г(m)).

Уравнение шифрования данных в режиме гаммирования может быть представлено в следующем виде:

Ш(i)=A(Y(i-1) C2, Z(i-1)) {+} C1 T(i)=Г(i) T(i) В этом уравнении Ш(i) обозначает 64-разрядный блок зашифро ванного текста, А - функцию шифрования в режиме простой замены (ар гументами этой функции являются два 32-разрядных числа). С1 и С2 - константы, заданные в ГОСТ 28147-89. Величины y(i) и Z(i) определяются итерационно по мере формирования гаммы следующим образом:

(Y(0),Z(0))=A(S), S - 64-разрядная двоичная последовательность (Y(i),Z(i))=(Y(i-1) [+] C2, Z(i-1) {+} C(1)), i=1, 2,..., m.

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как и в режиме гаммирования открытые данные, разбитые на 64-разрядные блоки T(i), зашифровываются путем поразрядного сло жения по модулю 2 с гаммой шифра Гш, которая вырабатывается блоками по 64 бит:

Гш=(Г(1), Г(2),..., Г(m)).

Уравнение шифрования данных в режиме гаммирования с обрат ной связью выглядят следующим образом:

Ш(1)=A(S)T(1)=Г(1)T(1), Ш(i)=A(Ш(i-1)T(i)=Г(i)T(i), i=2, 3,..., m.

Следует отметить, что в отличие от DES, у ГОСТ 28147-89 блок подстановки можно произвольно изменять, то есть он является дополни тельным 512-битовым ключом.

В ГОСТ 28147-89 определяется процесс выработки имитовставки, который единообразен для всех режимов шифрования. Имитовставка - это блок из р бит (имитовставка Ир), который вырабатывается либо перед шифрованием всего сообщения. либо параллельно с шифрованием по бло кам. Параметр р выбирается в соответствии с необходимым уровнем ими тозащищенности.

Для получения имитовставки открытые данные представляются также в виде блоков по 64 бит. Первый блок открытых данных Т(1) под вергается преобразованию, соответствующему первым 16 циклам алго ритма режима простой замены. Причем в качестве ключа используется тот же ключ, что и для шифрования данных. Полученное 64-разрядно число суммируется с открытым блоком Т(2) и сумма вновь подвергается 16 цик лам шифрования для режима простой замены. Данная процедура повто рятся для всех m блоков сообщения. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

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

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

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

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

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

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

• Режим простой замены или режим электронной кодовой книги (Electronic Codebook Mode - ECB) • Режим гаммирования • Режим гаммирования с самовостановлением или шифрование с об ратной связью (Cipher-Feedback mode - CFB) • Режим гаммирования с обратной связью по выходу (Output-Feed back mode - OFB) • Режим шифрования со сцеплением блоков (Cipher Block Chaining mode - CBC) Блочные шифры бывают двух основных видов:

• шифры перестановки (transposition, permutation, P-блоки);

• шифры замены (подстановки, substitution, S-блоки).

Шифры перестановок и шифры замены были рассмотрены выше.

Блочное шифрование можно осуществлять двояко:

1. Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруются одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одина ковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.

2. С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В ка честве первого блока в цепи ОС используется инициализирующее значе ние. Ошибка в одном бите влияет на два блока - ошибочный и следующий за ним. Пример - DES в режиме CBC.

Генератор ПСЧ может применяться и при блочном шифровании:

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

2. Поблочное шифрование потока данных с ОС. Генератор ПСЧ управляется шифрованным или исходным текстом или обоими вместе.

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

В этом случае гамма вырабатывается блоками и поблочно складывается по модулю 2 с исходным текстом. В качестве примера можно назвать B Crypt, DES в режимах CFB и OFB, ГОСТ 28147-89 в режимах гаммиро вания и гаммирования c обратной связью.

6. КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ 6.1. ОДНОСТОРОННИЕ ФУНКЦИИ Одним из центральных понятий криптосистем с открытым ключом является понятие односторонней функции.

Односторонней функцией называется функция заданная на мно жестве X и областью значений в множестве Y, т.е. f : XY, обладающая двумя свойствами:

1. Существует полиномиальный алгоритм вычисления f (x).

2. Не существует полиномиальный алгоритм инвертирования функции f (x), т.е. решения уравнения f (x)=y относительно y.

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

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

Другим важным примером кандидата на однонаправленную функ цию является модульное возведение в степень или модульное экспониро вание в кольце классов вычетов по модулю n - Zn. Пусть a,mZ. Тогда модульное возведение в степень m (относительно основания a и модуля n) это такая функция f[a,n]: ZnZn, определяемая как f[a,n](m)=ammod(n).

Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров a, n и m составляет несколько со тен знаков. То, что это возможно, и в самом деле так, показывает следую щий пример.

Пример 62. x49=((((x2x)2)2)2)2x Пример 62 показывает, как можно вычислить x49 c помощью лишь пяти возведений в квадрат и еще двух умножений. При вычислении ammod(n) приведение по модулю n желательно делать после каждого воз ведения в квадрат и каждого умножения, чтобы избежать получения очень больших целых чисел.

По аналогии с действительным анализом обратная операция в Zn известна как задача дискретного логарифмирования: даны целые числа a, n и x, требуется найти такое целое m (если оно существует), что ammod(n) =x. Например, 1816mod(43) = 9. Здесь 16 является дискретным логарифмом 9 с основанием 18 по модулю 43. Можно проверить, что число 3 вообще не имеет логарифма с основанием 5 по модулю 21.

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

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

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

Более употребимым понятием в криптографии является понятие функции с секретом. Иногда еще употребляется термин функция с ловуш кой. Функцией с секретом К называется функция fК : XY, зависящая от параметра К и обладающая тремя свойствами:

1. При любом К существует полиномиальный алгоритм вычисления значений fК (х);

2. При неизвестном К не существует полиномиального алгоритма ин вертирования fК (х).

3. При известном К существует полиномиальный алгоритм инвертиро вания fК (х).

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

Первый кандидат на однонаправленную функцию с секретом по хож на нашего второго кандидата на просто однонаправленную функцию:

модульное возведение в степень с фиксированной экспонентой и модулем.

Пусть m,nZ. Тогда модульное возведение в степень (относительно экс поненты m и модуля n) есть функция g[m,n]: ZnZn, определена следу ющим образом: g[m,n](a) = ammod(n).

Необходимо понимать различия между функциями f[a,n] и g[m,n].

Опять по аналогии с действительным анализом, операция обратная g[m,n] известна под названием взятия корня m-той степени из x по моду лю n: даны целые числа m, n и x. Требуется найти такое целое a(если оно существует), что am mod(n) = x. Например, 18 это корень 16-ой степени из 9 по модулю 43, так как 1816mod(43) = 9. Очевидно, что 25 также является корнем 16-ой степени из 9 по модулю 43.

В противоположность задаче дискретного логарифмирования, тем не менее, известно, что существует также и эффективный алгоритм взятия корня m-ой степени из x по модулю n (или выяснения, что его не сущест вует) для любого заданного x. Любопытный феномен заключается в том, что неизвестно, как построить этот эффективный алгоритм при заданных лишь m и n. Другими словами, функция g[m,n] в действительности не яв ляется однонаправленной, поскольку мы знаем, что она может быть эф фективно обращена. Но, несмотря на этот факт, мы не знаем, как это сде лать.

Тем не менее, легко построить эффективный алгоритм вычисления m-ого корня по модулю n при условии, что известно разложение n на простые множители. Именно по этой причине g[m,n] и является кандида том на однонаправленную функцию с секретом, для которой m и n ис пользуются как открытая информация, тогда как разложение служит в качестве секрета K.

Применение функций с секретом в криптографии позволяет:

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

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифрования (цифровая подпись и др.).

6.2. ГЕНЕРАЦИЯ КЛЮЧЕЙ В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (Diffi W., Hellman M.) в статье "Новые направления в криптографии" предложи ли новый принцип построения криптосистем, не требующий не только пе редачи ключа принимающему сообщение, но даже сохранения в тайне ме тода шифрования. Этот метод получил название “метод экспоненциально го ключевого обмена” и является первой криптосистемой с открытым ключом. Метод запатентован, но срок действия патента истек 29 апреля 1997 года. Рассмотрим его основные положения.

Пусть абоненты А и В условились организовать секретную пере писку между собой используя секретный ключ сгенерированный при по мощи алгоритма Диффи–Хеллмана. Для этого они вместе выбирают два достаточно больших простых числа n и q так, чтобы q было примитивным элементом в GF(n). Эти два числа необязательно хранить в секрете. Або ненты А и В могут передать эти числа по открытому каналу связи. Затем абоненты реализуют следующий алгоритм.

1 А выбирает случайное большое целое число, вычисляет x=qmod n и посылает В число x.

2 В выбирает случайное большое целое число, вычисляет y=qmod n и посылает A число y.

3 А вычисляет k1=y mod n.

4 B вычисляет k2=x mod n.

В итоге А и В получили такие числа, что k1=k2=qmod n. Никто из злоумышленников, имеющих доступ к этому открытому каналу не может определить эти значения, так как им известны n, q, x и y, но неизвестны и. Для получения и необходимо вычислить дискретный логарифм, что является трудной в вычислительном плане задачей. Таким образом, величина k=k1=k2 может являться секретным ключом, который А и В вы числили независимо. В данном алгоритме выбор n и q существенно влияет на криптостойкость.

Пример 63. Пусть абоненты А и В условились организовать сек ретную переписку между собой используя секретный ключ сгенерирован ный при помощи алгоритма Диффи–Хеллмана. Тогда они вместе выбира ют числа n=67 и q=11. Затем 1. А выбирает случайное целое число =47, вычисляет x=qmod n =1147mod 67 = 2 и посылает В число 2.

2. В выбирает случайное целое число =51 вычисляет y=qmod n =1151mod 67 = 3 и посылает A число 3.

3. А вычисляет k1=y mod n =347mod 67 = 4. B вычисляет k2=x mod n =251mod 67 = В итоге А и В получили секретный ключ k= k1= k2=27.

Пример 64. А теперь рассмотрим похожий пример, но с большими числами, а именно n= 47145699491406164851279623993595007385788105416184430877 и q= 9623993595307385078105416180853461.

1. А выбирает случайное целое число = 8105416184431367 вычисляет x=qmod n = mod 184430877= 283834363413940089769498071750446034632184657957036 и посыла ет В число x.

2. В выбирает случайное целое число = 026354046454419 вычисляет y=qmod n = 0781054161808534614374501449566023848745004454235242730706338861786424872851541 mod 6184430877 = 05625061872522661677845494058935332443487281531990777 и посы лает A число y.

3. А вычисляет k1=ymod n = mod 7145699491406164851279623993595007385788105416184430877 = 8 4. B вычисляет k2=xmod n = mod 145699491406164851279623993595007385788105416184430877 = 9332466343130308527526832915254594034.

В итоге А и В получили секретный ключ k= k1= k2= 308527526832915254594034.

Без дополнительных мер безопасности (введения сертификатов от крытых ключей), рассмотренный метод ключевого обмена уязвим с точки зрения атаки, известной под названием “человек посередине” (main in the midlle attact).

Предположим, что злоумышленник C может не только подслуши вать сообщения между A и B, но также изменять, удалять и создавать но вые ложные сообщения. Тогда C может выдавать себя за A, что сообщаю щего B, и за B, что сообщающего A. Атака состоит в следующем:

1. A посылает B свой открытый ключ. C перехватывает его и посылает B свой собственный открытый ключ.

2. B посылает A свой открытый ключ. C перехватывает его и посылает A свой собственный открытый ключ.

3. Когда A посылает сообщения B, зашифрованное на его открытом клю че, C перехватывает его. Т.к. сообщение в действительности зашифро вано на открытом ключе C, он расшифровывает его, снова зашифро вывает его на открытом ключе B и посылает B.

4. Когда B посылает сообщения A, зашифрованное на его открытом клю че, C перехватывает его. Так как сообщение в действительности за шифровано на открытом ключе C, он расшифровывает его, снова за шифровывает его на открытом ключе A и посылает A.

Атака возможна, даже если открытые ключи A и B и хранятся в БД. Злоумышленник C может перехватить запрос A к БД и подменить от крытый ключ. Данная атака очень эффективна. Открытые ключи должны проходить сертификацию, чтобы предотвратить подобные атаки, связан ные с подменой ключей и должны регулярно меняться.

6.3. ОСНОВНЫЕ ПОЛОЖЕНИЯ КРИПТОСИСТЕМЫ RSA В 1978 г. Рональд Ривест, Ади Шамир и Леонард Адлеман (R.Ri vest, A.Shamir, L.Adleman) предложили пример функции, обладающей ря дом замечательных свойств. На ее основе была построена реально ис пользуемая система шифрования, получившая название по первым буквам фамилий авторов – система RSA. Рассмотрим ее основные положения на примере криптосистемы с открытым ключом.

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

1 Кольцо целых чисел является факториальным (см. теорему 14). Но зада ча разложения больших чисел на простые множители за полиноми альное время не разрешима.

2 Задача вычисление логарифма за полиномиальное время не разрешима.

3 Следствие теоремы 10.

4 Функции Эйлера (см. п.2.5) Приведем общую схему алгоритма RSA. Пусть абоненты А и В ус ловились организовать секретную переписку между собой с открытым ключом. Тогда каждый из них, независимо от другого, выбирает два до статочно больших простых числа, находит их произведение, функцию Эй лера от этого произведения и выбирает случайное число, меньшее этого вычисленного значения функции Эйлера и взаимно простое с ним. Итак, А:р1,р2, rА=р1р2, (rА), НОД(a,(rА))=1, 0 < a < (rА), B:q1,q2, rB=q1q2, (rB), НОД (b,(rB))=1, 0 < b < (rB).

Затем печатается телефонная книга, доступная всем желающим, которая имеет вид:

rА – произведение двух простых чисел, известных только А, a – А: rА,a открытый ключ, доступный каждому, кто хочет передать секрет B: rB,b ное сообщение А, rB – произведение двух простых чисел, извест ных только B. b – открытый ключ, доступный каждому, кто хо чет передать секретное сообщение B.

Каждый из абонентов находит свой секретный ключ из сравнений а1(mod (rА)), 0 < < (rА), b1(mod (r )), 0 < < (r ).

B B Итак, Абонент Открытые ключи Секретные ключи A rА, a B rB, b Пусть абонент А решает послать сообщение m абоненту В:

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

m1mb(mod rB), 0 < m1 < rB, и отправляет абоненту В. Абонент В, расшифровывает это сообщение своим секретным ключом:

m2m1(mod rB), 0 < m2 < rB, и получает m2=m.

В самом деле: m2m1(m)bmb(mod rB).

Но b1(mod (r )), следовательно m2 m(mod rB). Но так как B 0

Пример 65. Пусть абоненты A и B решили установить между собой скрытую связь с открытым ключом.

Абонент A выбрал простые числа р1=7643 и р2=8753, их произведе ние rА=66899179, функцию Эйлера (r ) =р1р2(1-1/р1)(1-1/р2)=66882784.

A Затем он выбирает случайное число a=9467 (открытый ключ) и находит секретный ключ из решения сравнения: а1(mod (rА))=94671(mod 66882784), 0<<(rА), т.е. =30993427.

Абонент B выбрал простые числа q1=7481 и q2=9539, их произведе ние rB=71361259, функцию Эйлера (r ) =r (1-1/q1)(1-1/q2)=71344240. За B B тем он выбирает случайное число b=74671 (открытый ключ) и находит секретный ключ из решения сравнения: b1(mod (rB))=746711(mod 71344240), 0<<(rB), т.е. =33289711.

Таким образом, имеется следующая таблица:

Абонент Открытые ключи Секретные ключи A 66899179, 9467 B 71361259, 74671 Абонент A решает послать cверхсекретное сообщение абоненту B m=95637. Тогда он шифрует сообщение открытым ключом абонента B:

m1mb(mod rB)= 9563774671(mod 71361259)= 25963634.

Абонент B, получив это сообщение, расшифровывает его своим секретным ключом:

m2m1(mod p)= 2596363433289711(mod 71361259)= 95637.

Пример 66. А теперь рассмотрим похожий пример, но с большими числами, а именно: р1=7643 и р2=8753, их произведение rА=66899179, (r ) =р1р2(1-1/р1)(1-1/р2)=66882784, a=9467 и =30993427. Далее, A q1=170141183460469231731687303715884105727, q2= 86718619237468234569, b= 1567871. Тогда имеем: rB= 085697884921213758143162998032276663, (r ) =r (1-1/q1)(1-1/q2)= B B 936368. Находим секретный ключ из решения сравнения: b1(mod (rB)) =1826877046663628647754606040895353774569915678711(mod 936368), 0<<(rB), т.е. = 47807953854259478179905981879730111.

Таким образом имеется таблица:

Абонент Открытые ключи Секретные ключи A 66899179, 9467 B 17610964142557596262140073 7655799099395508 569788492 1213758143162998032276663, 18268770466636286477546060 408953537745699 Абонент A решает послать cверхсекретное сообщение абоненту B m=9563712352348897672389641396218609567172. Тогда он шифрует со общение открытым ключом абонента B: m1mb(mod rB)= 7672389641396218609567172182687704666362864775460604089535377456991567871(mod 032276663)= 594478223942973656948.

Абонент B, получив это сообщение, расшифровывает его своим се кретным ключом: m2m1(mod p)= (mod 993955085697884921213758143162998032276663)= 89641396218609567172.

6.4. НАДЕЖНОСТЬ СИСТЕМЫ RSA В рассмотренной криптосистеме с открытым ключом для расшиф ровки сообщения m необходимо найти секретный ключ. Это возможно в двух случаях:

1) если известно разложение rB на простые множители;

2) если известен модуль (rB) сравнения b1(mod (rB)).

Но так как rB=q1q2, то (rB)=(q1)(q2)=(q1-1)(q2-1)=q1q2-(q1+q2)+1 и (q1-q2)2=q12+q22-2q1q2=(q1+q2)2-4q1q2.

Следовательно, мы имеем равенства:

(rB)=rB-(q1+q2)+1, (q1-q2)2=(q1+q2)2-4q1q2, а значит, зная (rB), можно решить эту систему и найти q1 и q2, а зная q1 и q2, легко вычислить (rB). Таким образом, оба подхода определения ключа эквивалентны, т.е. задачи одной сложности. Таким образом, встает задача разложения на простые множители натурального числа.

В теории чисел, несмотря на ее многолетнюю историю и на очень интенсивные поиски в течение последних 30 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до (rB)1/2, и деля на них rB, найти требуемое разложение. Но учитывая, что количество простых чисел в этом промежутке асимптотически равно 2(rB)1/2(ln rB)-1, находим, что при rB, записываемом 1000 десятичными цифрами, найдется не менее простых чисел, на которые придется делить rB при разложении его на мно жители, что при современных возможностях вычислительной техники за тянется на долгие годы.

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

Необходимо также отметить, что система RSA обладает мульти пликативным свойством. Поясним сказанное. Пусть m1 и m2 - 2 различных открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим, что (m1m2)= m1m2= c1c2(mod n).

Другими словами, шифртекст открытого текста m=m1m2 есть c= c1c2(mod n). Это свойство, называемое также гомоморфным свойством RSA, позволяет осуществить атаку по выбранному шифртексту. Его нуж но учитывать при совмещении схем шифрования на основе RSA и цифро вой подписи RSA.

Кроме того, известно еще несколько атак на RSA. Рассмотрим из них две.

Первая из них называется ”Метод безключевого чтения RSA”. Суть заключается в следующем.

Криптоаналитику известны открытый ключ (a, n) и шифротекст С.

Тогда он подбирает такое число k, для которого выполняется следующее соотношение: Сak(mod n)=C. Т.е. криптоаналитик просто проводит k раз зашифрование на открытом ключе перехваченного шифротекста. Это вы глядит следующим образом: (((Сa)a)a…)a=Сak=С(n)-1=С(mod n). Найдя та кое k, криптоаналитик вычисляет Сk=mak=m(n)-1=m(mod n), т.е. получает открытый текст m.

Пример 67. Пусть абонент А хочет послать сообщение m= абоненту В. А знает n=212887 и открытый ключ a=3061. Он зашифровы вает сообщение открытым ключом, т.е. ma=1932633061=С= 35947 и посыла ет это число в открытый канал связи. Таким образом, криптоаналитику становится известно сообщение С, модуль n и a. Далее криптоаналитик вычисляет Сa(mod n)=359473061(mod 212887). Затем он находит такое k, чтобы выполнялось Сak=359473061k=35947=С. Получили k=1084. И, нако нец, вычисляем Сk=359471084=193263.

Следующая атака осуществляется на базе общего модуля. Основ ные предпосылки для ее осуществления заключаются в следующем.

При реализации RSA можно раздать всем абонентам криптосети одинаковый модуль n, но каждому свои значения аi(открытый ключ) и I (секретный ключ). При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разны ми аi и аk, причем НОД(аi,аk)=1 (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных i и k.

Таким образом, пусть заданы: m – сообщение, а и b – два открытых ключа шифрования, n – модуль. Тогда щифротекстами являются c1= mа(mod n) и c2=mb(mod n). Криптоаналитику известны: n, а, b, c1 и c2. Да лее, так как а и b взаимно – простые числа, то воспользовавшись результа тами главы 4, можно найти такие целые числа x и y, что аx +by =1. Тогда, возведя c1 в степень x, а c2 – в степень y, получим: c1xc2y=(mа)x(mb)y= mаx+by =m1=m.

Пример 68. Пусть абонент А хочет послать сообщение m= другим абонентам. В. Абоненту А даны n=399799 и открытый ключ a=4397. Он зашифровывает сообщение открытым ключом, т.е. ma=c1= 2371354397=268100(mod 399799) и посылает это число в открытый канал связи. Абонент В хочет также послать сообщение m=237135 другим або нентам. Для В даны n=399799 и открытый ключ b=7517. Он зашифровы вает сообщение открытым ключом, т.е. mb=c2=2371357517=263851 (mod 399799) и также посылает это число в открытый канал связи. Таким обра зом, криптоаналитику известно: зашифрованные сообщения c1 и c2, мо дуль n, открытые ключи a и b. Далее криптоаналитик решает уравнение аx+by=1=4397x+7517y и получает x=-1607 и y=940. Затем он возводит c1 в степень |x|, т.е. c1|x|=d1=2681001607=12105(mod 399799), а c2 в степень |y|, т.е. c2|y|=d2=263851940=362154(mod 399799). Так как x<0, то находится (d1)- =12105-1=39501(mod 399799). (При y<0 искали бы (d2)-1). Далее, перем ножая (d1)-1d2=39501362154=237135(mod 399799)=m, т.е. получили открытый текст.

6.5. ПРОБЛЕМЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ RSA В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроен ных средств в популярных приложениях.

Важнейшей проблемой практической реализации - генерация боль ших простых чисел. Решение задачи «в лоб» - генерация случайного боль шого числа n (нечетного) и проверка его делимости на множители от вплоть до n0.5. В случае неуспеха следует взять n+2 и так далее1.

В принципе в качестве p и q можно использовать «почти» простые числа, то есть числа для которых вероятность того, что они простые, стре мится к 1. Но в случае, если использовано составное число, а не простое, В теории чисел показано, что вероятность того, что число порядка n будет простым составляет 1/ln n криптостойкость RSA падает. Имеются неплохие алгоритмы, которые по зволяют генерировать «почти» простые числа с уровнем доверия 2-100.

Поскольку простые числа должны выбираться таким образом, что бы факторизовать их произведение было вычислительно невозможно, ре комендуется брать их очень большими и одинаковой длины. Так, для n = pq длины 1024 бита, p и q должны быть длиной 512 бит.

Разность чисел p и q (p-q) также не должна быть маленькой, поскольку в этом случае p~q и, следовательно, p~(n)1/2. Таким образом, разложение n может быть найдено простым делением на все числа поряд ка (n)1/2.

Кроме того, числа p и q должны быть также "устойчивыми" прос тыми числами.

Число p является устойчивым (strong), если оно удовлетворяет трем условиям:

1. p-1 имеет большой простой делитель, обозначим его как r (т.е.

p1(mod r ));

2. p+1 имеет большой простой делитель, обозначим как s (т.е. ps 1(mod s ));

3. r-1 имеет большой простой делитель, обозначим его как t (т.е.

r=1(mod t )).

Условие 1 не позволит успешно факторизовать n (p-1) методом Полларда, который позволяет быстро разложить число n на множители, если его делитель p имеет небольшие (скажем, меньше миллиона) простые делители. Условие 2 позволит избежать p+1 метода Ульямса, позволяю щего разложить n при условии, что p+1 имеет небольшие делители.

Условие 3 позволит избежать метода безключевого чтения RSA (цикли ческой атаки). Если p выбирается случайно и имеет довольно большой размер, то, как правило, p-1 и p+1 будут иметь большие простые делители.

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

Получить устойчивые простые числа можно следующим способом.

Генерируем большие простые числа s и t. Затем получаем такое простое число r, что r-1 делится на t (для этого рассматриваем нечетные числа вида r=kt+1, где k - последовательные натуральные числа, и проверяем их на простоту, пока не найдем простое). Теперь, имея простые r и s, строим новое простое p. Для этого вычисляем p=((sr-1-rs-1) mod rs)+xrs, где x – не которое целое число и проверяя p на простоту, находим устойчивое простое число p.

Следующая проблема - какой длины ключи следует использовать?

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

lg n Число операций Примечания Раскрываем на суперкомпьютерах 50 1.4* На пределе современных технологий 100 2.3* За пределами современных технологий 200 1.2* Требует существенных изменений в технологии 400 2.7* Не раскрываем 800 1.3* В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.

Сами авторы RSA рекомендуют использовать следующие размеры модуля n:

• 768 бит - для частных лиц;

• 1024 бит - для коммерческой информации;

• 2048 бит - для секретной информации1.

Третий немаловажный аспект реализации RSA - вычислительный, приходится использовать аппарат длинной арифметики. Если использует ся ключ длиной k бит, то для операций по открытому ключу требуется О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации но вых ключей требуется О(k4) операций.

По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время.

6.6. КРИПТОСИСТЕМА БЕЗ ПЕРЕДАЧИ КЛЮЧЕЙ Пусть абоненты А, В, С,... условились организовать секретную пе реписку между собой. Для этой цели они выбирают достаточно большое простое число р и такое, что р-1 хорошо разлагается на не очень большие простые множители. Если среди множителей такого числа кратных нет, то число р-1 называют евклидовым. Каждый из абонентов независимо один от другого выбирает случайное число, натуральное, взаимно простое с числом р-1: А, В, С,... – абоненты;

а, b, c,... – выбранные ими случайные числа. Далее, абонент А находит число из условия а1(mod (p)), 0 < <р-1;

(8) абонент В находит число из условия b1(mod (p)), 0 < <р-1, (9) где (p) – функция Эйлера, а, – секретные ключи абонента А;

b, – секретные ключи абонента В и т.д.

Пусть абонент А решает послать сообщение m абоненту В. Можно предполагать, что 0 < m < р-1. Тогда он сначала зашифровывает это сооб щение своим первым секретным ключом, находит:

m1mа(mod p), 0 < m1 < р (10) Данные оценки сделаны с учетом развития вычислительной техники вплоть до 2004 года.

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

m2m1b(mod p), 0 < m2 < р (11) и пересылает его обратно абоненту А. Абонент А, получив обратно свое дважды зашифрованное сообщение, шифрует его же в третий раз своим вторым ключом:

m3m2(mod p), 0 < m3 < р (12) и вновь отправляет его абоненту В. Последний расшифровывает эту шиф ротелеграмму при помощи своего второго ключа:

m4m3(mod p), 0 < m4 < р.

В самом деле, из сравнений (10) – (12) имеем:

m4mk(mod p), где kab(mod р-1).

В силу (8) и (9) k1(mod (p)). Поэтому m4m(mod p), а так как каждое из них положительно и меньше p, то m4=m.

Пример 69. Пусть абоненты A и B решили установить между со бой скрытую связь без передачи ключей. Они выбрали для этого простое число p = 9551. Тогда p-1=9550.

Абонент A выбирает случайное число a=8159, а абонент B – b=7159. Абонент A решает сравнение: 81591(mod (9551)), 0<< и находит = 6639, а абонент B решает сравнение: 71591(mod (9551)), 0<<9550 и находит = 6139.

Абонент A решает послать секретное сообщение абоненту B m=7032. Тогда он сначала шифрует сообщение своим первым ключом:

m1mа(mod p)= 703281593(mod 9551)= 153.

Абонент B, получив это сообщение, шифрует его своим первым ключом: m2m1b(mod p)= 1537159(mod 9551)= 4896, и пересылает его або ненту А, который, получив зашифрованное сообщение, шифрует его же в третий раз своим вторым ключом: m3m2(mod p) =48966639(mod 9551)= 7577 и отправляет его абоненту В, который расшифровывает эту шифро телеграмму при помощи своего второго ключа: m4m3(mod p)= 76139(mod 9551)= 7032.

Пример 70. А теперь рассмотрим похожий пример, но с большими числами, а именно пусть абоненты A и B выбирают случайное число p = 47285301313. Далее абонент A выбирает случайное число a= 42412084309938365114701009965471731267159726697218119, а абонент B – b= 65843. Абонент A решает сравнение: 7010099654717312671597266972181191(mod ( 986593281521497120414687020801267626233049500247285301313)), 0 < < 00247285301312 и находит = 95758405828622569613369504272231654775, а абонент B решает сравне ние: 5843 1(mod ( 59391)), 0 < < 9390 и находит = 89679595249365486507640220987.

Абонент A решает послать секретное сообщение абоненту B m=16439530856237023359734047455621923453212389086. Тогда он снача ла шифрует сообщение своим первым ключом: m1mа(mod p)= (mod 020801267626233049500247285301313)= 26416933820229094970133 5616973062664572414115995.

Абонент B, получив это сообщение, шифрует его своим первым ключом: m2m1b(mod p)= (mod 0801267626233049500247285301313) = 3851807662985672512619192514870979350742436070, и пересылает его абоненту А. Абонент А, получив зашифрованное сообщение, шифрует его же в третий раз своим вторым ключом: m3m2(mod p) = (mod 131106986593281521497120414687020801267626233049500247285301313) = 36160948437196 и отправляет его абоненту В, который расшифровывает эту шифротелеграмму при помощи своего второго ключа: m4m3(mod p)= 1609484371962050785008947982616772154473648909901784058010689679595249365486507640220987( mоd 49500247285301313)= 6.7. АЛГОРИТМ ЭЛЬ-ГАМАЛЯ Поиски более эффективных систем открытого шифрования при вели к тому, что в 1985 году Т.Эль-Гамаль (США) предложил алгоритм на основе возведения в степень по модулю большого простого числа p.

Криптоалгоритм не запатентован, но попадал под действие патента на метод ключевого обмена Диффи-Хеллмана.

В отличие от RSA, метод Эль-Гамаля основан на проблеме дис кретного логарифма. Этим он и похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восста новить аргумент по значению (то есть найти логарифм) довольно трудно.

Рассмотрим схему алгоритма.

Основу системы составляют параметры p и n - числа, первое из которых - простое, а второе - целое.

Абонент А генерирует секретный ключ и вычисляет открытый ключ y = n mod p. Если абонент Б хочет послать А сообщение m, то он выбирает случайное число k, меньшее p и вычисляет:

y1 = nk mod p и y2 = m yk, где - побитовое сложение по модулю 2.

Затем Б посылает (y1,y2) А.

А, получив зашифрованное сообщение, восстанавливает его:

m = (y1 mod p) y2.

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

Уравнение расшифровки в этом случае будет иметь вид:

m=y2/y1k mod p.

Пример 71. Пусть абоненты A и B решили установить между собой скрытую связь с открытым ключом на базе алгоритма Эль-Гамаля.

Абонент A выбрал простое число р=1125899906842679 и целое число n = 745819352812378.

Затем абонент А генерирует секретный ключ = 725391906243661, и вычисляет открытый ключ y = nmod p = mod 1125899906842679=1124568734648807 и передает числа p, n и y в от крытый канал.

Пусть абонент Б хочет послать А сообщение m=4567345. Он выби рает случайное число k= 51394216073587 меньшее p и вычисляет: y1= nkmodp =440797012227888, ykmodp = 112456873464880751394216073587=3804 8279630195, y2= myk=380488283459650 и посылает А пару (y1, y2).

Абонент А, получив зашифрованное сообщение, восстанавливает его:

m=(y1 mod p y2.=(440797012227888725391906243661 mod 380488283459650)= 380488279630195 380488283459650=4567345.

При использовании метода Эль-Гамаля в системе открытого шиф рования с модулем модулем p из 150 знаков достигается та же степень защиты, что для алгоритма RSA с модулем из 200 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако в таком вари анте открытого шифрования нет подтверждения подлинности сообщений.

Однако схема Эль-Гамаля не лишена определенных недостатков.

Среди них можно выделить следующие.

1.Отсутствие семантической стойкости. Если g – примитивный эле мент GF(p), то за полиномиальное время можно определить, является ли некоторое число x квадратичным вычетом, или нет. Это делается возведе нием в степень x(p-1)/2mod p. Если результат равен 1, то x - квадратичный вычет, если –1, то x квадратичный невычет. Затем пассивный противник проверяет, являются ли gk и gt квадратичными вычетами. gkt будет квадра тичными вычетом тогда и только тогда, когда gk и gt являются квадратич ными вычетами. Если это так, то y2= mykmod p будет квадратичным выче том тогда и только тогда, когда сообщение m будет само квадратичным вычетом. То есть, пассивный противник будет иметь некоторую информа цию об открытом тексте имея лишь шифрованный текст и открытый ключ.

2. Делимость шифра. Если дан шифрованный текст (y1,y2), то мож но получить другой шифрованный текст, изменив только вторую часть сообщения. Действительно, умножив y2 на gu (u0), мы получим шифро текст для другого сообщения m1=mgu.

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

В заключении заметим, что алгоритм цифровой подписи DSA, раз работанный NIST (National Institute of Standard and Technology) и являю щийся частью стандарта DSS, опирается на рассмотренный метод.

6.8. КРИПТОСИСТЕМЫ НА БАЗЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ Рассмотренная выше криптосистема Эль-Гамаля, базируется на том, что задача логарифмирования в конечном поле является достаточно сложной с вычислительной точки зрения. Однако конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 1985 году Коб лиц и Миллер (причем независимо друг от друга) предложили использо вать для построения криптосистем алгебраические структуры, определен ные на множестве точек эллиптической кривой (ЭК). Рассмотрим опреде ление ЭК над полями Галуа.

Пусть p>3 простое число, a,bGF(p), такие, что 4a2+27b20.

Эллиптической кривой E над полем GF(p) называется множество решений (x,y) уравнения:

y2 = x3 +ax+b mod(p) (13) над полем GF(p) вместе с дополнительной точкой, называемой точкой в бесконечности.

Представление ЭК в виде уравнения (13) носит название эллипти ческой кривой в форме Веерштрасса.

Если обозначить количество точек на кривой E через NE. Тогда, согласно теореме Хассе, NE=p+1-t, где |t|2(p)0.5.

NE называется порядком кривой E, а – t следом кривой E.

Для точек на кривой вводится бинарная операция сложения, кото рая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля:

1. += 2. Для любых (x,y)E, (x,y)+ =(x,y) 3. Для любых (x,y)E, (x,y)+(x,-y)= 4. Для любых (x1,y1)E, и (x2,y2)E, x1x2, (x1,y1)+(x2,y2)=(x3,y3), где x3=2- x1- x2, y3=(x1-x3)-y1, = (y2-y1)/(x2-x1).

5. Для любых (x1,y1)E, и y10, (x1,y1)+(x1,y1)=(x3,y3), где x3=2-2x1, y3=(x1-x3)-y1, = (3 x12+a)/2y1.

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

Если NE=p+1,то E называется суперсингулярной.

Пользуясь операцией сложения точек на кривой, можно естествен ным образом ввести операцию умножения точки PE на произвольное целое число k:

kP=P+P+…+P.

Где операция выполняется k раз.

Построим теперь одностороннюю функцию, на базе которой будем строить криптосистему.

Пусть E – ЭК, точка PE. Возьмем kZ, причем k

Теперь рассмотрим криптографический протокол, аналогичный протоколу Диффи-Хелмана.

Для установления секретной связи два пользователя A и B выбира ют ЭК E и точку P на ней. Затем A и B генерируют независимо друг от друга по секретному числу и. Затем пользователь A вычисляет произ ведение P и пересылает его B, а пользователь B вычисляет P и пересы лает его A. При этом параметры кривой, координаты точки на ней, значе ния произведений являются открытыми и могут передаваться по незащи щенным каналам связи. Далее пользователь A умножает присланное зна чение P на, получив после этого P, пользователь B умножает при сланное значение P на, получая такой же результат – P. Таким обра зом, оба пользователя получили общее секретное значение (координаты точки P на ЭК), которое они могут использовать для получения сек ретного ключа шифрования. Необходимо отметить, что криптоаналитику для восстановления ключа потребуется решить сложную с вычислитель ной точки зрения математическую задачу восстановления и по из вестным E, P, P и P.

Пример 72. Пусть абоненты A и B решили провести передачу со общений используя криптосистему на базе ЭК. Для этого они выбрали ЭК E: y2 = x3 +157x+223 mod(743), и точку P(117,692) на ней. Затем A генерирует секретное число = 735.

Пользователь B генерирует секретное число = 529.

Затем пользователь A вычисляет произведение P = (517,488) и пе ресылает его B, а пользователь B вычисляет P = (472,687) и пересылает его A. Далее пользователь A умножает присланное значение P на, получив после этого P=(332,590). Пользователь B умножает прислан ное значение P на, получая такой же результат – P=(332,590). Таким образом, оба пользователя получили общее секретное значение (коорди наты точки P на ЭК), которое они будут использовать в качестве обще го секретного ключа.

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

7. АУТЕНТИФИКАЦИЯ И ЭЛЕКТРОННАЯ ПОДПИСЬ 7.1. ПРОТОКОЛЫ АУТЕНТИФИКАЦИИ Назначение и суть протоколов аутентификации (иногда называе мых протоколами идентификации) состоит в подтверждении подлинности информации. Например, предотвращение доступа к компьютерной систе ме лиц, не являющихся ее пользователями, а также предотвращение до ступа пользователей к тем ресурсам, на которые у них нет полномочий.

Одним из наиболее эффективных практических протоколов аутентифика ции является протокол Шнорра. Рассмотрим его схему.

Пусть р и q – простые числа, причем q делит р-1. Пусть gGF(p) такое, что gq1(mod p), g1. Далее, пусть kGF(q) и y=g-k(mod p), Таким образом, опять возникла задача дискретного логарифмирования, т.е. по за данному значению y и при известных р, q, и g, необходимо найти k. Тогда алгоритм аутентификации будет состоять в следующем.

1. Абонент А выбирает случайное число a из множества {1,…, q-1}, вычисляет r=ga(mod p) и посылает его абоненту В. (Величина r мо жет быть вычислена заранее) 2. Абонент В выбирает случайное число e из множества {1,…, 2t-1}, где t – некоторый параметр, и посылает его абоненту A.

3. Абонент А вычисляет s= a+ ke(mod q) и посылает его абоненту В.

4. Абонент В проверяет соотношение r=gsye(mod p) и, если оно выпол няется, принимает доказательство, иначе отвергает.

Пример 73. Пусть абонент B решил проверить полномочия або нента А. Для этого они с абонентом B выбрали числа q=984563, p=11814757 и g=10112979. Затем абонент А выбирает секретный ключ k= 729417 и вычисляет открытый ключ y=g-k(mod p)=10112979-729417(mod 11814757)=3767753. Затем абонент А выбирает случайное число a= 519231 и вычисляет r=ga(mod p)=10112979519231(mod 11814757)=7848734 и посылает его абоненту В. Абонент В выбирает случайное число e= 76314858 и посылает его абоненту A. Абонент А, получив это число, вы числяет s=a+ke(mod q)=(519231+729417*76314858)(mod 984563)= и посылает его абоненту В. Абонент В, получив это число, вычисляет gsye(mod p)= 10112979471575376775376314858(mod 11814757)=7848734.

Пример 74. А теперь рассмотрим пример на эту же тему, но с большими числами. Пусть абонент B решил проверить полномочия або нента А. Для этого они с абонентом B выбрали числа q= 722347423367021691262933787104118513, p= 4074477207784543316290607287 и g= 5478935475349017949. Затем абонент А выбирает секретный ключ k= 7295623869010581752957901762390670675487945867563 и вычисляет от крытый ключ y=g-k(mod p)= 35475349017949-7295623869010581752957901762390670675487945867563(mod 4087891643314074477207784543316290607287)= 360411843753141724894950833309. Затем абонент А выбирает случайное число a=5190388978797754067832766596238127895245963785, вычисляет r=ga(mod p)= (mod 207784543316290607287)= 3822849771 и посылает его абоненту В. Абонент В выбирает случайное число e= 858 и посылает его абоненту A. Абонент А, получив это число, вычисляет s=a+ke(mod q)=(5190388978797754067832766596238127895245963785 + 7295623869010581752957901762390670675487945867563* 047185965479458694687397865967803727245674858)(mod 6722347423367021691262933787104118513)= 694418257220665517251888 и посылает его абоненту В. Абонент В, получив это число, вычисляет gsye(mod p)= (mod 316290607287)= 95*1675751187114338063500949009188674824208541085181883(mod 756192664087891643314074477207784543316290607287)= Существуют также и другие схемы. Рассмотрим из них схему аутентификации Фейге-Фиата-Шамира.

Пусть n – произведение двух больших простых чисел. Для генера ции открытых и закрытых ключей абонент A выбирает k различных чисел 1, 2,…k, каждое из которых является квадратичным вычетом (см. гл.

3.6) по модулю n. Строка 1, 2,…k служит открытым ключом. Затем вычисляются наименьшие значения 1, 2,…k, для которых i=sqrt(I-1) (mod n). Строка 1, 2,…k служит секретным ключом. Далее выполняется следующий протокол.

1. Абонент А выбирает случайное число a из множества {1,…, n-1} и вычисляет r=a2(mod n) и посылает его абоненту В.

2. Абонент В посылает А строку из k случайных битов – c1, c2,… ck 1 2 k 3. Абонент А вычисляет y= a(1c 2c …kc )(mod n) и посылает его абоненту В.

1 2 k 4. Абонент В проверяет, что r=y2(1c 2c …kc )(mod n) Абонент A и В повторяют этот протокол t раз, пока В не убедится, что A знает 1, 2,… k. Шанс, что A обманет В t раз, равен 1 из 2kt.

Пример 75. Рассмотрим работу этого алгоритма сначала на примере небольших чисел. Пусть n = 1113=143. Тогда возможными квадратичными остатками являются числа:

1. 1/x21 (mod 143) имеет решения x= 1, 12, 131, 142.

2. 3/x21 (mod 143) имеет решения x=17, 61, 82, 126.

3. 4/x21 (mod 143) имеет решения x= 2, 24, 119, 141.

4. 9/x21 (mod 143) имеет решения x= 3, 36, 107, 140.

5. 12/x21 (mod 143) имеет решения x=21, 34, 109, 122.

6. 14/x21 (mod 143) имеет решения x=27, 38, 105, 116.

7. 16/x21 (mod 143) имеет решения x=4, 48, 95, 139.

8. 22/x21 (mod 143) имеет решения x=55, 88.

9. 23/x21 (mod 143) имеет решения x=32, 45, 98, 111.

10. 25/x21 (mod 143) имеет решения x= 5, 60, 83, 138.

11. 26/x21 (mod 143) имеет решения x=13, 130.

12. 27/x21 (mod 143) имеет решения x=40, 51, 92, 103.

13. 36/x21 (mod 143) имеет решения x=6, 71, 72, 137.

14. 38/x21 (mod 143) имеет решения x=18, 70, 73, 125.

15. 42/x21 (mod 143) имеет решения x=31, 57, 86, 112.

16. 48/x21 (mod 143) имеет решения x=42, 68, 75, 101.

17. 49/x21 (mod 143) имеет решения x= 7, 59, 84, 136.

18. 53/x21 (mod 143) имеет решения x=14, 25, 118, 129.

19. 55/x21 (mod 143) имеет решения x=22, 121.

20. 56/x21 (mod 143) имеет решения x=54, 67, 76, 89.

21. 64/x21 (mod 143) имеет решения x=8, 47, 96, 135.

22. 66/x21 (mod 143) имеет решения x=66, 77.

23. 69/x21 (mod 143) имеет решения x=28, 50, 93, 115.

24. 75/x21 (mod 143) имеет решения x=19, 58, 85, 124.

25. 77/x21 (mod 143) имеет решения x=44, 99.

26. 78/x21 (mod 143) имеет решения x=65, 78.

27. 81/x21 (mod 143) имеет решения x= 9, 35, 108, 134.

28. 82/x21 (mod 143) имеет решения x=15, 37, 106, 128.

29. 88/x21 (mod 143) имеет решения x=33, 110.

30. 91/x21 (mod 143) имеет решения x=39, 104.

31. 92/x21 (mod 143) имеет решения x=53, 64, 79, 90.

32. 100/x21 (mod 143) имеет решения x=10, 23, 120, 133.

33. 103/x21 (mod 143) имеет решения x=31, 57, 86, 112.

34. 104/x21 (mod 143) имеет решения x=26, 117.

35. 108/x21 (mod 143) имеет решения x=41, 63, 80, 102.

36. 113/x21 (mod 143) имеет решения x=16, 49, 94, 127.

37. 114/x21 (mod 143) имеет решения x=20, 46, 97, 123.

38. 121/x21 (mod 143) имеет решения x=11, 132.

39. 126/x21 (mod 143) имеет решения x=29, 62, 81, 114.

40. 130/x21 (mod 143) имеет решения x=52, 91.

41. 133/x21 (mod 143) имеет решения x=43, 56, 87, 100.

Обратными значениями (по mod 143) и их квадратными корнями являются следующие числа:

-1 =sqrt(-1) 1. 1 1 2. 3 48 3. 4 36 4. 9 16 5. 12 12 6. 14 92 7. 16 9 8. 9. 23 56 10. 25 103 11. 12. 27 53 13. 36 4 14. 38 64 15. 42 126 16. 48 3 17. 49 108 18. 53 27 19. 20. 56 23 21. 64 38 22. 23. 69 114 24. 75 82 25. 26. 27. 81 113 28. 82 75 29. 30. 31. 92 14 32. 100 133 33. 103 25 34. 35. 108 49 36. 113 81 37. 114 69 38. 39. 126 42 40. 41. 133 100 Видим, что у чисел 22, 26, 55, 66, 77, 78, 88, 91, 104, 121 и 130 нет обратных значений. Это объясняется тем, что они не взаимно просты с числом 143. Кроме того, должно быть ровно (11-1)(13-1)/4=30 квадратич ных остатков по mod 143.

Выбираем число k = 27. Таким образом, абонент А получает открытый ключ состоящий из 27 значений, например, = (9, 12, 14, 16, 23, 25, 27, 36, 38, 42, 48, 49, 53, 56, 64, 69, 75, 81, 82, 92, 100, 103, 108, 113, 114, 126, 133). Соттветственно секретным ключом является =(4, 21, 53, 3, 54, 31, 14, 2, 8, 29, 17, 41, 40, 32, 18, 20, 15, 16, 19, 27, 43, 5, 7, 9, 28, 30,10).

Дальше выполняется протокол.

1. Абонент А выбирает случайным образом число a=113 меньше n и вычисляет r=a2(mod n)= 1132(mod 143)=42.

2. Абонент B посылает А строку из k случайных битов (c1, c2,… ck) – ( 0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1).

1 2 k 3. Абонент А вычисляет y= a(1c 2c …kc )(mod n) =70 и посылает его абоненту В.

1 2 k 4. Абонент В вычисляет y2(1c 2c …kc )(mod n)=42 и убеждается, что это значение совпадает с r.

2. Абонент A и В повторяют этот протокол столько раз, пока В не убедится, что A знает секретный ключ.

А теперь приведем похожий пример, но с большими числами.

Пример 76. Пусть n = 97127=12319. Выбираем число k = 105.

Затем определяем k квадратичных вычетов (1, 2,…k), которые будут открытым ключом – (11264, 1120, 3297, 7657, 9840, 12025, 1893, 4082, 6273, 539, 2738, 4939, 7142, 9347, 11554, 3655, 5868, 8083, 10300, 200, 2421, 9096, 11325, 1237, 3470, 5705, 7942, 103, 2346, 4591, 6838, 9087, 11338, 5784, 8043, 10304, 248, 2513, 4780, 9320, 11593, 1549, 3826, 6105, 8386, 2922, 5211, 7502, 9795, 12090, 2068, 6668, 8971, 11276, 1264, 3573, 5884, 10512, 510, 2829, 5150, 7473, 9798, 4466, 6799, 9134, 11471, 1491, 3832, 8520, 10867, 897, 3248, 5601, 7956, 2714, 5077, 7442, 9809, 12178, 2230, 6978, 9355, 11734, 1796, 4179, 6564, 1412, 3805, 6200, 8597, 10996, 1078, 5886, 8293, 10702, 794, 3207, 5622, 560, 2983, 5408, 7835, 10264, 376).

После этого определяем (1, 2,…k), которые будут являться секретным ключом – (34, 157, 1865, 2518, 3170, 541, 1340, 45, 281, 482, 2475, 505, 158, 2848, 3416, 2818, 4251, 2257, 2977, 2998, 377, 1616, 3878, 2714, 2877, 2347, 1233, 4647, 4820, 362, 274, 1644, 5603, 3819, 2833, 3736, 3198, 3467, 1510, 3447, 1376, 1981, 3461, 974, 2096, 1906, 2476, 1482, 2191, 3886, 3408, 5223, 4939, 4991, 4976, 4117, 1055, 3573, 4326, 1285, 1390, 1504, 2521, 243, 1487, 315, 718, 3476, 4767, 2468, 2454, 2663, 1447, 2992, 5051, 137, 749, 3737, 1809, 3432, 3999, 683, 3752, 735, 3474, 2089, 475, 1258, 341, 4094, 1685, 811,173,3012, 2311, 1481, 1522, 379, 1735, 2004, 681, 1065, 161, 2697, 2453).

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

1. Абонент А выбирает случайным образом число a=11678 меньше n и вычисляет r=a2(mod n)=4354.

2. Абонент B посылает А строку из k случайных битов (c1, c2,… ck) – ( 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1).

1 2 k 3. Абонент А вычисляет y= a(1c 2c …kc )(mod n) =10751 и посылает его абоненту В.

1 2 k 4. Абонент В вычисляет y2(1c 2c …kc )(mod n)=4354 и убеждается, что это значение совпадает с r.

Абонент A и В повторяют этот протокол столько раз, пока В не убедится, что A знает секретный ключ.

7.2. ЦИФРОВАЯ ПОДПИСЬ Криптосистема "открытый ключ" неудобна в том смысле, что по лучатель сообщения не знает, кто является отправителем сообщения. Это го недостатка лишены протоколы "электронной подписи". Рассмотрим из них два. Первый – на базе RSA, а второй на основе алгоритма Эль-Гамаля.

Пусть имеется банкир A и несколько вкладчиков – B1, B2, B3, ….

Банкир и каждый из вкладчиков независимо друг от друга выбирают два больших простых числа и держат их в секрете. Пусть P и Q – простые числа банкира, pi и qi – простые числа вкладчика Bi, i = 1, 2, 3, …. Пусть далее R = PQ, ri = qipi, i = 1, 2, 3, …. И пусть банкир выбирает случайно целое число S с условиями 0 < S < (R), (S, (R))=1, а каждый из вклад чиков также случайно и независимо друг от друга выбирает число si с условиями 0 < si < (ri), (si, (ri))=1, i = 1, 2, 3, …. После этого публикует ся всем доступная телефонная книга:

A: R, S B1: r1, s B2: r2, s …………….

Далее каждый из них, и банкир и вкладчики, находят свои секрет ные T, ti ключи из условий:

ST1(mod (R)), 0 < T < (R), siti1(mod (ri)), 0 < ti < (ri), i = 1, 2, 3, ….

Пусть вкладчик Bk собирается дать распоряжение m банкиру A, и пусть 0 < rk < R.

Последнее неравенство существенно для дальнейшего. Положим для удобства записи B=B, r=rk, t=tk, s=sk. Будем считать m < r и (m, r)=1.

k Вкладчик B шифрует распоряжение m сначала своим секретным ключом:

m1mt(mod r), 0 < m1 < r, а потом открытым ключом банкира:

m2m1S(mod R), 0 < m2 < R.

Банкир A, получив шифрованную телеграмму m2, расшифровывает ее пользуясь сначала своим секретным ключом T:

m3m2T(mod R), 0 < m3 < R.

а потом открытым ключом s вкладчика:

m4m3s(mod r), 0 < m4 < r, и получает m4 =m.

Действительно, так как m3m2T(mod R), а m2m1S(mod R), то m3m1TS(mod R), где ST1(mod (R)). Если (m1, R)=1, то по теореме Ферма-Эйлера m1TSm1(mod R), т.е. m3m1(mod R). Но 0

Пример 77. Пусть банкир A выбирает простые числа 10243 и 57037. Вкладчик B выбирает простые числа 175261 и 817549. Таким образом, R=1024357037=584229991 и r=175261817549=143284455289.

Пусть 381259693 и 3387425143 – открытые ключи банкира и вкладчика соответственно.

Находим секретный ключ банкира из условия:

ST1(mod (R))=381259693T1(mod (584229991)), 0 < T < 584162712.

Откуда T=182938789.

Далее находим секретный ключи вкладчика из условия:

st1(mod (r))=3387425143t1(mod (143284455289)), 0

Тогда открытая телефонная книга имеет вид:

A: 584229991, 381259693;

B: 143284455289, 3387425143.

Вкладчик B дает поручение m=134645771 своему банкиру A и замечая, что R

m1=134645771381259693116030491(mod 584229991), m2=11603049111178866736738467700641(mod 143284455289).

Банкир A, получив шифрованную телеграмму m2 = 38467700641, и замечая, что R

m3=384677006413387425143116030491(mod 143284455289), m4=116030491182938789134645771(mod 584229991).

А так как 134645771<584229991, то банкир делает вывод, что 134645771 и есть распоряжение вкладчика.

Пример 78. А теперь рассмотрим похожий пример, но с большими числами, а именно пусть банкир A выбирает простые числа P= 205208498221 и Q= 189390869761855907572637988050133502132777. Вкладчик B выбирает простые числа p= 837441302815640277772901915313574263597826351 и q= 068752870260867081. Таким образом, R=PQ= 404280671468710289717 и r=pq= 1707353985214366888130251431.

Пусть S=123876132205208335762278423601 и s= 4227858270210279 – открытые ключи банкира и вкладчика соответствен но.

Находим секретный ключ банкира из условия:

ST1(mod (R))=123876132205208335762278423601T1(mod ( 409950278676776821404280671468710289717)), 0 < T < 386 569056839027388336129999658720. Откуда T= 137940434810257460401.

Далее находим секретный ключ вкладчика из условия:

st1(mod (r))=1786393878363164227858270210279t1(mod ( 742232427841226232435332781707353985214366888130251431)), 0

Откуда t= 6153319.

Вкладчик B дает поручение m= 123343674951737516 своему банкиру A и замечая, что R

m1= 6479375920337706284851138975131623170385268669095130 (mod 09950278676776821404280671468710289717), m2= 55500695895883062 (mod 985214366888130251431).

Банкир A, получив шифрованную телеграмму m2 = 211395236453568380666048559059355500695895883062, и замечая, что R

m3= 62178639387836316 5130 (mod 30251431), m4= 200431245123343674951737516 (mod 386537523017258344 71468710289717).

А так как < 6786561409950278676776821404280671468710289717, то банкир делает вывод, что 812341242521515435903200431245123343674951737516 и есть распоряжение вкладчика.

А теперь рассмотрим цифровую подпись на базе алгоритма Эль Гамаля. Основные положения алгоритма таковы.

Пусть имеются два простых числа – p и 2p+1, p >2.Тогда v и w – образующие мультипликативных групп Z*p и Z*2p+1 (т.е. групп обратимых элементов в Zp и Z*2p+1). Далее вычисляем v0=(p+(p+1)v)(mod 2p), которая будет являться образующей в Z*2p. Затем выбираем секретный ключ x из Z*p. Далее вычисляем открытый ключ y. Он определяется следующим образом: z=v0x(mod 2p);

y=wz(mod 2p). Сообщение s, к которому надо при крепить цифровую подпись, принадлежит кольцу Z2p, т.е. sZ2p. Для вы числения электронной подписи выбираем случайное число rZ*2p и в качестве подписи передаем пару чисел (a,b), где a=a(r,s)=z-1rs(mod 2p), b=b(r,s)=wr(mod 2p+1). Для проверки подлинности подписи необходимо воспользоваться равенством ya=bs(mod 2p+1).

Пример 79. Пусть имеются два простых числа – p=1013 и 2p+1=2027. Образующие мультипликативных групп Z*1013 и Z*2027 соот ветственно равны v=958 и w=1352. Далее вычисляем v0=(p+(p+1)v)(mod 2p)=(1013+(1013+1)958)(mod 2026)=1971. Выбираем секретный ключ x из Z*p, x=835. Далее вычисляем открытый ключ y: z=v0x(mod 2p)=1971835(mod 2026)=855, y=wz(mod 2p)=1352855(mod 2026)=1758. Создаем сообщение s=1143, к которому надо прикрепить цифровую подпись. Для этого выби раем случайное число rZ*2p: r=1983. Вычисляем пару (a,b): a=z-1rs(mod 2p)=855-119831143(mod 2026)=191719831143(mod 2026)=497;

b=wr(mod 2p+1)=13521983(mod 2027)=920. Посылаем вычисленную пару (a,b) в от крытый канал. Проверяем подлинность подписи: ya=1758497(mod 2027) =1269=bs=9201143(mod 2027).

8. КРИПТОГРАФИЧЕСКИЕ АЛГОРИТМЫ И ЗАЩИТА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ В последнее время защита информации перестала быть задачей только для государственных структур. С нею приходится сталкиваться и многим обычным пользователям персональных компьютеров (ПК). Идя навстречу их пожеланиям, многие производители программного обеспече ния ст али включать свои продукты функции защиты данных. Однако в большинстве случаев разработчики не ставят своей целью использовать в них сколько-нибудь стойкие алгоритмы. Они считают своей основной за дачей предоставить пользователю возможность защитить информацию либо от случайного несанкционированного доступа, либо от неквалифи цированного взломщика. Они, скорее, маскируют информацию, чем реа лизуют алгоритмы надежного криптографического закрытия. Проде монстрируем данное утверждение на двух программных продуктах.

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

Из пароля пользователя Word вырабатывает массив длиной байт, называемый гаммой (gamma[0…15]). далее, каждый байт открытого текста (open_text[i]) последовательно складывается побитно (XOR) с бай том гаммы. В результате получается шифрованный текст (cripto_text[i]), который мы можем видеть в файле с паролем, т.е. шифрование произво дится согласно формуле:

cripto_text[i]=open_text[i] XOR gamma[i mod 16], где mod 16 – операция получения остатка от целочисленного деления на 16.

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

Самый частый символ в документе Word – это пробел (его значе ние в кодировке ASCII есть 0х20). Следовательно, самым частым симво лам в таблице частот соответствуют зашифрованные пробелы. Складывая побитно значения этих символов с 0х20, мы получим все 16 знаков гаммы.

Далее, зная гамму, расшифровываем весь текст.

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

Теперь посмотрим, как защищаются пароли пользователя в опера ционных системах (ОС) Microsoft Windows 95 первых версий (до OSR 2).

ОС Microsoft Windows 95 не является многопользовательской и не предоставляет возможность пользователям разделять свои ресурсы. Тем не менее, она запрашивает у пользователя при входе в систему его имя и пароль. Но если он ничего не ответит (нажмет кнопку Esc), ОС все равно разрешит ему работать дальше. Но для того, что бы работать в локальной вычислительной сети (ЛВС), где ПК доступны ресурсы или серверы, не обходимы соответствующие пароли, причем, возможно, различные. Что бы пользователю не нужно было их все запоминать, ОС Microsoft Windows 95 записывает пароли для доступа к ресурсам ЛВС в специаль ный файл с именем "имя_пользователя.pwl". В этом файле данные шифру ются на том самом пароле, который система запрашивает у пользователя при его входе в систему. Если пароль введен правильно, то в дальнейшем ОС сама подставляет соответствующий пароль при запросе пользователя на доступ к ресурсам или серверам ЛВС.

Данные в *.pwl файлах шифруются следующим образом. Из пароля пользователя по алгоритму шифрования RC4 вырабатывается гамма. Каж дый пароль на доступ к соответствующему ресурсу вместе с некоторой служебной информацией суммируется побитно с полученной гаммой. То есть каждый раз при шифровании используется одна и та же гамма. Если учесть, что *.pwl файл содержит зашифрованную запись, начинающегося с имени пользователя, дополненного до 20 символов пробелами, то задача вскрытия пароля становится элементарной. Получив первые 20 знаков гаммы, мы можем прочитать любой сохраненный в файле пароль ( учиты вая то обстоятельство, что редко когда используют пароли длиной более 10 символов).

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

ЗАКЛЮЧЕНИЕ Известно, что не существует единого шифра, подходящего для всех случаев жизни. Выбор способа шифрования зависит от особенностей информации, ее ценности и возможностей владельцев по защите своей ин формации. Прежде всего подчеркнем большое разнообразие видов защи щаемой информации: документальная, телефонная, телевизионная, компьютерная и т.д. и т.п. Каждый вид информации имеет свои специфи ческие особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое значение имеют объемы и требуемая скорость передачи шифрованной информации.

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

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

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

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

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

ЛИТЕРАТУРА 1. Аграновский А.В., Балакин А.В, Хади Р.А. "Классические шифры и ме тоды их криптоанализа", М: Машиностроение, Информационные технологии, № 10, 2001.

2. Ван дер Ваден Б.Л. Алгебра, пер. с нем. 2–изд.– М.:Наука, 1979. – 352 с.

3. Воеводин В.В. Линейная алгебра. – М.:Наука, 1980. – 348 с.

4. Гантмахер Ф.Р. Теория матриц. – М.:Наука, 1966. – 576 с.

5. Гельфанд И.М., Райков Д.А., Шилов Г.Е. Коммутативные нормирован ные кольца. – М.:Физматгиз, 1959. – 356 с.

6. Ибрагимов Н.Х. Группы преобразований в математической физике.

М.:Наука, 1983. – 280 с.

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

8. Кон П. Универсальная алгебра. - М.:Мир. - 1968. – 351 с.

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

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

11. Левин М. Криптография. Руководство пользователя. - М.: Познава тельная книга плюс, 2001. – 320 с.

12. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб.:

Издательство "Лань", 2001. – 224 с.

13. Смирнов В.И. Курс высшей математики, том III, часть I – М:. Наука, Главная редакция физико-математической литературы, 1974. – 324 с.

14. Фрид Э. Элементарное введение в абстрактную алгебру. Пер. с венгер.–М.:Мир, 1979. – 260 с.

15. Чмора А.Л. Современная прикладная криптография. 2-е изд. – М.:

Гелиос, АРВ, 2002. – 256 с. ил.

16. Шеннон К.Э. Теория связи в секретных системах. В кн. Шеннона К.Э.

“Работы по теории информации и кибернетике”. – М.: ИЛ, 1963. – с.

333 – 402.

17. Введение в криптографию / Под общ. ред. В.В. Ященко. – М.:

МЦНМО, ”ЧеРо”, 1998. – 272 с.

оглавление ВВЕДЕНИЕ............................................................................. 1. КЛАССИЧЕСКИЕ ШИФРЫ И ОСНОВНЫЕ ПОНЯТИЯ.......................................................................... 1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ТЕРМИНОЛОГИЯ................ 1.2. ИЗ ИСТОРИИ КРИПТОГРАФИИ.................................................. 1.3. МАРШРУТНАЯ ТРАНСПОЗИЦИЯ.............................................. 2. МНОЖЕСТВА И ОТОБРАЖЕНИЯ............................ 2.1. МНОЖЕСТВА..................................................................................... 2.2. ОТОБРАЖЕНИЯ................................................................................ 2.3. БИНАРНЫЕ ОТНОШЕНИЯ........................................................... 2.4. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ.................................... 2.5. АЛГОРИТМ ДЕЛЕНИЯ В Z............................................................ 3. МНОЖЕСТВА С АЛГЕБРАИЧЕСКИМИ ОПЕРАЦИЯМИ............................................................... 3.1. БИНАРНЫЕ ОПЕРАЦИИ................................................................ 3.2. ПОЛУГРУППЫ И МОНОИДЫ...................................................... 3.3. ГРУППЫ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ......... 3.3.1 Симметрическая и знакопеременная группы.......................... 3.4. МОРФИЗМЫ ГРУПП........................................................................ 3.4.1 Изоморфизмы................................................................................ 3.4.2. Гомоморфизмы.............................................................................. 3.5. КОЛЬЦА. ОПРЕДЕЛЕНИЕ И ОБЩИЕ СВОЙСТВА................ 3.5.1. Сравнения. Кольцо классов вычетов.......................................... 3.5.2.. Гомоморфизмы и идеалы колец................................................ 3.5.3. Типы колец...................................................................................... 3.6. ПОЛЕ..................................................................................................... 3.6.1. Основные понятия........................................................................ 3.6.2. Поля Галуа...................................................................................... 3.7. КОЛЬЦО МНОГОЧЛЕНОВ............................................................ 3.7.1. Основные понятия и определения.............................................. 3.7.2. Алгоритм деления в кольце многочленов.................................. 3.7.3. Разложение в кольце многочленов............................................. 3.7.4. Факториальность евклидовых колец........................................ 3.7.5. Неприводимые многочлены......................................................... 4. ДИОФАНТОВЫ УРАВНЕНИЯ................................... 4.1. ДИОФАНТОВО УРАВНЕНИЕ ПЕРВОЙ СТЕПЕНИ................ 4.2. РЕШЕНИЕ СРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ......................... 5. СИММЕТРИЧЕСКИЕ КРИПТОСИСТЕМЫ........... 5.1 МОНО- И МНОГОАЛФАВИТНЫЕ ПОДСТАНОВКИ.................................. 5.2 СИСТЕМЫ ШИФРОВАНИЯ ВИЖИНЕРА................................................. 5.3 ПЕРЕСТАНОВКИ..................................................................................... 5.4 ГАММИРОВАНИЕ.................................................................................... 5.5 ДАТЧИКИ ПОЧТИ СЛУЧАЙНЫХ ЧИСЕЛ................................................. 5.6 СТАНДАРТ ШИФРОВАНИЯ DES............................................................. 5.7 СТАНДАРТ ШИФРОВАНИЯ ГОСТ-28147-89........................................ 5.8 БЛОЧНЫЕ ШИФРЫ................................................................................. 6. КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ.. 6.1. ОДНОСТОРОННИЕ ФУНКЦИИ.................................................... 6.2. ГЕНЕРАЦИЯ КЛЮЧЕЙ................................................................... 6.3. ОСНОВНЫЕ ПОЛОЖЕНИЯ КРИПТОСИСТЕМЫ RSA......... 6.4. НАДЕЖНОСТЬ СИСТЕМЫ RSA................................................... 6.5. ПРОБЛЕМЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ RSA.............. 6.6. КРИПТОСИСТЕМА БЕЗ ПЕРЕДАЧИ КЛЮЧЕЙ...................... 6.7. АЛГОРИТМ ЭЛЬ-ГАМАЛЯ............................................................ 6.8. КРИПТОСИСТЕМЫ НА БАЗЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ............................................................................................... 7. АУТЕНТИФИКАЦИЯ И ЭЛЕКТРОННАЯ ПОДПИСЬ........................................................................ 7.1. ПРОТОКОЛЫ АУТЕНТИФИКАЦИИ.......................................... 7.2. ЦИФРОВАЯ ПОДПИСЬ................................................................... 8. КРИПТОГРАФИЧЕСКИЕ АЛГОРИТМЫ И ЗАЩИТА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ... ЗАКЛЮЧЕНИЕ................................................................. ЛИТЕРАТУРА.................................................................... ИСТОРИЯ КАФЕДРЫ 1945-1966 РЛПУ (кафедра радиолокационных приборов и уст ройств). Решением Советского правительства в августе 1945 г. в ЛИТМО был открыт факультет электроприборостроения. Приказом по институту от 17 сентября 1945 г. на этом факультете была организована кафедра ра диолокационных приборов и устройств, которая стала готовить инжене ров, специализирующихся в новых направлениях радиоэлектронной тех ники, таких как радиолокация, радиоуправление, теленаведение и др. Ор ганизатором и первым заведующим кафедрой был д.т.н., профессор С. И.

Зилитинкевич (до 1951 г.). Выпускникам кафедры присваивалась квали фикация инженер-радиомеханик, а с 1956 г. – радиоинженер (специ альность 0705).

В разные годы кафедрой заведовали доцент Б.С. Мишин, доцент И.П. Захаров, доцент А.Н. Иванов.

1966–1970 КиПРЭА (кафедра конструирования и производства ра диоэлектронной аппаратуры). Каждый учебный план специальности коренным образом отличался от предыдущих планов радиотехнической специальности своей четко выраженной конструкторско–технологической направленностью. Оканчивающим институт по этой специальности при сваивалась квалификация инженер–конструктор–технолог РЭА.

Заведовал кафедрой доцент А.Н. Иванов.

1970–1988 КиПЭВА (кафедра конструирования и производства электронной вычислительной аппаратуры). Бурное развитие электронной вычислительной техники и внедрение ее во все отрасли народного хозяй ства потребовали от отечественной радиоэлектронной промышленности решения новых ответственных задач. Кафедра стала готовить инженеров по специальности 0648. Подготовка проводилась по двум направлениям– автоматизация конструирования ЭВА и технология микроэлектронных устройств ЭВА.

Заведовали кафедрой д.т.н., проф. В.В. Новиков (до 1976 г.), затем проф. Г.А. Петухов.

1988–1997 МАИ (кафедра микроэлектроники и автоматизации проектирования). Кафедра выпускала инженеров–конструкторов–техно логов по микроэлектронике и автоматизации проектирования вычисли тельных средств (специальность 2205). Выпускники этой кафедры имеют хорошую технологическую подготовку и успешно работают как в произ водстве полупроводниковых интегральных микросхем, так и при их про ектировании, используя современные методы автоматизации проектиро вания. Инженеры специальности 2205 требуются микроэлектронной про мышленности и предприятиям–разработчикам вычислительных систем.

Кафедрой с 1988 г. по 1992 г. руководил проф. С.А. Арустамов, за тем снова проф. Г.А. Петухов.

С 1997 ПКС (кафедра проектирования компьютерных систем).

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

С 1996 г. кафедрой заведует д.т.н., профессор Ю.А. Гатчин.

За время своего существования кафедра выпустила инженеров, из них по специальности 0705 – 2472 чел. и по специальности 0648 (2205) – 1597 чел. На кафедре защищено 56 кандидатских и докторских диссертаций.

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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