RU2230438C2

Method for generating encryption-decryption key

Abstract

FIELD: electrical communications and computer engineering; cryptographic data conversion. SUBSTANCE: method involves generation of two binary vectors of a and p numbers, p being prime number and p>=2n-1, where n is key length in bits; transmission of binary vectors of numbers a and p to each network user over unprotected communication channel of network; independent generation of private keys by each of network users and generation of public keys by network users by converting binary vectors of private key and a and p numbers; transmission of public keys over unprotected communication channel to all other network users and generation of common private key by network user for communication with other network user by converting binary vectors of own private key and public key of other network user. EFFECT: enhanced speed of encryption-decryption key generation process; enhanced encryption speed. 1 cl, 1 dwg

Term

No projected expiry on record.

1 claim: 1 independent, 0 dependent

1
The method for forming the encryption key-decryption based on generating two binary vectors of a and p, and 1 <a <2n, and p is a prime number and r≥ 2n-1, where n - the key length in bits, transmission over an insecure communications channel Binary vectors of a and p each network user, generating network users independently of the first secret key xA1, ..., xB1, xA1 wherein - the first secret key of the user A, 1 <xA1 <2n;hV1 - the first in the user's private key, 1 <xV1 <2n and the formation of the first users of the network of public keys by converting binary vectors of the first secret key and the numbers a and p uA1≡ (mod p), ..., uV1≡ (mod p) where uA1 - the first public key of the user A;uV1 - the first public key of user B transmission over an insecure communication channel first public key to all the other users on the network and the formation of the user network to communicate with another user of the first shared secret subkey K1 by converting binary vectors his first secret key and the first public key of another user on the network Способ формирования ключа шифрования-дешифрования, основанный на генерировании двух двоичных векторов чисел а и р, причем 1<а<2n, а р является простым числом и р≥ 2n-1, где n - длина ключа в битах, передачи по незащищенному каналу связи двоичных векторов чисел а и р каждому пользователю сети, генерировании пользователями сети независимо друг от друга первых секретных ключей xA1,..., xB1, где xА1 - первый секретный ключ пользователя А, 1<xA1<2n;хВ1 - первый секретный ключ пользователя В, 1<xВ1<2n и формировании пользователями сети первых открытых ключей путем преобразования двоичных векторов первого секретного ключа и чисел а и р уА1≡ (mоd р),..., уВ1≡ (mod р), где уА1 - первый открытый ключ пользователя А;уВ1 - первый открытый ключ пользователя В, передачи по незащищенному каналу связи первых открытых ключей всем другим пользователям сети и формировании пользователем сети для связи с другим пользователем сети первого общего секретного подключа K1 путем преобразования двоичных векторов своего первого секретного ключа и первого открытого ключа другого пользователя сети KAV1 (mod p);KBA1 (mod p);K1 = KAV1 = KVA1, KАВ1(mod p);KBA1 (mod p);К1=KАВ1=KВА1, where KAB1 - the first shared secret is connected between the users A and B;где KAB1 - первый общий секретный подключ между пользователями А и В;KBA1 - the first shared secret is connected between the users B and A, KBA1 - первый общий секретный подключ между пользователями В и А, characterized in that the network users independently generates a second secret keys xA2, ..., xB2 where xa2 - the second secret key of the user A, 1 <xA2 <2n;hV2 - a second secret key of the user B, 1 <xB2 <2n, forms a second public keys by converting binary vectors and the second secret key of a and p yA2axA2 (mod p), ..., uB2axB2 (mod p), where uA2 - second the public key of the user A, YB2 - the second public key of user B transmits a second public keys over an insecure communication channel to all the other users on the network, formed to communicate with another user of the second shared secret subkey K2 by converting binary vectors his second secret key and a second public key Another netizen KAB2 (mod p);KVA2 (mod p);K2 = KAV2 = KVA2 where KAV2 - the second shared secret is connected between the users A and B;KVA2 - the second shared secret is connected between the users B and A, and to send a message is generated for each session a random binary vector ξ, 1 <ξ <2n, form a binary vector β by adding modulo two bits of random binary vector ξ with bits of binary vector first shared secret subkeys K1, using the binary vector β as the encryption key for seeding a shift register having n bits, and generating a pseudo-random sequence of symbols maximal length 2n-1 to encrypt messages form a binary vector α by modulo-two bits of a random binary vector ξ with bits of binary vector of the second shared secret subkey K2 and transmits it through the communication channel with the encrypted message, and when you receive a message by the network generates a random binary vector ξ by modulo two bits of the received binary vector α with bits of binary vector of the second shared secret subkey K2, and then form a binary vector β by adding modulo two bits of random binary vector ξ with bits of binary vector of the first shared secret subkey K1 and binary vector β lays in the ciphering device is produced using a shift register pseudo-random sequence of characters that is used to decrypt the message. отличающийся тем, что пользователи сети независимо друг от друга генерируют вторые секретные ключи xА2,..., xB2 где хА2 - второй секретный ключ пользователя A, 1<xА2<2n;хВ2 - второй секретный ключ пользователя В, 1<xB2<2n, формируют вторые открытые ключи путем преобразования двоичных векторов второго секретного ключа и чисел а и р yA2axA2(mod p),..., уB2axB2(mod p), где уА2 - второй открытый ключ пользователя А, уВ2 - второй открытый ключ пользователя В, передают вторые открытые ключи по незащищенному каналу связи всем другим пользователям сети, формируют для связи с другим пользователем сети второй общий секретный подключ К2 путем преобразования двоичных векторов своего второго секретного ключа и второго открытого ключа другого пользователя сети КAB2 (mod p);KВА2 (mod p);К2=КАВ2=КВА2, где КАВ2 - второй общий секретный подключ между пользователями А и В;КВА2 - второй общий секретный подключ между пользователями В и А, и для передачи сообщения генерируют для каждого сеанса связи случайный двоичный вектор ξ , 1<ξ <2n, формируют двоичный вектор β путем сложения по модулю два битов случайного двоичного вектора ξ с битами двоичного вектора первого общего секретного подключа K1, используют двоичный вектор β в качестве ключа шифрования для начального заполнения регистра сдвига, имеющего n разрядов и вырабатывающего псевдослучайную последовательность символов максимальной длины 2n-1 для шифрования сообщения, формируют двоичный вектор α путем сложения по модулю два битов случайного двоичного вектора ξ с битами двоичного вектора второго общего секретного подключа К2 и передают его по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения пользователя сети формируют случайный двоичный вектор ξ путем сложения по модулю два битов принимаемого двоичного вектора α с битами двоичного вектора второго общего секретного подключа К2, а затем формируют двоичный вектор β путем сложения по модулю два битов случайного двоичного вектора ξ с битами двоичного вектора первого общего секретного подключа K1 и двоичный вектор β закладывает в шифрующее устройство, вырабатывающее с помощью регистра сдвига псевдослучайную последовательность символов, используемую для дешифрования сообщения.

