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

Старт в науке

Роль комбинаторики в цифровой безопасности

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

Волынский Г.С. 1

---

1Гимназия №3

Белова Т.А. 1

---

1Гимназия №3

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

1.2 MB

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

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

Введение

Цель: выяснить, как комбинаторика помогает в сохранении конфиденциальности информации.

Объект исследования – человек и информация

Предмет исследования – комбинаторика, криптография, WordPasswordRecoveryLastic, PassFab, PasscoverySuite, компьютер.

Задачи:

Исследовать, что такое комбинаторика и как она возникла.

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

Понять, как комбинаторика применяется в цифровой безопасности.

На основе экспериментов проследить зависимость цифровой безопасности от комбинаторики

Гипотеза: цифровая безопасность никак не может существовать без комбинаторики.

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

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

Что такое комбинаторика?

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

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

Перестановки

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

Самым простым примером перестановокбудет вопрос: сколько вариантов существует записать трёхзначное число из цифр 1,2,3, чтобы они не повторялись. В данном случае можно просто перебрать все возможные варианты (123; 132; 213; 231; 312; 321) их получится шесть. В данном случае у нас получилось 3 возможных варианта, и у каждого из этих вариантов есть 2 варианта дальнейшего развития, поэтому 3*2 = 6. Такие задачи можно решать с помощью иллюстрирования их таблицами или с помощью графов. В теории графовграф перестановки — это граф, вершины которого соответствуют элементам перестановки, а рёбра представляют пары элементов, следование которых стало обратным после перестановки. Графы перестановки можно определить геометрически как графы пересечений отрезков, концы которых лежат на двух параллельных прямых. Различные перестановки могут дать один и тот же граф перестановки.

Рисунок 1. Графы

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

Рисунок 2. Пример регулярного дерева.

Однако для более сложных задач применяют факториал числа. Число всевозможных перестановок n элементов обозначается P_n. Как это будет ниже показано, оно равно произведению всех натуральных чисел от 1 до n. Для краткости это произведение обозначают символом n! (читается "эн факториал")

n! = 1 2 3 ...n.

Факториал определён только для целых неотрицательных чисел. 0! = 1(факториал 0 равен единице).

Сочетания

В комбинаторике сочетанием из n{\displaystyle n} по k{\displaystyle k} называется набор из k{\displaystyle k} элементов, выбранных из {\displaystyle n} n-элементного множества, в котором не учитывается порядок элементов.

Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, 3-элементные сочетания 2 и 3 ((нестрогие) подмножества, для которых k = 3{\displaystyle k=3}) из 6-элементного множества 1 (n = 6{\displaystyle n=6}) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов 1. Сочетания задаются формулой

Размещения

Пусть имеется nразличных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из n объектов по m, а их число равно

Пример всех размещений из n=3объектов (различных фигур) по m=2 - на картинке. Согласно формуле, их должно быть ровно = 3⋅ (3−2+1) = 3⋅2 = 6.

Рисунок 3. Размещения

Криптография

Криптография («криптос» - тайна, «графэйн» - писать) - наука о методах обеспечения:

Конфиденциальности (невозможности прочтения информации посторонним)

Аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.

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

Выборки с возвращением

Количество вариантов можно вычислить с помощью выборок с возвращением.

Рассмотрим случай, когда выборка может содержать какой-либо элемент более одного раза. Это - выборка с возвращением.

Пусть имеется n- буквенный алфавит. Сколько m-буквенных слов можно получить в этом алфавите?

Ответ очевиден, . Например, из пяти первых букв русского алфавита необходимо составить все трехбуквенные слова. Первую букву слова можно выбрать пятью способами, вторую и третью - тоже пятью, так как буква может быть выбрана повторно. Всего вариантов 5 × 5 × 5 = = 125.

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

Квантовый компьютер

Рисунок 4. Квантовый компьютер

Задачи комбинаторики в будущем, возможно, будет обрабатывать квантовый компьютер.

Квантовый компьютер — вычислительное устройство, которое использует явления квантовой механики (квантовая суперпозиция, квантовая запутанность) для передачи и обработки данных. Квантовый компьютер (в отличие от обычного) оперирует не битами (способными принимать значение либо 0, либо 1), а кубитами, имеющими значения одновременно и 0, и 1. Теоретически, это позволяет обрабатывать все возможные состояния одновременно, достигая существенного преимущества (квантового превосходства) над обычными компьютерами в ряде алгоритмов.

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

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

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

Хакерские атаки

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

Многие склонны думать, что типичный хакер представляет собой талантливого молодого самоучку или одиозного программиста, способного специальным образом модифицировать аппаратное или программное обеспечение, чтобы использовать его в целях, изначально не заложенных производителем. Но такой подход упрощает взгляд на проблему и не позволяет осмыслить все многообразие мотивов, которые побуждают хакеров к действиям. Если Вам нужна более подробная информация о хакерах, пожалуйста, ознакомьтесь с заметкой Венди Заморы «Under the hoodie: why money, power, and ego drive hackers to cybercrime» (Под капюшоном: почему деньги, власть и эгоизм толкают хакеров на преступление).

