История криптографии - History of cryptography

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

Развитие криптография параллельно с развитием криптоанализ - «взлом» кодов и шифры. Открытие и раннее применение частотный анализ чтение зашифрованных сообщений иногда меняло ход истории. Таким образом Циммерманн Telegram спровоцировал вступление Соединенных Штатов в Первую мировую войну; и Союзник чтение нацистская Германия Шифрование России сократило время Второй мировой войны, по некоторым оценкам, на целых два года.

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

Античность

Scytale, одно из первых устройств шифрования.

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

Немного глиняные таблички из Месопотамии несколько позже явно предназначались для защиты информации - было обнаружено, что один датированный около 1500 г. до н.э. зашифровал рецепт мастера для глазури для керамики, предположительно имеющей коммерческую ценность.[2][3] Более того, иврит ученые использовали простые моноалфавитные подстановочные шифры (такой как Шифр атбаш ) примерно с 600 по 500 год до нашей эры.[4][5]

В Индии около 400 г. до н.э. - 200 г. н.э. Млеччита викалпа или «искусство понимать шифрованное письмо и писать слова особым образом» было задокументировано в Кама Сутра с целью общения влюбленных. Скорее всего, это был простой подстановочный шифр.[6][7] Части египетского демотический Греческие волшебные папирусы были написаны в шифр сценарий.[8]

В древние греки говорят, что знали о шифрах.[9] В скитале транспозиционный шифр использовался Спартанский военный,[5] но точно не известно, использовалась ли scytale для шифрования, аутентификации или избегания плохих предзнаменований в речи.[10][11] Геродот рассказывает нам о секретных посланиях, физически скрытых под воском на деревянных табличках или в виде татуировки на голове раба, скрытой отросшими волосами, хотя это не совсем примеры криптографии как таковой поскольку сообщение, однажды известное, становится непосредственно читаемым; это известно как стеганография. Другой греческий метод был разработан Полибий (теперь называется "Площадь Полибия ").[5] В Римляне кое-что знал о криптографии (например, Шифр цезаря и его вариации).[12]

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

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

Дэвид Кан отмечает в Взломщики кодов что современная криптология возникла среди Арабов, первые люди, систематически документирующие криптоаналитические методы.[13] Аль-Халиль (717–786) написал Книга криптографических сообщений, который содержит первое использование перестановки и комбинации перечислить все возможные арабский слова с гласными и без них.[14]

Изобретение частотный анализ техника взлома моноалфавитного подстановочные шифры, к Аль-Кинди, Арабский математик,[15][16] где-то около 800 г. н.э. он оказался самым значительным достижением криптоаналитики до Второй мировой войны. Аль-Кинди написал книгу по криптографии под названием Рисала фи Истихрадж аль-Муамма (Рукопись для расшифровки криптографических сообщений), в котором он описал первые криптоаналитические методы, в том числе некоторые для полиалфавитные шифры, шифровальная классификация, арабская фонетика и синтаксис, и, что самое важное, дали первые описания частотного анализа.[17] Он также охватывал методы шифрования, криптоанализ некоторых способов шифрования и статистический анализ букв и их комбинаций на арабском языке.[18][19] Важный вклад Ибн Адлан (1187–1268) был на размер образца для использования частотного анализа.[14]

В раннесредневековой Англии между 800–1100 годами переписчики часто использовали замещающие шифры как игривый и умный способ зашифровать заметки, решения загадок и колофоны. Шифры, как правило, довольно просты, но иногда они отклоняются от обычного шаблона, что увеличивает их сложность и, возможно, также их изощренность.[20] В этот период на Западе проводились важные и важные криптографические эксперименты.

Ахмад аль-Калкашанди (1355–1418 гг.) Написал Субх аль-а 'ша, 14-томная энциклопедия, включающая раздел по криптологии. Эта информация была приписана Ибн ад-Дурайхим который жил с 1312 по 1361 год нашей эры, но чьи труды по криптографии были утеряны. В список шифров в этой работе вошли как замена и транспозиция, и впервые был использован шифр с множественными заменами для каждого простой текст буква (позже названная омофонической заменой). Также к Ибн ад-Дурайхиму относятся описание и отработанный пример криптоанализа, включая использование таблиц частота букв и наборы букв, которые не могут совпадать в одном слове.

Самый ранний пример омофонического подстановочный шифр это тот, который используется Герцог Мантуи в начале 1400-х гг.[21] Гомофонический шифр заменяет каждую букву несколькими символами в зависимости от частоты букв. Шифр опережает время, поскольку сочетает в себе моноалфавитные и полиалфавитные особенности.

По сути, все шифры оставались уязвимыми для криптоаналитической техники частотного анализа до разработки полиалфавитного шифра, и многие остались таковыми после этого. Наиболее ясно полиалфавитный шифр объяснил Леон Баттиста Альберти примерно в 1467 году нашей эры, за что его называли «отцом западной криптологии».[1] Йоханнес Тритемиус, в его работе Полиграфия, изобрел tabula recta, критический компонент шифра Виженера. Тритемий также написал Стеганография. Французский криптограф Блез де Виженера разработал практическую полиалфавитную систему, которая носит его имя, Шифр Виженера.[1]

