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

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

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

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

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

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

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

6. Носитель данных по любому из пп.1-5, отличающийся тем, что случайное число выбирается таким образом, чтобы длина этого случайного числа вместе с его весом по Хеммингу была примерно постоянной для различных случайных чисел.

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

8. Способ по п.7, отличающийся тем, что конфиденциальные данные представляют собой секретный ключ для шифрования сообщений.

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

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

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

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

13. Способ формирования зашифрованного сообщения в системе аутентификации системных компонентов или формирования цифровой подписи, отличающийся тем, что формируют случайное число r, делением секретного ключа d на это полученное случайное число r вычисляют первую часть (d1) ключа, выполнением операции d mod r получают вторую часть (d2) ключа, начинают формирование зашифрованного сообщения, для чего вычисляют M^r mod n, после чего вычисляют D1=(M^r)^d1 mod n и D2=M^d2 mod n и затем промежуточные результаты D1 и D2 перемножают и находят значение по модулю n.

14. Способ по п.13, отличающийся тем, что при вычислении D1 сначала вычисляют М mod n, а затем вычисляют (М^d1)^r mod n.

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

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

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

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

Помимо этого в последнее время получили известность методы, позволяющие за счет измерения потребляемого тока или временных характеристик при шифровании выявлять конфиденциальные данные и прежде всего используемый для их шифрования секретный ключ (см. Paul С. Kocher, "Timing Attacks on implementation of Diffie-Hellman, RSA, DSS, and other Systems", изд-во Springer Verlag 1998; WO 99/35782).

Наиболее простой из числа подобных методов получения несанкционированного доступа к конфиденциальной информации состоит в простом анализе электрических характеристик (SPA от анг. "Simple Power Analysis"). Этот метод анализа можно пояснить на следующем примере, когда известное сообщение М подвергается шифрованию с помощью секретного ключа d, т.е. формируется некоторый зашифрованный текст вида Y=М^d mod n. При модулярном возведении в степень промежуточный результат при наличии "1" в показателе d возводится в квадрат и умножается на М, тогда как при наличии "0" в показателе d промежуточный результат только возводится в квадрат. При известном М анализ токовых и/или временных характеристик, сопровождающих выполнение указанных операций, позволяет выявить само сообщение М. Поскольку это сообщение всегда используется при наличии "1" в показателе d, появляется возможность без каких-либо проблем выявить сам секретный ключ.

Воспрепятствовать подобной попытке получения несанкционированного доступа к данным достаточно просто, если внести в сообщение М, соответственно в ключ d определенные изменения. Однако из публикации Paul С.Kocher, "Timing Attacks on implementation of Diffle-Hellman, RSA, DSS, and other Systems", изд-во Springer Verlag, 1998, а также из заявки WO 99/35782 известны также другие методы анализа, которые позволяют выявить ключ даже при наличии измененного, т.е. закодированного ("замаскированного"), сообщения или ключа путем экспериментального снятия множества характеристик, форма которых позволяет судить о происходящем в интегральной микросхеме временном изменении тока (так называемый дифференциальный анализ электрических характеристик (DPA от англ. "Differential Power Analysis"), соответственно дифференциальный анализ электрических характеристик высшего порядка ("Higher Order DPA").

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

Так, в частности, для шифрования вместо секретного ключа d в этом методе предлагается использовать выражение d+r· Ф, где г представляет собой случайное число, а Ф представляет собой функцию Эйлера. При этом применительно конкретно к RSA-алгоритму (алгоритм цифровой подписи Райвеста-Шамира-Адлемана) справедливо следующее выражение: n=p· q, где р и q представляют собой простые числа, и тем самым Ф=(p-1)· (q-1). При использовании теоремы Эйлера справедливо следующее выражение: М^d mod n=M^{d+r· Ф} mod n. Если при каждом вычислении использовать различные случайные числа г, то даже в результате многократных попыток проанализировать вычислительные операции не удастся выявить ключ d.

В другом варианте секретный ключ d можно разложить на выражение вида d1· d2 mod Ф. В этом случае для шифрования используется следующее выражение: Y=M^{d1· d2 mod Ф}mod n=(M^d1)^d2 mod n.

Однако недостаток такого метода защиты ключа состоит в том, что из-за недостаточного объема памяти простые числа р и q или Ф обычно не хранят в памяти чип-карты.

Секретный ключ d также можно разложить на сумму d1 и d2. В этом случае справедливо следующее выражение: d=d1+d2, соответственно для шифрования используется следующее выражение:

Y=М ^d1+d2 mod n=М^d1· М^d2 mod n=(М^d1 mod n · М^d2 mod n) mod n.

С целью обеспечить достаточно высокую степень защиты данных при разложении показателя степени на выражение вида d=d1+d2 или d=d1· d2 mod Ф для каждого вычисления необходимо использовать новую случайную пару d1/d2. Поскольку формирование случайных чисел обычно является длительным процессом, подобный метод не пригоден для применения в чип-картах. Кроме того, при этом значительно увеличиваются затраты времени на вычисления, связанные с модулярным возведением в степень, что также препятствует применению этого метода в чип-картах.

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

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

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

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

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

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

Для шифрования сообщения М используется выражение вида Y=М^d mod n. При этом секретный ключ d разделяют на d1, d2 и r, где d1=d/r (r представляет собой случайное число) без учета остатка от такого деления. Остаток от этого деления образует вторую часть d2 ключа d. Тем самым d2=d mod r. Таким образом, для ключа d справедливо следующее выражение: d=r· d1+d2.

В результате выполнения вышеописанных операций зашифрованное сообщение принимает следующий вид:

Y=M^d mod n=M^{r· d1+d2} mod n=(M^r)^d1 · M^d2 mod n=

=((M^r ))^d1 mod n · M^d2 mod n) mod n.

Процесс формирования зашифрованного сообщения Y проиллюстрирован на прилагаемом к описанию чертеже.

Сначала на шаге 1 формируется случайное число r (RND r). Затем на шаге 2 делением секретного ключа d на сформированное на предыдущем шаге случайное число r вычисляется первая часть d1 этого ключа. Вторая часть d2 ключа формируется как d mod r.

На шаге 4 начинаются вычисления по формированию зашифрованного текста, для чего сначала вычисляется М^r mod n. На следующем шаге 5 вычисляется выражение D1=(M^r)^d1 mod n, после чего на шаге 6 вычисляется выражение D2=М^d2 mod n.

Очевидно, что порядок выполнения отдельных вычислительных операций во времени можно частично изменить. Так, например, сначала можно вычислять М ^d1 mod n, а затем (М^d1)^r mod n, поскольку (M^r)^d1 mod n=(М^d1)^r mod n.

На последнем шаге 7 промежуточные результаты D1 и D2 перемножаются и находится значение по модулю n. Тем самым справедливо следующее выражение: D1· D2 mod n=M^d mod n=Y.

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

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

Предлагаемое в изобретении решение может найти применение в самых разнообразных системах шифрования. В качестве примера при этом можно назвать RSA-алгоритм, шифрование по методу Эль-Гамаля, DSA-алгоритм (алгоритм цифровой подписи), основанные на использовании эллиптических кривых системы и т.д.