Сведения из истории криптографии

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

Древние греки оставили документальные подтверждения о различных применяемых ими шифровальных системах. Греками, а вернее спартанцами, во время многочисленных войн применялось одно из первых шифровальных устройств – Сцитала. Сцитала представляла собой цилиндрический жезл определенного диаметра. На Сциталу виток к витку наматывалась узкая полоска папируса (или кожаного ремня). На намотанной ленте вдоль оси жезла писали открытое сообщение. Затем ленту разматывали и переправляли адресату. После снятия папируса с жезла выходило, как будто буквы сообщения написаны в беспорядке поперек ленты. Если папирус попадал в руки противника, то секретное сообщение прочитать было невозможно. Для получения исходного текста была необходима Сцитала точно такого же диаметра – на нее наматывалась полученная полоска папируса, строки сообщения совмещались, и в результате можно было прочитать секретное послание. Ключом в данном методе шифрования являлся диаметр Сциталы. Интересно, что изобретение дешифровального "устройства" приписывается Аристотелю. Предполагается, что именно он предложил использовать конусообразное "копье", на которое наматывалась перехваченная лента с зашифрованным сообщением. Лента с буквами передвигалась вдоль оси конуса до тех пор, пока не появлялся осмысленный текст.

В Древней Греции использовались и другие шифры. Так, например, там был изобретен шифр, который в дальнейшем стал называться "квадратом Полибия". Согласно этому шифру буквы сообщения заменялись числами, представляющими собой координаты в квадрате 5x5, в который вписаны символы алфавита. Многочисленные исторические документы подтверждают, что в политике и в военном деле широко применялись различные шифры.

В арабских странах шифрование сообщений довольно широко использовалось как в военных, так и в политических целях и даже в переписке между торговыми партнерами. Кстати, слово " шифр " арабского происхождения, так же как и слово "цифра". В VIII – XV веках на свет появляются научные труды, содержащие сведения по криптографии: описания различных шифров и даже некоторых методов криптоанализа. Так, в многотомной энциклопедии "Шауба аль-Аша" упоминается о частотном криптоанализе (то есть анализе, основанном на частоте встречаемости букв открытого и зашифрованного сообщений). В этой же энциклопедии приводится таблица частотных характеристик букв арабского языка.

В средние века криптографические методы использовались, прежде всего, в военном деле, шпионаже, дипломатии. Изучением шифров занимались священники, ученые и дипломаты. На практике применялись различные шифры. Первые труды по криптографии созданы в XIV – XVI веках Чикко Симоннети (сотрудником папской канцелярии), Габлиэлем де Лавиндой (секретарем папы Клементия XII), Леоном Баттистой Альберти (знаменитым итальянским архитектором и философом), аббатом Иоганнесом Тритемием, жившем в Германии. Все указанные деятели внесли большой вклад в развитие криптографии, так как не только рассматривали в своих трудах существующие шифры, но и предлагали различные усовершенствованные методы шифрования, а также некоторые простейшие методы криптоанализа. Так, например, в трудах Симоннети и де Лавинды предлагаются шифры пропорциональной замены, в которых наиболее часто встречаемым буквам ставится в соответствие несколько символов для выравнивания частоты встречаемости знаков в шифротексте. Леон Альберти, вероятно, первым предложил так называемые полиалфавитные шифры. Нововведение Альберти состояло в том, чтобы использовать несколько замен в соответствии с ключом. Предполагается, что он также изобрёл первую автоматическую шифровальную машину — шифровальный диск, который осуществлял частичную реализацию его изобретения.

В XVII-XVIII веках во многих государствах Европы появились специальные шифровальные службы. В России датой появления криптографической службы специалисты называют 1549 год, когда был создан "посольский приказ", в котором имелось "цифирное" отделение. В эпоху Петра I криптографическая служба была реорганизована в "Посольскую канцелярию".

В различные времена криптографией занимались многие политики и ученые. Среди них Пифагор, Аристотель, Платон, Галилей, Д. Порта, Д. Кардано, Л. да Винчи, Ф. Виет, Д. Валлис, Б. Паскаль, И. Ньютон, Ф. Бекон, Х. Гольбах, Ф. Эпинус, Л. Эйлер, П.Ф. Шиллинг, Ч. Беббидж и другие.

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

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

В 20-х годах XX века для автоматизации процесса шифрования появились многочисленные механические устройства. В частности, широко использовались роторные шифровальные машины, в которых для выполнения операций замены символов применялись механические колеса – роторы. Шифровальные машины преобразовывали открытый текст в зашифрованный, состоящий из символов того же алфавита. После преобразования зашифрованная информация могла передаваться различными способами, например, по радиоканалу. Во всех развитых странах, в том числе и в СССР, создавались высокоскоростные шифрмашины, которые широко применялись во время второй мировой войны и позже.

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

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