В Европе криптография стала (тайно) более важной в результате политической конкуренции и религиозной революции. Например, в Европе во время и после эпоха Возрождения, граждане различных итальянских государств - Папская область и Римско-католическая церковь в том числе - были ответственны за быстрое распространение криптографических методов, некоторые из которых отражают понимание (или даже знание) полиалфавитного прогресса Альберти. «Продвинутые шифры» даже после Альберти не были такими продвинутыми, как утверждали их изобретатели / разработчики / пользователи (и, возможно, даже они сами). Они часто ломались. Этот чрезмерный оптимизм может быть присущ криптографии, поскольку тогда - и остается сегодня - в принципе трудно понять, насколько уязвима собственная система. При отсутствии знаний предположения и надежды вполне предсказуемы.

Криптография, криптоанализ, и предательство секретного агента / курьера, показанное в Заговор Бабингтона во время правления королевы Елизавета I что привело к казни Мария, королева Шотландии. Роберт Гук предложено в главе Книги духов доктора Ди, который Джон Ди использовал стеганографию Тритема, чтобы скрыть свое общение с королевой Елизаветой I.[22]

Главным криптографом короля Франции Людовика XIV был Антуан Россиньоль; он и его семья создали то, что известно как Великий шифр потому что он оставался нерешенным с момента своего первоначального использования до 1890 года, когда французский военный криптоаналитик, Этьен Базери решил это.[23] Зашифрованное сообщение времен Человек в железной маске (расшифровано незадолго до 1900 г. Этьен Базери ) пролил некоторый, к сожалению, не окончательный, свет на личность этого реального, хотя и легендарного и несчастного заключенного.

За пределами Европы, после того, как монголы положили конец Исламский золотой век, криптография оставалась сравнительно неразвитой. Криптография в Японии похоже, не использовались примерно до 1510 года, а передовые методы были известны только после открытия страны для Запада, начиная с 1860-х годов.

Криптография с 1800 года до Второй мировой войны

Основная статья: Криптография Первой мировой войны

Хотя криптография имеет долгую и сложную историю, только в 19 веке она разработала нечто большее, чем специальные подходы к шифрованию или криптоанализ (наука о поиске слабых мест в криптосистемах). Примеры последнего включают Чарльз Бэббидж с Крымская война эры работы по математическому криптоанализу полиалфавитные шифры, переработанная и опубликованная несколько позже прусским Фридрих Касиски. Понимание криптографии в то время, как правило, состояло из с трудом завоеванных практических правил; см., например, Огюст Керкхоффс 'криптографические письма в конце 19 века. Эдгар Аллан По использовал систематические методы для решения шифров в 1840-х годах. В частности, он отметил свои способности в Филадельфия бумага Еженедельный (экспресс) вестник Александра, предлагая представить шифры, из которых он приступил к решению почти всех. Его успех вызывал общественный резонанс в течение нескольких месяцев.[24] Позже он написал эссе о методах криптографии, которое оказалось полезным в качестве введения для начинающих британских криптоаналитиков, пытающихся взломать немецкие коды и шифры во время Первой мировой войны, а также знаменитую историю: Золотой жук, в котором криптоанализ был важным элементом.

Криптография и ее неправомерное использование были вовлечены в выполнение Мата Хари И в Осуждение Дрейфуса и тюремное заключение, как в начале 20 века. Криптографы также участвовали в раскрытии махинаций, приведших к делу Дрейфуса; Мата Хари, напротив, была застрелена.

В Первой мировой войне Адмиралтейство с Комната 40 нарушил военно-морские кодексы Германии и сыграл важную роль в нескольких морских сражениях во время войны, особенно в обнаружении крупных немецких вылетов в Северное море что привело к битвам Доггер Банк и Ютландия поскольку британский флот был отправлен на их перехват. Однако его наиболее важный вклад был, вероятно, в расшифровка в Циммерманн Telegram, а кабель из министерства иностранных дел Германии отправлено через Вашингтон в его посол Генрих фон Эккардт в Мексике, которая сыграла важную роль в вовлечении Соединенных Штатов в войну.

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

В течение 1920-х годов польские военно-морские офицеры помогали японским военным в разработке кодов и шифров.

Математические методы получили распространение в период до Второй мировой войны (особенно в Уильям Фридман применение статистических методов для криптоанализа и разработки шифров и в Мариан Реевски начальный прорыв в версию немецкой армии Enigma система в 1932 г.).

Криптография Второй мировой войны

Смотрите также: Криптография Второй мировой войны, Криптоанализ, и Список криптографов
В Энигма машина широко использовалась нацистской Германией; его криптоанализ союзниками обеспечил жизненно важную Ультра интеллект.

