Содержание курса по выбору

В этом параграфе представлен теоретический материал по занятиям на темы «Введение. История развития». «Простейшие шифры». «Система RSA», «Основы теории сравнений», конспекты 3-х занятий на темы банковские карты, штрихкоды, QR-коды и список задач к занятию решение олимпиадных задач.
Занятие 1. Введение. История криптографии.
Цель урока: познакомить с историей развития криптографии
Криптография - это наука, которая изучает математические методы защиты информации и методы преобразования, которые обеспечивают конфиденциальность и достоверность.
В истории криптографии можно разделить на четыре этапа:
• наивный,
• формальный,
• научный,
• компьютерный.
История криптографии насчитывает более тысячи лет. Уже в исторических документах древних цивилизаций - Индии, Египта, Китая, Месопотамии - можно найти информацию о системах и методах создания букв шифра. В наивной криптографии (до начала 16-го века) примитивные методы обычно используются для вовлечения врага в содержание зашифрованных текстов. На начальном этапе для защиты информации использовались методы кодирования и стеганографии, относящиеся к криптографии, но не идентичные. Большинство используемых шифров были сокращены до перестановки или замены.
Одним из первых известных примеров является шифр Цезаря, в котором каждая буква исходного текста заменяется другой буквой, разделенной определенным количеством цифр в алфавите.
Другая цифра, Полибийский квадрат, авторство которого приписывается греческому писателю Полибию, представляет собой обычную моноалфавитную замену, выполняемую с использованием квадратичной таблицы, случайно заполненной алфавитом (для греческого алфавита размер составляет 5x5). ). Каждая буква исходного текста заменяется буквой в квадрате внизу.
Особенности уровня формальной криптографии, примеры шифров этого уровня. (Конец XV - начало 20 века) связан с появлением шифров, которые формализованы и относительно устойчивы к ручному криптоанализу.
Это произошло в европейских странах во времена Ренессанса, когда развитие науки и коммерции подняло спрос на надежные способы защиты информации. Важную роль на этом этапе играет итальянский архитектор Леон Баттиста Альберти, который одним из первых предложил замену несколькими буквами. Этот код, названный в честь дипломата 16 века. Блез Вижинера заключался в последовательном «сложении» букв исходного текста с ключом. Его работа «Трактат о шифре» (1466) считается первой научной работой по криптологии.
Одной из первых печатных работ, в которой алгоритмы шифрования, известные в то время, были обобщены и сформулированы, является работа Polygraphia (1508) немецкого аббата Иоганна Триема. У него есть два небольших, но важных открытия:
• Метод заполнения многогранного квадрата (первые позиции заполнены легко запоминаемым ключевым словом, остальные заполняются оставшимися буквами алфавита)
• Шифрование буквенных пар (биграммы).
Простой, но последовательный метод замены нескольких букв (замена Bigram) - это шифр Playfer, созданный в начале 19-го века. Чарльз Уитстон. У Уитстона также есть главное усовершенствование - шифрование двойных квадратов. Шифры Playfer и Wheatstone использовались до Первой мировой войны, потому что было трудно оставить их для ручного криптоанализа.
В XIX в. Голландец Керхофф сформулировал основное требование к криптографическим системам, которое остается актуальным на сегодняшний день: секретность шифров должна основываться на секретности ключа, а не на алгоритме.
Наконец, последнее слово в до-научной криптографии, которая предложила еще большую криптографическую силу и позволила автоматизировать процесс шифрования, стало роторными криптосистемами. Одной из первых таких систем была механическая машина, изобретенная в 1790 году Томасом Джефферсоном, будущим президентом Соединенных Штатов.
Многоалфавитный обмен с использованием роторной машины осуществляется путем изменения относительного положения роторных роторов, каждый из которых выполняет «сшитую» замену. Практическое распространение роторных машин получили только в начале XX века. Одной из первых практических машин была немецкая Enigma, которая была разработана в 1917 году Эдвардом Хебернером и усовершенствована Артуром Кирхом.
Роторные системы являются воплощением формальной криптографии, потому что очень надежные шифры могут быть внедрены относительно легко. Успешная крипто-атака на роторные системы стала возможной только с появлением компьютеров в начале 1940-х годов.
Характеристика этапа Научной криптографии, примеры шифров данного этапа.
Появление криптосистем с строгим математическим обоснованием криптографической стойкости является основной чертой научной криптографии (1930–60-е годы).
Начало 30-х годов Разделы математики, которые составляют научную основу криптологии, были окончательно сформированы:
• теория вероятностей и математическая статистика,
• общая алгебра,
• теория чисел
• теория алгоритмов,
• теория информации
• кибернетика.
Важным шагом в развитии криптографии стала работа Клода Шеннона «Теория связи в секретных системах» (1949), в которой были обобщены научные основы криптографии и криптоанализа. С тех пор концепция криптологии (от греческого cryptos - secret и logos - message) была введена в науку преобразования информации для обеспечения ее секретности.
Стадия развития криптографии и криптоанализа до 1949 года упоминалась как преднаучная криптология. Шеннон ввел понятия «дисперсия» и «смешивание» и установил способность создавать произвольно сильные криптосистемы. В 1960-х гг. Ведущие криптографические школы разработали блочные шифры, которые являются еще более надежными по сравнению с роторными криптосистемами.
Характеристика этапа Компьютерной криптографии, примеры шифров данного этапа.
Компьютерная криптография (с 1970-х годов) обязана своим появлением компьютерным инструментам, способным реализовывать криптосистемы, которые предлагают криптостойкость, которая на несколько порядков превышает «ручное» и «механическое» шифрование при высоких скоростях шифрования.
Первым классом криптосистем, практическое применение которых стало возможным с появлением мощных и компактных вычислительных инструментов, стали блочные шифры.
1978 год. Был разработан и принят американский стандарт шифрования DES. Появление DES также обогатило криптоанализ: несколько новых типов криптоанализа (линейный, дифференциальный и т. Д.) Были разработаны для атаки на американский алгоритм, практическая реализация которого стала возможной только с появлением мощных компьютерных систем.
Середина 70-х годов. В двадцатом веке в современной криптографии произошел настоящий прорыв - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами.
Отправной точкой является работа, опубликованная в 1976 году Уитфилдом Диффи и Мартином Хеллманом под названием «Новые направления в современной криптографии»

