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

Формула изобретения

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

Описание изобретения к патенту

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

В совокупности заявленных признаков изобретения используются следующие термины:

- криптографическое преобразование (шифр) - совокупность шагов преобразования цифровых данных с использованием секретного ключа, обеспечивающих невозможность корректного выполнения криптографического преобразования без знания секретного ключа;

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

- специальные свойства криптографического преобразования - способность противостоять утечкам опасной информации по возможным побочным каналам при реализации криптографического преобразования в устройстве шифрования;

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

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

В процессе выполнения известных криптографических преобразований [1] обрабатываемые данные подвергаются преобразованиям с использованием секретного криптографического ключа (далее ключа). В различных шифрах секретный ключ используют по разному. Например, в алгоритме криптографического преобразования ГОСТ 28147-89 [2] на каждом раунде криптографического преобразования осуществляют сложение по модулю 2³² преобразовываемого 32-битового подблока данных и используемого 32-битового раундового подключа. При этом в процессе шифрования одного 64-битового блока данных каждый подключ используют 4 раза, что существенно снижает специальные свойства устройства шифрования, так как приводит к возможности многократного наблюдения криптографического ключа. Для устранения указанного недостатка в реальных устройствах используют частую смену криптографического ключа или выработку сеансовых криптографических ключей, что приводит к известным ограничениям [1].

Для устранения указанного недостатка в устройствах шифрования используют различные меры противодействия многократному наблюдению секретного ключа при его использовании в процессе шифрования [3]. Например, маскирование ключа путем побитного сложения по модулю 2 со случайным значением - маской. При этом, периодически осуществляют смену использованного случайного значения (маски) на новое.

В этом случае при реализации криптографического преобразования на вычислительном процессоре используют следующий порядок сложения 32-битового раундового подключа с преобразовываемым 32-битовым подблоком данных по модулю 2³²:

1. Маскированный раундовый подключ и использованную маску хранят в памяти раздельно.

2. При выполнения сложения в регистр аккумулятор помещают маскированный раундовый подключ.

3. Осуществляют сложение по модулю 2 использованной маски с содержимым регистра аккумулятора с сохранением результата в регистре аккумуляторе.

4. Осуществляют сложение по модулю 2³² преобразовываемого подблока данных с содержимым регистра аккумулятора с сохранением результата в регистре аккумуляторе.

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

Приведенный способ имеет недостаток, состоящий в появлении в "чистом" виде используемого раундового подключа в регистре аккумуляторе. Для устранения указанного недостатка необходимо реализовать специализированный сумматор (с использованием заказных микросхем) или с использованием программируемых логических схем [4].

Известен двоичный сумматор, называемый полным сумматором, который складывает три 1-разрядных операнда, образуя 2-разрядную сумму [4]. Сумма может принимать значения от 0 до 3, для ее представления используют два двоичных выходных бита. Работа полного сумматора описывается следующими уравнениями:

=k·х+k· _-1+х· _-1.

где 5 - младший разряд результата суммирования;

k - первый операнд;

x - второй операнд;

_-1 - третий операнд (перенос из предыдущего разряда);

- старший разряд результата суммирования (перенос в следующий раз-ряд);

- суммирование по модулю 2;

· - операция конъюнкции;

+ - операция дизъюнкции;

^- - операция отрицания.

Наиболее близким к заявленному способу является двоичный n-разрядный сумматор со сквозным переносом (см. рис.5.87 на стр.502, Дж. Ф. Уэй-керли, Проектирование цифровых устройств, том 1. Москва: Постмаркет, 2002. - 544 с.), состоящий из n последовательно включенных полных сумматоров, каждый из которых оперирует одним битом. Работа двоичного n-разрядного сумматора со сквозным переносом описывается следующими уравнениями:

_i=k_i·x_i+k_i · _i-1+x_i· _-1.

При этом i [0,n-1], _-1=0.

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

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

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

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

Изобретение иллюстрируется следующими рисунками:

Фиг.1 - 4-х разрядный сумматор со сквозным переносом и скрытым снятием маски в процессе суммирования.

Фиг.2 - полный сумматор со скрытым снятием маски в процессе суммирования.

Заявленный способ основан на следующих свойствах сложения n-разрядных чисел, представленных в позиционной системе счисления, с произвольным основанием q.

Пусть имеются n-разрядные целые числа K, X, и Г, такие, что 0 K<qⁿ, 0 Х<qⁿ и 0 Г<qⁿ. И пусть , где - операция поразрядного сложения по модулю q, т.е:

где k_i и x_i - i-ые разряды операндов;

s_i - i-ый разряд результата сложения;

_r - перенос из г-го разряда;

- наибольшее целое число, не превосходящее аргумент.

Известно, что , рассмотрим число S' формируемое следующим способом:

где - r-ый разряд первого, маскированного операнда;

x_r - r-ый разряд второго, немаскированного операнда;

s'_r - r-ый разряд числа S';