К началу Второй мировой войны механические и электромеханические шифровальные машины широко использовались, хотя - там, где такие машины были непрактичными -кодовые книги и ручные системы продолжали использоваться. Большие успехи были достигнуты как в дизайне шифров, так и в криптоанализ, все в секрете. Информация об этом периоде начала рассекречиваться по мере того, как подошел к концу официальный британский 50-летний период секретности, поскольку архивы США медленно открывались, и по мере появления различных мемуаров и статей.

Германия

Немцы широко использовали в нескольких вариантах электромеханический роторная машина известный как Enigma.[25] Математик Мариан Реевски, в Польше Бюро шифров, в декабре 1932 г. вывел детальную структуру Загадки немецкой армии, используя математику и ограниченную документацию, предоставленную капитаном Гюстав Бертран французского военная разведка. По словам историка, это был величайший прорыв в криптоанализе за тысячу и более лет. Дэвид Кан.[нужна цитата ] Реевский и его коллеги из Бюро математических шифров, Ежи Ружицкий и Хенрик Зыгальский, продолжил читать Enigma и идти в ногу с развитием компонентов машин немецкой армии и процедур шифрования. Поскольку ресурсы поляков были истощены из-за изменений, вводимых немцами, и по мере того, как надвигалась война, Бюро шифров, на польском Генеральный штаб инструкции от 25 июля 1939 г. Варшава, инициировал представителей французской и британской разведки в секретах расшифровки Enigma.

Вскоре после вторжение в Польшу Германией 1 сентября 1939 г., ключ Бюро шифров личный состав был эвакуирован на юго-восток; 17 сентября, когда Советский Союз напал на Польшу с востока они перешли в Румыния. Оттуда они достигли Парижа, Франция; в ПК Бруно, недалеко от Парижа, они продолжали работать над взломом Enigma, сотрудничая с британскими криптологи в Bletchley Park поскольку британцы начали свою работу, взламывая Enigma. Со временем британские криптографы, в число которых входили многие мастера шахмат и математики, такие как Гордон Велчман, Макс Ньюман, и Алан Тьюринг (концептуальный основоположник современного вычисление ) - совершил существенный прорыв в масштабах и технологиях Расшифровка загадки.

Взлом немецкого кода во Второй мировой войне также имел некоторый успех, в первую очередь благодаря взломать военно-морской шифр № 3. Это позволило им отслеживать и топить атлантические конвои. Это было только Ультра разведки, которая наконец убедила адмиралтейство изменить свои коды в июне 1943 года. Это удивительно, учитывая успех британских Комната 40 взломщики кода в предыдущей мировой войне.

В конце войны, 19 апреля 1945 года, высшим военным офицерам Великобритании сказали, что они никогда не смогут раскрыть, что немецкий шифр Enigma был взломан, потому что это даст побежденному противнику шанс сказать, что он «плохо себя и побежден. ".[26]

Немецкие военные также развернули несколько телетайп потоковые шифры. Блетчли-Парк назвал их Рыбные шифры, и Макс Ньюман и коллеги разработали и развернули Хит Робинсон, а затем и первый в мире программируемый цифровой электронный компьютер, Колосс, чтобы помочь с их криптоанализом. Министерство иностранных дел Германии начало использовать одноразовый блокнот в 1919 г .; часть этого трафика была прочитана во время Второй мировой войны, отчасти в результате обнаружения некоторых ключевых материалов в Южной Америке, которые были без должной осторожности выброшены немецким курьером.

В Schlüsselgerät 41 был разработан в конце войны как более безопасная замена Enigma, но имел ограниченное применение.

Япония

Группа армии США, SIS, сумел взломать систему дипломатических шифров высочайшего уровня безопасности Японии (электромеханический шаговый переключатель машина называется Фиолетовый американцами) в 1940 году, до начала Второй мировой войны. Машина Purple, разработанная на месте, заменила более раннюю машину Red, которая использовалась Министерством иностранных дел Японии, и родственную машину M-1, используемую военно-морскими атташе, которая была сломана военно-морскими силами США. Агнес Дрисколл. Все японские машинные шифры в той или иной степени взломаны союзниками.

Японский флот и армия в основном использовали системы кодовых книг, позже с отдельной числовой добавкой. ВМС США криптографы (в сотрудничестве с британскими и голландскими криптографами после 1940 г.) взломали несколько Японский флот криптосистемы. Взлом одного из них, JN-25, что привело к победе США в Битва за Мидуэй; и к публикации этого факта в Чикаго Трибьюн вскоре после боя, хотя японцы, кажется, этого не заметили, потому что они продолжали использовать систему JN-25.

Союзники

