Задачи по криптографии – Кукина_Сборник_задач_по_криптографии

Кукина_Сборник_задач_по_криптографии

Е. Г. Кукина, В. А. Романьков

СБОРНИК ЗАДАЧ И

УПРАЖНЕНИЙ ПО КРИПТОГРАФИИ

Е. Г. Кукина, В. А. Романьков

СБОРНИК ЗАДАЧ И

УПРАЖНЕНИЙ ПО КРИПТОГРАФИИ

2

ÓÄÊ 519.6 + 681.83 ÁÁÊ 32.973.202-018.2

Рецензенты:	доктор	физико-математических
наук профессор	À.	Н. Зубков;	кандидат
физико-математическихíàóêА. Н. Рыбалов

Кукина Е. Г., Романьков В. А.

Сборник задач и упражнений к учебнику В.А.Романькова ¾Введение в криптографию¿. Курс лекций. Омск: Èçä-âîОмского государственного университета, 2009 г.,2-åиздание, испр. и доп. Москва: Форум, 2012 г.

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

Сборник подготовлен при поддержке Министерства образования и науки Российской Федерации, проекты 14.В37.21.0359/0859.

ÓÄÊ 519.6 + 681.83 ÁÁÊ 32.973.202-018.2

5

Предисловие авторов

Книга		второго		автора		«Введение		â
криптографию.»			Êóðñ	лекций.		(Îìñê:		Èçä-
âî	Омского		государственного			университета,
2009	г., другая публикация Москва:						Форум,
2012	ã.)	базируется на записях лекций по
курсу «Криптография ,					читанных		автором
â	Омском		государственном			университете

имени Ф.М. Достоевского и ряде других университетов в период с 1996 по 2009 год. Книга представляет именно введение в предмет, не загруженное излишними деталями, компактное и

информативное.				Предназначена для того, чтобы
åå	читатели		íå	только	могли	ориентироваться
â	ìèðå	криптографии			è	åå	приложений,
íî	также,		если возникнет			соответствующее
желание		èëè		необходимость,		могли		быстро
перейти		ê	чтению специальной				литературы
по криптографии и ее приложениям.								Прежде
всего книга			направлена		на студентов,			впервые

6

знакомящихся с криптографией, и преподавателей курсов по криптографии и защите информации. Специалисты в области криптографии также смогут найти в ней êîå-÷òîинтересное.

Омское издание книги «Введение в криптографию» награждено Дипломом Первого Сибирского регионального конкуса на лучшую вузовскую книгу УНИВЕРСИТЕТСКАЯ КНИГА2009 г. в номинации Лучшее учебное издание по математике, информатике и вычислительной технике; Дипломом Конкурса Золотая медаль ITE Сибирской Ярмарки (учебная книга) УЧСИБ 2010 г.; Дипломом V Международного конкурса УНИВЕРСИТЕТСКАЯ КНИГА 2010 г. в номинации Лучшее учебное издание по естественным наукам .

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

7

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

на множители. Задачи повышенной трудности отмечены знаком :

Е. Г. Кукина, В .А. Романьков Омский государственный университет им. Ф.М. Достоевского Институт математики и информационных технологий

[email protected]; [email protected] Îìñê, 2013 ã.

8

Введение

Задачи и упражнения, включенные авторами в данное издание, призваны дополнить теоретическое содержание курса лекций В. А. Романькова «Введение в криптографию» [11], опубликованного издательством Омского государственного университета в 2009 году (2-åисправленное и дополненное издание [12] выпущено издательством Форум, Москва, 2012 г., ранее выходили методическое пособие [9] и более краткий вариант лекций [10]). В свою очередь учебник соответствует курсу лекций «Криптография», читаемому автором в Омском государственном университете имени Ф. М. Достоевского уже более 15 лет. Задачи и упражнения, включенные авторами в данный задачник прошли апробацию на практических занятиях этого курса.

Âучебнике «Введение в криптографию»

освещены	основные	ïî	мнению	автора
разделы	современной	криптографии.		Äàíî

