Вычислительный модуль и способ выполнения арифметической операции с зашифрованными операндами - RU2279123C2
Код документа: RU2279123C2
Чертежи
Описание
Настоящее изобретение относится к устройствам обработки данных и, в частности, к устройствам обработки данных, требующим обработки данных или адресов на высоком уровне защищенности, обеспечивающим защиту от физических атак и перехвата.
При вычислении и/или обработке данных, связанных с необходимостью обеспечения защиты, используются микропроцессоры или маркеры доступа или другие устройства обработки данных с высоким уровнем защищенности, обеспечивающим защиту от физических атак и перехвата. Блоки кэш-памяти и буферной памяти, наборы регистров, а также каналы передачи, например, в виде шин, на микропроцессорах, представляют собой регулярные структуры на кристалле, которые легко идентифицировать. Таким образом, они представляют собой предпочтительные точки атаки. Атаки могут состоять в перехвате посредством атак на выводах или в анализе профиля тока.
Методы шифрования позволяют эффективно защищать блоки внешней памяти, блоки буферной памяти и шины, в результате чего, обрабатываемые данные, например, пользовательские данные или программы, перемещаются и сохраняются на всем кристалле, предпочтительно, только в зашифрованном виде.
На фиг.10 показана общая схема вычислительного устройства. Главным блоком вычислительного устройства является арифметико-логическое устройство (АЛУ) 800. Простейшее АЛУ, способное выполнять операцию с двумя операндами, требует двух входных шин А, В (802, 804) и выходной шины Z (806). Входные шины и выходная шина АЛУ 800 присоединены к главной шине F (808). К главной шине (808) обычно также подключены две дополнительные шины D, E (810, 812), причем шина 810 подключена к кэшу М2 (814), который, в свою очередь, подключен к внешней памяти М1 (812) через шину памяти С (816). Кроме того, согласно варианту осуществления, показанному на фиг.10, вычислительное устройство содержит наборы регистров М3 (820), причем каждый набор регистров содержит регистры, в которых могут храниться (первоначально) входные данные АЛУ или выходные данные АЛУ, не подлежащие переносу в кэш 814 или во внешнюю память 818, т.е. не подлежащие загрузке из наборов регистров во внешнюю память до окончания сравнительно долгого вычисления.
В вычислительном устройстве, осуществляющем вычисления, критические с точки зрения обеспечения защищенности, данные шифруются до сохранения в различных блоках памяти М1-М3. Кроме того, во избежание атаки на шинные линии 802, 804, 806, 810, 812 и 816, предпочтительно передавать данные по этим шинным линиям в зашифрованном виде. В этом случае, на двух входах АЛУ предусмотрены две схемы 822, 824 дешифрования для дешифрования операндов, присутствующих на шинах А, В, например, данных или адресов, подлежащих обработке на АЛУ 800, перед их обработкой. Для защиты результата операции АЛУ, на выходе АЛУ 800 предусмотрено устройство 826 шифрования, поэтому на шинах 802, 804, 806 присутствуют зашифрованные данные.
Хотя эта концепция позволяет эффективно подавлять атаки на шинные линии, например, главную шину 808, а также шины 810, 812, 816 памяти, она обладает тем недостатком, что между двумя схемами 822, 824 дешифрования и схемой 826 шифрования присутствуют незащищенные данные открытого текста, поэтому, хотя атакующему труднее выяснить, где в вычислительном устройстве находится АЛУ 800, задача атакующего значительно облегчается, когда он определит местоположения устройств дешифрования, поскольку на выходах устройств 822 и 824 дешифрования присутствуют данные открытого текста.
С другой стороны, данные нужно дешифровать, поскольку операции АЛУ, которые могут представлять собой, например, простые арифметические операции, например, И, ИЛИ, «исключающее или», НЕ-И, НЕ-ИЛИ, НЕ или «сложение», нельзя просто осуществлять над зашифрованными данными, поскольку операции шифрования и дешифрования и простая операция в общем случае не коммутируются, что приводит к искажению результатов. Чтобы, тем не менее, закрыть этот пробел в защите, устройства 822, 824 дешифрования и устройство 826 шифрования обычно предпочитают размещать как можно ближе к АЛУ 800, чтобы линии передачи, по которым идут данные открытого текста, были как можно короче, что позволяет снизить эффективность атаки. Альтернативно, линии передачи, по которым передаются данные открытого текста, можно «скрывать» в кристалле с использованием технологических мер, например, с использованием особых профилей легирования или с использованием совокупности ложных линий, из-за чего атакующему приходится выявлять линии, по которым фактически передаются данные открытого текста, в отличие от ложных линий, по которым передаются только диверсионные, т.е. фальшивые, данные.
Эти традиционные меры защиты вычислительного устройства от атак сталкиваются с той проблемой, что они требуют дополнительных затрат и ограничивают свободу в разработке АЛУ. Ограничение свободы конструкции является недостатком, в частности, если АЛУ должно быть высокопроизводительным АЛУ, которое призвано выполнять совокупность вычислений, в частности, например, расчеты с длинными числами. Чтобы, тем не менее, поддерживать время вычисления в разумных пределах, АЛУ следует конструировать с учетом оптимизации производительности. Конечно, клиент вправе ожидать от любой системы защиты высокого уровня защищенности. Однако, в то же время, клиент также ожидает приемлемо продолжительного, предпочтительно, короткого времени вычисления. Короткое время вычисления важно, чтобы система защиты была принята на рынке, поскольку долгое время вычисления в идентификации защиты будет рассматриваться клиентом как раздражающий фактор.
Задачей настоящего изобретения является обеспечение простой и недорогой концепции реализации выполнения операции на зашифрованном операнде, сумматора с выборочным переносом для зашифрованных данных, а также криптографического процессора, который, тем не менее, обеспечивает высокий уровень защиты от атак. Для решения этой задачи предусмотрены вычислительное устройство, заявленное в пункте 1 формулы изобретения, способ, заявленный в п.27, криптографический процессор, заявленный в п.28, и способ или устройство для формирования средства вычислительного устройства, заявленный/ое в п.36 и/или в п.37.
Настоящее изобретение основано на том, что наивысшего уровня защищенности можно достичь, когда вычислительное устройство работает с полностью зашифрованными операндами, в связи с чем на входе обрабатывающего устройства не осуществляется дешифрование, и на выходе обрабатывающего устройства или АЛУ не осуществляется шифрование. Согласно изобретению, реализация АЛУ предусматривает, помимо входа для первого зашифрованного операнда и входа для второго зашифрованного операнда, наличие третьего входа для параметра шифрования, причем реализация АЛУ позволяет связывать зашифрованные операнды и параметры шифрования в соответствии со спецификацией вычисления над шифрованным текстом с учетом того, каким образом зашифрованы два операнда, в результате чего на выходе получается зашифрованный результат, равный значению, которое можно было бы получить, подвергнув первый операнд арифметической операции в соответствии со спецификацией вычисления над открытым текстом в незашифрованном виде и подвергнув второй операнд арифметической операции в соответствии со спецификацией вычисления над открытым текстом в незашифрованном виде, а затем зашифровав полученный результат. Другими словами, арифметическая операция, подлежащая выполнению над двумя зашифрованными операндами, например, операция OR (ИЛИ) в качестве спецификации вычисления над открытым текстом заменяется несколькими арифметическими подоперациями, формирующими спецификацию вычисления над шифрованным текстом, причем арифметические подоперации выбираются так, чтобы они имели на входе зашифрованные операнды либо инвертированные зашифрованные операнды и параметр шифрования либо инвертированный параметр шифрования.
При необходимости, можно предусмотреть дополнительные подоперации, имеющие на входе промежуточные результаты, полученные из зашифрованных входных операндов и ключа, так что входные операнды в виде открытого текста сами по себе нигде не присутствуют в АЛУ. Для повышения уровня защищенности, предпочтительно, чтобы не существовало также никаких промежуточных результатов из входных операндов в виде открытого текста. На примере операции ИЛИ это означает, что зашифрованные операнды и параметр шифрования подвергаются нескольким операциям AND (И) и нескольким операциям OR (ИЛИ) и, при необходимости, операциям отрицания (инвертирования), в результате чего АЛУ выдает результат, который равен результату, который был бы получен, если бы зашифрованные входные операнды были бы сначала дешифрованы, затем подвергнуты единичной операции ИЛИ, а затем повторно зашифрованы.
В случае использования метода шифрования, состоящего из алгоритма шифрования и ключа, для каждого алгоритма шифрования получается отдельная структура АЛУ для арифметической операции. В этом случае, уровень защищенности может возрастать просто за счет смены ключа алгоритма шифрования, либо для каждой операции, либо через несколько операций, что имеет преимущество в том, что изменяющиеся ключи можно использовать в случае идентичной структуры АЛУ, что еще больше затрудняет для атакующего извлечение данных открытого текста, например, из структуры АЛУ.
Иными словами, реализация обрабатывающего блока вычислительного устройства, отвечающего изобретению, позволяет выполнять одну или несколько математических подопераций, которые, совместно, обеспечивают спецификацию вычисления, выведенную из спецификации для операции с незашифрованными операндами, так что, по меньшей мере, один незашифрованный операнд, из которого получается, по меньшей мере, один зашифрованный операнд, заменяется математической комбинацией, по меньшей мере, одного зашифрованного операнда и параметра шифрования, причем математическая комбинация является обратной по отношению к алгоритму шифрования, с помощью которого зашифрован зашифрованный операнд.
Посредством математической комбинации, спецификация вычисления над открытым текстом преобразуется в спецификацию вычисления над шифрованным текстом, содержащую одну или несколько математических подопераций, которые получают, в качестве входной величины, только зашифрованный операнд или его инвертированную версию, или комбинацию зашифрованного операнда и/или его инвертированной версии с другими операндами. Незашифрованный операнд сам по себе нигде не появляется в качестве входной величины для математической подоперации и, потому, не может быть перехвачен.
Ясно, что спецификация вычисления над шифрованным текстом, которая получается из одного или нескольких математических подопераций, может быть реализована любым желаемым способом. Иными словами, это значит, что математические подоперации, которые совместно формируют спецификацию вычисления над шифрованным текстом, могут быть любого рода. Необходимо только, чтобы совместно они формировали именно ту спецификацию вычисления над шифрованным текстом, которая обеспечивает те же результаты, что и соответствующая спецификация вычисления над открытым текстом после шифрования результата.
Еще одно предварительное условие состоит в том, чтобы алгоритм шифрования, с помощью которого шифруется, по меньшей мере, один операнд, был обратимым алгоритмом шифрования. Если алгоритм шифрования является, например, побитовой функцией «исключающее ИЛИ» (XOR) или функцией «исключающее НЕ-ИЛИ» (XNOR), то алгоритм, обратный алгоритму шифрования, прост. Это также будет, опять же, функция «исключающее ИЛИ» и/или «исключающее НЕ-ИЛИ».
Концепция изобретения, в принципе, может быть реализована для любого обратимого алгоритма шифрования, в зависимости от степени сложности, который может быть оправдан в каждом случае. Простейшая реализация зашифрованного вычислительного устройства состоит в использовании побитовой операции XOR с ключом в качестве алгоритма шифрования, поскольку алгоритм, обратный алгоритму шифрования, опять же, представляет собой операцию «исключающее ИЛИ» с тем же ключом. Конечно, то же справедливо для функции «исключающее НЕ-ИЛИ».
В предпочтительных вариантах осуществления настоящего изобретения, сам по себе алгоритм шифрования является, опять же, побитовой арифметической операцией, например, операцией «исключающее ИЛИ» или «исключающее НЕ-ИЛИ». С учетом правил преобразования для арифметических операций, можно найти арифметическое уравнение, и, начиная с арифметической операции, подлежащей вычислению, и с алгоритма шифрования, причем в уравнении имеются не операнды в виде открытого текста, а зашифрованные операнды, логически связанные друг с другом и/или с параметром шифрования с использованием подопераций, чтобы обеспечить, опять же, тот же результат, который был бы получен, если бы входные параметры были бы сначала дешифрованы, затем подвергнуты арифметической операции, а затем снова зашифрованы.
Преимущество настоящего изобретения состоит в том, что в вычислительных устройствах, отвечающих изобретению, нигде нет операндов в виде открытого текста, а присутствуют только зашифрованные операнды. Таким образом, атакующий уже не может перехватить операнды в виде открытого текста в каком-либо месте вычислительного устройства.
Еще одно преимущество настоящего изобретения состоит в том, что, если метод шифрования, для которого реализовано вычислительное устройство, отвечающее изобретению, используется для сохранения данных в памяти, то никакие данные открытого текста уже не присутствуют ни в каком месте компьютера, но видны только зашифрованные данные и параметры шифрования. Если вычислительное устройство, отвечающее изобретению, реализовано на плате с микросхемами, для которой не гарантировано постоянное пребывание в защищенной среде, но напротив, она может оказаться в руках атакующего и в полном его распоряжении, атакующий никоим образом не может получить из платы с микросхемами никаких данных открытого текста, поскольку там находятся только зашифрованные данные. Данные открытого текста, подлежащие обработке, будут, таким образом, шифроваться в защищенной среде прежде, чем будут загружены в плату с микросхемами, и в качестве защищенной среды выступает, например, стационарный терминал, который может представлять собой, например, устройство для выдачи наличности, доступ к которому разрешен только определенным лицам. Структура интерфейса к плате с микросхемами не позволяет атакующему извлечь данные открытого текста из устройства выдачи наличности, поскольку данные открытого текста зашифрованы на защищенном терминале прежде, чем поступили на интерфейс к плате с микросхемами, и, поскольку защищенный терминал шифрует данные открытого текста таким образом, в частности, потому, что алгоритм шифрования согласуется со структурой АЛУ на плате с микросхемами. При этом, ни в одном месте не требуется двустороннего шифрования, вследствие чего получается фактически замкнутая система. Эту замкнутую систему легко защитить, если место, где в систему вводятся данные открытого текста, находится в надежной среде.
Еще одно преимущество настоящего изобретения в том, что АЛУ может быть реализовано различными способами в зависимости от имеющейся технологии изготовления кристаллов. Например, подоперации можно выбирать по-разному, в зависимости от правил арифметики, которая может быть, например, двоичной, чтобы всегда выдавать один и тот же результат, т.е. одну и ту же таблицу истинности. Если существует полная система, например, НЕ-И (NAND) или НЕ-ИЛИ (NOR), то может быть найдена соответствующая реализация.
Если, например, существуют только вентили НЕ-И, которые имеют всего лишь два входа, то можно найти реализацию, в которой присутствуют только вентили НЕ-И с двумя входами. Если же присутствуют вентили НЕ-И или вентили НЕ-ИЛИ, имеющие несколько входов, и, если, дополнительно, можно простым способом реализовать операции НЕ (NOT), то такую же таблицу истинности можно реализовать с использованием совокупности других связей и подопераций. Эту гибкость или изменяемость можно дополнительно использовать для нахождения наиболее подходящей компоновки в плане конструкций схем и времени вычисления или для использования сменных компоновок для одних и тех же вычислительных устройств, чтобы дополнительно сбить с толку потенциальных атакующих, желающих, например, сравнить несколько плат с микросхемами для получения секретной информации.
В наиболее общем случае, только операнд операции, подлежащей выполнению вычислительным устройством, является зашифрованным операндом, тогда как другие операнды являются операндами в виде открытого текста. Это уже обеспечивает определенный уровень защищенности в арифметической и/или логической операции, поскольку результат операции И между первым параметром «а» и вторым параметром «b» уже зашифрован, если только один из операндов, т.е. «а» или «b», зашифрован.
Альтернативно, оба операнда могут быть зашифрованы одним и тем же и/или разными алгоритмами шифрования, или одним алгоритмом шифрования, но с разными ключами.
Вычислительное устройство, отвечающее изобретению, может быть также выполнено с возможностью осуществления операции мультиплексирования, в которой, по меньшей мере, один операнд, который зашифрован, является управляющим сигналом. Мультиплексор, имеющий зашифрованный управляющий сигнал, может либо мультиплексировать незашифрованные входные данные зашифрованным способом, либо мультиплексировать зашифрованные входные данные зашифрованным способом. В зависимости от размера мультиплексора, управляющий сигнал имеет длину всего лишь одного бита, т.е. в случае мультиплексора 2:1. Для мультиплексоров большего размера, управляющий сигнал может иметь длину в 2 или несколько битов. В зависимости от нужного стандарта защиты, каждый бит управляющего сигнала может быть зашифрован своим собственным ключом, или все биты управляющего сигнала могут быть зашифрованы одним и тем же ключом.
Фиг.1 - схема вычислительного устройства, отвечающего изобретению.
Фиг.2а - реализация вычислительного устройства, отвечающего изобретению, для шифрования посредством побитовой операции «исключающее ИЛИ» операндов и, таким образом, для реализации на АЛУ операции «исключающее ИЛИ».
Фиг.2b - таблица истинности для схемы, показанной на фиг.2а.
Фиг.3а - схема АЛУ для вычислительного устройства, отвечающего изобретению, для реализации операции И, где операнды зашифрованы посредством операции «исключающее ИЛИ».
Фиг.3b - таблица истинности для схемы, показанной на фиг.3а.
Фиг.4а - схема АЛУ для вычислительного устройства, отвечающего изобретению, для реализации операции ИЛИ, где операнды зашифрованы посредством операции «исключающее ИЛИ».
Фиг.4b - таблица истинности для схемы, показанной на фиг.4а.
Фиг.5а - схема АЛУ для вычислительного устройства, отвечающего изобретению, для реализации операции НЕ-ИЛИ, где операнды зашифрованы посредством операции «исключающее ИЛИ».
Фиг.5b - таблица истинности для схемы, показанной на фиг.5а.
Фиг.6а - схема АЛУ для вычислительного устройства, отвечающего изобретению, для реализации операции НЕ-И, где операнды зашифрованы посредством операции «исключающее ИЛИ».
Фиг.6b - таблица истинности для схемы, показанной на фиг.6а.
Фиг.7а - схема АЛУ для вычислительного устройства, отвечающего изобретению, для реализации операции «сложение» для трех операндов, где три операнда зашифрованы посредством операции «исключающее ИЛИ».
Фиг.7b - таблица истинности для схемы, показанной на фиг.7а, в отношении переносов.
Фиг.8а - блок-схема мультиплексора 2:1 с зашифрованным управляющим сигналом.
Фиг.8b - блок-схема мультиплексора 3:1 с зашифрованным управляющим сигналом.
Фиг.8с - блок-схема мультиплексора 4:1 с зашифрованным управляющим сигналом.
Фиг.8d - пример реализации мультиплексора 2:1 с зашифрованным управляющим сигналом.
Фиг.9а-9с - блок-схемы вычислительного устройства, отвечающего изобретению, реализованного в качестве сумматора, где операнды шифруются с помощью разных ключей и переносы зашифрованы по-разному.
Фиг.10 - вычислительное устройство, отвечающее уровню техники, с дешифрованием на входе АЛУ и шифрованием на выходе АЛУ.
Фиг.11а - блок-схема криптопроцессора, отвечающего изобретению, имеющего вычислительное устройство, отвечающее изобретению.
Фиг.11b - более подробное представление устройства шифрования/дешифрования, показанного на фиг.11а.
Фиг.12а - схема двух битовых секций сумматора, причем каждая битовая секция содержит 1-битовый полный сумматор в качестве вычислительного устройства, отвечающего изобретению.
Фиг.12b - обобщенная блок-схема сумматора со сквозным переносом для зашифрованных данных.
Фиг.13 - блок-схема сумматора с выборочным переносом для зашифрованных данных с выборочным переносом в области шифрованного текста.
На фиг.1 показано вычислительное устройство, отвечающее изобретению, для выполнения арифметической операции над, по меньшей мере, двумя операндами, причем, по меньшей мере, два операнда являются зашифрованными операндами ak и bk. Вычислительное устройство, отвечающее изобретению, содержит арифметико-логическое устройство АЛУ 10, которое содержит, помимо первого входа 12 для первого зашифрованного операнда ak , второй вход 14 для второго зашифрованного операнда bk. АЛУ 10, отвечающее изобретению, дополнительно содержит третий вход 16 для параметра шифрования k, а также выход 18 для вывода зашифрованного результата арифметической операции ОП (ОР), осуществляемой АЛУ 10. Арифметико-логическое устройство 10 позволяет связывать первый вход 12, второй вход 14 и третий вход 16 для параметра шифрования k с учетом вида шифрования операндов ak, bk, с использованием арифметических подопераций таким образом, что на выходе получаются зашифрованный результат, который равен значению, можно было бы получить, подвергнув первый операнд «а» арифметической операции ОП в незашифрованном виде и подвергнув второй операнд «b» арифметической операции ОП в незашифрованном виде, а потом зашифровав полученный результат, что представлено квадратными скобками и индексом k на фиг.1. В арифметико-логическом устройстве 10 не осуществляется никакого дешифрования операндов ak и bk, но имеют место только такие подоперации, которые выполняются над зашифрованными операндами ak, bk и над параметром шифрования k или над инвертированными зашифрованными операндами, или над инвертированным параметром шифрования, или над промежуточными результатами предыдущих операций.
Описанное арифметико-логическое устройство, отвечающее изобретению, позволяет выполнять арифметико-логические операции непосредственно над зашифрованными данными и выводить результат также в зашифрованном виде. При этом, предпочтительно, также гарантируется, что ни в каком промежуточном результате не появляется открытый текст. Таким образом, реализуется структура процессора, обеспечивающая работу в полностью зашифрованном режиме в сочетании с зашифрованным хранением.
АЛУ 10, отвечающий изобретению, позволяет осуществлять все манипуляции в ЦП с зашифрованными данными. На нижеследующих чертежах простые операции АЛУ, такие, как «сложение», И, ИЛИ, НЕ, НЕ-И, НЕ-ИЛИ и «исключающее ИЛИ», представлены лишь в порядке примера. При этом данные на всех шинах (фиг.10), а также в блоках памяти М1-М3 (фиг.10) предполагаются зашифрованными.
Исключительно в порядке примера, в качестве простого метода шифрования на шинах A-F, показанных на фиг.10, используется побитовая операция «исключающее ИЛИ» над предпочтительно временным ключом kn и данными, однако и этот метод шифрования обеспечивает защиту вследствие возможности осуществления частой смены ключа. В данном случае n - это индекс ключа. Ключ kn предпочтительно является временным и область его действия ограничена, например, только одной или несколькими последовательными операциями. Для простейшего ЦП требуются две входные шины А, В, которые представляют собой две входные линии 12, 14, показанные на фиг.1. Данные на обеих шинах побитово шифруются одним и тем же ключом kn в целях упрощенного представления. Однако, на двух входах 12, 14, показанных на фиг.1, можно, конечно, использовать разные ключи. Кроме того, не обязательно использовать побитовое шифрование, но можно также шифровать, например, каждый второй, каждый четвертый, каждый шестой или каждый восьмой бит, оставляя перемежающие биты незашифрованными. Определенного уровня шифрования можно достичь, зашифровав только один бит операнда или один единственный разряд операнда, оставив другие разряды незашифрованными.
Хотя на нижеследующих фиг. 2а-7b в качестве основы всегда предполагается шифрование посредством побитового «исключающего ИЛИ» с ключом kn, очевидно, что в качестве алгоритма шифрования можно использовать любую другую обратимую операцию, например, операцию «исключающее НЕ-ИЛИ». Кроме того, в качестве алгоритмов шифрования можно использовать любые другие обратимые алгоритмы шифрования. Единственное предварительное условие состоит в том, что нужно найти выражения, в которых только зашифрованные операнды ak, bk и параметр шифрования k существуют в состоянии, когда они подверглись некоторой логической обработке, например, инвертированы или связаны или появляются в общем случае в математической функции, что становится очевидным при обзоре математических законов, например, правил эквивалентности для арифметических вычислений по аналогии с приведенными ниже примерами.
Как уже было объяснено, для нижеследующих иллюстративных реализаций АЛУ 10, отвечающего изобретению, в целях упрощения представления, предполагается шифрование операндов «а» и «b» посредством побитового «исключающего ИЛИ», причем зашифрованные операнды и/или зашифрованные результаты обозначаются индексом k, параметр шифрования обозначается k, и индекс n является индексом счета для n-го бита соответствующего операнда и/или ключа. Зашифрованные биты на входе вычислительного устройства, отвечающего изобретению, вычисляются следующим образом:
Уравнения, обратные уравнениям (1а) и (2а) (уравнения дешифрования), таковы:
Следующее вычисление вытекает из этого для операции «исключающее ИЛИ», т.е., скажем, если АЛУ должно выполнять операцию «исключающее ИЛИ»:
Нижеследующее уравнение 4 доказывает уравнение 3.
На фиг.2а представлена схемотехническая реализация уравнения 3. Для обеспечения результата, который эквивалентен операции «исключающее ИЛИ» над незашифрованными операндами a, b и последующему шифрованию, АЛУ 10 в этом случае содержит для выполнения арифметико-логических подопераций тройной вентиль 120 «исключающее ИЛИ», который связывает друг с другом зашифрованные входные параметры ak, bk и k. Таким образом, можно видеть, что параметры «а» и «b» открытого текста не присутствуют нигде в АЛУ 10, показанном на фиг.2а.
В реализации тройного вентиля «исключающее ИЛИ» гарантируется, что на внутренней линии нет никаких данных открытого текста. Например, запрещено использовать двухкаскадные двойные вентили «исключающее ИЛИ», поскольку в этом случае могут появиться промежуточные результаты открытого текста. Поэтому, для реализации тройного вентиля «исключающее ИЛИ» предпочтительно использовать таблицу перекодировки, имеющую, в качестве входных параметров, значения, представленные на фиг.2b для входных параметров kn, akn и bkn и (an XOR bn XOR kn). Таблица может быть реализована в ПЗУ.
Следует указать, что реализация операции «исключающее ИЛИ», показанная на фиг.2а, является лишь иллюстративной. Конечно, выражение, представленное в середине уравнения (4), также можно реализовать схемотехническими средствами. В этом случае, потребуются четыре соответствующим образом соединенных вентиля «исключающее ИЛИ». Хотя эта реализация затратна в отношении схемотехники и времени вычисления, ее, тем не менее, можно выбрать для того, чтобы ввести в заблуждение потенциальных атакующих.
На фиг.2b представлена таблица истинности. В первых трех столбцах представлены все возможные комбинации ключа k, первого операнда «а» и второго операнда «b». В столбцах №4 и №5 показаны зашифрованные входные операнды для всех возможных комбинаций битов. В столбце №6 показан результат операции «исключающее ИЛИ» для двух незашифрованных операндов a и b. В седьмом столбце показан результат, который получается в результате перешифрования выхода операции «исключающее ИЛИ» над незашифрованными операндами, что можно реализовать, например, посредством схемы 826 на фиг.10.
В восьмом столбце на фиг.2b показан результат первой арифметической подоперации 120. В предпоследнем столбце на фиг.2b показан результат второй подоперации 122, сравнение девятого столбца с седьмым столбцом на фиг.2b подтверждает правильность связи с арифметическими подоперациями.
На фиг.3а представлена реализация вычислительного устройства, отвечающего изобретению, в котором АЛУ выполняет операцию И. На фиг.3b представлена соответствующая таблица истинности. В нижеследующем уравнении (5) указан путь от операции И над незашифрованными операндами «а» и «b» с последующим шифрованием посредством «исключающего ИЛИ», что можно реализовать посредством схемы, показанной на фиг.10, к реализации настоящего изобретения, заданной, например, последней строкой уравнения (5). АЛУ, выполняющее операцию И, включает в себя всего пять подопераций 131-135, которые являются операциями И и операциями ИЛИ. Таблица истинности на фиг.3b подтверждает правильность реализации АЛУ, отвечающего изобретению, с использованием нескольких арифметико-логических операций для связывания зашифрованных операндов и ключа. Здесь уместно отметить, что любая из промежуточных строк уравнения (5) может быть реализована схемотехническими средствами в зависимости от того, какие вентили доступны разработчику схемы, и в зависимости от допустимых вычислительных затрат. Предполагается, что схемотехническая реализация, показанная на фиг.3а, более эффективна в отношении времени вычислений, чем схемотехническая реализация, например, четвертой строки уравнения (5). Однако, эту реализацию также можно использовать, чтобы вводить в заблуждение потенциальных атакующих, как уже было показано ранее.
Ниже даются ссылки на уравнение (5) для представления основной предложенной концепции создания средства вычислительного устройства посредством преобразования спецификации вычисления над открытым текстом в спецификацию вычисления над шифрованным текстом. Операция И обеспечена как спецификация вычисления над открытым текстом.
Кроме того, предполагается, как в случае уравнения (5), что зашифрованный операнд akn получается из незашифрованного операнда an посредством операции «исключающее ИЛИ» с ключом kn. Для простоты то же самое предполагается для операнда bkn.Таким образом, bkn эквивалентно результату операции «исключающее ИЛИ» над незашифрованным операндом bn с ключом kn. В вышеприведенном примере, спецификация вычисления над открытым текстом имеет вид: a И b. Спецификация вычисления над шифрованным текстом, которая получается в результате нескольких математических подопераций и в соответствии с которой реализуется блок шифрования, вытекает следующим образом из первой строки уравнения (5):
Незашифрованные операнды an и bn были заменены в уравнении (5) математической комбинацией зашифрованного операнда akn и ключа kn и bkn и ключа kn, соответственно, и эта математическая комбинация является обратной алгоритму шифрования. Таким образом, в правой части уравнения (5а) представлена спецификация вычисления над шифрованным текстом, полученная непосредственно из спецификации вычисления над открытым текстом.
Если операция «исключающее ИЛИ» используется в качестве алгоритма шифрования, то обратной функцией алгоритма шифрования вновь является функция «исключающее ИЛИ», т.е. она идентична алгоритму шифрования.
Для получения фактической реализации нужно иметь возможность преобразования спецификации вычисления над шифрованным текстом правой части уравнения (5а), где теперь присутствуют только зашифрованные операнды и ключи, любым описанным способом. Это преобразование может быть обеспечено соответствующими математическими законами и т.д. и представлено здесь для случая шифрования посредством «исключающего ИЛИ» или «исключающего НЕ-ИЛИ».
Предпочтительно использовать последнюю строку уравнения (5), полученную из правой части уравнения (5а), когда выполняется совокупность математических преобразований, как основание для реализации обрабатывающего устройства (10 на фиг.1). Таким образом, из уравнения (5а) можно видеть, как спецификация открытого текста для операции с незашифрованными операндами (an×bn) преобразуется в спецификацию вычисления над шифрованным текстом с математическими подоперациями путем замены незашифрованных операндов комбинацией зашифрованных операндов и параметров шифрования, причем эти математические подоперации можно реализовать любым способом, необходимым для математических преобразований, а именно, в соответствии с предварительным условием, согласно которому никакие подоперации не должны содержать в качестве входной величины операнда в виде открытого текста, для которого существует зашифрованный операнд.
Если шифруется только один операнд, то предварительное условие состоит в том, что операнд в виде открытого текста, соответствующий зашифрованному операнду, нельзя использовать нигде в качестве входной величины для математической подоперации.
На фиг.4а показана реализация операции ИЛИ над двумя операндами «а» и «b».
Уравнение (6) также указывает путь, которым можно следовать, чтобы получить совокупность подопераций, начиная с операции, использующей незашифрованные операнды, и с последующим шифрованием, причем совокупность подопераций такова, что они теперь содержат только зашифрованные операнды и параметр шифрования. На фиг.4а показано, как схемотехническая реализация канонической дизъюнктивной формы зашифрованной операции ИЛИ, использующая три подоперации И 141, 142, 143, две подоперации ИЛИ 144 и 145, а также операцию 146 отрицания и/или НЕ с ключом k, осуществляется на фиг.3а. Различные промежуточные результаты в уравнении (6) показывают, что АЛУ можно, конечно, реализовать различными способами, в данном случае, например, с использованием инвертирования зашифрованного первого операнда ak, зашифрованного второго операнда bk и/или ключа k.
Таблица истинности на фиг.4b показывает правильность схемотехнической реализации АЛУ, показанной на фиг.4а, при сравнении седьмого столбца с восьмым столбцом.
Ниже со ссылкой на фиг.5а описана реализация операции НЕ-ИЛИ над зашифрованными операндами. Для этого рассмотрим следующее уравнение (7).
На фиг.5а показана схемотехническая реализация уравнения (7). В качестве арифметических подопераций используются операции И 151-153, операции ИЛИ 154, 155 и операции НЕ 156 и 157, взаимодействующие и связанные друг с другом, согласно показанному на фиг.5а. Следует еще раз указать, что на фиг.5а, как и во всех остальных вариантах осуществления настоящего изобретения, присутствуют не только операнды ak и bk, зашифрованные на входе, но также все промежуточные результаты, например, на выходах вентилей 151-153, имеются промежуточные результаты, полученные из зашифрованных операндов, но не из операндов в виде открытого текста, вследствие чего, в вычислительном устройстве, отвечающем изобретению, нигде не появляются данные открытого текста, но везде присутствуют зашифрованные данные и/или результаты, полученные из зашифрованных данных. Таблица истинности, представленная на фиг.5b, и, в частности, сравнение седьмого столбца с восьмым столбцом показывает правильность схемотехнической реализации согласно фиг.5а.
Следует указать, что промежуточный результат, приведенный в уравнении (7), также можно реализовать схемотехническими средствами.
Ниже со ссылкой на фиг.6а описана реализация в соответствии с изобретением операции НЕ-И над зашифрованными операндами ak, bk с использованием параметра шифрования k. Уравнение (8) показывает арифметику для фиг.6а:
Показанное на фиг.6а АЛУ для вычислительного устройства, отвечающего изобретению, включает в себя в качестве арифметических подопераций три операции И 161-163, три операции НЕ 164-166, а также две операции ИЛИ 167, 168, которые, как показано на фиг.6а, связаны друг с другом и/или со входными операндами для обеспечения зашифрованного результата операции НЕ-И между незашифрованными операндами «а» и «b». Таблица истинности, показанная на фиг.6а, показывает на примере сравнения седьмого столбца с восьмым столбцом правильность реализации согласно фиг.6а.
Ниже со ссылкой на фиг.7а описана операция «сложение» как пример операции с тремя операндами над операндами a, b и c. Характеристическим уравнением будет нижеследующее уравнение (9):
Операция с тремя операндами и/или тремя битами операндов, при рассмотрении битовой секции сумматора, приводит к переносу «с», причем во втором с конца столбце и в третьем с конца столбце таблицы истинности, показанной на фиг.7b, переносы в операции «сложение» между незашифрованными операндами a, b и c обозначены как ср («р» от «plain» - незашифрованный), и в предпоследнем столбце показан перенос ck операции «сложение» АЛУ, отвечающего изобретению. Перенос ckn(n+1) получается из уравнения (10):
Реализация уравнения (10) представлена на фиг.7а. АЛУ, показанное на фиг.7а, для вычислительного устройства, отвечающего изобретению, включает в себя арифметические подоперации, а именно, операции И 171-173 и операции ИЛИ 179 и 180. На выходе получается перенос (ckn)n+1 для операции «сложение» с тремя входными операндами. Этот перенос совпадает, согласно таблице истинности, показанной на фиг.7b, с переносом, который можно получить, суммировав три операнда в незашифрованном виде с последующим шифрованием. В частности, (ckn)n+1 обозначает перенос для следующей более старшей ((n+1)-й) позиции (битовой секции), зашифрованный ключом kn, т.е. ключом текущей позиции n, который не зашифрован ключом kn+1 для следующей более старшей позиции. Это значит, что перешифрование (ckn)n+1 от ключа kn к ключу kn+1 происходит в зависимости от реализации битовой секции.
Уравнения (9) и (10) предписывают такую реализацию сумматора с зашифрованными операндами, при которой сумматор выводит зашифрованный агрегированный бит или бит суммы s' (s'=skn) и зашифрованный бит переноса с' (с'=(ckn)n+1), причем сумматор получает на входе, помимо двух зашифрованных операндов, зашифрованный бит переноса. Такой сумматор известен в технике как однобитовый полный сумматор.
Однобитовый полный сумматор используется для создания n-битового полного сумматора в качестве вычислительного устройства, отвечающего изобретению. В этом случае, однобитовый полный сумматор, согласно варианту осуществления настоящего изобретения, именуется битовой секцией или средством битовой секции. На фиг.12а показаны два средства битовой секции, связанные друг с другом. В частности, на фиг.12а показаны первая битовая секция 1200 для бита порядка n и битовая секция 1202 для бита порядка n+1. Главной частью каждой битовой секции является вычислительное устройство для зашифрованных операндов, обозначенное на фиг.12а позицией 1204. Согласно вышесказанному, возможны любые другие реализации зашифрованного сумматора при условии использования зашифрованных входных операндов и подачи зашифрованного переноса для создания зашифрованных выходных величин, т.е. зашифрованных битов суммы и зашифрованных битов переноса. В зависимости от необходимого уровня защищенности, можно использовать перенос в виде открытого текста и зашифрованный бит суммы, или же зашифрованный бит переноса и бит суммы в виде открытого текста. В сравнении с полностью незашифрованной реализацией АЛУ, здесь уже достигается повышенный уровень защищенности, хотя и не наивысший возможный уровень защищенности.
Однобитовый полный сумматор, показанный на фиг.12а, задан следующими двумя характеристическими уравнениями:
Здесь, уравнения сумматора выбраны так, что в сам однобитовый полный сумматор 1204 не нужно вводить никакого ключа шифрования, но его нужно вводить в битовую секцию 1202 или 1200 в соответствии с вариантом осуществления настоящего изобретения. Кроме того, однобитовый полный сумматор 1204 выполнен таким образом, что, для функции сумматора, на следующее более старшее средство битовой секции пересылается не сам зашифрованный бит переноса c′, а инвертированный зашифрованный бит переноса. Текущий бит зашифрованного операнда «а», т.е. a′n+1, поступает на первый вход «х» однобитового полного сумматора битовой секции для бита n+1. Текущий зашифрованный бит второго операнда, т.е. b′n+1, поступает на второй вход «y». Бит, который зависит от выходного бита переноса c′n предыдущей битовой секции 1200, поступает на третий вход «z».
Заметим, что выходной бит переноса предыдущей битовой секции может не использоваться напрямую, поскольку для разных средств 1200 и 1202 битовых секций существуют разные ключи шифрования kn+1 и kn, соответственно. Поэтому должно осуществляться перешифрование выходного бита переноса предыдущего средства битовой секции от ключа шифрования kn для предыдущего средства битовой секции в ключ шифрования kn+1текущего средства битовой секции.
В случае шифрования посредством операции «исключающее ИЛИ», перешифрование может достигаться просто путем выполнения операции «исключающее ИЛИ» над зашифрованным выходным битом битовой секции 1200 с ключом перешифрования tn+1. Эта операция представлена вентилем 1206 «исключающее ИЛИ». Ключ перешифрования tn+1 вычисляется, согласно его определению, путем выполнения операции «исключающее ИЛИ» над двумя ключами, относящимися к двум битовым секциям, т.е. путем выполнения «исключающего ИЛИ» над kn+1 для битовой секции 1202 и kn для битовой секции 1200.
Средство 1202 битовой секции выводит выходной бит переноса, который, однако, зашифрован ключом kn+1 и подлежит перешифрованию согласно следующему более старшему каскаду (не показан на фиг.12а). То же применяется ко входному переносу битовой секции 1200. В данном случае, получают выходной бит переноса следующего более младшего каскада, n-1, причем этот бит подлежит перешифрованию вентилем 1206 «исключающего ИЛИ» перешифрования.
Если несколько битовых секций соединены последовательно, как показано на фиг.12а, получается, в общем случае, сумматор со сквозным переносом (фиг.12b), который получает два зашифрованных операнда a′, b′, а также ключи перешифрования для отдельных битов ti в качестве входных величин. Сумматор со сквозным переносом, представленный на фиг.12b, дополнительно получает в качестве входного сигнала входной сигнал переноса, заданный равным 0 для обычного сумматора со сквозным переносом, работающего в режиме сумматора.
Очевидно, что вместо 0 можно применить 1, как будет объяснено для описанного ниже сумматора с выбором переноса. На выходе, сумматор, изображенный на фиг.12b, обеспечивает биты суммы в зашифрованном виде, а именно, s0', s1', ..., sN'. Кроме того, сумматор, изображенный на фиг.12b, выдает в качестве выходного сигнала бит переноса самой старшей битовой секции сумматора, если такой бит переноса создается.
Сумматор с выборочным переносом для зашифрованных данных можно построить, согласно фиг.13, из сумматора со сквозным переносом для зашифрованных данных, показанного на фиг.12а и фиг.12b, соответственно. Сумматоры с выборочным переносом работают быстрее, чем простые сумматоры со сквозным переносом, и описаны в "Computer Architecture a Quantitative Approach", Second Edition, Hennessy and Patterson, Morgan Kaufmann Publishers, Inc., 1996, appendix А. Однако, известные сумматоры с выборочным переносом, описанные в вышеупомянутой литературе, работают только с незашифрованными операндами и выдают незашифрованные результаты.
Ниже со ссылкой на фиг.13 описан сумматор с выборочным переносом, отвечающий изобретению, который выдает зашифрованные выходные сигналы. Прежде всего, предусмотрен первый сумматор 1300 со сквозным переносом, построенный из нескольких битовых секций, которые были описаны со ссылкой на фиг.12а. В частности, первый сумматор 1300 содержит совокупность средств битовой секции для суммирования зашифрованных битов операндов а', b' от младшего бита операндов до первого граничного бита операндов. На выходе, первый сумматор 1300 со сквозным переносом обеспечивает зашифрованные биты суммы r' для всех битов операндов от младшего бита операндов до первого граничного бита.
Выходной сигнал переноса битовой секции в сумматоре 1300 для первого граничного бита выводится посредством линии 1302, перешифруется посредством ключа преобразования tkn+1 (средством 1303 перешифрования) и поступает на средство 1304 выбора в виде мультиплексора. Сумматор с выборочным переносом дополнительно содержит второй сумматор 1306, а также третий сумматор 1308, которые обычно имеют такую же внутреннюю структуру, как первый сумматор 1300 и, как любые дополнительные сумматоры 1310 и 1312, которые могут присутствовать. Для перешифрования выходных битов переноса предусмотрено еще одно средство шифрования (например, 1315) в каждом случае между выходом мультиплексора предыдущего каскада и входом «1» мультиплексора следующего каскада.
На входы переноса младших битовых секций второго сумматора 1306 и третьего сумматора 1308 поступают HE(kn+1) и kn+1, соответственно (или, для третьего сумматора, HE(km+1) и km+1, соответственно).
Выбор битов суммы, которые вычисляются сумматором 1306 и сумматором 1308 (функция «выбора»), осуществляется в зависимости от того, 0 или 1 имеется на выходе 1302 переноса первого сумматора после перешифрования. Если получен 0, то в качестве битов r' результата выбирают биты результата второго сумматора 1306. Если же после перешифрования присутствует 1, то в качестве битов r' результата выбирают биты результата второго сумматора 1308. Если сумматор с выборочным переносом содержит дополнительные каскады, как показано на фиг.13, то выбор правильного сигнала переноса второго каскада производится с использованием средства 1314 выбора переноса. В частности, выбранным выходным сигналом переноса является выходной сигнал переноса того сумматора второго каскада, биты результата, т.е. биты суммы которого были выбраны в качестве результата r'.
Заметим, что фактический выбор «выбора переноса» осуществляется на линии 1302 посредством зашифрованного бита переноса. Поэтому не появляется никаких битов открытого текста. Дело в том, что биты HE(kn+1), а также kn+1, и HE(km+1), а также km+1, соответственно, поступающие на два сумматора второго и третьего каскадов, соответственно, также считаются, так сказать, зашифрованными битами и поступают, согласно фиг.12а, на вентиль 1206 «исключающего ИЛИ» младшей битовой секции соответствующего сумматора и, таким образом, подвергаются «перешифрованию», чтобы быть зашифрованными с помощью ключа фактического средства шифрования. Хотя на фиг.13 показано только, что ключи шифрования t поступают на сумматоры, следует отметить, что операция вычисления ключа перешифрования также может осуществляться в битовых секциях сумматора. В этом случае, на сумматоры должны поступать отдельные параметры шифрования ki для соответствующих битов, и операция «исключающее ИЛИ» над параметрами шифрования двух соседних битовых секций осуществляется на сумматорах.
Однако, из соображений скорости, предпочтительно вычислять параметры шифрования вне битовых секций.
Наконец, следует заметить, что вместо вышеописанного однобитового полного сумматора 1204, для выполнения однобитового полного сложения можно использовать другие средства, которые должны иметь возможность выполнять вычисление зашифрованных операндов и выводить зашифрованный бит результата и/или зашифрованный бит переноса без необходимости создавать промежуточные результаты в виде открытого текста.
Ниже описан еще один вариант осуществления вычислительного устройства, отвечающего изобретению, со ссылкой на фиг.8а-8d, где операция, подлежащая осуществлению над несколькими операндами, является операцией мультиплексирования. Если, например, как показано на фиг.8а, имеется два входных операнда a′, b′, где штрих «′» обозначает зашифрованные значения, операция над входными операндами состоит в том, что либо a′ поступает на выход, т.е. a′ становится сигналом m′, а b′ блокируется, либо b′ становится сигналом m′, а другой входной сигнал a′ блокируется.
Выбор осуществляется на основании зашифрованного управляющего сигнала x′, зашифрованного параметром шифрования k.
Вычислительное устройство, отвечающее изобретению, может, конечно, мультиплексировать незашифрованные операнды a, b с использованием зашифрованного управляющего сигнала x′.
Характеристическое уравнение и/или спецификация вычисления над открытым текстом для операции мультиплексирования 2:1 с незашифрованными операндами выглядит следующим образом:
Аналогично, характеристическое уравнение и/или спецификация вычисления над открытым текстом для операции мультиплексирования 3:1 с незашифрованными операндами выглядит следующим образом:
Для мультиплексора 4:1, показанного на фиг.8с, спецификация вычисления над открытым текстом для операции мультиплексирования 3:1 с незашифрованными операндами выглядит следующим образом:
Теперь получим спецификацию вычисления над шифрованным текстом из спецификации вычисления над открытым текстом путем замены управляющего сигнала в уравнениях 11-13 комбинацией зашифрованного управляющего сигнала и параметра шифрования.
В данном примере, алгоритмом шифрования является операция «исключающее ИЛИ» с ключом. Математическая комбинация зашифрованного управляющего сигнала и параметра шифрования, которая является обратной алгоритму шифрования, также является операцией «исключающее ИЛИ». Вставляя x′ XOR k в уравнение 11, получаем следующую спецификацию вычисления над шифрованным текстом для зашифрованного мультиплексора 2:1, причем несколько преобразований уже произведено для указания предпочтительной реализации обрабатывающего устройства: зашифрованного мультиплексора 3:1, причем несколько преобразований уже произведено для указания предпочтительной реализации обрабатывающего устройства:
Мультиплексор, показанный на фиг.8b, является мультиплексором 3:1, где управляющий сигнал содержит 2 бита x, y. Для простоты, предположим, что два бита x, у управляющего сигнала шифруются одним и тем же ключом для получения зашифрованных управляющих битов x′ и y′. Вставляя x′ XOR k и y′ XOR k, соответственно, в характеристическое уравнение (12) для незашифрованных операндов для мультиплексора 3:1, получаем следующую спецификацию вычисления над шифрованным текстом для зашифрованного мультиплексора 3:1, причем несколько преобразований уже произведено для указания предпочтительной реализации обрабатывающего устройства:
Аналогичный подход приводит к следующей спецификации вычисления над шифрованным текстом для мультиплексора 4:1, показанного на фиг.8с, причем эта спецификация вычисления над шифрованным текстом состоит из многих математических подопераций, указанных в уравнении (18):
Ниже со ссылкой на фиг.8d описана схемотехническая реализация спецификации вычисления, заданная уравнением (14), причем в качестве математических подопераций используются только операция И, операция ИЛИ и операция НЕ.
Схема зашифрованного мультиплексора, показанного на фиг.8d, включает в себя два входа 80, 81 для потоков данных a′, b′, которые зашифрованы и подлежат мультиплексированию. Обрабатывающее устройство мультиплексора, отвечающего изобретению, показанное на фиг.8d, дополнительно включает в себя вход 82 для зашифрованного управляющего сигнала, а также вход 83 для параметра шифрования k. Согласно уравнению (16), схема 4 содержит вентили И 84a, 84b, 84c, 84d, вентиль ИЛИ 85 и два инвертора 86a, 86b для создания инвертированной версии зашифрованного управляющего сигнала и инвертированной версии параметра шифрования, соответственно, которые входят в уравнение (16). Специалистам в данной области очевидно, что на фиг.8d представлена непосредственная схемотехническая реализация уравнения (16). Преобразовав уравнение (16) в соответствии с определенными математическими законами, можно получить другие реализации обрабатывающего устройства, аналогичного показанному на фиг.8d.
Все эти различные реализации имеют то общее, что они реализуют спецификацию вычисления, заданную уравнением (16) для мультиплексора 2:1, причем спецификация вычисления состоит из совокупности математических подопераций (84a-84d, 85, 86a, 86b), которые включают в себя, в качестве входных величин, только зашифрованный управляющий сигнал и параметр шифрования, но не управляющий сигнал в виде открытого текста.
Заметим, что мультиплексор представляет собой основной и часто незаменимый элемент многих электронных схем. Существуют разные варианты реализации мультиплексоров n-в-1, оптимизированные в отношении скорости, площади или топологии. Концепция изобретения позволяет значительно ограничить возможности осуществления атаки, в частности, тестирования посредством выводов, и атак стороннего канала, например, DPA (дифференциального анализа мощности) или SPA (простого анализа мощности). Согласно вышесказанному, в качестве метода шифрования используется принцип одноразовой набивки. Все N входных сигналов ai (i = 2,..., N), т.е. данные, подлежащие мультиплексированию, а также линии управления xn (n = 1... [log2N]; операция [x] означает наименьшее целое число, превышающее х), присутствуют в зашифрованном виде. Для шифрования предпочтительно использовать сложение по модулю 2 согласно шифру Вернама с непрерывно изменяющимся ключом ki, что соответствует операции «исключающее ИЛИ». Результат операции напрямую генерируется в пространстве шифрованного текста, без создания какого-либо промежуточного результата в пространстве открытого текста. Поток независимых и равномерно распределенных случайных битов для ключей обеспечивает полностью стохастический текущий профиль и стохастическую битовую комбинацию результата. Это в значительной мере затрудняет атаки SPA и DPA. Увеличение сложности/времени выполнения вследствие реализации мультиплексора, например, при сравнении уравнения (16) с уравнением (13), незначительно в отношении повышения безопасности.
Для обеспечения мультиплексора с n-битовыми входами на n-битовый выход, схему, показанную на фиг.8d, нужно повторить, например, для каждого бита для мультиплексора 2:1. Таким образом, на фиг.8d показана битовая секция для мультиплексора со входными сигналами, имеющая ширину более 1 бита.
Выше, со ссылкой на фиг.1-7b, были описаны, в частности, реализации вычислительного устройства, в которых оба операнда a, b, подлежащие связыванию посредством операции, зашифрованы одним и тем же ключом k. Предполагалось также, что результат также зашифрован этим ключом, что представлено характеристическими уравнениями и/или спецификациями вычисления, например, уравнениями (5) и (5а). В данном случае, вероятной целью атаки может быть генератор ключей, входящий в состав криптографического процессора. Одновременно перехватывая последовательность ключей, а также зашифрованный выходной поток данных, атакующий может вывести результат в виде открытого текста. Затратность такой атаки высока, поскольку, например, в случае 32-разрядного ЦП, чтобы добиться полного дешифрования, нужно одновременно отслеживать 64 бита. Чтобы, тем не менее, исключить эту локализованную точку атаки в виде генератора ключей, который также может быть деактивирован атакующим, предпочтительно, в ряде случаев, когда требуются высокие стандарты защищенности, использовать несколько разных алгоритмов шифрования или использовать один и тот же алгоритм шифрования, но разные ключи шифрования. Это, опять же, существенно повышает затраты, необходимые для осуществления успешной атаки.
Операнды для операции уже не шифруются одним и тем же ключом k, как показано, например, со ссылкой на фиг.2а, но операнды шифруются разными ключами. В данном случае, предпочтительно использовать отдельный ключ для каждого операнда, а именно, ключ i для операнда «а», ключ j для операнда «b». Также предпочтительно шифровать результат операции дополнительным ключом, который будем обозначать k. Ключ k, которым шифруется результат операции, можно выбирать независимо от i и j. Однако, предпочтительно использовать в качестве ключа k результат операции «исключающее ИЛИ» над ключами i и j.
Преимущество этого метода состоит в том, что перехвата отдельного потока ключей уже недостаточно для реконструкции выходного потока данных операции. Таким образом, порог атаки еще больше поднимается, тогда как затраты на оборудование возрастают незначительно. Использование нескольких независимых генераторов ключей дополнительно повышает защищенность в отношении криптоанализа, поскольку реальные генераторы ключей не могут генерировать независимые и равномерно распределенные случайные ключи. Кроме того, защищенность также повышается за счет того, что, при физической атаке с деактивацией генератора ключей, шифрование не полностью проваливается.
На фиг.9а-9с показаны три варианта вычислительного устройства (АЛУ), отвечающего изобретению, действующего как сумматор входных операндов a, b и имеющего дополнительный входной перенос cin, выходную сумму r и выходной перенос cout. В своей форме, показанной на фиг.9а-9с, вычислительное устройство, отвечающее изобретению, дополнительно содержит i, j для разных входов i, j параметров шифрования для различных ключей операндов a и b, соответственно.
Вычислительные устройства, показанные на фиг.9а-9с, также именуемые 1-битовыми полными сумматорами и работающие, в принципе, таким же образом, как описано со ссылкой на фиг.7а и 7b, не содержат входа для выходного ключа k, поскольку он задан, по определению, операцией «исключающее ИЛИ» ключей i и j. Это имеет то преимущество, что ключ k, который потребовался бы для дешифрования результата r, не появляется в явном виде и, поэтому, не может быть перехвачен в таком виде.
Согласно фиг.9а, входной перенос cin дополнительно шифруется ключом k, и выходной перенос cout также шифруется ключом k. Согласно фиг.9b, входной перенос cin шифруется тем же ключом, что и операнд «а», т.е. ключом i, тогда как выходной перенос шифруется ключом k. На фиг.9с показан еще один вариант, где входной перенос шифруется дополнительным ключом l, и выходной перенос также шифруется тем же дополнительным ключом l. Возможен также вариант с незашифрованным входным переносом или незашифрованным выходным переносом, хотя он и не изображен.
Нижеследующие уравнения шифрования применяются ко всем ключам:
Уравнения, обратные уравнениям шифрования уравнения (19), идентичны, поскольку, как уже было неоднократно указано, функция, обратная функции «исключающее ИЛИ», опять является функцией «исключающее ИЛИ».
Ниже приведен обзор логических операций, а также функций «сумма» (SUM) (бит суммы) и «перенос» (CARRY) (бит переноса) сумматора для версий, представленных на фиг.9а-9с:
Входы: операнды а(i), b(j), а также входной перенос cin(k)
Вспомогательные переменные: k=i⊕j, a'=a(i)⊕j, b'=b(j)⊕i
Логические операции:
Вариант фиг.9а: полный сумматор с суммой и выходным
переносом:
Вариант фиг.9b: полный сумматор с суммой и выходным переносом:
Вариант фиг.9c: полный сумматор с суммой и выходным переносом:
Ниже перечислены те канонические формы вышеописанных спецификаций вычисления над шифрованным текстом, которые могут быть реализованы непосредственно обрабатывающим устройством и которые могут включать в себя только математические подоперации, не имеющие данных открытого текста в качестве входных операндов. Ниже приведена спецификация вычисления для варианта полного сумматора (SUM, carry), показанного на фиг.9а. Преимущество этой спецификации вычислений состоит в том, что ключ k нигде не появляется в явном виде и, потому, не может быть перехвачен.
Специалисты в данной области могут легко вывести из уравнений (20)-(27) реализацию обрабатывающего устройства, причем здесь используются только математические подоперации, которые совместно дают спецификацию вычисления, которая является операцией И, операцией НЕ, операцией ИЛИ и операцией «исключающее ИЛИ».
Заметим также, что ключ k, которым шифруется результат r, получается в результате операции «исключающее ИЛИ» над i и j. Поэтому, обрабатывающее устройство вычислительного устройства, отвечающего изобретению, не имеет явного входа для ключа k.
На фиг.11а показана блок-схема криптографического процессора, отвечающего изобретению, который не содержит шифрования операнда (блока 822 и блока 824 на входе АЛУ 800) и результата шифрования (блока 826 на выходе АЛУ 800) в отличие от «незащищенного» криптографического процессора, показанного на фиг.10. АЛУ 800′ это вычислительное устройство для, по меньшей мере, одного зашифрованного операнда, осуществляющее операцию мультиплексирования, логическую операцию в соответствии с простой логической операцией, функцию 1-битового полного сумматора или алгоритма сложения с выборочным переносом и т.д., которые были объяснены выше или будут объяснены ниже.
Криптографический процессор, показанный на фиг.11а, включает в себя устройство 1100 шифрования/дешифрования, находящееся между внешней памятью 818 и кэшем 814 или, если кэш не предусмотрен, между внешней памятью 818 и шиной 808.
Согласно изобретению, предпочтительно шифровать данные в памяти посредством первого алгоритма шифрования, тогда как данные, передаваемые по шине 808 или хранящиеся в кэше 814, шифруются посредством второго алгоритма шифрования. Первый и второй алгоритмы шифрования, предпочтительно, отличаются друг от друга тем, что алгоритм шифрования, посредством которого зашифрованы данные, размещенные во внешней памяти 818, зашифрованы так называемым «жестким» алгоритмом шифрования, например, затратным криптоалгоритмом в виде, например, алгоритма DES или алгоритма AES. Второй алгоритм шифрования, посредством которого зашифрованы данные, размещенные в вычислительном устройстве 800′, отвечающем изобретению, предпочтительно, является «мягким» алгоритмом шифрования, который является малозатратным. Например, таким мягким алгоритмом шифрования является побитовая операция «исключающее ИЛИ» с ключом. В то время, как ключ для жесткого алгоритма шифрования никогда не меняется или меняется редко, ключ мягкого алгоритма шифрования меняется часто, или даже с каждым шифрованием, для достижения высокого уровня защищенности также для мягкого алгоритма шифрования.
На фиг.11b показано более подробное представление блока 1100, показанного на фиг.11а. В прямом пути передачи данных из памяти 818 на шину 808 или в кэш 814 сначала располагается устройство 1102 дешифрования DES, за которым следует устройство 1104 шифрования посредством «исключающего ИЛИ». Аналогично, в обратном пути передачи данных сначала располагается устройство 1106 дешифрования посредством «исключающего ИЛИ», за которым следует устройство 1108 шифрования DES. Таким образом, данные, сохраненные в памяти 818 посредством жесткого шифрования, первоначально дешифруются, а потом шифруются посредством второго (мягкого) алгоритма шифрования для подачи зашифрованных данных на АЛУ 800′. Результаты, полученные в АЛУ, при необходимости сохранения во внешней памяти 818, первоначально дешифруются согласно мягкому алгоритму шифрования (блок 1106), а потом шифруются согласно жесткому алгоритму шифрования (блок 1108).
Эта процедура гарантирует, что незашифрованные данные никуда не переносятся по шине в криптографическом процессоре. Единственно, где присутствуют незашифрованные данные, это между средствами 1102 и 1104 и между средствами 1106 и 1108, соответственно. Однако, это не шина связи, которую можно обнаружить и в дальнейшем перехватить с ограниченными затратами, в силу его широко распространенных структур.
Согласно изобретению, предпочтительно двухкаскадное шифрование, поскольку для данных, присутствующих во внешней памяти, требуется высокий уровень защищенности, которого можно добиться с помощью жесткого алгоритма шифрования. Однако, этот жесткий алгоритм шифрования привел бы к весьма затратной схеме, если бы АЛУ был приспособлен к этому жесткому алгоритму шифрования и, поэтому, привел бы к очень заметным потерям скорости, Поэтому предпочтительно переводить данные из жесткого алгоритма шифрования в мягкий алгоритм шифрования, чтобы структура АЛУ оставалась управляемой и имела разумную скорость вычисления, несмотря на оперирование зашифрованными данными.
Список обозначений
Вычислительное устройство и способ осуществления арифметической операции с зашифрованными операндами
Реферат
Изобретение относится к области вычислительной техники, а именно к вычислительным устройствам обработки данных. Техническим результатом является повышение уровня защиты обработки данных. Устройство имеет первый вход для подачи первого зашифрованного операнда, второй вход для второго зашифрованного операнда, третий вход для параметра шифрования и выход для зашифрованного результата операции. Также предложен сумматор с выборочным переносом для зашифрованных данных, криптографический процессор, обеспечивающий высокий уровень защиты от атак, способ выполнения операций над операндами, способ и устройство для формирования вычислительного устройства для выполнения операций над операндами. 6 н. и 31 з.п. ф-лы, 26 ил.
Формула
