Введение
Алгоритм шифрования и дешифрования информации
В криптографии шифр (или кодировщик) — это алгоритм выполнения шифрования или дешифрования — последовательность чётко определённых шагов, которые могут быть выполнены как процедура. Альтернативный, менее распространённый термин — кодирование. Шифровать или кодировать — значит преобразовывать информацию в шифр или код. В обыденной речи "шифр" является синонимом "кода", поскольку оба представляют собой набор шагов, которые шифруют сообщение; однако, эти понятия различны в криптографии, особенно в классической криптографии. Коды обычно заменяют строки символов разной длины на выходе, в то время как шифры обычно заменяют такое же количество символов, как и на входе. Код сопоставляет одно значение с другим. Слова и фразы могут быть закодированы буквами или цифрами. Коды обычно имеют прямое соответствие между вводом и ключом. Коды в первую очередь используются для экономии времени. Шифры являются алгоритмическими. Предоставленный ввод должен соответствовать процессу шифра, чтобы быть решённым. Шифры обычно используются для шифрования письменной информации. Коды работают путём замены в соответствии с большой кодовой книгой, которая связывает случайную строку символов или цифр со словом или фразой. Например, "UQJHSE" может быть кодом для "Продолжайте к следующим координатам". При использовании шифра исходная информация известна как открытый текст, а зашифрованная форма — как шифротекст. Шифротекст содержит всю информацию из открытого текста, но не в формате, читаемом человеком или компьютером без надлежащего механизма для его дешифрования. Работа шифра обычно зависит от дополнительной информации, называемой ключом (или, в традиционной терминологии АНБ, криптопеременной). Процедура шифрования варьируется в зависимости от ключа, что изменяет детальную работу алгоритма. Ключ должен быть выбран перед использованием шифра для шифрования сообщения. Без знания ключа расшифровать полученный шифротекст в читаемый открытый текст должно быть крайне сложно, если не невозможно. Большинство современных шифров можно классифицировать несколькими способами:
По тому, работают ли они с блоками символов обычно фиксированного размера (блочные шифры) или с непрерывным потоком символов (потоковые шифры). По тому, используется ли один и тот же ключ как для шифрования, так и для дешифрования (алгоритмы симметричного ключа), или используется другой ключ для каждого (алгоритмы асимметричного ключа). Если алгоритм симметричен, ключ должен быть известен отправителю и получателю, и никому другому. Если алгоритм асимметричен, то ключ шифрования отличается от ключа дешифрования, но тесно с ним связан. Если один ключ нельзя вывести из другого, алгоритм асимметричного ключа обладает свойством открытого/закрытого ключа, и один из ключей может быть опубликован без потери конфиденциальности.
Этимология
Слово "шифр" происходит от арабского слова صفر (sifr) и распространилось в Европе как часть арабской системы счисления в Средние века. Римская система счисления не содержала понятия нуля, что ограничивало прогресс в математике. В процессе перехода слово было заимствовано в средневековую латынь как cifra, а затем в среднефранцузский как cifre. В конечном итоге это привело к появлению английского слова cipher (реже cypher). Одна из теорий о том, как термин стал означать шифрование, заключается в том, что понятие нуля было непонятным для европейцев, и поэтому термин стал применяться к сообщению или коммуникации, которые трудно было расшифровать. Позже термин "шифр" также использовался для обозначения любой арабской цифры или вычислений с их использованием, поэтому шифрование текста в виде арабских цифр буквально означает преобразование текста в "цифры".
Противоположность кодам
В обыденных контекстах термины "код" и "шифр" обычно могут использоваться как взаимозаменяемые; однако в техническом смысле эти слова обозначают разные понятия. Коды несут в себе смысл: словам и фразам присваиваются числа или символы, что позволяет создать более короткое сообщение. Примером является коммерческий телеграфный код, который использовался для сокращения длинных телеграфных сообщений, возникавших при заключении коммерческих контрактов посредством обмена телеграммами. Другой пример – шифры целых слов, позволяющие пользователю заменять целое слово символом или знаком, подобно тому, как японский язык использует иероглифы кандзи (китайские иероглифы, используемые в японском языке) для дополнения японских слоговых символов. Например, фразу "The quick brown fox jumps over the lazy dog" можно заменить на "The quick brown 狐 jumps 上 the lazy 犬". Стенографисты иногда используют специальные символы для сокращения целых слов. Шифры же работают на более низком уровне: на уровне отдельных букв, небольших групп букв или, в современных схемах, отдельных битов и блоков битов. Некоторые системы использовали как коды, так и шифры, применяя многократное шифрование для повышения безопасности. В некоторых случаях термины "коды" и "шифры" используются как синонимы к "замене" и "перестановке" соответственно. Исторически криптография разделялась на кодирование и шифрование, при этом кодирование имело собственную терминологию, аналогичную терминологии шифрования: "кодирование, кодовый текст, декодирование" и так далее. Однако коды имеют ряд недостатков, включая уязвимость к криптоанализу и сложность управления объемной книгой кодов. По этой причине коды устарели в современной криптографии, и шифры стали доминирующей техникой.
Типы
Существует множество различных типов шифрования. Алгоритмы, использовавшиеся на ранних этапах развития криптографии, значительно отличаются от современных методов, а современные шифры можно классифицировать по принципу их работы и в зависимости от того, используют они один или два ключа.
Исторические
Шифр Цезаря — одна из самых ранних известных криптографических систем. Юлий Цезарь использовал шифр, который сдвигает буквы в алфавите на три позиции и переносит оставшиеся буквы в начало, чтобы писать Марку Туллию Цицерону примерно в 50 году до н.э. [11]
Исторические шифры, использовавшиеся в прошлом с использованием пера и бумаги, иногда называют классическими шифрами. Они включают простые шифры подстановки (такие как ROT13) и шифры перестановки (такие как шифр «заборчик»). Например, фразу "GOOD DOG" можно зашифровать как "PLLX XLP", где "L" заменяет "O", "P" заменяет "G", а "X" заменяет "D" в сообщении. Перестановка букв в фразе "GOOD DOG" может привести к "DGOGDOO". Эти простые шифры и примеры легко взломать, даже без пар открытого и зашифрованного текста. В 1640-х годах парламентский командующий Эдвард Монтегю, 2-й граф Манчестер, разработал шифры для отправки зашифрованных сообщений своим союзникам во время Английской гражданской войны. Простые шифры были заменены полиалфавитными шифрами подстановки (такими как шифр Виженера), которые меняли алфавит подстановки для каждой буквы. Например, фразу "GOOD DOG" можно зашифровать как "PLSX TWF", где "L", "S" и "W" заменяют "O". Даже при наличии небольшого количества известного или предполагаемого открытого текста, простые полиалфавитные шифры подстановки и шифры перестановки букв, предназначенные для шифрования ручкой и бумагой, легко взломать. Возможно создание защищенного шифра для пера и бумаги на основе одноразового шифра, но они имеют и другие недостатки. В начале двадцатого века были изобретены электромеханические машины для шифрования и дешифрования с использованием перестановки, полиалфавитной подстановки и своеобразной «аддитивной» подстановки. В роторных машинах несколько роторных дисков обеспечивали полиалфавитную подстановку, а коммутационные панели — дополнительную подстановку. Ключи можно было легко менять, заменяя роторные диски и провода коммутационной панели. Хотя эти методы шифрования были сложнее предыдущих и требовали машин для шифрования и дешифрования, были изобретены и другие машины, такие как британская «Бомба», для взлома этих методов шифрования.
Размер ключа и уязвимость
В чистой математической атаке (т.е. при отсутствии какой-либо другой информации, помогающей взломать шифр) два фактора имеют первостепенное значение:
Доступная вычислительная мощность, то есть вычислительные ресурсы, которые могут быть применены к решению задачи. Важно отметить, что средняя производительность одного компьютера – не единственный фактор, который следует учитывать. Злоумышленник может использовать несколько компьютеров одновременно, например, для существенного увеличения скорости полного перебора ключа (т.е. атаки "полным перебором" или "грубой силой"). Размер ключа, т.е. длина ключа, используемого для шифрования сообщения. С увеличением размера ключа возрастает и сложность полного перебора, доходящая до точки, когда прямой взлом шифрования становится невозможным. Поскольку желаемым результатом является вычислительная сложность, теоретически следует выбирать алгоритм и желаемый уровень сложности, а затем определять длину ключа соответствующим образом. Пример такого подхода можно найти в статье Key Length, где на основе различных отчетов предлагается, что симметричный шифр с длиной ключа 128 бит, асимметричный шифр с ключами длиной 3072 бита и шифр на эллиптических кривых с длиной ключа 256 бит имеют примерно одинаковую стойкость в настоящее время. Клод Шеннон, используя принципы теории информации, доказал, что любой теоретически невзламываемый шифр должен иметь ключи, длина которых не меньше длины открытого текста, и которые используются только один раз: одноразовый шифр.