способ и устройство для выполнения криптографического вычисления

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

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

/а/ случайно выбирают (11) два целых числа p₁' и p₂ ', сумма которых равна числу р';

/б/ решают (12), является ли указанное число р' простым числом, на основании комбинирования хранящегося в памяти простого числа Р с указанными числами p₁' и p₂';

/в/ если решают, что число р' является простым числом, числа p₁' и р₂' вводят (14) в запоминающее устройство электронного компонента; в противном случае повторяют этапы /а/ и /б/.

2. Способ по п.1, в котором определяют первое целое число p₁ и второе целое число р₂ таким образом, чтобы хранящееся в памяти простое число Р было равно сумме определенных целых чисел p₁ и р₂ ; и в котором этап /б/ осуществляют на основании операций, осуществляемых на числах p₁, p₂, p₁' и р₂'.

3. Способ по любому из предыдущих пунктов, в котором первое и второе целые числа p₁ и р₂ определяют случайно.

4. Способ по п.1, в котором этап /б/ осуществляют при помощи теста на простоту, основанного на комбинации теста типа Соловея-Страссена и теста типа Миллера-Рабина.

5. Способ по п.1, дополнительно содержащий перед этапом /б/ следующий этап:

/а1/ на основании операций, осуществленных с числами p₁' и р₂', проверяют, чтобы число р' не делилось на одно или несколько определенных простых чисел,

в котором повторяют этапы /а/ и /а1/, если число р' делится на одно из указанных определенных простых чисел.

6. Способ по п.5, в котором этап /а1/ содержит следующие этапы для простого числа у, строго превышающего 1:

случайно выбирают первое целое число с из целых чисел в диапазоне от 0 до y-1 и второе целое число d среди целых чисел в диапазоне от 1 до y-1;

определяют число u при помощи следующего уравнения:

u=c+dp₁'modulo y;

определяют число v при помощи следующего уравнения:

v=c-dp₂ 'modulo y;

определяют, делится ли р на y, в зависимости от разности между числом u и числом v.

7. Способ по п.1, в котором генерируют, по меньшей мере, два простых числа последовательно путем повторения этапов /а/-/с/ для создания пары асимметричных ключей.

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

9. Электронный компонент (21) генерирования ключа для определенного криптографического алгоритма, при этом указанный компонент содержит:

блок (22) выбора, выполненный с возможностью случайного выбора двух целых чисел p₁' и р₂', сумма которых является числом р';

запоминающее устройство (23) для запоминания простого числа Р и для запоминания чисел p ₁' и р₂', когда определяют, что сумма указанных чисел p₁' и р₂' является простым числом;

блок (24) решения, выполненный с возможностью решить, является ли число р' простым числом, на основании комбинации между хранящимся в памяти простым числом Р и указанными числами p₁' и р₂'.

10. Электронный компонент по п.9, в котором блок (22) выбора определяет первое целое число p₁ и второе целое число р₂ таким образом, чтобы хранящееся в памяти простое число Р было равно сумме указанных определенных целых чисел p₁ и р₂; и

в котором блок (23) решения может решить, является ли число р' целым числом, на основании операций, осуществленных на числах p₁, р₂, p ₁' и p₂'.

11. Электронный компонент по п.10, в котором блок (22) выбора определяет первое и второе целые числа p₁ и р₂ случайно.

12. Электронный компонент по п.9, в котором блок (23) решения применяет тест на простоту, основанный на комбинации теста типа Соловея-Страссена и теста типа Миллера-Рабина.

13. Электронный компонент по п.9, в котором блок (22) выбора производит предварительный контроль на основании операций, осуществленных на числах p ₁' и р₂', чтобы проверить, что число р' не делится на одно или несколько определенных простых чисел; и в котором блок (22) выбора повторяет случайный выбор двух целых чисел p₁' и р₂', если р' делится на определенное простое число.

14. Электронный компонент по п.9, в котором для осуществления предварительного контроля для простого числа у, строго превышающего 1, блок (22) выбора дополнительно содержит:

средства, выполненные с возможностью случайного выбора первого числа с среди целых чисел в диапазоне от 0 до y-1 и второго целого числа d среди целых чисел в диапазоне от 1 до y-1;

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

u=c+dp₁'modulo y;

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

