Простая перестановка без ключа - один из самых простых методов шифрования. Буквы перемешиваются по каким-либо правилам, но эти правила могут быть разными - и простыми и сложными.
Допустим, у нас есть фраза: «МОЖНО, НО НЕЛЬЗЯ» . И мы хотим её зашифровать. Самый простой способ - это записать всю фразу задом наперёд: «ЯЗЬЛЕН ОН, ОНЖОМ» . Можно порядок слов в предложении оставить исходным, но каждое слово записать задом наперёд: «ОНЖОМ, ОН ЯЗЬЛЕН» . А можно менять местами каждые две буквы: «ОМНЖ,ООНЕНЬЛЯЗ» . Это называется «транспозиция» или простая перестановка в чистом виде.
В этом шифре используется таблица. Сообщение записывается в таблицу по строкам, а для образования шифрованного текста считывается по столбцам. Ну или наоборот - записывается на столбцам, а считывается по строкам. Мы как бы переворачиваем таблицу относительно её диагонали, проходящей через верхний левый и нижний правый углы. Математики называют такой способ переворота таблицы транспонированием.
Для шифрования нужно нарисовать подходящего размера таблицу, вписать туда построчно шифруемый текст, а затем выписать его по столбцам в одну строку. Для расшифровки нужно лишь будет сообщить ключ шифра в виде размера таблицы. На рисунке ниже из ABCDEFGHIJKL получается ADGJBEHKCFIL . Согласитесь, понять без картинки, что это был алфавит, уже практически невозможно.
Итак, например, нам нужно зашифровать текст «Я памятник себе воздвиг нерукотворный, к нему не зарастёт народная тропа» . В нём 72 символа. 72 - удобное число, оно делится без остатка на 2,4,6,8,12,18,24,36, поэтому можно использовать таблицы 2х36, 3х24, 4х18, 6х12, 8х9, 9х8, 12х6, 18х4, 24х3, 36х2:). Определяемся с ключом (размером таблицы), вписываем текст по строкам, а затем переписываем его по столбцам.
На рисунке выше показаны варианты с таблицами 9×8, 8×9, 4×18 и 18×4. Для третьего варианта (таблица 4×18) получится вот такой текст:
«Ямиеввнкой у атрар якбоиеор,н зс ояопт езгртн енатнд панс д увыкмерёанта (4:18) »
В данном случае я взял текст «как есть», то есть с пропусками между словами и со знаками препинания. Но если текст осмысленный, то знаки препинания и пропуски между словами можно и не использовать.
Упрощённый вариант транспонирования (с двухстрочной таблицей) - «штакетник». Напоминает «по конструкции» забор-шахматку.
Это очень простой способ шифровки, часто применяемый школьниками. Фраза записывается в две строки: в верхней пишутся нечётные буквы, в нижней - чётные. Затем нужно выписать подряд сначала верхнюю строку, затем нижнюю. Такое шифрование легко проделать и в уме, не выписывая сначала две строки.
«Я памятник себе воздвиг нерукотворный» превращается в «ЯАЯНКЕЕОДИНРКТОНЙ ПМТИСБВЗВГЕУОВРЫ».
Известно, что в V веке до нашей эры правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью «скиталы», первого простейшего криптографического устройства, реализующего метод простой перестановки.
Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который и назывался «скитала», наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично. Для восстановления текста требовалась скитала такого же диаметра.
По сути скитала - это наша обычная плоская таблица, обёрнутая вокруг цилиндра.
Считается, что автором способа взлома шифра скиталы является Аристотель, который наматывал ленту на конусообразную палку до тех пор, пока не появлялись читаемые куски текста. Изначально древний аппарат использовался в качестве сохранения секретных рецептов. Сейчас вместо узкой полоски пергамента можно использовать серпантин, а роль скиталы выполнит карандаш.
Похожий результат можно получить, если буквы сообщения писать через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Ниже пример готовой головоломки, составленной по таким правилам. «Три дробь четыре» - это подсказка, что зашифровано три слова, читать надо каждую четвёртую букву (4-8-12-16-..), по достижению конца переходить снова к началу со сдвигом на 1 букву влево (3-7-11-15-..) и т.д. На рисунке ниже зашифровано «Идите назначенным маршрутом».
Более практический метод шифрования, называемый одиночной перестановкой по ключу, очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы не сдвигаются, а переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Кодируемая фраза записывается в подходящую таблицу построчно. Затем над таблицей вставляется пустая строка и в неё вписывается ключевое слово/фраза/последовательность чисел. Затем это ключевое слово/фраза/последовательность сортируется по алфавиту/значению, вместе с ней сортируются столбцы, тем самым перемешивая всю таблицу. Затем зашифрованная фраза выписывается построчно из этой перемешанной таблицы.
Например, можно сделать головоломку на основе судоку. Разгадывающему даётся текст «-УРОМКУЛО ЬУЁЗЕБЯДЛ НЗЯАТЛЫЙА ЦЬБАДНЕПУ ЕММДНИТОЁ ИЧТЮКЬНОО УНЁЙВЫЧЁС ХИЕПОТОДЦ ПРМГОУИК-» и предлагается решить судоку, в которой одна из строк помечена.
Решать эту головоломку придётся так: сначала нужно записать текст в таблицу 9×9, затем разгадать судоку, нарисовать пустую таблицу 9×9, надписать над ней ключевую строку из помеченной строки, и затем в таблицу под номерами вписать столбцы согласно их порядковым номерам в исходной таблице.
Для детей можно использовать этот же метод, но попроще, даже без цифр, а сразу нарисовав порядок перестановки в виде путей.
Для дополнительной скрытности можно повторно шифровать сообщение, которое уже было зашифровано. Этот способ известен под названием «двойная перестановка». Для этого размер второй таблицы подбирают так, чтобы длины её строк и столбцов были не такие, как в первой таблице. Лучше всего, если они будут взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы, а во второй строки.
Обычное транспонирование таблицы (заполняем по строкам, читаем по столбцам) можно усложнить и считывать не по столбцам, а змейкой, зигзагом, по спирали или каким-то другим способом, т.е. задавать маршрут обхода таблицы. Такие способы заполнения таблицы если и не усиливают стойкость шифра, то делают процесс шифрования гораздо более занимательным. Правда, процесс расшифровки при этом усложняется, особенно, если маршрут неизвестен, и его ещё надо узнать.
На рисунке сверху последовательность символов «АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.,?» вписана построчно в таблицу 6×6, а затем считана по маршруту, указанному линиями. Получаются следующие шифровки:
АЁЛСЧЭБЖМТШЮВЗНУЩЯГИОФЪ.ДЙПХЫ,ЕКРЦЬ?
АЁЛСЧЭЮЯ.,?ЬЦРКЕДГВБЖМТШЩЪЫХПЙИЗНУФО
АБЁЛЖВГЗМСЧТНИДЕЙОУШЭЮЩФПКРХЪЯ.ЫЦЬ,?
АЁЛСЧЭЮШТМЖБВЗНУЩЯ.ЪФОИГДЙПХЫ,?ЬЦРКЕ
НЗВБАЁЖМЛСТШЧЭЮЯЩУФЪ.,?ЬЫХЦРПЙКЕДГИО
А здесь нужно обходить таблицу «ходом коня», причём маршрут уже нарисован, так что это совсем для маленьких:)
Но если подать эту головоломку так, как показано ниже, то будет уже совсем не просто, так как вариантов обхода ходом коня может быть много, и нужно будет найти из всех этих вариантов единственный правильный.
Зашифровано «Пушкин. Медный всадник».
Волшебными (или магическими) квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1 до n 2 (где n - размерность квадрата), которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.
В известном ещё в Древнем Китае квадрате Ло-Шу третьего порядка (3×3) константа квадрата 15 повторяется 8 раз:
по трём горизонталям: 2+9+4 = 7+5+3 = 6+1+8 = 15
по трём вертикалям: 2+7+6 = 9+5+1 = 4+3+8 = 15
по двум диагоналям: 2+5+8 = 4+5+6 = 15
Кстати, константу нечетного квадрата легко посчитать, умножив среднее число ряда, из которого составлен квадрат, на порядок квадрата. Для квадрата 3-го порядка (3×3) константа равна 1234 5 6789 *3=15.
Далее, чтобы зашифровать какое-то послание, нужно сначала подобрать или составить подходящий по размеру волшебный квадрат, затем нарисовать пустую таблицу такого же размера, и вписать буквы текста по очереди в таблицу в соответствии с номерами в волшебном квадрате. Затем просто выписываем построчно буквы из таблицы в одну длинную строку. Порядок квадрата должен быть равен округлённому в большую сторону корню из длины шифруемой строки, чтобы строка полностью вошла в квадрат. Если строка короче, то остаток можно заполнить произвольными буквами или цифрами.
На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты и отражения. Счёт волшебным квадратам 4-го порядка уже идёт на сотни, 5-го - на сотни тысяч. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, так как ручной перебор всех вариантов ключа для этого шифра был немыслим.
Есть очень простой метод составления нечётных волшебных квадратов, т.е. размером 3×3, 5×5, 7×7 и т.д. Это метод «террас» или «пирамидок».
Рисуется квадрат нужного размера и к нему пририсовываются ступенчатые «террасы» (обозначены пунктиром). Далее по диагоналям сверху вниз направо квадрат заполняется последовательными числами. После этого «террасы» переносятся внутрь квадрата: правые - налево, левые - направо, верхние - вниз, а нижние - наверх. Получается волшебный квадрат!
На базе этого метода можно составлять разные головоломки. Если использовать метод напрямую, то получится вот такая головоломка:
Чтобы решить эту головоломку, нужно буквы из «террас» перенести в квадрат, тогда в квадрате прочитается полное сообщение. Здесь зашифрована фраза «За мостом засада, пройти нельзя, переходите речку в брод.»
А если использовать метод наоборот, то получится головоломка типа такой.
Чтобы её решить, надо вытащить соответствующие буквы из квадрата в «террасы».
Для квадратов 4×4, 6×6 и т.д. таких простых способов их составления не существует, поэтому проще использовать готовые. Например, квадрат Дюрера.
(см. также )
Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона "Математическая теория связи".
В своей работе "Теория связи в секретных системах" Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания .
В качестве первичного признака, по которому проводится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены . Если буквы открытого текста при шифровании лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки . С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра.
Рис.
6.1.
Всевозможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами . Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки ( рис. 6.1).
Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр "Сцитала". Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна и - взаимнооднозначное отображение множества в себя. Тогда шифр перестановки действует так: отрезок открытого текста преобразуется в отрезок шифрованного текста.
Классическим примером такого шифра является система, использующая карточку с отверстиями - решетку , которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. При зашифровке буквы сообщения вписываются в эти отверстия. При расшифровке сообщение вписывается в диаграмму нужных размеров, затем накладывается решетка, после чего на виду оказываются только буквы открытого текста.
Также возможны и другие варианты шифра перестановки, например, шифры столбцовой и двойной перестановки.
При расшифровывании буквы шифртекста записываются по столбцам в соответствии с последовательностью чисел ключа, после чего исходный текст считывается по строкам. Для удобства запоминания ключа применяют перестановку столбцов таблицы по ключевому слову или фразе, всем символам которых ставятся в соответствие номера, определяемые порядком соответствующих букв в алфавите.
При решении заданий на криптоанализ шифров перестановки необходимо восстановить начальный порядок следования букв текста. Для этого используется анализ совместимости символов, в чем может помочь таблица сочетаемости (см. ).
| Г | С | Слева | Справа | Г | С | |
|---|---|---|---|---|---|---|
| 3 | 97 | л, д, к, т, в, р, н | А | л, н, с, т, р, в, к, м | 12 | 88 |
| 80 | 20 | я, е, у, и, а, о | Б | о, ы, е, а, р, у | 81 | 19 |
| 68 | 32 | я, т, а, е, и, о | В | о, а, и, ы, с, н, л, р | 60 | 40 |
| 78 | 22 | р, у, а, и, е, о | Г | о, а, р, л, и, в | 69 | 31 |
| 72 | 28 | р, я, у, а, и, е, о | Д | е, а, и, о, н, у, р, в | 68 | 32 |
| 19 | 81 | м, и, л, д, т, р, н | Е | н, т, р, с, л, в, м, и | 12 | 88 |
| 83 | 17 | р, е, и, а, у, о | Ж | е, и, д, а, н | 71 | 29 |
| 89 | 11 | о, е, а, и | 3 | а, н, в, о, м, д | 51 | 49 |
| 27 | 73 | р, т, м, и, о, л, н | И | с, н, в, и, е, м, к, з | 25 | 75 |
| 55 | 45 | ь, в, е, о, а, и, с | К | о, а, и, р, у, т, л, е | 73 | 27 |
| 77 | 23 | г, в, ы, и, е, о, а | Л | и, е, о, а, ь, я, ю, у | 75 | 25 |
| 80 | 20 | я, ы, а, и, е, о | М | и, е, о, у, а, н, п, ы | 73 | 27 |
| 55 | 45 | д, ь, н, о, а, и, е | Н | о, а, и, е, ы, н, у | 80 | 20 |
| 11 | 89 | р, п, к, в, т, н | О | в, с, т, р, и, д, н, м | 15 | 85 |
| 65 | 35 | в, с, у, а, и, е, о | П | о, р, е, а, у, и, л | 68 | 32 |
| 55 | 45 | и, к, т, а, п, о, е | Р | а, е, о, и, у, я,ы, н | 80 | 20 |
| 69 | 31 | с, т, в, а, е, и, о | С | т, к, о, я, е, ь, с, н | 32 | 68 |
| 57 | 43 | ч, у, и, а, е, о, с | Т | о, а, е, и, ь, в, р, с | 63 | 37 |
| 15 | 85 | п, т, к, д, н, м, р | У | т, п, с, д, н, ю, ж | 16 | 84 |
| 70 | 30 | н, а, е, о, и | Ф | и, е, о, а, е, о, а | 81 | 19 |
| 90 | 10 | у, е, о, а, ы, и | X | о, и, с, н, в, п, р | 43 | 57 |
| 69 | 31 | е, ю, н, а, и | Ц | и, е, а, ы | 93 | 7 |
| 82 | 18 | е, а, у, и, о | Ч | е, и, т, н | 66 | 34 |
| 67 | 33 | ь, у, ы, е, о, а, и, в | Ш | е, и, н, а, о, л | 68 | 32 |
| 84 | 16 | е, б, а, я, ю | Щ | е, и, а | 97 | 3 |
| 0 | 100 | м, р, т, с, б, в, н | Ы | Л, х, е, м, и, в, с, н | 56 | 44 |
| 0 | 100 | н, с, т, л | Ь | н, к, в, п, с, е, о, и | 24 | 76 |
| 14 | 86 | с, ы, м, л, д, т, р, н | Э | н, т, р, с, к | 0 | 100 |
| 58 | 42 | ь, о, а, и, л, у | Ю | д, т, щ, ц, н, п | 11 | 89 |
| 43 | 57 | о, н, р, л, а, и, с | Я | в, с, т, п, д, к, м, л | 16 | 84 |
При анализе сочетаемости букв друг с другом следует иметь в виду зависимость появления букв в открытом тексте от значительного числа предшествующих букв. Для анализа этих закономерностей используют понятие условной вероятности.
Систематически вопрос о зависимости букв алфавита в открытом тексте от предыдущих букв исследовался известным русским математиком А.А. Марковым (1856-1922). Он доказал, что появления букв в открытом тексте нельзя считать независимыми друг от друга. В связи с этим А.А. Марковым отмечена еще одна устойчивая закономерность открытых текстов, связанная с чередованием гласных и согласных букв. Им были подсчитаны частоты встречаемости биграмм вида гласная-гласная (г, г ), гласная-согласная (г, с ), согласная-гласная (с, г ), согласная-согласная (с, с ) в русском тексте длиной в знаков. Результаты подсчета отражены в следующей таблице:
| Г | С | Всего | |
| Г | 6588 | 38310 | 44898 |
| С | 38296 | 16806 | 55102 |
Пример 6.2 Открытый текст, сохраняя пробелы между словами, записали в таблицу. Начало было в первой строке, текст записывали слева направо, переходя со строки на следующую, шифрование заключалось в перестановке столбцов. Найдите открытый текст.
Шифрованный текст:
| Д | В | Ы | Т | ||
| Г | О | Е | Р | О | |
| У | Ь | Д | У | Б | |
| М | М | Я | Ы | Р | П |
Решение. Присвоим столбцам номера в порядке их следования. Наша задача - найти такой порядок столбцов, при котором текст будет осмысленным.
Составим таблицу:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | Х | |||||
| 2 | Х | |||||
| 3 | Х | |||||
| 4 | Х | |||||
| 5 | Х | |||||
| 6 | Х |
Клетка (, ) в этой таблице означает, что столбец с номером следует за столбцом с номером . Знаком "Х" отметим невозможные случаи.
Сочетания столбцов 1, 2 и 5, 2 невозможны, так как гласная не может находиться перед мягким знаком. Невозможны и следования столбцов 2, 1 и 2, 5. Теперь из третьей строки следует, что 1, 5 и 5, 1 невозможны, так как УУ - нехарактерная для русского языка биграмма. Далее, два пробела подряд не могут быть в тексте, значит, ставим "Х" в клетках 3, 4 и 4, 3. Снова обратимся к третьей строке. Если бы столбец 2 следовал за столбцом 4, то слово начиналось бы с мягкого знака. Ставим "Х" в клетке 4, 2. Из первой строки: невозможна комбинация 4, 5, невозможна и 3, 5. Итог наших рассуждений представлен в таблице:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | Х | Х | Х | |||
| 2 | Х | Х | Х | |||
| 3 | Х | Х | Х | |||
| 4 | Х | Х | Х | Х | ||
| 5 | Х | Х | Х | |||
| 6 | Х |
Итак, после столбца 6 обязательно следует столбец 5. Но тогда поставим "Х" в клетке 6, 2 и получим: столбец 2 следует за столбцом 3. Далее, мы вычеркнули 5, 1 и 2, 1, следовательно, надо проверить варианты: ...6532... и...65432... . Но (4, 3) вычеркнуто ранее. Итак, остались варианты расположения столбцов:
Запишем 6, 5, 3, 2 столбцы подряд:
| 6 | 5 | 3 | 2 |
| т | ы | - | в |
| о | р | о | г |
| б | у | д | ь |
| п | р | я | м |
Попытка поставить столбец 1 перед столбцом 6 приведет к биграмме МП в последней строке и сочетанию ДТЫ в первой. Остались варианты: 653241, 146532.
Ответ: 653241 - ключ, открытый текст: ты\_в\_дороге\_будь\_упрямым (строка из популярной в 1970-е годы песни).
Приведем еще один пример криптоанализа шифра столбцовой перестановки.
Пример 6.3 Расшифровать: СВПООЗЛУЙЬСТЬ\_ЕДПСОКОКАЙЗО
Решение. Текст содержит 25 символов, что позволяет записать его в квадратную матрицу 5х5. Известно, что шифрование производилось по столбцам, следовательно, расшифровывание следует проводить, меняя порядок столбцов.
Шифры подстановки (замены) основаны на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно-однозначное отображение конечного множества M на себя. Число N элементов множеств называется степенью подстановки. Количество n чисел действительно перемещаемых подстановкой называется длиной цикла подстановки.
Шифры перестановки – это шифр, преобразование из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих.
Слабость шифров замены. Если в открытом сообщении часто встречается какой-то символ, то в шифрованном сообщении с такой же частотой встречается соответствующий символ. При больших объемах текста это приводит к успешному криптоанализу. Таким образом, на одном ключе нельзя шифровать достаточно длинные сообщения.
Сети (как элемент шифрования) – любой блочный шифр является комбинацией первых двух схем. Использование понятия «сети» в блочном шифровании заключается в многократном повторении исходных операций (повторения – циклы или раунды, а сами операции - слоями). Некоторые из слоев могут содержать ключи. Это позволяет:
Сеть Фейсиля (Файсиля) – Feistel – это способ построения цикла шифрования в алгоритмах шифрования итеративных на основе регистра сдвига, с функцией обратной связи, зависящей от раундового ключа (оптимальное число раундов от 8 до 32)
DES – федеральный стандарт шифрования США (1997-2001).
Архитектура – классическая, сбалансированная сеть Фейсиля с начальными и конечными битовыми перестановками общего вида. Размер ключа – 56 бит. На его основе – международный стандарт ISO 8372-87. Алгоритм предназначен для шифрования данных 64-битовыми блоками.
DES представляет собой комбинацию двух основных методов:
К тексту применяется единичная комбинация этих двух методов.
DES включает 16 раундов, то есть одна и та же комбинация методов применяется к открытому тексту 16 раз.
Наложение ключа-раунда производится операцией XOR
Исходный текст=>Начальная перестановка=>Шифрование * 16(<=Ключ) =>Конечная перестановка=>шифротекст
Цель начальной перестановки – равномерно распределить по блокам рядом стоящие биты.
Для зашифрования и расшифрования можно использовать одну и ту же функцию, но ключи используются в обратном порядке.
DES предусматривает 4 типа работы:
Считается, что четырех режимов достаточно, чтобы использовать DES в практически любой области, для которой этот алгоритм подходит
Аппаратная реализация алгоритма на отдельной микросхеме позволяет достичь высокой скорости шифрования при незначительных габаритах устройства.
AES-федеральный стандарт шифрования США, используемый в настоящее время.
AES – улучшенный стандарт шифрования.
Требования:
Алгоритм является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований.
Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байтов размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока.
Алгоритм состоит из определенного количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа).
ГОСТ 28147089 – стандарт РФ на шифрование и имитозащиту данных.
Алгоритм предназначен для аппаратной и программной реализации, удовлетворяет необходимым криптографическим требования и не накладывает ограничений на степень секретности защищаемой информации.
Алгоритм реализует шифрование 64-битовых блоков данных с помощью 256-битового ключа, состоящего из восьми 32-битовых подключей.
На каждом i-м раунде используется K i -й подключ.
Алгоритмы шифрования ГОСТ 28147-89 обладают достоинствами других алгоритмов для симметричных систем и превосходят их своими возможностями.
На каждом i-м раунде алгоритма ГОСТ выполняется следующие операции:
L i =R i -1 , R i =L i -1 (плюсвкружочке)f(R i -1 , K i)
После выполнения этих 32 операций реализация алгоритма шифрования будет завершена.
Достоинством ГОСТ является наличие защиты от навязывания ложных данных (режим имитовставки), а также одинаковый цикл шифрования во всех 4 режимах (алгоритмах) ГОСТ.
Высокая криптостойкость обеспечивается за счет большой длины ключа (256 бит) и 32 раундов преобразования.
Стандарт включает режимы (алгоритмы):
Асимметричные алгоритмы шифрования.
В асимметричных алгоритмах шифрования (или криптографии с открытым ключом) для зашифрованной информации используют один ключ (открытый), а для расшифровывания – другой (секретный)
Эти ключи различны и не могут быть получены один из другого.
Схема обмена информацией:
Использование асимметричного метода шифрования
Применение таких шифров стало возможным благодаря К. Шеннону, предложившему строить шифр таким способом, чтобы его раскрытие было эквивалентно решению математической задачи, требующей выполнения объемов вычислений, превосходящих возможности современных ЭВМ (например, операции с большими простыми числами и их произведениями; нахождение значения произведения P=x*y)
Криптосистема шифрования данных RSA.
В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий её изобретателей (Rivest, Shamir, Adleman)
Чтобы использовать алгоритмы RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги:
Красным выделено создание ключа.
Асимметрические криптосистемы на базе эллиптических кривых.
На базе эллиптических кривых Е можно реализовать не только криптоалгоритмы асимметричного шифрования, но и выработки общего секретного ключа для симметричного шифрования.
Криптосистемы на базе эллиптических кривых позволяют использовать существенно меньшие размеры ключей по сравнению с другими криптоалгоритмами при сохранении одинакового уровня криптостойкости.
Для перечисленных выше реализаций используются эллиптические кривые над полями Галуа GF(p) конечным числом p элементов двух видов:
Пример: Алгоритм асимметричного шифрования на базе эллиптических кривых ECES (Elliptic Curve Encryption Scheme)
Алгоритм Эль-Гамаля.
Система Эль-Гамаля – это криптосистема с открытым ключом, основанная на проблеме вычисления логарифма. Данный алгоритм используется как для шифрования, так и для цифровой подписи.
Множество параметров системы включает простое число p и целое g, степени которого по модулю p порождают большое число элементов Z p
Методы замены.
Шифр замены замещает одни символы другими, но сохраняет порядок их следования в сообщении.
4 типа замены (подстановки):
Пример. Замена – открытый текст, Ключ – Ключ
Шифры перестановки.
Отличие шифра перестановки – изменяется только порядок следования символов сходного текста, но не изменяют их самих.
Пример. Текст «Грузите апельсины бочками Братья Карамазовы»
Шифротекст «Птр_аезгуионл_бысеьит_крабмчаизрямаакь_а__в____оы»
При шифровании перестановкой символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока этого текста.
Простая перестановка
Выбирается размер блока шифрования в n столбцов и m строк и ключевая последовательность, которая формируется из натурального ряда чисел 1,2,...,n случайной перестановкой.
Шифрование проводится в следующем порядке:
Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.
Зашифрованный текст выписывается колонками в порядке возрастания номеров колонок, задаваемых ключевой последовательностью.
Заполняется новый блок и т.д.
Например, зашифруем текст
ГРУЗИТЕ_АПЕЛЬСИНЫ_БОЧКАХ
блоком размером 8*3 и ключом 5-8-1-3-7-4-6-2.
Таблица простой перестановки будет иметь вид:
|
Г Р У З И Т Е _ А П Е Л Ь С И Н Ы _ Б О Ч К А Х |
Зашифрованное сообщение:
УЕБ_НХЗЛОЕСЛГАЫЕИАИЬЧРП_
Расшифрование выполняется в следующем порядке:
Из зашифрованного текста выделяется блок символов размером n*m.
Этот блок разбивается на n групп по m символов.
Символы записываются в те столбцы таблицы перестановки, номера которых совпадают с номерами групп в блоке. Расшифрованный текст читается по строкам таблицы перестановки.
Выделяется новый блок символов и т.д.
Перестановка, усложненная по таблице
При усложнении перестановки по таблицам для повышения стойкости шифра в таблицу перестановки вводятся неиспользуемые клетки таблицы. Количество и расположение неиспользуемых элементов является дополнительным ключом шифрования.
При шифровании текста в неиспользуемые элементы не заносятся символы текста и в зашифрованный текст из них не записываются никакие символы - они просто пропускаются. При расшифровке символы зашифрованного текста также не заносятся в неиспользуемые элементы.
Для дальнейшего увеличения криптостойкости шифра можно в процессе шифрования менять ключи, размеры таблицы перестановки, количество и расположение неиспользуемых элементов по некоторому алгоритму, причем этот алгоритм становится дополнительным ключом шифра.
Перестановка, усложненная по маршрутам
Высокую стойкость шифрования можно обеспечить усложнением перестановок по маршрутам типа гамильтоновских. При этом для записи символов шифруемого текста используются вершины некоторого гиперкуба, а знаки зашифрованного текста считываются по маршрутам Гамильтона, причем используются несколько различных маршрутов. Для примера рассмотрим шифрование по маршрутам Гамильтона при n=3.
Струкрура трехмерного гиперкуба представлена на рисунке 6.
Рисунок 6. Трехмерный гиперкуб
Номера вершин куба определяют последовательность его заполнения символами шифруемого текста при формировании блока. В общем случае n-мерный гиперкуб имеет n 2 вершин.
Рисунок 7. Маршруты Гамильтона
Последовательность перестановок символов в шифруемом блоке для первой схемы 5-6-2-1-3-4-8-7, а для второй 5-1-3-4-2-6-8-7. Аналогично можно получить последовательность перестановок для других маршрутов: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3-7-8-6 и т.д.
Размерность гиперкуба, количество вид выбираемых маршрутов Гамильтона составляют секретный ключ метода.
Стойкость простой перестановки однозначно определяется размерами используемой матрицы перестановки. Например, при использовании матрицы 16*16 число возможных перестановок достигает 1.4E26. Такое число вариантов невозможно перебрать даже с использованием ЭВМ. Стойкость усложненных перестановок еще выше. Однако следует иметь в виду, что при шифровании перестановкой полностью сохраняются вероятностные характеристики исходного текста, что облегчает криптоанализ.
Шифрование по методу магических квадратов.
Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, строке и диагонали одно и то же число.
При шифровании буквы открытого текста необходимо вписать в магический квадрат в соответствии с нумерацией его клеток. Для получения шифротекста считывают содержимое заполненной таблицы по строкам.
Зашифруем фразу «МАГИЧЕСКАЯ СИЛА» с помощью магического квадрата размером 4х4. Для этого выберем один из 880 вариантов магических квадратов заданного размера (рисунок 8а). Затем вписываем каждую букву сообщения в отдельную ячейку таблицы с номером, соответствующим порядковому номеру буквы в исходной фразе (рисунок 8б). При считывании заполненной таблицы по строкам получаем шифротекст: «_ГАИАЕССЧЯ_КИАЛМ».
Рисунок 8. Пример шифрования с помощью магических квадратов
Шифр перестановки «скитала». В V в. до н.э. правители греческого государства Спарты имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки (рис. 1.6).
Рис. 1.6.
Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску кожи и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали со стержня полоску - буквы на ней оказывались расположенными вразнобой.
Вестник обычно прятал сообщение, используя кожаную полосу как пояс, т.е. кроме шифрования применяли также и стеганографию. Чтобы получить исходное сообщение, полоску кожи надо намотать вокруг скиталы того же диаметра. Ключом этого шифра является диаметр стержн я - с к итал ы. Зная только вид шифра, но не имея ключа, расшифровать сообщение непросто. Шифр «скитала» многократно совершенствовался в последующие времена.
Способ взлома этого шифра предложен Аристотелем. Надо изготовить длинный конус и, начиная с основания, обертывать его лентой с шифрованным сообщением, постепенно сдвигая к вершине. В какой-то момент начнут просматриваться куски сообщения. Диаметр конуса в этом месте соответствует диаметру скиталы.
Шифрующие таблицы. Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования в простейшем варианте сходен с шифром «скитала». Например, текст сообщение записывается в таблицу определенного размера в столбик, а считывается но строкам.
Запишем фразу «Терминатор прибывает седьмого в полночь» в таблицу размером 5x7 (рис. 1.7) но столбцам. Выписав текст из таблицы построчно, получим шифр: «тннвеглеарадонртиеьвомобтмнчирысооь».
Рис. 1.7.
Отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. При расшифровке действия выполняют в обратном порядке (построчная запись, чтение по столбцам).
Этот шифр может быть несколько усложнен: например, столбцы могут быть переставлены в некоторой последовательности, определяемой ключом. Возможна двойная перестановка - столбцов и строк.
Решетка Кардано. Решетка Кардано (поворотная решетка) - это прямоугольная или квадратная карточка с четным числом строк и столбцов 2k X 2т. В ней проделаны отверстия таким образом, что при последовательном отражении или поворачивании и заполнении открытых клеток карточки постепенно будут заполнены все клетки листа.
Карточку сначала отражают относительно вертикальной оси симметрии, затем - относительно горизонтальной оси, и снова - относительно вертикальной (рис. 1.8).
Если решетка Кардано - квадратная, то возможен и другой вариант ее преобразований - поворот на 90° (рис. 1.9).
Рис. 1.8.
Рис. 1.9.
При записи обычным способом (слева направо и сверху вниз) словосочетания «шифрование текста» (без пробелов) в свободные клетки поворотной решетки, изображенной на рис. 1.9, получим текст в виде таблицы (рис. 1.10), или, записав текст в одну строку, - «кшииоесвтафатрен».
Рис. 1.10.
Получатель должен знать трафарет и наложить его в той же последовательности, что и при шифровании. Ключом является выбранный тип перемещения решетки (отражение или поворот) и трафарет - расположение отверстий, которые для квадратной решетки размером 2т х 2к могут быть выбраны 4""* способами (с учетом начальной ориентации трафарета). В этом случае среди трафаретов, считающихся различными, будут встречаться такие, которые являются зеркальным отражением или поворотами других трафаретов, т.е. трафареты, различающиеся только начальным расположением (ориентацией). Если пренебречь начальным расположением трафарета, то, очевидно, различных трафаретов будет в 4 раза меньше - 4""*"
Например, для решеток размером 4X4 существует 256 возможных вариантов трафарета (с учетом начальной ориентации) или всего 64 различных трафаретов.
Несмотря на то, что число трафаретов для больших решеток достаточно велико (порядка 4 млн (4- 10 е)), оно все же существенно меньше, чем случайных перестановок элементов таблицы, число которых равно (2т? 2k).
Например, для таблицы размером 4x4 число случайных перестановок составляет порядка 2 ? 10 13 , а для таблиц размером 8x8 - около 10 89 .
Решетки Кардано, так же как и шифрующие таблицы, являются частными случаями шифра маршрутной перестановки.
