Перейти к содержимому

Учебное пособие по криптологии

Регион РФ: Москва

Год публикации: 2002

Библиографическая ссылка:: Баричев С.Г, Серов Р.Е. Основы современной криптографии: Учебное пособие. - М.: Горячая линия - Телеком, 2002.

Для того, чтобы оценить ресурс, необходимо авторизоваться.

Электронная версия второго издания известной книги Баричев С.Г, Серов Р.Е. "Основы современной криптографии" (М.: Горячая линия - Телеком, 2002). В ней последовательно рассмотрены основные разделы современной криптографии: симметричное шифрование, асимметричное шифрование, системы ЭЦП, управление ключами, имитозащита информации и вопросы реализации криптосистем. В книгу включен глоссарий. Приведено описание популярных криптосистем и криптографических стандартов, включая новый отечественный ГОСТ на системы ЭЦП. Для студентов вузов и специалистов в области компьютерной безопасности. В электронной версии отсутствует ряд глав, имеющихся в печатном издании.

Регион РФ: Москва

Год публикации: 2004

Библиографическая ссылка:: Коробейников А.Г., Гатчин Ю.А. Математические основы криптологии. Учебное пособие. - СПб.: СПбГУ ИТМО, 2004. - 106 с.

Для того, чтобы оценить ресурс, необходимо авторизоваться.

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

Учебное пособие по криптологии

Криптология и кибербезопасность

Три учебных пособия по криптографии в 2016 году!

На фото, сделанном в Московском Доме Книги на Арбате, представлены учебники по криптографии 2016 года, авторы которых — сотрудники кафедры «Криптология и кибербезопасность» НИЯУ МИФИ!

Профессор нашей кафедры Запечников С.В. совместно с с.н.с. Казариным О.В. и ныне покойным проф. Тарасовым А.А. стал автором учебно-методического пособия «Криптографические методы защиты информации. Учебник для академического бакалавриата» (издательство Юрайт). 42 учебных заведения уже выбрали это издание!

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

Два сотрудника нашей кафедры — профессор Фомичев В.М. и доцент Мельников Д.А. завершили в 2016 году работу над двухтомником «Криптографически е методы защиты информации. Часть 1 — Математические аспекты, часть 2 — Системные и прикладные аспекты. Учебник для академического бакалавриата» (издательство Юрайт).

Математические основы криптологии

1 А. Г. Коробейников, Ю.А.Гатчин Математические основы криптологии Учебное пособие Санкт-Петербург 2004

2 2 УДК 5 Коробейников А. Г, Ю.А.Гатчин. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, с, илл. В данной книге представлен материал, необходимый для введения в теорию криптографичесих алгоритмов, математическим фундаментом которых является прикладная теория чисел. Это в первую очередь теория групп, теория колец и теория полей. Рассмотрены криптосистемы с секретным ключом (симметричные или классические), а также криптосистемы с открытым ключом (асимметричные). Кроме того, представлены основные положения криптографического протокола "электронная подпись". В каждом разделе приведены примеры на соответствующие темы. Книга предназначена в первую очередь для студентов, обучающихся по специальности Комплексная защита объектов информатизации, но может быть интересна широкому кругу специалистов. Илл. 6, список литературы 7 наим. Cанкт-Петербургский государственный университет информационных технологий, механики и оптики, Коробейников А. Г., Гатчин Ю.А. 2004

3 3 ВВЕДЕНИЕ Долгое время наука криптография была засекречена, т.к. применялась, в основном, для защиты государственных и военных секретов. Термин "криптология" даже нельзя было произносить тем, кто профессионально работал в этой области, не говоря уже о каких бы то ни было открытых публикациях на эту тему. В открытых организациях, как учебных, так и научно-исследовательских, никто криптологией официально не занимался. Слово "криптология" впервые появилось у нас в переводной статье Дж. Л. Месси "Введение в современную криптологию" в тематическом выпуске ТИИЭР, т.76, 5 за 988 год. Освещающая классические вопросы криптологии, она может служить хорошим введением в предмет. В настоящее время, методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц и организаций. Дело здесь совсем не обязательно в секретах, а в том, что сейчас очень большой обмен информацией происходит в цифровом виде через открытые каналы связи. К этой информации возможно применение угроз недружественного ознакомления, накопления, подмены, фальсификации и т.д. Наиболее надежные методы защиты от таких угроз дает именно криптография. Математические методы, используемые в криптографии, невозможно успешно освоить без знания таких алгебраических структур, как группы, кольца и поля. Поэтому знание и умение работать с этими объектами является необходимым условием для подготовки специалистов в области защиты информации. В силу присущей методам криптографии специфики, большой интерес представляет множество целых чисел и различные алгебраические структуры на его базе. Поэтому основное внимание будет уделено работе с целыми числами. Математическая криптография возникла как наука о шифровании информации, т.е. как наука о криптосистемах. Большое влияние на развитие криптографии оказали появившиеся в середине двадцатого века работы американского математика Клода Шеннона. В классической шенноновской модели системы секретной связи имеют место два полностью доверяющих друг-другу участника, которым необходимо передавать между собой информацию, не предназначенную для третьих лиц. Такая информация называется конфиденциальной или секретной. Отсюда возникает задача обеспечения конфиденциальности, т.е. защита секретной информации от противника. Эта задача, по крайней мере исторически, первая задача криптографии. Она традиционно решается с помощью криптосистем. При обмене информацией между участниками часто возникает ситуация, когда информация не является конфиденциальной, но важен факт поступления сообщений в неискаженном виде, т.е. наличие гарантии, что