v=c-dp₂'modulo y;

средства, выполненные с возможностью определения, делится ли р на y, в зависимости от разности между числом u и числом v.

15. Электронный компонент по п.9, в котором последовательно генерируют несколько простых чисел р'.

16. Электронный компонент по п.9, в котором криптографический алгоритм является алгоритмом типа RSA.

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

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

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

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

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

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

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

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

Так, известен метод шифрования с открытым ключом, называемый RSA по первым буквам фамилий его создателей Ривеста, Шамира, Адельмана. Этот метод является самым старым и самым распространенным в этой области.

Согласно этому методу выбирают четыре числа, обозначаемые р, q, e и d. Числа р и q являются двумя разными простыми числами. Их генерируют случайно.

Числа d и e проверяют следующее уравнение:

e*d=1 modulo(p-1)(q-1).

В этом случае можно использовать алгоритм Евклида для генерирования d на основании е, р и q при помощи расчетов, хорошо известных специалистам.

Затем число, полученное от произведения чисел р и q, обозначают n (модуль).

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

После этого для отправки данной, соответствующей целому числу М, находящемуся в пределах от 0 до n-1, вычисляют предназначенное для отправки соответствующее закодированное число С при помощи следующего уравнения:

С=M^e modulo n

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

D=C^d modulo n

После этого получают оригинальное незашифрованное сообщение М при помощи следующего уравнения:

D=M^de =М modulo n

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

В алгоритмах типа RSA отмечается, что модуль n принадлежит открытому ключу и может, таким образом, быть известен всем; тогда как число d должно оставаться секретным для обеспечения защиты алгоритма. Однако число d получают из чисел р и q. Следовательно, для защиты таких алгоритмов необходимо, чтобы числа р и q оставались секретными.

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

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

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

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

В настоящее время известны многие типы атак.

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

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

Известен метод генерирования чисел р и q, позволяющий сохранить эти числа в секрете. Действительно, в статье "Efficient Generation of Shared RSA keys", написанной Дэном Бонехом и Мэттью Франклином, предлагается генерировать числа р и q одновременно и секретно.

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

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

Действительно, в частности, случайно выбирают четыре целых числа р_а, p_b, q_a и q_b, при этом число р является результатом суммы числа р_а и числа p_b, а число q является результатом суммы числа q_a и числа q_b.

После этого проверяют, являются ли числа р и q простыми числами на основании их произведения, манипулируя числами р_а, p_b, q_a и q_b.

В случае, если числа р и q не являются простыми, повторяют случайный выбор двух других чисел р и q, пока выбранные числа р и q не будут определены как простые числа.

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

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

Первым объектом настоящего изобретения является способ генерирования ключа для криптографического алгоритма в электронном компоненте, в память которого вводят простое число Р.

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

/а/ случайно выбирают два целых числа p₁' и p ₂', сумма которых равна числу р';

/б/ определяют, является ли указанное число р' простым числом, на основании комбинирования хранящегося в памяти простого числа Р с указанными числами p₁' и р₂';

/в/ если решают, что число р' является простым числом, числа p₁' и р₂' вводят в запоминающее устройство электронного компонента; в противном случае повторяют этапы /а/ и /б/.

Благодаря этому отличительному признаку, можно секретно и эффективно генерировать простое число р'.

Действительно, генерированным таким образом числом р' не манипулируют напрямую в ходе различных этапов способа, а манипулируют только целыми числами p₁ ' и р₂'. Следовательно, исключается возможность взлома секрета числа р' путем атак на алгоритм во время этапа генерирования этого простого числа р'.

Кроме того, это генерирование простого числа является эффективным, так как оно позволяет последовательно генерировать несколько простых чисел. При этом более вероятным является случайный выбор одного простого числа, чем случайный выбор нескольких простых чисел одновременно, как это предлагается в статье "Efficient Generation of Shared RSA keys".

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

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

Как правило, такие тесты на простоту являются вероятностными алгоритмами. Они позволяют определить, является ли целое число простым числом, с очень высокой степенью вероятности.

В варианте выполнения настоящего изобретения определяют первое целое число p₁ и второе целое число р₂ таким образом, чтобы хранящееся в памяти простое число Р было равно сумме определенных целых чисел p₁ и p₂. В этом случае этап /б/ осуществляют на основании операций, осуществляемых на числах p₁, p₂, p₁' и p₂ '.

