Проблема защиты информации и современные информационные технологии.

2. Криптология – наука, состоящая из двух ветвей: криптография + криптоанализ.

Криптографию можно определить как науку о способах шифрования информации,

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

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

1) обеспечение конфиденциальности информации;

2) обеспечение целостности и достоверности информации;

3) обеспечение неотслеживаемости действий участников информационного обмена.

Криптоанализ – область деятельности противоположная деятельности криптогра-

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

3. Составными частями криптографической деятельности являются:

1) разработка и анализ одноключевых (симметричных) криптосистем;

2) разработка и анализ двухключевых(асимметричных) криптосистем;

3) разработка и анализ криптографических протоколов;

4) управление ключевой информацией.

4. Введем в обращение словарь необходимых для дальнейшего изложения терминов.

Алфавит – конечный упорядоченный набор символов произвольной природы, предназначенный для записи текстовой информации.

Открытый текст – упорядоченный набор символов алфавита, предназначенный для криптографического преобразования.

Закрытый текст (шифртекст, криптотекст) – результат работы криптографии-ческого алгоритма, примененного к некоторому открытому тексту.

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

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

Шифрование (зашифрование) – преобразование открытого текста в закрытый с помощью определенных правил, содержащихся в шифре.

Расшифрование – преобразование закрытого текста в открытый, доступный для ознакомления с его содержимым (термин «дешифрование» относят к действиям противника).

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

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

Криптоаналитическая атака – попытка вскрытия шифра или ознакомления с содержимым зашифрованного сообщения, как правило, незаконным пользователем (противником). Возможны криптоатаки исследовательского характера.

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

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

А канал связи Б

шифрующее устройство П устройство расшифровки

Алисы Е противник Боба D

Открытое сообщение Алисы М поступает в устройство Е, которое преобразует его в закрытый текст С, т.е. С = Е(М). Сообщение С передается по каналу связи, прослуши-ваемым возможно противником и попадает в устройство расшифровки Боба D, кото-рое позволяет из С восстановить М, т.е. М = D(C).

6. Современная криптография исповедует принцип Керкгоффса, состоящий в том,

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

7. В соответствии с принципом Керкгоффса противник может решиться на прямой

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

1) атака с известным шифртекстом –

противник располагает некоторым набором перехваченных шифртекстов;

2) атака с известным открытым текстом –

противник располагает некоторым набором открытых текстов и соответст-

вующим им шифртекстов;

3) простая атака с выбором открытого текста –

противник располагает возможностью для выбранных по своему усмотре-

нию открытых текстов получить соответствующие им шифртексты.;

4) адаптивная атака с выбором открытого текста –

противник в условиях предыдущей атаки располагает возможностью пода-

вать на зашифрование открытые тексты порциями таким образом, что оче-

редная порция выбирается с учетом анализа зашифрования предыдущих

порций;

5) простая атака с выбором шифртекста –

противник имеет возможность подать на расшифрование выбранные по

своему усмотрению шифртексты;

6) адаптивная атака с выбором шифртекста –

противник в условиях предыдущей атаки имеет возможность подавать на

расшифрование криптотексты порциями так, что очередная порция выбира-

ется в зависимости от итогов расшифрования предыдущих порций;

7) атака с выбором текста –

противник располагает возможностями подавать на зашифрование и рас-

шифрование любые открытые и закрытые тексты;

8) атака с выбором ключа –

противник, не зная конкретных используемых ключей, знает некоторые

различия между ними.

8. Методы оценки криптоалгоритмов.

К методам оценки криптоалгоритмов относят следующие:

1) всевозможные попытки вскрытия шифра;

2) оценка сложности алгоритмов дешифрования;

3) оценка статистической безопасности шифра.

К необходим условиям стойкости криптосистемы относят следующие:

1) отсутствие статистической зависимости между входной и выходной после-

довательностями;

2) выходная последовательность должна по своим статистическим свойствам

быть похожа на истинно случайную последовательность;

3) при неизменной входной последовательности незначительное изменение

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

вательности;

4) при неизменном ключе незначительное изменение входной последователь-

ности должно приводить к существенному изменению выходной последо-

вательности;

5) отсутствие зависимости между ключами, последовательно используемыми

в процессе шифрования.

9. Стойкость шифра.

К. Шеннон ввел понятие абсолютно стойкого шифра и строго доказал их сущест-

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

вскрыть. Основной смысл рассуждений К. Шеннона сводится к тому, что если опы-

том считать перехват противником шифрованного сообщения, то апостериорные