4 4 никто не сумеет подделать сообщение. Такая гарантия называется обеспечением целостности информации и составляет вторую задачу криптографии. Для предотвращения угрозы контроля за источниками информации (откуда пересылаются сообщения) необходима система контроля за доступом к ресурсам, которая должна удовлетворять двум, казалось бы, взаимно исключающим требованиям. Во первых, всякий желающий должен иметь возможность обратиться к этой системе анонимно, а во вторых, при этом все же доказать свое право на доступ к ресурсам. Примером могут служить бумажные купюры. Если ресурсом является некоторый товар, то наличие у покупателя достаточного количества купюр является доказательством его права на доступ к ресурсу. С другой стороны, хотя каждая бумажная купюра и имеет уникальный номер, отслеживать купюры по номерам практически невозможно, т.е. нельзя определить, кто ее использовал и в каких платежах. Аналог этого свойства в криптографии называется неотслеживаемостью. Обеспечение неотслеживаемости третья задача криптографии. Если задача обеспечения конфиденциальности решается с помощью криптосистем, то для обеспечения целостности и неотслеживаемости разрабатываются криптографические протоколы. В первой части кратко рассмотрена история криптографии и её основные понятия. Приведены основные классические шифры, такие как, шифр Цезаря, маршрутная транспозиция, таблица Виженера, одноразовый блокнот и т.д. Во второй части введены базовые определения и понятия теории множеств, такие как "отображение" и "бинарные отношения", представлена основная теорема арифметики, наибольший общий делитель и т.д.. В третьей части определены и рассмотрены основные алгебраические структуры используемые в криптографии. Это такие множества как группы, кольца, поля. Определены понятия гомоморфизмов, изоморфизмов и автоморфизмов. Введено кольцо классов вычетов. Определены правила отображений из одного кольца в другое. Рассмотрены поля Галуа. В четвертой части изучаются основные свойства диофантова уравнения и методы его решения. В пятой части представлены основные положения шифрования с секретным ключом. Рассмотрены подстановки, перестановки, блочные и потоковые шифры, система Виженера и т.д. т.п. В шестой части рассмотрены основные положения асимметричного шифрования. Рассмотрены криптосистемы на базе алгоритмов Диффи- Хелмана, Эль-Гамаля, RSA, эллиптических кривых и т.д. и т.п. В седьмой части рассмотрены основные положения криптографического протоколов аутентификации и "электронной подписи".

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

6 6. КЛАССИЧЕСКИЕ ШИФРЫ И ОСНОВНЫЕ ПОНЯТИЯ.. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ТЕРМИНОЛОГИЯ Проблемами защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей. В этой книге основное внимание будет уделено криптографическим методам. Современная криптография включает в себя четыре основных направления:. Симметричные криптосистемы. 2. Криптосистемы с открытым ключом. 3. Системы электронной подписи. 4. Управление ключами. Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа. В качестве информации, подлежащей шифрованию и дешифрованию, будут рассматриваться тексты, построенные на некотором алфавите. Под этими терминами понимается следующее. Алфавит - конечное множество используемых для кодирования информации знаков. Текст - упорядоченный набор из элементов алфавита. В качестве примеров алфавитов, используемых в современных информационных системах (ИС) можно привести следующие: алфавит Z буквы русского алфавита и пробел; алфавит Z буквы русского алфавита, знаки препинания и пробела; алфавит Z 256 символы, входящие в стандартные коды ASCII и КОИ-8; бинарный алфавит Z 2 = <0,>; восьмеричный алфавит Z 8 = <0,,2,3,4,5,6,7>; шестнадцатеричный алфавит Z 6 = <0,,2,3,4,5,6,7,8,9,0,, 2,3, 4, 5>; и т.д.и т.п.