64 paragraphs, as filed

The invention relates to the field of telecommunications and computer engineering, and more particularly to the field of cryptographic methods and devices for data conversion.

The combination of features of the claimed method uses the following terms:

secret key (or password) is a sequence of bits known only to the legitimate user;

an encryption key-decryption key (shifrklyuch) is a bit combination used in encrypting data information signals; shifrklyuch cipher element is removable and is used to convert a given message or the given totality of messages; shifrklyuch is known only to the legitimate user, or may be generated by a deterministic procedure for the password;

the code is a set of elementary steps of converting input data using shifrklyucha; a cipher may be implemented as a computer program or as a separate device;

Encryption is the process of cryptographic transformation of data blocks using shifrklyucha transforming data into ciphertext, which is a pseudo-random sequence of characters from which to obtain information without knowing the key is practically impossible;

Decryption is the process, reverse the procedure of encryption; decryption ensures the recovery of information on the cryptogram with knowledge shifrklyucha;

binary vector numbers - a signal in the form of a sequence of zero and one bits corresponding representation of the number in the binary system.

Known methods for forming the encryption key-decryption (see., Eg, the Russian standard GOST 28147-89 encryption [1], the British algorithm B-Grypt, US standard DES, Japanese data encryption algorithm FEAL [2], pp. 48-52, and RF patent for invention number 2171012, MPK7 H 04 L 9/08, 9/00, from the application № 2000108296/09 03.04.2000).

In the known methods the formation of the encryption key-decryption performed by using a random number generator with some uncertainty, for example, by selecting bits from the timer. Formed numeric key sent by the user and the network is used as a base (initial values) of the pseudorandom sequence generator numbers. Wherein the output bit stream is summed modulo 2 with the source code to form an encrypted message, and vice versa.

However, the known methods-analogues forming the encryption key-decryption require the use of secure communication channels for transmission to network users generated key.

The closest in its technical essence to the claimed method for generating encryption key-decryption is a method described in US standard protocol DES [2], p. 71, and [3], p.61.

Prototype method includes the formation of the network for all users of two binary vectors of a and p, and the prime p≥2n-1, the choice of network users independently secret key xA, ..., xB, such that 1 <Xx <2n, 1 <xB <2n, the formation of network users public keys uAahA (mod p), ..., uBaxV (mod p), the exchange of public keys of users and each of them forming the common secret KAB subkey (mod p) Kva ( mod p), K = KAV = KBA and subkey using this as a basis for the initial filling of the shift register having n bits and generates a pseudo-random sequence of characters maximum length.

<IMG>

However, the method has the disadvantage of the prototype. Despite the fact that the code is based on the addition of pseudo-random bit stream with plaintext bits modulo 2 is generally unrecognizable theoretically (see [2]. P.128) itself cryptosystem is persistent and not be disclosed. If the structure of the shift register having n-bits is known, to find the initial state of the shift register must know the n characters known plaintext, which are formed on the module 2 with the corresponding n-ciphertext symbols. The resulting n-code pseudorandom sequence determine the state of the shift register at a certain moment in time. Simulating operation of the shift register in the reverse direction, it is possible to determine the initial state, and hence the keys used by the network users in the encryption-decryption information.

