Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Производительность кода на примере ГОСТ 2814789 симметричного шифрования Наверняка все слышали о терм

Работа добавлена на сайт samzan.ru: 2015-07-10

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 29.1.2022

«Производительность кода»

(на примере ГОСТ 28147-89 симметричного шифрования)

Наверняка все слышали о термине «Производительность процессора», этот объективный, вычисляемый параметр меряют в Флопах, но большинство измеряет его в Гигагерцах, по наивности полагая что это одно и тоже. Термин «Производительность кода» неизвестен никому, и сразу объясню почему. Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако «Производительность кода», также как и «Производительность процессора»  имеет объективные характеристики, которые поддаются измерениям. Статья именно о производительности кода выполняемого процессорным ядром.

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках…..

Теперь по серьезному. В современных процессорах основными преобразованиями являются действия над 32 битными числами, все остальное по большому счету экзотика. Поэтому учитывать будем главное,- операции с 32 битными числами. Как вы думаете, сколько 32битных операций одновременно может выполнить ядро современного процессора?

Студент скажет одну, его преподаватель подумает и скажет четыре, профессионал скажет что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12RTT-шек. Это максимально, я честно признаюсь, такого кода раньше не писал, но в этой статье попытаюсь превзойти себя и все-таки выдать 12RTT. Код с одновременным выполнением двенадцати 32битных операций я в этой статье продемонстрирую, пускай и с некоторыми оговорками.

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно будет иметь производительность в 1RTT-шку. Такой  производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня и интерпретаторы виртуальных машин.

Пока диапазон параметра «производительность кода» может варьироваться от  1RTT до 12RTT, причем с дробными величинами, отражающими неравномерность загрузки исполнительных устройств ядра процессора в период выполнения кода.

Не нужно считать что, показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1RTT). В этом случае при 100% загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности.

Другими словами при максимальной загрузке процессора, показываемого например в диспетчере задач ОС Windows, его реальная производительность может варьироваться от 1RTT до 12RTT.  Увидев в окне производительности 100% загрузку на каком либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

Единственным критерием косвенной оценки работы процессорного ядра с максимальной производительностью может служить его энергопотребление, и как следствие шум кулера. Вот если кулер зашумел, тогда, да,- загрузка пошла по максимуму.

Но хватит общих понятий, как говорится, «короче, Склифасовский».

Традиционная реализация ГОСТ 28147-89

Не являясь профессионалом в области информационной безопасности, всё же знаком с темой шифрования. Для меня эта тема близка с точки зрения программиста, который, как и самый первый программист, когда было только слово (информация), после дня (ночи) тяжелого труда, усталый, смотрит на результат своего труда и думает: «это хорошо»….

Заняться конкретной темой симметричного поточного шифрования меня сподвигли разговоры, с лично мной, глубоко уважаемым, профессиональным криптографом. И занявшись ей, постарался сделать именно «хорошо», а в этой теме «хорошо»,- значит быстро, а быстро значит выполнять за единицу времени максимальное число операций. Другими словами встала задача написания программного кода с максимальным значением RTT.

Криптографическое преобразование по ГОСТ 28147-89 используется для поточного  шифрования информации в каналах связи и на дисковых накопителях.

В настоящее время повсеместно применяется программная реализация данного ГОСТ на РОН центрального процессора. В известных методах реализации ГОСТ вся секретная информация (ключи шифрования, блоки замен) размещаются в оперативной памяти.

Это снижает надежность шифрования,  поскольку, имея дамп оперативной памяти, можно полностью выявить все секретные элементы криптопреобразования.

Кроме этого, метод имеет ограничения по быстродействию, обусловленные расположением основных объектов криптопреобразования в ОП и неполной загрузкой исполнительных устройств ALU. Современные процессоры, реализуя криптопроцедуру по известному методу могут обеспечить скорость шифрования на уровне 40-60 мегабайт в секунду.

Если уж разбираться до конца, то причиной низкого быстродействия и слабой защищенности криптопреобразования является программная реализация блока подстановок.

Вот как он описан в официальном документе ГОСТ 28147-89  :

По п. 1.2. ГОСТ этот блок реализует тетрадные (по четыре бита) перестановки в 32битном слове, но архитектура процессора х86/64 и его система команд не способна  эффективно манипулировать тетрадами.

