XXII Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Математика как инструмент работы кодировщиков

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Радулов И.В. 1

---

1МОУ гимназия №46

Моргунова М.И. 1

---

1МОУ гимназия №46

Работа в формате PDF

1.7 MB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Введение

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

На телефоне моих родителей установлено много мобильных приложений, это и госуслуги и Mir Pay и … Но если будет взломана информация, то тогда может случиться непоправимое, и тогда к личной информации будут иметь доступ мошенники.

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

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

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

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

Цель проекта

Показать роль математики в создании надежной защиты информации.

Задачи проекта

1. Создать буклет(стенд) «Криптографические способы шифрования информации».

2. Создать буклет «Памятка по защите личных данных».

3. Рассказать о значимости математики в шифровании.

4. Изучить историю криптографии.

5. Показать разные виды способы шифрования информации.

1.Что такое криптография?

Криптография — наука о способах шифрования информации с целью защиты ее от незаконного использования.

Первые методы криптографии сейчас считаются довольно простыми. Например, у римского императора Гая Юлия Цезаря был собственный код: буква заменялась на букву, следующую за ней третьей в алфавите. То есть, по коду Цезаря в русском алфавите «А» меняется на «Г», «Б» — на «Д» и так далее.

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

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

1.1 Основы криптографии

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

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

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

Основные понятия криптографии

1.2 Зачем нужна криптография?

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

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

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

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

2. История криптографии

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

2.1 Стеганография

Стеганография — это техника скрытия самого сообщения, которая появилась, вероятно, в одно время с криптографией и по аналогичным причинам.

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

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

2.2 Шифры подстановки

Шифр подстановки — это метод шифрования, в котором элементы исходного открытого текста заменяются зашифрованным текстом в соответствии с некоторым правилом. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее.

Шифр Полибия — это один из самых первых известных шифров подстановки, названный в честь греческого историка Полибия.

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

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

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

Когда два алфавита, оригинальный (или алфавит открытого сообщения) и шифроалфавит, расположены таким образом, шифрование любого сообщения сводится к замене букв из первого алфавита буквами из второго. Ключ к такому шифру получает название по букве, соответствующей зашифрованному значению буквы А (первой буквы оригинального алфавита). В нашем случае это буква D. Известное выражение AVE CAESAR («Радуйся, Цезарь») будет зашифровано как DYH FDHVDU. Обратно, если зашифрованное сообщение выглядит как WUHH, то расшифрованный текст будет TREE («Дерево»). В случае с только что описанным шифром Цезаря криптоаналитик, который перехватил сообщение и знает используемый алгоритм, но не знает ключ к шифру, должен будет перебрать все возможные сдвиги алфавита, пока не найдет сообщение, имеющее смысл. Для этого он должен будет, в худшем случае, попробовать все возможные ключи или сдвиги. В алфавите, состоящем из n букв, существует n возможных сдвигов, то есть n ключей.

Как связанны шифр Цезаря и модульная арифметика? Для ответа на этот вопрос, мы составим таблицу из стандартного английского алфавита и алфавита, который сдвинут на три буквы, добавив титульный ряд из 26 подряд идущих чисел.

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

Заметим, что 3 — ключ нашего шифра. Итак, наша функция записывается так

C(х) = (х + 3) (mod 26),

где х — изначальная позиция, а С(х) — зашифрованная позиция. Теперь достаточно подставить вместо буквы ее числовое значение и применить трансформацию.

В качестве примера возьмем слово “PLAY” и зашифруем его.

Буква Р стоит на позиции 15, С(15) = 15 + 3   18 (mod 26), а число 18 соответствует букве S.

Буква L стоит на позиции 11, С(11) = 11 + 3   14 (mod 26), а число 14 соответствует букве О.

Буква А стоит на позиции 0, С(0) = 0 + 3   3 (mod 26), а число 3 соответствует букве D.

Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27   1 (mod 26), а число 1 соответствует букве В.

Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.

В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)] выражается формулой

С(х) = (х + k) (mod n),

где n — длина алфавита (26 в английском алфавите), a k — ключ, используемый в данном шифре.

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

С^-1(х) = (х — k) (mod n).

2.3 Современная криптография-алгоритм RSA

В августе 1977 г. Мартин Гарднер — знаменитый американский писатель и популяризатор науки — озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После того, как он объяснил принцип системы шифрования с открытым ключом, Мартин показал само зашифрованное сообщение и открытый ключ N, используемый для зашифровки этого сообщения:

Гарднер призвал читателей попытаться расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для расшифровки нужно разложить число N на простые множители р и q. Более того, он назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто хотел бы побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института.

Правильный ответ получили лишь через 17 лет. Он был получен в результате сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Алгоритм, представленный Гарднером, известен как RSA — буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы в упрощенной форме.

2.4 Подробнее об алгоритме RSA

Основы алгоритма RSA:

• Количество натуральных чисел, меньших n и взаимно простых с n, называется функцией Эйлера и обозначается как ф(n).

• Если n = p∙q, где р и q — простые числа, то ф(n) = (р — 1)(q — 1).

• Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то а^p-1  1 (mod р).

• Согласно теореме Эйлера, если НОД (n, а) = 1, то а^ф(n)  1 (mod n).

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

