| ||
Чтоб никто не догадался>Владимир (Люден) Ю. Некрасов В этой статье я хотел бы описать принципы и методы шифрования, сопроводив их некоторым количеством примеров. Благодаря обилию книг, публикаций и программ, всем интересующимся этой темой ныне есть чем поживиться. Криптография — тайнопись, специальная система изменения обычного письма,используемая с целью сделать текст понятным лишь для ограниченного числа лиц, знающих эту систему. (БСЭ, том 13, 1973) Первые шагиСвой первый шифр я придумал в двенадцать лет, прочтя «Золотого жука» Э. А. По. Фабулу рассказа составляет расшифровка таинственной записки, оставленной некогда грозным пиратом капитаном Киддом и наводящей, при правильном истолковании, на клад несметных сокровищ, награбленных в далекие времена в южных морях. Чтобы вы могли ощутить сам дух криптографии, я, пожалуй, приведу из рассказа небольшой фрагмент. «Легран разогрел пергамент и дал его мне. Между черепом и козленком, грубо начертанным чем-то красным, стояли такие знаки: 53##+305)) 6*; 4826) 4#.) 4#); 806*; 48+8 <...> ...Прямо скажу, если текст зашифрован без грубых ошибок и документ в приличной сохранности, я больше ни в чем не нуждаюсь; последующие трудности для меня просто не существуют». Здесь мы можем наблюдать воочию несколько уровней секретности документа: текст написан невидимыми в обычных условиях чернилами, вместо герба и подписи применяются своеобразные геральдические знаки («череп» и «козленок» — здесь игра английских слов Kidd и Kid), которые одновременно намекают на язык шифрования, ну и, наконец, сама шифровка. Желающие могут обратиться к самому рассказу — получите истинное удовольствие. Вот на основании шифра из этой романтической истории (кстати, сундук с сокровищами был-таки откопан!) я и составил свой собственный принцип шифрования. Конечно, алгоритм вышел у меня слабенький и хиленький, но нашим тогдашним с другом нуждам и его вполне хватало. А выглядело это так. Каждая буква русского алфавита заменялась на определенный символ или цифру, а цифры оригинала и знаки препинания в нем заключались в двойные кавычки. В апреле 88 года (мне тринадцать лет) мой друг передает мне шифровку: ]u(86) «!» )S .#6 5’.]5:[S «?». Что означало: «Привет! Ты уже купался?» (Некоторые символы в шифровке, которым невозможно найти соответствие на клавиатуре компьютера, заменены буквой S.) Что интересно, профессиональный шифровальщик, известный в Сети под ником ***, расколол мой шифр за... семь минут. И признался, что и это много. Лишь много позже я познакомился с рассказом Артура Конан Дойля «Пляшущие человечки». Но акценты восприятия уже сместились, и прекрасный шифр, придуманный создателем сыщика с Бейкер-стрит, остался вне поля моего воображения. И тем не менее, я искренне и настоятельно рекомендую всем любознательным и просто любителям кодов и шифров перечесть эту чудесную вещь. Основные представленияДалее я приведу для уважаемых читателей примеры двух наиболее доступных для понимания и распространенных методов шифрования под названиями шифрование с помощью датчика псевдослучайных чисел и метод RSA (это аббревиатура по именам создателей алгоритма — Rivest, Shamir и Adleman). Кроме того, я позволю себе упомянуть о таких китах шифрования, как DES (Data Encryption Standard) — государственном методе шифрования США, и ГОСТ 28147-89 — государственном методе шифрования почившего в бозе СССР. Отмечу, что публикация двух последних выходит за рамки данной статьи, но знать о них небезынтересно, и потому любознательных я отсылаю к соответствующим первоисточникам. Рассмотрим несколько довольно важных понятий, имеющих отношение к криптографии и шифрованию в частности, а затем перейдем к конкретике. Ключ шифрования — это набор секретных параметров для алгоритма шифрования, определяющих его уникальные условия засекречивания (или рассекречивания) информации. Существует понятие открытого и закрытого ключей. В ряде алгоритмов для зашифровывания данных используется один ключ, а для расшифровывания — другой. Первый ключ не является секретным, распространяется среди всех пользователей, работающих с данным алгоритмом шифрования и может быть без ущерба для криптостойкости алгоритма даже опубликован или помещен в Интернете. Кстати, некоторые хорошие алгоритмы позволяют наряду с таким открытым ключом опубликовать и свой принцип, также без ущерба для криптостойкости. Ключ же, используемый для расшифровки информации, секретен в полном смысле этого слова и является тайной каждого конкретного пользователя. Рассекречивание данных с помощью открытого ключа невозможно, и так же невозможно получение закрытого ключа при помощи знания открытого. Примером такого алгоритма шифрования является широко известный RSA, который мы рассмотрим ниже. Время, необходимое для взлома шифра, определяет его криптостойкость. Если время расшифровывания превышает все разумные сроки и к тому же (что еще лучше) неясно, достижим ли желаемый результат в принципе, алгоритм шифрования называют «сильным», иначе «слабым». Нам понадобится еще понятие гаммы для понимания работы алгоритмов шифрования. Гамма — это некая двоичная последовательность, кратная, как правило, восьми — грубо говоря, число — создаваемая псевдослучайно по некоторому алгоритму и предназначенная для шифрования или расшифровывания данных. Как именно — зависит от специфики применяемого метода шифрования. Длина гаммы — величина произвольная и зависит от потребностей программиста. Чем длиннее, тем сложнее взломать шифр — возрастает количество операций перебора для определения ключа. Интересно, что ключ — главная цель всех взломщиков — в некоторых алгоритмах может быть определен именно исходя из известной правильной гаммы, хотя бы одной. В самом деле, гамма шифрования длиной один байт может иметь 2^8=256 возможных значений. Гамма длиною в два байта имеет их уже 2^16=65536. Гамма в 4 байта — 2^32 — более четырех миллиардов. Есть и еще одно условие: гаммы, продуцируемые псевдослучайно, не должны повторяться. Чем дольше, тем лучше. Если промежуток между инициализирующим значением для алгоритма псевдослучайной генерации гамм и первым повторением подряда гамм в числовом ряду велик, то такой алгоритм генерации гамм (не путать с алгоритмом шифрования!) называют длиннопериодическим, имея в виду период как количество спродуцированных — перед первым повторением — псевдослучайных двоичных последовательностей. Если период превышает длину зашифровываемого набора данных, то взломать такой шифр можно лишь прямым перебором (при условии, что не известна ни одна часть зашифрованного текста.) Почему? Потому что невозможно вычислить или установить другим способом ни одно значение гаммы. В противном же случае, если период менее длины зашифровываемого письма, криптостойкость понижается. К сведению: сейчас в алгоритмах шифрования используются более чем 100-битные ключи, потому что ключи меньшего размера для того же алгоритма RSA уже взломаны. Величина ключа шифрования ограничивается лишь скоростью обработки данных программой шифрования, использующей этот ключ. А теперь — к делу. Рассматриваем алгоритм шифрования с помощью датчика (или генератора) псевдослучайных чисел. Сокращенно ДПСЧ (ГПСЧ). Метод этот заключается в наложении гаммы (этот процесс в криптографии называют «гаммирование») на каждое «слово» («слово» определяется длиной гаммы) зашифровываемого текста обратимым образом (простейший пример — логическая операция «исключающее ИЛИ»). То есть каждый символ зашифровываемого текста подвергается операции «исключающее ИЛИ» с генерируемой для него псевдослучайным образом гаммой — в результате мы получаем зашифрованный символ, из которых и составляется секретный текст. Формула шифрования выглядит так: C(i)= M(i) xor G(i) где C(i) — закодированный символ текста, M(i) — символ открытого текста, G(i) — соответствующая гамма. Устойчивость против «взлома» в этом шифре в большей степени определяется не характеристиками собственно гаммы, но самим алгоритмом ДПСЧ. Выберем для практической работы простой, но эффективный и криптостойкий датчик под названием «линейный ДПСЧ». Расшифровываю: линейная комбинация — это выражение вида C1u1+C2u2+C3u3+...+Cnun, где Ci — числа, хотя бы одно из которых отлично от нуля, а ui — те или иные математические объекты, для которых определены операции сложения и умножения на число. В сумму объекты ui входят в первой степени, то есть линейно, поэтому выражение называется линейным. Алгоритм шифрования с помощью ДПСЧ чрезвычайно прост для программирования и его общая формула выглядит так: T(i+1)=(A*T(i)+C) mod M где A и C — константы, T(0) — стартовая гамма, которая, кстати, может быть и ключом, а M выбирается в зависимости от требуемой длины гаммы и равно 2^b, где b — длина (в битах) гаммы и шифруемого слова компьютера соответственно. Для того чтобы данный шифр был криптостойким, важно, чтобы алгоритм, создающий гаммы для него, был длиннопериодическим. Данный метод очень хорош тем, что уже давно было математически строго показано, при каких именно A и C обеспечивается наименьшая повторяемость гамм и их оптимальное статистическое случайное (вероятностное) распределение. Между прочим, подбирая всякий раз новые константы для алгоритма (необязательно этого — любого алгоритма шифрования), необходимо проводить тщательные математические, статистические и криптологические изыскания с целью подтвердить надежность данного варианта. Ибо важное правило криптографии гласит: даже самые грозно и неуязвимо выглядящие шифры и алгоритмы могут быть легко вскрыты из-за ляпсусов и мелких оплошностей секретчика! Помните об этом. Для линейного ДПСЧ в приведенной выше формуле оптимальными значениями A и C признаны: A mod 4 = 1 и C — нечетное. Естественно, что для каждого нового слова текста генерируется новая гамма или несколько гамм, затем они каким-либо образом накладываются друг на друга, объединяются или взаимодействуют, с единой целью — увеличить криптостойкость шифра. Что важно, алгоритм должен быть защищен от возможности проследить связи между двумя последовательно получаемыми гаммами — лучше всего это сделать, используя методику обратной связи между зашифровываемыми частями открытого текста и генерацией новых гамм. Ниже привожу примерный эскиз реализации одной из таких методик. Определяем контрольную сумму (некоторую величину, характеризующую с той или иной стороны данный фрагмент текста) первого сегмента открытого текста S(1). Генерируем гамму с участием найденной контрольной суммы и зашифровываем сегмент открытого текста S(1). Находим контрольную сумму зашифрованного участка текста S(1) и генерируем новую гамму с участием этого числа. Зашифровываем участок открытого текста S(2). И так далее. Алгоритм также должен быть неуязвим с точки зрения криптоанализа: должны исключаться возможности добавления к зашифрованному тексту дополнительных посторонних вставок и сравнение зашифрованного текста до и после такой операции, поскольку незащищенный вышеописанным методом генерации гамм с участием обратной связи шифр элементарно вскрывается. Увы, недостаток газетного пространства не дает мне возможности показать, как именно это возможно реализовать. Ну и на десерт маленький пример реализации алгоритма на ставшем уже доброй традицией языке Паскале. Пример 1. Const Пояснения. N0 — стартовая гамма, некоторая аналогия части ключа. Приведение типа byte(...) необходимо потому, что при перемножении чисел возможно получение значения, большего, чем может уместиться в тип byte, — тогда при выполнении операции деления по модулю результат наследует полученный тип (integer или longint). Для дешифрации письма достаточно применить алгоритм к зашифрованному тексту еще раз. В строке с операцией XOR («исключающее ИЛИ») дважды выполняется приведение к типу: в первый раз символьный тип преобразуется в тип байт, а второй — наоборот, байтовый тип к символьному. Длина гаммы в примере выбрана для простоты реализации минимальная — один байт. Алгоритм RSAПростыми числами называются числа, не имеющие делителей, кроме самих себя и единицы. А вот взаимно простыми числами называются числа, не имеющие общих делителей, кроме 1. Под большими и очень большими :-) числами будем понимать числа с разрядностью не менее 200 бит. Итак. Определим открытый и секретный ключи. 1) Выберем два очень больших числа p и q. 2) Определим n как результат перемножения p и q (n=p*q) 3) Выберем большое случайное число, которое назовем d, причем это число должно быть взаимно простым с результатом умножения (p-1)*(q-1). 4) Отыщем такое число e, для которого верно соотношение (e*d) mod ((p-1)*(q-1)) = 1. 5) Открытым ключом является пара чисел e и n, секретным — пара чисел d и n. Зашифровываем информацию по открытому ключу e, n. Разбиваем зашифровываемый текст на символы, каждый из которых может быть представлен в виде числа M(i)=0,1,..,n-1. Собственно зашифровываем данные (текст, письмо, дневник, файл), рассматриваемые как числовой ряд M(i), используя формулу C(i)= (M(i)^e) mod n. Расшифровывание информации также достаточно просто реализуется. Имея секретный ключ d, n и числовую последовательность C(i), выполняем M(i)= (C(i)^d) mod n. Рассмотрим простейший пример применения алгоритма RSA. Чтобы не утруждать себя громоздкими вычислениями, возьмем очень маленькие исходные числа p и q. Пример 21) p=3, q=7. 2) n=p*q=21. 3) Выбираем d как 5. 4) (e*5) mod 12=1, e=17. 5) Открытый ключ 17, 21, закрытый (секретный) — 5, 21. Пусть нам нужно зашифровать слово «USD». Чтобы не загромождать большими числами текст статьи, присвоим каждой букве просто порядковый номер из ряда натуральных чисел. То есть: USD = 1 2 3. Зашифровываем: C(1)= 1^17 mod 21= 1; C(2)= 2^17 mod 21 =11; C(3)= 3^17 mod 21= 12. Получился код: 1 11 12 Расшифровываем. (1)= 1^5 mod 21= 1; M(2)= 11^5 mod 21= 2; M(3)= 12^5 mod 21= 3. Имеем: 1 2 3 Тождественно слову «USD». Как видим, алгоритм достаточно прозрачен и прост в воплощении — реализующую его программу предлагаю составить читателю самостоятельно (это как бы домашнее задание :-)). Криптостойкость RSA основывается на том предположении , что пока исключительно трудно (если возможно вообще) определить секретный ключ из ключа открытого. Но! Для этого требуется решить задачу о существовании делителей целого числа, и если эта задача будет решена, то алгоритм просто утратит какую бы то ни было криптостойкость в принципе и перестанет быть алгоритмом шифрования. И к существенным недостаткам RSA можно отнести ту особенность, что одинаковые символы открытого текста будут и в зашифрованном тексте также выглядеть одинаково, что с точки зрения криптографии — неправильно. ИтогиПервый из рассмотренных нами методов — шифрование с помощью ГПСЧ — является самым простым и доступным в программной реализации, отличается высокой криптостойкостью и быстротой и позволяет зашифровывать большие объемы информации в течении считанных секунд. Кстати, технически шифрование файлов может быть реализовано и на аппаратной основе. Однако возвращаясь к алгоритму шифрования с использованием ГПСЧ замечу, что именно простота и кажущаяся неуязвимость могут сыграть злую шутку с программистом, решившим попрактиковаться в криптографии. Каждый алгоритм (не только ГПСЧ) должен подвергаться всестороннему анализу, иначе... сами понимаете. Метод RSA весьма популярен сейчас, он обладает многими достоинствами, и главным из них является открытость ключа шифрования. Но в силу высказанных выше соображений этот метод сейчас вызывает недоверие, и чует мое сердце :-), что скоро он будет «расколот» до конца. Математика, кибернетика, криптоанализ, информатика — все эти науки развиваются очень скорыми темпами, особенно сегодня. Засим разрешите откланяться... Читайте «МК» — пока-пока! Источник: http://www.mycomp.com.ua/
| ||
Copyright © "Internet Zone", http://www.izcity.com/, info@izcity.com |