Рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность»

1 2 3 4 5 6 7 8 9 ... 18

Ім'я файлу: Рожков_Ниссенбаум_ТЧМК_лекции.doc
Розширення: doc
Розмір: 2493кб.
Дата: 13.04.2023
скачати
Пов'язані файли:
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ.docx
Конфуцианство.doc
ZMIST2.docx
1111 Методологія та методи наукового дослідження.ppt
Кримінально- процесуальне право.docx
Історичне есе на тему Соціально-економічне та політичний розвито
Історична довідка про Тараса Шевченка.docx
службова Никифорову.docx
Zubchaste_koleso.docx

ДОДАТОКЕМіС2.docx
ФБ_КП_ЦарікС.О._(fixed) (1).doc
21.pdf
Хоменко Поради батькам при запинках в мовленні у дітей.docx
Реферат на тему_Українські та міжнародні організації зі стандарт
Реферат на тему_Українські та міжнародні організації зі стандарт
1 ENDOCRINE SYSTEM.docx
Задачи похідна.docx
цуацаца.rtf
case-tehnologiya-rozroblennya-vimog-do-programnogo-zabezpechenny
gosudarstvennoe_i_municipalnoe_upravlenie-shpargal.pdf
текст доклада ъ.docx
Bedyukh_Yuliya_Oleksandrivna_Mm-21.docx.pdf
Типи календарів.docx
курсова психологія.doc
Реферат 2629.docx
пояснююча записка111.doc
Зміст практики.doc
Основи автоматики. Лекція 2.docx
Особливості організації інклюзивного навчання.docx
Практичне завдання_1.docx
Контрольні запитання ЛР № 8.docx
2 питання.rtf
Документ Microsoft Office Word.docx
kazedu_179257.docx
Курсова_робота_Пасевич_Аліна,_ЮД_046,_1_курс.docx
1 (1).docx
конспект заняття.docx
d71d73ee90c56_1797715607_1707122403.doc

А.В. Рожков

О.В. Ниссенбаум

Теоретико-числовые методы в криптографии

Учебное пособие

Тюмень 2007

Аннотация.

Рассмотрены теоретико-числовые и алгебраические основы криптографии, криптографические алгоритмы, построенные на теоретико-числовых и теоретико-сложностных проблемах, такие как RSA, Диффи-Хеллмана, Эль-Гамаля. Рассмотрена проблема генерации простых чисел, приведены вероятностные тесты на простоту и алгоритмы генерации доказуемо простых чисел с математическим обоснованием. В третьей главе приведены алгоритмы, криптоанализа асимметричных криптосистем – алгоритмы факторизации и дискретного логарифмирования – с оценками сложности. Изложение сопровождается примерами. В пособие включены также рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность» ТюмГУ, и задания для самостоятельного выполнения с ответами к ним.

ПРЕДИСЛОВИЕ

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

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

В первой главе содержатся основы теории чисел и криптографические алгоритмы, базирующиеся на теоретико-числовых принципах. Читателю, знакомому с теорией чисел, можно ограничиться чтением шестого и седьмого пунктов из §3, и продолжить чтение начиная с §5. Указанные разделы содержат описания вероятностных тестов на простоту, криптосистем, основанных на теоретико-числовых принципах (таких как RSA, Диффи-Хеллмана), методы построения доказуемо простых чисел. Описания криптосистем сопровождаются доказательствами их стойкости.

Вторая глава посвящена алгебраическим основам теории чисел и таким алгебраическим структурам как кольца многочленов. На кольцах и полях многочленов построены некоторые криптосистемы, в частности AES.

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

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

В Приложении 1 приведена таблица простых чисел и порождающих элементов циклических групп целых чисел, им соответствующих.

Приложение 2 представляет собой рабочую программу курса «Теоретико-числовые методы в криптографии», читаемого студентам специальности 090102 «Компьютерная безопасность» в Тюменском государственном университете и включает в себя в том числе вопросы к экзамену.

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

1 2 3 4 5 6 7 8 9 ... 18

скачати