СПОСОБ И УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ КРИПТОГРАФИЧЕСКОГО ВЫЧИСЛЕНИЯ Российский патент 2009 года по МПК H04L9/06 

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

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

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

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

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

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

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

Вместе с тем после каждой из этих операций имеет смысл извлечь немаскированные промежуточные данные путем «демаскирования» данных. Легче демаскировать промежуточные данные, полученные в результате линейной операции. Действительно, линейную операцию L, производимую на данных х, маскированных при помощи единицы или исключения со случайной маской m, можно записать следующим образом:

L(х⊕m)=L(x)⊕L(m).

Таким образом, зная m, можно легко демаскировать L(х⊕m), чтобы получить L(х).

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

F(x⊕m)=F(x)⊕F(m).

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

Известны алгоритмы шифрования, в которых используются нелинейные операции, такие как алгоритмы DES от "Data Encryption Standard" или алгоритм AES от "Advanced Encryption Standard". Было предложено несколько способов защиты алгоритма AES при помощи маскирования.

В таких алгоритмах нелинейные операции, как правило, осуществляют в виде таблиц замещения. Так, нелинейную операцию, соответствующую таблице замещения tab[i], применяемой к данным х, можно записать в следующем виде:

у=tab[x].

В этом случае защита маскированием требует спонтанного генерирования случайно маскированных таблиц. Так, маскированную нелинейную операцию, соответствующую маскированной таблице замещения tab'[i], применяемой к данным х, маскированной случайной маской ml, можно записать в следующем виде:

y=tab'[x⊕m1]=y⊕m2

Чтобы иметь возможность демаскировать полученные таким образом данные у', применяют сохранение в памяти маскированных таблиц. Способы защиты такого типа были предложены для алгоритма шифрования DES в документе авторов Louis Goubin и Jacques Patarin "DES and Differential Power Analysis - The "Duplication" Methode" в Cetin Кауа Кос and Christof Paar, editors, Proceedings of CHES'99, том 1717 "Lectures Notes in Computer Science", стр.158-172, Springer-Verlag, 2000, а также в патенте FR 2802741 «Устройство для применения алгоритма поблочного шифрования с повторением раундов».

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

Например, нелинейная операция AES может быть осуществлена с использованием таблицы замещения размером 256 байт. Одновременное шифрование 16 байт сообщения требует наличия в памяти 16 маскированных таблиц замещения на 256 байт каждая. Следовательно, размер памяти, необходимый для маскирования осуществляемой таким образом нелинейной операции, должен составлять 4 кбайт.

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

Известен также документ "Provably Secure Masking of AES", Johannes Blomer, Guajardo Merchan, Volker Krummel, опубликованный 30.04.04, и документ "Secure and Efficient Masking of AES - A Mission Impossible" версия 1, E.Oswald, Stephan Mangard, Norbert Pramstaller, 4 июня 2004 г., в котором предложено осуществлять нелинейную операцию алгоритма AES в конечном поле GF(4).

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

Вместе с тем, такой способ маскирования AES предполагает осуществлять нелинейные операции в GF(4) и, следовательно, обрабатывать биты попарно.

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

Таким образом, эффективную реализацию алгоритма шифрования с обработкой бит попарно сложно производить на 8, 16, 32 и даже 64-разрядных микропроцессорах.

Настоящее изобретение призвано предложить решение для устранения этих недостатков.

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

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

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

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

Таким образом, можно реализовать нелинейную операцию, точно определенную для блоков данных размером k, на блоках данных размером j, генерируя несколько промежуточных блоков данных размером j, при этом размер выражается в битах, на основании блока данных размером k. После обработки промежуточных блоков данных и, в частности, применения нелинейной операции объединяют полученные таким образом блоки данных, чтобы получить блок данных размером k, соответствующий преобразованию исходного блока данных. Это преобразование включает точно определенную нелинейную операцию. Оно может также включать другие операции алгоритма. Действительно, может быть более предпочтительным осуществлять другие операции алгоритма на j-битовых блоках данных, чем на k-битовых блоках данных, прежде чем объединять эти блоки, чтобы снова получить k-битовый блок данных.

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

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

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

