Устройство поддержки защищенных логических вычислений Российский патент 2017 года по МПК G09C1/04 

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство поддержки защищенных логических вычислений, включающее физический генератор случайных чисел, регистры памяти, устройства вычисления остатка по модулю, многоразрядные сумматоры, многоразрядный умножители, введены блок генерации случайных чисел, входы которого подключены к 5-ти канальной шине передачи значений модулей-ограничителей, являющейся входом устройства, первая группа выходов которого подключена к k канальной шине передачи значений первой системы k модулей, вторая группа выходов которого подключена к q канальной шине передачи значений второй системы q модулей, третья группа выходов которого подключена к 3-х канальной шине передачи значений случайных чисел; блок зашифрования исходных логических данных, включающий блок зашифрования коэффициентов полинома, первая группа входов которого подключена к 2ⁿ канальной шине передачи значений коэффициентов, являющейся входом устройства, вторая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, третья группа входов которого подключена к q канальной шине передачи значений второй системы q модулей и четвертая группа входов которого подключена к 3-х канальной шине передачи случайных чисел, а выходы подключены к 2ⁿ kq канальной шине передачи значений зашифрованных коэффициентов, являющейся выходом устройства, и блок зашифрования логических переменных, первая группа входов которого подключена к n канальной шине передачи значений логических переменных, являющейся входом устройства, вторая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, третья группа входов которого подключена к q канальной шине передачи значений второй системы q модулей и четвертая группа входов которого подключена к 3-х канальной шине передачи случайных чисел, а выходы подключены к knq канальной шине передачи значений зашифрованных логических переменных, являющейся выходом устройства; блок расшифрования результата логических вычислений, первая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, вторая группа входов которого подключена к q канальной шине передачи значений второй системы q модулей, третья группа входов которого подключена к 3-х канальной шине передачи случайных чисел и четвертая группа входов которого подключена к kq канальной шине передачи значений вычисления полиномов, являющейся входом устройства, а выходы подключены к s канальной шине передачи значений вычисления булевых функций, являющейся выходом устройства; при этом, блок генерации случайных чисел состоит из 5-ти устройств вычисления остатка по модулю, где второй вход i-го устройства вычисления остатка по модулю подключен к i-му каналу 5-ти канальной шины передачи значений модулей-ограничителей (i=1, 2, …, 5), а первый вход i-го устройства вычисления остатка по модулю подключен к i-му выходу физического генератора случайных чисел (i=1, 2, …, 5), выходы первого и второго устройств вычисления остатка по модулю подключены соответственно к адресным входам первого и второго блоков памяти хранения систем простых модулей, где k выходов первого блока памяти хранения систем простых модулей подключены к k канальной шине передачи значений первой системы k модулей, a q выходов второго блока памяти хранения систем простых модулей подключены к q канальной шине передачи значений второй системы q модулей, выходы третьего, четвертого и пятого устройств вычисления остатка по модулю подключены к 3-х канальной шине передачи случайных чисел; при этом блок зашифрования коэффициентов состоит из регистра памяти, входы которого подключены к 2ⁿ канальной шине передачи значений коэффициентов, а выходы с первого по 2ⁿ-ый соответственно подключены ко вторым входам 2ⁿ многоразрядных умножителей, первые входы которых подключены к первому каналу 3-х канальной шины передачи случайных чисел, а выходы многоразрядных умножителей подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с первого по k-ый, и так далее, и выход 2ⁿ-го многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с (k(2ⁿ-1)+1)-го по 2ⁿk-ый, а первые входы устройств вычисления остатка по модулю с первого по k-ый подключены соответственно к каналам с первого по k-ый k канальной шины передачи значений первой системы k модулей, и так далее, и первые входы устройств вычисления остатка по модулю с (k(2ⁿ-1)+1)-го по 2ⁿ k-ый подключены соответственно к каналам с первого по k-ый k канальной шины передачи значений первой системы k модулей, выходы устройств вычисления остатка по модулю подключены ко вторым входам многоразрядных умножителей, где выход i-го устройства вычисления остатка по модулю подключен ко второму входу i-го многоразрядного умножителя (i=1, 2, …, 2ⁿk), первый вход каждого многоразрядного умножителя подключен ко 2-му каналу 3-х канальной шины передачи случайных чисел, а выходы многоразрядных умножителей подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с первого по q-ый, и так далее, и выход 2ⁿk-го многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с ((2ⁿk-1)q+1)-го по 2ⁿkq-ый, а первые входы устройств вычисления остатка по модулю подключены к q канальной шине передачи значений второй системы q модулей, где первый вход первого устройства вычисления остатка по модулю подключен к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход q-го устройства вычисления остатка по модулю подключен к q-му каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход ((2ⁿk-1)q+1)-го устройства вычисления остатка по модулю подключен к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход 2ⁿkq-го устройства вычисления остатка по модулю подключен к q-му каналу q канальной шины передачи значений второй системы q модулей, а выходы устройств вычисления остатка по модулю подключены ко входам регистра памяти хранения зашифрованных коэффициентов, где выход i-ого устройства вычисления остатка по модулю подключен к i-му входу регистра памяти хранения зашифрованных коэффициентов (i=1, 2, …, 2ⁿkq), выходы которого с первого по 2ⁿkq-ый подключены к 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов; при этом, блок зашифрования переменных состоит из регистра памяти хранения значений переменных, входы которого подключены к n канальной шине передачи значений логических переменных, k многоразрядных умножителей, вторые входы каждого из которых подключены к третьему каналу 3-х канальной шины передачи случайных чисел, а первые входы подключены к k канальной шине передачи значений первой системы k модулей, где первый вход i-го многоразрядного умножителя подключен к i-му каналу k канальной шины передачи значений первой системы k модулей (i=1, 2, …, k), kn многоразрядных сумматоров, первые входы которых подключены к выходам многоразрядных умножителей, где первый вход первого, (k+1)-го, и так далее, и ((k-1)n+1)-го многоразрядного сумматора подключен к выходу первого многоразрядного умножителя, и так далее, и первый вход k-го, 2k-го, и так далее, и kn-го многоразрядного сумматора подключен к выходу k-го многоразрядного умножителя, а вторые входы многоразрядных сумматоров подключены к выходам регистра памяти хранения значений переменных, где вторые входы многоразрядных сумматоров с первого по k-ый подключены к первому выходу регистра памяти хранения значений переменных, и так далее, и вторые входы многоразрядных сумматоров с ((k-1)n+1)-го по kn-ый подключены к n-му выходу регистра памяти хранения значений переменных, выходы многоразрядных сумматоров подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного сумматора подключен ко вторым входам устройств вычисления остатка по модулю с первого по q-ый, и так далее, и выход kn-го многоразрядного сумматора подключен ко вторым входам устройств вычисления остатка по модулю с ((kn-1)q+1)-го по knq-ый, первые входы устройств вычисления остатка по модулю подключены к q канальной шине передачи значений второй системы q модулей, где первые входы первого, (q+1)-го и так далее, и ((kn-1)q+1)-го устройства вычисления остатка по модулю подключены к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первые входы q-го, 2q-го, и так далее, и knq-го устройства вычисления остатка по модулю подключены к q-му каналу q канальной шины передачи значений второй системы q модулей, выходы устройств вычисления остатка по модулю подключены ко входам регистра памяти хранения значений зашифрованных переменных, где выход i-го устройства вычисления остатка по модулю подключен к i-му входу регистра памяти хранения значений зашифрованных переменных (i=1, 2, ……, knq), выходы которого подключены к knq канальной шине передачи значений зашифрованных логических переменных; при этом, блок расшифрования результата логических вычислений состоит из регистра памяти, хранения значений вычисления полиномов, входы которого подключены к kq канальной шине передачи значений вычисления полиномов, k устройств восстановления по КТО, первые группы входов которых подключены к выходам регистра памяти хранения значений вычисления полиномов, где первая группа входов первого устройства восстановления по КТО подключена к первым q выходам регистра памяти, хранения значений вычисления полиномов и так далее, и первая группа входов k-го устройства восстановления по КТО подключена к k-ым q выходам регистра памяти, хранения значений вычисления полиномов, вторая группа q входов каждого устройства восстановления по КТО подключена к q канальной шине передачи значений второй системы q модулей, а выходы подключены к первым входам устройств целочисленного деления, где выход i-го устройства восстановления, по КТО подключен к первому входу i-го устройства целочисленного деления (i=1, …, k), вторые входы каждого из устройств целочисленного деления подключены ко второму каналу 3-х канальной шина передачи случайных чисел, а выходы подключены к первой группе входов устройства восстановления по КТО, вторая группа k входов которого подключена к k канальной шине передачи значений первой системы k модулей, а выход подключен к первому входу устройства целочисленного деления, второй вход которого подключен к первому каналу 3-х канальной шины передачи случайных чисел, а выход подключен ко входу регистра памяти хранения значений вычисления булевых функций, двоичные выходы которого подключены к s канальной шине передачи значений вычисления булевых функций.

