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

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

1. Криптографический способ, осуществляемый в чип-карте и заключающийся в том, что

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

Е=x^d(mod p·q),

где d и mod p·q являются компонентами секретного ключа, причем р представляет собой первый простой множитель, q представляет собой второй простой множитель, d представляет собой показатель степени, а х представляет собой основание, при этом

б) для выполнения операции модульного возведения в степень выбирают два натуральных числа r и s при условии, что величины d и (kgV(r, s)) являются взаимно простыми, и выполняют следующие этапы вычислений:

x₁=x(mod р·r),

х₂=x(mod q·s),

d_1=d(mod (р·r)),

d_2=d(mod )(q·s)),

где () представляет собой функцию Эйлера, a kgV(r, s) является наименьшим общим кратным для чисел r и s, после чего

в) в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляют число z по формулам

z=z₁(mod р·r) и z=z₂(mod q·s),

г) вычисляют результат операции Е возведения в степень путем сокращения z по модулю p·q,

д) ранее вычисленное число z и тем самым результат операции Е возведения в степень проверяют на этапе контроля на наличие вычислительных ошибок, при этом

е) указанный этап контроля заключается в выполнении следующих вычислительных операций:

е1) вычисление наименьшего возможного натурального числа е, удовлетворяющего условию e·d=1(mod (kgV(r, s))), с помощью расширенного алгоритма Евклида,

е2) вычисление значения С=z^e(mod kgV(r, s)),

e3) сравнение между собой значений х и С по модулю kgV(r, s), при этом результат операции Е модульного возведения в степень отбрасывается как ошибочный, если х C(mod kgV(r, s)).

2. Криптографический способ, осуществляемый в чип-карте и заключающийся в том, что

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

Е=x^d(mod p·q),

где d и mod p·q являются компонентами секретного ключа, причем р представляет собой первый простой множитель, q представляет собой второй простой множитель, d представляет собой показатель степени, а х представляет собой основание, при этом

б) для выполнения операции модульного возведения в степень выбирают два натуральных числа r и s, а также два числа b₁ и b₂ из интервала [1, ..., r-1], соответственно [1, ..., s-1], являющихся взаимно простыми по отношению к числам r и s соответственно, причем эти числа b₁ и b ₂ удовлетворяют условию b₁=b₂(mod ggT(r, s)), где ggT(r, s) представляет собой наибольший общий делитель для чисел r и s,

в) с помощью обоих этих чисел b₁ и b₂ в соответствии с китайской теоремой об остатках вычисляют числа x₁ и х₂, которые удовлетворяют следующим условиям:

x₁=x(mod р), x₁=b₁(mod r),

x₂=x(mod q), x₂=b₂(mod s),

после чего выполняют следующие этапы вычислений:

d_1=d(mod (р)),

d_2=d(mod (q)),

где () представляет собой функцию Эйлера, a kgV(r, s) представляет собой наименьшее общее кратное для чисел r и s, после чего

г) в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляют число z по формулам

z=z₁(mod р·r) и z=z₂(mod q·s),

д) вычисляют результат операции Е возведения в степень путем сокращения z по модулю p·q,

е) ранее вычисленное число z (а тем самым автоматически и результат операции Е возведения в степень) проверяют на этапе контроля на наличие вычислительных ошибок, при этом

ж) указанный этап контроля заключается в выполнении следующих вычислительных операций:

ж1) вычисление чисел

причем до выполнения операции модульного возведения в степень по модулю (r), соответственно (s) сокращают d_1 и d_2,

ж2) сравнение между собой значений z₁ и C₁ по модулю r, а также z ₂ и C₂ по модулю s, при этом результат операции Е модульного возведения в степень отбрасывается как ошибочный, если C₁ z₁mod r или С₂ z₂mod s.

3. Способ по п.2, отличающийся тем, что числа r и s являются нечетными.

4. Способ по любому из пп.1-3, отличающийся тем, что числа r и s выбирают из интервала [0, 2^k-1], где 16 k 32.

5. Способ по любому из пп.1-3, отличающийся тем, что по меньшей мере одно из чисел r и s выбирают таким образом, чтобы в двоичном представлении произведения р·r, соответственно q·s присутствовало максимально большое количество ведущих единиц.

