СПОСОБ СУММИРОВАНИЯ МАСКИРОВАННОГО ЧИСЛА СО СКРЫТЫМ СНЯТИЕМ МАСКИ В ПРОЦЕССЕ СУММИРОВАНИЯ
SUMMATION METHOD OF MASKED NUMBER WITH CONCEALED UNMASKING DURING SUMMATION

Изобретение относится к области вычислительной техники и технике защиты информации. Изобретение, в частности, может использоваться в средствах криптографической защиты информации.
В совокупности заявленных признаков изобретения используются следующие термины:
- криптографическое преобразование (шифр) - совокупность шагов преобразования цифровых данных с использованием секретного ключа, обеспечивающих невозможность корректного выполнения криптографического преобразования без знания секретного ключа;
- устройство шифрования - устройство, реализующее преобразование цифровых данных в соответствии с заданным криптографическим преобразованием;
- специальные свойства криптографического преобразования - способность противостоять утечкам опасной информации по возможным побочным каналам при реализации криптографического преобразования в устройстве шифрования;
- побочные каналы - каналы передачи информации, непредусмотренные как штатные для передачи информации в конкретном устройстве шифрования (например, утечка обрабатываемых в устройстве шифрования конфиденциальных данных через электромагнитные колебания, возникающие в результате работы вычислительной техники).
- маска - случайное число, поразрядно слагаемое по модулю основания с защищаемым числом и обеспечивающее его конфиденциальность при передаче и хранении в вычислительном средстве.
32
В процессе выполнения известных криптографических преобразований [1] обрабатываемые данные подвергаются преобразованиям с использованием секретного криптографического ключа (далее ключа). В различных шифрах секретный ключ используют по разному. Например, в алгоритме криптографического преобразования ГОСТ 28147-89 [2] на каждом раунде криптографического преобразования осуществляют сложение по модулю 2 преобразовываемого 32-битового подблока данных и используемого 32-битового раундового подключа. При этом в процессе шифрования одного 64-битового блока данных каждый подключ используют 4 раза, что существенно снижает специальные свойства устройства шифрования, так как приводит к возможности многократного наблюдения криптографического ключа. Для устранения указанного недостатка в реальных устройствах используют частую смену криптографического ключа или выработку сеансовых криптографических ключей, что приводит к известным ограничениям [1].
Для устранения указанного недостатка в устройствах шифрования используют различные меры противодействия многократному наблюдению секретного ключа при его использовании в процессе шифрования [3]. Например, маскирование ключа путем побитного сложения по модулю 2 со случайным значением - маской. При этом, периодически осуществляют смену использованного случайного значения (маски) на новое.
32
В этом случае при реализации криптографического преобразования на вычислительном процессоре используют следующий порядок сложения 32-битового раундового подключа с преобразовываемым 32-битовым подблоком данных по модулю 2:
1. Маскированный раундовый подключ и использованную маску хранят в памяти раздельно.
2. При выполнения сложения в регистр аккумулятор помещают маскированный раундовый подключ.
3. Осуществляют сложение по модулю 2 использованной маски с содержимым регистра аккумулятора с сохранением результата в регистре аккумуляторе.
32
4. Осуществляют сложение по модулю 2 преобразовываемого подблока данных с содержимым регистра аккумулятора с сохранением результата в регистре аккумуляторе.
В этом случае после шага 4 в регистре аккумуляторе находится результат сложения преобразовываемого подблока данных с раундовым подключем, при этом, использованный раундовый подключ передавался по шинам вычислительного средства в маскированном виде.
Приведенный способ имеет недостаток, состоящий в появлении в "чистом" виде используемого раундового подключа в регистре аккумуляторе. Для устранения указанного недостатка необходимо реализовать специализированный сумматор (с использованием заказных микросхем) или с использованием программируемых логических схем [4].
Известен двоичный сумматор, называемый полным сумматором, который складывает три 1-разрядных операнда, образуя 2-разрядную сумму [4]. Сумма может принимать значения от 0 до 3, для ее представления используют два двоичных выходных бита. Работа полного сумматора описывается следующими уравнениями:
-1
-1
η=k·х+k·η+х·η.
где 5 - младший разряд результата суммирования;
k - первый операнд;
x - второй операнд;
-1
η - третий операнд (перенос из предыдущего разряда);
η - старший разряд результата суммирования (перенос в следующий раз-ряд);
⊕ - суммирование по модулю 2;
· - операция конъюнкции;
+ - операция дизъюнкции;
-
- операция отрицания.
Наиболее близким к заявленному способу является двоичный n-разрядный сумматор со сквозным переносом (см. рис.5.87 на стр.502, Дж. Ф. Уэй-керли, Проектирование цифровых устройств, том 1. Москва: Постмаркет, 2002. - 544 с.), состоящий из n последовательно включенных полных сумматоров, каждый из которых оперирует одним битом. Работа двоичного n-разрядного сумматора со сквозным переносом описывается следующими уравнениями:
i
i
i
i
i-1
i
-1
η=k·x+k·η+x·η.
-1
При этом i∈[0,n-1], η=0.
Недостатком способа-прототипа является необходимость использования обоих операндов в "чистом" виде, без наложенных по модулю 2 масок. В криптографической технике использование способа-прототипа для построения сумматора существенно снижает специальные свойства устройства шифрования, что обусловлено необходимостью представлять ключи в "чистом" виде, немаскированными маской. В этом случае при многократном обращении к ключам в устройстве шифрования нарушителю предоставляется возможность накопления статистики по побочным каналам и дальнейшем восстановлении ключей.
Решение задачи суммирования двух чисел, одно из которых маскировано путем поразрядного сложения по модулю основания системы счисления с маской, со скрытым снятием маски в процессе суммирования без получения разрядов маскированного операнда в "чистом" виде позволит существенно повысить специальные свойства устройств шифрования.
Целью настоящего изобретения является разработка способа суммирования двух чисел, одно из которых маскировано путем поразрядного сложения с маской по модулю основания системы счисления, со скрытым снятием маски в процессе суммирования без получения значений разрядов маскированного операнда в "чистом" виде.
Техническим результатом заявленного способа является разработка способа суммирования двух чисел, одно из которых маскировано путем поразрядного сложения с маской по модулю основания системы счисления, со скрытым снятием маски в процессе суммирования без получения разрядов маскированного операнда в "чистом" виде, что позволит обеспечить высокие специальные свойства устройств шифрования при использовании заявленного способа.
Изобретение иллюстрируется следующими рисунками:
Фиг.1 - 4-х разрядный сумматор со сквозным переносом и скрытым снятием маски в процессе суммирования.
Фиг.2 - полный сумматор со скрытым снятием маски в процессе суммирования.
Заявленный способ основан на следующих свойствах сложения n-разрядных чисел, представленных в позиционной системе счисления, с произвольным основанием q.
n
n
n
Пусть имеются n-разрядные целые числа K, X, и Г, такие, что 0≤K<q, 0≤Х<q и 0≤Г<q. И пусть , где ⊕ - операция поразрядного сложения по модулю q, т.е:
i
i
где k и x - i-ые разряды операндов;
i
s - i-ый разряд результата сложения;
r
η - перенос из г-го разряда;
- наибольшее целое число, не превосходящее аргумент.
Известно, что , рассмотрим число S' формируемое следующим способом:
где  - r-ый разряд первого, маскированного операнда;
r
x - r-ый разряд второго, немаскированного операнда;
r
s' - r-ый разряд числа S';
r
η - перенос из i-го разряда, формируемый приведенным способом.
r
r
r
r
r
r-1
В этом случае η фактически является переносом при сложении не маскированных операндов. В соответсвии с заявленым способом q-значную функцию η формируют как функцию четырех независимых переменных k, γ, x и η.
Рассмотрим значение
Если при сложении двух операндов  и X, один из которых  является маскированным путем поразрядного сложения по модулю основания q с маской Г перенос в старшие разряды формировать по правилу:
n
то при поразрядном вычитании по модулю основания q из результата S' использованной ранее маски Г получившееся значение будет равно результату S сложения по модулю q двух не маскированных операндов K и X:
Для двоичной системы счисления операции поразрядного сложения и вычитания по модулю основания совпадают и являются операцией поразрядного сложения по модулю 2. Для двоичной системы счисления уравнения принимают следующий вид:
Технический результат изобретения достигатеся тем, что в способе суммирования маскированного числа со скрытым снятием маски в процессе суммирования осуществляют поразрядное сложение двух операндов, при сложении каждого разряда осуществляют сложение значений разрядов операндов и переноса из предыдущего разряда, формируют разряд выходного результата и значение переноса в следующий разряд, при этом для младшего разряда в качестве значения переноса из предыдущего разряда используют нулевое значение, значение переноса с выхода переноса старшего разряда является выходным значеним переноса сумматора. Дополнительно при поразрядном сложении используют один из операндов, поразрядно сложенный по модулю основания системы счисления с маской, из результата поразрядного сложения поразрядно вычитают маску по модулю основания системы счисления, результат поразрядного вычитания является выходным результатом. Значение переноса в следующий разряд в каждом разряде формируют из входного значения данного разряда операнда, сложенного по модулю основания системы счисления с маской, второго операнда, маски и переноса из предыдущего разрядам. Значение переноса в следующий разряд формируют логической функцией переноса, не используя в процессе формирования переноса поразрядное вычитание по модулю основания системы счисления маски из первого операнда.
4
Техническая возможность реализации заявленного способа иллюстрируется устройством, реализующим заявленный способ при сложении в двоичной системе счисления по модулю 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
Таблица истинности переноса в старший разряд
№
k<sub>r</sub>
γ<sub>r</sub>
x<sub>r</sub>
η<sub>r-1</sub>
η<sub>r</sub>
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 с.).