. Сначала были сформулированы принципы обмена зашифрованной информацией без обмена секретным ключом. Тем не менее, Ральф Меркли подошел к идее асимметричных криптосистем. Несколько лет спустя Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, основанную на проблеме факторизации больших простых чисел. Асимметричная криптография открыла несколько новых областей применения одновременно, в частности электронная цифровая подпись (EDS) и системы электронных денег [48].
В 1980-х и 1990-х годах появились совершенно новые направления криптографии:
• вероятностное шифрование
• квантовая криптография и др.
В тот же период были разработаны шифры Nephistel (SAFER, RC6 и т. Д.), А в 2000 году, после открытого международного конкурса, был принят новый национальный стандарт шифрования США, DES, [48].
Контрольные вопросы
1. Назовите и охарактеризуйте основные этапы развития криптографии?
2. Дайте определение криптологии, криптографии и криптоанализа?
3.Назовите разделы математики, являющиеся научной основой криптологии?
4. Каких выдающихся криптографов вы знаете?
Занятие 2. Простейшие шифры
Цель урока: ознакомление обучающихся с основными простейшими шифрами
Шифры замены: шифр Цезаря,
1. Шифр Цезаря. (I век до н. э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому алфавиту он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е, ...; затем под ним выписывался тот же алфавит, но с циклическим сдвигом на 3 буквы влево:
Попробуйте прочитать, что здесь написано?
Ответ: У Центра Азии.
Мы очень быстро разгадали. Это связано с тем, что шифр имеет очень низкую криптостойкость.
Шифры перестановки: Шифр сцитала, Шифр поворотная решетка
Занятие 5. Банковские карты
Цель урока: изучить методы защиты информации на банковских карточках
МОТИВАЦИОННЫЙ ЭТАП.
Рис. 1 Кредитная Diners Club карта 1951г.

Рис. 2 Современная кредитная карта Diners Club


История изготовления банковских карт началась еще в 1914 году в США. В то время были выпущены первые аналоги современных пластиковых карт, хотя они были сделаны из картона и представляли собой не что иное, как кредитную записку клиента.
В 1928 году целлюлоза была заменена более надежным материалом - металлом, что на примитивном уровне позволило автоматизировать обработку данных. Основание Diners Club в 1949 году ознаменовало первую по-настоящему массовую систему платежных карт в мире. Автором идеи был американец Фрэнк Макнамара. В 1950 году ему удалось убедить несколько ресторанов принимать безналичные платежи с помощью личных, гарантированных кредитных карт, которые Макнамара раздавал своим лучшим клиентам.
Дебетовые и кредитные карты, предлагаемые крупными банками и универмагами, на самом деле определяются серией наборов чисел, которые рассчитываются и проверяются с использованием одного и того же алгоритма на основе модульной арифметики, которую мы уже знаем.
Большинство карт имеют 16 цифр от 0 до 9. Числа сгруппированы в четыре цифры для удобства чтения. Для наших целей мы будем обозначать их следующим образом:
ABCD EFGH IJKL MNOP
Каждая группа номеров кодирует определенную информацию: первая группа (ABCD) идентифицирует банк (или другую организацию, предоставляющую услуги).
Каждый банк имеет свой номер, который может варьироваться в зависимости от континента, марки карты и условий. Пятая цифра (E) соответствует типу карты и указывает, какое финансовое учреждение управляет счетом.
Следующие десять цифр (FGH IJKL MNO) являются уникальным идентификатором для каждой карты. Эти цифры относятся к номеру счета клиента, уровню карты (Classic, Gold, Platinum и т. Д.), А также к пределу кредитования, сроку действия и процентным ставкам в зависимости от типа кредита.
Наконец, контрольная цифра (P) связана с предыдущими цифрами в соответствии с лунным алгоритмом.
В России первые шесть цифр номера карты (ABCDEF) являются банковским идентификационным номером (БИН). Первая из этих шести цифр указывает на платежную систему. Например, у карт Visa первая цифра — 4, у MasterCard — 5.
Рис. 3
Седьмая и восьмая цифры номера карты (GH) уточняют, в рамках какой программы банка была выпущена карта. Следующие семь цифр (IJKL MNO) идентифицируют непосредственно карту. Последняя цифра (Р) — контрольная [18].
ЭТАП УСВОЕНИЯ ПОНЯТИЙ.
ОРИЕНТИРОВОЧНЫЙ ЭТАП.
Алгоритм Луна назван так в честь Ганса Питера Луна, немецкого инженера, разработавшего его. Для 16-значной карты этот алгоритм работает следующим образом.
1. Каждая цифра в нечетной позиции, начиная с первого числа слева, умножается на два. Если результат больше 9, мы добавляем обе цифры этого двузначного числа (или соответственно вычитаем 9 из них).
Например, если мы получим 18, сложение чисел даст 1 + 8 = 9, а вычитание даст 18-9 = 9.
2. Затем мы добавляем все полученные таким образом результаты, а также четные номера позиций (включая последнюю контрольную цифру).
3. Если окончательная сумма кратна 10 (то есть ее значение равно нулю по модулю 10), номер карты действителен. Обратите внимание, что это последняя контрольная цифра, которая дает общий множитель 10.
Задача 1. Проверьте по алгоритму Луна, является ли карта 2324165843142536 действительной?
Решение. по алгоритму Луна имеем:
2∙2 =4; 2∙2 = 4; 1∙2 = 2; 5∙2=10 =1 + 0 = 1; 4∙2 = 8 =; 1∙2 = 2; 2∙2 =4; 3∙2 = 6
Далее найдем сумму результатов и цифр на четных позициях:
3 + 4 + 6 + 8 + 3 + 4 + 5 + 6 = 39
4 + 4 + 2 + 1 + 8 + 2 + 4 + 6 = 31
39 + 31 = 70
Результат равен 70, это число кратно 10. Следовательно номер карты является действительным.
Алгоритм Луна можно применить другим способом: номер карты ABCD EFGH IJKL MNOP является правильным, если удвоенная сумма цифр на нечетных позициях и сумма цифр на четных позициях плюс количество цифр на нечетных позициях, которые больше, чем 4, кратно 10. Это правило записывается так:
2 (A + C + E + G + 1 + К + М + О) + (B + D + F + H + J + L + N + P) + (количество цифр на нечетных позициях, которые больше, чем 4) = 0 (mod 10).
Примените это правило к предыдущему примеру:
1234 5678 9012 3452
2(1+3+5+7+9+1+3+5) +(2+4+6+8+0+2+4+2) +4=100
100 кратно 10,
Следовательно, номер кредитной карты является действительным, и показали, что на первый взгляд случайные номера карт соответствуют строгому математическому стандарту.
Задача 2. Можно ли восстановить цифру, отсутствующую в номере карты? Да, если иметь дело с действительной кредитной картой. В номере 4539 4512 03Х8 7356 найти Х.
Решение.
Цифры, стоящие на нечетных позициях 4-3-4-1-0-Х-7-5, умножить на 2.
Т. Е 4∙2=8; 3∙2=6; 4∙2=8; 1∙2=2; 0∙2=0; Х∙2=2Х; 7∙2=14=5; 5∙2=10=1
Сложить цифры, стоящие на четных позициях, и получившиеся цифры на нечетных, получим:
(5+9+5+2+3+8+3+6) + 8+6+8+2+0+2X+5+1=30+41+2X=71+2X
Число 71+2X должно быть кратно 10
Если значение Х ≤4, то для таких Х: 71+2Х никогда не будет кратно 10