Сначала Джеймс вычисляет значение n путем умножения двух простых чисел р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(n), е) = 1. Напомним, что ф(n) = (р — 1)(q — 1). Данные, которые являются открытыми, — это значение n и значение е (ни при каких обстоятельствах нельзя выдавать значения р и q). Пара (n, е) является открытым ключом системы, а значения р и q называются RSА-числами. Затем Джеймс вычисляет единственное значение d по модулю ф(n), которое удовлетворяет условию d∙е = 1(mod ф(n)), то есть d является обратным элементом к числу е по модулю ф(n). Мы знаем, что обратный элемент существует, потому что НОД (ф(n), е) = 1. Это число d является закрытым ключом системы. Со своей стороны, Питер использует открытый ключ (n, е) для шифрования сообщения М с помощью функции М = m^e (mod n). Получив сообщение, Джеймс вычисляет M^d = (m^e)^d (mod n), а это выражение эквивалентно M^d = (m^e)^d = m (mod n), что свидетельствует о возможности расшифровать сообщение.

Теперь мы применим эту процедуру к конкретным числовым значениям.

Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)∙(11—1) = 20.

Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).

• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7∙3   1 (mod 20).

• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:

9⁷ = 4 782969   15 (mod 33).

Зашифрованное сообщение имеет вид «15». Питер посылает его нам.

Джеймс получает сообщение «15» и расшифровывает его следующим образом:

15³ = 3375   9 (mod 33).

Сообщение расшифровано правильно.

Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:

204²³⁵   34 (mod 391).

Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.

2.5 Почему мы можем доверять алгоритму RSA

Потенциальный шпион располагает значениями n и е, потому что они являются открытыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый ключ. Как мы показали в предыдущем примере, значение d получается из n и е. Чем же обусловлена безопасность? Напомним, что для построения d необходимо знать ф(n) = (р — 1)(q — 1), в частности, р и q. Для этого «диостаточно» разложить n на простые множители р и q. Проблема для шпиона заключается в том, что разложение большого числа на простые множители является медленным и трудоемким процессом. Если n достаточно большое (состоящее более чем из 100 цифр), не существует известных способов нахождения р и q за разумное количество времени. В настоящее время простые числа, используемые для шифрования чрезвычайно конфиденциальных сообщений, состоят более чем из 200 цифр.

2.6 Криптография будущего. Квантовая криптография

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

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

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

В идеальном случае длина ключа равна длине сообщения. Если нужно передать пару предложений, например, в 200 символов, то с учетом того, что каждый символ занимает 1 байт, или 8 бит, нужно передать 1600 бит. Алиса берет одиночные фотоны, кодирует в них бит и отправляет. Конечно, фотоны летят не через идеальную, а через реальную среду и претерпевают потери в оптоволокне. Но мы помним, что каждый фотон несет уникальный бит информации. Это значит, что, если он потерялся, найдется другой фотон, который дойдет до получателя, будет успешно задетектирован и записан.

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

Сейчас предельное расстояние одного пролета квантовой криптографии в реальных условиях составляет 100–130 километров. В квантовой сети, соединяющей Пекин и Шанхай, 32 промежуточных доверенных узла. А квантовая память и квантовый повторитель позволят сделать эти узлы недоверенными. 

В 2019 — начале 2020 года группа Михаила Лукина в Гарварде совершила большой прорыв, показав квантовую память с тремя параметрами, вышедшими на уровень, необходимый для квантового повторителя. Это параметр времени хранения информации, параметр fidelity, то есть качества, а также вероятность срабатывания, то есть сколько попыток придется сделать, прежде чем пройдет успешная запись считывания. Раньше казалось, что параметры квантовой памяти противоречивы и никогда не смогут работать одновременно. Сейчас первые образцы на центрах окраски в наноалмазах сумели получить квантовую память.

2.7 Криптография и QR код. Как он работает

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

Чтобы закодировать фразу, нам нужно разделить каждое слово на группы по 2 буквы, затем присвоить им номера и перекодировать в 11-битный двоичный код (то есть таким образом, чтобы каждые 2 буквы состояли из последовательности из 11 нулей и единиц. Если в слове нечетное количество букв, то последняя буква будет закодирована 6-битным кодом, то есть будет состоять из 6 нулей и единиц). Например, возьмем слово HELLO. После разбивания на слоги это будет HE LL O. В 11-битном двоичном коде это будет выглядеть как 01100001011 01111000110 011000. А если написать все вместе, то 0110000101101111000110011000.

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

3. Заключение. Выводы

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

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

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

Список используемой литературы

1.[Электронный ресурс]:https://practicum.yandex.ru/blog/chto-takoe-kriptografiya/

2.[Электронный ресурс]: https://blog.skillfactory.ru/glossary/kriptografiya/

3.[Электронный ресурс]: https://www.symmetron.ru/articles/zachem-nuzhna-kriptografiya/

4.Жуан Гомес МИР МАТЕМАТИКИ. МАТЕМАТИКИ, ШПИОНЫ И ХАКЕРЫ.

КОДИРОВАНИЕ И КРИПТОГРАФИЯ

Приложение

Исследовательская часть

Анкетирование 1:

рис.1

рис2

рис.3

рис.4

рис.5

рис.6

рис.7

рис.8

Анализ анкетирования:

Люди в современном мире часто встречаются с кражей персональных данных. Но несмотря на это, не достаточно хорошо их защищают, используя короткие пароли для своих интернет аккаунтов, не меняя их с течением времени.

Проверочная работа с QR-кодами:

Рис.10 рис.11 рис.12

Опрос по итогам проверочной работы:

рис.13

рис.14

рис.15

рис.16

Анализ опроса:

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