If the structure of a shift register having n-bits is unknown, it suffices to 2 n-symbols known plaintext, and their respective 2 n-characters ciphertext to relatively quickly (within a few seconds of the computer) to determine the state of the shift register and to compute used keys (see., eg, [4] p. 93).

Therefore, the keys generated for the encryption-decryption information may be used only once and at the next session, due to be determined by the new. And it leads to considerable complication of the key distribution procedure in a network, since whenever required authentication session and network user authentication through the use of electronic signatures and digital signatures. This reduces the speed of formation of the encryption key-decryption and encryption speed information, as Posts required hashing.

The present invention is directed to increasing the speed of formation of the encryption key-decryption and message encryption speed increase.

This is achieved by the fact that in the known method of forming the encryption key-decryption is to generate to all users via binary vectors of two numbers a and p, and the prime r≥2n-1, to generate network users independently of the secret key that the formation of network users public key exchange network users public keys and the formation of each of them to communicate with other users of the public network of secret connect additional performed generating each user the network independently of each other the second secret keys such that B2 <2n, the formation of the second public key exchange network users second public key and the formation of each of them a second shared secret subkey for communication with other network users to generate for each session for the transmission of the original text of a random binary vector ξ, 1 <ξ <2n, the formation of binary vector β by adding modulo 2 bits random binary vector ξ with bits of binary vector of the first shared secret subkey K1, use binary vector β as the encryption key for the initial filling of the shift register having n-bits and generates a pseudo-random sequence of characters maximum length 2n-1, the formation of binary vector α by addition of modulo 2 bit random binary vector ξ bits binary vector second shared secret subkeys K2 and the transfer of the binary vector α over a communication channel with the encrypted message, and when receiving a message carrying out formation of a random binary vector ξ by modulo-2 addition of the received bits of the binary vector α with bits binary vector of the second shared secret subkey K2 and the formation of the decryption key β by adding modulo 2 bit binary vector of the first shared secret subkey K1 with bits of random binary vector ξ.

<IMG>

Listed set of essential features eliminates the possibility of determining the secret key and shared secret network users are connected, even when using the method of cryptanalysis with a known-plaintext attack. In this case, although it is determined initial state of the shift register, but to determine the secret subkeys K1 and K2 require knowledge of a random binary vector ξ, which is selected for each communication session randomly. Since the statistical methods of cryptanalysis are not applicable in this case, the secret plug K1, K2 can be opened only by a total busting the entire set of keys. In accordance with the Russian standard GOST 28147-89 for the shift register 256 having a memory, the cardinality of the keys will be 1077. If an autopsy will be key with a computer having a clock frequency of 10 GHz, the number of operations performed by this computer for a year will be 3 × 1019, and the time of opening will be a key 3 x 1057 years.

Knowledge cryptanalyst public key, and the numbers a and p transmitted over insecure channels, and does not allow to find the value of the secret key and shared secret network user is connected K1 and K2, as proceedings location reduces to calculating the discrete logarithm of an arbitrary element of a finite field Fp, having a total number of elements 1077. Therefore, the solution of this problem is beyond the technical capabilities of modern computers.

Despite the fact that computer network may be a plurality of users for a method of forming the encryption key-decryption with each of them will use different secret plug inaccessible to other users on the network.

<IMG>

The method may be implemented using a computer or computing device of the block diagram in the drawing, where

Unit 1 - IO device;

unit 4 - device for generating a random binary vector session;

Unit 5 - the device for creating the session key encryption;

For ease of description of the device will use small numbers. We assume that the users on the network use shift registers with 5 memory (key length is 5 bits, n = 5). Then, in the center of the key distribution is determined by two numbers a = 2 and p = 25-1 = 31 and generates binary vectors of these numbers

p = 11111 = 31

and an insecure communication channel is transmitted to all users of the network.

Accepted binary vectors of a and p fixed network users in block 1 and submit them to the unit 2. The unit 2 network users generate secret keys (for example, user A generates a secret key and the user B generates secret keys are fixed and form their public keys (eg , user A generates public keys

<IMG>

<IMG>

As a user generates public keys

<IMG>

The generated public keys supplied in the unit 1, fix them there and transmitted over an insecure communications channel through the key distribution center to other network users. Accepted open prickly other users is fixed at 1 unit.

If user A wants to send an encrypted message to user B, he proceeds as follows:

In block 3 generates a secret user is connected between the user A and B, using the open plug which arrive from the user unit 1, and secret keys from a unit 2:

Document	Relation	Office	Cited during
RU2715163C1	Cited by	Russian Federation	Search report
US9614820B2	Cited by	United States of America	Applicant

Document	Office	Kind	Date
2001135945	Russian Federation	A	2001-12-27
RU20010135945	–	–	–

Method for generating encryption-decryption key

Abstract

Term

Priority claims2

Events

Numbers

Titles2