7 7 Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом (называемый также криптограммой) (рис.). Ключ - информация, необходимая для шифрования и дешифрования текстов. Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются каким-нибудь символом, например k. Параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Цель криптографической системы заключается в том, чтобы зашифровать осмысленный исходный текст, получив в результате совершенно бессмысленный на взгляд шифрованный текст. Получатель, которому он предназначен, должен быть способен расшифровать эту шифрограмму, восстановив, таким образом, соответствующий ей открытый текст. При этом противник (называемый также криптоаналитиком) должен быть неспособен раскрыть исходный текст. Существует важное отличие между дешифрованием и раскрытием криптосистемы. Раскрытием криптосистемы назыисходный текст Криптографическая система шифрованный текст КЛЮЧ Рис.. Процесс шифрования данных Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный (рис.2). шифрованный текст Криптографическая система исходный текст КЛЮЧ Рис.2. Процесс дешифрования данных

8 8 вается результат работы криптоаналитика, приводящий к возможности эффективного раскрытия любого, зашифрованного с помощью данной криптосистемы, открытого текста. Степень неспособности криптосистемы к раскрытию называется ее стойкостью (криптостойкостью), или другими словами криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых: количество всех возможных ключей; среднее время, необходимое для криптоанализа. Таким образом, преобразование T k определяется соответствующим алгоритмом и значением параметра k. Эффективность шифрования с целью защиты информации зависит от сохранения тайны ключа и криптостойкости шифра. Существуют несколько способов, в соответствии с которыми могут классифицироваться криптографические системы. Например, существует такая классификация: - криптосистемы ограниченного использования; - криптосистемы общего использования; - криптосистемы с секретным ключом; - криптосистемы с открытым ключом. Криптографическая система называется криптосистемой ограниченного использования, если ее стойкость основывается на сохранении в секрете самого характера алгоритмов шифрования и дешифрования. Простейшим историческим примером такой системы можно считать шифр Цезаря, который будет рассмотрен далее. Криптосистемы ограниченного использования обычно разрабатываются любителями и почти всегда являются детской забавой для опытного криптоаналитика-профессионала. Гораздо важнее то, что такие системы вообще не используются для конфиденциальной связи в современной ситуации, когда должна обеспечиваться работа большого числа абонентов. Криптографическая система называется криптосистемой общего использования, если ее стойкость основывается не на секретности алгоритмов шифрования и дешифрования, а на секретности ее ключа. Ключ должен легко вырабатываться конкретными пользователями при помощи их собственных ключей таким образом, чтобы даже разработчик криптосистемы не мог раскрыть ее, не имея доступа к тому ключу, который в ней в действительности использовался. Для некоторых применений (главным образом в военных, дипломатических и разведывательных ведомствах) для разработчика общей криптосистемы нет никаких причин для того, чтобы открытым образом описывать характер ее алгоритмов. Сохраняя эту информацию в тайне, можно обеспечить даже некоторую дополнительную безопасность. Однако, решающим обстоятельством, позволяющим полагаться на такую секретность, это не является, поскольку ничего нельзя сказать о том, когда она может быть скомпрометирована. По этой

Читайте так же:  Агентский договор по продаже билетов на концерты

9 причине, исследования надежности таких систем всегда должны проводиться в предположении, что потенциальному противнику о криптосистеме известно все, за исключением реально используемого секретного ключа. А если на самом деле противник такими знаниями не обладает, то это даже лучше. Для других типов применений, подобных, например, большим финансовым комплексам, в действительности лучше раскрывать, как работают их криптосистемы. В противном случае пользователи всегда будут предполагать возможность существования некоего секретного метода раскрытия такой криптосистемы. Одним из требований обеспечения стойкости общей криптографической системы является огромное количество возможных ключей, не позволяющее провести исчерпывающий поиск (при котором осуществляется попытка систематического дешифровывания заданной криптограммы, используя при этом каждый из возможных ключей до тех пор, пока не получится некий осмысленный открытый текст). Однако необходимо знать, что большое число ключей само по себе стойкости криптосистемы не обеспечивает. Общая криптографическая система называется криптосистемой с секретным ключом, если в ней любые две стороны, перед тем, как связаться друг с другом, должны заранее договориться между собой об использовании в дальнейшем некоторой секретной части информации, которая и называется секретным ключом. Такой механизм секретного распределения ключей мог эффективно работать в прошлом, то есть в ситуации, когда криптография использовалась небольшим числом пользователей. В настоящее время, когда криптография стала общедоступной, было бы неразумно организовывать такую сеть, в которой каждой паре потенциальных пользователей заранее предоставлялся бы их совместный секретный ключ, потому что тогда число таких ключей возрастало бы лавинообразно с увеличением числа пользователей. В 976 году Уитфрид Диффи (Diffie) и Мартин Хеллман (Hellman) заложили основы для преодоления этой трудности, предложив понятие криптографии с открытым ключом. Сходное понятие было независимо открыто Ральфом Мерклем (Merkle). Вскоре последовала его первая практическая реализация, предложенная Рональдом Ривестом (Rivest), Эди Шамиром (Shamir) и Леонардом Адлеманом (Adleman). Секретная связь по незащищенным каналам связи между двумя совершенно незнакомыми друг с другом сторонами наконец-то стала возможна. Основное наблюдение, которое, собственно, и привело к криптографии с открытым ключом, заключалось в следующем тот, кто зашифровывает сообщение, не обязательно должен быть способен его расшифровывать. В таких системах каждый пользователь выбирает свой собственный секретный ключ, на основании которого получает пару алгоритмов. Затем он делает один из них доступным каждому из возможных пользователей, объявляя этот алгоритм своим открытым алгоритмом 9

