Изобретение относится к передаче информации и может быть использовано в связных и вычислительных системах для формирования контрольной комбинации двоичной информации (например, сообщения), а также при цифровом подписывании в качестве "хэш"-функции для преобразования N-битной информации (например, сообщения) в n-битную свертку. The invention relates to the transmission of information and can be used in communication and computing systems to generate a control combination of binary information (for example, messages), as well as for digital signing as a “hash” function for converting N-bit information (for example, messages) to n-bit convolution.
Известен способ формирования n-битной контрольной комбинации, заключающийся в функциональном преобразовании некоторым устройством или алгоритмом N бит-информации в n-битную комбинацию, например, путем суммирования n-битных частей N-битной информации [1]. Полученная сумма является контрольной комбинацией. Информация хранится или передается вместе с контрольной суммой. При проверке или получении информации контрольная сумма формируется заново и сравнивается с хранящейся или принятой. При несовпадении вновь сформированной и имеющейся или принятой контрольных сумм делается вывод об искажении информации при хранении или передаче. A known method of forming an n-bit control combination, which consists in the functional conversion by some device or algorithm of N bit information into an n-bit combination, for example, by summing n-bit parts of N-bit information [1]. The amount received is a control combination. Information is stored or transmitted along with a checksum. When checking or receiving information, the checksum is formed again and compared with the stored or received. If the newly formed and existing or accepted checksums do not match, a conclusion is drawn about the distortion of information during storage or transmission.
Данный способ не спасает от преднамеренного искажения информации, позволяя заменить информацию на другую с той же контрольной комбинацией. Например, в случае суммирования n-битных частей N-битной информации можно к одной n-битной части прибавить некоторое число, а из другой n-битной части вычесть то же самое число. Так искаженная информация будет иметь ту же контрольную сумму, что и исходная. This method does not save from deliberate distortion of information, allowing you to replace the information with another with the same control combination. For example, in the case of summing n-bit parts of N-bit information, you can add a certain number to one n-bit part, and subtract the same number from another n-bit part. So the distorted information will have the same checksum as the original.
Целью изобретения является обеспечение невозможности подмены информации на другую с той же контрольной комбинацией. The aim of the invention is to ensure the impossibility of substituting information for another with the same control combination.
Поставленная цель достигается тем, что при формировании n-битной контрольной комбинации N-битной информации (например, сообщения, преобразованного в дискретную последовательность электрических импульсов) в качестве функционального преобразования выбирают последовательное шифрование устройством или алгоритм шифрования некоторого m-битного числа, используя при очередном шифровании в качестве ключа очередную s-битную часть преобразуемой информации, а в качестве шифруемого числа - m-битный результат предыдущего шифрования. This goal is achieved by the fact that when generating an n-bit control combination of N-bit information (for example, a message converted into a discrete sequence of electrical pulses), a serial encryption by the device or an encryption algorithm of a certain m-bit number is selected as the functional transformation, using the next encryption as the key, the next s-bit part of the converted information, and as the encrypted number, the m-bit result of the previous encryption.
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.N-bit information T is converted to an n-bit combination W using an encryption device that implements the encryption algorithm F, as follows (the encryption device converts the m-bit source combination, and into the m-bit encryption combination b using the s-bit key k: b = F k (a). First T is divided into blocks by s-bits, where s is the length of the transformation key F, that is, T = U 1 U 2 ... U N (if the block U N ′ contains less than s bits, then it is supplemented in some way (for example, with zeros) to s bits.) Then, for m ≥ n, the encryption device N'times sequentially encrypts some Roe m-bit number a (for example, 0) by using as keys s-bit units U i, i = . Namely:
,
Where
g i - m-bit combinations. Certain n bits (for example, the least significant) results of the last conversion g N ′ are the n - bit control combination W.
Если m < n, то устройство шифрования N' раз последовательно шифрует некоторые m-битные числа а1, а2,..., аr (например 0,1,..., r-1) с использованием в качестве ключей s-битных блоков Ui, , а именно:
,
где
, - m-битные комбинации. Определенные n бит результатов последних преобразований g , g ,..., g и есть n-битная контрольная комбинация W.If m <n, then the encryption device N 'times sequentially encrypts some m-bit numbers a 1 , 2 , ..., and r (for example, 0,1, ..., r-1) using s as keys -bit blocks U i , , namely:
,
Where
, - m-bit combinations. Defined n bits of the results of recent transformations g , g , ..., g and there is an n-bit control combination W.
В качестве устройства шифрования можно выбрать "Албер" (патент 2007884). Тогда при n= 64 для подбора другой информации T' с той же контрольной комбинацией W нужно будет перебрать в среднем 1019 различных T'.As the encryption device, you can select "Albert" (patent 2007884). Then, for n = 64, in order to select other information T 'with the same control combination W, it will be necessary to sort out on average 10 19 different T'.
При известном T все gi, известны. Для нахождения другой информации T' = T с той же контрольной комбинацией W необходимо для некоторого подобрать или V≠U, при которой Fv(gi)=FU(gi) или V при которой . Следовательно, задача сводится к определению ключа в устройстве шифрования "Албер", что невозможно.Given T, all g i , known. To find other information, T '= T with the same control combination W is necessary for some choose either V ≠ U for which F v (g i ) = F U (g i ) or V for which . Therefore, the task is reduced to determining the key in the Alber encryption device, which is impossible.