Experimental estimation for software implementation speed of some block cipher's transformations.pdf Основными параметрами современных блочных криптосхем являются линейныепреобразования, действующие на блоке, и нелинейные преобразования, представляющиесобой параллельное применение нелинейных преобразований (подстановок) наблоках меньшей длины. В [1] указывается, что для обеспечения стойкости блочнойкриптосхемы линейные преобразования должны обладать достаточно хорошими рассеивающимисвойствами. При этом основная трудоемкость одной итерации блочнойкриптосхемы, как правило, приходится на вычисление линейного преобразования.При синтезе линейных преобразований разработчики пытаются достичь «золотойсередины» между такими относительно противоречивыми требованиями к линейномупреобразованию блочной криптосхемы, как максимизация скорости вычисления, минимизацияпамяти, необходимой для хранения, и достаточно хорошие рассеивающиесвойства.На данный момент в криптографической практике для реализации на ЭВМ однойитерации блочной криптосхемы используют подход (см., например, [2]), которыйзаключается в использовании заранее вычисленных таблиц, в которых хранится результаткомпозиции нелинейного и линейного преобразований. Результат примененияодной итерации (после наложения ключа) представляет собой сумму по модулю 2 содержимоготаблицы, взятого по байтам-адресам. Наилучшие показатели по скоростишифрования и количеству тактов процессора, необходимых для зашифрования одногобайта, достигаются в случае, если таблица может быть целиком помещена в кэшпамятьпроцессора.Однако с ростом и - длины блока - увеличивается и размер памяти, который необходимдля хранения таблиц. Это приводит к двум негативным с точки зрения реализациипоследствиям. Во-первых, если криптосхема реализуется на вычислительныхсредствах с ограничениями по памяти (например, смарт-карты), то на длину блоканакладываются существенные ограничения. Во-вторых, таблицы слишком большихразмеров могут целиком не помещаться в кэш-память процессора, что существенноснижает скорость шифрования.Пусть длина блока n = m и' = k m' и' , где и' - длина подстановки. В работе [3]предложено использовать линейные преобразования специального вида. В качествелинейного преобразования L рассматривается композиция L(x) = A(P(x)), где P представляетсобой перестановку подвекторов длины и', A = diag(Ai, A2, . . . , A&), Ai = A,i = 1,...,k, A E GL(m' u' ,2). При хранении в виде заранее вычисленных таблицтакое линейное преобразование занимает в k2 раз меньше памяти, чем произвольноелинейное преобразование.Обычно на практике, за редким исключением, и' = 8, поэтому открытым остаетсявопрос, при каких значениях m' заранее вычисленные таблицы линейного преобразованияцеликом помещаются в кэш-память. Формально, для хранения таблиц необходимо2n (m')2u' бит. Так как на ЭВМ помимо программы шифрования может быть запущеноеще достаточно большое количество других приложений, то выполнение неравенства2п' (m')2 и1 < Ncache (где Ncache - размер кэш-памяти процессора) является необходимым,но не достаточным условием полного размещения таблицы в кэш-памяти.С целью определения наилучших с точки зрения скорости шифрования и количестватактов процессора, необходимых для обработки одного байта информации, значенийm' E {2, 4, 8,16} при различных значениях k E {2, 3, .. ., 8} и и' = 8 и сопоставимомпо криптографическим характеристикам числе итераций были проведены эксперименты,которые показали, что оптимальными значениями являются m' = k = 2,m' = k = 4 и m' = k = 8, которые соответствуют длине блока, равной 32, 128 и 512 битсоответственно. При данных значениях m' и k скорость шифрования в 2,5-1,3 разавыше, чем при любой другой фиксации.

Скачать электронную версию публикации