Сущность изобретения поясняется чертежами, где на Фиг. 1 представлена схема организации защищенных вычислений с использованием математических преобразований китайской теоремы об остатках, на Фиг 2 представлена блок-схема алгоритма реализации защищенных логических вычислений, на Фиг. 3 представлена структурная схема устройства поддержки защищенных логических вычислений, на Фиг. 4 представлена структурная схема блока зашифрования исходных логических данных, на Фиг. 5 представлена структурная схема блока генерации случайных чисел, на Фиг. 6 представлена структурная схема блока зашифрования коэффициентов полинома, на Фиг. 7 представлена структурная схема блока зашифрования логических переменных и на Фиг. 8 представлена структурная схема блока расшифрования результата логических вычислений.

Структурная схема предлагаемого устройства и его узлов представлена на фиг. 3-8, общая структура устройства представлена на фиг. 3 и включает: блок генерации случайных чисел 1, блок зашифрования исходных логических данных 2, блок расшифрования результата логических вычислений 3, 2ⁿ канальную шину передачи значений коэффициентов 4, n канальную шину передачи значений логических переменных 5, 5-ти канальную шину передачи значений модулей-ограничителей 6, k канальную шину передачи значений первой системы k модулей 7, q канальную шину передачи значений второй системы q модулей 8, 3-х канальную шину передачи случайных чисел 9, 2ⁿkq канальную шину передачи значений зашифрованных коэффициентов 10, knq канальную шину передачи значений зашифрованных логических переменных 11, kq канальную шину передачи значений вычисления полиномов 12, s канальную шину передачи значений вычисления булевых функций 13. Структурная схема блока генерации случайных чисел 1 представлена на Фиг. 5 и включает физический генератор случайных чисел 14, устройства вычисления остатка по модулю 15.1-15.5, блоки памяти хранения систем простых модулей 16.1, 16.2. Блок зашифрования исходных логических данных 2 (фиг. 4) состоит из двух блоков: блока зашифрования коэффициентов полинома 2.1 и блока зашифрования логических переменных 2.2. Структурная схема блока зашифрования коэффициентов полинома 2.1 представлена на Фиг. 6 и включает регистр памяти хранения значений коэффициентов 17, многоразрядные умножители 18.1-18.2ⁿ, устройства вычисления остатка по модулю 19.1-19.2ⁿk, многоразрядные умножители 20.1-20.2ⁿk, устройства вычисления остатка по модулю 21.1-21.2ⁿkq, регистр памяти хранения зашифрованных коэффициентов 22. Структурная схема блока зашифрования логических переменных 2.2 представлена на Фиг. 7 и включает регистр памяти хранения значений переменных 23, многоразрядные умножители 24.1-24.k, многоразрядные сумматоры 25.1-25.kn, устройства вычисления остатка по модулю 26.1-26.knq, регистр памяти хранения значений зашифрованных переменных 27. Структурная схема блока расшифрования результата логических вычислений 3 представлена на Фиг. 8 и включает регистр памяти хранения значений вычисления полиномов 28, устройства восстановления по КТО 29.1-29.k, устройство целочисленного деления 30.1-30.k, устройство восстановления по КТО 31, устройство целочисленного деления 32, регистр памяти хранения значений вычисления булевых функций 33.