Американцы называли разведывательные данные, полученные в результате криптоанализа, возможно, особенно с помощью машины Purple, как «Магия '. Британцы в конце концов остановились наУльтра 'для разведки, полученной в результате криптоанализа, в частности, из трафика сообщений, защищенного различными загадками. Более ранний британский термин для Ultra был «Бонифаций» в попытке предположить, что в случае его предательства, у него мог быть отдельный агент в качестве источника.

SIGABA описана в Патент США 6,175,625 , подана в 1944 г., но выпущена не ранее 2001 г.

Союзник шифровальные машины, использованные во Второй мировой войне, включали британских Тип X и американский СИГАБА; Оба были электромеханическими роторами, по духу похожими на Enigma, хотя и с существенными улучшениями. Ни один из них не сломался во время войны. Поляки использовали Lacida машина, но ее безопасность оказалась ниже запланированной (шифровальщики польской армии в Великобритании), и ее использование было прекращено. Войска США в полевых условиях использовали М-209 и еще менее безопасный М-94 семейные машины. Британский ГП сначала агенты использовали «шифры стихотворений» (заученные стихи были ключами шифрования / дешифрования), но позже, во время войны, они начали выключатель к одноразовые колодки.

В Шифр VIC (использовался по крайней мере до 1957 г. в связи с Рудольф Абель шпионской сети Нью-Йорка) был очень сложным ручным шифром, и, по словам Дэвида Кана в работе, он считается самым сложным из известных, из когда-либо используемых Советским Союзом Кан о кодах. Для расшифровки советских шифров (особенно когда одноразовые колодки были повторно использованы) см. Венона проект.

Роль женщин

В Великобритании и США было задействовано большое количество женщин для взлома кодов, около 7000 сообщили в Блетчли-Парк.[27] и 11 000 - для отдельных операций армии и флота США вокруг Вашингтона, округ Колумбия.[28] По традиции в Японии и Нацистская доктрина в Германии женщины не допускались к работе на войне, по крайней мере, до конца войны. Даже после того, как системы шифрования были взломаны, требовался большой объем работы, чтобы реагировать на внесенные изменения, восстанавливать ежедневные настройки ключей для нескольких сетей, а также перехватывать, обрабатывать, переводить, определять приоритеты и анализировать огромный объем вражеских сообщений, генерируемых в глобальном конфликте. Несколько женщин, в том числе Элизабет Фридман и Агнес Мейер Дрисколл, внесли большой вклад в взлом кодов США в 1930-х годах, а незадолго до нападения на Перл-Харбор военно-морские силы и армия начали активно набирать лучших выпускников женских колледжей. Лиза Манди утверждает, что это неравенство в использовании талантов женщин между союзниками и странами Оси имело стратегическое значение в войне.[28]:стр.29

Современная криптография

Шифрование в наше время достигается за счет использования алгоритмов, имеющих ключ для шифрования и дешифрования информации. Эти ключи преобразуют сообщения и данные в «цифровую тарабарщину» с помощью шифрования, а затем возвращают их в исходную форму с помощью дешифрования. В общем, чем длиннее ключ, тем сложнее взломать код. Это верно, потому что для расшифровки зашифрованного сообщения с помощью грубой силы злоумышленник должен пробовать все возможные ключи. Чтобы поместить это в контекст, каждая двоичная единица информации или бит имеет значение 0 или 1. В этом случае 8-битный ключ будет иметь 256 или 2 ^ 8 возможных ключей. 56-битный ключ будет иметь 2 ^ 56 или 72 квадриллиона возможных ключей для попытки расшифровать сообщение. Благодаря современным технологиям дешифровать шифры, использующие ключи такой длины, становится легче. DES, ранний шифр, одобренный правительством США, имеет эффективную длину ключа 56 бит, и тестовые сообщения, использующие этот шифр, были взломаны путем перебора ключей. Однако с развитием технологий повышается и качество шифрования. После Второй мировой войны одним из наиболее заметных достижений в изучении криптографии стало введение шифров с асимметричным ключом (иногда называемых шифрами с открытым ключом). Это алгоритмы, которые используют два математически связанных ключа для шифрования одного и того же сообщения. Некоторые из этих алгоритмов допускают публикацию одного из ключей, так как чрезвычайно сложно определить один ключ, просто зная о другом.[29]

Примерно с 1990 года использование Интернет в коммерческих целях и введение коммерческих транзакций через Интернет потребовало широкого распространения стандарта шифрования. Перед введением Расширенный стандарт шифрования (AES), информация, отправляемая через Интернет, например финансовые данные, была зашифрована, если вообще была зашифрована, чаще всего с использованием стандарта шифрования данных (DES). Это было одобрено NBS (правительственным агентством США) в целях обеспечения безопасности после публичного призыва и конкурса среди кандидатов на такой алгоритм шифрования. DES был одобрен на короткий период, но широко использовался из-за сложных споров по поводу использования общественностью высококачественного шифрования. В конце концов, DES был заменен на AES после еще одного открытого конкурса, организованного агентством-преемником NBS, NIST. Примерно с конца 1990-х - начала 2000-х годов использование алгоритмов с открытым ключом стало более распространенным подходом к шифрованию, и вскоре гибрид двух схем стал наиболее распространенным способом продолжения операций электронной коммерции. Кроме того, создание нового протокола, известного как Secure Socket Layer или SSL, открыло путь для онлайн-транзакций. Для транзакций, от покупки товаров до онлайн-оплаты счетов и банковских операций, использовался протокол SSL. Кроме того, по мере того, как беспроводное подключение к Интернету становилось все более распространенным среди домашних хозяйств, потребность в шифровании росла, поскольку в этих повседневных ситуациях требовался определенный уровень безопасности.[30]