10 0 шифрования, в то время как другой, соответствующий первому и являющийся его личным алгоритмом дешифрования, хранит в строгом секрете. Само собой разумеется, что такие системы могут быть стойкими, только если по свойствам общедоступного алгоритма шифрования невозможно "вычислить" или подобрать соответствующий ему алгоритм дешифрования. Термины распределение ключей и управление ключами относятся к процессам системы обработки информации, содержанием которых является составление и распределение ключей между пользователями. Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения..2. ИЗ ИСТОРИИ КРИПТОГРАФИИ Потребность шифровать и передавать шифрованные сообщения возникла очень давно. Так, еще в V-IV вв. до н. э. греки применяли специальное шифрующее устройство. По описанию Плутарха, оно состояло из двух палок одинаковой длины и толщины. Одну оставляли себе, а другую отдавали отъезжающему. Эти палки называли скиталами. Когда правителям нужно было сообщить какую-нибудь важную тайну, они вырезали длинную и узкую, вроде ремня, полосу папируса, наматывали ее на свою скиталу, не оставляя на ней никакого промежутка, так чтобы вся поверхность палки была охвачена этой полосой. Затем, оставляя папирус на скитале в том виде, как он есть, писали на нем все, что нужно, а написав, снимали полосу и без палки отправляли адресату. Так как буквы на ней разбросаны в беспорядке, то прочитать написанное можно только при помощи соответствующей скиталы, намотав на нее без пропусков полосу папируса. Аристотелю принадлежит способ дешифрования этого шифра. Надо изготовить длинный конус и, начиная с основания, обертывать его лентой с шифрованным сообщением, постепенно сдвигая ее к вершине. В какой-то момент начнут просматриваться куски сообщения. Так можно определить диаметр скиталы. Были и другие способы защиты информации, разработанные в античные времена. Напрмер, древнегреческий полководец Эней Тактика в IV веке до н.э. предложил устройство, названное впоследствии "диском Энея". Принцип его таков. На диске диаметром 0-5 см и толщиной -2 см высверливались отверстия по числу букв алфавита. В центре диска помещалась "катушка" с намотанной на ней ниткой достаточной длины. При зашифровании нитка "вытягивалась" с катушки и последовательно протягивалась через отверстия, в соответствии с буквами шифруемого текста. Диск и являлся посланием. Получатель послания последовательно

