СПОСОБ ШИФРОВАНИЯ ЦИФРОВОЙ ПОДПИСИ ДВОИЧНОГО СООБЩЕНИЯ (АЛБЕР-ПОДПИСЬ) Российский патент 1995 года по МПК H04L9/00 

Описание патента на изобретение RU2030836C1

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

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

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

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

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

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

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

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

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

Выработанное предварительно n-битные контрольные комбинации всех Q=2q номеров сообщений свертывают парами описанным способом в 2q-1n-битных комбинаций q-1-го уровня, полученные 2q-1 n-битные комбинации q-1-го уровня снова свертывают парами в 2q-2 n-битных комбинаций q-2-го уровня, затем снова свертывают, и так q раз, пока не останется одна общедоступная n-битная комбинация 0-го уровня, которую с доверенным лицом заранее передают получателю, а при передаче сообщения ему передают вместе с 2mn/r-битной подписью n-битную контрольную комбинацию, парную для получения комбинации q-1-го уровня, а также q-1 комбинаций q-1, q-2,...,1-го уровней, дополняющих до пар при получении комбинаций следующего уровня, полученную на приеме подпись свертывают описанным способом, n-битную комбинацию снова свертывают с принятой парной n-битной комбинацией, результат свертывают с принятой парной комбинацией q-1-го уровня, и так q раз, пока не задействуют все q принятых дополняющих до пар n-битных комбинаций, полученную в результате n-битную комбинацию сравнивают с общедоступной n-битной комбинацией, хранящейся у получателя.

Свертывание N-битного сообщения в m-битную, m<<N, свертку уменьшает размер подписи в N/2m раз по сравнению с требуемым в прототипе. Свертывание подписи в n-битную комбинацию требует хранения у получателя всего лишь n контрольных бит на каждое сообщение. Если в свертке подписывать одновременно по r бит, то размер передаваемой подписи уменьшится в r раз. Если осуществить древовидное попарное свертывание контрольных комбинаций всех сообщений, то у получателя достаточно хранить лишь одну n-битную общедоступную контрольную комбинацию.

Сложность подделки подписи определяется минимальным из чисел m (длина свертки), n (длина общедоступной контрольной комбинации) и s (длина секретного ключа). Поэтому все эти числа целесообразно выбирать одинаковыми, то есть m=n=s. При этом, рекомендуется ограничиться максимальным значением 128. Так, при n= 64 сложность подделки подписи определяется перебором 264≈1019 ключей, а при n=128 надо перебрать 2128≈1039 ключей, что абсолютно нереально.

Для примера рассмотрим случай n=m=s=64.

N-битный открытый текст Т делится на блоки по 16 байт - Т1, Т2,...,ТN'.

Открытый текст Т свертывается в 64-битную комбинацию В следующим образом:
В= F(FTN'-1(...FT1V(0)...)), где FТi(Х) - результат шифрования алгоритмом Албер 8-байтной комбинации Х на 16-байтном ключе Тi.

Криптографическая стойкость алгоритма Албер гарантирует сложность подбора другого сообщения Т'≠Т с той же сверткой В на уровне 264переборов различных Т'.

Если К - 8-байтный секретный ключ отправителя, то группу из 128 индивидуальных ключей (по паре для каждого бита свертки)
k1,0t, k1,1t, k2,0t, k2,1t,...,k64,0t,k64,1t (1) для t-го сообщения вырабатывают следующим образом:
k1,0t=Fk(t), k1,1t=Fk(kt1,0),
k2,0t=Fk(k1,1t), k2,1t=Fk(k2,0t),
k64,0t=Fk(k63,1t), k64,1t=Fk(k64,0t), где t=, - номер сообщения, которое будет подписываться с использованием этой группы ключей.

В так выработанной группе ключей для определения любого ключа ki,j, 1 ≅ i ≅ 64, j=0,1, при известных остальных ключах (кроме секретного ключа К) необходимо вычислить секретный ключ К, для чего требуется перебор 264 всех возможных вариантов ключа К.

Общедоступные 64-битные контрольные комбинации хt, 1 ≅ t ≅ Q, для Q сообщений вырабатывают заранее. Для этого сначала формируют из секретного ключа t-ую группу индивидуальных ключей (1). Затем на каждой паре индивидуальных ключей kti,0, kti,1 шифруют 0 и 1 (например, комбинации из 64 нулей или 64 единиц). Полученные 128 8-битных блоков t t
F(0)=р1,0, F (1)=р1,1,...,
F (0)= рt, F (1)=рt свертывают точно так же, как и сообщение Т. Последовательность
р1,0t, р1,1t,...,р64,0t, р64,1t (2) разбивают на блоки р1, р2,..,р64 по 16 байт и формируют контрольную комбинацию
хt=Fр64(Fр63) (...Fр1(0)...)).