В статическом виде элементы предлагаемого устройства взаимосвязаны следующим образом (фиг. 3): 5-ти канальная шина передачи значений модулей-ограничителей 6, являющаяся входом устройства, подключена к группе входов блока генерации случайных чисел 1, первая группа выходов которого подключена к третьей группе входов блока зашифрования исходных логических данных 2 и первой группе входов блока расшифрования результата логических вычислений 3 посредством k канальной шины передачи значений первой системы k модулей 7, вторая группа выходов которого подключена к четвертой группе входов блока зашифрования исходных логических данных 2 и второй группе входов блока расшифрования результата логических вычислений 3 посредством q канальной шины передачи значений второй системы q модулей 8, третья группа выходов которого подключена к пятой группе входов блока зашифрования исходных логических данных 2 и третьей группе входов блока расшифрования результата логических вычислений 3 посредством 3-х канальной шины передачи случайных чисел 9; n канальная шина передачи значений логических переменных 5, являющаяся входом устройства, подключена к первой группе входов блока зашифрования исходных логических данных 2; 2ⁿ канальная шина передачи значений коэффициентов 4, являющаяся входом устройства, подключена ко второй группе входов блока зашифрования исходных логических данных 2, первая группа выходов блока зашифрования исходных логических данных 2 подключена к 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов 10, являющейся выходом устройства, а вторая группа выходов подключена к knq канальной шине передачи значений зашифрованных логических переменных 11, являющейся выходом устройства, четвертая группа входов блока расшифрования результата логических вычислений 3 подключена к kq канальной шине передачи значений вычисления полиномов 12, являющейся входом устройства, а группа выходов блока расшифрования результата логических вычислений 3 подключена к s канальной шине передачи значений вычисления булевых функций 13, являющейся выходом устройства; при этом, элементы блока генерации случайных чисел 1 (Фиг. 5) взаимосвязаны следующим образом: i-ый выход физического генератора случайных чисел 14 подключен к первому входу i-го устройства вычисления остатка по модулю 15.1-15.5 (i=1, 2, …, 5), второй вход i-го устройства вычисления остатка по модулю 15.1-15.5 подключен к i-му каналу 5-ти канальной шины передачи значений модулей ограничителей 6 (i=1, 2, …, 5), выходы первого и второго устройств вычисления остатка по модулю 15.1, 15.2 соответственно подключены ко входам первого и второго блоков памяти хранения систем простых модулей 16.1, 16.2, выходы первого блока памяти хранения систем простых модулей 16.1 подключены к k канальной шине передачи значений первой системы k модулей 7, выходы второго блока памяти хранения систем простых модулей 16.2 подключены к q канальной шине передачи значений второй системы q модулей 8, выходы третьего, четвертого и пятого устройств вычисления остатка по модулю 15.3-15.5 подключены соответственно к 3-х канальной шине передачи случайных чисел 9; при этом, элементы блока зашифрования коэффициентов полинома 2.1 (Фиг. 6) взаимосвязаны следующим образом: 2ⁿ канальная шина передачи значений коэффициентов 4 подключена к группе входов регистра памяти хранения значений коэффициентов 17, i-ый выход которого подключен ко второму входу i-го многоразрядного умножителя 18.1-18.2ⁿ (i=1, 2, …, 2ⁿ), первый вход каждого многоразрядного умножителя 18.1-18.2ⁿ подключен к первому каналу 3-х канальной шины передачи случайных чисел 9.1, выход первого многоразрядного умножителя 18.1 подключен ко вторым входам каждого устройства вычисления остатка по модулю с 19.1 по 19.k, и так далее, и выход 2ⁿ-го многоразрядного умножителя 18.2ⁿ подключен ко вторым входам каждого устройства вычисления остатка по модулю с 19.k(2ⁿ-1)+1 по 19.2ⁿk, первые входы устройств вычисления остатка по модулю 19.1, 19.k+1, …, 19.k(2ⁿ-1)+1 подключены к первому каналу k канальной шины передачи значений первой системы k модулей 7, и так далее, и первые входы устройств вычисления остатка по модулю 19.k, 19.2k, …, 19.2ⁿk подключены к k-му каналу k канальной шины передачи значений первой системы k модулей 7, а выход i-го устройства вычисления остатка по модулю 19.1 -19.2ⁿk подключен ко второму входу i-го многоразрядного умножителя 20.1-20.2ⁿk, первый вход каждого из которых подключен ко второму каналу 3-х канальной шины передачи случайных чисел 9.2, выход многоразрядного умножителя 20.1 подключен ко второму входу каждого устройства вычисления остатка по модулю с 21.1 по 21.q, и так далее, и выход многоразрядного умножителя 20.2ⁿk подключен ко второму входу каждого устройства вычисления остатка по модулю с 21.(2ⁿk-1)q+1 по 21.2ⁿkq, первые входы устройств вычисления остатка по модулю 21.1, 21.q+1, …, 21.(2ⁿk-1)q+1 подключены к первому каналу q канальной шины передачи значений второй системы q модулей 8, и так далее, и первые входы устройств вычисления остатка по модулю 21.q, 21.2q, …, 21.2ⁿkq подключены к q-му каналу q канальной шины передачи значений второй системы q модулей 8, а выходы устройств вычисления остатка по модулю 21.1-21.2ⁿkq подключены соответственно ко входам регистра памяти хранения зашифрованных коэффициентов 22, выходы которого подключены к 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов 22; при этом, элементы блока зашифрования логических переменных 2.1 (Фиг. 7) взаимосвязаны следующим образом: n канальная шина передачи значений логических переменных 5 подключена к группе входов регистра памяти хранения значений переменных 23, первый выход которого подключен ко вторым входам многоразрядных сумматоров с 25.1 по 25.k, и так далее, и n-ый выход подключен ко вторым входам многоразрядных умножителей с 25.(k-1)n+1 по 25.kn, первый вход i-го многоразрядного умножителя 24.1-24.k подключен к i-му каналу k канальной шины передачи значений первой системы k модулей 7 (i=1, 2, …, k), второй вход каждого многоразрядного умножителя 24.1-24.k подключен к третьему каналу 3-х канальной шины передачи случайных чисел 9, выход первого многоразрядного умножителя 24.1 подключен к первому входу многоразрядных сумматоров 25.1, 25.k+1, …, 25.(k-1)n+1, и так далее, и выход k-го многоразрядного умножителя 24.k подключен к первому входу многоразрядных сумматоров 25.k, 25.2k, …, 25.kn, выход многоразрядного сумматора 25.1 подключен ко вторым входам устройств вычисления остатка по модулю с 26.1 по 26.q, и так далее, и выход многоразрядного сумматора 25.kn подключен ко вторым входам устройств вычисления остатка по модулю с 26.(kn-1)q+1 по 26.knq, первые входы устройств вычисления остатка по модулю 26.1, 26.q+1, …, 26.(kn-1)q+1 подключены к первому каналу q канальной шины передачи значений второй системы q модулей 8, и так далее, и первые входы устройств вычисления остатка по модулю 26.q, 26.2q, …, 26.knq подключены к q-му каналу q канальной шины передачи значений второй системы q модулей 8, выходы устройств вычисления остатка по модулю 26.1-26.kng подключены соответственно ко входам регистра памяти хранения значений зашифрованных переменных 27, выходы которого подключены к knq канальной шине передачи значений зашифрованных логических переменных 11; при этом элементы блока расшифрования результата логических вычислений 3 (Фиг. 8) взаимосвязаны следующим образом: kq канальная шина передачи значений вычисления полиномов 12 подключена ко входам регистра памяти хранения значений вычисления полиномов 28, первые q выходов которого соответственно подключены к первой группе входов устройства восстановления по КТО 29.1, и так далее, и k-ые q выходов соответственно подключены к первой группе входов устройства по КТО 29.k, вторая группа входов каждого устройства восстановления по КТО 29.1-29.k подключена к q канальной шине передачи значений второй системы q модулей 8, выход i-го устройства восстановления по КТО 29.1-29.k подключен к первому входу i-го устройства целочисленного деления 30.1-30.k (i=1, 2, …, k), второй вход каждого из которых подключен к второму каналу 3-х канальной шины передачи случайных чисел 9.2, выход каждого из устройств целочисленного деления 30.1-30.k подключен соответственно к входам первой группы входов устройства восстановления по КТО 31, вторая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей 7, а выход подключен к первому входу устройства целочисленного деления 32, второй вход которого подключен к первому каналу 3-х канальной шины передачи случайных чисел 9.1, а выход подключен ко входу регистра памяти хранения значений вычисления булевых функций 33, двоичные выходы которого подключены к s канальной шине передачи значений вычисления булевых функций 13.

