Модель шифрования при помощи подстановочно-перестановочной сети (SP-сеть)¶
Изучаем принципы организации современной системы шифрования на теоретическом примере.
Описание задачи¶
Большинство современных информационных систем используют шифр AES (или подобный ему) для шифрования сообщений. Эти шифры базируются на алгоритме подстановочно-перестановочной сети (SP-сети).
Если требуется просто зашифровать или расшифровать сообщение, в Julia есть библиотеки наподобие
AES.jl, позволяющие зашифровать и расшифровывать последовательности байтов.
Представленный здесь алгоритм не обязательно является надежным шифром. "Сильным" этот шифр может сделать правильный выбор параметров S- и P-блоков, а также лучших функций для порождения раундовых ключей и их добавления в шифротекст, есть и другие дополнительные механизмы, описанные в стандартах. Мы лишь создаем учебный пример, который в некоторых отношениях удобно анализировать и дорабатывать.
Общий вид модели¶
Шифр на основе SP-сети получает на вход блок данных и ключ и совершает несколько раундов, состоящих из чередующихся стадий подстановки (substitution) и перестановки (permutation) битов в блоке.
# Загрузим модель, если она еще не открыта на холсте
if "sp_net_cipher_model" ∉ getfield.(engee.get_all_models(), :name)
engee.load( "$(@__DIR__)/sp_net_cipher_model.engee");
end
model_data = engee.run( "sp_net_cipher_model" );
println( "Количество ошибок передачи: ", convert(Int, model_data["Кол-во ошибок"].value[end]) )
Дальше мы раскроем каждый блок модели и посмотрим, как работает один отдельный раунд.
Модель с тремя раундами шифрования¶
Если раскрыть каждую из подсистем, можно получить очень наглядное представление работы каждого раунда работы алгоритма (модель sp_net_cipher_model_3R_expand).
Она позволяет увидеть настройки каждого этапа и проверить, что будет, если настройки подстановочных или перестановочных блоков не согласованы.
Запустим эту модель и проверим, что передача сообщения с одинаковыми байтами AAAAAAAA порождает разные байты шифротекста:
# Загрузим модель, если она еще не открыта на холсте
if "sp_net_cipher_model_3R_expand" ∉ getfield.(engee.get_all_models(), :name)
engee.load( "$(@__DIR__)/sp_net_cipher_model_3R_expand.engee");
end
model_data = engee.run( "sp_net_cipher_model_3R_expand" );
source_message = collect(model_data["Блок сообщения"]).value
cipher_text = UInt16.(collect(model_data["Зашифрованный блок"]).value)
received_message = UInt16.(collect(model_data["Расшифрованный блок"]).value)
source_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in source_message])... )
cipher_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in cipher_text])... )
received_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in received_message])... )
println( "Отправленное сообщение: ", join( vcat( string.(source_bytes, base=16)... ), " " ) )
println( "Зашифрованное сообщение: ", join( vcat( string.(cipher_bytes, base=16)... ), " " ))
println( "Полученное сообщение: ", join( vcat( string.(received_bytes, base=16)... ), " " ) )
println( "Отправленная строка: ", String( source_bytes ))
println( "Полученная строка: ", String( received_bytes ))
Заметим что шифротекст начал повторяться начиная с 17 блока.
Модель однораундового шифра¶
Если упростить сеть до одного раунда, модель будет выглядеть следующим образом:
Мы видим все привычные элементы SP-сети:
- функцию перемешивания битов ключа с битами открытого текста (
XOR), - блоки подстановки, принимающие битовые (
Bool) векторы на вход, - блоки пермутации битов, который принимает на вход вектор из четырех объединенных результатов предыдущей операции.
Если все параметры S- и P- блоков выставлены правильно, то на выходе мы получаем то же сообщение, что и было на входе.
# Загрузим модель, если она еще не открыта на холсте
if "sp_net_cipher_model_1R" ∉ getfield.(engee.get_all_models(), :name)
engee.load( "$(@__DIR__)/sp_net_cipher_model_1R.engee");
end
model_data = engee.run( "sp_net_cipher_model_1R" );
Изучим отправленное и принятое сообщение:
source_message = collect(model_data["Блок сообщения"]).value
cipher_text = UInt16.(collect(model_data["Зашифрованный блок"]).value)
received_message = UInt16.(collect(model_data["Расшифрованный блок"]).value)
source_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in source_message])... )
cipher_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in cipher_text])... )
received_bytes = vcat( reverse.([reinterpret( UInt8, [UInt16(c)]) for c in received_message])... )
println( "Отправленное сообщение: ", join( vcat( string.(source_bytes, base=16)... ), " " ) )
println( "Зашифрованное сообщение: ", join( vcat( string.(cipher_bytes, base=16)... ), " " ))
println( "Полученное сообщение: ", join( vcat( string.(received_bytes, base=16)... ), " " ) )
println( "Отправленная строка: ", String( source_bytes ))
println( "Полученная строка: ", String( received_bytes ))
Создание раундовых ключей¶
Алгоритм создания раундовых ключей организован следующим образом:
- последовательность байтов, образующая ключ, разбивается на блоки по 64 бита
- блоки перекрываются (ключ
d0 9a d0 bb d1 8e d1 87порождает блокиd0 9a d0 bb,9a d0 bb d1,d0 bb d1 8eи т.д.) - ключ используется циклично
64-битный блок ключа разделяется на 4 раундовых ключа по 16 бит (последовательно), из которых мы используем только три первых раундовых ключа.
Соображения по работе с моделью¶
При интерпретации или планировании изменений модели стоит учитывать следующие особенности:
- сообщение и ключ передаются в модель циклически и никогда не заканчиваются,
- полный цикл работы с одним блоком выполняется за один такт моделирования без задержек
- поэтому на верхнем уровне мы работаем не с векторами из битов, а с числами
UInt16,UInt32и т.д., - входное сообщение и раундовые ключи подаются в модель блоками по 16 бит, все четыре S-блока на каждом раунде принимают на вход блоки по 4 бита, а P-блоки с векторами из 16 бинарных бит,
- параметры перестановки внутри S- и P-блоков берутся не из кодовой книги, а порождаются операцией
shuffleс указаннымseed, - сообщение передается в алгоритм неперекрывающимися блоками, а блоки ключа порождаются окном со смещением в один байт.
Заключение¶
Мы создали модель, которая позволяет изучить все этапы шифрования сообщения при помощи SP-сети и внести любые изменения в архитектуру этого алгоритма, не погружаясь в технические вопросы программирования.