Хакерские атаки обычно имеют технический характер (как, например, вредоносная реклама, которая внедряет на компьютер опасные объекты в теневом режиме и не требует участия пользователя). Однако хакеры также могут прибегать к психологическим методам, чтобы обманны тм путем заставить пользователя открыть вредоносное вложение или предоставить конфиденциальные данные. Такие методы называют методами социальной инженерии.

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

Ботнеты
Программы-угонщики браузеров
DDoS-атаки
Программы-вымогатели
Руткиты
Троянские программы
Вирусы
Сетевые черви

Хакерство как феномен прошло путь от подростковой забавы до многомиллиардного бизнеса с развитой преступной инфраструктурой, позволяющей разрабатывать хакерские инструменты на заказ и продавать их амбициозным ворам, не лишенным денег, но обладающим меньшими техническими навыками (таких злоумышленников уничижительно называют «скрипткидди», поскольку они используют для нападения чужой программный код, не понимая механизма его действия). Лишь один из примеров таких инструментов – программа-вымогатель как услуга (RaaS).

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

Сложные задачи на комбинаторику

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

Задача 1:

Закодируем файл с паролем с минимальной длиной 1 и максимальной длиной 4 символа, все строчные латинские буквы(26 штук) и цифры(10 штук). Проверяем количество вариантов комбинаторной формулой. Для пароля длиной m символов количество вариантов .

Делаем таблицу в Excel:

Вывод:

В этой задаче уже никак не обойдёшься без понимания комбинаторики, знания её формул.

Задача 2:

Мы опросили людей, какой длины они обычно используют пароли, и считают ли они, что это надежно. 59% ответили, что считают 4 символа приемлемой длиной, 41% ответили, что их пароли более длинные.

Вывод:

Таким образом большинство считает, что пароль длинной в 4 символа нормальный для цифровой безопасности.

Но так ли это? Давайте убедимся над этим, проведя ряд экспериментов.

Эксперименты

Мы провели несколько экспериментов касательно взлома паролей.

Был создан файл в Word, после этого с помощью команды «Файл – Сведения – Защитить документ – Зашифровать с использованием пароля» установили пароль 1234. Проверили, что без пароля Word не открывает файл.

Мы установили 3 приложения для взлома паролей Word:

Word Password Recovery Lastic[ CITATION 1 \l 1033 ];

PassFab [ CITATION 2 \l 1033 ];

Passcovery Suite [ CITATION 3 \l 1033 ].

Эксперимент 1

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

Однако, сайт не позволяет осуществить это без покупки лицензии.

Вывод:

Данная программа не подходит для взлома пароля.

Эксперимент 2

Установим и запустим демоверсию PassFab. При запуске использовали метод перебора и дали программе подсказку (указав максимальную длину пароля 4 символа, все строчные латинские буквы и цифры). Программа загружает центральный процессор практически на 100%, но не использует вычислительные возможности видеокарты.

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

Вывод:

Длину пароля программа определила правильно, но демоверсия не позволяет оценить её возможности.

Эксперимент 3

Переходим к PasscoverySuite. Сведения о файле программа показала:

У PasscoverySuite это заняло бы около 4 часов при максимальной загрузке процессора и видеокарты. Однако в демоверсии приложение отключается через 30 минут использования.

Мы использовали метод перебора и дали программе подсказку (указав максимальную длину пароля 4 символа, все строчные латинские буквы и цифры):

Через 2 минуты работы программа выдала результат:

Число вариантов 1727604 совпадает с данными, рассчитанными нами в задаче 1.

Так как это демоверсия, программа показывает только первые 2 символа, и не показывает реальную длину пароля. Но эти символы совпадают с двумя первыми символами настоящего пароля.

Вывод:

программа смогла подобрать пароль (после подсказки о его максимальной длине и используемых символах).

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

Заключение

В процессе разработки проекта гипотеза нашла своё подтверждение, что отчётливо видно из проведённых экспериментов. Актуальность была подтверждена. Были использованы объекты исследования - человек и информация. Были использованы предметы исследования - комбинаторика, криптография, WordPasswordRecoveryLastic, PassFab, PasscoverySuite. Мы добились нашей цели. Все 3 задачи были достигнуты. Все рассмотренные нами явления существуют благодаря основным законам комбинаторики. Тот же антивирус в коде считает огромное количество операций и событий. Хакеры пишут программы, подбирая код, который позволит получить доступ к программе на уровне администратора. Квантовый компьютер может быстро считать огромные факториалы чисел. В ходе проведенных нами экспериментов мы выяснили, что существуют использующие комбинаторику программы, которые действительно могут взломать некий пароль. Мы выяснили, что длина пароля в 4 символа явно недостаточна для надёжной цифровой безопасности. Таким образом благодаря комбинаторике существует цифровая безопасность.

Список рисунков

Рисунок 1. Графы 4

Рисунок 2. Пример регулярного дерева. 4

Рисунок 3. Размещения 6

Рисунок 4. Квантовый компьютер 9

Список литературы