Рассмотрим свойства математических преобразований КТО, обеспечивающие возможность реализации защищенных вычислений.

Формулировка КТО звучит следующим образом [3].

Пусть М=m₁⋅m₂⋅…⋅m_k, m₁, m₂, …, m_k - попарно взаимно простые числа. Поставим в соответствие произвольному целому числу а(0≤а<М) кортеж , где a_i≡a (mod m_i) (i=1, 2, …, k), то есть .

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

То есть, если , то справедливо:

1.

2.

3. .

Следствие 1.

Система сравнений 1-й степени с неизвестным x:

имеет единственное решение по модулю М.

Следствие 2.

Сравнение 1-й степени с неизвестным ω: ω≡a(mod М) эквивалентно системе (1).

Решение системы (1) представляет собой класс вычетов:

ω≡ω₀ (mod М),

где

где i=1, 2, k; ϕ(m_i) - функция Эйлера.

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

Пример. Пусть а=52, b=32, М=m₁⋅m₂⋅m₃=3⋅5⋅7=105, тогда справедливо , тогда .

Сумма: .

Разность: .

Выполним восстановление результатов вычисления суммы и разности: М=105, , , , ϕ(3)=2, ϕ(5)=4, ϕ(7)=6.

Сумма: 35⋅2⋅3+21⋅1⋅4+15⋅1⋅7 (mod 105)=84 (mod 105).