Общедоступные контрольные комбинации х12,...,хQ передают с доверенным лицом всем получателям.

Свертку В= (b1,...,b64), bi=0,1, 1 ≅ i ≅ 64, t-го сообщения Т подписывают следующим образом. Сначала формируют 128 64-битных блоков
b1,0, b1,1, ...,b64,0, b64,1, (3) где bi,0= F(0), bi,1=kit,

1 , если bi=0, и bi,0=kti
,0 , bi,1= F(1), если bi=1.

128 блоков (3) составляют 2*64*64-битную подпись, передаваемую получателю.

На приеме из полученных 128 блоков (3) формируют последовательность (2). Для этого сначала свертывают принятое сообщение Т и получают свертку В=(b1,...,b64). Получатель знает,
что если bi=0, то bi,0= F(0), bi,1=kit,

1, поэтому рit,
0 =bi,0, рit,
1 = Fbi,1 (1), а если bi=1, то bi,0=kit,
0 , bi,1=F (1), поэтому рit,
0 = Fbi,0(0), рit,
1 =bi,1.

Сформированную последовательность (2) свертывают и результат ytсравнивают с контрольной комбинацией хt. Равенство ytt удостоверяет отправителя и сообщение. Неравенство yt≠хt говорит получателю о том, что кто-то пытался изменить сообщение, подпись или имя отправителя.

Сложность восстановления ключа k из равенства b=Fk(а) при известных а и b определяется числом 264 переборов всех вариантов ключа k. Поэтому для замены пары kti

,0 , F(1) на пару F(0), kti
,1 (то есть формирования подписи для знака 0 вместо знака 1) необходимо затратить работу, определяемую перебором 264 вариантов ключа ki,1t.

В свертке В=(b1,...,b64) сообщения Т можно подписывать не отдельные биты b1,...,b64, а сразу группы по r бит с1=(b1,...,br), с2=(br+1,...,b2r),.. .

Как и в побитном случае, сначала формируют 64/r пар индивидуальных ключей
kt1

,0 =Fk(t), kt1
,1 =Fk(kt1
,0 ),
kt2
,0 =Fk(kt1
,1 ), kt2
,1 =FK(kt2
,0 ),
. . . . . . . .

Затем с их помощью формируют общедоступную 64-битную контрольную комбинацию хt. Для этого на каждой паре ключей ktj

,0 , ktj
,1последовательно 2r-1 раз шифруют комбинацию из 64 нулей. А именно:
F0)=c0,1, F0)= с0,2,...,F(0)=
=c0,2r -1tj
,0 , (4)
F(0)=с1,1, F 0)=с1,2,..., F(0)=
=c1,2r -1jt,
1 (5)
Последовательность
рt1
,0 , рt1
,1 , рt2
,0 , рt2
,1 ,... (6) разбивают на блоки по 16 байт и свертывают в 64-битную комбинацию х, которую в качестве общедоступной контрольной комбинации t для t-го сообщения с доверенным лицом передают возможным получателям.

Подпись C, c1,2r -1- r-битной группы сi, i=1,...,64/r, свертки В сообщения Т формируют следующим образом F(0)=с0,1, F0)=с0,2,..., Fc0)=
= c,
F (0)=с1,1, F(0)=с1,2,...,F2r(0)=
=c1,2r -1- .

Получателю передают 128/r 64-битных комбинаций c, c1,2r -1-, c, c1,2r -1-,...

На приеме сначала свертывают сообщение Т в свертку В и разбивают ее на r-битные группы с1, с2,.. Затем шифруют принятые комбинации cеще 2r-1-сi раз, а комбинации c1,2r -1- еще сi раз, то есть:
F(0)=c,...,F(0)=
= c0,2r -1ti

,0 ,
F(0)=c,..., Fr -2(0)=
= c1,2r -1ti
,1 .

Аналогичным образом докручивают до рtj

,0 , рtj
,1 остальные 64-битные пары c0,cj, c1,2r -1- подписи. Полученную последовательность (6) разбивают на блоки по 16 байт и свертывают в 64-битную комбинацию yt, которую сравнивают с общедоступной контрольной комбинацией хt t-го сообщения.