11 вытягивал нитку из отверстий, что позволяло ему получать передаваемое сообщение, но в обратном порядке следования букв. При перехвате диска недоброжелатель имел возможность прочитать сообщение тем же образом, что и получатель. Но Эней предусмотрел возможность легкого уничтожения передаваемого сообщения при угрозе захвата диска. Для этого было достаточно выдернуть "катушку" с закрепленным на ней концом нити до полного выхода всей нити из всех отверстий диска. Сам термин шифр арабского происхождения. В начале XV в. арабы опубликовали энциклопедию Шауба Аль-Аща, в которой есть специальный раздел о шифрах. В этой энциклопедии указан способ раскрытия шифра простой замены. Он основан на различной частоте повторяемости букв в тексте. В этом разделе есть перечень букв в порядке их повторяемости на основе изучения текста Корана. Заметим, что в русском тексте чаще всего встречается буква О, затем буква Е и на третьем месте стоят буквы И и А. Более точно: на 000 букв русского текста в среднем приходится 90 букв О, 72 буквы Е или Ё, 60 букв И и А и т.д. В Древней Греции идея Энея была использована при создании и других оригинальных шифров замены. Например, в одном из вариантов вместо диска использовалась линейка с числом отверстий, равных количеству букв алфавита. Каждое отверстие обозначалось своей буквой; буквы по отверстиям располагались в произвольном порядке. К линейке была прикреплена катушка с намотанной на нее ниткой. Рядом с катушкой имелась прорезь. При шифровании нить протягивалась через прорезь, а затем через отверстие, соответствующее первой букве шифруемого текста, при этом на нити завязывался узелок в месте прохождения ее через отверстие; затем нить возвращалась в прорезь и аналогично зашифровывалась вторая буква текста и т.д. После окончания шифрования нить извлекалась и передавалась получателю сообщения. Тот, имея идентичную линейку, протягивал нить через прорезь до отверстий, определяемых узлами, и восстанавливал исходный текст по буквам отверстий. Это устройство получило название "линейка Энея". Шифр, реализуемый линейкой Энея, является одним из примеров шифра замены: буквы заменяются на расстояния между узелками с учетом прохождения через прорезь. Ключом шифра являлся порядок расположения букв по отверстиям в линейке. Противник, завладевший нитью (даже имея линейку, но без нанесенных на ней букв), не сможет прочитать сообщение. Аналогичное "линейке Энея" "узелковое письмо" получило распространение у индейцев Центральной Америки. Свои сообщения они также передавали в виде нитки, на которой завязывались разноцветные узелки, определявшие содержание сообщения. Заметным вкладом Энея в криптографию является предложенный им так называемый книжный шифр, описанный в сочинении "Об обороне укрепленных мест". Эней предложил прокалывать малозаметные дырки в книге или в другом документе над буквами (или под ними) секретного со-

12 2 общения. Интересно отметить, что в первой мировой войне германские шпионы использовали аналогичный шифр, заменив дырки на точки, наносимые симпатическими чернилами на буквы газетного текста. Книжный шифр в современном его виде имеет несколько иной вид. Суть этого шифра состоит в замене букв на номер строки и номер этой буквы в строке и заранее оговоренной странице некоторой книги. Ключом такого шифра является книга и используемая страница в ней. Этот шифр оказался "долгожителем" и применялся даже во времена второй мировой войны. В Древней Греции (II в. до н. э.) был также известен шифр, называемый квадрат Полибия. Это устройство представляло собой квадрат 5 х 5, столбцы и строки которого нумеровали цифрами от до 5. В каждую клетку этого квадрата записывалась одна буква. (В греческом варианте одна клетка оставалась пустой, в латинском в одну клетку помещали две буквы i и j.) В результате каждой букве отвечала пара чисел и шифрованное сообщение превращалось в последовательность пар чисел. Пример Это сообщение записано при использовании латинского варианта квадрата Полибия, в котором буквы расположены в алфавитном порядке. ("Cogito, ergo sum" лат, "Я мыслю, следовательно существую"). Интересно отметить, что в несколько измененном виде шифр Полибия дошел до наших дней и получил своеобразное название "тюремный шифр". Для его использования нужно только знать естественный порядок расположения букв алфавита (как в указанном выше примере для английского языка). Стороны квадрата обозначаются не буквами (ABCDE), а числами (2345). Число 3, например, передается путем тройного стука. При передаче буквы сначала "отстукивается число, соответствующее строке, в которой находится буква, а затем номер соответствующего столбца. Например, буква "F" передается двойным стуком (вторая строка) и затем одинарным (первый столбец). С применением этого шифра связаны некоторые исторические казусы. Так, декабристы, посаженные в тюрьму после неудавшегося восстания, не смогли установить связь с находившимся в "одиночке" князем Одоевским. Оказалось, что этот князь (хорошо образованный по тем временам) не помнил естественный порядок расположения букв в русском и французском алфавитах (другими языками он не владел). Декабристы для русского алфавита использовали прямоугольник размера 5x6 (5 строк и 6 столбцов) и редуцированный до 30 букв алфавит. Тюремный шифр", строго говоря, не шифр, а способ перекодировки сообщения с целью его приведения к виду, удобному для передачи по каналу связи (через стенку). Дело в том, что в таблице использовался естественный порядок расположения букв алфавита. Отметим, что при произвольном расположении букв в квадрате возникает одно затруднение: либо нужно помнить отправителю и получателю сообщения заданный произвольный порядок следования букв в таблице (ключ шифра), что во-

Читайте так же:  19 арбитражный суд г. Воронеж