вероятности открытых текстов не должны в случае такого совершенного шифра

соответственно отличаться от их априорных вероятностей. Это означает, что про-

тивник в результате перехвата не получает никакой информации о сообщении, ко-

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

совершенного шифра являются следующие:

1) ключ выбирается случайно и равновероятно из ключевого пространства;

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

3) ключ используется для шифрования лишь одного сообщения.

Нарушение любого из этих условий лишает шифр его статуса абсолютно стойкого

шифра.

В отличие от абсолютно стойких шифров все прочие являются стойкими в вычис-

лительном смысле, т.е. могут быть вскрыты при выполнении определенного (как

правило, очень большого) объема вычислений. Поэтому необходимые значения

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

противник был не в состоянии такой объем вычислений выполнить за приемлемое

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

криптоалгоритм, является положение, при котором противнику не остается ничего

лучшего, как прибегать к прямой атаке на алгоритм.

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

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

1) защищающейся стороне требуется оценить стоимость защиты, требующейся в условиях присутствия конкретного противника, времени жизни секретной информа-ции и ее относительной ценности;

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

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

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

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

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

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

Одними из наиболее востребованных протоколов является протокол цифровой подпи-си (ЦП). Но существует целый ряд и других прикладных протоколов. Например, про-

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

Раздел второй

1. Исторические шифры.

1) Шифр Цезаря и шифр Августа.

Текст на латинском языке изменялся за счет замены каждой буквы на третью от нее в алфавите (шифр Цезаря) или на следующую в алфавите (шифр Августа). Замена была циклической, т.е. последние буквы алфавита заменялись первыми. Это пример шифров простой замены, при которой алфавит открытых текста инъективно отображается в алфавит закрытых текстов. Ключом к шифру является величина «сдвига». Ввиду незначительной величины ключевого пространства такой шифр легко вскрывается прямой атакой. Приведем пример. Открытый текст «CAESAR» по указанному правилу Цезаря преобразуется в шифртекст «FDHVDU».

2) Шифр Сцитала (Scitale).

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

3) Квадрат Полибия (древняя Греция)

В квадрат , строки и столбцы которого пронумерованы от 1 до 5, вписывались буквы латинского или греческого алфавитов по одной в каждую клетку. Латинские буквы i и j записывались в одну клетку. Шифрование производилось заменой каждой буквы открытого текста парой чисел – координат этой буквы в указанном квадрате. Это тоже шифр простой замены, но алфавит открытых текстов отличается от алфавита закрытых. Ключом является порядок размещения букв в квадрате. Ключевое пространство весьма обширно и оценивается величиной 25! (Сравним с числом 25 в шифрах Цезаря-Августа). Приведем пример. Зададим ключ в виде:

Тогда открытый текст «REMEMBER» преобразуется в шифртекст «4215321532121542».

4) Шифр четырех квадратов.

Латинский алфавит, из которого изъята буква j, записывается в квадрат в произвольном порядке. Составляются четыре таких квадрата, вообще говоря, различных. Квадраты записываются в матрицу так, чтобы строки и столбцы их были выровнены и составляли единое целое. Открытый текст разбивается на биграммы, т.е. пары букв. Каждая биграмма открытого текста заменяется иной биграммой по следующему правилу. Первая буква заменяемой биграммы ищется в левом верхнем квадрате, а вторая – в правом нижнем. Отмеченные буквы задают в матрице алфавитов две противоположные вершины прямоугольника. Замещающие буквы находят в вершинах этого прямоугольника соответственно в правом верхнем и левом нижнем квадрате. Этот шифр является биграммным шифром замены. Ключом служат указанные квадраты алфавитов. Объем ключевого пространства оценивается величиной . Рассмотрим пример со следующим ключом:

Расшифруйте закрытый текст «MOPWTIOMFXNS».

5) Шифр Кардано.

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

Для k = 2 зашифруем фразу: «ПО ПРОЧТЕНИИ СЖЕЧЬ». В соответствии с алгоритмом шифрования лишаем текст пробелов и вписываем буквы в имеющиеся прорези, изображенные жирными линиями. Получим до первого поворота

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

Считывая текст построчно, разобьем его на блоки: «ЖОНПЧЕОИ ПИТЧСРЬЕ».

6) Шифр ADFGVX.