Разность: 35⋅2⋅(-1)+21⋅1⋅0+15⋅1⋅(-1)(mod 105)=20 (mod 105).

Для выполнения операции умножения кортежей остатков необходимо выполнение условия М>а⋅b, тогда добавим еще два модуля m₄=11, m₅=13, М=15015>52⋅32, но можно вместо модулей 3, 5, 7, 11, 13, выбрать другие сочетания модулей: либо 5, 11, 23, 31, либо 13, 17, 23, либо 5, 17, 23, 29 и т.д.

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

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

Возможность применения математических преобразований КТО к логическим вычислениям может быть реализована путем представления булевых функций и систем числовым полиномом [4], вида:

где х=[х₁х₂…х_n], , i_j∈{0, 1} - степень переменной, которая формируется по правилу (i₁ i₂…i_n)₂=i, то есть i=0, 1, …, 2ⁿ-1, i=0, 1, …, 2ⁿ-1, j=1, 2, …, n.

Рассмотрим алгоритм реализации защищенных логических вычислений, основанный на применении математических преобразований КТО к числовой полиномиальной форме булевых функций (3) с использованием генератора случайных чисел. Работа алгоритма представлена на Фиг. 2 и включает три этапа:

- зашифрование исходных данных в защищенной вычислительной среде (А);

- обработка зашифрованных данных в открытой распределенной вычислительной среде (В);

- расшифрование результатов вычисления в закрытой вычислительной среде (С).

Этап 1. Зашифрование исходных данных в защищенной вычислительной среде.

Входные данные. Значения коэффициентов и переменных числового полинома (3): , х₁, х₂, …, х_n.

Шаг 1.1. Генерация случайных чисел L₁, L₂, K₁, K₂, K₃.

Шаг 1.2. Умножение коэффициентов числового полинома на случайное число K₁:

Шаг 1.3. Выбор системы простых модулей m₁, m₂, …, m_k в соответствии со значением числа L₁.

Шаг 1.4. Представление значений (4) в системе остаточных классов по модулям m₁, m₂, …, m_k:

расширение диапазона значений переменных x₁, х₂, …, х_n:

где K₃ - случайное целое неотрицательное число, K₃m_j+x_i≡x_j (mod m_j), ,

Шаг 1.5. Умножение остатков (5) на случайное число K₂:

Шаг 1.6. Выбор системы простых модулей в соответствии со значением числа L₂, где .