представление о симметричных и асимметричных системах шифрования, электронных подписях, идентификации и аутентификации, распределении

9

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

немного.	Â	основном упражнения		и задачи
оригинальные.
Параграфы		сборника	соответствуют
лекциям	и приложениям учебника			«Введение

в криптографию» (более точно, они соответствуют изданию [12], которое включает некоторые новые по сравнению с [11] разделы и приложения). Сохраняется терминология, предполагается знакомство с теоретическим материалом учебника. Думается однако, что условия абсолютного большинства задач будут понятны и для читателя,

studfiles.net

Задания и ответы.docx — Конкурс: «Криптография» (6-8 классы, информатика)

Задание №13.
Шифр Плейфера. Шифрование производится с помощью квадрата (или прямоугольника), в
который занесены в произвольном порядке буквы и конфигурация таблицы составляют в
совокупности секретный ключ. Для определённости возьмём прямоугольную таблицу размером
4*8, в качестве букв алфавита ­ кириллицу, а буквы расположим в алфавитном порядке. Так как
число русских букв 33, а число клеток ­ 32, исключим из таблицы букву Ё. Для того чтобы

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

znanio.ru

1.2. Основные задачи криптографии.

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

• государственная тайна;

• военная тайна;

• коммерческая тайна;

• юридическая тайна;

• врачебная тайна и т. д.

Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:

• имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;

• имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.

1.3 Выводы по разделу 1.

Криптография — это набор методов защиты информационных взаимодействий от отклонений от их нормального, штатного протекания, вызванных злоумышленными действиями различных субъектов, методов, базирующихся на секретных алгоритмах преобразования информации, включая алгоритмы, не являющиеся собственно секретными, но использующие секретные параметры. Исторически первой задачей криптографии была защита передаваемых текстовых сообщений от несанкционированного ознакомления с их содержанием, что нашло отражение в самом названии этой дисциплины, эта защита базируется на использовании «секретного языка», известного только отправителю и получателю, все методы шифрования являются лишь развитием этой философской идеи. С усложнением информационных взаимодействий в человеческом обществе возникли и продолжают возникать новые задачи по их защите, некоторые из них были решены в рамках криптографии, что потребовало развития принципиально новых подходов и методов.

2. Криптографические средства защиты.

1. Криптографическими средствами защиты называются специальные средства и методы преобразования информации, в результате которых маскируется ее содержание. Основными видами криптографического закрытия являются шифрование и кодирование защищаемых данных. При этом шифрование есть такой вид закрытия, при котором самостоятельному преобразованию подвергается каждый символ закрываемых данных; при кодировании защищаемые данные делятся на блоки, имеющие смысловое значение, и каждый такой блок заменяется цифровым, буквенным или комбинированным кодом. При этом используется несколько различных систем шифрования: заменой, перестановкой, гаммированием, аналитическим преобразованием шифруемых данных. Широкое распространение получили комбинированные шифры, когда исходный текст последовательно преобразуется с использованием двух или даже трех различных шифров.

2.1 Принцыпы работы Криптосистемы.

Типичный пример изображения ситуации, в которой возникает задача криптографии (шифрования) изображён на рисунке №1:

Рис. №1

На рисунке № 1 А и В — законные пользователи защищённой информации, они хотят обмениваться информацией по общедоступному каналу связи. П — незаконный пользователь (противник, хакер), который хочет перехватывать передаваемые по каналу связи сообщения и попытаться извлечь из них интересную для него информацию. Эту простую схему можно считать моделью типичной ситуации, в которой применяются криптографические методы защиты информации или просто шифрование.

Исторически в криптографии закрепились некоторые военные слова (противник, атака на шифр и др.). Они наиболее точно отражают смысл соответствующих криптографических понятий. Вместе с тем широко известная военная терминология, основанная на понятии кода (военно-морские коды, коды Генерального штаба, кодовые книги, кодобозначения и т. п.), уже не применяется в теоретической криптографии. Дело в том, что за последние десятилетия сформировалась теория кодирования — большое научное направление, которое разрабатывает и изучает методы защиты информации от случайных искажений в каналах связи.

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

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