В варианте выполнения настоящего изобретения этап генерирования содержит операцию разложения (Т), состоящую в разложении k-битовых блоков данных (а) на j-битовые блоки данных (b, с), и этап объединения содержит обратную операцию разложения (Т^-1), состоящую в создании k-битового блока данных (а') на основании j-битовых блоков данных (В, С).

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

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

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

На фиг.2 показан такой вариант выполнения, применяемый для алгоритма типа AES. Так, предназначенный для шифрования блок данных 201 размером k разбивают при помощи операции разложения Т на несколько предназначенных для шифрования промежуточных блоков данных (202) размером j. В этом случае для промежуточных блоков данных размером j применяют операции, защищенные маскированием (203), эквивалентные операциям алгоритма AES, точно определенным для блоков данных размером k. Получают зашифрованные промежуточные блоки данных 204. Затем применяют обратную операцию разложения Т^-1 для получения зашифрованного блока данных 206 размером k. Таким образом, этот вариант выполнения требует изменения операций алгоритма, чтобы их можно было применять для промежуточных блоков данных.

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

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

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

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

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

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

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

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

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

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

- средства генерирования нескольких j-битовых маскированных блоков на основании исходного k-битового блока данных, при этом j является целым числом меньше k;

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

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

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

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

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

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

Изобретение будет более понятно при рассмотрении прилагаемых чертежей, на которых:

фиг.1 иллюстрирует способ защиты алгоритма шифрования согласно варианту выполнения настоящего изобретения;

фиг.2 иллюстрирует способ защиты алгоритма шифрования типа AES согласно варианту выполнения настоящего изобретения.

В варианте выполнения настоящего изобретения используют хорошо известные математические свойства конечных полей (или полей Галуа, Galois Fields (GF)), чтобы на основании исходного блока данных размером k генерировать несколько блоков данных размером строго меньше k. В описании представлен вариант выполнения настоящего изобретения для защиты путем маскирования алгоритма шифрования типа AES, использующего на входе сообщение, состоящее из 16 байт, при этом каждый из байт обрабатывают путем повторения раундов, каждый из которых содержит последовательность линейных операций и, по меньшей мере, одну нелинейную операцию. Изобретение касается и других типов алгоритма шифрования, содержащих, по меньшей мере, одну нелинейную операцию, независимо от того, осуществляется ли он с повторением раундов или нет.

В алгоритме типа AES нелинейная операция соответствует мультипликативной инверсии для ненулевых элементов в конечном поле GF(2⁸). Таким образом, чтобы на основании одного блока данных генерировать несколько промежуточных блоков данных строго меньшего размера, в варианте выполнения настоящего изобретения предлагается транспонировать нелинейную операцию из поля GF(2⁸) на поле GF((2⁴)²).

Известен документ авторов Tsing-Fu Ling, Chih-Pin Su, Chih-Tsun Huang и Cheng-Wen Wu "A high-throuhput low-cost AES cipher chip", а также документ Vincent Rijmen "Efficient implementation of the Rijndael S-box" и документ Atri Rudra, Pradeep K.Dubey, Charanjit S.Jutia, Vijay Kurmar, Josyula R.Rao и Pankaj Rohatgi "Efficient Rijndael Encryption Implementation with Composite Field Arithmetic", затем документ R.W.Ward и T.C.A.Molteno "Efficient hardware calculation of inversion in GF(2⁸)", в которых показывается, как нелинейная операция алгоритма AES может быть транспонирована в сложное поле GF((2⁴)²) и как такое транспонирование позволяет улучшить эффективность алгоритма шифрования.

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

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

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

- линейную операцию, классически обозначаемую ShiftRows, соответствующую перемещению, применяемому для 16 байт;

- линейную операцию, классически обозначаемую MixColumns, применяемую для 16 байт.

Операция SubBytes алгоритма AES содержит нелинейную операцию, которая в конечном поле GF(2⁸) для ненулевых элементов соответствует мультипликативной инверсии. Такую операцию можно транспонировать в сложное поле GF((2⁴)²) таким образом, чтобы обрабатывать блоки данных размером 4 бит перед реализацией обратной операции преобразования Т^-1 для других операций обработки байт.

Выбирают отображение GF(2⁴) и следующий полином поля:

Р(х)=х²+Dx+Е;

при этом D и Е являются элементами конечного поля GF(2⁴), таким образом, можно записать:

GF(2⁸)≅GF(2⁴)[x]/P(x)

На фиг.1 показан вариант выполнения настоящего изобретения.

Конструируют операцию 102 разложения Т, которая записывается следующим образом:

Т(а)=bx+с;

где а является элементом GF(2⁸), (bx+с) является элементом GF((2⁴)²), a b и с являются элементами конечного поля GF(2⁴).

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

Эту операцию разложения можно осуществить в виде умножения с матрицей 8×8.

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

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

Настоящее изобретение охватывает варианты выполнения, независимо от этапа алгоритма, на котором реализуют эту операцию разложения.

После осуществления нелинейной операции с использованием таблицы замещения можно реализовать обратную операцию разложения Т^-1 для возвращения в конечное поле GF(2⁸) и новой обработки байт.

Настоящее изобретение охватывает варианты выполнения независимо от этапа алгоритма, на котором реализуют эту обратную операцию разложения.

В зависимости от этапов, на которых реализуют операцию разложения Т и обратную операцию разложения Т^-1, к конечному полю GF((2⁴)²) адаптируют другие операции алгоритма, определенные в GF(2⁸).

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

GF((2⁴)²). В этом случае операции алгоритма шифрования заменяют их эквивалентами в конечном поле GF((2⁴)²).

В варианте выполнения настоящего изобретения производят маскирование 103, по меньшей мере, промежуточных блоков данных, обработанных в момент нелинейной операции, по меньшей мере, для первого раунда и последнего раунда алгоритма AES, что будет подробнее показано далее. Изобретение охватывает также вариант выполнения, в котором промежуточные блоки, обработанные в момент нелинейной операции, маскируют для всех раундов алгоритма, а также вариант выполнения, в котором маскируют все или часть промежуточных блоков, обработанных во время исполнения алгоритма, независимо от того, являются ли эти блоки данных элементами GF(2⁸) или элементами GF((2⁴)²).

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

В конечном поле GF((2⁴)²) инверсию элемента (bx+с) можно записать в следующем виде:

(bx+с)^-1=bΔ^-1х+(с+bD)Δ^-1;

где Δ=b²E+bcD+с².

Таким образом, первая нелинейная операция мультипликативной инверсии конечного поля GF(2⁸), транспонированная в конечное поле GF((2⁴)²), соответствует умножениям, сложениям и нелинейной операции мультипликативной инверсии. Эта нелинейная операция в конечном поле GF((2⁴)2) может быть осуществлена при помощи таблицы замещения 4 бит на 4 бит, занимающей 8 байт.

Как было указано выше, требуется маскировать обработанные таким образом блоки данных. Маскирование сложений хорошо известно.

Чтобы маскировать умножения, вводят алгоритм 104 маскированного умножения М(х, у, z). В дальнейшем элементы m1, m2, m3, n, n', n1, n2 являются случайными масками. Такой алгоритм на входе использует:

- маскированные элементы GF(2⁴), (b⊕m1) и (с⊕m2);

- маску m3.

Такой алгоритм на выходе выдает маскированное произведение в виде:

bc⊕m3.

Можно записать следующие этапы:

u=(b⊕m1)(c⊕m2)=bc⊕bm2⊕cm1⊕m1m2

v=(с⊕m2)m1=cm1⊕m1m2

w=(b⊕m1)m2=bm2⊕m1m2

M(b⊕m1,с⊕m2,m3)=u⊕v⊕wm1m2⊕m3=bc⊕m3

В варианте выполнения настоящего изобретения маскируют первые промежуточные блоки данных. Таким образом, получают первое маскированное разложение, которое записывается в следующем виде:

(b⊕m1)x+(с⊕m2).

Затем используют алгоритм маскированного умножения для вычисления маскированного умножения в следующем виде:

М(b⊕m1,с⊕m2,m3)=bc⊕m3.

Затем на этапе 105 точно так же вычисляют следующие произведения для получения маскированного блока данных Δ:

р=(bc⊕m3)D=bcD⊕m3D;

q=(b⊕m1)²E=b²E⊕m1²E;

r=(с⊕m2)²=с²⊕m2².

В результате получают следующее уравнение:

р⊕q⊕r⊕m1²E⊕m2²⊕m3D⊕n=Δ⊕n.

Таким образом, в конечном поле GF(2⁴) путем сложения и умножения получают маскированный блок данных Δ⊕n, к которому применяют нелинейную операцию мультипликативной инверсии.

В варианте выполнения настоящего изобретения эту нелинейную операцию осуществляют на маскированном блоке данных, используя на этапе 106 таблицу замещения tab(x), проверяя следующее уравнение:

tab[x⊕n]=х^-1⊕n'.

Таким образом, эта маскированная таблица замещения позволяет получить инверсию маскированного блока данных, то есть Δ^-1⊕n'.

Применяя алгоритм маскированного умножения, вычисляют:

- М(b⊕m1,Δ^-1⊕n',n1)=bΔ^-1⊕n1=В;

- M(bD+с)⊕(m1D+m2),Δ^-1⊕n',n2)=(bD+с),Δ^-1⊕n2=С.

Таким образом, путем объединения 108 маскированных блоков данных b⊕m1, с⊕m2 и Δ^-1⊕n' получают Вх+С.

Таким образом, получают маскированное значение (bx+с)^-1, причем не обрабатывая для реализации этой нелинейной операции немаскированные блоки данных b, с и Δ.

Затем выполняют обратную операцию 109 разложения Т^-1 для получения элемента 110:

а'=T^-1(Вх+С).

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

Предпочтительно нелинейную операцию транспонируют из конечного поля GF(2⁸) в конечное поле GF((2⁴)²), в котором нелинейная операция соответствует комбинации сложений, умножений и эквивалентной нелинейной операции в поле с меньшим числом элементов.

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

Изобретение относится к области криптографии. Технический результат заключается в уменьшении требуемой памяти для выполнения шифрования. Сущность изобретения заключается в том, что криптографическое вычисление осуществляют в электронном компоненте согласно определенному криптографическому алгоритму, включающему, по меньшей мере, одну точно определенную нелинейную операцию на k-битовых блоках данных, при этом k является целым числом больше 2. Генерируют несколько промежуточных маскированных блоков данных из j бит (b⊕m, с⊕m2, Δ⊕n) на основании исходного блока данных (а) из k бит, при этом j является целым числом, меньшим k. Затем производят нелинейную операцию S, по меньшей мере, на одном j-битовом маскированном промежуточном блоке данных (Δ⊕n) при помощи таблицы замещения (106) с 2^j входами, получая j-битовый измененный блок данных (S(Δ)⊕n). Измененный j-битовый блок данных объединяют, по меньшей мере, с некоторыми из указанных j-битовых маскированных промежуточных блоков данных в один итоговый k-битовый блок (а'), соответствующий исходному k-битовому блоку данных, через преобразование, включающее указанную точно определенную нелинейную операцию. 2 н. и 17 з.п. ф-лы, 2 ил.

1. Способ выполнения криптографического расчета в электронном компоненте согласно определенному криптографическому алгоритму, включающему, по меньшей мере, одну точно определенную нелинейную операцию на блоках данных из k бит, при этом k является целым числом, превышающим 2, при этом способ содержит следующие этапы:
генерируют несколько промежуточных маскированных блоков данных из j бит (b⊕m, c⊕m2, Δ⊕n) на основании исходного блока данных из k бит, при этом j является целым числом, меньшим k;
производят нелинейную операцию S, соответствующую указанной точно определенной нелинейной операции, по меньшей мере, на одном j-битовом маскированном промежуточном блоке данных (Δ⊕n) при помощи таблицы замещения (106) с 2^j входами, получая j-битовый измененный блок данных (S(Δ)⊕n);
измененный j-битовый блок данных объединяют, по меньшей мере, с некоторыми из указанных j-битовых маскированных промежуточных блоков данных в один итоговый k-битовый блок (а'), соответствующий исходному k-битовому блоку данных, через преобразование, включающее указанную точно определенную нелинейную операцию.

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

3. Способ по п.1, в котором промежуточные блоки данных маскируют (103) перед применением нелинейной операции.

4. Способ по п.1, в котором этап генерирования содержит операцию разложения (Т), состоящую в разложении k-битового блока данных на j-битовые блоки данных (b, с), и этап объединения содержит обратную операцию разложения (Т^-1), состоящую в составлении k-битового блока данных на основании j-битовых блоков данных (В, С) в k-битовый блок данных (а').

5. Способ по п.4, в котором криптографическое вычисление алгоритма дополнительно включает, по меньшей мере, одну линейную операцию, и согласно которому маскированную линейную операцию осуществляют перед операцией разложения (Т) или после обратной операции разложения (Т^-1).

6. Способ по п.4, в котором криптографическое вычисление алгоритма дополнительно включает линейную операцию, и согласно которому указанную маскированную линейную операцию осуществляют после операции разложения (Т) и перед обратной операцией разложения (Т^-1).

7. Способ по п.4, в котором операцию разложения (Т) применяют в начале криптографического алгоритма и обратную операцию разложения (Т^-1) - в конце криптографического алгоритма.

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

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

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

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

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

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

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

15. Способ по п.12, в котором таблицу замещения генерируют перед каждой маскированной нелинейной операцией.

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

17. Способ по п.1, в котором криптографический алгоритм является алгоритмом AES.

18. Электронный компонент, предназначенный для криптографического вычисления согласно определенному криптографическому алгоритму, включающему, по меньшей мере, одну точно определенную нелинейную операцию на k-битовых блоках данных, при этом к является целым числом больше 2, при этом компонент содержит
средства генерирования нескольких j-битовых маскированных блоков на основании исходного k-битового блока данных, при этом j меньше k;
средства применения нелинейной операции S, соответствующей указанной точно определенной нелинейной операции, по меньшей мере, для одного из j-битовых маскированных блоков при помощи таблицы замещения с 2^j входами с последующим получением измененного j-битового блока;
средства объединения измененного j-битового блока и, по меньшей мере, некоторых из указанных j-битовых маскированных блоков в один итоговый k-битовый блок, соответствующий исходному k-битовому блоку данных, через преобразование, включающее указанную точно определенную нелинейную операцию.

19. Электронный компонент по п.18, в котором криптографический алгоритм является алгоритмом AES.