Введение в криптологию // 2004 г.
| ВВЕДЕНИЕ Проблема защиты информации путем ее преобразования, исключающего прочтение посторонними, волновала человечество с давних времен. История кpиптогpафии практически ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Примером тому могут являться священные книги Древнего Египта и Древней Индии. Однако с началом широкого распространения письменности криптография стала формироваться как самостоятельная наука. Бурное развитие криптографические системы получили в годы первой и второй мировых войн. В дальнейшем появление достаточно мощных вычислительных средств ускорило разработку и совершенствование новых криптографических методов. В настоящее время про-блема их использования в информационных системах стала особенно актуальной. Это вызвано несколькими причинами. С одной стороны, расширилось использование глобальных компьютерных сетей, по ко-торым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ним посторонних лиц. С другой стороны, появление новых мощных компьютеров, технологий сетевых и нейронных вычислений сделало возможным дискредитацию криптографических систем, еще недавно считавшихся практически не раскрываемыми. Письменность обладает свойством вседоступности, которое в за-висимости от получателя сообщения можно рассматривать и как полезное, и как вредное. Потому параллельно письменности развивается секретное письмо – криптография. И поскольку компьютер революци-онно расширил сферу письменности, то почти одновременно возникла потребность столь же стремительного развития криптографии. Настоящее учебное пособие предназначено для того, чтобы помочь студентам обобщить полученный на лекционных занятиях материал и использовать его при подготовке к сдаче экзамена, а также в своей профессиональной деятельности, если она будет связана с защитой информации. Учебное пособие содержит информацию: • об общих классических сведениях по криптологии; • основах и принципах реализации симметричной и асимметричной методологий шифрования данных; • о теоретических основах работы известных криптоалгоритмов, их практической работе и применении. РАЗДЕЛ 1. ОБЩИЙ ОБЗОР ГЛАВА 1. ИСТОРИЯ КРИПТОГРАФИИ 1.1. Появление шифров Данные о первых способах тайнописи весьма обрывочны. Пред-полагается, что они были известны в Древнем Египте, Вавилоне, Шумере и Китае и появились одновременно с письменностью в IV тысячелетии до н.э. Секретная переписка развивалась независимо друг от друга в различных государствах. Криптограммы использовались даже в древние времена, хотя из-за применяемого в древнем мире идеографического письма в виде стилизованных картинок были примитивны. Так как число знаков идеографического письма было более тысячи, то их запоминание уже представляло трудную задачу. Тем не менее коды, появившиеся вместе со словарями, были хо-рошо известны в Вавилоне и Ассирии, а древние египтяне применяли по меньшей мере три системы шифрования. С развитием фонетического письма письменность резко упростилась. В древнем семитском алфавите во II тысячелетии до н.э. было всего около 30 знаков. Ими обо-значались согласные звуки, некоторые гласные и слоги. Упрощение письма стимулировало и развитие криптографии. 1.1.1. Шифр Цезаря Шифр замены, связанный с именем Юлия Цезаря, описал историк Древнего Рима Светоний. Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выпи-сывался алфавит: А, Б, В … затем под ним выписывался тот же алфавит со сдвигом на 3 буквы: При шифровании буква А заменялась буквой Г, Б заменялась на Д, и т.д. Так, например, слово "ЦЕЗАРЬ" превращалось в слово "ЩЗКГУЮ". Ключом в шифре Цезаря является величина сдвига нижней строки алфавита. 1.1.2. Скитала Иной шифр связан с перестановкой букв сообщения по определенному, известному отправителю и получателю правилу. Спартанцы наматывали полоску пергамента спиралью на палочку и писали на нем вдоль палочки текст сообщения. После сня-тия полоски буквы на ней располагались хаотично. Это аналогично тому, что писать буквы не подряд, а через условленное число по кольцу до тех пор, пока весь текст не будет исчерпан. Для прочтения шифровки нужно знать систему засекречивания и обладать ключом в виде палочки, принятого диаметра. Этот шифр именовался “скитала” по названию стержня, на ко-торый наматывались свитки папируса. Он был весьма популярен в Спарте и много раз совершенствовался в позднейшие времена. Зная тип шифра, но не имея ключа, расшифровать сообщение было сложно, хотя позднее Аристотель придумал способ дешифрования этого шифра с помощью конуса. 1.1.3. Диск Энея и его вариации Были и другие способы защиты информации, разработан-ные в античные времена. Древнегреческий полководец Эней Тактика в IV в. до н.э. предложил устройство, названное впо-следствии “диском Энея". На диске диаметром 10-15 см и толщиной 1-2 см высверливались отверстия по числу букв алфавита. В центре диска помещалась "катушка" с намотанной на ней ниткой достаточной длины. При шифровании нитка последовательно протягивалась через отверстия в соответствии с буквами шифруемого текста. Диск и являлся посланием. Получатель по-слания последовательно вытягивал нитку из отверстий, что позволяло ему получать передаваемое сообщение, но в обратном порядке следования букв. Эней предусмотрел возможность лег-кого уничтожения передаваемого сообщения при угрозе захвата диска. Для этого было достаточно выдернуть "катушку" с закрепленным на ней концом нити до полного выхода всей нити из всех отверстий диска. Идея Энея была использована и в других оригинальных шифрах замены. В одном из вариантов вместо диска использо-валась линейка с числом отверстий, равных количеству букв алфавита. Каждое отверстие обозначалось своей буквой; буквы по отверстиям располагались в произвольном порядке. К линейке была прикреплена катушка с намотанной на нее ниткой. Рядом с катушкой имелась прорезь. При шифровании нить протя-гивалась через прорезь, а затем через отверстие, соответствую-щее первой букве шифруемого текста, при этом на нити завязы-вался узелок в месте прохождения ее через отверстие. Затем нить возвращалась в прорезь и аналогично зашифровывалась вторая буква текста и т.д. После окончания шифрования нить извлекалась и передавалась получателю сообщения, который, имея идентичную линейку, протягивал нить через прорезь до отверстий, определяемых узлами, и восстанавливал исходный текст по буквам отверстий. Это устройство получило название "линейка Энея". Ключом такого шифра являлся порядок расположения букв по отверстиям в линейке. Посторонний, полу-чивший нить (даже имея линейку, но без нанесенных на ней букв), не сможет прочитать передаваемое сообщение. Римляне в IV в. до н.э. применяли шифрующие диски. Каждый из двух дисков, помещенных на общую ось, содержал на ободе алфавит в случайной последовательности. Найдя на одном диске букву текста, с другого диска считывали соответствующую ей букву шифра. Такие приборы, порождающие шифр простой замены использовались вплоть до эпохи Возрождения. Это, в общем-то, своего рода прообраз известной немецкой шифровальной машины Enigma. 1.1.4. Квадрат Полибия Греческий историк Полибий изобрел во II в. до н.э. “поли-бианский квадрат” размером 5 х 5, заполненный алфавитом в случайном порядке. Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от нее в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца. В других вариантах буква кодировалась номером соответствующей строки и столбца. Для связи греки и римляне использовали шифр, обозначив каждую ячейку своим числом флагов (ночью сигнал подавался факелами). • Известны и достаточно комичные способы, не связанные на-прямую с криптографией. Один из примеров “сокрытия” информации приведен древнегреческим историком Геродотом. На голове раба, которая брилась наголо, записывалось нужное со-общение. Когда волосы его достаточно отрастали, раба отправляли к адресату, который снова брил его голову и считывал полученное сообщение. 1.2. Криптография средневековья Во времена средневековья многие лучшие достижения цивилизации были утрачены. Применявшиеся в это время шифры были достаточно просты. 1.2.1. Различные варианты перестановок В шифрах средневековья часто используются таблицы, ко-торые дают простые шифрующие процедуры перестановки букв в сообщении. Ключом в них служат размер таблицы, фраза, задающая перестановку, или некая особенность таблиц. Простая перестановка без ключа – один из самых простых методов шифрования, родственный шифру скитала. Например, сообщение “НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ” записывается в таблицу по столбцам. Однако составление вручную таких таблиц, где любая буква встречается в строке или столбце один раз, – весьма трудоемкая задача. Для ручного многоалфавитного шифра полагаются лишь на длину и сложность ключа, используя приведенную таблицу, которую можно не держать в тайне, что упрощает шифрование и дешифрование. Книга Альберти "Трактат о шифре", написанная в 1466 г., представляла собой первый в мире научный труд по криптологии, если не считать арабских рукописей, с которыми Европа в то время вряд ли была знакома. В 1508 г. аббат из Германии Иоганн Трисемус написал "По-лиграфию", первую печатную работу по криптологии. В ней он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получе-ния такого шифра обычно использовались ключевое слово (или фраза) и таблица, которая для русского языка может иметь размер 5 х 6. Ключевое слово вписывалось в таблицу по строкам, а повторяющиеся буквы отбрасывались. Таблица дозаполнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключевое слово легко хранить в памяти, то такой подход упрощал процессы шифрования и дешифрования. Можно шифровать по две буквы за один раз. Такие шифры были названы би-граммными. Открытый текст разбивался на пары букв (би-граммы), и текст шифровки строился из него по следующим очень простым правилам: 1. Если обе буквы биграммы исходного текста принадлежали одной колонке таблицы, то буквами шифра считались буквы, которые лежали под ними. Если буква открытого текста находилась в нижнем ряду, то для шифра бралась соответствующая буква из верхнего ряда. 2. Если обе буквы биграммы исходного текста принадлежали одной строке таблицы, то буквами шифра считались буквы, которые лежали справа от них. Если буква открытого текста находилась в правой колонке, то для шифра бралась соответствую-щая буква из левой колонки. 3. Если обе буквы биграммы открытого текста лежали в разных рядах и колонках, то вместо них брались такие две буквы, чтобы вся четверка их представляла прямоугольник, причем последовательность букв в шифре была зеркальной исходной паре. Шифрование биграммами резко усилило стойкость шифров. Шифр “Решетка Кардано” представляет собой правильный квадрат (размеры могут варьироваться), разделенный на ячейки. Некоторые ячейки вырезаны. Текст записывается путем наложения квадрата с вырезанными ячейками на некоторый другой квадрат, имеющий ту же размерность. Путем вращения квадрата-шифра по часовой стрелке (или против часо-вой стрелки) адресат сможет прочитать посланное ему сообщение. 1.2.2. Магические квадраты Магическими квадратами называются квадратные табли-цы с вписанными в их клетки последовательными натуральны-ми числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Они ши-роко применялись для вписывания шифруемого текста по при-веденной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка, созданная путем перестановки букв. Считалось, что такие шифровки охраняет не только ключ, но и магическая сила. Число таких квадратов быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, не принимая во внимание его повороты. Магических квадратов 4 х4 – 880, а магических квадратов разме-ром 5 х 5 около 25 * 10 в 4-й степени. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим. 1.2.3. Арабская криптография Арабская цивилизация в это время была одной из самых развитых. Арабская медицина и математика являлись ведущими в мире. Естественно, что и наилучшие условия для развития криптографии появились именно здесь. Одно из основных понятий криптографии – шифр – произошло от арабского слова "цифра". Именно в арабских книгах впервые были описаны со-держательные методы криптоанализа (дешифрования). "Книга о большом стремлении человека разгадать загадки древней пись-менности" Абу Бакр Ахмед бен Али бен Вахшия ан-Набати была одним из первых трудов по криптографии. В 1412 г. Шехаб аль Кашканди написал 14-томную энциклопедию "Шауба аль-Аша". В этой работе имеется раздел о криптографии "Относительно сокрытия в буквах тайных сооб-щений". В нем дано систематическое описание различных шифров замены и перестановки. Здесь же приводится и криптоанализ этих шифров на основе подсчета частотности букв в арабском языке по тексту Корана, развиваются методы дешифрования, базирующиеся на разночастотности букв. В работе Каш-канди предлагается несколько систем шифрования: • одна буква может заменять другую; • можно писать слово в обратном порядке; • можно переставлять в обратном порядке чередующиеся буквы слов; • заменять буквы на цифры в соответствии с принятой заменой арабских букв на числа; • можно заменять каждую букву открытого текста на две арабские буквы, которые используются в качестве чисел и сумма которых равна цифровой величине шифруемой буквы открытого текста и т.д. 1.3. Криптография в России Странные русские письмена встречаются начиная с древно-сти. Однако по этому поводу много разных мнений: одни считают их остатками древней системы письменности, вытесненной впоследствии кириллическим алфавитом, другие – культовыми или календарными знаками и лишь немногие – настоящими шифрами. Чаще всего за шифры принимаются руны венедов, содержащие около 16 символов, которых явно недостаточно для передачи всех славянских звуков. Бесспорно тем не менее то, что уже с XIV в. в Новгороде существовала техника тайного письма, продолжение которой можно найти в шифровках русских дипломатических документов позднейших времен. Это были шифры простой замены, даже скорее коды, потому что кроме букв встречаются символы странных очертаний. Следует заметить, что соответствие букв знакам этого кода было многозначным: одна и та же буква могла передаваться несколькими разными символами. Уровень развития криптографии на Руси в это время безнадежно отставал от европейского. Однако через торговые связи Новгорода с Германией на Руси очень скоро становились известны все важнейшие открытия. Необходимость улучшения состояния государевой службы шифрования, входящей в Посольский приказ, особенно проявилась в конце XVII в., когда усилиями русской дипломатической службы расширяются международные связи Москвы. Заключая с Польшей в 1667 г. Андрусовское перемирие, видный русский дипломат А.Л. Ордин-Нащокин одновременно учредил и постоянную почтовую связь России с Европой. Коренным образом положение меняется с приходом к власти Петра I, который в 1712 г. встречался с Лейбницем, чтобы уговорить его разработать проекты развития образования и государственного устройства в России. В Петербурге появилась Цифирная палата, задачами которой было развитие и использование систем шифрования. Наиболее быстро применение криптографии развивалось в дипломатической службе обновленно-го Российского государства. Военные были более консервативны, хотя и они во время войны 1812 г. достаточно активно использовали шифры. Интересен оказался факт использования шифров в письмах А.С. Грибоедова к своей жене из Персии. При исследовании, сделанном криптоаналитиками, оказалось, что эти письма содержали дипломатические послания. Цифирное дело в России развивалось, и шифры стали употребляться не только для зарубежной, но и внутренней переписки. К концу 30-х годов XX в. с появлением специальных крупных криптографических подразделений, привлечением талантливых ученых и инженеров криптография в России вновь вышла на передовые позиции, что чрезвычайно пригодилось в годы второй мировой войны. 1.4. Дальнейшее развитие криптографии Постоянно расширяющееся применение шифров выдвинуло новое требование к ним, в частности легкость массового использования и усиление устойчивости к взлому. Во второй половине XIX в. появляется множество работ по вскрытию сложных шифров замены для конкретных условий, при использовании повторяющегося короткого ключа, при шифровке нескольких сообщений одним ключом. Тогда же в Англии и США стали выходить периодические издания, посвященные вопросам криптоанализа, где профессионалы и любители, обмениваясь опытом, предлагали новые типы шифров и анализировали их стойкость. В XIX в. с расширением связных коммуникаций процесс шифрования автоматизировался. Цифровое шифрующее колесо было изобретено госсекретарем Томасом Джефферсоном в 1790 г., ставшим потом третьим президентом США. Похожие шифрующие устройства применялись армией США и после второй мировой войны. Принцип работы таких машин, очень похожих на арифмометры, заключался в многоалфавитной за-мене текста сообщения по длинному ключу. Длина периода ключа определялась наименьшим общим кратным периодов оборотов шифрующих колес. При 4-х колесах и периодах их оборотов 13, 15, 17 и 19 получалась большая длина периода ключа 62985, очень затрудняющая расшифровку коротких со-общений. Гораздо более примитивный прибор, цилиндр Базери, был предложен Этьеном Базери в 1891 г. Он состоял из 20 дисков со случайно нанесенным по ободу алфавитом. Перед началом шифрования диски помешались на общую ось в порядке, определяемым ключом. Набрав первые 20 букв текста в ряд на цилиндрах, их поворачивали вместе и считывали в другом ряду шифрованное сообщение. Процесс повторялся до тех пор, пока все сообщение не было зашифровано. Однако первая практически используемая криптографическая машина была предложена Жильбером Вернамом лишь в 1917 г. Применение машин в криптографии расширялось, что привело к созданию частных фирм, занимающихся их серийным выпуском. Создание цифровых ЭВМ заставило полностью изменить взгляд на шифры и их расшифровывание. Очень быстро после распространения ЭВМ криптография сделала в своем развитии огромный скачок. Во-первых, были разработаны стойкие блочные шифры с секретным ключом, предназначенные для решения классиче-ской задачи – обеспечения секретности и целостности передаваемых или хранимых данных. Они до сих пор остаются наиболее часто используемыми средствами криптографической защиты. Во-вторых, были созданы методы решения новых задач сферы защиты информации, наиболее известными из которых являются задача подписи цифрового документа и открытого распределения ключей. (С) 2004, Д.А. Беляев, Ю.В. Гольчевский | |
|
| |
| Просмотров: 46 | |
| Всего комментариев: 0 | |