Проект учащихся: «Криптография. Шифры. Цели и задачи исследования
No notes for slide
Человек – социальное существо. Мы учимся взаимодействовать с другими, наблюдая за их реакцией на наши действия с первых дней жизни. При любом взаимодействии мы используем то, что искусствоведы называют «культурными кодами». А ведь культурные коды – самые сложные в дешифровке, здесь нет специальной программы, которая подскажет, что может значить приподнятая бровь или беспричинные, казалось бы, слёзы; нет однозначного ответа; более того, даже сам «кодирующий» может не знать, что он имел в виду под своим действием! Наука понимать окружающих – это то, что мы постигаем всю жизнь, и чем лучше развито это умение, тем, как правило, гармоничнее складывается общение с окружающими и любая деятельность, в которой нужны согласованные действия.
Изучение криптографии в обеих её ипостасях (шифровка и дешифровка) позволяет научиться находить связь между шифрованным, запутанным, непонятным посланием и смыслом, который в нём таится. Проходя исторический путь от шифра Юлия Цезаря до RSA-ключей, от розеттского камня до эсперанто, мы учимся воспринимать информацию в непривычном нам виде, разгадываем загадки, привыкаем к многовариантности. И главное – учимся понимать: как разных, непохожих на нас людей, так и математико-лингвистические механизмы, которые лежат в основе каждого, абсолютно каждого послания.
Итак, приключенческий рассказ о криптографии для детей, для всех, у кого есть дети, и для всех, кто когда-нибудь был ребёнком.
Трепещут на ветру флаги, ржут разгорячённые кони, бряцают доспехи: это Римская империя обнаружила, что в мире ещё есть кто–то, кого они не завоевали. Под командованием Гая Юлия Цезаря находится огромная армия, которой надо быстро и точно управлять.
Шпионы не дремлют, враги готовятся перехватить посланников императора, чтобы узнать все его блестящие планы. Каждый кусок пергамента, попадающий не в те руки – это вероятность проиграть сражение.
Но вот захвачен посланник, злоумышленник разворачивает записку… и ничего не понимает! «Наверное, – чешет он в затылке, – это на каком–то неизвестном языке…». Рим торжествует, его планы в безопасности.
Что же такое шифр Цезаря? Самый простой его вариант – это когда мы вместо каждой буквы ставим следующую по алфавиту: вместо «а» – «б», вместо «е» – «ж», а вместо «я» – «а». Тогда, например, «Я люблю играть» станет «А мявмя йдсбуэ». Давайте посмотрим на табличку, сверху в ней будет буква, которую шифруем, а снизу – на которую заменяем.
Алфавит как бы «сдвинут» на одну букву, правда? Поэтому этот шифр ещё называют «шифром сдвига» и говорят «используем шифр Цезаря со сдвигом 10» или «со сдвигом 18». Это значит, что надо «сдвинуть» нижний алфавит не на 1, как у нас, а, например, на 10 – тогда у нас вместо «а» будет «й», а вместо «у» – «э».
Сам Цезарь использовал этот шифр со сдвигом 3, то есть его таблица шифрования выглядела вот так:
Точнее, она бы так выглядела, если бы Цезарь жил в России. В его случае алфавит был латинский.
Такой шифр достаточно легко взломать, если вы профессиональный шпион или Шерлок Холмс. Но он до сих пор подходит для того, чтобы хранить свои маленькие секреты от посторонних глаз.
Вы и сами можете устроить свой маленький домашний заговор. Договоритесь о своём числе сдвига, и вы сможете оставлять друг другу шифрованные записки на холодильнике о сюрпризе на чей-нибудь день рождения, отправлять шифрованные сообщения и, может быть, если случится длинная разлука, даже писать друг другу тайные, кодированные письма!
Но вся история криптографии – это история борьбы между искусством зашифровывать послания и искусством их расшифровывать. Когда появляется новый способ закодировать сообщение, находятся те, кто пытаются этот код взломать.
Что такое «взломать код»? Это значит – придумать способ его разгадать, не зная ключа и смысла шифра. Шифр Цезаря тоже когда-то был взломан – так называемым «методом частотного анализа». Посмотрите на любой текст – гласных в нём гораздо больше, чем согласных, а «о» гораздо больше, чем, например, «я». Для каждого языка можно назвать самые часто и редко используемые буквы. Надо только найти, какой буквы больше всего в зашифрованном тексте. И скорее всего это будет зашифрованная «о», «е», «и» или «а» – самые часто встречающиеся буквы в русских словах. А как только ты знаешь, какой буквой обозначили, например, «а», ты знаешь, и на сколько «сдвинут» шифрованный алфавит, а значит, можешь расшифровать весь текст.
Когда разгадку кода Цезаря узнал весь мир, криптографам пришлось придумать что-нибудь помощнее. Но, как часто бывает, люди не стали изобретать что–то совсем новое, а усложнили уже имеющееся. Вместо того, чтобы шифровать все буквы по одному и тому же сдвинутому алфавиту, в тайных посланиях их стали использовать несколько. Например, первую букву шифруем по алфавиту со сдвигом 3, вторую – со сдвигом 5, третью – со сдвигом 20, четвертую – снова со сдвигом 3, пятую – со сдвигом 5, шестую – со сдвигом 20 и так далее, по кругу. Такой шифр называют полиалфавитным (то есть многоалфавитным). Попробуйте, так ваш шифр уже может разгадать только тот, кто посвящён в тайны криптографии!
Казалось бы, злоумышленники должны были запутаться и тайны должны были навсегда остаться тайнами. Но если шифр один раз был взломан, то и любые более сложные его варианты тоже будут однажды взломаны.
Давайте представим, что кто–то зашифровал послание двумя алфавитами. Первая буква – со сдвигом 5, вторая – со сдвигом 3, третья – снова 5, четвертая снова 3 – как на табличке ниже.
Мы можем разделить все зашифрованные буквы на две группы: буквы, зашифрованные со сдвигом 5 (1, 3, 5, 7, 9, 11, 13, 15, 17, 19) и буквы, зашифрованные со сдвигом 3 (2, 4, 6, 8, 10, 12, 14, 16, 18, 20). И внутри каждой группы искать, какие буквы встретились нам чаще остальных – так же, как в шифре Цезаря, только мороки побольше.
Если шифровщик использовал три алфавита, то мы разделим буквы на три группы, если пять – то на пять. А дальше снова идет в ход тот же самый частотный анализ.
Можно задать вопрос – откуда дешифраторы знали, что алфавитов три, а не, например, пять? На самом деле они не знали. И перебирали все возможные варианты. Поэтому дешифровка занимала гораздо больше времени, но все же была возможной.
В криптографии сообщение, которое надо передать, называется «открытым текстом», а зашифрованное сообщение – «шифрованным текстом». И правило, по которому текст зашифрован, называется «ключом шифра».
Незаметно подкрался XX век. Человечество всё больше надеется на машины: поезда заменяют повозки, радио появляется почти в каждом доме, и уже встали на крыло первые самолеты. И шифровку тайных планов в конце концов тоже передают машинам.
Во время Второй мировой войны было изобретено очень много машин для шифрования сообщений, но все они опирались на идею того, что полиалфавитный шифр можно ещё больше запутать. Запутать настолько, что, хотя по идее его и можно будет разгадать, на практике это ни у кого не получится. Запутать настолько, насколько это способна сделать машина, но не способен человек. Самая известная из таких шифровальных машин – «Энигма», использовавшаяся Германией.
theromanroad.files.wordpress.com
Но, пока самой главной тайной Германии была конструкция «Энигмы», самой главной тайной её противников было то, что к середине войны все страны уже «Энигму» разгадали. Если бы об этом стало известно в самой Германии, они бы начали придумывать что-то новое, но до конца войны они верили в идеальность своей шифровальной машины, а Франция, Англия, Польша, Россия читали тайные немецкие сообщения как открытую книгу.
Всё дело в том, что польский ученый Мариан Реевский однажды подумал о том, что раз придумали машину для шифровки сообщений, то можно придумать и машину для расшифровки, и первый свой образец называл «Бомба». Не из-за «взрывного» эффекта, как можно было бы подумать, а в честь вкусного, круглого пирожного.
Потом математик Алан Тьюринг построил на его основе машину, которая полностью расшифровывала код «Энигмы», и которую, между прочим, можно считать первым прародителем наших современных компьютеров.
Самый сложный код за всю Вторую мировую придумали американцы. На каждый боевой корабль США был откомандирован… индеец. Их язык был настолько непонятен и малоизучен, звучал так странно, что дешифровщики не знали, как и подступиться, и флот США безбоязненно передавал информацию на языке индейского племени чокта.
Вообще, криптография – это же не только о том, как загадать загадку, но и о том, как её разгадать. Не всегда такие загадки специально придумывают люди – иногда их подбрасывает сама история. И одной из главных загадок для криптографов долгое время была загадка древнеегипетского языка.
Никто не знал, что же значат все эти иероглифы. Что египтяне имели в виду, рисуя птиц и скарабеев. Но в один счастливый день французская армия обнаружила в Египте «Розеттский камень».
На этом камне была надпись – одна и та же, на древнегреческом, египетском буквенном (демотический текст) и египетском иероглифическом. Историки того времени хорошо знали древнегреческий, поэтому что же написано на камне они узнали быстро. Но главное, что, зная перевод, они смогли раскрыть тайны древнего египетского языка. Демотический текст был расшифрован достаточно быстро, а вот над иероглифами историки, лингвисты, математики, криптографы ломали голову долгие годы, но в конце концов всё-таки разгадали.
И это была большая победа криптографов – победа над самим временем, которое надеялось спрятать от людей их историю.
Но среди всех этих разгаданных шифров есть три особенных. Один – это метод Диффи – Хеллмана. Если маленькое сообщение зашифровать этим методом, то, чтобы его расшифровать, надо взять все компьютеры в мире и занять их этим на много-много лет. Именно он используется сегодня в Интернете.
Второй – это квантовое шифрование. Оно, правда, ещё не совсем придумано, зато, если люди сделают квантовые компьютеры такими, как о них мечтают, то такой шифр будет знать, когда его пытаются расшифровывать .
А третий особенный шифр – это «книжный шифр». Его удивительность в том, что им просто что-то зашифровать и непросто – расшифровать. Два человека выбирают одну и ту же книгу, и каждое слово из своего письма в ней ищут и заменяют тремя цифрами: номер страницы, номер строки и номер слова в строке. Это очень просто сделать, правда? А разгадать совсем не просто: откуда шпиону знать, какую книгу вы выбрали? И самое главное, компьютеры в этом деле тоже особо не помогут. Конечно, если подключить очень много умных людей и очень много мощных компьютеров, такой шифр не устоит.
Но есть главное правило безопасности. Её, этой безопасности, должно быть столько, чтобы зашифрованное послание не стоило тех огромных усилий, которые надо потратить на её расшифровку. То есть чтобы злодею – шпиону пришлось потратить столько сил, чтобы разгадать ваш код, сколько он не готов тратить на то, чтобы узнать ваше сообщение. И это правило работает всегда и везде, как в дружеских школьных переписках, так и в мире настоящих шпионских игр.
Криптография – это искусство загадывать и разгадывать загадки. Искусство сохранить тайны, и искусство их раскрывать. С криптографией мы учимся понимать друг друга и придумываем, как сохранить что-то важное для себя в безопасности. А чем лучше мы умеем и то и другое, тем спокойнее и деятельнее может быть наша жизнь.
С 1991 г. Институт криптографии, связи и информатики Академии ФСБ Российской Федерации проводит ежегодные олимпиады по криптографии и математике для школьников г. Москвы и Подмосковья. Год от года растет популярность этих олимпиад, о чем свидетельствует, например, то, что в последней из них приняло участие более пятисот школьников 9-11 классов. Олимпиады по криптографии и математике вызывают интерес у школьников необычностью своего жанра. Кроме того, призерам предоставляются льготы при поступлении в Институт.
Школьники часто спрашивают, с какой литературой по криптографии им следует познакомиться, чтобы успешно выступить на олимпиаде. Никаких специальных знаний для решения задач не требуется - в этом вы убедитесь, ознакомившись с задачами, которые приводятся в данной главе. Вместе с тем, мы не можем отрицать, что предварительное знакомство с криптографией полезно хотя бы чисто психологически, поскольку «внешний вид» задач может показаться необычным. Многие задачи нашей олимпиады - криптографические. Часть задач имеет криптографическую окраску, но их суть - математическая. Отдельные задачи - чисто математические.
При подведении итогов каждой олимпиады мы знакомим участников с общедоступными книгами по криптографии, которых в последние годы появилось достаточно много. Однако эти книги либо слишком сложны для школьников, либо поверхностны или недостаточно полны, либо малодоступны. Поэтому авторы настоящей главы поставили перед собой две основные цели: во-первых, предложить элементарное введение в криптографию, используя при этом чудесные детективные сюжеты известных произведении Ж. Верна, А. Конан Дойла, Э. По, В. Каверина, связанные с зашифрованными сообщениями; во-вторых, привести условия задач всех наших олимпиад с ответами и решениями.
1. Введение
Если вы хотите передать свое текстовое сообщение (последовательность символов некоторого алфавита) адресату так, чтобы оно осталось тайным для посторонних лиц, то у вас есть, по крайней мере, две возможности. Вы можете попытаться скрыть сам факт передачи текста, то есть прибегнуть к методам стеганографии, в арсенале которой - симпатические (невидимые) чернила, микроточки и тому подобные средства. Другая возможность заключается в попытке скрыть смысл сообщения от посторонних лиц, случайно или намеренно познакомившихся с передаваемым текстом. В этом случае вы можете прибегнуть к методам криптографии. Термин «криптография» происходит от двух греческих слов: «криптос» - тайна и «графейн» - писать, и означает тайнопись. «Тайнопись» как раз и подразумевает, что вы скрываете смысл своего сообщения.
Сообщение, которое вы хотите передать адресату, будем называть открытым сообщением. Например, в задаче 2.5 (раздел «Условия задач») одним из открытых сообщений является фраза:
КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ
Для сохранения сообщения в тайне оно преобразуется криптографическими методами и только после этого передается адресату. Преобразованное сообщение будем называть шифрованным сообщением (или зашифрованным сообщением). Другое название зашифрованного сообщения - криптограмма (или шифртекст). В задаче 2.5 зашифрованное сообщение выглядит так:
ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ
Зашифрованное сообщение не обязательно должно быть последовательностью букв, как в указанной выше задаче. Часто зашифрованное сообщение может представлять собой последовательность цифр или специальных знаков (например, «пляшущих человечков»).
Процесс преобразования открытого сообщения в шифрованное будем называть шифрованием или зашифрованием. Адресату заранее сообщается, как из шифрованного сообщения получить открытое. Этот процесс получения исходного сообщения называют дешифрованием или расшифрованием.
При выборе правила шифрования надо стремиться к тому, чтобы посторонние лица, не знающие правила расшифрования, не смогли восстановить по криптограмме открытое сообщение. В этом случае вы скроете смысл сообщения и обеспечите «тайнопись».
Для удобства дальнейшего изложения обозначим буквой А - открытое сообщение, В - шифрованное сообщение, правило шифрования, правило расшифрования. В этом случае зашифрование открытого сообщения А в шифрованное сообщение В можно записать в виде
Обратное преобразование (то есть получение открытого сообщения А путем расшифрования В) запишется в виде соотношения
Правило зашифрования не может быть произвольным. Оно должно быть таким, чтобы по шифртексту В с помощью правила расшифрования можно было однозначно восстановить открытое сообщение А. Однотипные правила зашифрования можно объединить в классы. Внутри класса правила различаются между собой по значениям некоторого параметра, которое может быть числом, таблицей и т. д. В криптографии конкретное значение такого параметра обычно называют ключом. По сути дела, ключ выбирает конкретное правило зашифрования из данного класса правил.
Зачем понадобилось вводить понятие ключа? Есть, по крайней мере, два обстоятельства, которые позволяют понять необходимость этого. Во-первых, обычно шифрование производится с использованием специальных устройств. У вас должна быть возможность изменять значение параметров устройства, чтобы зашифрованное сообщение не смогли расшифровать даже лица, имеющие точно такое же устройство, но не знающие выбранного вами значения параметра. Во-вторых, многократное использование одного и того же правила зашифрования для зашифрования открытых текстов создает предпосылки для получения открытых сообщений по шифрованным без знания правила расшифрования Поэтому необходимо своевременно менять правило зашифрования.
Используя понятие ключа, процесс зашифрования можно описать в виде соотношения
в котором а - выбранный ключ, известный отправителю и адресату.
Для каждого ключа а шифрпреобразование должно быть обратимым, то есть должно существовать обратное преобразование да, которое при выбранном ключе а однозначно определяет открытое сообщение А по шифрованному сообщению В:
Совокупность преобразований и набор ключей, которым они соответствуют, будем называть шифром.
Среди всех шифров можно выделить два больших класса: шифры перестановки и шифры замены.
Шифрами перестановки называются такие шифры, преобразования из которых приводят к изменению только порядка следования символов исходного сообщения. Примером преобразования, которое может содержаться в шифре перестановки, является следующее правило. Каждая буква исходного сообщения, стоящая в тексте на позиции с
четным номером, меняется местами с предшествующей ей буквой. В этом случае ясно, что и исходное, и шифрованное сообщение состоят из одних и тех же букв.
Шифрами замены называются такие шифры, преобразования из которых приводят к замене каждого символа открытого сообщения на другие символы - шифробозначения, причем порядок следования шифробозначений совпадает с порядком следования соответствующих им символов открытого сообщения. В качестве примера преобразования, которое может содержаться в шифре замены, приведем такое правило. Каждая буква исходного сообщения заменяется на ее порядковый номер в алфавите. В этом случае исходный буквенный текст преобразуется в числовой.
Как правило, в задачах олимпиад шифр известен, а использованный ключ - нет. Для определения исходного текста по шифрованному при неизвестном ключе возможны два подхода: первый - определить ключ и затем найти исходное сообщение расшифрованием; второй - найти исходное сообщение без определения ключа. Получение открытого сообщения по шифрованному без заранее известного ключа называется вскрытием шифра, в отличие от расшифрования - когда ключ известен. Во многих случаях вскрытие шифра возможно, что и демонстрируют победители наших олимпиад.
Под стойкостью шифра, как правило, понимается способность противостоять попыткам провести его вскрытие. При анализе шифра обычно исходят из принципа, сформулированного голландцем Огустом Керкгоффсом (1835-1903). Согласно этому принципу при вскрытии криптограммы противнику известно о шифре все, кроме используемого ключа. Одной из естественных характеристик шифра является число его возможных ключей. Ведь вскрытие шифра можно осуществлять перебором всех возможных его ключей. Мы уже говорили, что в приводимых ниже задачах олимпиад, как правило, шифр известен, но неизвестен выбранный ключ, что соответствует принципу Керкгоффса. Так, в задаче 4.4 все дело сводится к перебору 24 различных вариантов ключа, из которых только один дает читаемый текст. Поэтому многие участники олимпиады смогли восстановить сообщение на латинском языке, даже не зная этого языка.
Подчас смешивают два понятия: шифрование и кодирование. Мы уже договорились, что для шифрования надо знать шифр и секретный ключ. При кодировании нет ничего секретного, есть только определенная замена букв или слов на заранее определенные символы. Методы кодирования направлены не на то, чтобы скрыть открытое сообщение, а на то, чтобы представить его в более удобном виде для передачи по техническим средствам связи, для уменьшения длины сообщения и т.д. В принципе, кодирование, конечно же, можно рассматривать как
шифр замены, для которого «набор» возможных ключей состоит только из одного ключа (например, буква в азбуке Морзе всегда кодируется знаками и это не является секретом).
В настоящее время для защиты информации широко используются электронные шифровальные устройства. Важной характеристикой таких устройств является не только стойкость реализуемого шифра, но и высокая скорость осуществления процессов шифрования и расшифрования. Для создания и обеспечения грамотной эксплуатации такой техники широко используются достижения современной криптографии, в основе которой лежат математика, информатика, физика, электроника и другие науки.
Современная криптография бурно развивается. В ней появляются новые направления. Так, с 1976 года развивается «открытая криптография». Ее отличительной особенностью является разделение ключей для зашифрования и расшифрования. При этом ключ для зашифрования не требуется делать секретным, более того, он может быть общедоступным и содержаться в телефонном справочнике вместе с фамилией и адресом его владельца. Подробнее об этом и других современных задачах криптографии можно прочитать в главах 1, 2, 3 этой книги.
Наряду с термином «криптография» в литературе встречается термин «криптология», также происходящий от греческих корней, означающих «тайный» и «слово». Этот термин используется для обозначения всей области секретной связи. Криптологию делят на две части: криптографию и криптоанализ. Криптограф пытается найти методы обеспечения секретности сообщений, криптоаналитик пытается при неизвестном ключе выполнить обратную задачу. При этом часто говорят, что криптоаналитик вскрыл шифр, хотя чаще он вскрывает ключ заранее известного шифра.
Криптография - это наука о том, как обеспечить секретность сообщения
Криптология - это раздел математики, изучающий математические основы криптографических методов
Периоды криптографии: 1. Первый период (приблизительно с 3-го тысячелетия до н. э.) характеризуется господством моноалфавитных шифров (основной принцип - замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами)
ШИФР ЦЕЗАРЯ (шифр сдвига, сдвиг Цезаря) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Пример шифра Цезаря (шифрование с использованием ключа К=3) : Зашифруем слово « FAMILI » Получаем: IDPLOL (сдвиг на 3)
Пример шифрование с использованием ключа К=3 в русском алфавите. Исходный алфавит: А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Шифрованный: Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Оригинальный текст: Ученикам, чтобы преуспеть, надо догонять тех, кто впереди, и не ждать тех, кто позади. Шифрованный текст получается путём замены каждой буквы оригинального текста соответствующей буквой шифрованного алфавита: Ццъзрлнгп ъхсдю тузцфтзхя ргжс жсёсрхя хзш нхс етзузжл л рз йжгхя хзш нхс тскгжл
2. Второй период (хронологические рамки - с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) - до начала XX века) ознаменовался введением в обиход полиалфавитных шифров
Например, в процессе шифрования используется таблица Виженера, которая устроена следующим образом: в первой строке выписывается весь алфавит, в каждой следующей осуществляется циклический сдвиг на одну букву. Так получается квадратная таблица, число строк которой и равно числу букв алфавита.
3. Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.
К примеру, немецкая машина « Энигма », использовалась для шифрования засекреченной информации во время второй мировой войны. Вторая мировая война послужила своеобразным катализатором развития компьютерных систем - через криптографию.
Wehrmacht Enigma (« Энигма ») Шифровальная машина Третьего рейха. Код, созданный при помощи « Энигмы », считается одним из сильнейших из использованных во Второй мировой. Turing Bombe («Бомба Тьюринга») Разработанный под руководством Алана Тьюринга дешифратор. Его использование позволило союзникам расколоть казавшийся монолитным код « Энигмы ».
4. Четвёртый период - с середины до 70-х годов XX века - период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам - линейному и дифференциальному криптоанализу. Однако до 1975 года криптография оставалась «классической» или же, более корректно, криптографией с секретным ключом.
5. Современный период развития криптографии (с конца 1970-х годов по настоящее время) отличается зарождением и развитием нового направления - криптография с открытым ключом.
Криптоанализ - это наука о том, как вскрыть шифрованное сообщение, то есть как извлечь открытый текст не зная ключа.
Взаимосвязь алгебры и критологии
Опр. 1. Шифрование - это обратимое преобразование открытого текста в шифртекст. Оно определяется двумя взаимно обратными отображениями, Ek: T →C и Dk: C→T, где T - множество открытых текстов, C - множество всех шифртекстов, k –– ключ, выбираемый из пространства ключей K. Если обозначить через E множество { Ek: k∈K } всех отображений зашифрования, а через D множество { Dk: k∈K } всех отображений дешифрования, то для любых t ∈T, k∈K выполняется равенство Dk (Ek (t)) =t . Тогда совокупность (T, C, K, E, D) называется шифром, или шифр-системой. Простейшими и старейшими классами шифров являются шифры перестановки и шифрзамены. В этих шифрах C =T =, где A - алфавит текста, n - длина сообщения.
Опр. 2. Роль ключа k в шифре перестановки играет произвольная перестановка k∈Sn из группы перестановок множества {1, ..., n }; таким образом, пространство ключей K=Sn , отображение шифрования определяется равенством: а отображение расшифрования определяется равенством:
Опр. 3. Роль ключа k в шифре замены, играет произвольная перестановка k ∈ Sn из группы перестановок алфавита A; таким образом, пространство ключей K = Sn , отображение шифрования определяется равенством: а отображение расшифрования определяется равенством:
Пример. 1. Если верить истории, то первый шифр перестановки использовали в Спарте. На цилиндр, который назывался сцитала, плотно, виток к витку наматывалась узкая пергаментная лента. Затем, вдоль оси цилиндра записывался текст. Кода ленту снимали с цилиндра, на ней оставалась цепочка букв, на первый взгляд, совершенно беспорядочная. Лента сматывалась и передавалась адресату, который читал сообщение, наматывая ленту на такую же сциталу. После этого текст опять становился понятным. Ключом к шифру является диаметр сциталы. Поэтому она не очень хорошо защищала доверенные тайны, ведь достаточно скоро, Аристотель придумал устройство « антисцитала », который предложил наматывать ленту на конус, сдвигая ее от вершины к основанию конуса. Там, где диаметр конического сечения совпадал с диаметром сциталы, на ленте проступали осмысленные слоги и слова, после чего изготовлялась сцитала соответствующего диаметра и буквы складывались в связный текст.
Пример 2. Первый шифр замены изобрел Юлий Цезарь. В качестве перестановки букв алфавита он использовал просто циклический сдвиг на три буквы. Обратная перестановка тоже, естественно, является циклическим сдвигом. В общем случае в этом шифре использовался сдвиг вида и ключом являлось число k . Так как ключевое пространство невелико, алгоритм шифрования Цезарь, видимо, не особо афишировал.
Пример 3. К классу шифров перестановки относятся шифры маршрутной перестановки. Идея у них такая. Сообщение записывается в таблицу по одному маршруту, например по горизонталям, а считывается по другому, например по вертикалям. Для увеличения ключевого пространства использовалась еще перестановка столбцов таблицы.
ШИФР С ЗАМЕНОЙ БУКВ ЦИФРАМИ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Например:« LIFE » - «12 9 6 5»
ЦИФРОВАЯ ТАБЛИЦА Первая цифра в шифре – столбец, вторая – строка или наоборот. Так слово «MIND» можно зашифровать как «33 24 34 14».
КВАДРАТ ПОЛИБИЯ 1 МЕТОД. Вместо каждой буквы в слове используется соответствующая ей буква снизу (A = F, B = G и т.д.). Пример: CIPHER - HOUNIW. 2 МЕТОД. Указываются соответствующие каждой букве цифры из таблицы. Первой пишется цифра по горизонтали, второй - по вертикали. (A = 11, B = 21…). Пример: CIPHER = 31 42 53 32 51 24
Цветовая таблица А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я 0 1 2 3 4 5 6 7 8 9 . , : ; ! ? Первый цвет в шифре – строка, вторая – столбец
Исходный текст: Целью изучения данной темы является знакомство студентов с теорией шифрования текстов, а также формирование навыков исследования математических объектов и методики их использования при обучении и организации научно-исследовательской работы школьников; вовлечение студентов в научно-исследовательскую деятельность. Зашифрованный текст:
Джулиан Ассанж Р. 1971 На своем портале WikiLeaks публично продемонстрировал всем желающим изнанку многих государственных структур. Коррупция, военные преступления, сверхсекретные тайны - вообще все, до чего дотянулся деятельный либертарианец, стало достоянием общественности. Помимо этого, Ассанж - создатель адской криптосистемы под названием «Отрицаемое шифрование» (Deniable encryption). Это способ компоновки зашифрованной информации, который обеспечивает возможность правдоподобного отрицания ее наличия.
Брэм Коэн Р. 1975 Американский программист, родом из солнечной Калифорнии. На радость всему миру придумал протокол BitTorrent , которым небезуспешно пользуются и по сей день.
Фильмы Зодиак 2007 Г. Напряженный триллер Дэвида Финчера, построенный на реальных событиях. Большую часть фильма умнейшие сотрудники полиции Сан-Франциско тщетно пытаются расколоть шифр зарвавшегося маньяка. Энигма 2001 Г. Игровой фильм в декорациях Второй мировой войны: блестящие математики собираются в Блетчли-Парке, чтобы разгадать новый шифр коварных нацистов. Картина полна необъяснимых загадок и тайн - впрочем, об этом можно догадаться и по названию.
Знакомство с криптографией потребуется каждому пользователю электронных средств обмена информацией, поэтому криптография в будущем станет "третьей грамотностью" наравне со "второй грамотностью" - владением компьютером и информационными технологиями.
В книге впервые на русском языке дается систематическое изложение научных основ криптографии от простейших примеров и основных понятий до современных криптографических конструкций. Понимание принципов криптографии стало для многих потребностью в связи с широким распространением криптографических средств обеспечения информационной безопасности. Поэтому книга может быть полезна массовому читателю.
Книга рассчитана на студентов-математиков и специалистов по информационной безопасности.
Предмет криптографии.
Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче ТП, чтобы уточнить ситуацию и используемые понятия.
Прежде всего заметим, что эта задача возникает только для информации, которая нуждается в защите. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия:
- государственная тайна;
- военная тайна;
- коммерческая тайна;
- юридическая тайна;
- врачебная тайна и т. д.
Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:
- имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;
- имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем. чтобы обратить ее себе во благо, а законным пользователям во вред.
Для простоты мы вначале ограничимся рассмотрением только одной угрозы - угрозы разглашения информации. Существуют и другие угрозы для защищаемой информации со стороны незаконных пользователей: подмена, имитация и др. О них мы поговорим ниже.
Оглавление
Предисловия
Глава 1. Основные понятия криптографии
§1. Введение
§2. Предмет криптографии
§3. Математические основы
§4. Новые направления
§5. Заключение
Глава 2. Криптография и теория сложности
§1. Введение
§2. Криптография и гипотеза Р = NP
§3. Односторонние функции
§4. Псевдослучайные генераторы
§5. Доказательства с нулевым разглашением
Глава 3. Криптографические протоколы
§1. Введение
§2. Целостность. Протоколы аутентификации и электронной подписи
§3. Неотслеживаемость. Электронные деньги
§4. Протоколы типа «подбрасывание монеты по телефону»
§5. Еще раз о разделении секрета
§6. Поиграем в «кубики». Протоколы голосования
§7. За пределами стандартных предположений. Конфиденциальная передача сообщений
§8. Вместо заключения
Глава 4. Алгоритмические проблемы теории чисел
§1. Введение
§2. Система шифрования RSA
§3. Сложность теоретико-числовых алгоритмов
§4. Как отличить составное число от простого
§5. Как строить большие простые числа
§6. Как проверить большое число на простоту
§7. Как раскладывают составные числа на множители
§8. Дискретное логарифмирование
§9. Заключение
Глава 5. Математика разделения секрета
§1. Введение
§2. Разделение секрета для произвольных структур доступа
§3. Линейное разделение секрета
§4. Идеальное разделение секрета и матроиды
Глава 6. Компьютер и криптография
§1. Вместо введения
§2. Немного теории
§3. Как зашифровать файл?
§4. Поучимся на чужих ошибках
§5. Вместо заключения
Глава 7. Олимпиады по криптографии для школьников
§1. Введение
§2. Шифры замены
§3. Шифры перестановки
§4. Многоалфавитные шифры замены с периодическим ключом
§5. Условия задач олимпиад по математике и криптографии
§6. Указания и решения
Приложение А. Отрывок из статьи К. Шеннона «Теория связи в секретных системах»
Приложение Б. Аннотированный список рекомендованной литературы
Приложение В. Словарь криптографических терминов
Алфавитный указатель русскоязычных терминов
Алфавитный указатель англоязычных терминов.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в криптографию, Ященко В.В., 2012 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.