С развитием информационных технологий криптография не только приобрела новые сферы применения, но и претерпела значительные изменения. В древние времена в процессе обмена зашифрованными сообщениями участвовало только две стороны, поэтому ключом шифрования необходимо было обеспечить только эти две стороны. В современных информационных системах в процессе передачи информации задействовано множество абонентов, и все они заинтересованы в надежных и удобных каналах получения ключей шифрования. Проблема распределения ключей была решена в двадцатом веке благодаря изобретению нового принципа шифрования – асимметричного шифрования или шифрования с открытым ключом (70-е годы ХХ в.). Основоположниками этого метода шифрования считаются У. Диффи и М. Хеллман. В асимметричных алгоритмах шифрования используются специальные математические функции – односторонние функции. Открытие асимметричных криптосистем позволило еще больше расширить сферы применения криптографии. Именно шифрование с открытым ключом лежит в основе процедур формирования цифровой подписи и проверки подлинности, а следовательно, и в основе принципов работы банковских пластиковых карт, "электронных" денег и других современных технологий.

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

Криптографические атаки

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

Атаки могут быть пассивными и активными.

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

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

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

Наиболее простыми характеристиками текстов, используемыми в криптоанализе, являются такие характеристики, как повторяемость букв, пар букв (биграмм) и вообще n-грамм, сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие. Такие характеристики изучаются на основе наблюдений текстов достаточно большой длины.

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

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

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

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

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

Однако еще в XIX веке специалисты в области криптографии предположили, что секретность алгоритма шифрования не является гарантией от взлома. Более того, в дальнейшем было понято, что по -настоящему надежная система шифрования должна оставаться защищённой, даже если противник полностью узнал алгоритм шифрования. Секретность ключа должна быть достаточна для хорошего шифра, чтобы сохранить стойкость к попыткам взлома. Этот фундаментальный принцип впервые был сформулирован в 1883 Керкхоффсом (A. Kerckhoffs) и обычно называется принципом Керкхоффса.

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

Принципы криптографии

Цель криптографической системы заключается в том, чтобы зашифровать осмысленный исходный текст (также называемый открытым текстом), получив в результате совершенно бессмысленный на взгляд шифрованный текст (шифртекст, криптограмма). Получатель, которому он предназначен, должен быть способен расшифровать (говорят также "дешифровать") этот шифртекст, восстановив, таким образом, соответствующий ему открытый текст. Криптография предполагает наличие трех компонентов: данных, ключа и криптографического преобразования.

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

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

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

Считается, что криптографическое преобразование известно всем, но, не зная ключа, с помощью которого пользователь закрыл смысл сообщения от любопытных глаз, требуется потратить невообразимо много усилий на восстановление текста сообщения. (Следует еще раз повторить, что нет абсолютно устойчивого от вскрытия шифрования. Качество шифра определяется лишь деньгами, которые нужно выложить за его вскрытие от $10 и до $1000000.)

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

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

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

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

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

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

Развитие криптографии

Криптография. Наука сколь таинственная, столь и увлекательная. Одна из древнейших на планете. Существует она, скорее всего, с того самого момента, когда появился на Земле homo sapiens – человек мыслящий. А вместе с ним и первые наскальные рисунки. Криптография – это наука о шифрах. О тех самых проблемах, которые можно создать своему противнику в плане сокрытия собственной важной информации. Потому в противовес ей возник криптоанализ. А объединила «две стороны одной медали» уже современная наука – криптология.

Сведения о системах и способах шифрования обнаружены в исторических документах таких древних цивилизаций, как Индия, Египет, Месопотамия. Шифровались даже религиозные тексты и медицинские рецепты. К шифрованию нередко прибегали ученые, дабы до поры до времени не прослыть еретиками и не подвергнуться преследованиям инквизиции. И в то же время весьма закрытая наука – криптография – во многих, даже европейских странах, не продвинулась, как гласит история, дальше «шифра Цезаря» – простейшего шифра замены. Строжайшая тайна, которая преследовала эту науку на протяжении веков, не позволяла ей бурно развиваться. И, тем не менее, искусство шифрования развивалось все-таки значительно быстрее, чем искусство дешифрования.

Широко известным историческим примером криптосистемы является так называемый шифр Цезаря, который представляет собой простую замену каждой буквы открытого текста третьей следующей за ней буквой алфавита (с циклическим переносом, когда это необходимо). Например, "A" заменялась на "D", "B" на "E", "Z" на "C".

В ручных шифрах давнего времени часто используются таблицы, которые дают простые шифрующие процедуры перестановки букв в сообщении. Ключом в них служат размер таблицы, фраза, задающая перестановку или специальная особенность таблиц. Простая перестановка без ключа - один из самых простых методов шифрования, родственный шифру скитала. Например, сообщение НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ записывается в таблицу по столбцам. Для таблицы из 5 строк и 7 столбцов это выглядит так:

