RU2114463C1

RU2114463C1 - Способ формирования n-битной контрольной комбинации n-битной двоичной информации

Info

Publication number: RU2114463C1
Application number: RU94024374A
Authority: RU
Inventors: Борис Владимирович Березин; Петр Васильевич Дорошкевич
Original assignee: Борис Владимирович Березин; Петр Васильевич Дорошкевич
Priority date: 1994-06-29
Filing date: 1994-06-29
Publication date: 1998-06-27

Abstract

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

Description

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

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

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

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

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

N-битная информация T преобразуется в n-битную комбинацию W с помощью устройства шифрования, реализующего алгоритм шифрования F, следующим образом (устройство шифрования преобразует m-битную исходную комбинацию, а в m-битную шифркомбинацию b с использованием s-битного ключа k: b = F_k(a) . Сначала T разбивается на блоки по s-бит, где s - длина ключа преобразования F, то есть T= U₁U₂...U_N (если блок U_N′ содержит меньше s бит, то он некоторым образом (например, нулями) дополняется до s бит). Затем при m ≥ n устройство шифрования N'раз последовательно шифрует некоторое m-битное число а (например, 0) с использованием в качестве ключей s-битных блоков U_i, i =

. А именно:

,
где
g_i,

- m-битные комбинации. Определенные n бит (например, младшие) результаты последнего преобразования g_N′ и есть n - битная контрольная комбинация W.

Если m < n, то устройство шифрования N' раз последовательно шифрует некоторые m-битные числа а₁, а₂,..., а_r (например 0,1,..., r-1) с использованием в качестве ключей s-битных блоков U_i,

, а именно:

,
где

, - m-битные комбинации. Определенные n бит результатов последних преобразований g

\binom{1}{N′}

, g

\binom{2}{N′}

,..., g

\binom{r}{N′}

и есть n-битная контрольная комбинация W.

В качестве устройства шифрования можно выбрать "Албер" (патент 2007884). Тогда при n= 64 для подбора другой информации T' с той же контрольной комбинацией W нужно будет перебрать в среднем 10¹⁹ различных T'.

При известном T все g_i,

известны. Для нахождения другой информации T' = T с той же контрольной комбинацией W необходимо для некоторого

подобрать или V≠U, при которой F_v(g_i)=F_U(g_i) или V при которой

. Следовательно, задача сводится к определению ключа в устройстве шифрования "Албер", что невозможно.

Claims

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