close

Вход

Забыли?

вход по аккаунту

?

Доклад на тему: «История криптографии»

код для вставкиСкачать
Доклад на тему:
«История криптографии»
Выполнила: Дубасова Екатерина
Преподаватель: Брагилевский В.Н.
История криптографии насчитывает не одно тысячелетие. Уже в исторических
документах древних цивилизаций – Индии, Китае, Месопотамии, Египте – имеются
сведения о системах и способах составления шифровального письма. Видимо, первые
системы шифрования появились одновременно с письменностью в четвертом
тысячелетии. В то время в городе Менет-Хуфу на берегу Нила были нарисованы
иероглифы, рассказывающие историю одного господина. Это первая документально
зафиксированная криптограмма.
Эта система не была тайнописью в том смысле, как ее понимают в современном мире.
Дошедшая до наших дней надпись, вырезанная примерно в 1900 году до н. э. на гробнице
знатного человека по имени Хнумхотеп, лишь в отдельных местах состоит из необычных
иероглифических символов вместо более привычных иероглифов. Но это было сделано не
для затруднения чтения текста, а скорее, чтобы придать ему большую важность.
Далее криптография начинает применяться и в государственной деятельности. В
Спарте в V-IV вв. до н.э. использовалось одно из первых шифровальных приспособлений
– Сцитала. Это жезл цилиндрической формы, на который наматывалась лента пергамента.
Вдоль оси цилиндра на пергамент построчно записывался текст, предназначенный для
передачи. После записи текста лента сматывалась с жезла и передавалась адресату,
который имел такую же сциталу. Метод вскрытия такого шифра приписывается
Аристотелю. Предлагалось заточить на конус длинный брус и, обернув вокруг него ленту,
начать сдвигать ее по конусу от малого диаметра до самого большого. В том месте, где
диаметр конуса совпадал с диаметром сциталы, буквы текста сочетались в слоги и слова.
После этого оставалось лишь изготовить цилиндр нужного диаметра.
В I в. до н.э. Цезарь использовал придуманный им шифр. Алфавит открытого текста,
циклически сдвигался на 3 буквы влево.
В мрачные годы средневековья практика шифрования хранилась в строжайшей тайне.
В годы крестовых походов шифровальщики, служившие у Папы Римского, после года
работы подлежали физическому уничтожению.
В XIV веке появилась книга о системах тайнописи, в которой использовались шифры
многозначной замены.
В 1466 г. Леон Альберти написал труд о шифрах.
1518г. – первая печатная книга по криптографии. Автор – аббат Иоганнес Тритемий.
Оба труда описывали шифр такой, что с каждой буквой задействовался новый алфавит.
Одним из усовершенствований многоалфавитных систем является использование в
качестве ключа текста самого сообщения или же шифрованного текста. Эта идея
принадлежит Джероламо Кардано и Блезу де Виженеру.
Самоключ Виженера был незаслуженно забыт на долгое время, а под шифром
Виженера до сих пор понимают самый простой вариант с коротким ключевым словом и с
таблицей, состоящей из обычных алфавитов.
Последующие шифры с некоторыми модификациями были очень похожи на шифр
Виженера и 17,18 не дали новых идей в криптографии. Много новых идей принес 19-й
век. Примерно в 1800 году Джефферсон – первый государственный секретарь США,
ставший позже третьим президентом, создал дисковый шифр.
Дисковый шифратор Джефферсона состоял из 25-36 деревянных дисков одинакового
размера, насаженных на общую ось. На одном конце оси имелась неподвижная головка,
на другом – резьба и гайка, с помощью которой все диски фиксировались в любом
нужном угловом положении. Имелась также прямолинейная рейка, способная вращаться
на оси и позволяющая выделить строку букв на дисках, параллельную оси. На боковой
поверхности каждого диска, разделенной на 26 равных частей, наносились буквы
смешанных английских алфавитов. Для зашифрования части сообщения(длина которой
равнялась числу дисков на оси) под рейку, находящуюся в фиксированном угловом
положении, подводилась первая буква сообщения, найденная на первом диске, затем –
вторая буква сообщения, найденная на втором диске, и т.д., так, чтобы все подобранные
буквы оказались в одной строке. Положение дисков фиксировалось гайкой, после чего
рейка подводилась под любую другую строку цилиндра, буквы которой составляли
шифрованный текст. При расшифровании буквы шифрованного текста, набранные на
последовательных дисках, подводились аналогичным образом под рейку, положение
дисков фиксировалось гайкой, после чего с помощью рейки просматривались
образовавшиеся строки цилиндра, среди которых нетрудно было найти открытое
сообщение.
Кажущаяся некорректность, связанная с возможностью неоднозначности
расшифрования, устраняется достаточно большим числом используемых дисков. Это
замечание относится, конечно, лишь к осмысленным текстам. При зашифровании
неосмысленных текстов требовалась дополнительная информация о величине сдвига
рейки, без чего однозначное расшифрование невозможно.
Такая шифросистема имеет огромное количество ключевых элементов. К ним
относятся: расположение букв алфавита на дисках, расстановка дисков на оси, выбор
набора дисков из имеющегося запаса. Дисковый шифр можно отнести по типу к
многоалфавитной замене. Его особенностью является поблочный характер зашифрования,
при котором каждый участок текста(блок) шифруется независимо от других. Позже такие
шифры стали называться блочными шифрами. Джефферсон отложил этот шифр в архив.
Он был обнаружен в его бумагах в библиотеке конгресса лишь в 1922г., когда по иронии
судьбы в армии США начали применять почти аналогичную систему, изобретенную
независимо от Джефферсона. В 1817 году Дессиус Уодсворт сконструировал
шифровальное устройство, в котором алфавиты открытого и зашифрованного текста были
разных длин.
Во второй половине 19 века появился весьма устойчивый способ усложнения числовых
кодов – гаммирование. Он заключался в перешифровании закодированного сообщения с
помощью некоторого ключевого числа, которое и называлось гаммой. Шифрование с
помощью гаммы состояло в сложении всех кодированных групп сообщения с одним и тем
же ключевым числом. Эту операцию стали называть наложением гаммы. Обратную
операцию – снятием гаммы.
В то время голландец Керкгоффс написал книгу «Военная криптография». В ней
сформулированы 6 конкретных требований к шифрам. Одно из них состоит в том, что
надежность шифра определяется лишь секретностью ключа.
В годы обеих войн криптография довольно бурно развивалась. Значительный успех
связан с американцем Г. Вернамом. В 1917 году он, будучи сотрудником телеграфной
компании, предложил идею автоматического шифрования телеграфных сообщений. Речь
шла о своеобразном наложении гаммы на знаки алфавита, представленные в соответствии
с телетайпным кодом Бодо пятизначными «импульсными комбинациями». Например,
буква а представлялась комбинацией (+ + - - -). На бумажной ленте, используемой при
работе телетайпа, знаку «+» отвечало наличие отверстия, а знаку «-» - его отсутствие. При
считывании с ленты металлические щупы проходили через отверстия, замыкали
электрическую цепь и тем самым посылали в линию импульс тока. Вернам предложил
электромеханически покоординатно складывать «импульсы» знаков открытого текста с
«импульсами» гаммы, предварительно нанесенными на ленту. Сложение проводилось по
модулю 2. Вернам сконструировал и устройство для такого сложения. Процесс
шифрования оказывался полностью автоматизированным, в предложенной схеме
исключался шифровальщик.
Еще одной известной машиной для шифрования была «Энигма». Как и другие
роторные машины, Энигма состояла из комбинации механических и электрических
систем. Механическая часть включала в себя клавиатуру, набор вращающихся дисков
(роторов), которые были расположены вдоль вала и прилегали к нему, и ступенчатого
механизма, двигающего один или более роторов при каждом нажатии клавиши.
Конкретный механизм работы мог быть разным, но общий принцип был таков: при
каждом нажатии клавиши самый правый ротор сдвигается на одну позицию, а при
определённых условиях сдвигаются и другие роторы. Движение роторов приводит к
различным криптографическим преобразованиям при каждом следующем нажатии
клавиши на клавиатуре.
Механические части двигались, образуя меняющийся электрический контур, то есть,
фактически, шифрование букв осуществлялось электрически. При нажатии клавиш контур
замыкался, ток проходил через различные компоненты и в итоге включал одну из
множества лампочек, отображавшую выводимую букву. Например, при шифровке
сообщения, начинающегося с ANX…, оператор вначале нажимал кнопку A, и загоралась
лампочка Z, то есть Z становилась первой буквой криптограммы. Оператор продолжал
шифрование N таким же образом, и так далее.
Механизм состоял из 26 лампочек, клавиш, разъёмов и электрических схем внутри
роторов. Ток шёл из батареи через переключатель в коммутационную панель.
Коммутационная панель позволяла перекоммутировать соединения между клавиатурой и
неподвижным входным колесом. Далее ток проходил через разъём, входное колесо и
схему соединений трёх (в армейской модели) или четырёх (в военно-морской модели)
роторов и входил в рефлектор. Рефлектор возвращал ток обратно, через роторы и входное
колесо, но уже по другому пути, далее через разъём «S», соединённый с разъёмом «D»,
через другой переключатель, и зажигалась лампочка. Таким образом, постоянное
изменение электрической цепи, через которую шёл ток, вследствие вращения роторов
позволяло реализовать многоалфавитный шифр подстановки, что давало высокую
устойчивость шифра для того времени.
Хотя с точки зрения криптографии шифр Энигмы был слаб, на практике только
сочетание этого фактора с другими, такими как ошибки операторов, процедурные изъяны,
предположения о тексте сообщений (например при передаче метеосводок) и захваты
экземпляров Энигмы и шифровальных книг, позволило взломщикам разгадывать шифры и
читать сообщения.
Именно Энигма вермахта (Wehrmacht Enigma) — немецкая военная модель — чаще
всего является предметом дискуссий. Эта машина получила дурную славу, потому что
криптоаналитики Антигитлеровской коалиции смогли расшифровать большое количество
сообщений, зашифрованных с ее помощью. Специально для этих целей была создана
машина с кодовым названием Bombe, оказавшая значительное содействие
Антигитлеровской коалиции в войне. Вся информация, полученная криптоанализом с её
помощью, имела кодовое название ULTRA.
Прототип «Бомбы» был создан польскими математиками накануне второй мировой войны
для министерства обороны Польши. На основе этой разработки и при непосредственной
поддержке её создателей в англии был сконструирован более "продвинутый " агрегат.
Теоретическую часть работы выполнил Алан Матисон Тьюринг его работы по
криптографическому анализу алгоритма, реализованного в шифровальной машине
«Энигма» основывался на более раннем криптоанализе предыдущих версий этой машины,
которые были выполнены в 1938 году польским криптоаналитиком Марианом Реевским.
Принцип работы разработанного Тьюрингом дешифратора состоял в переборе возможных
вариантов ключа шифра и попыток расшифровки текста, если была известна структура
расшифровываемого сообщения или часть открытого текста.
Выдающиеся результаты в применении математических методов криптографии
принадлежат Клоду Шеннону. Он был первым, кто подошел к криптографии с подлинно
научной точки зрения. Центральной в его работах является концепция избыточной
информации, содержащейся в текстовых сообщениях. Избыточность означает, что в
сообщении содержится больше символов, чем в действительности требуется для передачи
содержащейся в ней информации. Например всего лишь десять английских слов – the, of
and, to, a, in, that, it, is, i – составляют более 25% любого(английского текста). Легко
понять, что их можно изъять из текста без потери информации, так как их легко
восстановить по контексту. Фактически Шеннон показал, что успех криптоанализа
определяется тем, насколько избыточность, имеющаяся в сообщении, «переносится» в
шифрованный текст. Если шифрование «стирает» избыточность, то восстановить текст
сообщения по криптограмме становится принципиально невозможно.
Кроме того Шеннона исчерпывающее исследовал понятия абсолютной секретности
систем - он доказал существование абсолютно стойких, невскрываемых шифров, и
сформулировал условия, необходимые для этого. Кроме того, Шеннон определил
основные принципы, которым должны соответствовать надежные шифры. Именно он ввел
в рассмотрение понятия перемешивания и рассеивания, и предложил строить стойкие
криптографические системы из относительно несложных преобразований.
Так же он говорил о том, что две системы с одинаковым объемом ключа могут быть
обе разрешимы единственным образом, когда перехвачено N букв, но они могут
значительно отличаться по количеству времени и усилий, затрачиваемых для получения
решения. На основе анализа основных недостатков секретных систем предлагал методы
построения систем, для решения которых требуются большие затраты времени и сил.
Рассматривал проблема несовместимости различных желательных качеств секретных
систем. Кроме того, он посчитал количество информации, которого будет достаточно для
взлома шифра.
Развитие компьютерной техники и электроники после Второй мировой сделало
возможным использование более сложных шифров. Более того, компьютеры позволили
шифровать любые данные, которые представимы в цифровом бинарном виде, в отличие
от классических шифров, которые предназначались только для шифрования написанных
текстов. Это привело к непригодности лингвистических методов криптоанализа для
большинства случаев, так как многие компьютерные шифры характеризуются работой с
последовательностями битов (возможно сгруппированных в блоки), в то время как
классические и механические схемы обычно манипулировали традиционными знаками
(буквами и цифрами). С другой стороны, компьютеры помогают криптоанализу, что
может компенсировать усложнение шифров. Однако, несмотря на это, хорошие
современные шифры идут впереди криптоанализа, обычно использование качественного
шифра очень эффективно (то есть осуществляется быстро и с минимальными ресурсами),
в то время как взлом требует усилий на много порядков больше как по времени, так и по
ресурсам, делая криптоанализ настолько неэффективным и непрактичным, что можно
считать его невозможным за разумное время или с разумными ресурсами.
Согласно принципу Керкгоффса, стойкость алгоритма определяется его ключом. То
есть взломщик знает сам алгоритм, может с помощью него анализировать открытый текст
и соответствующий ему зашифрованный. Ему неизвестен лишь ключ. То есть рассмотрим
алгоритм, который нельзя взломать без знания ключа. Единственным способом получить
открытый текст в этом случае – просто перебрать все возможные ключи. Как же защитить
информацию от этого способа взлома? Для этого существует понятие генераторов
случайных и псевдослучайных последовательностей. В качестве примера рассмотрим
алгоритм, который почти не используется на практике из-за ряда причин, но который в
данной ситуации является простым и наглядным – одноразовый блокнот. Одноразовый
блокнот – не повторяющийся случайный набор символов ключа. Каждый символ ключа в
блокноте складывается с одним символом открытого текста. В результате получается
шифртекст. Длина ключа равна длине открытого текста и, соответственно, шифртекста.
После передачи сообщения отправитель уничтожает ключ, что делает и получатель после
расшифровки текста. Такой способ шифрования взлому не поддается вообще. Но это при
условии того, что ключом является случайная последовательность. Проблема заключается
в том, что фактически генератор случайных чисел не создает случайную
последовательность. С помощью компьютера невозможно создать что-либо
действительно случайное. Дональд Кнут приписал Джону фон Нейману следующие слова:
«Каждый, кто применяет арифметические для создания случайных чисел, впадает в грех».
Число состояний, в которых может находиться компьютер велико, однако, строго
ограничено, а выдаваемый результат всегда четко определяется исходными данными и
текущим состоянием компьютера. То есть, любой генератор случайных чисел,
реализованный с помощью компьютера, периодичен по определению. То есть
предсказуем. А все, что предсказуемо, не может быть случайным. Самое большее, что
можно создать с помощью компьютера – это генератор псевдослучайных
последовательностей. То есть нечто, что выглядит набором случайных чисел. В идеале
период генерируемой последовательности должен быть не меньше длины требуемой
последовательности. Кроме того при повторном запуске генератора должны получаться
разные последовательности при одинаковом входе. В качестве примера широко
распространенного генератора приведен RC4.
Потоковый шифр RC4 был создан Роном Ривестом из RSA Security в 1987 году. Хотя
официально сокращение обозначает Rivest Cipher 4, его часто считают сокращением от
Ron’s Code[2].
Шифр являлся коммерческой тайной, но в сентябре 1994 года его описание было
анонимно отправлено в рассылку Cypherpunks[3]. Вскоре описание RC4 было
опубликовано в ньюс-группе sci.crypt. Именно оттуда исходный код попал на множество
сайтов в сети Интернет. Опубликованный шифр давал те же шифротексты на выходе,
какие давал подлинный RC4. По-видимому, данный текст был получен в результате
анализа исполняемого кода. Опубликованный шифр совместим с имеющимися
продуктами, использующими RC4, а некоторые участники телеконференции, имевшие, по
их словам, доступ к исходному коду RC4, подтвердили идентичность алгоритмов при
различиях в обозначениях и структуре программы. Главными факторами,
способствовавшими широкому применению RC4, были простота его аппаратной и
программной реализации, а также высокая скорость работы алгоритма в обоих случаях.
Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция
генерирует последовательность битов, которая затем объединяется с открытым текстом
посредством суммирования по модулю два. Расшифровка заключается в регенерации
этого ключевого потока и сложении его и шифрограммы по модулю два. На выходе
получаем исходный незашифрованный текст.
Другая главная часть алгоритма — функция инициализации, которая использует ключ
переменной длины для создания начального состояния генератора ключевого потока.
unsigned char S[256];
unsigned int i, j;
/* ключевое расписание */
void rc4_init(unsigned char *key, unsigned int key_length) {
for (i = 0; i < 256; i++)
S[i] = i;
for (i = j = 0; i < 256; i++) {
unsigned char temp;
j = (j + key[i % key_length] + S[i]) & 255;
temp = S[i];
S[i] = S[j];
S[j] = temp;
}
i = j = 0;
}
/* Вывод одного псевдослучайного байта */
unsigned char rc4_output() {
unsigned char temp;
i = (i + 1) & 255;
j = (j + S[i]) & 255;
temp = S[j];
S[j] = S[i];
S[i] = temp;
return S[(temp + S[j]) & 255];
}
Генераторов существует достаточно много. Источником их энтропии могут быть шум
звуковой карты, счетчик тактов процессора, размер жесткого диска. Выбор должен
зависеть от необходимой секретности, скорости и т.п.
Об этом можно спокойно рассуждать сейчас, когда действительно есть из чего
выбирать. Но в начале 70-х все было совсем по-другому. Гражданские исследования в
области криптографии были крайне скудны. В этой области почти не публиковались
исследовательские работы. Большинство людей знали, что в своих коммуникациях
военные используют специальную аппаратуру кодирования, но мало кто разбирался в
криптографии как в науке. Заметными знаниями обладало АНБ США, но оно не
признавало публично даже факт собственного существования. Покупатели не знают, что
они покупают. Многие мелкие компании изготавливали и продавали криптографическое
оборудование преимущественно заокеанским правительствам. Оборудование разных
производителей отличалось друг от друга и не могло взаимодействовать. Никто не знал,
действительно ли какое-либо из этих устройств обеспечивает защиту, не существовало
независимой организации, которая могла бы сертифицировать надежность.
В 1972 году Национальное бюро стандартов инициировало программу защиты каналов
связи и компьютерных данных. Одной из задач этой программы стояла разработка
единого, стандартного криптографического алгоритма. Этот алгоритм можно было бы
тестировать и сертифицировать, а реализующие его криптографические устройства могли
бы взаимодействовать друг с другом. К тому же алгоритм мог бы быть относительно
недорогим и доступным. 15 мая 1973 года, после консультации с АНБ (Агентством
национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит
строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех
требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer,
представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он
был основан на более раннем алгоритме Хорста Фейстеля. 17 марта 1975 года
предложенный алгоритм DES был издан в Федеральном Регистре. В следующем году
было проведено 2 открытых симпозиума по обсуждению этого стандарта, где подверглись
жёсткой критике изменения, внесённые АНБ в алгоритм: уменьшение первоначальной
длины ключа и S-блоки (блоки подстановки), критерии проектирования которых не
раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы
АНБ могло легко просматривать зашифрованные сообщения. После чего сенатом США
была проведена проверка действий АНБ, результатом которой стало заявление,
опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ
убедило IBM, что уменьшенной длины ключа более чем достаточно для всех
коммерческих приложений, использующих DES, косвенно помогало в разработке Sперестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению,
алгоритмом шифрования и был лишён статистической или математической слабости.
Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма.
23 ноября 1976 года стандарт DES был утвержден в качестве федерального стандарта и
разрешен к использованию во всех несекретных правительственных каналах связи.
Официальное описание стандарта «Data Encryption Standard» было опубликовано 15
января 1977 года и шесть месяцев спустя стандарт вступил в действие. В 1981 году
появилось руководство по реализации и использованию стандарта шифрования данных.
Публикация стандарта являла беспрецедентный акт. Никогда ранее не публиковались
алгоритмы, оцененные агентством АНБ. Возможно, эта публикация была следствием
недопонимания между АНБ и НБС. АНБ полагало, что DES будет реализовываться
только аппаратно. Стандарт требовал именно аппаратную реализацию, но НБС
опубликовало информацию, достаточную для программной реализации DES.
Неофициально АНБ охарактеризовало DES как одну из своих самых крупных ошибок.
Если бы АНБ предполагало, что опубликованные подробности позволят писать
программное обеспечение, оно никогда не согласилось бы на это. Для оживления
криптоанализа DES сделал очень много. Теперь исследователи получили доступ к
алгоритму, который АНБ объявило надежным. Не случайно следующий
правительственный стандартный алгоритм, Skipjack, был засекречен.
Алгоритм DES является блочным симметричным. Т.е. для зашифрования и
расшифрования используется один и тот же ключ. До 1976 года все алгоритмы были
именно такими. Поворотным пунктом в истории криптографии стала статья Уитфилда
Диффи и Мартина Хеллмана «Новые направления в криптографии».
Уитфилд Диффи родился 5 июня 1944 г. Получил степень бакалавра наук в математике
из Массачусетского Технологического Института в 1965 году. В 1991 он присоединился к
лаборатории Sun Microsystems (в Menlo Park, California) в качестве выдающегося
инженера, преимущественно работающий в области криптографии с открытым ключом.
В 1992 он был получил докторскую степень технических наук. Он также является
основателем Marconi Foundation и Isaac Newton Institute. В Июле 2008, он также был
награжден докторской степенью в Лондонском университете.
Мартин Хеллман родился 2 октября 1945 г. Получил степень бакалавра в НьюЙоркском университете (1966), степень магистра (1967) и доктора философии (1969) в
Стэнфордском университете.
После работы в Уотсоновском исследовательском центре IBM и MIT, в 1971 г.
вернулся в Стэнфорд, где преподавал и занимался исследованиями до 1996 г.
В 2002 году Мартин Хеллман писал:
«Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана.
Однако, когда система была впервые описана на бумаге Диффи и мной, это была система
распространения публичных ключей, концепция которой была выработана Меркле, и
поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркле“, если ее
связывают с именами. Я надеюсь что это небольшое изменение поможет признанию
равного вклада Меркле в изобретение криптографии с открытыми ключами.»
Ральф Меркле(родился 2 февраля 1952) является пионером в области криптографии с
открытым ключом, а совсем недавно исследователь и спикера о нанотехнологиях и
крионики.
Схема обмена ключами Диффи — Хеллмана, изобретённая в 1976 году при
сотрудничестве Уитфилда Диффи и Мартина Хеллмана, под сильным влиянием работы
Ральфа Меркле (Ralph Merkle) о системе распространения публичных ключей, стала
первым практическим методом для получения общего секретного ключа при общении
через незащищенный канал связи. Для обеспечения устойчивости, по совету Джона Гилла
(John Gill), была использована проблема дискретного логарифмирования. Годом позже
был изобретен первый алгоритм асимметричного шифрования RSA, который решил
проблему общения через незащищённый канал кардинально, уже не требуя, чтобы каждая
сторона имела копию одного и того же секретного ключа. Прежде чем рассмотреть этот
алгоритм, вспомним выдающегося математика 18 века.
Леона́рд Э́йлер (нем. Leonhard Euler; 4 (15) апреля 1707, Базель, Швейцария — 7 (18)
сентября 1783, Санкт-Петербург, Российская империя). Эйлер — автор более чем 800
работ[L 1] по математическому анализу, дифференциальной геометрии, теории чисел,
приближённым вычислениям, небесной механике, математической физике, оптике,
баллистике, кораблестроению, теории музыки и др. Многие его работы оказали
значительное влияние на развитие науки.
Почти полжизни провёл в России, где внёс существенный вклад в становление
российской науки.
В данном случае интересует функция Эйлера. Функция Эйлера φ(n), где n —
натуральное число, равна количеству натуральных чисел, не больших n и взаимно
простых с ним.
Если а и m взаимнопросты, то
, - теорема Эйлера.
Алгоритм RSA требует, чтобы вычисляемая функция Эйлера зависела не только от
простых чисел, но от больших простых чисел. Как же получить большие простые числа?
Типовой алгоритм:
1. Сгенерировать k − 1 случайных битов и составить из них k-битное число p (старший бит
равен 1).
2. Увеличить p на 1 и проверить его простоту. Повторять этот шаг до тех пор, пока не
будет найдено простое число.
Тестирование простоты:
Проверить (вероятную) простоту числа p, содержащее k битов, можно так:
Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого
небольшого предела (например, 256). Такая проверка позволяет эффективно отсечь
множество заведомо составных чисел, прежде чем проверять их посредством более
трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает
все четные числа и 54% нечетных чисел, проверка делимости p на все простые числа до
100 отсеивает 76% нечетных чисел, а проверка делимости p на все простые числа до 256
отсеивает 80% нечетных чисел.
Выполнить тест Миллера — Рабина с количеством раундов не меньше k.
Если число p не проходит хотя бы одной проверки — оно не является простым. В
противном случае с большой вероятностью (зависящей от количества раундов) число p
является простым.
Гэри Ли Миллер - профессор компьютерных наук в Университете Карнеги-Меллона,
Питсбург, США. В 2003 году он выиграл ACM Париже Kanellakis премии (с тремя
другими) для теста Миллера-Рабина простоты. Он также выступил сотрудник АСМ в 2002
году.
Миллер получил степень Кандидата в Калифорнийском университете в Беркли в 1975
году под руководством Мануэля Блюм. Диссертация на степень Доктора имела отношение
к гипотезе Римана и тестам для простоты.
Майкл Осер Рабина родился 1 сентября 1931. Является ученым в области информатики
и получателем Премия Тьюринга. В 1975 году Рабин также изобрел Миллера-Рабина
испытаний, рандомизированный алгоритм, который может определить очень быстро (но с
небольшой вероятностью ошибки), является ли число простым. Метод Рабина был
основан на предыдущей работе Гэри Миллера, который решил проблему
детерминировано с предположением, что обобщенная гипотеза Римана верна, но версия
Рабина испытания работала без такого предположения.
Как генерировать большие простые числа – знаем. Теорему Эйлера вспомнили. Теперь
можно обратиться к алгоритму RSA.
Система была названа по первым буквам фамилий её создателей.
Последняя буква этого алгоритма – Ади Шамир(Shamir). Ади Шамир родился в ТельАвиве, Израиль, в 1952. После окончания местной школы он учился в университете
Вейцмана, где он изучал математику и получил степени магистра (1975) и доктора
философии по информатике (1977). После завершения его обучения в университете
Shamir переехал в Соединенные Штаты и стал заниматься исследованиями в
Массачусетском Технологическом Институте , где он работал в Лаборатории
Информатики как преподаватель. Здесь Shamir встретил Рональда Л. Ривеста. Рональд
Линн Ривест (род. 1947, Скенектади, Нью-Йорк) получил степень бакалавра по
математике в Йельском университете в 1969 году и ученую степень доктора философии
(англ. Ph.D) по компьютерным наукам в Стенфордском университете в 1974. Является
одним из авторов учебника «Алгоритмы: построение и анализ». Шамир увидел, что одна
из задач Ривеста состояла в том, чтобы вести продвинутый курс алгоритма - область
которого у него только были элементарные знания. Шэмир взял все библиотечные книги
об алгоритмах и с большой скоростью начал изучать этот предмет подробнее. Большое
внимание Шамир уделяет работе Ривеста. Затем они вместе начинают развивать алгоритм
криптографии с открытым ключом (возможность двух человек, которые никогда не
встречались, общаться через компьютеры в безопасном режиме), основанный на работе
Витфилда Диффи и Мартина Хеллмэна. Затем пара ввела третьего исследователя,
Леонарда Адлемэна, чтобы проверить систему, которую они разработали.
Адлеман родился в Калифорнии в 1945г., вырос в Сан-Франциско, поступил в
Калифорнийский университет в Беркли, где получил степени бакалавра по математике в
1968 и доктора философии по электротехнике и компьютерным наукам в 1976.
Некоторые из начальных систем, которые они развивали, оказались очень легкими для
расшифрования, но на их 43-ьей попытке они поняли, что у них был достаточный уровень
шифрования, одобренный всеми членами группы. Система была основана на простых
числах и односторонних функциях. Описание RSA было опубликовано в августе 1977
года в журнале Scientific American. Авторы RSA поддерживали идею её активного
распространения. В свою очередь, Агентство национальной безопасности (США),
опасаясь использования этого алгоритма в негосударственных структурах, на протяжении
нескольких лет безуспешно требовало прекращения распространения системы. Ситуация
порой доходила до абсурда — например, когда программист Адам Бек(Adam Back) описал
алгоритм RSA на языке Perl, состоящий из пяти строк, правительство США запретило
распространение этой программы за пределами страны. Люди, недовольные подобным
ограничением, в знак протеста напечатали текст этой программы на своих футболках.
В 1977 году создателями RSA была зашифрована фраза «The Magic Words are
Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку
была обещана награда в 100 долларов США. Лишь в конце 1995 года удалось практически
реализовать раскрытие шифра RSA для 500-значного ключа. На протяжении полугода
более 600 добровольцев жертвовали процессорное время 1600 машин (две из которых
были факс-машинами). Координирование проходило через Интернет, и это был один из
первых подобных проектов распределённых вычислений. Полученную награду
победители пожертвовали в фонд свободного программного обеспечения.
Алгоритм выглядит следующим образом:
1. Выбираются два случайных простых числа p и q заданного размера. Чем больше, тем
лучше. Для максимальной безопасности они должны иметь равную длину.
2. Вычисляется их произведение n=pq.
3. Вычисляется значение функции Эйлера от числа n:
4. Случайным образом выбирается целое число e, взаимно простое со значением функции
.
5. Вычисляется число d, удовлетворяющее сравнению
, то есть ,
, где k любое натуральное число (0, 1, 2…).
6. Пара P = (e,n) публикуется в качестве открытого ключа.
7. Пара S = (d,n) играет роль секретного ключа.
После вычисления чисел e и d, числа p и q желательно уничтожить.
Зашифрование: c=m e mod n.
Расшифрование: m=c d mod n.
Криптография с открытым ключом используется при создании цифровых подписей.
Цифровая подпись - реквизит электронного документа, предназначенный для защиты
данного электронного документа от подделки, полученный в результате
криптографического преобразования информации с использованием закрытого ключа
электронной цифровой подписи и позволяющий идентифицировать владельца
сертификата ключа подписи, а также установить отсутствие искажения информации в
электронном документе, а также обеспечивает неотказуемость подписавшегося.
Так же важной задачей является аутентификация, то есть проверка подлинности.
Существует ряд протоколов, используемых для аутентификации. Например, протокол
Нидхема-Шредера для аутентификации с симметричным ключом: Протоколы такого типа
должны использовать посредников, из-за чего они более трудно реализуемы по сравнению
с протоколами с открытым ключом.
Одной из разновидностей криптосистем с открытым ключом является вероятностное
шифрование, разработанное Шафи Гольвассером и Сильвио Минелли. Его суть состоит в
том, чтобы алгоритм шифрования Е подчинить вероятностным моделям. Вероятностные
алгоритмы ставят в соответствие открытому тексту М не просто криптотекст С, а
некоторый элемент из множества криптотекстов СМ. При этом каждый элемент этого
множества выбирается с некоторой вероятностью. Другими словами, для любого
открытого текста М результат работы алгоритма Е будет случайной величиной. Может
показаться, что в этом случае дешифровать информацию будет невозможно. Но это
совсем не так. Для того чтобы сделать возможной дешифровку, нужно, чтобы для разных
открытых текстов М1 и М2 множества СМ1 и СМ2 не пересекались. Вероятностные
алгоритмы шифрования являются более надежными, нежели детерминированные.
Еще одним направлением криптографии является квантовая криптография.
Квантовая криптография — метод защиты коммуникаций, основанный на определенных
явлениях квантовой физики. В отличие от традиционной криптографии, которая
использует математические методы, чтобы обеспечить секретность информации,
квантовая криптография сосредоточена на физике информации, так как рассматривает
случаи, когда информация переносится с помощью объектов квантовой механики.
Процесс отправки и приема информации всегда выполняется физическими средствами,
например при помощи электронов в электрическом токе, или фотонов в линиях
волоконно-оптической связи. А подслушивание может рассматриваться, как измерение
определенных параметров физических объектов — в нашем случае, переносчиков
информации. Развитие квантовых систем криптографии в наши дни идет буквально
семимильными шагами. Причин тому немало: во-первых, квантовая криптография - это
самый защищенный из всех на практике существующих на сегодня методов защиты
данных, во-вторых, квантовые системы защиты данных в отличие от всех прочих
практически не загружают вычислительные ресурсы систем, что в условиях интенсивного
обмена данными важно, наконец в-третьих, при помощи системы квантовой
криптографии можно защитить абсолютно любые данные, в любых форматах и любых
стандартах. Однако есть у квантовых систем и недостаток - для их работы требуется
волоконно-оптическая инфраструктура, к тому же "дальнобойность" передачи квантовых
данных без использования специальных усилителей сигнала невелика. Последние
достижения – 200-250 км.
Исследователь из компании IBM решил сложную математическую задачу, которая 30
лет не давала покоя криптографам. Результатом исследования стал полноценный
механизм полностью гомоморфного шифрования, который позволяет обрабатывать
надежно зашифрованные данные, не заглядывая в их содержание. Ученый Крейг Джентри
впервые начал изучение проблемы гомоморфного шифрования, еще будучи студентом, он
проходил летнюю практику в исследовательском подразделении IBM Research. Свои
исследования он продолжил в Стэнфордском университете, где защитил кандидатскую
диссертацию. Для решения давней теоретической задачи Джентри использовал
математическую модель под названием «идеальная решетка» (ideal lattice). Эта модель
позволила анализировать зашифрованные данные без нарушения их секретности.
Список используемой литературы:
1. http://ru.wikipedia.org/wiki/Криптография
2. «Дэвид Кан «Взломщики кодов»»: Центрполиграф; М.; 2000 ISBN 5-227-00678-4
Оригинал: David Kahn, “The codebreakers”. Перевод: А. Ключевский
3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии.
Учебное пособие. М., Гелиос АРВ, 2005.
4. http://ru.wikipedia.org/wiki/Энигма
5. http://ru.wikipedia.org/wiki/Turing_Bombe
6. Брюс Шнайер «Прикладная криптография»
7. http://ru.wikipedia.org/wiki/RC4
8. http://ru.wikipedia.org/wiki/Диффи,_Уитфилд
9. http://ru.wikipedia.org/wiki/Хеллман,_Мартин
10. http://en.wikipedia.org/wiki/Ralph_Merkle
11. http://ru.wikipedia.org/wiki/Криптосистема_с_открытым_ключом
12. http://ru.wikipedia.org/wiki/Эйлер,_Леонард
13. http://ru.wikipedia.org/wiki/Функция_Эйлера
14. http://ru.wikipedia.org/wiki/Случайное_простое_число
15. http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
16. http://ru.wikipedia.org/wiki/Рабин,_Майкл_Озер
17. http://en.wikipedia.org/wiki/Gary_L._Miller_(mathematician)
18. http://ru.wikipedia.org/wiki/Шамир,_Ади
19. http://ru.wikipedia.org/wiki/Райвест,_Рональд
20. http://ru.wikipedia.org/wiki/Адлеман,_Леонард_Макс
21. http://www.facebook.com/pages/Adi-Shamir/53609805766#/pages/AdiShamir/53609805766?v=info
22. http://ru.wikipedia.org/wiki/RSA
23. http://www.ru-coding.com/algoritm_6.php
24. http://ru.wikipedia.org/wiki/Квантовая_криптография
25. http://www.ibm.com/news/ru/ru/2009/06/25/a737496p86512a82.html
Литература, использованная для подготовки 1-го слайда презентации:
26. Артун Конан Дойл «Пляшущие человечки» (верхнее изображение)
27. http://murders.ru/Zodiac.html (нижнее левое изображение)
28. http://myrt.ru/news/inter/807-zaveshhanie-olive-levassera.html (нижнее правое изобр-е)
Документ
Категория
Техника молодежи
Просмотров
87
Размер файла
328 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа