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

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

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

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

Выработанное предварительно n-битные контрольные комбинации всех Q=2^q номеров сообщений свертывают парами описанным способом в 2^q-1n-битных комбинаций q-1-го уровня, полученные 2^q-1 n-битные комбинации q-1-го уровня снова свертывают парами в 2^q-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 сложность подделки подписи определяется перебором 2⁶⁴≈10¹⁹ ключей, а при n=128 надо перебрать 2¹²⁸≈10³⁹ ключей, что абсолютно нереально.

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

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

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

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

Если К - 8-байтный секретный ключ отправителя, то группу из 128 индивидуальных ключей (по паре для каждого бита свертки)
k_1,0^t, k_1,1^t, k_2,0^t, k_2,1^t,...,k_64,0^t,k_64,1^t (1) для t-го сообщения вырабатывают следующим образом:
k_1,0^t=F_k(t), k_1,1^t=F_k(k^t_1,0),
k_2,0^t=F_k(k_1,1^t), k_2,1^t=F_k(k_2,0^t),
k_64,0^t=F_k(k_63,1^t), k_64,1^t=F_k(k_64,0^t), где t=, - номер сообщения, которое будет подписываться с использованием этой группы ключей.

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

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

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

Свертку В= (b₁,...,b₆₄), b_i=0,1, 1 ≅ i ≅ 64, t-го сообщения Т подписывают следующим образом. Сначала формируют 128 64-битных блоков
b_1,0, b_1,1, ...,b_64,0, b_64,1, (3) где b_i,0= F(0), b_i,1=k_it,

₁ , если b_i=0, и b_i,0=kti_,0 , b_i,1= F(1), если b_i=1.

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

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

₁, поэтому р_it,₀ =b_i,0, р_it,₁ = F_bi,1 (1), а если b_i=1, то b_i,0=k_it,₀ , b_i,1=F (1), поэтому р_it,₀ = F_bi,0(0), р_it,₁ =b_i,1.

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

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

_,0 , F(1) на пару F(0), kti_,1 (то есть формирования подписи для знака 0 вместо знака 1) необходимо затратить работу, определяемую перебором 2⁶⁴ вариантов ключа k_i,1^t.

В свертке В=(b₁,...,b₆₄) сообщения Т можно подписывать не отдельные биты b₁,...,b₆₄, а сразу группы по r бит с₁=(b₁,...,b_r), с₂=(b_r+1,...,b_2r),.. .

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

_,0 =F_k(t), kt1_,1 =F_k(kt1_,0 ),
kt2_,0 =F_k(kt1_,1 ), kt2_,1 =F_K(kt2_,0 ),
. . . . . . . .

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

_,0 , ktj_,1последовательно 2^r-1 раз шифруют комбинацию из 64 нулей. А именно:
F0)=c_0,1, F0)= с_0,2,...,F(0)=
=c_0,2r _-1=рtj_,0 , (4)
F(0)=с_1,1, F 0)=с_1,2,..., F(0)=
=c_1,2r _-1=р_jt,₁ (5)
Последовательность
рt1_,0 , рt1_,1 , рt2_,0 , рt2_,1 ,... (6) разбивают на блоки по 16 байт и свертывают в 64-битную комбинацию х, которую в качестве общедоступной контрольной комбинации t для t-го сообщения с доверенным лицом передают возможным получателям.

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

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

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

_,0 ,
F(0)=c,..., Fr _-2(0)=
= c_1,2r _-1 =рti_,1 .

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

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

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

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

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

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

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

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

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

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

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