6. Способ по п.5, отличающийся тем, что

а) сначала на первом подэтапе по меньшей мере для одного из чисел r и s выбирают соответствующее оптимальное число r_опт , соответственно s_опт, не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирают по соседнему значению r=r_опт -i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

7. Способ по п.5, отличающийся тем, что

а) на первом подэтапе для каждого из чисел r и s выбирают соответствующее оптимальное число r _опт, соответственно s_опт, не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирают по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

8. Способ по п.5, отличающийся тем, что

а) сначала на первом подэтапе выбирают по меньшей мере одно из чисел r_опт и s_опт , не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми,

б) на втором подэтапе выбирают по соседнему значению r=r_опт-i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми, при условии, что такое значение существует для i=0, 1, ..., k, и

в) на третьем подэтапе в том случае, если на втором подэтапе не было выбрано ни одного значения, выбирают по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

9. Способ по любому из пп.1-3, отличающийся тем, что оба числа r и s выбирают таким образом, чтобы в двоичном представлении произведения р·r и произведения q·s присутствовало максимально большое количество ведущих единиц.

10. Способ по п.9, отличающийся тем, что

а) сначала на первом подэтапе по меньшей мере для одного из чисел r и s выбирают соответствующее оптимальное число r _опт, соответственно s_опт, не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирают по соседнему значению r=r_опт -i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

11. Способ по п.9, отличающийся тем, что а) на первом подэтапе для каждого из чисел r и s выбирают соответствующее оптимальное число r _опт, соответственно s_опт, не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирают по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

12. Способ по п.9, отличающийся тем, что

а) сначала на первом подэтапе выбирают по меньшей мере одно из чисел r_опт и s _опт, не ограничивая такой выбор условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми,

б) на втором подэтапе выбирают по соседнему значению r=r_опт-i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми, при условии, что такое значение существует для i=0, 1, ..., k, и

в) на третьем подэтапе в том случае, если на втором подэтапе не было выбрано ни одного значения, выбирают по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

13. Способ по любому из пп.1-3, отличающийся тем, что криптографический способ предусматривает выполнение алгоритма Райвеста-Шамира-Адлемана.

14. Способ по любому из пп.1-3, отличающийся тем, что криптографический способ предусматривает выполнение алгоритма цифровой подписи Рабина.

15. Способ по любому из пп.1-3, отличающийся тем, что криптографический способ предусматривает выполнение алгоритма идентификации Фиата-Шамира.

16. Чип-карта, имеющая по меньшей мере одно вычислительное устройство, обеспечивающее

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

Е=x^d(mod p·q),

где d и mod p·q являются компонентами секретного ключа, причем р представляет собой первый простой множитель, q представляет собой второй простой множитель, d представляет собой показатель степени, а х представляет собой основание, при этом

б) для выполнения операции модульного возведения в степень выбираются два натуральных числа r и s при условии, что величины d и (kgV(r, s)) являются взаимно простыми, и выполняются следующие этапы вычислений:

x₁=x(mod p·r),

x₂=x(mod q·s),

d_1=d(mod (р·r)),

d_2=d(mod (q·s)),

где () представляет собой функцию Эйлера, a kgV(r, s) является наименьшим общим кратным для чисел r и s, после чего

в) в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляется число z по формулам

z=z₁(mod p·r) и z=z₂ (mod q·s),

г) вычисляется результат операции Е возведения в степень путем сокращения z по модулю p·q,

д) ранее вычисленное число z (а тем самым автоматически и результат операции Е возведения в степень) проверяется на этапе контроля на наличие вычислительных ошибок, при этом

е) указанный этап контроля заключается в выполнении следующих вычислительных операций:

е1) вычисление наименьшего возможного натурального числа е, удовлетворяющего условию e·d=1(mod (kgV(r, s))), с помощью расширенного алгоритма Евклида,

е2) вычисление значения С=z^e(mod kgV(r, s)),

е3) сравнение между собой значений х и С по модулю kgV(r, s), при этом результат операции Е модульного возведения в степень отбрасывается как ошибочный, если х C(mod kgV(r, s)).

17. Чип-карта, имеющая по меньшей мере одно вычислительное устройство, обеспечивающее

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

Е=x^d(mod p·q),

