Минимальная реализация алгоритма RSA на C++

Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

Continue reading

Proggy-Buggy 2018: Задача A. Шифр Цезаря

Задание

Багги мнит себя Гаем Юлием Цезарем и любит громогласно его цитировать при каждом удобном случае, выдавая мысли Цезаря за свои. Проги пошутил над Багги и зашифровал в стиле Цезаря список цитат, которыми пользуется Багги. Багги в панике. Если хотите, помогите ему расшифровать известную цитату :

UDMHUHCHUHBH

Напишите программу, которая для вышеприведенного шифртекста выводит соответствующий открытый текст.

Код

Решение

Шифр Цезаря так же известен как шифр сдвига. Каждая буква сдвигается в алфавите на константу влево или вправо по модулю длины алфавита . В нашем случае зашифрованное и расшифрованное сообщение будет состоять только из букв (в условии не сказано ничего про сам алфавит).

Ниже пример шифрования методом сдвига (в данном случае на 3 единицы вправо)

A заменяется на D
B заменяется на E
и так далее
Z заменяется на C

Нам остается только подобрать ключ. Простым перебором получаем что зашифрованное сообщение было получено сдвигом всех букв исходного сообщения на единицу влево.
Ну что еще сказать?
Пришёл, увидел, победил!
Veni, vidi, vici!