13 3 обще говоря затруднительно, либо иметь при себе запись этих букв. Во втором случае появляется опасность ознакомления с ключом посторонних лиц. В в. н.э. Ю. Цезарь во время войны с галлами, переписываясь со своими друзьями в Риме, заменял в сообщении первую букву латинского алфавита (А) на четвертую (D), вторую (В) на пятую (Е), наконец, последнюю на третью: 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 Пример 2. Донесение Ю. Цезаря Сенату об одержанной им победе над Понтийским царем выглядело так: YHQL YLGL YLFL("Veni, vidi, vici" лат. "Пришел, увидел, победил"). Император Август ( в. н. э.) в своей переписке заменял первую букву на вторую, вторую на третью и т. д. Последнюю на первую: 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 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 A Пример 3. Любимое изречение императора Августа выглядело так: GFTUJOB MFOUF ("Festina lente" лат. "Торопись медленно"). Квадрат Полибия, шифр Цезаря входят в класс шифров, называемых подстановка или простая замена, т.е. это шифры, в которых каждой букве алфавита соответствует буква, цифра, символ или какая-нибудь их комбинация. В известных рассказах Пляшущие человечки Конан Дойля и Золотой жук Эдгара По используемые шифры относятся к указанному классу шифров. В другом классе шифров перестановка буквы сообщения каким-нибудь способом переставляются между собой. К этому классу принадлежит шифр скитала. Неудобство шифров типа подстановка (простая замена) в случае использования стандартного алфавита очевидно. Таблица частот встречаемости букв алфавита позволяет определить одни или несколько символов, а этого иногда достаточно для дешифрования всего сообщения ( Пляшущие человечки Конан Дойля или Золотой жук Эдгара По). Поэтому обычно пользуются разными приемами, чтобы затруднить дешифрование. Для этой цели используют многобуквенную систему шифрования систему, в которой одному символу отвечают одна или несколько комбинаций двух и более символов. Другой прием использование нескольких алфавитов. В этом случае для каждого символа употребляют тот или иной алфавит в зависимости от ключа, который связан каким-нибудь способом с самим символом или с его порядком в передаваемом сообщении.

14 4.3. МАРШРУТНАЯ ТРАНСПОЗИЦИЯ К классу перестановка относится шифр маршрутная транспозиция и его вариант постолбцовая транспозиция. В каждом из них в данный прямоугольник [n m] сообщение вписывается заранее обусловленным способом, а столбцы нумеруются или обычным порядком следования, или в порядке следования букв ключа буквенного ключевого слова. Пример 4. Зашифруем фразу Дела давно минувших дней, преданья старины глубокой, используя для этого два прямоугольника 6 8. В первом прямоугольнике столбцы нумеруются в обычном порядке следования слева направо, а во втором в порядке следования букв слова Пушкин. Используя расположение букв этого ключа в алфавите, получим набор чисел [ ]: д е л а д а в н о м и н у в ш и х д н е й п р е д а н ь я с т а р и н ы г л у б о к о й а б в г В первом случае получим шифрованный текст, если будем выписывать буквы очередного столбца в порядке следования столбцов (прямом или обратном), во втором, если будем выписывать буквы столбца в порядке следования букв ключа. Таким образом, будем иметь: ) двундтго енвеаалй лошйнруа амипьибб дихрянов андесыкг; 2) дихрянов амипьибб андесыкг двундтго енвеаалй лошйнруа..4. ТАБЛИЦА ВИЖЕНЕРА д е л а д а в н о м и н у в ш и х д н е й п р е д а н ь я с т а р и н ы г л у б о к о й а б в г В процессе шифрования (и дешифрования) иногда используется таблица Виженера, которая устроена следующим образом: в первой строке выписывается весь алфавит, в каждой следующей осуществляется циклический сдвиг на одну букву. Так получается квадратная таблица, число строк которой равно числу букв в алфавите. Чтобы зашифровать какое-нибудь сообщение, поступают следующим образом. Выбирается слово лозунг и подписывается с повторением над буквами сообщения. Чтобы получить шифрованный текст, находят очередной знак лозунга, начиная с первого в вертикальном алфавите, а ему соответствующий знак сообщения в горизонтальном.