где d и mod p·q являются компонентами секретного ключа, причем р представляет собой первый простой множитель, q представляет собой второй простой множитель, d представляет собой показатель степени, а х представляет собой основание, при этом

б) для выполнения операции модульного возведения в степень выбираются два натуральных числа r и s, а также два числа b₁ и b₂ из интервала [1, ..., r-1], соответственно [1, ..., s-1], являющихся взаимно простыми по отношению к числам r и s соответственно, причем эти числа b₁ и b ₂ удовлетворяют условию b₁=b₂(mod ggT(r, s)), где ggT(r, s) представляет собой наибольший общий делитель для чисел r и s,

в) с помощью обоих этих чисел b₁ и b₂ в соответствии с китайской теоремой об остатках вычисляются числа x₁ и x₂, которые удовлетворяют следующим условиям:

x₁ =x(mod р), x₁=b₁(mod r),

x₂ =x(mod q), x₂=b₂(mod s),

после чего выполняются следующие этапы вычислений:

d_1=d(mod (p)),

d_2=d(mod (q)),

где () представляет собой функцию Эйлера, a kgV(r, s) представляет собой наименьшее общее кратное для чисел r и s, после чего

г) в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляется число z по формулам

z=z₁(mod р·r) и z=z₂ (mod q·s),

д) вычисляется результат операции Е возведения в степень путем сокращения z по модулю p·q,

е) ранее вычисленное число z (а тем самым автоматически и результат операции Е возведения в степень) проверяются на этапе контроля на наличие вычислительных ошибок, при этом

ж) указанный этап контроля заключается в выполнении следующих вычислительных операций:

ж1) вычисление чисел

причем до выполнения операции модульного возведения в степень по модулю (r), соответственно (s) сокращаются d_1 и d_2,

ж2) сравнение между собой значений z₁ и C₁ по модулю r, а также z ₂ и С₂ по модулю s, при этом результат операции Е модульного возведения в степень отбрасывается как ошибочный, если C₁ z₁mod r или C₂ z₂mod s.

18. Чип-карта по п.17, отличающаяся тем, что числа r и s являются нечетными.

19. Чип-карта по любому из пп.16-18, отличающаяся тем, что числа r и s выбираются из интервала [0, 2^k-1], где 16 k 32.

20. Чип-карта по любому из пп.16-18, отличающаяся тем, что по меньшей мере одно из чисел r и s выбирается таким образом, чтобы в двоичном представлении произведения р·r, соответственно q·s присутствовало максимально большое количество ведущих единиц.

21. Чип-карта по п.20, отличающаяся тем, что

а) сначала на первом подэтапе по меньшей мере для одного из чисел r и s выбирается соответствующее оптимальное число r _опт, соответственно s_опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирается по соседнему значению r=r_опт -i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

22. Чип-карта по п.20, отличающаяся тем, что

а) на первом подэтапе для каждого из чисел r и s выбирается соответствующее оптимальное число r_опт, соответственно s_опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирается по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

23. Чип-карта по п.20, отличающаяся тем, что

а) сначала на первом подэтапе выбирается по меньшей мере одно из чисел r_опт и s _опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми,

б) на втором подэтапе выбирается по соседнему значению r=r_опт-i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми, при условии, что такое значение существует для i=0, 1, ..., k, и

в) на третьем подэтапе в том случае, если на втором подэтапе не было выбрано ни одного значения, выбирается по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

24. Чип-карта по любому из пп.16-18, отличающаяся тем, что оба числа r и s выбираются таким образом, чтобы в двоичном представлении произведения р·r и произведения q·s присутствовало максимально большое количество ведущих единиц.

25. Чип-карта по п.24, отличающаяся тем, что

а) сначала на первом подэтапе по меньшей мере для одного из чисел r и s выбирается соответствующее оптимальное число r_опт, соответственно s_опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирается по соседнему значению r=r_опт -i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

26. Чип-карта по п.24, отличающаяся тем, что

а) на первом подэтапе для каждого из чисел r и s выбирается соответствующее оптимальное число r_опт, соответственно s_опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми, и

б) на втором подэтапе выбирается по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

27. Чип-карта по п.24, отличающаяся тем, что

