Криптосистем основанные на эллиптических кривых. Содержание реферат
 Скачать 1.29 Mb.
|
1.1. Основные понятияВозможно ещё наши предки, жившие в каменном веке, оставляли друг другу краткие послания с помощью камней, прутьев или линий на земле. Такие послания указывали более короткий путь к водопою или поляне, где росли растения, пригодные в пищу. К шифровкам они отношения не имеют и появились в связи с бедностью первобытного языка. Индейские племена, сохранившиеся до наших дней, используют условные знаки. Цель таких знаков - передать информацию от одного члена племени к другому. Индейцы племени сиу используют для условных знаков рисуночное письмо. Ученые называют такие схематичные рисунки пиктограммами. Вот так выглядит на языке сиу костёр, спрятанное продовольствие, враг (животное - медведь или волк), далеко (два дня пути), далеко (десять дней пути). Конечно, можно придумать свои знаки на основе индейских пиктограмм и договориться об их использовании, например, перед туристическим походом для обозначения схемы маршрута - изменений направления, развилок, привалов. Знаки легко начертить заостренной палкой на земле или мелом на камне (рисунок 1.1). Рисунок 1.1  Все привыкли к словам "шифр" и "код", но мало кто задумывался, что на самом деле они означают. Все шифры строятся по похожим законам. Одна буква или цифра заменяет только одну букву или цифру. "1" может означать "А" или "Я", но никак не слог "НА" или целое слово "Англия". Шифры бывают простые и сложные. В простых шифрах один знак всегда заменяет одну и ту же букву или цифру. Например, "О" всегда заменяет "К", а "9" - "Ф". Коды устроены по-другому. Буква, знак, цифра, слог или целое слово могут заменять букву, знак, слог, слово, группу слов или даже целую мысль. Например, группа цифр "98765" означает "война с Германией", а слог "КА" - "война". Но каждый раз, когда в послании будет использоваться эта группа цифр или слово, они будут означать одно и то же. Теперь кодированием стали называть изменение исходного текста, цель которого - подготовка к передаче его с помощью каких-то технических устройств. Современные примеры кодирования нам очень хорошо известны, это телеграф или цифровая телефонная связь (в частности, все мобильные телефоны). Способ кодирования не является секретом, наоборот, он должен быть известен всем, кто использует данный способ связи. Наверное, одна из самых старых систем кодировки - флажковая азбука, которая издавна применялась на флоте. Криптография - тайная система изменения письма с целью сделать текст непонятным для непосвященных лиц. Начало криптографии совпадает с началом письменности, так как написанный текст мог понять только умеющий читать. Существовали три основных способа защиты информации. Один из них предполагал защиту силовыми методами: охрана документа - носителя информации - физическими лицами, передача его специальным курьером и т.д. Второй способ получил название "стеганография" - латино-греческое сочетание слов, означающих в совокупности "тайнопись". Он заключался в сокрытии самого факта наличия информации. В данном случае использовались так называемые симпатические чернила. При соответствующем "проявлении" бумаги текст становится видимым. Один из примеров сокрытия информации приведен в трудах древнегреческого историка Геродота. На голове раба, которая брилась наголо, записывалось нужное сообщение. И когда волосы его достаточно отрастали, раба отправляли к адресату, который снова брил его голову и считывал полученное сообщение. Третий способ защиты информации заключался в преобразовании смыслового текста в некий набор хаотических знаков (или букв алфавита). Получатель данного донесения имел возможность преобразовать его в то же самое осмысленное сообщение, если обладал ключом к его построению. Этот способ защиты информации называется криптографическим. Криптография - слово греческое и в переводе означает "тайнопись". По утверждению ряда специалистов криптография по возрасту - ровесник египетских пирамид. В документах древних цивилизаций - Индии, Египта, Месопотамии - есть сведения о системах и способах составления шифрованных писем. Историческим примером шифра замены является шифр Цезаря (1 век до н.э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е,.,; затем под ним выписывался тот же алфавит, но со сдвигом на 3 буквы влево (таблица 1.1): Таблица 1.1
При зашифровке буква А заменялась буквой Г Б заменялась на Д, Б-Ей так далее. Так, например, слово "РИМ" превращалось в слово "УЛП". Получатель сообщения "УЛП" искал эти буквы в нижней строке и по буквам над ними восстанавливал исходное слово "РИМ". Ключом в шифре Цезаря является величина сдвига 3-й нижней строки алфавита. Преемник Юлия Цезаря - Цезарь Август - использовал тот же шифр, но с ключом - сдвиг 4. Слово "РИМ" он в этом случае зашифровал бы в буквосочетание "ФМР". В художественной литературе классическим примером шифра замены является известный шифр "Пляшущие человечки" (К. Дойля). В нем буквы текста заменялись на символические фигурки людей. Ключом такого шифра являлись позы человечков,, заменяющих буквы. Примерно в конце первого тысячелетия арабские ученые придумали метод, который позволял довольно быстро и легко взламывать такие шифры при условии, что имеется довольно большой кусок текста (хотя бы 2-3 сотни знаков). Дело в том, что при тщательном изучении богословами священной книги мусульман - Корана - выяснилось, что некоторые буквы алфавита появляются в текстах очень часто, а другие, наоборот, очень редко. Более внимательные наблюдения показали, что частота появления одной и той же буквы в различных текстах почти постоянна. Это значит, что если взять несколько не очень коротких текстов, для каждого из них подсчитать, сколько раз в нем встречается интересующая нас буква, и разделить это число на общее число знаков в тексте, то все полученные значения окажутся очень близкими между собой. В таблице изображена частота букв русского алфавита. Обратим внимание на то, что в ней учитываются буквы и пробел, но не учитываются знаки препинания. Как видно, в русских текстах чаще всего встречается буква "о", а реже всего буквы "ф" и "э", их частоты отличаются в 45 раз (таблица 1.2). Для расшифровки текста предлагается поступать так: - сначала для каждого символа шифрованного текста подсчитать его частоту; - затем расположить эти символы в порядке убывания частоты: сначала самый частый, потом следующий и так далее; - расположить буквы алфавита данного языка тоже в порядке убывания частоты; - заменить в шифрованном тексте первую букву первого списка на первую букву второго списка и так далее. Таблица 1.2.
Рассмотрим на примере применение данного метода. Возьмем текст, зашифрованный с помощью шифра замены, представленного выше (для простоты рассуждений сохраним пробелы между словами). Ю еивюкгзя ймнм фдтрфзо гмжлядкфджгъц, Я гмвл гм тижийкмк гиждргию кждеи, Фдтгмййю фъчм дг обифдэ гмедяджгдц Ибмяйигржзцйядод йкдбеи Гмк, фмйы ю гм лвжл - рлчи ф тифмкгдц бзжм Фмйы взж емжмазфмк з кбмгыю лнмазк, З йбифмг нлрл ю рдядбы ф едрблггдв взжм Азф нлрмк сдкы дрзг еззк. Для начала подсчитаем общее количество знаков в тексте (напомним, что учитываются только буквы и пробелы между словами, но не знаки препинания) - 270. Затем составим таблицу частоты знаков в зашифрованном тексте (таблица 1.3). После этого начнем заменять буквы из зашифрованного текста сходными с ними по частоте из русского алфавита, пользуясь таблицами 1 и 2. Далее, если мы видим две буквы со схожими частотами, то будем руководствоваться правилами русского языка и просто благозвучием, например, нет слов ю, ф и т.д. Буквы "Ь" и "Д" из нашего текста имеют частоты близкие к буквам "Е" и "О". Таким образом, букву "М" следует заменить на букву "Е", нежели на "О", в таком случае "Д" меняем на "О", получим: Ю еивюкгзя йене фотрфзо гежляокфожгъц, Я гевл ге тижийкек гижоргию кжоеи, Фотгеййю фъчеог обифоэ гееояожгоц Ибеяйигржзцйяооо йкобеи Гек, фейы ю ге лвжл - рлчи ф тифекгоц бзже З йбифег нлрл ю рояобы ф еорблггов взже Азф нлрек сокы орзг еззк. Таблица 1.3
После замены можно увидеть, что в тексте часто повторяется слово "ге", что может означать только "не", следовательно, "г" меняется на "н". Далее заметим, что буквой "з" обозначается одно слово, перед которым в одном случае ставится запятая, а в другом - нет. Эта буква к тому же стоит на стыке согласных, а значит - "з" обозначает гласную букву. Предположим, что это буква "и", снова поменяем текст: Ю еивюкния йене фотрфио нежляокфожнъц, Я невл не тижийкек нижорнию кжоеи, Фотнеййю фъчеог обифоэ нееояожгоц Ибеяйинржицйяооо йкобеи Нек, фейы ю не лвжл - рлчи ф тифекноц биже Фейы виж еежеазфек и кбеныю лнеаик, И йбифен нлрл ю рояобы ф еорблннов взже Азф нлрек сокы орин еиик. Затем мы видим, что буква "к" стоит после букв "и" и "е" в конце слова, что характерно для глаголов. Сверяясь с таблицей частотности, мы видим две согласные с похожей частотой - это "т" и "с". Кроме того, нельзя не заметить, что в тексте присутствует слово "нек", что естественно соответствует слову "нет". Таким образом "к" в данном шифре означает "т". Далее по таблице частотности у нас следует буква "ф". Она обозначает слово из одной буквы, которое не может быть ничем другим, кроме как предлогом: в или к. Но так как у буквы "в" частота встречаемости в русском алфавите больше, то значит в шифровке "ф" меняем на "т". Снова изменим текст. Ю еивютния йеневотрвио нежляотвожнъц, Я невл не тижийтетнижорнию тжоеи, Вотнеййю въчеог обивоэ нееояожгоц Ибеяйинржицйяооо йтобеи Нет, вейы ю не лвжл - рлчи в тиветноц биже Вейы виж еежеазвети тбеныю лнеаит, И йбивен нлрл ю рояобы в еорблннов взже Азв нлрек соты орин еиит. Теперь рассмотрим букву "и". Судя по ее расположению в словах, она означает гласную букву, а из гласных самая большая частота из нерассмотренных нами у буквы "а". Продолжим продвигаться по таблице частотности. Буква "ж" по таблице частотности соответствует букве "р", а букве "й" - "с". Кроме того, в тексте еще встречаются слова из одной буквы, которые являются предлогами. Одна из них - "я", которая как раз по частотности соответствует букве "к". Теперь снова рассмотрим текст. Ю еавютния сеневотрвио нерляотворнъц, Кневл не тарастетнарорнаю троеа, Вотнессю въчеон обавоэ нееокоргоц Абексинррицскооостобеи Нет, весы ю не лврл - рлчи в тиветноц бире Весы вир еереазвети тбеныю лнеаит, Исбавен нлрл ю рокобы в еорблннов вире Аив нлрек соты орин еиит. Теперь мы видим, что слово "весы" соответствует слову "весь", а "соть" - "хоть". Заменим "ы" на "ь", а "с" на "х". Еще можно заметить, что "ю" составляет слово из одной буквы, из оставшихся предлогов и местоимений это может быть только "я". Буква "л" соответствует "у". Судя по расположению букв в словах "б" соответствует "л". Снова преобразуем шифровку. Я еавятниксеневотрвио нерукотворнъц, Кневл не тарастетнарорнаятроеа, Вотнессю въчеон олавоэ нееокоргоц Алексинррицскооостолеи Нет, весьянеуврл - ручи в тиветноц лире Весь вир еереазвети тленью унеаит, Иславен нурл я рокольв еорллннов вире Аив нурек хотьорин еиит. После преобразований стало ясно, что "троеа" - "тропа", "павятник" - "памятник", "тарастет" - "зарастет", "нерукотворнъц" - "нерукотворный", "выче" - "выше", "руша" - "душа", "нуду" - "буду", "воздвио" - "воздвиг", "аив" - "жив", а "главоэ" - "главою". После проделанных операций мы видим, что перед нами отрывок из стихотворения А.С. Пушкина "Памятник": Япамятниксебевоздвигнерукотворный, Кнемунезарастетнароднаятропа, Вознессявышеонглавоюнепокорной Александрийскогостолпа Нет, весьянеумру - душавзаветнойлире Весьмирпереживети тленьяубежит, Иславенбудуядокольвподлунноммире Жив будетхотьодинпиит. |