Немецкий военный шифр времен первой мировой войны, представляющий собой композицию двух шифров: билитеральной замены и матричного шифра обхо-да. Тридцать шесть символов открытого текста (26 латинских букв и 10 цифр) запи-сываются в матрицу , строки и столбцы которой, как в квадрате Полибия, про-нумерованы буквами, вынесенными в заголовок. Открытый текст на латинице, который лишается пробелов и знаков препинания, но может содержать цифры, преобразуется билитеральной заменой, т.е. каждый символ текста заменяется парой буквенных координат. Затем полученный текст подвергается повторному шифрованию, при котором он выписывается под заранее задуманным словом-лозунгом буква под буквой так, что в результате образуется матрица текста, число столбцов которой совпадает с числом букв лозунга. Столбцы матрицы затем переставляются в порядке следования букв лозунга при их размещении в стандартном алфавите латиницы. После этого текст из матрицы считывается построчно сверху вниз и разбивается на m-граммы. Композиция двух шифров в данном случае усложняет криптоанализ закрытых текстов и увеличивает ключевое пространство. Ключ состоит из исходного шифровального квадрата и слова-лозунга.

Рассмотрим пример. Пусть таблица билитеральной замены имеет вид:

Зашифруем следующую фразу «DON’T PUT IT OFF TILL TOMORROW». Тогда промежуточный шифртекст выглядит так:

«FXADFAXGVAGXXGGFXGADAVAVXGGFFFFFXGADDAADVXVXADFD».

Пусть слово-лозунг есть «GARDEN». Теперь применим к полученному тексту матричный шифр обхода:

4 1 6 2 3 5

G A R D E N

F X A D F A

X G V A G X

X G G F X G

A D A V A V

X G G F F F

F F X G A D

D A A D V X

V X A D F D

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

«XGGDG FAXDA FVFGD DFGXA FAVFF XXAXF DVAXG VFDXD AVGAG XAA».

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

2. Частотный метод.

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

Вернемся к историческим шифрам.

7) Шифр Б. де Виженера.

Полиалфавитный шифр, т.е. шифр замены, при котором замещающий символ зависит от места в открытом тексте, на котором стоит заменяемый символ. Шифрующая таблица Виженера представляет собой в случае латиницы квадрат , который заполнен буквами алфавита так, что каждая строка сдвинута на одну позицию вперед по отношению к предыдущей. При этом последние буквы приписываются спереди в соответствующем порядке. Таким образом, формально используются 26 алфавитов. Ключом служит некоторое слово на латинице, которое приписывается некоторое количество раз под открытым текстом, который предварительно лишен пробелов и знаков препинания и представляет собой единую строку. Строка закрытого текста получается по следующему правилу: для замены буквы открытого текста ее ищут в верхней строке таблицы Виженера, а стоящую под ней букву ключа – в левом столбце таблицы; замещающей буквой является та, что стоит на пересечении строки и столбца, в которых стоят заменяемая буква и соответствующая буква ключа. Текст, полученный таким образом, далее может быть разбит на m-граммы. Заметим, что это один из вариантов шифра Виженера. Ясно, что в этом случае одна и та же буква может заменяться разными в зависимости от попадания в пару с какой-либо ключевой буквой. Приведем пример. Имеется открытый текст:

“CHAUCER MET A YOUNG LADY AT COURT NAMED PHILIPPA”

Выберем ключевое слово:

“SHERIDAN”

Получим шифртекст:

CHAUCERMETAYOUNGLADYATCOURT NAMEDPH I LI PPA

SHE RI DANSHE RI DANS HER I DANSHE R IDANSHERI DAN

-------------------------------------------------------------------------------------

UOELKHRZWAEPWXNTDHHP IWCBMYXEI P EQHOMCQSPN

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

СELUP

HTARH

AADTI

UYYNL

COAAI

EUTMP

RNCEP

MGODA

Каждая из этих последовательностей преобразуется данным ключом по правилу сдвига по mod 26 на соответственно 18, 7, 4, 17, 8, 3, 0, 13 позиций.Поэтому, разбивая шифртекст на такие подпоследовательности, можнодля достаточно длинного текста при помощи обычного частотного анализа найти величины этих сдвигов. Остается проблема определения длины ключа. Для этого пытаются найти в шифртексте одинаковые биграммы и триграммы(т.е. буквосочетания из двух и трех букв). Предполагая, что они порождены одинаковыми биграммами и триграммами открытого текста, делают вывод, что величина расстояния между двумя одинаковыми k-граммами кратна длине ключа. Это позволяет сократить количество вариантов перебора.

8) Шифр Г. Вернама (одноразовый блокнот)

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

9) Аффинные шифры.