studfiles.net

1.2. Основные задачи криптографии.

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

• государственная тайна;

• военная тайна;

• коммерческая тайна;

• юридическая тайна;

• врачебная тайна и т. д.

Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:

• имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;

• имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.

1.3 Выводы по разделу 1.

Криптография — это набор методов защиты информационных взаимодействий от отклонений от их нормального, штатного протекания, вызванных злоумышленными действиями различных субъектов, методов, базирующихся на секретных алгоритмах преобразования информации, включая алгоритмы, не являющиеся собственно секретными, но использующие секретные параметры. Исторически первой задачей криптографии была защита передаваемых текстовых сообщений от несанкционированного ознакомления с их содержанием, что нашло отражение в самом названии этой дисциплины, эта защита базируется на использовании «секретного языка», известного только отправителю и получателю, все методы шифрования являются лишь развитием этой философской идеи. С усложнением информационных взаимодействий в человеческом обществе возникли и продолжают возникать новые задачи по их защите, некоторые из них были решены в рамках криптографии, что потребовало развития принципиально новых подходов и методов.

2. Криптографические средства защиты.

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

2.1 Принцыпы работы Криптосистемы.

Типичный пример изображения ситуации, в которой возникает задача криптографии (шифрования) изображён на рисунке №1:

Рис. №1

На рисунке № 1 А и В — законные пользователи защищённой информации, они хотят обмениваться информацией по общедоступному каналу связи. П — незаконный пользователь (противник, хакер), который хочет перехватывать передаваемые по каналу связи сообщения и попытаться извлечь из них интересную для него информацию. Эту простую схему можно считать моделью типичной ситуации, в которой применяются криптографические методы защиты информации или просто шифрование.

Исторически в криптографии закрепились некоторые военные слова (противник, атака на шифр и др.). Они наиболее точно отражают смысл соответствующих криптографических понятий. Вместе с тем широко известная военная терминология, основанная на понятии кода (военно-морские коды, коды Генерального штаба, кодовые книги, кодобозначения и т. п.), уже не применяется в теоретической криптографии. Дело в том, что за последние десятилетия сформировалась теория кодирования — большое научное направление, которое разрабатывает и изучает методы защиты информации от случайных искажений в каналах связи.

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

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

studfiles.net

Задачи по криптографии – больше не помеха идеальной успеваемости

Очень часто для того, чтобы преуспеть в своей специальности в будущем, вовсе не обязательно идеально разбираться во всех дисциплинах, которым учат в ВУЗе. Намного важнее уделять много внимание предметам, которые непосредственно связаны со специальностью.

И криптография, какой бы интересной для кого-то она не была, иногда просто способствует расфокусированию внимания студента. Задачи с ключами, шифрами и сложными алгоритмами выполнения и решения, обычно, интересны далеко не всем. Если учащийся не собирается связать карьеру с данной наукой, конечно. Но от домашнего задания, как известно, никто не освобожден.

Где могут помочь с криптографией?

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

Студенчество сравнительно недавно открыло для себя удивительный вариант решения затруднений с учебой – это работа со специализированными образовательно-информационными сервисами. Их преимущества поразительны, вот лишь некоторые из них:

• высокая надежность и порядочность;
• возможность узнать отзывы пользователей сервиса об их услугах;
• студент может сам приехать в их филиал;
• задача может быть выполнена за считанные минуты;
• для специалистов сервиса не существует понятия «сложно»;
• цена за решение домашнего задания будет очень низкой.

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

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

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

Как побороть криптографию и сэкономить средства?

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

Найти помощь по заданиям от аспирантов и, даже преподавателей по криптографии, можно именно в специальных сервисах. Ни один фрилансер не будет заботиться о финансовом положении студента – это факт. К тому же, узнать об образовании такого независимого работника крайне сложно.