_r - перенос из i-го разряда, формируемый приведенным способом.

В этом случае _r фактически является переносом при сложении не маскированных операндов. В соответсвии с заявленым способом q-значную функцию _r формируют как функцию четырех независимых переменных k_r, _r, x_r и _r-1.

Рассмотрим значение

Если при сложении двух операндов и X, один из которых является маскированным путем поразрядного сложения по модулю основания q с маской Г перенос в старшие разряды формировать по правилу:

то при поразрядном вычитании по модулю основания q из результата S' использованной ранее маски Г получившееся значение будет равно результату S сложения по модулю qⁿ двух не маскированных операндов K и X:

Для двоичной системы счисления операции поразрядного сложения и вычитания по модулю основания совпадают и являются операцией поразрядного сложения по модулю 2. Для двоичной системы счисления уравнения принимают следующий вид:

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

Техническая возможность реализации заявленного способа иллюстрируется устройством, реализующим заявленный способ при сложении в двоичной системе счисления по модулю 2⁴ (фиг.1), которое состоит из четырех блоков 11 полных сумматоров, со снятием маски в процессе суммирования, и четырех блоков 12 сложения по модулю два. Устройство, реализующее заявленный способ, содержит двенадцать входов и четыре выхода.

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

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

Как было показано выше, устройство, реализующее заявленный способ, содержит (фиг.1) первый блок 11, входы 1, 2 и 3 которого соединены соответственно с входами 1, 5 и 9 устройства, на вход 4 первого блока 11 подается значение логического 0, выход 1 первого блока 11 соединен со входом 4 второго блока 11, выход 2 первого блока 11 соединен с входом 1 первого блока 12, вход 2 первого блока 12 соединен с входом 5 устройства, выход 1 первого блока 12 соединен с выходом 1 устройства.

Входы 1, 2 и 3 второго блока 11 соединены соответственно с входами 2, 6 и 10 устройства, вход 4 второго блока 11 соединен с выходом 1 первого блока 11, выход 1 второго блока 11 соединен со входом 4 третьего блока 11, выход 2 второго блока 11 соединен с входом 1 второго блока 12, вход 2 второго блока 12 соединен с входом 6 устройства, выход 1 второго блока 12 соединен с выходом 2 устройства.

Входы 1, 2 и 3 третьего блока 11 соединены соответственно с входами 3, 7 и 11 устройства, вход 4 третьего блока 11 соединен с выходом 1 второго блока 11, выход 1 третьего блока 11 соединен со входом 4 четвертого блока 11, выход 2 третьего блока 11 соединен с входом 1 третьего блока 12, вход 2 третьего блока 12 соединен с входом 7 устройства, выход 1 третьего блока 12 соединен с выходом 3 устройства.

Входы 1, 2 и 3 четвертого блока 11 соединены соответственно с входами 4, 8 и 12 устройства, вход 4 четвертого блока 11 соединен с выходом 1 третьего блока 11, выход 1 четвертого блока 11 терминируется, выход 2 четвертого блока 11 соединен с входом 1 четвертого блока 12, вход 2 четвертого блока 12 соединен с входом 8 устройства, выход 1 четвертого блока 12 соединен с выходом 4 устройства.

При работе устройства, реализующего заявленный способ, на входы устройства 1, 2, 3 и 4 подают соответственно 0-ой, 1-ый, 2-ой и 3-ий разряды маскированного операнда, на входы устройства 5, 6, 7 и 8 подают соответственно 0-ой, 1-ый, 2-ой и 3-ий разряды использованной маски, на входы устройства 9, 10, 11 и 12 подают соответственно 0-ой, 1-ый, 2-ой и 3-ий разряды второго операнда.

С входов 1, 5 и 9 нулевые разряды маскированного операнда, использованной маски и второго операнда подают соответственно на входы 1, 2 и 3 первого блока 11, на вход 4 первого блока 11 подают нулевое значение. В первом блоке 11 в соответствии с заявленным способом формируют значение переноса в старший разряд и подают его на выход 1 первого блока 11; дополнительно в первом блоке 11 формируют промежуточный результат суммирования в соответствии с заявленным способом и подают его на выход 2 первого блока 11, с которого его подают на вход 1 первого блока 12, на вход 2 которого подают значение с входа 9 устройства, результат сложения по модулю два в первом блоке 12 с выхода 1 первого блока 12 подают на выход 1 устройства.

С входов 2, 6 и 10 первые разряды маскированного операнда, использованной маски и второго операнда подают соответственно на входы 1, 2 и 3 второго блока 11, на вход 4 второго блока 11 подают значение с выхода 1 первого блока 11. Во втором блоке 11 в соответствии с заявленным способом формируют значение переноса в старший разряд и подают его на выход 1 второго блока 11, дополнительно во втором блоке 11 формируют промежуточный результат суммирования в соответствии с заявленным способом и подают его на выход 2 второго блока 11, с которого его подают на вход 1 второго блока 12, на вход 2 которого подают значение с входа 10 устройства, результат сложения по модулю два во втором блоке 12 с выхода 1 второго блока 12 подают на выход 2 устройства.