Общая идея таких шифров состоит в том, что рабочим алфавитом открытых и закрытых текстов является кольцо Z ,где n – число символов алфавита естественного языка (речь идет о европейских языках). Таким образом, все вычисления производятся по модулю n. Если k – порядок шифра, то при генерировании ключей выбирают обратимую матрицу над кольцом Z и столбец над тем же кольцом размера . Пусть это будет матрица А и столбец S.

Открытый текст разбивается на k-граммы и оцифровывается (т.е. описывается через символы кольца Z ). Обозначив k-грамму открытого текста через Х, а соответствующий шифртекст через Y, процедуру шифрования можно описать так:

.

Результатом шифрования является набор образов вида Y.

Ключ расшифрования представляет из себя тоже пару: , , где , а . Таким образом,

.

Открытый текст представляет из себя набор прообразов вида X.

В случае, когда S = 0, говорят о линейном шифре, а если А = 0, – о шифре сдвига.

Ключевое пространство для линейного шифра k-го порядка совпадает с множеством обратимых матриц k-го порядка над Z .Это количество оценивается значением обобщенной функции Эйлера:

,

где .

Этот вид шифра оказывается нестойким против атаки с выбором открытого текста. Действительно, достаточно получить шифртексты для k (где k – порядок шифра) единичных столбцов в линейном случае, т.е. для

, ,

где 1 расположена на i-м месте, и дополнительно еще один шифртекст для

в случае аффинного шифра. Знание таких шифртекстов позволяет легко получить ключ зашифрования и, значит, ключ расшифрования.

При атаке с шифртекстом для k = 1 и k = 2 применим частотный метод (простой или с учетом частот биграмм). В случае атаки с известным открытым текстом можно существенно уменьшить количество вариантов перебора. Когда k = 2, аффинный шифр поддается частотному анализу как и любой биграммный шифр. Приведем пример. Пусть задан открытый текст:

«WALTER SCOTT IS THE CREATOR OF THE ENGLISH HISTORICAL NOVEL»

Применим аффинный шифр второго порядка, для чего зададим матрицу второго по-рядка А и вектор сдвига В:

А = , В = .

Далее следует разбить текст на биграммы ( если число символов оказывается нечет-ным, добавляем букву «J») и перевести его в цифровую запись, заменяя буквы и пробел номерами от 0 до 26. Получим представление открытого текста в виде:

«2200 1119 0417 2618 0214 1919 2608 1826 1907 0426 0217 0400 1914 1726 1405 2619

0704 2604 1306 1108 1807 2607 0818 1914 1708 0200 1126 1314 2104 1109».

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

умножаем полученное на матрицу А слева и прибавляем к результату столбец В. В итоге получаем цифровую запись шифртекста (напомним, что все вычисления производятся по mod 27):

«1409 2416 1215 1610 2319 1018 2307 1905 1309 0315 0201 0518 0003 1425 1122 1813

0124 1522 0818 0210 0802 2104 0719 0003 0525 2204 1110 2415 1714 0413».

Остается записать криптограмму в исходном алфавите:

«OJYQMPQKXTKSXHTFNJDPCBFSADOZLWSNBYPWISCKICVEHTADFZWELKYPROEN».

В случае атаки с известным открытым текстом предположим, что шифрующий алгоритм преобразует столбцы Х = (3 , 11) , Х = (8, 23) , Х = (9,1) соответст-венно в Y = (22, 17) , Y = (17, 7) , Y = (20, 12) . Вычитая из равенства Y = АХ + B (для i = 1,2) равенство Y = AX + B, получаем систему

А = ,

А = .

Иначе, получается матричное равенство

А = .

Так как матрица А считается неизвестной, то это равенство можно рассматривать, как матричное уравнение относительно А. Если матрица в правой части обратима, то уравнение имеет единственное решение, если же необратима, то записывая А в виде

А = ,

можно получить линейные соотношения, доставляемые указанным уравнением, которые существенно сокращают возможный перебор вариантов (придется решать систему четырех линейных уравнений с четырьмя неизвестными над кольцом Z ). Напомним, что необходимым и достаточным условием обратимости матрицы D над кольцом Z является обратимость det D по mod n. Легко видеть, что в примере мат-рица справа имеет определитель, равный 13 (mod 27), 13 = 25 ( mod 27). Потому, используя обычный алгоритм нахождения обратной матрицы, получим, что

= .

Теперь можно найти и матрицу А:

А = = (mod 27).

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

A = , С = .

Оценивая величину для отметим, что прямая атака оказывается бесперспективной.

Раздел третий

1. Первичная классификация шифров.

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

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