а) сначала на первом подэтапе выбирается по меньшей мере одно из чисел r_опт и s _опт без ограничения такого выбора условием, согласно которому величины d и (kgV(r, s)) должны быть взаимно простыми,

б) на втором подэтапе выбирается по соседнему значению r=r_опт-i, соответственно s=s_опт-i, где i=0, 1, ..., k, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми, при условии, что такое значение существует для i=0, 1, ..., k, и

в) на третьем подэтапе в том случае, если на втором подэтапе не было выбрано ни одного значения, выбирается по значению r=2¹·r _опт, соответственно s=2¹·s_опт , где 1=0, 1, ..., j, таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми.

28. Чип-карта по любому из пп.16-18, отличающаяся тем, что она выполнена с возможностью осуществления криптографического способа, предусматривающего выполнение алгоритма Райвеста-Шамира-Адлемана.

29. Чип-карта по любому из пп.16-18, отличающаяся тем, что она выполнена с возможностью осуществления криптографического способа, предусматривающего выполнение алгоритма цифровой подписи Рабина.

30. Чип-карта по любому из пп.16-18, отличающаяся тем, что она выполнена с возможностью осуществления криптографического способа, предусматривающего выполнение алгоритма идентификации Фиата-Шамира.

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

Криптографические методы, к которым относятся методы шифрования информации и методы создания электронных подписей, находят все более широкое распространение, что обусловлено прежде всего возрастанием того значения, которое в деловой сфере приобретает электронное ведение бизнеса. Для практической реализации подобных методов обычно используются соответствующие электронные устройства, которые для этой цели могут быть оснащены, например, универсальным программируемым микроконтроллером или же специализированной электронной схемой, например, в виде специализированной интегральной схемы (ИС). Одним из представляющих особый интерес криптографических устройств является карта со встроенной микросхемой (так называемая чип-карта), поскольку на такой карте при ее соответствующем техническому назначению выполнении можно сохранить секретные параметры ключа доступа в защищенном от несанкционированного доступа к ним виде. При этом основные усилия при разработке криптографических методов направлены на повышение скорости их выполнения, а также на защиту обрабатываемой с их помощью информации от всех возможных типов получения к ней несанкционированного доступа ("взлома"). Предлагаемое в изобретении решение пригодно для его использования прежде всего применительно к чип-картам, чем, однако, не ограничиваются возможные области его применения. Более того, предлагаемое в настоящем изобретении решение может быть реализовано в криптографических устройствах всех типов.

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

где р и q представляют собой простые числа. Наиболее значимым криптографическим методом, предусматривающим выполнение указанной операции модульного возведения в степень, является алгоритм цифровой подписи Райвеста-Шамира-Адлемана (RSA-алгоритм), известный, например, из публикации Alfred J. Menezes, Paul С. van Oorschot и Scott A. Vanstone, "Handbook of Applied Cryptography", изд-во CRC Press, Boca Raton, 1997, cc.285-291. Однако операция модульного возведения в степень используется не только в RSA-алгоритме, но и, например, в алгоритме цифровой подписи Рабина, известном из указанной выше публикации авторов Menezes и др., сс.438-442, и в алгоритме идентификации Фиата-Шамира, также известном из этой же публикации авторов Menezes и др., сс.408-410.

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

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

где

Применение китайской теоремы об остатках позволяет оперировать при модульном возведении в степень уже не с величиной по модулю N, т.е. с вычисляемым по модулю значением того числа, в котором все еще сохраняются его собственные простые множители, разложению на которые оно подвергается, а последовательно сначала с величиной по модулю р, а затем с величиной по модулю q, т.е. при использовании подобного правила вычислений изначально необходимо знать сохраняемую в тайне методику разложения на простые множители n=p·q, что в результате приводит к разбиению всего процесса вычислений на первый этап вычислений согласно уравнению (3), на котором основной подвергаемой обработке величиной является первый простой множитель, и на второй этап вычислений согласно уравнению (4), на котором основной подвергаемой обработке величиной является второй простой множитель. Преимущество такого подхода состоит в том, что показатель степени d в уравнении (1) необходимо определять как величину, рассчитываемую по модулю (p·q), тогда как показатели степени в уравнении (2) необходимо определять лишь как величины, рассчитываемые по модулю (р) и (q) соответственно, где через обозначена функция Эйлера.