Клод Шеннон

Клод Э. Шеннон считается многими[ласковые слова ] быть отцом математической криптографии. Шеннон несколько лет проработал в Bell Labs, и за время своего пребывания там он написал статью под названием «Математическая теория криптографии». Эта статья была написана в 1945 году и впоследствии была опубликована в Bell System Technical Journal в 1949 году.[31] Принято считать, что эта статья стала отправной точкой для развития современной криптографии. Во время войны Шеннон был вдохновлен на решение «проблем криптографии, [потому что] системы секретности представляют интересное приложение теории коммуникации». Шеннон выделил две основные цели криптографии: секретность и достоверность. Его внимание было сосредоточено на исследовании секретности, и тридцать пять лет спустя Г.Дж. Симмонс затронет вопрос подлинности. Шеннон написал следующую статью под названием «Математическая теория коммуникации», в которой освещается один из наиболее важных аспектов его работы: переход криптографии от искусства к науке.[32]

В своих работах Шеннон описал два основных типа систем секретности. Первые - это те, которые разработаны с целью защиты от хакеров и злоумышленников, которые имеют бесконечные ресурсы для декодирования сообщения (теоретическая секретность, теперь безусловная безопасность), а вторые - те, которые предназначены для защиты от хакеров и атак с ограниченными ресурсами, с помощью которых для декодирования сообщения (практическая секретность, теперь вычислительная безопасность). Большая часть работ Шеннона сосредоточена на теоретической секретности; здесь Шеннон ввел определение «неразрывности» шифра. Если шифр определялся как «нерушимый», считалось, что он обладает «полной секретностью». Доказывая «совершенную секретность», Шеннон определил, что это может быть получено только с помощью секретного ключа, длина которого, указанная в двоичных цифрах, больше или равна количеству битов, содержащихся в зашифрованной информации. Более того, Шеннон разработал «расстояние уникальности», определяемое как «количество открытого текста, которое ... определяет секретный ключ».[32]

Работа Шеннона повлияла на дальнейшие исследования в области криптографии в 1970-х годах, поскольку разработчики криптографии с открытым ключом М. Э. Хеллман и У. Диффи указали на исследование Шеннона как на большое влияние. Его работа также повлияла на современные разработки шифров с секретным ключом. В конце работы Шеннона с криптографией прогресс замедлился, пока Хеллман и Диффи не представили свою статью, касающуюся «криптографии с открытым ключом».[32]

Стандарт шифрования

В середине 1970-х годов произошло два крупных публичных (т. Е. Несекретных) прогресса. Сначала была публикация проекта Стандарт шифрования данных в США. Федеральный регистр 17 марта 1975 г. Предложенный шифр DES был представлен исследовательской группой в IBM, по приглашению Национального бюро стандартов (ныне NIST ), стремясь разработать безопасные средства электронной связи для таких предприятий, как банки и другие крупные финансовые организации. После совета и модификации АНБ, действуя за кулисами, он был принят и опубликован как Федеральный стандарт обработки информации Издание 1977 г. (в настоящее время FIPS 46-3 ). DES был первым общедоступным шифром, получившим «благословение» национального агентства, такого как АНБ. Выпуск его спецификации NBS стимулировал взрыв общественного и академического интереса к криптографии.