Шаг 1.7. Представление значений (6) в системе остаточных классов по модулям :

представление значений (7) в системе остаточных классов по модулям :

Шаг 1.8. Передача значений остатков (8, 9) в канал связи для обработки в открытой распределенной вычислительной среде.

Этап 2. Обработка зашифрованных данных в открытой распределенной вычислительной среде.

Шаг 2.1. Получение вычислительными средствами открытой распределенной вычислительной среды значений остатков (8) и (9).

Шаг 2.2. Вычисление зашифрованных значений полиномов:

где (i₁i₂…i_n)₂=i.

Шаг 2.3. Передача значений вычисления зашифрованных полиномов (10) в защищенную вычислительную среду.

Этап 3. Расшифрование результатов логических вычислений в защищенной вычислительной среде.

Шаг 3.1. Получение значений вычисления зашифрованных полиномов (10).

Шаг 3.2. Вычисление остатков от полученных значений (10) по модулям :

Шаг 3.3. Первый цикл обратного восстановления результата логических преобразований по КТО:

где , - функция Эйлера.

Шаг 3.4. Деление значений (12) на значение случайного числа K₂:

Шаг 3.5. Вычисление остатков от полученных значений (13) по модулям m₁, m₂, …, m_k:

,

Шаг 3.6. Второй цикл обратного восстановления результата вычисления логических преобразований по КТО:

где .

Шаг 3.7. Деление значения (15) на значение случайного числа K₁:

Выходные данные. Значения вычисления логических функций:

Функционирование устройства осуществляется следующим образом: в момент времени соответствующий началу работы устройства, из защищенной вычислительной системы по 5-ти канальной шине передачи значений модулей-ограничителей 6 подаются значения модулей на входы устройств вычисления остатка по модулю 15.1-15.5, ограничивающие значения случайных чисел, генерируемых физическим генератором случайных чисел 14, путем вычисления остатков, при этом на выходах первого и второго устройств вычисления остатка по модулю 15.1 и 15.2 формируются значения адресов ячеек памяти хранения систем простых модулей соответственно L₁ и L₂ в блоках памяти хранения систем простых модулей 16.1 и 16.2, на выходах третьего, четвертого и пятого устройств вычисления остатка по модулю 15.3-15.5 формируются значения случайных чисел K₁, K₂, K₃, передаваемых в блоки зашифрования исходных логических данных 2 и расшифрования результата логических вычислений 3 по 3-х канальной шине передачи случайных чисел 9. Из блока памяти хранения систем простых модулей 16.1 передаются значения k модулей по k канальной шине передачи значений первой системы k модулей 7 в блоки зашифрования исходных логических данных 2 и расшифрования результата логических вычислений 3. Из блока памяти хранения систем простых модулей 16.2 передаются значения q модулей по q канальной шине передачи значений второй системы q модулей 8 в блоки зашифрования исходных логических данных 2 и расшифрования результата логических вычислений 3. Далее в блоке зашифрования коэффициентов полиномов 2.1 выполняется зашифрование коэффициентов полинома , поступающих из защищенной вычислительной среда по 2ⁿ канальной шине передачи значений коэффициентов 4, путем преобразований (4, 5, 7, 8), далее зашифрованные значения коэффициентов (8) передаются по 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов 10 в открытую распределенную вычислительную среду, параллельно с зашифрованием коэффициентов полинома, в блоке зашифрования логических переменных 2.2 выполняется зашифрование логических переменных х₁, х₂, …, х_n, поступающих из защищенной вычислительной системы по n канальной шине передачи значений логических переменных 5, путем преобразований (6, 9), далее зашифрованные значения логических переменных (9) передаются по knq канальной шине передачи значений зашифрованных переменных 11 в открытую распределенную вычислительную среду. В открытой распределенной вычислительной среде вычисляются зашифрованные значения полиномов (10), которые подаются по kq канальной шине передачи значений вычисления полиномов 12 на входы блока расшифрования результата логических вычислений 3, в котором выполняются преобразования (11-16), далее расшифрованные значения вычисления булевых функций (17) поступают по s канальной шине передачи значений вычисления булевых функций 13 в защищенную вычислительную среду.

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

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

Литература

1. US №8630422 B2, 2009 г.

2. US №8565435 B2, 2010 г.

3. Бухштаб А.А. Теория чисел - М.: Просвещение, 1966. С. 121-125.

4. Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография / Финько О.А.; под ред. В.Д. Малюгина; - М.: Ин-т проблем управления им. В.А. Трапезникова РАН; Краснодар: Краснодарский воен. ин-т, 2003. - 224 с. http://elibrary.ru/item.asp?id=23447304. С. 20.

