Реализация и взлом шифра Цезаря

Лицо ЦезаряДоброго времени суток, дорогие читатели и посетители! Сегодня небольшое погружение в мир криптографии и шифрования. Для меня эта область представляет некоторый интерес. А в целом, знать об этом нужно!  В нашем цифровом веке без шифрования все уже давно бы рухнуло, ваша почта шифруется, ваши фото шифруются(в России вряд ли, но все же), ваши переписки тоже шифруются. В идеальном интернете шифроваться должно вообще все, особенно любая финансовая информация. Финансы защищены даже лучше, чем личная жизнь. В любом случае, сегодня полезно хотя бы примерно знать, как это все работает. Для начала, предлагаю посмотреть на мою реализацию самого простого из шифров. А там и до RSA доберемся, поехали!

 

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр простого сдвига

Так же известен под названием «Шифр Цезаря». Это шифр простой подстановки, при шифровании каждый символ текста заменяется символом, находящимся на некотором постоянном расстоянии левее или правее в алфавите. Наглядно на картинке из вики:

Действие шифра Цезаря

читать далее «Реализация и взлом шифра Цезаря»

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

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

Топологическая сортировка

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

Реализация топологической сортировки на c++ с использованием стека

читать далее «Реализация топологической сортировки и поиск компонент сильной связности графа»

Реализация алгоритма поиска в глубину на графе

Краткое описание алгоритма поиска в глубину

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

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

Моя реализация поиска в глубину на c++

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

Реализация алгоритма поиска в ширину на графе

Краткое описание алгоритма поиска в ширину

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

Моя реализация поиска в ширину на c++

Граф представлен следующим образом. Массив(vector c++) из n элементов, где n — число вершин в графе. Каждый элемент массива соответствует вершине графа и содержит вложенный массив — список вершин, смежных с данной.


typedef vector< vector<int> > graphNotWeighted;

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

Исходный код алгоритма поиска в ширину на c++

читать далее «Реализация алгоритма поиска в ширину на графе»