Для программной реализации блока подстановок используют специальные таблицы в оперативной памяти подготавливаемые на этапе инициализации криптофункции. Эти таблицы объединяют узлы замен смежных тетрад в байтовые таблицы размером 8х8 бит, таким образом в оперативной памяти размещается четыре 256 байтных таблицы.

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в этих таблицах  дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32 битного слова (следующая операция алгоритма преобразования по ГОСТ).

Пример реализации ГОСТ 28147-89 по данному методу показан в приложении №1.

Информация блока подстановок является секретным компонентом криптофункции, вот как это сформулировано в официальном документе ГОСТ 28147-89:

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТ 28147-89 п.1.7., поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. ФСБ, сертифицирующая в том числе и программные реализации шифрования по ГОСТ 28147-89 на данное нарушение смотрит мягко говоря снисходительно. Если для размещения ключей в ОП ФСБ еще требует наличия «фигового листочка», в виде маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде.

ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТ 28147-89 п.1.7..

И это не смотря на общеизвестные методы взлома шифров через съём дампа памяти….

К вопросу хранения ключей и блоков замен во внутренних регистрах процессора вернемся чуть позже, есть красивое и главное быстрое решение, а пока только ключи шифрования будем хранить в ММХ регистрах, это надежнее.

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1RTT-шку, теперь напишем код с производительностью 2RTT-шки.

Многопоточная реализация ГОСТ 28147-89

Единственной возможностью ускорить криптопроцедуры в известном алгоритме является введение многопоточности. Смысл такого изменения реализации алгоритма заключается в том, чтобы обсчитывать сразу несколько блоков данных параллельно.

Большинство программистов подразумевает под параллельной обработкой исключительно работу нескольких процессорных ядер, синхронизированных через прерывания и семафоры в памяти.

Однако существует и иной вариант параллельной обработки данных на одном единственном ядре процессора. Поясню эту неочевидную мысль

Современные процессоры имеют в своем составе как минимум два, а то и 3-6 арифметико/логических устройств. Эти АЛУ (FPU, блоки адресной арифметики и т.д.) могут работать независимо друг от друга, единственным условием их параллельной работы является непересекающиеся программные объекты, которыми они оперируют. Другими словами в командах, которые одновременно выполняют АЛУ, адреса памяти и номера регистров должны быть разными. Либо в общие регистры и адреса памяти, к которым обращаются различные исполнительные устройства процессора, не должно выполняться операций записи.

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32-64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает  на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

Большинство программных последовательностей, генерируемых автоматически (компиляторами) не могут загрузить все АЛУ и  FPU находящиеся в ядре процессора, в этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы ГиперТрейдинга и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

Компиляторы, даже самые оптимизированные, и тем более движки виртуальных машин, не могут сформировать оптимизированный код с точки зрения быстродействия. Только программист с инженерными знаниями может написать такой оптимизированный код, причем инструментом для написания такого кода является исключительно Ассемблер.

Характерной иллюстрацией возможности выполнения нескольких независимых программных потоков на одном ядре процессора служит реализация ГОСТ, выполняемого в два потока на единственном ядре процессора. Идея кода проста, имеется два блока данных для шифрации/дешифрации, но одно ядро процессора, которое будет выполнять преобразование. Можно выполнить для этих двух блоков данных преобразование последовательно, так и делается до настоящего времени. В этом случае, время, требуемое на выполнение преобразований, удваивается.

Но можно поступить и иначе. Можно команды, относящиеся к обработке разных блоков данных чередовать, вот как эти варианты можно представить графически:

На рисунке верхний пример показывает обычный порядок выполнения обработки двух независимых блоков данных. Сначала обрабатывается первый блок, затем процессор переходит к обработке второго блока. Естественно, результирующее время равно удвоенному времени необходимого для обработки одного блока, а исполнительные устройства ядра процессора загружены не полностью.

Ниже показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

Это конечно очень упрощенное объяснение принципа параллельного выполнения программных потоков на единственном ядре, реально все гораздо сложнее. В реальности нужно учитывать конвейерную архитектуру исполнительных устройств, ограничения на одновременный доступ в Кеш и блок регистров РОН, наличие узлов адресной арифметики, коммутаторов и много еще чего… Так что тема для профессионалов, которых можно «пересчитать по пальцам»… одной руки…

