В годы второй мировой войны японские специалисты трудились над разработкой шифровальных систем, названия которым давались по цветовым оттенкам. В середине 30-х американская разведка выявила тайный шифр — «пурпурный» код. В результате работ специальной команды, которую возглавил знаменитый американский криптограф Уильям Фредерик Фридман, было установлено, что японцы используют новую шифровальную машину. Фридман усердно занялся расшифровкой «пурпурного» кода — одного из самых сложных. И в 1940 г. работа дала результаты, код был взломан, а его алгоритм — опубликован. Взлом японского шифра помог разведке США получить доступ к секретной дипломатической корреспонденции.
Что же до шифровального устройства, то американцы изначально предполагали, что имеют дело с одной из версий «Энигмы». Но вскоре обнаружилось, что «пурпурный» код принадлежит японской шифровальной машине с кодовым названием Purple. В Японии она известна под названиями «Алфавитная печатная машина типа 97» (в оригинале 九七式欧文印字機) или «Шифровальная машина типа B» (в оригинале 暗号機 タイプ). Purple заменила шифраторы Red, которые использовались Министерством иностранных дел Японии.
Устройство состояло из комбинации кабелей и контактной панели, благодаря чему удавалось создавать множество разнообразных шифров. Для того, чтобы зашифровать сообщение, выбирался и устанавливался соответствующий ключ. После этого через клавиатуру электронной пишущей машинки вводился текст. Пройдя через переплетение контактных устройств и кабелей, сообщение распечатывалось уже в зашифрованном виде.
В Purple вместо скремблеров использовались телефонные переключатели или шаговые искатели. Что делало машину более сложной по сравнению с другими подобными шифровальными устройствами. Также использовались сотни различных шрифтов, что еще более усложняло и без того нелегкую работу американским криптоаналитикам. Но как видно, несмотря на все старания японцев, «пурпурный» код был взломан.
В 1940 г. Фридману удалось воссоздать копию шифровальной машины Purple, что существенно помогло в дешифровании последующих закодированных сообщений японцев.
Уильям Фредерик Фридман (1891 — 1969 г.г.)
Уильям Фредерик Фридман — американский криптограф, считается одним из основателей (отцом) американской криптологии. Он начал использовать термины «криптоанализ» (cryptanalysis) и «криптология» (cryptology). Он организовал и стал первым директором американской службы радиотехнической разведки.
Авторству Фридмана принадлежат три учебника по военной криптографии, множество научных работ по анализу кода и шифров. Он один из первых начал применять статистические методы в криптоанализе, разработал девять шифровальных машин. Его имя увековечено в Зале славы военной разведки США и Зале Славы Агентства национальной безопасности.
Шифр, построенный на конечных автоматах
Purple является одной из первых машин, построенных на конечных автоматах. Впервые понятие конечного автомата, как дискретного преобразователя с конечным числом возможных состояний в качестве схем кодирования и декодирования информации, было рассмотрено в статье Клода Шеннона (1948 г.).
Более простое и понятное описание машины Purple производится именно в конечно-автоматных терминах.
Для простой замены символов открытого текста и шифртекста, помимо входной и выходной коммутационной панели, используются блоки L, M, R, S и stepping, которые являются конечными криптоавтоматами, L = M = R. У первой четверки автоматов, выступающих в качестве преобразователей, имеются чисто инициализирующие ключи. Последний (stepping) — комбинационный криптоавтомат, используется в роли управляющего автомата, что определяет порядок смены состояний в первых трех. Состояниями в автоматах L, M, R, S являются целые 0, 1,..., 24, в каждом из них под действием входного символа состояние q может либо сохраниться, либо измениться к состоянию q+1 mod 25. В соответствии с ключом шифра криптоавтоматы L, M, R делятся на «быстрый» — f, «средний» — m и «медленный» — s. Состояние S изменяется под действием каждого входного символа. Среди L, M, R подобное делает только один, который выбирается криптоавтоматом stepping в зависимости от состояния S и m так, что f всякий раз изменяет своё состояние. Но есть два исключения:
— если S находится в состоянии 24, то состояние меняет m;
— если S в состоянии 23, а m — в 24, то состояние меняет s.
Схема шифрования в Purple
Все каналы связи между компонентами машины подразделяются на информационные и управляющие. Информационные передают символы латинского алфавита (алфавита шифра). Управляющие передают символы состояний от L, M, R, S к stepping и логические 0, 1 от stepping к L, M, R.
Последние два символы взяты произвольно и берутся для обозначения команд управления «сохранить состояние», «изменить состояние». Информационные каналы, связанные с S, передают гласные латинские буквы, а связанные с L, M, R передают латинские буквы. Функция информационного выхода каждого автомата-преобразователя при любой фиксации его состояния выступает в роли некоторой биекцией на соответствующем информационном алфавите.
Шифр Закревского
Аркадий Дмитриевич Закревский (1928 — 2014 г.г.)
Выдающийся кибернетик, специалист в области дискретной математики, алгоритмического и логического проектирования Аркадий Дмитриевич Закревский в своей рукописи (1959 г.) предложил вариант симметричного конечно-автоматного шифра.
Шифр инициализируемый по ключу криптоавтоматом C = <X, Q, Y, K, ψ, ϕ>, в котором множество ключей K = Q × K0 таково, что Υ = {Ck = <X, Q, Y, ψk, ϕk>: k ∈ K} есть множество всех сильносвязных автоматов с фиксированными алфавитами X, Q, Y и биективными функциями ϕkq: X → Y, определяемыми при любых k ∈ K и q ∈ Q как ϕkq(x) = ϕ(k, x, q) для всех x ∈ X. На ключе k = (q0, k0) ∈ K сообщение α ∈ X* зашифровывается автоматом Ck из «ключевого» (определяемого ключом k) начального состояния q0 ∈ Q в криптограмму β = ¯ϕk(α, q0) ∈ Y*, которая расшифровывается в сообщение α = ¯ϕ0 k(β, q0) автоматом Dk = <Y, Q, X, ψ0 k, ϕ0 k>, где функции ψ0 k и ϕ0 k определяются по правилу: если ψk(x, q) = s и ϕk(x, q) = y, то ψ0 k(y, q) = s и ϕ0 k(y, q) = x для всех x ∈ X, y ∈ Y, q ∈ Q.
Пусть в C здесь |X| = |Y | = m и |Q| = n. Тогда непосредственно подсчитывается, что |Υ| > n(m−1)nnm!
Два ключа k и k' в K называются эквивалентными, если автоматы Ck, Ck' в Υ осуществляют одно и то же отображение из X* в Y* из своих «ключевых» начальных соостояний q0, q'0 ∈ Q соответственно, т. е. если ϕ¯k,q0 = ¯ϕk',q'0. Обозначим κ количество всех классов эквивалентности ключей в K, или, что то же самое, число всех попарно неэквивалентных ключей рассматриваемого шифра.
Автор: ua-hosting.company
