Способ формирования n-битной контрольной комбинации n- битной двоичной информации
Патент 2114463
Авторы
Классы МПК
Способ формирования n-битной контрольной комбинации n- битной двоичной информации
Реферат
Изобретение относится к передаче информации. Его использование в связных и вычислительных системах для формирования контрольной двоичной комбинации, а также при цифровом подписывании в качестве "хэш"-функции позволяет обеспечить невозможность подмены информации на другую с той же контрольной комбинацией. Способ заключается в функциональном преобразовании N-битной информации, представленной в виде последовательности электрических импульсов, в n-битную комбинацию. Технический результат достигается благодаря тому, что в качестве функционального преобразования выбирают последовательное шифрование некоторой m-битной комбинации, используя при очередном шифровании в качестве ключа очередную s-битную часть преобразуемой N-битной информации, а в качестве шифруемой информации - m-битный результат предыдущего шифрования, и, после израсходования всех N битов выбирают n-битную контрольную комбинацию из m-битного результата последнего шифрования.
Изобретение относится к передаче информации и может быть использовано в связных и вычислительных системах для формирования контрольной комбинации двоичной информации (например, сообщения), а также при цифровом подписывании в качестве "хэш"-функции для преобразования 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 = Fk(a) . Сначала T разбивается на блоки по s-бит, где s - длина ключа преобразования F, то есть T= U1U2...UN (если блок UN содержит меньше s бит, то он некоторым образом (например, нулями) дополняется до s бит). Затем при m n устройство шифрования N'раз последовательно шифрует некоторое m-битное число а (например, 0) с использованием в качестве ключей s-битных блоков Ui, i = . А именно: , где gi, - m-битные комбинации. Определенные n бит (например, младшие) результаты последнего преобразования gN и есть n - битная контрольная комбинация W. Если m < n, то устройство шифрования N' раз последовательно шифрует некоторые m-битные числа а1, а2,..., аr (например 0,1,..., r-1) с использованием в качестве ключей s-битных блоков Ui, , а именно: , где , - m-битные комбинации. Определенные n бит результатов последних преобразований g1N, g2N,..., grN и есть n-битная контрольная комбинация W. В качестве устройства шифрования можно выбрать "Албер" (патент 2007884). Тогда при n= 64 для подбора другой информации T' с той же контрольной комбинацией W нужно будет перебрать в среднем 1019 различных T'. При известном T все gi, известны. Для нахождения другой информации T' = T с той же контрольной комбинацией W необходимо для некоторого подобрать или VU, при которой Fv(gi)=FU(gi) или V при которой . Следовательно, задача сводится к определению ключа в устройстве шифрования "Албер", что невозможно.Формула изобретения
Способ формирования n-битной контрольной комбинации N-битной двоичной информации, заключающийся в функциональном преобразовании N-битной информации, представленной в виде последовательности электрических импульсов, в n-битную комбинацию, отличающийся тем, что в качестве функционального преобразования выбирают последовательное шифрование некоторой m-битной комбинации, используя при очередном шифровании в качестве ключа очередную s-битную часть преобразуемой N-битной информации, а в качестве шифруемой информации - m-битный результат предыдущего шифрования, и после израсходования всех N битов выбирают n-битную контрольную комбинацию из m-битного результата последнего шифрования.