Чтобы подделать подпись r-битной группы сj', зная подпись группы сj= сj', надо по цепочке (4), если сj'<сj, либо по цепочке (5), если сj'>сj, пройти влево. Это требует определения ключа в схеме Албер, которое можно осуществить перебором 264 его вариантов.

Сократить количество общедоступных 64-битных контрольных комбинаций, хранящихся у получателей сообщений, можно следующим образом. Пусть общее количество сообщений равно Q= 2q. Tогда заранее из 64-битных контрольных комбинаций р1, р2,...,рQ формируют 2q-1 64-битных комбинаций
р1q-1= F(0), р2q-1= F(0),..., p= F (0) q-1-го уровня. Затем и 2q-1 комбинаций р1q-1 р2q-1..., p формируют 2q-2 64-битных комбинаций
pq1

-2= F(0), pq2
-2=F(0),...,p=F(0) q-2-го уровня. И так далее, до 0-го уровня:
p0=F(0).

64-битная комбинация р0 является общедоступной контрольной комбинацией для всех Q=2q сообщений и ее с доверенным лицом передают получателям.

t-ое сообщение Т подписывают описанным выше образом и подпись вместе с q комбинациями ptq, p ,...,p всех уровней, дополняющих до пары в проделанной заранее процедуре получения комбинации следующего уровня, передают получателю. На приеме формируют комбинацию рt, а затем цепочку комбинаций
F(0) = pq-1, F(0) = pq-2,..., F(0) = x0.

Комбинацию х0 сравнивают с контрольной комбинацией р0 и по результату сравнения делают вывод о подлинности подписи.

Похожие патенты RU2030836C1

название год авторы номер документа
СПОСОБ ФОРМИРОВАНИЯ N-БИТНОЙ КОНТРОЛЬНОЙ КОМБИНАЦИИ N-БИТНОЙ ДВОИЧНОЙ ИНФОРМАЦИИ 1994
  • Березин Борис Владимирович
  • Дорошкевич Петр Васильевич
RU2114463C1
УСТРОЙСТВО ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ "АЛБЕР" 1991
  • Березин Борис Владимирович
RU2007884C1
СПОСОБ ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ И УСТРОЙСТВО ДЛЯ ОСУЩЕСТВЛЕНИЯ СПОСОБА - "АЛБЕР" 1994
  • Березин Борис Владимирович
RU2099890C1
УСТРОЙСТВО ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ "АЛБЕР" 1991
  • Березин Борис Владимирович
RU2024209C1
СИСТЕМА И СПОСОБ ЗАЩИТЫ ИНФОРМАЦИИ 2018
  • Ма, Баоли
  • Чжан, Вэньбинь
  • Ма, Хуаньюй
  • Лю, Чжэн
  • Цуй, Цзяхой
RU2719423C1
СПОСОБ ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 1995
  • Березин Борис Владимирович
  • Волков Сергей Сергеевич
  • Рощин Борис Васильевич
  • Сердюков Петр Николаевич
RU2097931C1
СПОСОБ ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ 1992
  • Березин Борис Владимирович
RU2032990C1
СИСТЕМА И СПОСОБ ДЛЯ ЗАЩИТЫ ИНФОРМАЦИИ 2018
  • Ма, Баоли
  • Чжан, Вэньбинь
RU2721959C1
СИСТЕМА И СПОСОБ ЗАЩИТЫ ИНФОРМАЦИИ 2018
  • Цуй, Цзяхой
  • Ма, Баоли
  • Лю, Чжэн
  • Чжан, Вэньбинь
  • Ма, Хуаньюй
RU2716740C1
СПОСОБ ДОСТАВКИ КЛЮЧА С ПРОВЕРКОЙ ПОДЛИННОСТИ КОРРЕСПОНДЕНТА РАДИОСЕТИ 2016
  • Бурнашев Рустам Умидович
  • Разиков Владимир Николаевич
  • Козловцев Виктор Владимирович
  • Жарков Владимир Евгеньевич
RU2654122C2

Реферат патента 1995 года СПОСОБ ШИФРОВАНИЯ ЦИФРОВОЙ ПОДПИСИ ДВОИЧНОГО СООБЩЕНИЯ (АЛБЕР-ПОДПИСЬ)

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

Формула изобретения RU 2 030 836 C1