Устаревший DES был официально заменен на Расширенный стандарт шифрования (AES) в 2001 году, когда NIST объявил о FIPS 197. После открытого конкурса NIST выбрал Rijndael, представленный двумя бельгийскими криптографами как AES. DES и его более безопасные варианты (например, Тройной DES ), все еще используются сегодня, будучи включены во многие национальные и организационные стандарты. Однако его 56-битный размер ключа оказался недостаточным для защиты от атака грубой силой (одна такая атака, предпринятая кибер-группой гражданских прав Фонд электронных рубежей в 1997 году удалось за 56 часов.[33]В результате, использование прямого шифрования DES теперь, без сомнения, небезопасно для использования в новых проектах криптосистем, а сообщения, защищенные более старыми криптосистемами с использованием DES, и действительно все сообщения, отправленные с 1976 года с использованием DES, также находятся под угрозой. Независимо от присущего DES качества, размер ключа DES (56 бит) считался некоторыми слишком маленьким даже в 1976 году, возможно, наиболее публично Уитфилд Диффи. Существовало подозрение, что правительственные организации уже тогда обладали достаточной вычислительной мощностью, чтобы взламывать сообщения DES; очевидно, что другие достигли этой способности.

Открытый ключ

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

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

По необходимости, ключ в каждой такой системе должен был быть обменен между взаимодействующими сторонами каким-либо безопасным способом до любого использования системы (обычно используется термин «через безопасный канал '), например, надежный курьер с портфелем, прикованным наручниками к запястью, или личный контакт, или верный почтовый голубь. Это требование никогда не бывает тривиальным и очень быстро становится неуправляемым по мере увеличения числа участников, когда безопасные каналы недоступны для обмена ключами, или когда, как это разумная криптографическая практика, ключи часто меняются. В частности, если предполагается, что сообщения будут защищены от других пользователей, для каждой возможной пары пользователей требуется отдельный ключ. Такая система называется секретным ключом или симметричный ключ криптосистема. Обмен ключами D-H (а также последующие улучшения и варианты) сделали работу этих систем намного проще и безопаснее, чем когда-либо ранее за всю историю.

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

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

Эффективность асимметричных алгоритмов зависит от класса математических задач, называемых односторонними функциями, которые требуют относительно небольшой вычислительной мощности для выполнения, но огромной мощности для реверсирования, если реверсирование вообще возможно. Классический пример односторонней функции - умножение очень больших простых чисел. Умножить два больших простых числа довольно быстро, но очень сложно найти множители произведения двух больших простых чисел. Из-за математики односторонних функций большинство возможных ключей - плохой выбор в качестве криптографических ключей; подходит только небольшая часть возможных ключей заданной длины, поэтому асимметричным алгоритмам требуются очень длинные ключи для достижения той же длины. уровень безопасности обеспечивается относительно более короткими симметричными ключами. Необходимость как генерировать пары ключей, так и выполнять операции шифрования / дешифрования, делает асимметричные алгоритмы дорогостоящими в вычислительном отношении по сравнению с большинством симметричных алгоритмов. Поскольку симметричные алгоритмы часто могут использовать любую последовательность (случайную или, по крайней мере, непредсказуемую) бит в качестве ключа, одноразовый ключ сеанса могут быть быстро созданы для краткосрочного использования. Следовательно, распространенной практикой является использование длинного асимметричного ключа для обмена одноразовым, гораздо более коротким (но столь же надежным) симметричным ключом. Более медленный асимметричный алгоритм безопасно отправляет симметричный сеансовый ключ, а более быстрый симметричный алгоритм берет на себя оставшуюся часть сообщения.

Криптография с асимметричным ключом, обмен ключами Диффи – Хеллмана и наиболее известный из алгоритмов открытого / закрытого ключей (то есть то, что обычно называется алгоритмом RSA), похоже, были независимо разработаны в британском разведывательном агентстве до публичного объявления. Диффи и Хеллмана в 1976 году. GCHQ опубликовал документы, в которых утверждалось, что они разработали криптографию с открытым ключом до публикации статьи Диффи и Хеллмана.[нужна цитата ] Различные секретные статьи были написаны в GCHQ в течение 1960-х и 1970-х годов, что в конечном итоге привело к схемам, по существу идентичным шифрованию RSA и обмену ключами Диффи-Хеллмана в 1973 и 1974 годах. Некоторые из них теперь опубликованы, и изобретатели (Джеймс Х. Эллис , Клиффорд Кокс и Малкольм Уильямсон) обнародовали (некоторые) свои работы.

Хеширование

Хеширование это распространенный метод, используемый в криптографии для быстрого кодирования информации с использованием типичных алгоритмов. Как правило, алгоритм применяется к строке текста, и результирующая строка становится «хеш-значением». Это создает «цифровой отпечаток» сообщения, поскольку конкретное значение хеш-функции используется для идентификации конкретного сообщения. Выходные данные алгоритма также называют «дайджестом сообщения» или «контрольной суммой». Хеширование полезно для определения того, была ли информация изменена при передаче. Если значение хеш-функции при приеме отличается от значения при отправке, это свидетельствует о том, что сообщение было изменено. После того, как алгоритм был применен к хешируемым данным, хеш-функция производит вывод фиксированной длины. По сути, все, что проходит через хеш-функцию, должно разрешаться в вывод той же длины, что и все остальное, переданное через ту же хеш-функцию. Важно отметить, что хеширование - это не то же самое, что шифрование. Хеширование - это односторонняя операция, которая используется для преобразования данных в сжатый дайджест сообщения. Кроме того, целостность сообщения может быть измерена с помощью хеширования. И наоборот, шифрование - это двусторонняя операция, которая используется для преобразования открытого текста в зашифрованный текст, а затем наоборот. При шифровании конфиденциальность сообщения гарантируется.[34]

Для проверки цифровых подписей можно использовать хеш-функции, так что при подписании документов через Интернет подпись применяется к одному конкретному человеку. Как и собственноручная подпись, эти подписи проверяются путем присвоения человеку их точного хэш-кода. Кроме того, хеширование применяется к паролям для компьютерных систем. Хеширование паролей началось с UNIX Операционная система. Пользователь в системе сначала создаст пароль. Этот пароль будет хеширован с использованием алгоритма или ключа, а затем сохранен в файле паролей. Это все еще актуально сегодня, поскольку веб-приложения, требующие паролей, часто хэшируют пароли пользователей и сохраняют их в базе данных.[35]

Политика криптографии

Общественные разработки 1970-х разрушили почти монополию на высококачественную криптографию, принадлежавшую правительственным организациям (см. S. Levy's Крипто для журналистского отчета о некоторых политических противоречиях того времени в США). Впервые в истории внешние государственные организации получили доступ к криптографии, которую никто (включая правительства) не мог взломать. Существенные споры и конфликты, как государственные, так и частные, начались более или менее сразу, что иногда называют крипто войны. Они еще не утихли. Во многих странах, например, экспорт криптографии подлежит ограничениям. До 1996 года экспорт из США криптографии с использованием ключей длиной более 40 бит (слишком маленьких, чтобы их можно было защитить от опытного злоумышленника) был резко ограничен. Еще в 2004 году бывший ФБР Директор Луи Фри, давая показания перед 9/11 Комиссия, призвала принять новые законы против публичного использования шифрования.

Одним из самых значительных сторонников надежного шифрования для публичного использования был Фил Циммерманн. Он написал, а затем в 1991 году выпустил PGP (Pretty Good Privacy), очень качественный криптосистема. Он распространял бесплатную версию PGP, когда чувствовал угрозу со стороны законодательства, которое тогда находилось на рассмотрении правительства США, которое потребовало бы включения бэкдоров во все криптографические продукты, разрабатываемые в США. Его система была распространена во всем мире вскоре после того, как он выпустил ее в США, и это положило начало длительному уголовному расследованию в отношении него Министерством юстиции США по обвинению в нарушении экспортных ограничений. Министерство юстиции в конце концов отказалось от иска против Циммермана, и бесплатное распространение PGP продолжилось по всему миру. PGP даже со временем стал открытым Интернет стандарт (RFC 2440 или же OpenPGP ).

Современный криптоанализ

В то время как современные шифры вроде AES а асимметричные шифры более высокого качества широко считаются неразрушаемыми, плохие конструкции и реализации все еще иногда принимаются, и в последние годы произошли важные криптоаналитические взломы развернутых криптосистем. Известные примеры сломанных криптографических проектов включают в себя первые Вай фай схема шифрования WEP, то Система скремблирования контента используется для шифрования и контроля использования DVD, A5 / 1 и A5 / 2 шифры, используемые в GSM сотовые телефоны и КРИПТО1 шифр, используемый в широко распространенных MIFARE Классический смарт-карты из Полупроводники NXP, выделившееся подразделение Philips Electronics. Все это симметричные шифры. До сих пор ни одна из математических идей, лежащих в основе криптографии с открытым ключом, не была доказана как «неразрушимая», и поэтому некоторые будущие достижения математического анализа могут сделать системы, полагающиеся на них, небезопасными. Хотя немногие информированные наблюдатели предвидят такой прорыв, размер ключа, рекомендуемый для обеспечения безопасности в соответствии с передовой практикой, продолжает расти, поскольку увеличивающаяся вычислительная мощность, необходимая для взлома кодов, становится дешевле и доступнее. Квантовые компьютеры, если когда-либо будет построена с достаточной мощностью, может нарушить существующие алгоритмы открытого ключа, и в настоящее время предпринимаются усилия по разработке и стандартизации постквантовая криптография.

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

Смотрите также

Рекомендации

  1. ^ а б c d «Краткая история криптографии». Cypher Research Laboratories. 24 января 2006 г.. Получено 18 сентября 2013.
  2. ^ «Криптография в древних цивилизациях». Получено 18 сентября 2013.[постоянная мертвая ссылка ]
  3. ^ Кан, Дэвид. Взломщики кодов: всеобъемлющая история секретной коммуникации с древних времен в Интернет, исправленная и обновленная. Скрибнер. Нью Йорк, Нью Йорк. 1996 г.
  4. ^ «Краткая история криптографии». Криптозин. 16 мая 2008 г.
  5. ^ а б c «2.1 - Краткая история криптографии». all.net. Получено 19 марта 2018.
  6. ^ Переводчики: Ричард Бертон, Бхагаванлал Индраджит, Шиварам Парашурам Бхиде (18 января 2009 г.). Камасутра Ватсьяяна (перевод с санскрита в семи частях с предисловием, введением и заключительными замечаниями). Проект Гутенберг. Получено 3 декабря 2015.CS1 maint: несколько имен: список авторов (связь)
  7. ^ Дэвид Кан (декабрь 1996 г.). Взломщики кодов. Саймон и Шустер. п. 74. ISBN  9781439103555. Получено 25 ноября 2015.
  8. ^ Ханс Дитер Бец (1992). «Греческий магический папирус в переводе, включая демотические заклинания, том 1».
  9. ^ «История шифрования». SANS.
  10. ^ Келли, Томас. «Миф Скайтейла». Cryptologia 22.3 (1998): 244–260.
  11. ^ Латейнер, Д. «Значение имен и других зловещих случайных высказываний в классической историографии». Греческие, римские и византийские исследования 45.1 (2010): 35–57. Распечатать.
  12. ^ icitsuser (22 января 2017 г.). «Древняя история криптографии». ICITS. Получено 7 апреля 2019.
  13. ^ Кан, Дэвид (1996). Взломщики кодов: всеобъемлющая история секретной связи с древнейшими временами в Интернете. Саймон и Шустер. ISBN  9781439103555.
  14. ^ а б Бромелинг, Лайл Д. (1 ноября 2011 г.). «Отчет о ранних статистических выводах в арабской криптологии». Американский статистик. 65 (4): 255–257. Дои:10.1198 / tas.2011.10191. S2CID  123537702.
  15. ^ Лиман, Оливер (16 июля 2015 г.). Биографическая энциклопедия исламской философии. Bloomsbury Publishing. ISBN  9781472569455.
  16. ^ Аль-Джубури, И. М. Н. (19 марта 2018 г.). История исламской философии: с точки зрения греческой философии и ранней истории ислама. Авторы на Line Ltd. ISBN  9780755210114.
  17. ^ Саймон Сингх, Кодовая книга, стр. 14–20
  18. ^ «Аль-Кинди, криптография, расшифровка кода и шифры». Получено 12 января 2007.
  19. ^ Ибрагим А. Аль-Кади (Апрель 1992 г.), "Истоки криптологии: вклад арабов", Криптология 16 (2): 97–126
  20. ^ Зальцман, Бенджамин А. "Ut hkskdkxt: Раннесредневековая криптография, текстовые ошибки и Scribal Agency (Speculum, готовится к печати)". Зеркало.
  21. ^ Дэвид Саламон Кодирование для данных и компьютерных коммуникаций. Спрингер, 2006.
  22. ^ Роберт Гук (1705). Посмертные произведения Роберта Гука. Ричард Уоллер, Лондон. п. 203.
  23. ^ Лунд, Пол (2009). Книга кодов. Беркли и Лос-Анджелес, Калифорния: Калифорнийский университет Press. стр.106–107. ISBN  9780520260139.
  24. ^ Сильверман, Кеннет. Эдгар А. По: Скорбное и нескончаемое воспоминание. Нью-Йорк: Harper Perennial, 1991. стр. 152-3
  25. ^ «Инфографика - История шифрования». www.egress.com. Получено 19 марта 2018.
  26. ^ Фентон, Бен (22 июня 2006 г.). «Энигма и британский кодекс чести». Дейли Телеграф. Лондон.
  27. ^ Фессенден, Марисса (27 января 2015 г.). «Женщины были ключом к взлому кодов Второй мировой войны в Блетчли-парке». Смитсоновский журнал. Получено 10 мая 2019. На пике популярности в Блетчли-парке работало более 10 000 человек, из которых более двух третей составляли женщины.
  28. ^ а б Манди, Лиза (2017). Code Girls: Нерассказанная история американских женщин, нарушивших кодекс Второй мировой войны. Нью-Йорк, Бостон: Hachette Books. ISBN  978-0-316-35253-6.
  29. ^ Фрумкин, Дэн (8 мая 1998 г.). «Расшифровка шифрования». Вашингтон Пост. Получено 18 сентября 2013.
  30. ^ Ли, Том (август 2000). «Криптография и новая экономика» (PDF). Промышленный физик. 6 (4): 31. Архивировано с оригинал (PDF) 16 февраля 2012 г.. Получено 18 сентября 2013.
  31. ^ Коммуникационная теория секретных систем, Клод Шеннон, 1949 г.
  32. ^ а б c Берлекамп, Элвин; Соломон В. Голомб; Томас М. Кавер; Роберт Г. Галлагер; Джеймс Л. Мэсси; Эндрю Дж. Витерби (январь 2002 г.). «Клод Элвуд Шеннон (1916–2001)» (PDF). Уведомления AMS. 49 (1): 8–16. Получено 18 сентября 2013.
  33. ^ Фонд электронных границ, Взлом DES, О'Рейли, 1998.
  34. ^ Шон Харрис. «Криптография» (PDF). Архивировано из оригинал (PDF) 15 сентября 2012 г.. Получено 18 сентября 2013.
  35. ^ Грэ, Джозеф Стерлинг. «Хеш-функции в криптографии» (PDF). Получено 18 сентября 2013.

внешняя ссылка