С входов 3, 7 и 11 вторые разряды маскированного операнда, использованной маски и второго операнда подают соответственно на входы 1, 2 и 3 третьего блока 11, на вход 4 третьего блока 11 подают значение с выхода 1 второго блока 11. В третьем блоке 11 в соответствии с заявленным способом формируют значение переноса в старший разряд и подают его на выход 1 третьего блока 11, дополнительно в третьем блоке 11 формируют промежуточный результат суммирования в соответствии с заявленным способом и подают его на выход 2 третьего блока 11, с которого его подают на вход 1 третьего блока 12, на вход 2 которого подают значение с входа 11 устройства, результат сложения по модулю два в третьем блоке 12 с выхода 1 третьего блока 12 подают на выход 3 устройства.

С входов 4, 8 и 12 третьи разряды маскированного операнда, использованной маски и второго операнда подают соответственно на входы 1, 2 и 3 четвертого блока 11, на вход 4 четвертого блока 11 подают значение с выхода 1 третьего блока 11. В четвертом блоке 11 в соответствии с заявленным способом формируют значение переноса в старший разряд и подают его на выход 1 четвертого блока 11 и терминируют, дополнительно в четвертом блоке 11 формируют промежуточный результат суммирования в соответствии с заявленным способом и подают его на выход 2 четвертого блока 11, с которого его подают на вход 1 четвертого блока 12, на вход 2 которого подают значение с входа 12 устройства, результат сложения по модулю два в четвертом блоке 12 с выхода 1 четвертого блока 12 подают на выход 4 устройства.

Входящий в состав устройства блок 11 полного сумматора, со снятием маски в процессе суммирования, работает следующим образом (фиг.2).

Блок 11 содержит блок 1 формирования переноса, блоки 2 и 3 сложения по модулю два, четыре входа и два выхода. Блок 1 реализует комбинационную функцию переноса в соответствии с заявленным способом и может быть реализован, например, на элементах памяти [5]. При этом блок 1 содержит входы 1, 2, 3 и 4, которые соединены соответственно с входами 1, 2, 3 и 4 блока 11, и выход 1, который соединен с выходом 1 блока 11. Блок 2 содержит входы 1 и 2, которые соединены соответственно с входами 4 и

3 блока 11, выход 1 блока 2 соединен со входом 2 блока 3. Блок 3 содержит входы 1 и 2, вход 1 блока 3 соединен с входом 1 блока 11, вход 2 блока 3 соединен с выходом 1 блока 2, выход 1 блока 3 соединен с выходом 2 блока 11.

При работе блока 11 на входы 1, 2, 3 и 4 блока подают соответственно разряды маскированного операнда, использованной маски, второго операнда и переноса из предыдущего разряда, значения со входов 3 и 4 подают соответственно на входы 2 и 1 блока 2, где их суммируют по модулю два, результат суммирования с выхода 1 блока 2 и значение с входа 1 блока 11 подают соответственно на входы 2 и 1 блока 3, где их суммируют по модулю два, результат суммирования с выхода 1 блока 3 подают на выход 2 блока 11, значение с выход 2 блока 11 является промежуточным результатом суммирования в соответствии с заявленным способом.

Дополнительно значения с входов 1, 2, 3 и 4 блока 11 подают соответственно на входы 1, 2, 3 и 4 блока 1, который содержит записанную таблицу истинности комбинационной схемы переноса заявленного способа (таблица 1), при этом вход 1, 2, 3 и 4 блока 1 соответствуют 1-му, 2-му, 3-му и 4-му столбцам таблицы 1, хранимые в блоке 1 значения соответствуют 5-му столбцу таблицы. Значение, выбранное в соответствии с поданными на входы блока 1 значениями, подается на выход блока 1 и с выхода блока 1 на выход 1 блока 11. Значение с выхода 1 блока 11 является переносом в старший разряд в соответствии с заявленным способом.

Таблица 1
Таблица истинности переноса в старший разряд
№	kr	r	xr	r-1	r
0	1	2	3	4	5
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	0
15	1	1	1	1	1

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

Литература

1. Б. Шнайер, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. - М.: Издательство ТРИУМФ, 2002 - 816 с.: ил.

2. ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

3. Домашев А.В. и др. Программирование алгоритмов защиты информации. Учебное пособие. Издание второе, исправленное и дополненное. - М.: Издатель Молгачева С.В., Издательство "Нолидж. 2002. - 552 с.

4. Дж. Ф. Уэйкерли, Проектирование цифровых устройств, том 1. М.: Постмаркет, 2002. - 544 с.).

5. Дж. Ф. Уэйкерли, Проектирование цифровых устройств, том 2. М.: Постмаркет, 2002. - 528 с.).