XIV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Применение комбинаторных методов в генерации паролей для веб-сайта
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Комбинаторика – раздел математики, изучающий дискретные объекты, множества и отношения на них. Рассматриваемые объекты, как правило, являются определёнными комбинациями других объектов (чисел, букв). Важную область составляет теория перечислений, в основе которой лежат «правило суммы» и «правило произведения». Впервые, с комбинаторными задачами люди столкнулись в глубокой древности, но наукой комбинаторика становится лишь в XVII в. — в период, возникновения теории вероятностей. Чтобы решать комбинаторные задачи, нужно уметь подсчитывать число различных комбинаций, подчиненных каким-либо условиям.
В настоящее время, комбинаторика – своего рода основа основ: красивая теория с массой нетривиальных задач и подходов, прекрасная база для приложений в computer science, в анализе сложных сетей, в теории кодирования и криптографии.
В своей работе, я познакомилась с историей возникновения и развития комбинаторики, изучила методы решения задач о перечислении, подсчёте количества различных конфигураций, образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, а также рассмотрела практическое применение комбинаторных методов в генерации пароля для веб-сайта.
Актуальность исследования выбранной темы заключается в необходимости решения комбинаторных задач, поскольку комбинаторика, с одной стороны, богата красивыми постановками задач, доступными школьнику, с другой стороны, является очень глубокой современной областью знаний, без овладения инструментами которой невозможно серьезное понимание, как большинства других фундаментальных дисциплин, так и многих прикладных проблем.
Цель исследования: разработать рекомендацию по созданию надежного пароля на основе комбинаторных методов.
Задачи исследования:
Познакомиться с историей возникновения и развития комбинаторики.
Изучить основные методы решения комбинаторных задач.
Рассмотреть практическое применение комбинаторных методов в создании пароля для веб-сайта.
Объект: комбинаторика
Предмет: прикладные разделы математики.
Методы исследования: анализ, синтез, индукция.
История возникновения и развития комбинаторики
Исследования, посвященные различным вариантам выборки заданного числа элементов из некоторого конечного множества, занимали величайшие, математические умы человечества довольно давно.
Комбинаторные мотивы можно обнаружить в символике китайской «Книги Перемен» (V век до н. э.). Классическая задача комбинаторики: «сколько имеется способов извлечь m элементов из N возможных» упоминается, начиная примерно с IV столетия до н.э., в сутрах древней Индии.
В Средние века комбинаторика продолжала развиваться, в большинстве случаев, за пределами европейской цивилизации. В XII столетии индийский математик Бхаскара в своём главном труде «Лилавати» исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.
Однако, как самостоятельная научная дисциплина комбинаторика стала выделяться из математики только в XVII-ом веке:
В 1654 году Блез Паскаль открыл несложный метод вычисления биномиальных коэффициентов: «треугольник Паскаля».Известно, что этот способ был уже известен на Востоке, но Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики.
Сам термин «комбинаторика» придумал Г. Лейбниц, который в 1666 году опубликовал книгу «Рассуждения о комбинаторном искусстве».
Ученик Лейбница – Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
Окончательно комбинаторика, как самостоятельный раздел математики, оформилась в трудах Эйлера. При решении комбинаторных задач он глубоко изучил свойства сочетаний, размещений и перестановок.
Комбинаторика: основные правила и формулы
Правило сложения: если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами. Чтобы использовать правило сложения необходимо:
определить количество элементов в каждой группе;
убедиться, что в различных группах, из которых выбирают элемент, нет одинаковых элементов.
При использовании правила сложения необходимо обратить внимание на то, чтобы ни один из способов выбора элемента А не совпадал с каким-либо способом выбора элемента В. Если элемент А можно получить n способами, элемент B получить m способами, то выбрать А или В можно получить m + n - k способами, где k — это количество повторяющихся способов.
Правило произведения: если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то пару элементов А и B можно выбрать n × m способами.
Факториалом числа называется произведение n последовательных натуральных чисел, начиная с единицы.
Обозначение: n!
Формула: n! = 1⋅2⋅3⋅...⋅ (n−2) ⋅ (n−1) ⋅ n.
Принято, что 0! = 1.
Множеством называется совокупность каких-либо объектов, которые называются элементами этого множества и обладают общим для всех их свойством.
Обозначение: {a, b, c}
Выборками называются подмножества какого-либо множества.
Упорядоченными выборками называются выборки, в которых важен порядок элементов. Если в выборке поменяют местами два элемента, и получится другая выборка, то данная выборка является упорядоченной.
Неупорядоченными выборками называются выборки, в которых не важен порядок элементов.
Перестановкой множества из n элементов называется любой упорядоченный набор всех элементов этого множества.
Обозначение: Pn, где n — количество элементов множества.
Теорема: число перестановок без повторений из n элементов равно n!
Формула: Pn= n!
В некоторых задачах присутствуют случаи, когда переставляемые предметы одинаковы. Тогда получается меньше перестановок, ведь некоторые из них совпадают друг с другом.
Формула: Pn(n1, n2 … nn) =
Размещением без повторений называется упорядоченная выборка элементов k из данного множества элементов n.
Формула:
Размещением с повторениями называется упорядоченная выборка k элементов с повторениями, которая составлена из основного множества n элементов.
Формула:
Сочетанием без повторений называется неупорядоченная выборка без повторений.
Формула:
С очетанием с повторениями называется неупорядоченная выборка с повторениями.
Формула:
При решении задач, в которых нужно определить число комбинаций, необходимо обратить внимание на важность порядка элементов.
В данном разделе были рассмотрены основные правила и формулы комбинаторики для последующего использования в решении задач на создание пароля для веб-сайта, а также для дальнейшей реализации программы генерации пароля на языке python.
Комбинаторные расчеты надежности пароля
Каждый пользователь компьютера или мобильных устройств сталкивался с необходимостью создания пароля для защиты своих учетных данных. Надежный пароль - важнейший компонент современной интернет-безопасности.Однако немногие относятся к созданию паролей с должной ответственностью.
Многие пользователи используют короткие пароли, которые часто состоят только из цифр или букв алфавита, что значительно сокращает количество возможных комбинаций.
Технологии для вскрытия паролей на месте не стоят. Сейчас опытному злоумышленнику на вскрытие восьмизначного пароля необходимо совсем немного времени. Чаще всего взлом осуществляется способом подбора пароля перебором. Алгоритм очень прост и ограничивается попыткой пробовать как можно больше комбинаций символов. Помимо этого, есть математический раздел – криптография, в котором изучаются способы шифрования и дешифрования информации. Для дешифрования пароля с помощью криптографии, необходимо определить количество возможных паролей, посредством комбинаторных методов.
Для создания пароля разрешается применять следующие символы:
Заглавные буквы латинского алфавита: от A до Z (26 символов)
Строчные буквы латинского алфавита: от a до z (26 символов)
Цифры: от 0 до 9 (10 символов)
Специальные символы: " # $ % & ' ( ) {} [ , - . / : ; < = > … (33 символа)
Задача №1
Веб-сайт просит пользователя создать восьмизначный пароль, содержащий только цифры, где каждая цифра используется только один раз. Определите: сколько существует различных возможных паролей?
Решение:
Для создания такого пароля разрешается применять только цифры – 10 символов. Каждая цифра должна использоваться только один раз.
Значит, для определения количества паролей необходимо использовать формулу размещения без повторений:
Тогда, количество размещений из 8 цифр, выбранных из 10, составляет:
= = = 1814400 паролей
Ответ: 1814400 паролей, содержащих только цифры, где каждая цифра используется только один раз.
Задача №2
Веб-сайт просит пользователя создать восьмизначный пароль, содержащий только строчные буквы латинского алфавита, где каждая буква используется только один раз. Определите: сколько существует различных возможных паролей?
Решение:
Для создания такого пароля разрешается применять только строчные буквы латинского алфавита – 26 символов. Каждая буква должна использоваться только один раз.
Значит, для определения количества паролей необходимо использовать формулу размещения без повторений:
Тогда, количество размещений из 8 строчных букв латинского алфавита, выбранных из 26, составляет:
= = = 62990928000 паролей
Ответ: 62990928000 паролей, содержащих только строчные буквы латинского алфавита, где каждая буква используется только один раз.
Задача №3
Веб-сайт просит пользователя создать пароль, содержащий только цифры и строчные буквы латинского алфавита.
Определите:
а) Сколько существует таких паролей длины 8?
б) Сколько существует таких паролей длины 8, если в каждом из них обязательно присутствует одна цифра?
в) Сколько существует таких паролей, длины 8, если в каждом из них обязательно присутствуют совпадающие символы?
Решение:
а) Для создания такого пароля разрешается применять: строчные буквы латинского алфавита - 26 символов, а также цифры - 10 символов.
Итого, 26 + 10 = 36 символов.
На первую позицию пароля можно поставить любой из 36 символов. Учитывая, что для создания такого пароля нет никаких ограничений, значит на вторую и последующие позиции можно поставить также любой из 36 символов.
Используя правило произведения, получим:
36 × 36 × 36 × 36 × 36 × 36 × 36 × 36 = 368 = 2821109907456 – количество паролей длины восемь.
б) Для создания такого пароля необходимо использовать как минимум одну цифру. Сначала, я рассмотрела количество паролей без цифр, то есть число паролей с использованием только строчных букв:
Используя правило произведения, получим:
26 × 26 × 26 × 26 × 26 × 26 × 26 × 26 = 268 = 208827064576 – количествопаролей без цифр.
Из пункта а) известно, число паролей длины восемь: 368 = 2821109907456
Значит, 2821109907456 – 208827064576 = 2612282842880 – количество паролей с использованием минимум одной цифры.
в) Для создания такого пароля необходимо использовать совпадающие символы. Рассмотрим количество паролей без совпадающих символов, то есть число паролей, в которых все символы различны.
Тогда, на первую позицию пароля без совпадающих символов можно поставить любой из 36 символов. Но на вторую позицию можно поставить любой из 35 символов, так как один из символов уже выбран в первую позицию и так до последней позиции пароля.
Используя правило произведения, получим:
36 × 35 × 34 × 33 × 32 × 31 × 30 × 29 = 1220096908800 – количество паролей без совпадающих символов.
Из пункта а) известно, число паролей длины восемь: 368 = 2821109907456
Значит, 2821109907456 – 1220096908800 = 1601012998656 – количество паролей с совпадающими символами.
Ответ: а) 2821109907456 паролей длины восемь.
б) 2612282842880 паролей с использованием одной цифры.
в) 1601012998656 паролей с совпадающими символами.
Задача №4
Веб-сайт просит пользователя создать пароль, содержащий только цифры, строчные и заглавные буквы латинского алфавита.
Определите:
а) Сколько существует таких паролей длины 8?
б) Сколько существует таких паролей длины 8, если в каждом из них обязательно присутствует одна цифра?
в) Сколько существует таких паролей, длины 8, если в каждом из них обязательно присутствуют совпадающие символы?
Решение:
а) Для создания такого пароля разрешается применять: строчные буквы латинского алфавита - 26 символов, заглавные буквы латинского алфавита - 26 символов, а также цифры - 10 символов.
Итого, 26 + 26 + 10 = 62 символа.
На первую позицию пароля можно поставить любой из 62 символов. Учитывая, что для создания такого пароля нет никаких ограничений, значит на вторую и последующие позиции можно поставить также любой из 62 символов.
Используя правило произведения, получим:
62 × 62 × 62 × 62 × 62 × 62 × 62 × 62 = 628 = 218340105584896 – количество паролей длины восемь.
б) Для создания такого пароля необходимо использовать как минимум одну цифру. Рассмотрим количество паролей без цифр, то есть число паролей с использованием только строчных и заглавных букв:
Используя правило произведения, получим:
52 × 52 × 52 × 52 × 52 × 52 × 52 × 52 = 528 = 53459728531456 – количество паролей без цифр.
Из пункта а) известно, число паролей длины восемь:
628 = 218340105584896
Значит, 218340105584896 – 53459728531456 = 164880377053440 – количество паролей с использованием минимум одной цифры.
в) Для создания такого пароля необходимо использовать совпадающие символы. Рассмотрим количество паролей без совпадающих символов, то есть число паролей, в которых все символы различны.
Тогда, на первую позицию пароля без совпадающих символов можно поставить любой из 62 символов. Но на вторую позицию можно поставить любой из 61 символов, так как один из символов уже выбран в первую позицию и так до последней позиции пароля.
Используя правило произведения, получим:
62 × 61 × 60 × 59 × 58 × 57 × 56 × 55 = 136325893334400 – количество паролей без совпадающих символов.
Из пункта а) известно, число паролей длины восемь:
628 = 218340105584896
Значит, 218340105584896 – 136325893334400 = 82014212250496 – количество паролей с совпадающими символами.
Ответ: а) 218340105584896 паролей длины восемь.
б) 164880377053440 паролей с использованием одной цифры.
в) 82014212250496 паролей с совпадающими символами.
Задача №5
Веб-сайт просит пользователя создать пароль, содержащий буквенно-цифровые символы, включая строчные и прописные буквы, а также цифры, без использования специальных символов. Пароль должен состоять как минимум из 8, но не более чем из 12 символов и должен содержать как минимум одну заглавную букву и как минимум одну цифру. Допускается повторение цифр и букв. Сколько разных паролей можно создать, удовлетворяющих этим критериям?
Решение:
1) Для создания такого пароля разрешается применять: строчные буквы латинского алфавита - 26 символов, заглавные буквы латинского алфавита - 26 символов, а также цифры - 10 символов.
Итого, 26 + 26 + 10 = 62 символа.
Для того, чтобы определить общее число паролей длины 8, я использовала правило произведения:
62 × 62 × 62 × 62 × 62 × 62 × 62 × 62 = 628 – количество паролей длины восемь.
2) Рассмотрим количество паролей без заглавных букв, то есть число паролей с использованием только строчных букв и цифр:
36 × 36 × 36 × 36 × 36 × 36 × 36 × 36 = 368 – количество паролей без заглавных букв.
3) Определим количество паролей без цифр, то есть число паролей с использованием только строчных и заглавных букв:
52 × 52 × 52 × 52 × 52 × 52 × 52 × 52 = 528 – количество паролей без цифр.
4) Для того, чтобы найти количество паролей, которые содержат только строчные буквы, необходимо также использовать правило произведения:
26 × 26 × 26 × 26 × 26 × 26 × 26 × 26 = 268 – количество паролей, которые содержат только строчные буквы.
5) Используя полученные данные, можно определить количество разрешенных паролей:
628 – 368 – 528 + 268 – количество разрешенных паролей из 8 символов.
629 – 369 – 529 + 269 – количество разрешенных паролей из 9 символов.
6210 – 3610 – 5210 + 2610 – количество разрешенных паролей из 10 символов.
6211 – 3611 – 5211 + 2611 – количество разрешенных паролей из 11 символов.
6212 – 3612 – 5212 + 2612 – количество разрешенных паролей из 12 символов.
Ответ: 628 – 368 – 528 + 268 – количество паролей из 8 символов.
629 – 369 – 529 + 269 – количество паролей из 9 символов.
6210 – 3610 – 5210 + 2610 – количество паролей из 10 символов.
6211 – 3611 – 5211 + 2611 – количество паролей из 11 символов.
6212 – 3612 – 5212 + 2612 – количество паролей из 12 символов.
При решении данных задач было замечено, что чем больше различных символов используется при составлении пароля, тем больше комбинаций в результате получается. Следовательно, можно значительно повысить безопасность паролей, увеличив время, необходимое для перебора всех возможных вариантов паролей.
Рекомендации для создания надежного пароля на основе комбинаторных методов:
Длина пароля должна быть не менее 8 символов;
Пароль должен содержать заглавные и строчные буквы, цифры и специальные символы;
Пароль не должен содержать очевидные и простые слова, фразы и наборы символов, которые можно легко подобрать.
Практическое применение комбинаторных методов в создании паролей
Комбинаторика – это настоящий клад для разработчиков программного обеспечения, поскольку она помогает анализировать различные алгоритмы, выбирать оптимальную стратегию перебора. Следует отметить, что комбинаторные формулы необходимы для вычисления вероятностей, а те, в свою очередь служат основой для машинного обучения – одного из мощнейших трендов в ПО 21-го века!
Использование комбинаторики в программировании я изучила с помощью Python 3 — это высокоуровневый язык программирования, мощный инструмент для создания программ самого разнообразного назначения.
Во встроенном в Python модуле itertools существует ряд функций, позволяющих комбинировать различные значения. Чтобы воспользоваться возможностями данного модуля, необходимо импортировать библиотеку, предварительно указав метод, к которому будет происходить обращение в программе.
К числу комбинаторных функций относятся:
Функция itertools.permutations используется для нахождения перестановок. Первый элемент – будет исходным множеством. Второй элемент – результат перестановки какой-то пары элементов и так до момента, пока не будут перебраны все уникальные комбинации.
Функция itertools.combinations выбирает все сочетания из последовательности. Пусть в ней имеется n различных объектов. Необходимо выбрать из них k объектов всевозможными способами (то есть меняется состав выбранных объектов, причем порядок не важен). Получившиеся комбинации являются сочетаниями из n объектов по k.
Функция itertools.combinations_with_replacement описывает, сколькими способами можно составить комбинацию из n элементов по k элементов. Важно помнить, что в сочетаниях без повторений элементы не повторяются внутри одной выборки.
В «Google Chrome» инструмент создания безопасных паролей присутствует по умолчанию и готов к использованию сразу после установки веб-браузера. Надежные пароли создаются автоматически одним нажатием кнопки благодаря встроенному генератору паролей, который основывается на методах комбинаторики.
Для того, чтобы сгенерировать пароль необходимо:
Открыть Chrome на компьютере.
Убедится, что вы вошли в аккаунт в браузере Chrome.
Открыть сайт и начать создавать аккаунт.
Нажать на поле для ввода пароля «Сгенерировать надежный пароль».
Задача
Создайте программу для генерации восьмизначного пароля, содержащего только цифры и строчные буквы латинского алфавита, где каждая цифра и буква используется только один раз.
Решение:
Программа для генерации восьмизначного пароля:
Небольшая часть результата программы для генерации восьмизначного пароля, содержащего цифры и строчные буквы латинского алфавита, где каждая цифра и буква используется только один раз:
В данном разделе была реализована программа генерации пароля на языке Python 3, посредством правил и формул комбинаторики.
Заключение:
Комбинаторика, как раздел математики, с одной стороны, богата исключительно красивыми постановками задач, доступными школьнику, а с другой стороны, является глубокой современной областью знаний, без овладения инструментами которой невозможно серьезное понимание, как большинства других фундаментальных дисциплин, так и многих прикладных проблем.
В ходе выполнения данной работы была достигнута цель - разработать рекомендацию по созданию надежного пароля на основе комбинаторных методов, выполнены все поставленные задачи.
Я познакомилась с историей возникновения и развития комбинаторики, изучила методы решения задач о перечислении, подсчёте количества различных конфигураций, образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения.
Рассмотрев применение комбинаторных методов в генерации пароля для веб-сайта, я показала практическую значимость комбинаторики как области математики.
Список источников и литературы:
Виленкин Н.Я., Комбинаторика. - М.: Просвещение, 2006
Комбинаторика, URL: https://ru.wikipedia.org/wiki/Комбинаторика
Комбинаторика, URL: https://fmclass.ru/math.php?id=4986cacac0f94
Комбинаторика для начинающих, URL: https://ru.coursera.org/learn/kombinatorika-dlya-nachinayushchikh
Как создать надежный пароль и защитить аккаунт, URL: https://support.google.com/accounts/answer/32040?hl=ru
Начальные сведения комбинаторики, URL: https://www.yaklass.ru/p/algebra/11-klass/nachalnye-svedeniia-kombinatoriki-9340
Python itertools — описание модуля и функций, URL: https://all-python.ru/osnovy/itertools.html
Современная комбинаторика, URL: https://ru.coursera.org/learn/modern-combinatorics?