15 5 Пример 5. Таблица, составлена из 3 буквы русского алфавита (без букв Ё и Ъ). таблица А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Выбираем лозунг математика. Находим столбец, отвечающий букве "м" лозунга, а затем строку, соответствующую букве "к". На пересечении выделенных столбца и строки находим букву "ц". Так продолжая дальше, получаем весь шифрованный текст. м а т е м а т и к а м а т е м а т и к а м а т е м а к р и п т о г р а ф и я с е р ь е з н а я н а у к а ц р ь ф я о х ш к ф ф я д к э ь ч п ч а л н т ш ц а К сообщению можно применять несколько систем шифрования..5. МОДИФИЦИРОВАННЫЙ ШИФР ЦЕЗАРЯ Аббат Тритемеус автор первой печатной книги о тайнописи (58г.) предложил несколько шифров и среди них шифр, который можно считать усовершенствованием шифра Цезаря. Этот шифр устроен так. Все буквы алфавита нумеруются по порядку (от до 3 в русском варианте). Затем выбирают какое-нибудь слово, называемое "ключом", и подписывают под сообщением с повторением. Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 3, то из нее вычитают 3. В результате получают последо-

Читайте так же:  Надбавка за стаж работы в районах крайнего севера 50

16 6 вательность чисел от до 3. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Разбиваем этот текст на группы одной длины, получают шифрованное сообщение. Пример 6. Выбираем ключевое слово "Пособие". Составляем сообщение "сессия начинается в конце семестра" с е с с и я н а ч и н а е т с я в к о н ц е с е м е с т р а по с о б и е п о с о б и е п о с о б и е п о с о б и е п о Шифруем, разбиваем текст на группы длины 6, и получаем шифрованное сообщение: в ф д а и и у р з ь э в о ш в о ф щ р ц э х б ч ы з ь ш б п Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 33, то из нее вычитают 33. В результате получают последовательность чисел от до 33. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Разбивал этот текст на группы одной длины (например, по 5), получают шифрованное сообщение. Если под ключом шифра понимать однобуквенное слово В (в русском варианте), то мы получим шифр Цезаря. Пример 7. Для сообщения из примера 6, получим: ф и ф ф л в р г ь л р г и х ф в в н т р щ и ф и п и ф х у г.6. ОДНОРАЗОВЫЙ БЛОКНОТ Почти все используемые на практике шифры характеризуются как условно надежные, поскольку они могут быть раскрыты в принципе при наличии неограниченных вычислительных возможностей. Абсолютно надежные шифры нельзя разрушить даже при наличии неограниченных вычислительных возможностей. Доказательство существования и единственности абсолютно надежного шифра получил К.Шеннон с помощью разработанного им теоретико-информационного метода исследования шифров. Таким образом, единственный абсолютно надежный шифр, который используется на практике, это так называемый одноразовый блокнот, в основе которого лежит та же идея, что и шифре Цезаря. Рассмотрим его основную идею. Занумеровав все символы расширенного алфавита Z 44 числами от 0 до 43, можно рассматривать любой передавамый текст, как последовательность чисел множества А=<0,,2,,43>. Имея случайную последовательность из чисел множества А той же длины что и передаваемый текст (ключ), складываем по модулю 44 число a n передаваемого текста с соответствующим числом c n ключа a n +c n b n (mod 44), 0 b n 43, Операции сложения и вычитания по модулю будут определены в главе 3

17 получим последовательность знаков шифрованного текста. Чтобы получить передаваемый текст, можно воспользоваться тем же ключом: a n b n -c n (mod 44), 0 a n 43. У двух абонентов, находящихся в секретной переписке, имеются два одинаковых блокнота, составленных из отрывных страниц, на каждой из которых напечатана таблица со случайными числами или буквами, т.е. случайная последовательность чисел из множества А. Таблица имеет только две копии: одна используется отправителем, другая получателем. Отправитель свой текст шифрует указанным выше способом при помощи первой страницы блокнота. Зашифровав сообщение и отправив его второму абоненту, он уничтожает использованную страницу. Получатель шифрованного текста расшифровывает его и также уничтожает использованный лист блокнота. Нетрудно видеть, что одноразовый шифр нераскрываем в принципе, так как символ в тексте может быть заменен любым другим символом и этот выбор совершенно случаен. 7

