Previous: 6.3.1 Список видов атак, зарегистрированных Network ICE    UP: 6 Сетевая безопасность
Down: 7 Программирование для сетей (новые идеи, принципы и возможности)
    Next: 6.4.1 Алгоритм DES

Проблема сокрытия содержания послания при его транспортировке волновала людей с древних пор. Известно, что еще Цезарь (100-44 годы до нашей эры) при переписке использовал шифр, получивший его имя. В 1518 году Джоанес Тритемиус написал первую книгу по криптографии, где впервые были описаны многоалфавитные подстановочные шифры. Лишь в 1918 году во время первой мировой войны в Германии была применена шифровальная система ADFGVX. Позднее в 1933-45 годах в Германии была разработана и применена первая шифровальная машина (на этом принципе работает система crypt в UNIX). Мощное развитие криптография получила в период второй мировой войны. С этой шифровальной машиной связан и первый успех в области вскрытия сложных шифров.

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

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

• Знание использованного алгоритма не должно снижать надежность шифрования.
• Длина зашифрованного текста должна быть равна длине исходного открытого текста (это требование относится к числу желательных и выполняется не всегда).
• Зашифрованный текст не может быть прочтен без знания ключа.
• Каждый ключ из многообразия ключей должен обеспечивать достаточную надежность.
• Изменение длины ключа не должно приводить к изменению алгоритма шифрования.
• Если известен зашифрованный и открытый текст сообщения, то число операций, необходимых для определения ключа, не должно быть меньше полного числа возможных ключей.
• Дешифрование путем перебора всех возможных ключей должно выходить далеко за пределы возможностей современных ЭВМ.
• Если при шифровании в текст вводятся дополнительные биты, то алгоритм их внесения должен быть надежно скрыт.
• Не должно быть легко устанавливаемой зависимости между последовательно используемыми ключами.
• Алгоритм может быть реализован аппаратно.

В симметричных криптосистемах могут использоваться одно- или многоалфавитные подстановки (например, одно-алфавитная подстановка Цезаря), при этом производится замена символов исходного текста на другие с использованием достаточно сложных алгоритмов. Многоалфавитные подстановки несравненно более надежны. К числу простых методов шифрования относится способ перестановок символов исходного текста (этот метод эффективен только лишь при достаточно большой длине исходного текста). Множество перестановок символов для текста из N символов равно N!, что до какой-то степени гарантирует надежность процедуры. Несколько большую надежность предлагает метод гаммирования, когда на исходный текст накладывается псевдослучайная последовательность бит, генерируемая на основе ключа шифрования, например, с использованием операции исключающего ИЛИ. Обратное преобразование (дешифрование) выполняется генерацией точно такой же псевдослучайной последовательности и наложением ее на зашифрованной текст. Гаммирование уязвимо для случая, когда злоумышленнику становится известен фрагмент исходного текста. В этих обстоятельствах он без труда восстановит фрагмент псевдослучайной последовательности, а по нему и всю последовательность. Так если достаточно большое число сообщений начинается со слов "Секретно", а в конце ставится дата сообщения, расшифровка становится вопросом времени и терпения.

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

Таблица 6.4.1.

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

Шифрование и дешифрование базируются на использовании ключей. Математически это можно выразить следующим образом (cм. lglwww.epfl.ch/~jkienzle/digital_money/node11.html; www.ee.mtu.edu/courses/ ee465/groupa/overview.html):

E_K(M) = C
D_K(c) = M, где K - ключ, M - исходный текст; C - зашифрованный текст.

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

Шифры бывают поточными и блочными. В первом случае обработка исходного текста производится побитно или побайтно. Во втором - текст перед обработкой разбивается на блоки.

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

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