СПОСОБ ШИФРОВАНИЯ ЦИФРОВОЙ ПОДПИСИ ДВОИЧНОГО СООБЩЕНИЯ (АЛБЕР-ПОДПИСЬ).

1. Способ шифрования цифровой подписи двоичного сообщения, заключающийся в формировании из личного секретного ключа отправителя для каждого бита подписываемой информации пары производных ключей, формировании с их помощью для каждого бита общедоступных контрольных комбинаций, передаче в качестве подписи бита соответствующих производных ключей, формировании на приеме из принятых производных ключей комбинаций и сравнении их с общедоступными контрольными комбинациями, отличающийся тем, что на личном секретном ключе формируют t = [m/r] пар производных ключей (где t, m, r - целые числа, m ≥ 1, 1 ≅ r ≅ m, t - количество r-битных групп, m - длина преобразованного сообщения, r - количество подписываемых одновременно бит), на каждой паре производных ключей 2r - 1 раз последовательно шифруют произвольно выбранные целые числа a и b, причем ключом для второго и последующих шифрований служит результат предыдущего шифрования, полученные в результате 2t двоичных чисел преобразуют в S-битную комбинацию (S - длина контрольной комбинации), которую передают получателям в качестве общедоступной контрольной комбинации, при передаче двоичного сообщения его преобразуют в m-битную комбинацию, на каждой паре производных ключей последовательно шифруют числа a и b, причем число a шифруют на первом ключе пары столько раз, каково численное значение соответствующей этой паре ключей r-битной группы, а число b шифруют на втором ключе пары количество раз, дополняющее предыдущее до числа 2r - 1, 2t результатов шифрований или самих производных ключей, если численное значение r бит равно 0 или 2r - 1, передают в качестве подписи двоичного сообщения, на приеме сообщение преобразуют в m-битную комбинацию, на полученных t парах чисел подписи последовательно дошифровывают числа a и b столько раз, чтобы суммарное количество шифрований на передаче и приеме для каждой пары производных ключей каждой r-битной группы было 2r - 1, полученные в результате 2t двоичные числа преобразуют в S-битную комбинацию и сравнивают с хранящейся у получателя общедоступной контрольной комбинацией. 2. Способ шифрования цифровой подписи двоичного сообщения, заключающийся в формировании общедоступных контрольных комбинаций для всех передаваемых сообщений, формировании и передаче с сообщениями подписей, формировании на приеме из подписей комбинаций и сравнении их с хранящимися у получателя общедоступными контрольными, отличающийся тем, что из сформированных предварительно контрольных комбинаций всех Q = 2q сообщений путем шифрования некоторого произвольного целого числа, с использованием в качестве ключей пар контрольных комбинаций формируют 2q-1 комбинаций (q - 1)-го уровня, из полученных 2q-1 комбинаций (q - 1)-го уровня формируют 2q-2 комбинаций (q - 2)-го уровня, из которых снова формируют комбинации, и так q раз, пока не останется одна комбинация нулевого уровня, которую в качестве общедоступной контрольной передают получателю, а при передаче i-го сообщения вместе с подписью передают контрольную комбинацию, парную для получения комбинации (q - 1)-го уровня, а также q - 1 комбинаций (q - 1)-, (q - 2)-, ... 1-го уровней, дополняющих до пар при получении комбинаций следующего уровня, из полученной на приеме подписи i-го сообщения формируют комбинацию, из которой вместе с принятой парной комбинацией формируют комбинацию (q - 1)-го уровня, из которой снова с принятой парной комбинацией (q - 1)-го уровня формируют комбинацию (q - 2)-го уровня, и так q раз, пока не используют все q принятых дополняющих до пар комбинаций, полученную в результате комбинацию сравнивают с общедоступной контрольной комбинацией, хранящейся у получателя. 3. Способ по п.1, отличающийся тем, что при формировании S-битной контрольной комбинации и m-битного результата преобразования сообщения применяют последовательное шифрование некоторого числа, используя при очередном шифровании в качестве ключа очередную группу преобразуемой информации, а в качестве шифруемого числа - результат предыдущего шифрования.

Документы, цитированные в отчете о поиске Патент 1995 года RU2030836C1

W
Diffie and M.E.Hellman "New direction in cryptografy "IEEE, Traus, and Informations Theory, IT -22, 6 (Nov.1976).

RU 2 030 836 C1

Авторы

Березин Борис Владимирович

Дорошкевич Петр Васильевич

Даты

1995-03-10Публикация

1991-12-26Подача