18 8 2. МНОЖЕСТВА И ОТОБРАЖЕНИЯ 2.. МНОЖЕСТВА Математическое понятие множество является одним из центральных во всей математике. Оно определяется в зависимости от задач. Примером может служить группа аксиом, известная как система NGB (по имени авторов Джона фон Нейман, Поля Бернайса, Курта Геделя). Главная идея, положенная в основу NGB, заключается в различении понятий множества и класса. Все объекты NGB являются классами. Класс соответствует нашему интуитивному пониманию совокупности. Множеством являются те классы, которые являются элементами других классов. Классы, не являющиеся множествами, называются собственными классами. Существует другая группа аксиом система ZF (по имени авторов Эрнста Цермело и Абрахама Френкеля). Это теория построимых множеств, т.е. множество строится из некоторых простых элементов, с помощью таких операций, как пересечение, объединение, дополнение и т.д. Мы будем понимать под множеством любую совокупность объектов, называемых элементами множества. Множества с конечным числом различных элементов могут быть описаны путем явного перечисления всех элементов. Обычно эти элементы заключаются в фигурные скобки. Например, <6,32,64>множество степеней двойки, заключенных между 0 и 00. Множество обозначается прописной буквой какого-либо алфавита, а его элементы строчными буквами того же или другого алфавита. Для некоторых особо важных множеств приняты стандарные обозначения, которых следует придерживаться. Так, буквами N, Z, Q, R обозначают соответственно множество натуральных чисел, множество целых чисел, множество рациональных чисел и множество вещественных чисел. При заданном множестве S включение a S указывает на то, что a элемент множества. В противном случае записывают a S. Говорят, что S подмножество T или S T (S содержится в T), когда имеет место импликация: x S, x x T. Два множества совпадают (или равны), если у них одни и те же элементы. Символически это записывается в виде: S=T S T и T S. Пустое множество, т.е. множество, не содержащее ни одного элемента, по определению входит в число подмножеств любого множества. Под пересечением двух множеств S и T понимают множество S T=, а под их объединением множество S T=.

19 9 Пусть X и Y произвольные множества. Пару (x,y) элементов x X, y Y, взятых в данном порядке, называют упорядоченной парой, считая при этом, что (x,y )=(x 2,y 2 ) тогда и только тогда, когда x =x 2, y =y 2. Декартовым произведением двух множеств X и Y называется множество всех упорядоченных пар (x,y): X Y=<(x,y) x X, y Y>. Пример 8. Пусть, R множество всех вещественных чисел. Тогда декартов квадрат R 2 =R R есть просто множество всех декартовых координат на плоскости относительно заданных координатных осей. Аналогично можно ввести декартово произведение трех, четырех и т.д. множеств. При X =X 2 =X 3 = =X k =X cокращенно пишут X k и говорят о k-й декартовой степени множества X. Элементами X k являются последовательности, или строки (x,x 2, x k ) длины k ОТОБРАЖЕНИЯ Понятие отображения или функции также является одним из центральных в математике. При заданных X и Y отображение f с областью определения X и областью значений Y сопоставляет каждому элементу x X элемент f(x) Y. Символически отображение записывается в виде f:x Y. Образом при отображении f называется множество всех элементов вида f(x): Im f = =f(X) Y. Множество f - (y) = называется прообразом элемента y Y. Отображение f:x Y называется сюръективным, или отображением на, когда Im f=y. Отображение f:x Y называется инъективным, когда из x x' следует f(x) f(x'). Отображение f:x Y называется биективным, или взаимно однозначным, если оно одновременно сюръективно и инъективно. Равенство f=g двух отображений означает по определению, что их соответствующие области совпадают. Пример 9. Пусть R + множество положительных вещественных чисел. Тогда отображения f:r R, g:r R +, h:r + R +, определенные одним и тем же правилом x x 2, все различны: f ни сюръективно, ни инъективно, g сюръективно, но не инъективно, а отображение h биективно. Таким образом, задание области определения и области значений важная часть определения отображения. Единичным или тождественным отображением e X :X X называется отображение, переводящее каждый элемент x X в себя.

20 20 Отображение f - является обратным к f, если f(x)=y f - (y)=x. Пример 0. Найти обратное отображение f - для f(x)=. Обратное x 5 отображение удовлетворяет условию f(f - (x))=f - (f(x))=e X =x. Следо- вательно, = x. =f - (x) x 2-5x 2 ; f - (x) =/x f ( x) 5 Проверка.f(f - (x))=f(/x 2 +5)= =x=f - (f(x))=f - ( )= 2 / x x x БИНАРНЫЕ ОТНОШЕНИЯ Для любых двух множеств X и Y всякое подмножество O X Y называется бинарным отношением между X и Y (или просто на X, если X=Y). Бинарное отношение

на X называется отношением эквивалентности, если для всех x, x, x 2 X выполнены условия: i. x

x (рефлексивность); ii. x

x (симметричность); iii. x

x (транзитивность). Подмножество H=

x> X всех элементов, эквивалентных данному x, называется классом эквивалентности, содержащим x. Так как x

x (условие i), то x' H. Любой элемент x' H называется представителем класса H. Справедливо следующая теорема. Теорема. Множество классов эквивалентности по отношению

является разбиением множества X в том смысле, что X является объединением непересекающихся подмножеств. Доказательство. В самом деле, так как x H, то X= H i. Далее, класс H однозначно определяется любым своим представителем, т.е. H i =H j x i

Тема Tiny Framework Войти