Следует отметить тот представляющий интерес факт, что в последнее время получил известность алгоритм "взлома" тех криптографических методов, в которых используется описанное выше модульное возведение в степень, при этом такой алгоритм основан на том, что в результате соответствующего искусственного вмешательства в протекающий в остальном без сбоев процесс вычислений на основании искаженного результата, полученного при неверном выполнении операции по модульному возведению в степень, можно получить информацию о простых множителях, разложению на которые подвергается число N, при условии, что при этом используется конкретная реализация китайской теоремы об остатках согласно уравнениям (2)-(4). Подобный метод получения несанкционированного доступа к информации, известный как "метод "взлома", выявленный специалистами фирмы Bellcore", рассмотрен, например, в публикации Dan Boneh, Richard A. DeMillo и Richard J. Lipton, "On the importance of checking Cryptographic Protocols for Faults", Advances in Cryptology - EUROCRYPT, 97, Lecture Notes in Computer Science 1233, изд-во Springer, Berlin, 1997. Согласно приведенной в указанной публикации информации получить доступ к данным можно путем преднамеренного создания неисправностей в шифраторе, подвергая его различного рода физическим воздействиям, таким, например, как завышение тактовой частоты, подача слишком высокого напряжения питания или радиационное облучение, что с определенной, хотя и не слишком высокой вероятностью приводит к возникновению ошибок в вычислениях при выполнении операции по модульному возведению в степень в соответствии с китайской теоремой об остатках. Если подобная ошибка в вычислениях возникает при оперировании только с одним из двух членов в уравнении (2), то на основании ошибочного результата возведения в степень можно восстановить оба простых множителя р и q.

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

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

Из заявки WO 98/52319 А1 известен, в частности, способ защиты вычислительных операций по модульному возведению в степень в соответствии с китайской теоремой об остатках от "взлома" по выявленной специалистами Bellcore методике. Этот способ состоит в том, что сначала выбирается некоторое секретное число j, например в интервале [0, 2^k-1], где 16 k 32. После этого выполняются вычисления в соответствии со следующими выражениями:

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

Если соблюдение этого условия (11) подтверждается, то согласно известному способу выполняются вычисления в соответствии со следующими выражениями:

на основании которых затем с помощью китайской теоремы об остатках можно определить значение

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

В соответствии с таким известным способом оба простых числа р и q необходимо умножать на один и тот же множитель d. В заявке WO 98/52319 А1 описан также второй вариант осуществления заявленного в ней способа, позволяющий умножать простые числа р и q на разные множители r и s. При этом, однако, для выполнения контрольных вычислений может потребоваться выполнение двух дополнительных операций возведения в степень.

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

Эта задача решается в предлагаемых в изобретении криптографическом способе и чип-карте для его осуществления.

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

Е=х^d(mod p·q),

где d и mod p·q являются компонентами секретного ключа, причем р представляет собой первый простой множитель, q представляет собой второй простой множитель, d представляет собой показатель степени, а х представляет собой основание.

В первом варианте предлагаемого способа для выполнения операции модульного возведения в степень выбирают два натуральных числа r и s, при условии, что величины d и (kgV(r, s)) являются взаимно простыми, и выполняют следующие этапы вычислений:

x₁=x(mod р·r),

x₂=x(mod q·s),

d_1=d(mod (р·r)),

d_2=d(mod (q·s)),

где () представляет собой функцию Эйлера, a kgV(r, s) является наименьшим общим кратным для чисел r и s.

Затем в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляют число z по формулам z=z₁ (mod р·r) и z=z₂(mod q·s).

Далее вычисляют результат операции Е возведения в степень путем сокращения z по модулю p·q и ранее вычисленное число z и тем самым результат операции Е возведения в степень проверяют на этапе контроля на наличие вычислительных ошибок. При этом этап контроля заключается в выполнении следующих вычислительных операций:

- вычисление наименьшего возможного натурального числа е, удовлетворяющего условию e·d=1(mod (kgV(r, s))), с помощью расширенного алгоритма Евклида,

- вычисление значения С=z^e(mod kgV(r, s)),

- сравнение между собой значений х и С по модулю kgV(r, s).