Конгруентность. a конгруентно b по модулю n (a ╨ _nb), если при делении на n a и b, получается идентичный остаток. Так 100 ╨ ₁₁ 34 (100 и 34 при делении на 11 дают остаток 1) и -6 ╨ ₈10 (ведь -6 =8(-1)+2). Мы всегда имеем a ╨ _nb для некоторого 0 ё bё n-1. Если a ╨ _nb и с╨ d, то справедливы равенства:

Аналогичная процедура для деления не всегда справедлива: 6╨ ₁₂18 но 3N 9. Приведенные здесь и далее математические определения и обоснования взяты из: http://lglwww.epfl.ch/~jkienzle/digital/node20.html.

Необходимо также вспомнить о знакомом всем со школьной скамьи понятии наибольшего общего делителя. Для a и b число (a,b) является наибольшим общим делителем, который делит a и b без остатка:

(56,98)=14; (76,190)=38

Теорема 1. Для любых a,b существуют целые числа x,y, для которых ax+by=(a,b). В данной статье не приводится доказательств представленных утверждений, их следует искать в книгах по дискретной математике.

В этом можно убедиться, решая уравнение 30x+69y=3 путем последовательных упрощающих подстановок (ищется целочисленное решение:

30x+69y=3

30x'+9y=3	[x'=x+2y]
3x'+9y'=3	[y'=y+3x']
3x"+0y'=3	[x"=x'+3y']

Легко видеть, что x"=1, y'=0 является решением окончательного уравнения. Мы можем получить решение исходного уравнения путем обратной подстановки.

x'=x"-3y'=1 y=y'-3x'=-3 x=x'-1y=7

Мы можем решить уравнение вида 30x+69y=15 путем умножения нашего решения: y=-15, x=35. Должно быть ясно, что уравнение не будет иметь целочисленного решения, если 15 заменить на что-то некратное (30,69)=3.

Все другие целочисленные решения 30x+69y=15 могут быть получены, варьируя первое решение:

y=-15+(30/3)t x=35 -(69/3)t для целого t

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

Важно то, что этот процесс реализуем на ЭВМ даже в случае, когда a и b имеют несколько сотен значащих цифр. Легко показать, что 600-значное число не потребует более чем 4000 уравнений. Теорема 1 справедлива и для простых чисел.

Во многих криптографических приложениях используется:

a a² a³ . mod p, где a и p целые числа.

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

Фокус заключается в том, что берется число и осуществляется возведение в квадрат.

432² = 186624; 186624 mod 987 = 81; 432⁴ mod 987 = 81² mod 987 = 639
432⁸ -> 639² mod 987 -> 690 .. 432⁵¹² -> 858
так как 678= 512+128+32+4+2, то:
432⁶⁷⁸->(81)(639)..(858) -> 204

Вычисления с использованием показателя включают в себя ограниченное число умножений. Если числа содержат несколько сотен цифр, необходимы специальные подпрограммы для выполнения таких вычислений. Рассмотрим последовательность степеней 2ⁿ mod 11:

2 4 8 5 10 9 7 3 6 1

Здесь числа от 1 до 10 появляются в виде псевдослучайной последовательности.

Теорема 2

Пусть p является простым числом. Существует такое a, что для каждого 1ё b ё p-1, существует такое 1ё x ё p-1, что a^x ╨ _pb, a не обязательно равно 2.

Степени 2 mod 7 равны 2, 4, 1. Далее числа повторяются, а числа 3, 5, или 6 не могут быть получены никогда. Рассмотрим некоторые следствия этой теоремы.

Следствие 4. Пусть a соответствует требованиям теоремы 2, тогда a^p-1 ╨ _p1.
Следствие 5. Для любого b N 0, b^p-1 ╨ _p1.
Следствие 6. Если x ╨ _(p-1)y, тогда b^x ╨ _pb^y

Лемма
Пусть b N 0, d наименьшее положительное число, такое что b^d ╨ _p1. Тогда для любого с>0 c b^c ╨ _p1 d делит c без остатка. В частности для следствия 5, d делит p-1 без остатка.