Так, во время генерирования секретного простого числа р' в фазе теста на простоту числа р' предпочтительно не манипулируют ни простым числом Р, ни числом р', что сводит на нет потенциальные атаки на секретность числа р' во время этого этапа генерирования.

Можно случайно определять первое и второе целые числа p₁ и p₂.

Этап /б/ можно осуществлять при помощи теста на простоту, основанного на комбинации теста типа Соловея-Страссена и теста типа Миллера-Рабина. Так, например, тест на простоту может быть основан на тесте на простоту, описанном в статье "Efficient Generation of Shared RSA keys" Дэна Бонеха и Мэттью Франклина в разделе 3 "Distributed Primality Test". Действительно, этот тест на простоту основан, с одной стороны, на тесте на простоту Соловея-Страссена и, с другой стороны, на тесте на простоту Рабина-Миллера. Тест на простоту Соловея-Страссена описан в документе Р.Соловея и В.Страссена "A fast monte carlo test for primality", 1977. Тест на простоту Рабина-Миллера описан в документе М.Рабина "Probabilistic algorithm for testing primality", 1980.

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

/а1/ на основании операций, осуществленных с числами p₁' и p₂', проверяют, чтобы число р' не делилось на одно или несколько определенных простых чисел.

В этом случае повторяют этапы /а/ и /а1/, если число р' делится на одно из определенных простых чисел.

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

В варианте выполнения настоящего изобретения этап /а1/ содержит следующие этапы для простого числа у, строго превышающего 1:

- случайно выбирают первое целое число с из целых чисел в диапазоне от 0 до y-1 и второе целое число d среди целых чисел в диапазоне от 1 до y-1;

- определяют число u при помощи следующего уравнения:

u=c+dp₁' modulo y;

- определяют число v при помощи следующего уравнения:

v=c-dp₂' modulo y;

- определяют, делится ли р на y, в зависимости от разности между числом u и числом v.

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

Вторым объектом настоящего изобретения является электронный компонент генерирования ключа для определенного криптографического алгоритма.

Компонент содержит:

- блок выбора, выполненный с возможностью случайного выбора двух целых чисел p₁' и р₂', сумма которых является числом р';

- запоминающее устройство для запоминания простого числа Р и для запоминания чисел p₁' и р₂', когда определяют, что сумма указанных чисел p₁' и p₂' является простым числом;

- блок решения, выполненный с возможностью решить, является ли число р' простым числом, на основании комбинации между хранящимся в памяти простым числом Р и указанными числами p₁' и р₂'.

Блок выбора может определить первое целое число p₁ и второе целое число р₂ таким образом, чтобы хранящееся в памяти простое число Р было равно сумме указанных определенных целых чисел p₁ и р₂; и блок решения может решить, является ли число р' целым числом на основании операций, осуществленных на числах p₁, р₂, p ₁' и р₂'.

В варианте выполнения настоящего изобретения блок выбора определяет первое и второе целые числа p₁ и р₂ случайно.

Предпочтительно блок решения применяет тест на простоту, основанный на комбинации теста типа Соловея-Страссена и теста типа Миллера-Рабина и предложенный в статье "Efficient Generation of Shared RSA keys".

Предпочтительно блок выбора производит предварительный контроль на основании операций, осуществленных на числах p₁' и р₂', чтобы проверить, что число р' не делится на одно или несколько определенных простых чисел.

В этом случае блок выбора повторяет случайный выбор двух целых чисел p₁ ' и р₂', если р' делится на определенное простое число.

В варианте выполнения настоящего изобретения для осуществления предварительного контроля относительно простого числа y, строго превышающего 1, блок выбора дополнительно содержит:

- средства, выполненные с возможностью случайного выбора первого числа с среди целых чисел в диапазоне от 0 до y-1 и второго целого числа d среди целых чисел в диапазоне от 1 до y-1;

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

u=c+dp₁' modulo y;

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

v=c-dp₂' modulo y;

- средства, выполненные с возможностью определения, делится ли р на y, в зависимости от разности между числом u и числом v.

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

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

Фиг.1 - основные этапы способа генерирования ключа согласно варианту выполнения настоящего изобретения.