Результат операции Е модульного возведения в степень отбрасывается как ошибочный, если х C(mod kgV(r, s)).

Во втором варианте предлагаемого способа для выполнения операции модульного возведения в степень выбирают два натуральных числа r и s, а также два числа b ₁ и b₂ из интервала [1, ..., r-1], соответственно [1, ..., s-1], являющиеся взаимно простыми по отношению к числам r и s соответственно, причем эти числа b₁ и b ₂ удовлетворяют условию b₁=b₂(mod ggT(r, s)), где ggT(r, s) представляет собой наибольший общий делитель для чисел r и s.

С помощью обоих чисел b₁ и b₂ в соответствии с китайской теоремой об остатках вычисляют числа x₁ и х₂, которые удовлетворяют следующим условиям:

x₁=x(mod р), x₁ =b₁(mod r),

х₂=x(mod q), x₂ =b₂(mod s),

после чего выполняют следующие этапы вычислений:

d_1=d(mod (р)),

d_2=d(mod (q)),

где () представляет собой функцию Эйлера, a kgV(r, s) представляет собой наименьшее общее кратное для чисел r и s.

Далее в соответствии с китайской теоремой об остатках на основании величин z₁ и z₂ вычисляют число z по формулам z=z ₁(mod р·r) и z=z₂(mod q·s), вычисляют результат операции Е возведения в степень путем сокращения z по модулю p·q и ранее вычисленное число z (а тем самым автоматически и результат операции Е возведения в степень) проверяют на этапе контроля на наличие вычислительных ошибок.

Этот этап контроля заключается в выполнении следующих вычислительных операций:

- вычисление чисел

причем до выполнения операции модульного возведения в степень по модулю (r), соответственно (s), сокращают d_1 и d_2,

- сравнение между собой значений z₁ и С₁ по модулю r, а также z ₂ и С₂ по модулю s.

Результат операции Е модульного возведения в степень отбрасывается как ошибочный, если C₁ z₁ mod r или С₂ r₂ mod s.

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

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

Согласно изобретению предлагается выбирать два целых числа r и s, например, в интервале [0, 2^k-1], где 16 k 32, благодаря чему величины d и (kgV(r, s)) являются взаимно простыми, при этом kgV(r, s) представляет собой наименьшее общее кратное для чисел r и s, а () представляет собой функцию Эйлера. Затем выполняются вычисления в соответствии со следующими выражениями:

В этом случае справедливы следующие выражения: z₁=х^d(mod p·r) и z₂=х ^d(mod q·s). На основании известных величин z₁ и z₂ в соответствии с китайской теоремой об остатках можно легко вычислить число z согласно следующим выражениям:

Числа r и s следует выбирать согласно изобретению таким образом, чтобы величины d и (kgV(r, s)) были взаимно простыми. При наличии таких условий можно с помощью расширенного алгоритма Евклида легко найти натуральное число е в соответствии со следующим выражением:

Далее с помощью чисел z и е можно следующим образом вычислить число С:

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

Сравнение между собой обоих значений С и х по модулю kgV(r, s) позволяет с высокой степенью вероятности выявить наличие ошибки в вычислениях. Если С x(mod kgV(r, s)), то результат модульного возведения в степень следует рассматривать как ошибочный и отбросить.

В соответствии с RSA-алгоритмом (равно как и в соответствии с алгоритмом цифровой подписи Рабина) для формирования цифровой подписи или для дешифрации следует выполнить одну операция модульного возведения в степень, при этом модуль p·q и показатель степени d зависят только от секретного ключа. По этой причине числа d, е, r и s можно вычислять лишь однократно при вводе этого секретного ключа и затем сохранять для последующего использования.

В соответствии с одним из вариантов осуществления изобретения также предлагается выбирать два целых числа r и s, например, в интервале [0, 2^k-1], где 16 k 32. При использовании двоичного вычислительного (арифметического) устройства в качестве чисел r и s рекомендуется выбирать нечетные числа. Кроме того, выбирают два постоянных, не зависящих от х числа b₁ и b₂ из интервала [1, ..., r-1], соответственно [1, ..., s-1], являющихся взаимно простыми с числом r, соответственно s. Если числа r и s не являются взаимно простыми, то числа b₁ и b₂ должны удовлетворять дополнительному условию b₁=b₂(mod ggT(r, s)), где ggT(r, s) представляет собой наибольший общий делитель для чисел r и s.

