Главная
Быстрая цифровая подпись – вариант цифровой подписи, использующий алгоритм с гораздо меньшим (в десятки раз) числом вычислений модульной арифметики по сравнению с традиционными схемами ЭЦП. Схема быстрой электронной подписи, как и обычная, включает в себя алгоритм генерации ключевых пар пользователя, функцию вычисления подписи и функцию проверки подписи.
Проблемы ЭЦП
С момента изобретения ЭЦП в 1976 году, она является самой многообещающей областью исследований в криптосистемах с открытым ключом. Одним из стандартных математических решений для построения криптографических алгоритмов является задача дискретного логарифмирования, на основе которой были разработаны многие алгоритмы получения ЭЦП. Главным недостатком традиционных алгоритмов ЭЦП, таких как схема Эль-Гамаля и RSA, является их вычислительная сложность. Вычисление экспонент в модульной арифметике требует наибольших вычислительных затрат в схемах криптосистем с открытым ключом. В настоящее время ведётся большое количество работ по улучшению производительности криптографических алгоритмов путём сокращения количества вычислений экспонент. Наиболее короткой известной схемой ЭЦП является BLS (Boneh – Lynn - Shacham), использующая эллиптические кривые, но она ограничена группами, в которых есть функция составления пары. Разработчики алгоритмов работают как над улучшением традиционных схем с дискретным логарифмированием, используя параллельные вычисления экспонент, так и изучают принципиально другие подходы, основанные, например, на теории графов вместо модульной арифметики.
Некоторые алгоритмы быстрой цифровой подписи
Схема быстрой ЭЦП, основанная на алгоритме Диффи-Хеллмана
Пусть G {displaystyle G} – абелева группа, G g , q {displaystyle G_{g,q}} – её циклическая подгруппа с генератором g {displaystyle g} порядка q {displaystyle q} , где q {displaystyle q} – большое простое число. Пусть l q {displaystyle l_{q}} и l p {displaystyle l_{p}} - параметры безопасности, причём l q = | q | {displaystyle l_{q}=|q|} . Пусть H : { 0 , 1 } ∗ → G g , q {displaystyle H:{{0,1}^{*}} ightarrow G_{g,q}} , L : { 0 , 1 } ∗ → Z q ∗ {displaystyle L:{{0,1}^{*}} ightarrow Z_{q}^{*}} и G : { 0 , 1 } ∗ → Z q ∗ {displaystyle G:{{0,1}^{*}} ightarrow Z_{q}^{*}} - хеш-функции. Схема подписи представляет собой следующее:
Генерация ключа
Пользователь выбирает случайный секретный ключ x ∈ Z q ∗ {displaystyle xin Z_{q}^{*}} и вычисляет открытый ключ y = g x {displaystyle y=g^{x}} .
Создание подписи
Входными данными являются секретный ключ x ∈ Z q ∗ {displaystyle xin Z_{q}^{*}} и сообщение m ∈ { 0 , 1 } ∗ {displaystyle min {0,1}^{*}} .
Далее сторона, создающая подпись:
1. выбирает случайное число k ∈ Z q ∗ {displaystyle kin mathbb {Z} _{q}^{*}} и случайный бит b m ∈ { 0 , 1 } {displaystyle b_{m}in {0,1}} ;
2. вычисляет h = H ( m , b m ) {displaystyle h=H(m,b_{m})} ;
3. вычисляет u = h x {displaystyle u=h^{x}} ;
4. вычисляет v = ( g n ∗ h ) k {displaystyle v=(g^{n}*h)^{k}} , где n = L ( m , g , h , y , u ) {displaystyle n=L(m,g,h,y,u)} ;
5. вычисляет r = G ( m , g , h , y , u , v ) {displaystyle r=G(m,g,h,y,u,v)} ;
6. вычисляет s = k − x r m o d q {displaystyle s=k-xr mod q} .
Подписью сообщения m {displaystyle m} является σ = ( u , r , s , b m ) {displaystyle sigma =(u,r,s,b_{m})} .
Проверка подписи
Чтобы проверить подпись σ {displaystyle sigma } сообщения m, делается следующее:
1. σ {displaystyle sigma } представляется как ( u , r , s , b m ) {displaystyle (u,r,s,b_{m})} ;
2. вычисляется h = H ( m , b m ) {displaystyle h=H(m,b_{m})} и n = L ( m , g , h , y , u ) {displaystyle n=L(m,g,h,y,u)} ;
3. вычисляется v ′ = ( g n ∗ h ) s ∗ ( y n ∗ u ) r {displaystyle vprime =(g^{n}*h)^{s}*(y^{n}*u)^{r}} ;
4. проверяется, выполняется ли r = G ( m , g , h , y , u , v ′ ) {displaystyle r=G(m,g,h,y,u,vprime )} .
Если равенство на шаге 4 выполняется, подпись проходит проверку.
Схема быстрой ЭЦП, основанная на алгоритме Фиата-Шамира
ZN обозначает кольцо целых чисел по модулю N {displaystyle N} , t {displaystyle t} и p {displaystyle p} — параметры безопасности, обычно t ⩽ 4 {displaystyle tleqslant 4} , p ⩽ 20 {displaystyle pleqslant 20}
Роль центра аутентификации ключей (ЦАК)
ЦАК выбирает:
- случайные простые числа p {displaystyle p} и q {displaystyle q} так, чтобы p , q ⩾ 2 256 {displaystyle p,qgeqslant 2^{256}} ;
- однонаправленную хеш-функцию h : Z N ⊗ Z → { 0 , 1 } t k {displaystyle h:Z_{N}otimes Z ightarrow {{0,1}}^{t}k} ;
- свои собственные секретный и открытый ключи.
ЦАК публикует N = p ∗ q {displaystyle N=p*q} , h {displaystyle h} и открытый ключ.
Секретный ключ ЦАК используется для подписи создаваемых им открытых ключей. Для создания таких подписей ЦАК может использовать любую безопасную схему ЭЦП.
Генерация пользовательских ключей.
Каждый пользователь выбирает секретный ключ s = ( s 1 , ⋯ s k ) {displaystyle s=(s_{1},cdots ,s_{k})} , состоящий из случайных чисел s i {displaystyle s_{i}} , s i {displaystyle s_{i}} меняется от 1 до N {displaystyle N} , таких, что НОД ( s i , N ) = 1 {displaystyle (si,N)=1} для всех s {displaystyle s} от 1 до k {displaystyle k} . Создание подписи может быть ускорено, если выбирать в качестве s 1 , ⋯ s k {displaystyle s_{1},cdots ,s_{k}} небольшие целые числа. Безопасность такой схемы основана на предположении о том, что вычисление корней 2 t mod N {displaystyle 2^{t}mod N} является трудным. В настоящее время неизвестно о существовании алгоритмов, вычисляющих корни 2 t mod N {displaystyle 2^{t}mod N} при условии, что эти корни порядка N 2 − t + 1 {displaystyle N^{2^{-t+1}}} .
Регистрация пользователей.
ЦАК проверяет соответствие пользователя, создаёт строку I {displaystyle I} , содержащую имя, адрес и т. д. и создаёт подпись S {displaystyle S} для пары ( I , v ) {displaystyle (I,v)} , состоящую из I {displaystyle I} и открытого ключа пользователя v {displaystyle v} .
Создание подписи.
Входное сообщение m {displaystyle m} , секретный ключ s = ( s 1 , ⋯ s k ) {displaystyle s=(s_{1},cdots ,s_{k})} и N {displaystyle N} — модуль, по которому проводят вычисления.
1. Выбирается случайное число r {displaystyle r} из диапазона [ 1 , N ] {displaystyle [1,N]} , вычисляется x = r 2 t {displaystyle x=r^{2^{t}}} .
2. Вычисляется e = ( e 1 1 , ⋯ e t k ) = h ( x , m ) {displaystyle e=(e_{1}1,cdots ,e_{t}k)=h(x,m)} .
3. Вычисляется y = r ∏ j = 1 k s j ∑ i = 1 t e i j ∗ 2 i − 1 mod N {displaystyle y=rprod olimits _{j=1}^{k}s_{j}^{sum olimits _{i=1}^{t}e_{ij}*2^{i-1}}mod N} .
Подписью на выходе является пара ( e , y ) {displaystyle (e,y)} .
Создание подписи требует не более k ∗ t + t − 1 {displaystyle {k*t+t-1}} операций умножения по модулю, а в среднем для случайного e {displaystyle e} требуется только t ( k + 2 ) / 2 + 1 {displaystyle t(k+2)/2+1} операций умножения.
Проверка подписи.
Входные данные — подпись ( e , y ) {displaystyle (e,y)} , сообщение m {displaystyle m} , v = ( v 1 , ⋯ v k ) {displaystyle v=(v_{1},cdots ,v_{k})} , I , S , N {displaystyle I,S,N} .
1. Проверяется подпись S {displaystyle S} для ( I , v ) {displaystyle (I,v)} .
2. Вычисляется z = y 2 t ∏ j = 1 k v j ∑ i = 1 e i j ∗ 2 i − 1 mod N {displaystyle z=y^{2^{t}}prod olimits _{j=1}^{k}v_{j}^{sum olimits _{i=1}e_{ij}*2^{i-1}}mod N} .
3. Проверяется, что e = h ( z , m ) {displaystyle e=h(z,m)} .
Для проверки подписи требуется в среднем для случайного e {displaystyle e} t ( k + 2 ) / 2 + 1 {displaystyle t(k+2)/2+1} операций умножения по модулю, максимум k ∗ t + t {displaystyle {k*t+t}} .
Безопасность подписи.
Чтобы подделать подпись сообщения m {displaystyle m} , криптоаналитик должен решить уравнение e = h ( y 2 t ∏ j = 1 k v j ∑ i = 1 t e i , j ∗ 2 i − 1 , m ) mod N {displaystyle e=h(y^{2^{t}}prod olimits _{j=1}^{k}v_{j}^{sum olimits _{i=1}^{t}e_{i,j}*2^{i-1}},m)mod N} для e {displaystyle e} и y {displaystyle y} .
В настоящее время неизвестно алгоритмов для решения этого уравнения.
Применение быстрой ЭЦП
Быстрые алгоритмы цифровой подписи являются наиболее эффективными в тех случаях, когда преимущественно важна скорость получения ключа и небольшой размер подписи. Подобные требования имеют место в мобильных, сенсорных или персональных сетях (радиус которых ограничивается пределами одной комнаты) при передаче мультимедийного трафика. Использование цифровой подписи в мобильных телефонах стандарта GSM позволяет пользователям самостоятельно создавать PIN- код, а не получать его от оператора.
Реализация ускоренных алгоритмов создания ЭЦП для устройств с ограниченными ресурсами, таких как КПК, встроенные смарт-карты и мобильные телефоны, вычислительная мощность которых сильно уступает возможностям персональных компьютеров, позволит тратить меньше энергии на создание и хранение подписи и тем самым увеличит время работы устройства без подзарядки.