Метод параллельного шифрования эффективно реализуется только для 64битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТ 28147-89 по данному методу показан в приложении №2.

Ясно, что данная реализация ГОСТа имеет производительность кода 2RTT-шки, а теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение №1) составляет 352 такта и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТ (приложение №2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6Ггц.

Интересная получается картина, код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но думаю читатели уже поняли почему на процессоре происходят такие чудеса….

Теоретически код из второго примера должен выполняться за тоже количество тактов, что и код из первого примера, но узел планировщика разрабатывают хоть и инженеры фирмы Интел, но тоже люди, а мы все далеки от совершенства… Так что имеется возможность оценить эффективность их творения. Этот код будет работать и на процессоре AMD, так что можно сравнить их результаты.

Если кто мне не верит «на слово», то для таких неверующих прилагаются тестовые программы с счетчиками тактов. Программы в исходных кодах, естественно на Ассемблере, так что есть возможность проверить мои слова, а заодно и подсмотреть некоторые хитрости профессионального коддинга.

Использование SSE  регистров и AVX команд современных процессоров для реализации ГОСТ 28147-89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТ 28147-89  на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE регистрах.

На одном SSE регистре можно разместить сразу две таблицы из 16 строк. Таким образом, четыре SSE регистра позволят полностью разместить все таблицы замен. Единственным условием такого размещения является требование чередования, согласно которому тетрады одного байта должны помещаться в разные  SSE регистры. Кроме этого целесообразно размещать младшие и старшие тетрады входных байтов соответственно в младших и старших тетрадах байтов SSE регистров.

Эти требования обуславливаются оптимизацией под имеющийся набор AVX команд.  

Таким образом, каждый байт SSE регистра будет содержать две тетрады, относящиеся к разным байтам входного регистра блока подстановок, при этом позиция байта на SSE регистре однозначно соответствует индексу в таблице замены блока подстановки.

Схема одного из возможных размещений узлов замены на SSE регистрах показана на рисунке:

Размещение секретной информации узлов замен на SSE регистрах повышает защищенность криптопроцедуры, но полная изоляция этой секретной информации возможна при соблюдении следующих условий:

- Ядро процессора переведено в режим Хоста Гипервизора и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.

- Загрузка SSE регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).

- Программы  криптопроцедур по ГОСТ размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).

Выполнение этих требований позволит гарантировать полную изоляцию и неизменность программного кода криптопроцедур и используемой в них секретной информации.  

Для эффективной выборки из SSE регистров тетрад используется имеющиеся в составе блоков FPU многовходовые байтовые коммутаторы. Эти коммутаторы позволяют осуществлять пересылки из любого байта источника в любой байт приемника, по индексам находящемся в специальном индексном SSE регистре. Причем параллельно выполняется пересылка для всех 16 байт SSE регистра- приемника.

Имея узлы хранения подстановок на SSE регистрах и многовходовый коммутатор в блоках FPU можно организовать следующее преобразование в блоке подстановок:

В этой схеме входной регистр в каждой тетраде задает адрес для соответствующего коммутатора, который по шине данных передает из накопителей узлов замены информацию в выходной регистр.

Такую схему можно организовать тремя способами:

- Создать соответствующий дизайн чипа, но это для нас «фантастика».

- Перепрограммировать микрокод и создать собственную процессорную команду для реализации этой функции на существующих процессорах, - это уже не «фантастика», но к сожалению, не реально в нынешних условиях.

- Написать программу на официальных командах AVX, вариант пускай и не очень эффективный, но зато осуществим «здесь и сейчас». Поэтому этим и займемся далее.

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Первый операнд которой является приемником информации из коммутаторов, второй операнд является источником, к которому подключены входы коммутаторов, а третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором и значение в нем задает номер направления с которого коммутатор считывает информацию. Вот описание этой команды из официальной документации фирмы Интел:

А вот схема работы этой команды, - изображена только половина SSE регистров, для второй половины все аналогично:

Коммутатор использует только младшие четыре бита для определения направления коммутации, последний бит в каждом байте используется для принудительного обнуления соответствующего байта приемника, но эта функция коммутатора в нашем случае пока не востребована.