Далее сначала в соответствии с китайской теоремой об остатках вычисляется число x₁ согласно следующему выражению:

Затем аналогичным образом вычисляется число х₂:

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

Для сокращения машинного времени можно сократить показатели степени d_1 и d_2 в уравнениях (27), соответственно (28) еще до возведения в степень по модулю (r), соответственно (s). Тем самым выражения (23) и (25) сводятся к следующему виду:

Выражения (24) и (26) в свою очередь сводятся к следующему виду:

На основании чисел z₁ и z₂ в соответствии с китайской теоремой об остатках можно легко вычислить число z:

Даже если числа r и s не являются взаимно простыми, то такое число z существует в любом случае, поскольку . Поскольку числа p и q являются взаимно простыми, из выражений (29), (30) и (31) следует, что:

и поэтому искомое число z легко определить на основании двух вычисленных выше значений.

Из выражений (21), (25) и (27) следует, что

Из выражений (22), (26) и (28) следует, что

Проверка соблюдения условий (33) и (34) позволяет с высокой степенью вероятности выявить ошибку. Если при такой проверке будет установлено несоблюдение одного из условий (33) и (34), то результат модульного возведения в степень следует рассматривать как ошибочный и отбросить.

В отличие от способа, представленного в п.8 в заявке WO 98/52319 А1, в рассмотренном выше варианте осуществления предлагаемого в изобретении способа числа b₁ и b₂ не зависят от основания x. Обычно при использовании RSA-алгоритма или алгоритма цифровой подписи Рабина секретный ключ однократно вводится в криптографическое устройство, например в чип-карту, и затем многократно используется. При этом при выполнении используемой в этих алгоритмах операции модульного возведения в степень показатель степени d, равно как и модуль p·q, являются неизменными и постоянными компонентами секретного ключа. По этой причине значения C₁ и С ₂ требуется вычислять лишь однократно при вводе ключа в криптографическое устройство и затем их можно сохранить в памяти этого устройства. По сравнению с известным из заявки WO 98/52319 А1 способом сохранение этих значений позволяет на две сократить количество операций по модульному возведению в степень.

В состав обычного криптографического устройства, например чип-карты, оснащенного дополнительными аппаратными средствами для ускорения выполнения арифметических модульных операций, входят быстродействующие сумматоры и/или умножители, тогда как для выполнения необходимой для модульного сокращения операции деления на многозначное число требуется применять стандартные методы, известные, например, из публикации Donald Knuth, "The Art of Computer Programming", т.2: Seminumerical Algorithms, 2-е изд., изд-во Addison-Wesley, 1981. Один из известных методов, позволяющих упростить подобную операцию деления, состоит в умножении модуля р на число r до выполнения операции по возведению в степень, и поэтому в двоичном представлении произведения р·r присутствует максимально возможное количество единиц (см., например, указанную выше публикацию авторов Menezes и др., сс.598-599). Деление на число, содержащее максимально возможное количество ведущих единиц, является значительно более простой операцией по сравнению с делением на некоторое отвлеченное число.

Множитель r выбирают согласно изобретению таким образом, чтобы величины d и (r) были взаимно простыми. Однако в рассмотренном выше варианте осуществления изобретения наличие подобной взаимной простоты не требуется. Для каждого модуля р существует зависящий от конкретной технической реализации операции деления оптимальный множитель r_опт. Если выбранное в качестве r значение несколько меньше оптимального, то количество содержащихся в произведении р·r ведущих единиц все еще остается достаточным для того, чтобы можно было упростить выполнение операции деления. При этом число d с высокой вероятностью является взаимно простым по отношению по меньшей мере к одному из значений (r_опт-i); i=1, ..., k, при этом k представляет собой малое число, зависящее от конкретной реализации.

В противном случае r заменяется на величину 2ⁱ·r, где 2ⁱ представляет собой зависящую от конкретной реализации приемлемую степень двойки.

Аналогичные подстановки соответственно возможны и применительно ко второму простому множителю q. Поскольку множители r (для р) и s (для q) можно выбирать независимо один от другого, соответствующим образом можно выбирать и значения для множителя s.