Шифр подстано́вки — это метод шифрования, в котором элементы исходного открытого текста заменяются зашифрованным текстом в соответствии с некоторым правилом. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее. В классической криптографии различают четыре типа шифра подстановки[1]:
В качестве альтернативы шифрам подстановки можно рассматривать перестановочные шифры. В них, элементы текста переставляются в ином от исходного порядке, а сами элементы остаются неизменными. Напротив, в шифрах подстановки, элементы текста не меняют свою последовательность, а изменяются сами.
Использование шифров подстановки берет свое начало в Месопотамии. С целью сокрытия информации о рецепте производства глазури для гончарных изделий автор заменял часть слов на цифры и клинописные знаки. Римский император Гай Юлий Цезарь при написании секретных сообщений смещал каждую букву алфавита на 3 позиции. Данный вид шифров подстановки впоследствии назвали его именем, шифр Цезаря. Другой не менее известный шифр античности, Атбаш, применялся в Библии для создания скрытых посланий. Каждая буква слова заменялась её зеркальным отражением в алфавите[2] [3].
Одним из первых шифровальных устройств принято считать линейку Энея, при использовании которой длинная нить продевалась через прорезь, а затем через проделанные в линейке отверстия. Рядом с отверстиями располагались соответствующие им буквы. На нити завязывался узелок в месте прохождения её через отверстие. Таким образом осуществлялась замена текста послания на последовательность расстояний между узелками. Данное устройство было изобретено древнегреческим полководцем Энеем Тактиком в IV веке до н. э.[4][5]
С началом использования частотного анализа для вскрытия моноалфавитных шифров в IX веке, появилась необходимость в изменении частотности появления символов обычного текста. С этой целью стал применяться однозвучный шифр подстановки, сутью которого было сопоставление нескольких заменяющих символов одной букве пропорционально частотности появление этой буквы в различных текстах. Секретарь антипапы Клемёнтия VII Габриель де Лавинда в XV веке впервые использует омофоны для обеспечения приблизительно одинаковой частотности гласных букв. Спустя 65 лет Леон Баттиста Альберти подробно описывает однозвучный шифр подстановки в своей книге «Трактат о шифрах». Основной проблемой распространения омофонической замены была необходимость использования расширенного алфавита для зашифровки сообщений.[6][7] [8][9]