Программа с выборкой тетрад через коммутаторы FPU  было написана, но я даже не стал ее помещать в приложение, – слишком убого. Иметь регистр размером 128 бит и использовать в нем только 32бита,- не профессионально.

Как говорится: «Наш финиш горизонт», поэтому выжимать, так выжимать,…. будем прессовать и складывать в пакеты…

Это не игра слов, а суровая FPUшная реальность, регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» - пакет, которая ставится перед мнемоникой команды и не менее магические буковки «Q», «D», «W», «B» которые ставятся в конце и объявляют на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE регистра на четыре 32битных блока, соответственно все команды будут иметь сначала префикс «P»  а в конце символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, т.е. в параллель рассчитывать четыре блока данных.

Программа реализующая этот метод имеется в приложении №3, там же все пояснения, если кто либо заинтересуется в подробностях.

Но прессовать, так прессовать, в современных процессорах имеется как минимум два блока FPU и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных.

Такая программка была написана и ее можно посмотреть в приложении №4, только смотреть осторожно, можно слететь с катушек, это что называется «код не для всех…..»

Цена вопроса

Использование SSE регистров для хранения узлов замены понятно, - дает некую гарантию изоляции секретной информации, а вот расчет самой криптофункции на FPU это неочевидно. Поэтому были проведены замеры времени выполнения стандартных процедур по методу прямой замены в соответствии с ГОСТ 28147-89 для четырех потоков и для восьми потоков.

Для четырех потоков была получена скорость выполнения 472 процессорных тактов. Таким образом, для процессора с частотой 3,6 Ггц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 Ггц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков соответственно со скоростью 392 мегабайт в секунду.

Как может заметить читатель, код в примере №3 имеет производительность 4RTT, а код в примере №4 имеет производительность 8RTT. В этих примерах на SSE регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20% увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены  с использованием универсальных AVX команд, имеющихся как в процессорах фирмы Интел, так и в процессорах AMD. Если выполнить оптимизацию под процессора AMD, результат будет значительно лучше. Звучит поперек тренда, но, тем не менее это правда, и вот почему, - процессора AMD имеют дополнительный набор команд, так называемое XOR расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТ.

Имеются ввиду команды логического пакетного сдвига байтов и пакетного циклического сдвига двойных слов. В примерах приведенных в приложениях №3,4 используются последовательности универсальных команд реализующих необходимое преобразование в первом случае одна «лишняя» команда, а в другом случае сразу четыре лишних команды. Так что резервы оптимизации есть, и они не малые.