Изобретение относится к области шифрования. Техническим результатом является повышение производительности устройства поддержки защищенных логических вычислений. Устройство содержит блок генерации случайных чисел, блок зашифрования исходных логических данных, блок расшифрования результата логических вычислений, 2ⁿ канальную шину передачи значений коэффициентов, n канальную шину передачи значений логических переменных, 5-ти канальную шину передачи значений модулей-ограничителей, k канальную шину передачи значений первой системы k модулей, q канальную шину передачи значений второй системы q модулей, 3-х канальную шину передачи случайных чисел, 2ⁿkq канальную шину передачи значений зашифрованных коэффициентов, knq канальную шину передачи значений зашифрованных логических переменных, kq канальную шину передачи значений вычисления полиномов, s канальную шину передачи значений вычисления булевых функций. 8 ил.

Устройство поддержки защищенных логических вычислений, включающее физический генератор случайных чисел, регистры памяти, устройства вычисления остатка по модулю, многоразрядные сумматоры, многоразрядный умножители, отличающееся тем, что введены блок генерации случайных чисел, входы которого подключены к 5-ти канальной шине передачи значений модулей-ограничителей, ограничивающих значения случайных чисел, генерируемых физическим генератором случайных чисел, путем вычисления остатков, и являющейся входом устройства, первая группа выходов которого подключена к k канальной шине передачи значений первой системы k модулей, вторая группа выходов которого подключена к q канальной шине передачи значений второй системы q модулей, третья группа выходов которого подключена к 3-х канальной шине передачи значений случайных чисел; блок зашифрования исходных логических данных, включающий блок зашифрования коэффициентов полинома, первая группа входов которого подключена к 2ⁿ канальной шине передачи значений коэффициентов, являющейся входом устройства, вторая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, третья группа входов которого подключена к q канальной шине передачи значений второй системы q модулей и четвертая группа входов которого подключена к 3-х канальной шине передачи случайных чисел, а выходы подключены к 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов, являющейся выходом устройства, и блок зашифрования логических переменных, первая группа входов которого подключена к n канальной шине передачи значений логических переменных, являющейся входом устройства, вторая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, третья группа входов которого подключена к q канальной шине передачи значений второй системы q модулей и четвертая группа входов которого подключена к 3-х канальной шине передачи случайных чисел, а выходы подключены к knq канальной шине передачи значений зашифрованных логических переменных, являющейся выходом устройства; блок расшифрования результата логических вычислений, первая группа входов которого подключена к k канальной шине передачи значений первой системы k модулей, вторая группа входов которого подключена к q канальной шине передачи значений второй системы q модулей, третья группа входов которого подключена к 3-х канальной шине передачи случайных чисел и четвертая группа входов которого подключена к kq канальной шине передачи значений вычисления полиномов, являющейся входом устройства, а выходы подключены к s канальной шине передачи значений вычисления булевых функций, являющейся выходом устройства; при этом блок генерации случайных чисел состоит из 5-ти устройств вычисления остатка по модулю, где второй вход i-го устройства вычисления остатка по модулю подключен к i-му каналу 5-ти канальной шины передачи значений модулей-ограничителей, ограничивающих значения случайных чисел, генерируемых физическим генератором случайных чисел, путем вычисления остатков (i=1, 2, …, 5), а первый вход i-го устройства вычисления остатка по модулю подключен к i-му выходу физического генератора случайных чисел (i=1, 2, …, 5), выходы первого и второго устройств вычисления остатка по модулю подключены соответственно к адресным входам первого и второго блоков памяти хранения систем простых модулей, где k выходы первого блока памяти хранения систем простых модулей подключены к k канальной шине передачи значений первой системы k модулей, a q выходы второго блока памяти хранения систем простых модулей подключены к q канальной шине передачи значений второй системы q модулей, выходы третьего, четвертого и пятого устройств вычисления остатка по модулю подключены к 3-х канальной шине передачи случайных чисел; при этом блок зашифрования коэффициентов состоит из регистра памяти, входы которого подключены к 2ⁿ канальной шине передачи значений коэффициентов, а выходы с первого по 2ⁿ-ый соответственно подключены ко вторым входам 2ⁿ многоразрядных умножителей, первые входы которых подключены к первому каналу 3-х канальной шины передачи случайных чисел, а выходы многоразрядных умножителей подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с первого по k-ый, и так далее, и выход 2ⁿ-го многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с (k(2ⁿ-1)+1)-го по 2ⁿk-ый, а первые входы устройств вычисления остатка по модулю с первого по k-ый подключены соответственно к каналам с первого по k-ый k канальной шины передачи значений первой системы k модулей, и так далее, и первые входы устройств вычисления остатка по модулю с (k(2ⁿ-1)+1)-го по 2ⁿk-ый подключены соответственно к каналам с первого по k-ый k канальной шины передачи значений первой системы k модулей, выходы устройств вычисления остатка по модулю подключены ко вторым входам многоразрядных умножителей, где выход i-го устройства вычисления остатка по модулю подключен ко второму входу i-го многоразрядного умножителя (i=1, 2, … 2ⁿk), первый вход каждого многоразрядного умножителя подключен ко 2-му каналу 3-х канальной шины передачи случайных чисел, а выходы многоразрядных умножителей подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с первого по q-ый, и так далее, и выход 2ⁿk-го многоразрядного умножителя подключен ко вторым входам устройств вычисления остатка по модулю с ((2ⁿk-1)q+1)-го по 2ⁿkq-ый, а первые входы устройств вычисления остатка по модулю подключены к q канальной шине передачи значений второй системы q модулей, где первый вход первого устройства вычисления остатка по модулю подключен к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход q-го устройства вычисления остатка по модулю подключен к q-му каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход ((2ⁿk-1)q+1)-го устройства вычисления остатка по модулю подключен к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первый вход 2ⁿkq-го устройства вычисления остатка по модулю подключен к q-му каналу q канальной шины передачи значений второй системы q модулей, а выходы устройств вычисления остатка по модулю подключены ко входам регистра памяти хранения зашифрованных коэффициентов, где выход i-ого устройства вычисления остатка по модулю подключен к i-му входу регистра памяти хранения зашифрованных коэффициентов (i=1, 2, …, 2ⁿkq), выходы которого с первого по 2ⁿkq-ый подключены к 2ⁿkq канальной шине передачи значений зашифрованных коэффициентов; при этом блок зашифрования переменных состоит из регистра памяти хранения значений переменных, входы которого подключены к n канальной шине передачи значений логических переменных, k многоразрядных умножителей, вторые входы каждого из которых подключены к третьему каналу 3-х канальной шины передачи случайных чисел, а первые входы подключены к k канальной шине передачи значений первой системы k модулей, где первый вход i-го многоразрядного умножителя подключен к i-му каналу k канальной шины передачи значений первой системы k модулей (i=1, 2, …, k), kn многоразрядных сумматоров, первые входы которых подключены к выходам многоразрядных умножителей, где первый вход первого, (k+1)-го, и так далее, и ((k-1)n+1)-го многоразрядного сумматора подключен к выходу первого многоразрядного умножителя, и так далее, и первый вход k-го, 2k-го, и так далее, и kn-го многоразрядного сумматора подключен к выходу k-го многоразрядного умножителя, а вторые входы многоразрядных сумматоров подключены к выходам регистра памяти хранения значений переменных, где вторые входы многоразрядных сумматоров с первого по k-ый подключены к первому выходу регистра памяти хранения значений переменных, и так далее, и вторые входы многоразрядных сумматоров с ((k-1)n+1)-го по kn-ый подключены к n-му выходу регистра памяти хранения значений переменных, выходы многоразрядных сумматоров подключены ко вторым входам устройств вычисления остатка по модулю, где выход первого многоразрядного сумматора подключен ко вторым входам устройств вычисления остатка по модулю с первого по q-ый, и так далее, и выход kn-го многоразрядного сумматора подключен ко вторым входам устройств вычисления остатка по модулю с ((kn-1)q+1)-го по knq-ый, первые входы устройств вычисления остатка по модулю подключены к q канальной шине передачи значений второй системы q модулей, где первые входы первого, (q+1)-го и так далее, и ((kn-1)q+1)-го устройства вычисления остатка по модулю подключены к первому каналу q канальной шины передачи значений второй системы q модулей, и так далее, и первые входы q-го, 2q-го, и так далее, и knq-го устройства вычисления остатка по модулю подключены к q-му каналу q канальной шины передачи значений второй системы q модулей, выходы устройств вычисления остатка по модулю подключены ко входам регистра памяти хранения значений зашифрованных переменных, где выход i-го устройства вычисления остатка по модулю подключен к i-му входу регистра памяти хранения значений зашифрованных переменных (i=1, 2, …, knq), выходы которого подключены к knq канальной шине передачи значений зашифрованных логических переменных; при этом блок расшифрования результата логических вычислений состоит из регистра памяти, хранения значений вычисления полиномов, входы которого подключены к kq канальной шине передачи значений вычисления полиномов, k устройств восстановления по КТО, первые группы входов которых подключены к выходам регистра памяти хранения значений вычисления полиномов, где первая группа входов первого устройства восстановления по КТО подключена к первым q выходам регистра памяти, хранения значений вычисления полиномов и так далее, и первая группа входов k-го устройства восстановления по КТО подключена к k-ым q выходам регистра памяти, хранения значений вычисления полиномов, вторая группа q входов каждого устройства восстановления по КТО подключена к q канальной шине передачи значений второй системы q модулей, а выходы подключены к первым входам устройств целочисленного деления, где выход i-го устройства восстановления по КТО подключен к первому входу i-го устройства целочисленного деления (i=1, …, k), вторые входы каждого из устройств целочисленного деления подключены ко второму каналу 3-х канальной шины передачи случайных чисел, а выходы подключены к первой группе входов устройства восстановления по КТО, вторая группа k входов которого подключена к k канальной шине передачи значений первой системы k модулей, а выход подключен к первому входу устройства целочисленного деления, второй вход которого подключен к первому каналу 3-х канальной шины передачи случайных чисел, а выход подключен ко входу регистра памяти хранения значений вычисления булевых функций, двоичные выходы которого подключены к s канальной шине передачи значений вычисления булевых функций.