Наш сервис – ваш помощник и друг

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

Сотрудничество с нами – это всегда отличная идея, идеальная инвестиция в собственное образование.

matematiku5.ru

Юрий Лифшиц | Курс «Современные задачи криптографии»

Лекции Лекция 1: Основные протоколы: разделение секрета, привязка к биту, подбрасывание монетки. Лекция 2: Византийское соглашение, покер по телефону. Лекция 3: Электронные выборы Лекция 4: Электронные деньги Лекция 5: Введение в нулевое разглашение Лекция 6: Нулевое разглашение для класса NP Лекция 7: Забывчивая передача данных, проверяемое разделение секрета Лекция 8: Многосторонние секретные вычисления Лекция 9: Псевдослучайные генераторы Лекция 10: Псевдослучайные функции Конспекты 20 сентября — Влад Кудинов 27 сентября — Алексей Диевский 4 октября — Алексей Богатов 11 октября — Васильев Виктор 18 октября — Паша Никитин 25 октября — Вася Столбов 1 ноября — Егор Елизаров 8 ноября — Наташа Валландер 15 ноября — Никита Афанасенко 22 ноября — Тимофей Брыксин 29 ноября — Алексей Федоров 6 декабря — Алексей Калюкин 13 декабря — Илья Сергей

Темы для семинара Тема 1: Блочные шифры Источники: Goldwasser-Bellare, глава 4; Rogaway-Bellare, глава 3 Докладчик: Дмитрий Прокашев, Презентация не сдана! Тема 2: Односторонние функции с секретом Источники: Goldwasser-Bellare, глава 2. Докладчик: Дмитрий Антипов, Презентация не сдана! Тема 3: Криптосистема RSA Источники: Goldwasser-Bellare, глава 7; Rogaway-Bellare, глава 10 Докладчик: Евгений Сеппель, Презентация PPT Тема 4: Хэш функции Источники: Goldwasser-Bellare, глава 8; Rogaway-Bellare, глава 6 Докладчик: Антон Нестеров, Презентация PPT Тема 5: Аутентификация сообщений Источники: Goldwasser-Bellare, глава 8; Rogaway-Bellare, глава 7 Докладчик: Ольга Евтифеева, Презентация PPT Тема 6: Цифровая подпись Источники: Goldwasser-Bellare, глава 9; Rogaway-Bellare, глава 12 Докладчик: Алексей Тукнов, Презентация PPT Тема 7: RC5 Источники: Презентация, Статья, Список ссылок, Докладчик: Сергей Винк, Презентация не сдана! Тема 8: Введение в стеганографию Источники: Information hiding Докладчик: Антон Басков, Презентация PPT Тема 9: Квантовая криптография Источники: Samuel J. Lomonaco lecture on Quantum Cryptography Докладчик: Алина Головдинова, Презентация PPT Тема 10: Криптоанализ RSA Источники: Статья Докладчик: Николай Гравин, Презентация PPT Тема 11: Криптоанализ блочных шифров Источники: Статья Докладчик: Дмитрий Ширяев, Презентация PPT

yury.name

ПРИЛОЖЕНИЕ Избранные задачи олимпиад по криптографии. 25 этюдов о шифрах



ПРИЛОЖЕНИЕ Избранные задачи олимпиад по криптографии. 25 этюдов о шифрах Jeremy Fuller

Online Status

Show your status to all

Auto Updates

Keep up to date

Notifications

Do you need them?

API Access

Enable/Disable access

• New sale! + $249

  3 min ago

• New sale! + $129

  50 min ago

• New sale! + $119

  2 hours ago

• New sale! + $499

  3 hours ago

• New sale! + $249

  26 hours ago

• Product Purchase — $50

  28 hours ago

• New sale! + $119

  29 hours ago

• Paypal Withdrawal — $300

  37 hours ago

• New sale! + $129

  39 hours ago

• New sale! + $119

  45 hours ago

• New sale! + $499

  46 hours ago

librolife.ru