Согласно теореме 2, если p простое число, существует такое a, при котором равенство a^x ╨ _pb имеет решение для любого bN 0. Такое значение a называется примитивным корнем p, а x называется дискретным логарифмом b. Получение b при заданных a и x относительно просто, определение же x по a и b заметно сложнее. Многие современные системы шифрования основываются на факте, что никаких эффективных путей вычисления дискретных логарифмов не найдено. Никакого эффективного метода определения примитивных корней также неизвестно. Однако часто возможно найти примитивные корни в некоторых специальных случаях. Возьмем p=1223. p-1=2*13*47. Согласно лемме, если a не примитивный корень, тогда мы либо имеем a²⁶ , a⁹⁴ или
a⁶¹¹ ╨ ₁₂₂₃1. a=2 и a=3 не годятся, но a=5 соответствует всем трем условиям, таким образом, это значение является примитивным корнем. Мы могли бы сказать, что a=4 не может быть признано примитивным корнем без проверки.

Легко показать, что если a примитивный корень, a^x примитивный корень в том и только том случае, если (x,p-1)=1. В этом примере это означает, что число примитивных корней равно

1222*(1/2)*(12/13)*(46/47)=552

Таким образом, если мы выберем а произвольно, вероятность того, что это будет примитивный корень равна ~.45. Выбирая а наугад и тестируя, можно сравнительно быстро найти примитивный корень.

Наиболее современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм rsa (rivest-shamir-adleman - разработчики этой системы - Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на разложение больших чисел на множители.

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

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

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

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

Рис. 6.4.1.

Если хакер умудрится вставить свою ЭВМ в разрыв канала, соединяющего субъектов А и В, у него появляется возможность перехватывать в том числе и шифрованные сообщения. Пусть субъект А сформировал пару ключей К_1А и К_2А (ключ с индексом 2 является секретным), аналогичную пару ключей сгенерировал субъект В (К_1В и К_2В ). Хакер же тем временем подготовил две пары ключей (К_1ХА:К_2ХА и К_1ХВ:К_2ХВ ). Когда субъект А пошлет открытый ключ К_1А субъекту В, хакер его подменит ключом К_1ХА . Аналогичную процедуру он проделает с ключом К_1В, посланным от В к А. Теперь сообщение А к В, зашифрованное с помощью ключа К_1ХА будет послано В. Хакер его перехватывает, дешифрует с помощью ключа К_2ХА, шифрует с помощью ключа К_1ХВ и посылает В. Субъект В, получив послание, дешифрует его с помощью "секретного" ключа К_2ХВ, полученного от хакера (о чем он, естественно, не подозревает). Аналогичная процедура будет проведена и при посылки сообщения от В к А. В сущности единственным параметром который изменится существенным образом будет время доставки сообщения, так как это время будет включать дешифровку и повторную шифровку сообщения. Но при использовании быстродействующей ЭВМ и при работе с традиционной электронной почтой это может оказаться незаметным. Понятно, что между А и В появится дополнительный шаг (hop). Но и это может быть легко замаскировано под прокси сервер или Firewall.

Решить эту проблему можно путем пересылки открытого ключа своему партнеру по какому-то альтернативному каналу или сверки его по телефону.

Полезную информацию по системам шифрования можно получить на следующих серверах:

www.cs.hut.fi/crypto/
www.subject.com/crypto/crypto.html
www.rsa.com/
www.netscape.com/newsref/ref/rsa.html
www.microsoft.com/workshop/prog/security/pkcb/crypt.htm
www.semper.org/sirene/people/gerrit/secprod.html
www.fri.com/~rcv/deschall.htm
www.cl.cam.ac.uk/brute/

Previous: 6.3.1 Список видов атак, зарегистрированных Network ICE    UP: 6 Сетевая безопасность
Down: 7 Программирование для сетей (новые идеи, принципы и возможности)    Next: 6.4.1 Алгоритм DES