Фиг.2 - схема электронного компонента согласно варианту выполнения настоящего изобретения.

В варианте выполнения настоящего изобретения способ генерирования ключа для криптографического алгоритма предназначен для его применения в электронном компоненте.

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

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

На этапе 11 производят случайный выбор двух целых чисел, обозначаемых p₁' и р₂'. Затем на этапе 12 решают, является ли простым числом сумма, обозначенная р', этих двух выбранных чисел. Этот этап осуществляют таким образом, чтобы сохранять в секрете число р'. Так, предпочтительно на этом этапе числом р' как таковым не манипулируют. Определение простоты числа р' осуществляют при помощи операций, производимых на числах p ₁' и р₂'.

После этого на этапе 13, если определено, что число р' не является простым числом, повторяют предыдущие этапы 11 и 12.

Если же, наоборот, обнаруживается, что это число является простым числом, то в этом случае числа p₁' и р₂ ' вводятся в память.

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

На этапе 12 можно применить любой тест на простоту, который позволяет решить, является ли число комбинацией из двух простых чисел, поскольку этот тест не содержит операций, которые могут поставить под угрозу секретность одного из этих двух чисел произведения. Такие тесты на простоту хорошо известны и легко доступны специалистам. Предпочтительно эти тесты на простоту могут позволить решить на основании произведения n простого числа Р и числа р', являющегося результатом суммы случайно выбранных чисел p₁' и р₂', является ли число р' простым числом. Этот тест содержит операции на числах p₁' и р₂', но не содержит операций, производимых непосредственно на числе р'.

Так, например, тест на простоту может быть основан на комбинации теста типа Соловея-Страссена и теста типа Миллера-Рабина, как было предложено в статье "Efficient Generation of Shared RSA keys".

В этом случае Р представляют в виде двух чисел, обозначаемых p₁ и р₂. Это разложение можно осуществить случайно или произвольно.

Этот тест позволяет решить, является ли число m произведением двух простых чисел Р и р', где m отвечает уравнению:

m=(p₁+р₂)*(p₁'+р₂ ')

где

Р=p₁+р ₂

и

p'=p₁ '+р₂'.

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

Отмечается, что в таком варианте числом m можно манипулировать без всякого опасения, так как оно не является секретным.

Как детально описано в статье "Efficient Generation of Shared RSA keys", в этом тесте предполагается, что различные числа отвечают следующим характеристикам:

p₁=3 mod 4

и

p ₁'=3 mod 4

затем

р ₂=0 mod 4

и

р₂ '=0 mod 4

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

В первую очередь, случайно выбирают числа а среди целых чисел от 1 до m-1.

После этого вычисляют символ Якоби относительно выбранного таким образом числа m, обозначаемый (a/m).

Затем, если вычисленный таким образом символ Якоби отличается от 1, повторяют этап случайного выбора числа а.

Если символ Якоби равен 1, переходят в следующему этапу,

В этом случае производят первый промежуточный расчет на числах m, p₁ и p₂' и получают число u, отвечающее следующему уравнению:

После этого производят второй промежуточный расчет на числах m, p₁ и p₂ и получают число v, отвечающее следующему уравнению:

После этого проверяют, выполняется ли следующее уравнение:

u=+/-v mod m

Если это уравнение верно, делают вывод, что m является произведением двух целых чисел Р и р' с определенной вероятностью.

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

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

Таким образом, можно рассмотреть набор простых чисел. Затем перед этапом 12 требуется определить, делится ли число р' на простое число, обозначенное у. Для этого случайно выбирают целое число с среди целых чисел от 0 до у-1 и целое число d среди целых чисел от 1 до у-1.

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

u=с+dp₁' modulo y

v=с-dp₂' modulo y

В этом случае можно проверить, выполняется ли следующее уравнение:

u-v=0 modulo y

Если это уравнение верно, делают вывод, что число р' делится на у.

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

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

Он дополнительно содержит запоминающее устройство 23 для введения в память простого числа Р и чисел p₁' и p₂', если решают, что сумма этих чисел p₁' и p₂ ' является простым числом.

Он содержит также блок решения, выполненный с возможностью решения, является ли число р' простым числом на основании комбинации введенного в память простого числа Р с числами p₁' и p ₂'.

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