Криптография.

Немного истории: Криптография (тайнопись) – это наука о методах преобразования информации с целью её защиты от несанкционированного доступа. Её название происходит от греческих слов «криптос» - секрет и «графа» - писать. Сам же метод называется шифром от арабского «сафар» - нумеровать.

С древнейших времён криптографией пользовались политические деятеля, дипломаты, военные и разведчики. Так, согласно Светонию, Юлий Цезарь использовал в качестве шифра циклический сдвиг алфавита на 3 позиции. В русском варианте вместо «а» следовало бы писать «г», вместо «б» - «д» и т.д., а вместо «я» - «в».

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

Систему шифрования можно рассматривать как множество функций, отображающих открытый текст (М) в шифротекст (С). Причём само это множество, как правило, не является секретом. Секретным является конкретный выбор функций из этого множества или «ключ» (К). Функция зашифровывания Е_к, определяемая ключом К, отображает открытый текст М в шифротекст С:

.

Для расшифровывания используется обратная функция D_к:

.

Ключ – это сменный элемент шифра. Секретность поддерживается периодическим изменением ключа. Так в шифре Цезаря ключом является величина сдвига 3. Фактически же в качестве ключа можно было бы использовать любое число от 1 до N-1, где N – длина используемого алфавита, храня это число в секрете. Такой шифр, однако, не является надёжным из-за малого числа потенциально возможных ключей, позволяющего произвести расшифровывание полным перебором ключей до появления из криптограммы осмысленного текста.

Развивая идею шифра Цезаря, можно было бы попытаться использовать в качестве ключа произвольную подстановку на N буквах алфавита. Число таких подстановок равно N!, что более чем достаточно для невозможности вскрытия шифра путём полного перебора ключей. Тем не менее, шифр простой подстановки также не является надёжным и легко может быть вскрыт с помощью известной для каждого языка частоты встречаемости различных букв алфавита. Этот способ вскрытия шифров был известен ещё арабам, определившим частоты встречаемости букв по текстам Корана. С примером классического криптоанализа в доступной форме можно ознакомиться по рассказу Эдгара По «Золотой жук».

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

1. противник располагает только шифротекстом;

2. противник располагает открытым текстом и соответствующим шифротекстом;

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

В идеале шифр должен выдерживать все три вида нападения. Шифр же простой подстановки не выдерживает даже слабейшей атаки. Намного более стоек шифр Виженера (1523 – 1596), в котором осуществляются сдвиги алфавита на различное число позиций с помощью ключевого слова. Для этого номера букв открытого текста складываются по модулю N с номерами букв ключевого слова, которое периодически повторяется.

Ряд выдающихся математиков прошлого были выдающимися криптоаналитиками. Так, Франсуа Виет (1540 – 1603) прославился тем, что будучи советником французских королей Генриха III и Генриха IV Наварского, вскрыл шифр испанского короля Филиппа, которым тот пользовался для переписки с лидерами Католической лиги. Российский академик Христиан Гольдбах (1690 – 1764), работая в коллегии иностранных дел в царствование Елизаветы Петровны, успешно вскрыл ряд дипломатических шифров, за что был удостоен чина тайного советника. Знаменитый английский логик Алан Тьюринг (1912 – 1954) во время Второй мировой войны был криптоаналитиком в МИ-6. Классическими в области криптографии являются работы американского математика Клода Шеннона (1916 – 2001).

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

Существует ли абсолютно стойкий шифр, способный выдержать любую атаку криптоаналитиков? Ответ положителен. Таков шифр, использующий в качестве ключа случайную ленту однократного использования. Пусть алфавит естественного языка закодирован двоичными блоками типа телеграфного кода. При зашифровывании двоичная лента сообщения поразрядно складывается с двоичной лентой ключа. При расшифровывании с двоичной лентой ключа складывается шифротекст. Разумеется, все сложения выполняются по модулю 2.

Этот шифр обеспечивает абсолютную секретность, но требует предварительного обмена ключом, что может вызвать затруднение. Современная криптография, ограничиваясь практической секретностью, не позволяющей вскрыть шифр в разумное время, даёт возможность избежать процедуры предварительного распространения ключа. Эти методы, совершившие настоящую революцию в криптографии, связаны с именами американских учёных Диффи и Хеллманом (Diffie, Hellman, 1976). Они используют теория чисел и опираются на современную теорию алгоритмической сложности.

Элементы теории чисел. Приведём без доказательства необходимые для дальнейшего сведения из теории чисел. Натуральное число р называется простым, если оно делится только на 1 и р. Первыми простыми числами являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, … . Простых чисел бесконечно много. Обозначив через число простых, меньших n, имеем

.

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

Всякое целое, делящее одновременно целые а и b, называется их общим делителем. Наибольший общий делитель обозначается (а, b), например (8,12)=4. Эффективным алгоритмом для нахождения (а, b) является алгоритм Евклида, которому для нахождения (а, b) требуется не более шагов. Из алгоритма Евклида вытекает также существование таких целых m и n, что

.

Если (а, b)=1, то числа а и b называются взаимно простыми.

Функция Эйлера определяется для натуральных n как число чисел ряда 0, 1, 2, …, n-1, взаимно простых с n. Имеем . Если р- простое, то . Если же , где р и q простое, то по формуле включения и исключения имеем .

Пусть n – натуральное число. Два целых числа а и b называются сравнимыми по модулю n, если их разность делится на n, что символически обозначается как .

Пусть , где р и q – простые. Тогда из и следует , что сразу вытекает из единственности разложения на простые множители.

Отношение сравнения является отношением эквивалентности и разбивает множество целых чисел на n классов эквивалентности, которые называются классами вычетов по модулю n и обозначаются в зависимости от остатка при делении на n. Отношение сравнения по модулю n согласовано с операциями сложения и умножения в кольце целых чисел (является отношением конгруэнтности) в том смысле, что класс эквивалентности, в который попадает результат любой из операций, определяется классами, из которых берутся аргументы операции. Это позволяет превратить в кольцо с естественными операциями сложения и умножения, выполняемыми по модулю n. Если p – простое, то кольцо является полем. В качестве примера приведём таблицы сложения и умножения в поле :

Ненулевые элементы поля образуют группу по умножению, которая называется мультипликативной группой поля. Эта группа является циклической, т.е. существует элемент а, называемый примитивным корнем по модулю р, степени которого порождают всю мультипликативную группу. Это имеет место в том и только в том случае, если р-1 – наименьшее натуральное число, для которого а^р-1=1. Число примитивных корней по модулю р равно .

В качестве примера рассмотрим поле . Элемент 3 является примитивным корнем по модулю 7, так как 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1. Другим примитивным корнем является 5. Больше примитивных корней нет, т.к. .