Если речь зашла об дальнейшей оптимизации нелишне помнить о наличие 256 битных регистров (YMM регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только  перспектива, на данный момент процессора очень сильно замедляются, когда выполняют 256 битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM регистрах выигрыша не даёт. Но это только пока, на новых моделях процессоров несомненно будет увеличено быстродействие 256 битных команд и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600-700мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

Но будем прессовать дальше, наша цель получить 12RTT-шек, это можно сделать выполняя одновременно команды на всех имеющихся в ядре процессора FPU, а их у Интел три штуки, мы же пока задействовали только два, так что вперед!

Опять встает вопрос количества регистров, их не хватает, чтобы раскрутить такой алгоритм. Но нам поможет режим ГиперТрейдинга. У процессорного ядра имеется второй набор регистров, доступных в режиме логических процессоров. Поэтому будем выполнять один и тот же код сразу на двух логических процессорах. В этом режиме исполнительных устройств у нас конечно не прибавится, но за счет чередования можно получить полную загрузку всех исполнительных устройств.

Рассчитывать на прибавку в 50% конечно не приходится, узким местом становится Кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8RTT), но он имеется в программных файлах . Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Интел, у AMD только два блока FPU на два процессорных модуля (аналог режима ГиперТрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим аналогичном режиму Гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE регистрах и получить те же 12RTT. Этот вариант я не проверял, но думаю на AMD код в 12 RTT будет работать более эффективно, желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно

Серьезный вопрос, но с достаточно простым ответом, - это нужно всем. Скоро все подсядем на облака, будем там хранить и данные и программы, а там, ой как хочется обустроить свой собственный, приватный уголок. Для этого придется шифровать трафик, и скорость криптопреобразования будет главным определяющим фактором комфортной работы в облаке. Выбор алгоритма шифрования у нас не велик, либо ГОСТ, либо AES.

Причем, как это ни странно, встроенное в процессора шифрование по AES алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100-150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Там проблема опять в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь ввиду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3-6RTT практически нет, компиляторы вообще генерят код на уровне 1-2,5RTT, А основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний, что ассемблер, что какой-нибудь там СИ-шарп,- все едино, как говорится, «что в лоб, что по лбу».

Но не все так печально, в «сухом остатке» после недели бессонных ночей имеется новый алгоритм реализации ГОСТ, который грех не запатентовать. И заявки на патенты (целых три) уже оформлены и поданы, так что господа коммерсанты, выстраивайтесь в очередь, женщинам и детям скидка.

Приложение 1.

Основной цикл шифрования на РОН в один поток.

Четыре таблицы узлов замен расположены в памяти, каждая таблица имеет 256 записей по 4 байта, в каждой записи учтен циклический сдвиг выходного байта на 11 позиций влево.

Цикл простой замены состоит из 32 проходов, макросы с1 и с2 чередуются, для того чтобы после каждого прохода не выполнять команду переноса информации из накопителя1 в накопитель2

Use32

;///////////////////////////////тестовый модуль 1 проход

macro c1 reg;

{

    ;//в начале макроса ключ в есх

    ;//в конце макроса ключ для следующей итерации в edx

    ;//в начале макроса  накопитель1 - еaх, накопитель2 - еbх

    ;//в конце  макроса  накопитель1 - еbх, накопитель2 – еaх

    ;//Узел замен 1байт расположен в памяти по адресу esp+01000h

    ;//Узел замен 1байт расположен в памяти по адресу esp+01400h 

    ;//Узел замен 1байт расположен в памяти по адресу esp+01800h 

    ;//Узел замен 1байт расположен в памяти по адресу esp+01с00h 

    ;//Ключи расположены в ММХ регистрах

 

;///////////////////////////////////////////////////////////////////////////

add ecx,eax;

 movzx edx,cl;                           выборка индекса для узла замен 1б

  movzx esi,ch;                          выборка индекса для узла замен 2б

   xor ebx,dword [esp+01000h+edx*4];     накопитель + узел замен 1байт

    movd edx,reg;                        чтение ключа для следующего макроса

     xor ebx,dword [esp+01400h+esi*4];   накопитель + узел замен 2байт

      shr ecx,16;                        3,4 байты на место 1,2 байта

       movzx edi,cl;                     выборка индекса для узла замен 3б

        movzx ecx,ch;                    выборка индекса для узла замен 4б

         xor ebx,dword [esp+01800h+edi*4];  накопитель + узел замен 3байт 

          xor ebx,dword [esp+01c00h+ecx*4]; накопитель + узел замен 4байт 

}

;///////////////////////////////тестовый модуль 2 проход

macro c2 reg;

{

;//Тоже самое что и макрос с1, только:  

        ;//в начеле макроса ключ в еdх,

        ;//в конце макроса ключ для следующей итерации в ecx

        ;//в начале макроса  накопитель1 - еbх, накопитель2 - еaх

        ;//в конце  макроса  накопитель1 - еaх, накопитель2 - еbх

;//////////////////////////////////////////////////////////////////////////

add edx,ebx;

 movzx ecx,dl;

  movzx esi,dh;

   xor eax,dword [esp+01000h+ecx*4];

    movd ecx,reg;                        чтение ключа для следующего макроса

     xor eax,dword [esp+01400h+esi*4];

      shr edx,16;

       movzx edi,dl;

        movzx edx,dh;

         xor eax,dword [esp+01800h+edi*4];

          xor eax,dword [esp+01c00h+edx*4];

}

Приложение 2.

Основной цикл шифрования на РОН в два потока.

Тоже самое преобразование, что и в приложении №1, только накопители 1,2 первого потока используют регистры R8, R9 а накопители второго потока используют регистры R10, R11.

Узлы замен для обоих потоков одинаковые, но ключи могут быть для каждого потока индивидуальными.

Чередование команд для первого и второго потока сделано с учетом максимальной загрузки 2АЛУ, 2блоков адресной арифметики и 2коммутаторов Кеш-памяти.

Use64

;///////////////////////////////тестовый модуль 1 проход

macro c1 reg;

{

;//////////////////////первый поток 1-2 байт

add ecx,r8d;                           суммирование с ключом первый поток

 movzx edi,cl;

  movzx esi,ch;

   xor r9d,dword [esp+01000h+edi*4];

    movd edx,reg;                      чтение ключа для следующего макроса

     xor r9d,dword [esp+01400h+esi*4];

      shr ecx,16;

;//////////////////////второй поток 1-2 байт

add eax,r10d;                          суммирование с ключом второй поток

 movzx r15d,al;

  movzx ebp,ah;

   xor r11d,dword [esp+01000h+r15d*4];

    movd ebx,reg;                      чтение ключа для следующего макроса

     xor r11d,dword [esp+01400h+ebp*4];

      shr eax,16;

;//////////////////////первый поток 3-4 байт

 movzx edi,cl;

 xor r9d,dword [esp+01800h+edi*4];

  movzx esi,ch;

   xor r9d,dword [esp+01c00h+esi*4];

;//////////////////////второй поток 3-4 байт

movzx r15d,al;

 xor r11d,dword [esp+01800h+r15d*4];

  movzx ebp,ah;

   xor r11d,dword [esp+01c00h+ebp*4];

}

;///////////////////////////////тестовый модуль 2 проход

macro c2 reg;

{

;//////////////////////первый поток 1-2 байт

add edx,r11d;                          суммирование с ключом первый поток

 movzx edi,dl;

  movzx esi,dh;

   xor r10d,dword [esp+01000h+edi*4];

    movd ecx,reg;                      чтение ключа для следующего макроса

     xor r10d,dword [esp+01400h+esi*4];

      shr edx,16;

;//////////////////////второй поток 1-2 байт

add ebx,r9d;                           суммирование с ключом второй поток

 movzx r15d,bl;

  movzx ebp,bh;

   xor r8d,dword [esp+01000h+r15d*4];

    movd eax,reg;                      чтение ключа для следующего макроса

     xor r8d,dword [esp+01400h+ebp*4];

      shr ebx,16;

;//////////////////////первый поток 3-4 байт

 movzx edi,dl;

 xor r10d,dword [esp+01800h+edi*4];

  movzx esi,dh;

   xor r10d,dword [esp+01c00h+esi*4];

;//////////////////////второй поток 3-4 байт

movzx r15d,bl;

 xor r8d,dword [esp+01800h+r15d*4];

  movzx ebp,bh;

   xor r8d,dword [esp+01c00h+ebp*4];

}

Приложение №3.

Основной цикл шифрования на SSE в четыре потока.

SSE6, SSE7 содержат поочередно накопители1  и накопители2 (четыре накопителя по 4 байта каждый)

Сначала готовятся индексные регистры для работы коммутатора

- младшие тетрады в байтах маскируются

- старшие тетрады сначала сдвигаются на место младших и затем маскируются

Индексный регистр SSE2 содержит индексы младних тетрад 1,2 байта и индексы старших тетрад 3,4 байта.

Индексный регистр SSE3 содержит индексы младних тетрад 3,4 байта и индексы старших тетрад 1,2 байта.

Технологические маски содержатся в ОП. Маска имеет размер 16 байт, в комментариях указана маска только для одного потока, остальные три маски аналогичные.

После выборки через коммутаторы информации с узлов замен (регистры SSE8, SSE9, SSE10, SSE11). С каждого узла замены считывается две актуальные тетрады, остальные мусор.

Чтобы отсечь мусор считанная информация маскируется технологическими масками, отсекающими лишние тетрады. Маски имеют размер 16 байт, в комментарии показана маска для одного потока, остальные три потока имеют аналогичные маски.

Затем производится сборка тетрад в полное 32битное слово для каждого потока.

Собранное слово сдвигается циклически на 11 позиций влево, после чего складывается с накопителем1.

Циклический сдвиг выполнен на командах логического сдвига, поскольку в системе команд AVX отсутствуют команды ротации.

Пример кода не оптимизирован по быстродействию, но максимально удобен для понимания.

Ключи шифрования для каждого потока находятся в ОП.

Use64

macro zxmm kl

{

;/////подготовка блока замен 1-2байт

vpand xmm2,xmm5,[esp+80h];      000000f0fh;     маска м-тетрад 1b,2b

 vpsrlq xmm3,xmm5,4;

  vpand xmm13,xmm3,[esp+090h];  00f0f0000h;     маска с-тетрад 4b,3b

   por xmm2,xmm13;

;/////подготовка блока замен 3-4байт

pand xmm3,[esp+0a0h];           000000f0fh;     маска c-тетрад 1б,2b

 pand xmm5,[esp+0b0h];          00f0f0000h;     маска 4b-mт,3b-mt

  por xmm3,xmm5;

;/////////блок замен 1-2 байты

vpshufb xmm12,xmm8,xmm2;        блок замен      замена 1б-мч, 4б-сч

 pand xmm12,[esp];              0f000000fh;     маска  1b-мт,4-ct

  vpshufb xmm13,xmm9,xmm2;      блок замен      замена 2б-мч, 3б-сч

   pand xmm13,[esp+20h];        000f00f00h;     маска  2б-mt,3b-ct

;/////////блок замен 3-4 байты

vpshufb xmm14,xmm10,xmm3;       блок замен      замена 3б-мч, 2б-сч

 pand xmm14,[esp+40h];          0000ff000h;     маска  2б-ст, 3bmt

  vpshufb xmm15,xmm11,xmm3;     блок замен      замена 4б-мч, 1б-сч

   pand xmm15,[esp+60h];        00f0000f0h;     маска  1b -ct, 4b-mt

;///////сборка тетрад

por xmm13,xmm12;

por xmm13,xmm14;

 por xmm13,xmm15;

;//////////загрузка следующих ключей

 movdqa xmm5,[esp+100h+kl*16];

}

;///////////////////////////////тестовый модуль 1 проход

macro c1 kl;

{

zxmm kl;

;/////циклический сдвиг на 11 влево

 vpslld xmm12,xmm13,11;          левый сдвиг на 11 позиций

  psrld xmm13,21;                правый сдвиг на 21 позицию

   pxor xmm7,xmm12;              суммирование заполнение и накопитель

    pxor xmm7,xmm13;             суммирование заполнение и накопитель

     paddd xmm5,xmm7;            сложить с ключом накопитель

}

;///////////////////////////////тестовый модуль 2 проход

macro c2 kl;

{

zxmm kl;

;/////циклический сдвиг на 11 влево

vpslld xmm12,xmm13,11;           левый сдвиг на 11 позиций

 psrld xmm13,21;                 правый сдвиг на 21 позицию

  pxor xmm6,xmm12;               суммирование заполнение и накопитель

   pxor xmm6,xmm13;              суммирование заполнение и накопитель

    paddd xmm5,xmm6;             сложить с ключом накопитель

}

Приложение №4.

Основной цикл шифрования на SSE в восемь потоков.

SSE0, SSE1, SSE6, SSE7 содержат поочередно накопители1  и накопители2 (восемь накопителей по 4 байта каждый)

Сначала готовятся индексные регистры для работы коммутатора

- младшие тетрады в байтах маскируются

- старшие тетрады сначала сдвигаются на место младших и затем маскируются той же маской.

Сборка индексных регистров оптимизирована, но суть та же, что и в примере №3

Пример кода не оптимизирован по быстродействию, но максимально удобен для понимания.

Ключи шифрования находятся в ОП.

Use64

macro zxmm kl

{

;/////подготовка блока замен 1 накопитель

 vpsrlq xmm3,xmm5,4;

 pand xmm5,[esp+080h];        технологическая маска выделения младших тетрад

  pand xmm3,[esp+080h];       технологическая маска выделения младших тетрад

;/////замена 1-2байт -м.т.     3-4байт с.т.

vpblendw xmm2,xmm3,xmm5,055h;

;/////замена  1-2байт - с.т.   3-4байт м.т.

pblendw xmm5,xmm3,0aah;

;/////////блок замен 1-2 байты  - 1 накопитель

 vpshufb xmm15,xmm8,xmm2;

 pand xmm15,[esp];

  vpshufb xmm14,xmm9,xmm2;

   pand xmm14,[esp+20h];

    por xmm14,xmm15;

;/////////блок замен 3-4 байты - 1 накопитель

 vpshufb xmm12,xmm10,xmm5;

 pand xmm12,[esp+40h];

  por xmm12,xmm14;

   vpshufb xmm13,xmm11,xmm5;

    pand xmm13,[esp+60h];

;/////подготовка блока замен -2 накопитель

vpsrlq xmm3,xmm4,4;

 pand xmm4,[esp+80h];

  pand xmm3,[esp+080h];

;/////замена 1-2байт -м.т.     3-4байт с.т.

vpblendw xmm2,xmm3,xmm4,055h;

;/////замена  1-2байт - с.т.   3-4байт м.т.

pblendw xmm4,xmm3,0aah;

;/////////блок замен 1-2 байты  - 2 накопитель

 vpshufb xmm14,xmm8,xmm2;

 pand xmm14,[esp];

  vpshufb xmm15,xmm9,xmm2;

   pand xmm15,[esp+20h];

    por xmm14,xmm15;

;/////////блок замен 3-4 байты - 2 накопитель

 vpshufb xmm3,xmm10,xmm4;

 pand xmm3,[esp+40h];

  por xmm14,xmm3;

   vpshufb xmm15,xmm11,xmm4;

    pand xmm15,[esp+60h];

}

;///////////////////////////////тестовый модуль 1 проход

macro c1 kl;

{

zxmm kl;

;/////циклический сдвиг на 11 влево - 1 накопитель

por xmm13,xmm12;

 vpslld xmm12,xmm13,11;

  psrld xmm13,21;

   xorps xmm7,xmm12;

    xorps xmm7,xmm13;             суммирование заполнение1 1 накопитель

     vpaddd xmm5,xmm7,[esp+100h+kl*32];     сложить заполнение с ключом

;/////циклический сдвиг на 11 влево - 2 накопитель

por xmm15,xmm14;

 vpslld xmm14,xmm15,11;

  psrld xmm15,21;

   xorps xmm1,xmm14;

    xorps xmm1,xmm15;             суммирование заполнение1 2 накопитель

     vpaddd xmm4,xmm1,[esp+120h+kl*32];      сложить заполнение с ключом

}

;///////////////////////////////тестовый модуль 2 проход

macro c2 kl;

{

zxmm kl;

;/////циклический сдвиг на 11 влево - 1 накопитель

por xmm13,xmm12;

 vpslld xmm12,xmm13,11;

  psrld xmm13,21;

   xorps xmm6,xmm12;

    xorps xmm6,xmm13;              суммирование заполнение 0 1 накопитель

     vpaddd xmm5,xmm6,[esp+100h+kl*32];       сложить заполнение с ключом

;/////циклический сдвиг на 11 влево - 2 накопитель

por xmm15,xmm14;

 vpslld xmm14,xmm15,11;

  psrld xmm15,21;

   xorps xmm0,xmm14;

    xorps xmm0,xmm15;            суммирование заполнение 0 2 накопитель

     vpaddd xmm4,xmm0,[esp+120h+kl*32];        сложить заполнение с ключом

}




1. формирование резервного страхового фонда предприятия
2. тема государственного регулирования и управления административноправового регулирования в области эконо
3. педагогический кадров Демидовой Л
4. лейтенант служби цивільного захисту М
5.  ВВЕДЕНИЕ3 2 ОСНОВНЫЕ ЗАДАЧИ И ФУНКЦИИ АРХИВОВ ОРГАНИЗАЦИЙ6 3
6. Простейшие сведения о многочленах
7. Історія Геродота- він зараховує до скіфів і до Великої Скуфі всі племена що розташовувалися на північ Гр
8. Комсомольский ВДЦ
9. Конкурентная структура рынка как фактор ценообразования
10. нравственного воспитания направленного на нравственное совершенствование личности школьника приобретает
11. Золотые правила иудейских мудрецов
12. Гражданско-правовое положение некоммерческих организаций
13. і. Но~ай Ордасы Алтын Ордадан XIII ~асырды~ екінші жартысында б~лектене бастады
14. нападение мотивированное деструктивное поведение противоречащее нормам сосуществования людей наносящ
15. тема освещения дает возможность готовить пищу стирать шить читать и выполнять другие повседневные домашни
16. Курсовая работа- Анализ себестоимости продукции
17. Доклад- Постструктурализм
18. Обломов Сообщение 515б Обломов ~ главный герой романа
19. ПСИХ ЗАБОЛЕВАНИЯ В экономически развитых государствах большее значение приобретают нервнопсихические з
20. м ребенком В детстве росла и развивалась нормально от сверстников не отставала