Н О Н С Б Н Я

Е Е О Я О Е Т

Я С В Е Л П Н

С Т И Щ Е О Ы

Н А Т Е Е Н М

После того, как открытый текст записан колонками, для образования шифровки он считывается по строкам. Если его записывать группами по 5 букв, то получится: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы. Объединение букв в группы не входит в ключ шифра и используется лишь для удобства записи несмыслового текста.

Несмотря на значительные успехи математики за века, прошедшие со времён Цезаря, тайнопись вплоть до середины 20 века не сделала существенных шагов вперёд. В ней бытовал дилетантский, умозрительный, ненаучный подход.

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

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

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

Казалось бы, сделано все для невозможности вскрытия шифровок Энигмы. И все же английские криптографические службы в Блетчли Парке (уединенное поместье в 80 километрах севернее Лондона, отведенное британским криптологам.) почти всю войну читали немецкие шифры. Это стало возможным лишь благодаря польской разведке, которая к злополучному 1939 году смогла получить чертежи Энигмы и разобраться в ее устройстве. После нападения гитлеровцев на Польшу чертежи немецкой шифровальной машины были переданы Англии. Довольно быстро британские криптоаналитики установили, что для взлома шифра, нужно знать распайку проводов в шифрующих колесах. Началась охота британских спецслужб за образцами Энигмы. Первый удалось выкрасть прямо с завода на юго-востоке Германии, второй сняли со сбитого в небе Норвегии немецкого бомбардировщика, третий был найден во время боев за Францию у немецких военных связистов, взятых в плен. Остальные Энигмы сняты водолазами с немецких подводных лодок, за которыми специально стали охотиться и топить на малых глубинах. Взлом шифров Энигмы шел тяжело до тех пор, пока в 1942 году не вступили в строй несколько ЭВМ, специально созданных для этого Аланом Тьюрингом. Это была первая в мире довольно быстродействующая ЭВМ под названием "Колосс", специализированная для взлома шифров. После этого английские криптоаналитики могли меньше чем за день могли расколоть любую шифровку Энигмы, полученную добытыми ранее колесами, методично перебирая все возможные ключи. Немцы рассчитывали на сложность своего шифра, исходя из его ручной дешифровки, в то время как англичане стали его ломать, используя ЭВМ. Отметим, что сами немцы допускали возможность взлома шифра Энигмы. Еще в 1930 году ведущий немецкий криптоаналитик Георг Шредер продемонстрировал такую возможность, едко заметив при этом: "Энигма - дерьмо!" Однако она постоянно усложнялась и были периоды, когда в Блетчли Парке с ней не могли справиться. Перед шифровками Энигмы, которые исходили не от войск, а из немецких криптографических центров, "Колосс" тоже был бессилен.

Высокое развитие криптографической техники стран западных союзников в значительной степени предопределило ход многих боевых операций во время Второй мировой войны. Англия, хоть и несла на море большие потери, но практически подавляла любые организованные действия немецкого флота, перехватывая и читая приказы гроссадмиралов Редера и Деница. В книгах воспоминаний английских криптографов страницы сплошь усеяны фразами "...мы знали...", за которыми стоит колоссальный труд тысяч человек.

· Шифры Кардано

В середине ХVІ века в Италии появляется книга математика, врача и философа Дж. Кардано «О тонкостях» с дополнением «О разных вещах», в котором имеются разделы, посвчщенные ариптографии. В ней нашли отражение новые идеи криптографии: использование части самого передаваемого открытого текста в качестве ключа шифра и новый способ шифрования, который вошел в историю как «Решетка Кардано». Для ее изготовления брался лист из твердого материала (картон, прегамент, металл), представляющий собой квадрат, в котором вырезаны «окна». При использовании всех «окон» решетка поворачивалась на 90градусов, и вновь буквы открытого текста записывались в «окна» повернутой решетки. Затем вновь производился поворот на 90 градусов и т.д. В один «заход» заработала 4 раза. Если текст зашифрован не полностью, то решетка ставилась в исходное положение и вся процедура повторялась. Это ничто иное, как шифр перестановки.

Главное требование к решетке Кардано – при всех поворотах «окна» не должны попадать на одно и то же место в квадрате, в котором образуются шифртекст.

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

Жизнь Кардано была омрачена тяжелым и некрасивым спором – ссорой со своим другом – математиком Тарталья. Кардано «позаимствовал» свою знаменитую «формулу Кардано» (решение уравнения третьей степени) у его друга и опубликовал ее под собственным именем. Этот факт вызвал весбма негативную оценку со стороны современников Кардано и у последующих поколений математиков.

Судьба Кардано сложилась трагически. Как астролог, он заранее предсказал себе 75 лет жизни.

x=

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: