RU2371864C1 - Method of forming and checking electronic text message certified with digital water-mark - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: method consists in the fact that there preliminarily formed for a sender and an addressee is a binary sequence of common secret key and hashing function with binary output value; minimum allowable K_min number of original groups of binary sequences of an electronic message from K received groups is set; K≥K_min groups of binary sequences are extracted from the binary sequence of electronic message; electronic message is certified by the sender with digital water-mark by means of pre-formed hashing function and binary sequence of secret key, and the message is transmitted to the addressee; authenticity of the electronic message received with the addressee is checked by means of pre-formed functions of hashing and binary sequence of secret key; in addition, as an electronic message there used is an electronic text message, each symbol of which is represented in the form of its specified binary sequence, and besides there formed is secret key of the sender, which consists of the first, the second, the third and the fourth binary sequences, as well as secret key of the addressee, which consists of the first, the second and the third binary sequences. The proposed method can be used for identifying authenticity of electronic text messages transmitted in modern information telecommunication systems.

EFFECT: increasing protection of the message certified with digital water-mark of the sender against intentional actions of external breakers or potential internal breakers as per the change of its content.

6 cl, 9 dwg

Description

The invention relates to the field of telecommunications and information technology, in particular to a technique for protecting the authenticity of electronic text messages created by electronic text editors such as Word, Write, Notepad, etc. A genuine electronic text message means such an alphanumeric message created by the sender and received by the recipient in which there are no unauthorized changes to its content.

The claimed method can be used to establish the authenticity of electronic text messages transmitted in modern information and telecommunication systems.

Known methods for verifying the authenticity of electronic text messages based on calculation by the sender and verification by the recipient of a secure insertion of this message. These methods relate to cryptographic methods for verifying the authenticity of electronic text messages and are described, for example, in state standard 28147-89. Information processing systems. Cryptographic protection. Cryptographic conversion algorithm. - M .: Gosstandart of the USSR, 1989. In these methods, an electronic text message, consisting of alphanumeric and other characters, is converted into a binary sequence of an electronic text message, which is divided by the sender into consecutive blocks of length n bits, where usually n = 64. Using the encryption function using a secret key binary sequence preformed for the sender and recipient, the encrypted current block is generated sequentially from each block taking into account the previous encrypted block until the binary sequence of the electronic text message arrives. From the last encrypted block, a binary sequence of length l <n bits is extracted, which is called the fake insert of this message. Then the electronic text message itself and its security-sensitive insert are transmitted via a communication channel or recorded on electronic media such as CDs and floppy disks. An electronic text message received by the recipient is checked, for which purpose its binary sequence is re-divided into consecutively received blocks of length n bits, using the encryption function using the binary sequence of the secret key, the next encrypted received block is formed sequentially from each received block, taking into account the previous encrypted block, until while the binary sequence of the received electronic text message arrives. From the last encrypted received block, a binary sequence of a fake insert with a length l <n bits of a received message is extracted, and when the newly formed and received fake inserts coincide completely, the received electronic text message is considered authentic.

The disadvantages of these analogues are the need for additional transmission of an improtected insertion of an electronic text message, which leads to an additional consumption of transmission channel capacity or storage capacity, as well as low security of electronic text messages verified by a cryptographic imitation from the effects of random or intentional transmission channel errors. If one or more errors of the transmission channel occur, the newly formed, impervious insertion of the received electronic text message will significantly differ from the one generated on the transmitting side, and the received electronic text message will be recognized by the recipient as inauthentic, even if its meaning has not changed due to errors.

Also known are methods of generating and verifying a digital watermarked electronic text message. In recent years, such methods have been developed within the framework of steganographic methods for protecting information. These methods are described, for example, in the book: V.G. Gribunin, I.N. Okov, I.V. Turintsev. Digital steganography. M .: Solon-R, 2002, page 6-17. The main idea of these methods is to embed a special label in a certified electronic text message - a digital watermark (CEH) using a secret key. This CEH is a unique identifier, and the fact of extracting this CEH from a received electronic text message using a secret key allows the recipient to make sure that the content of the message authenticated with this watermark is not changed or formed as a result of malicious actions. By analogy with watermarks certifying the authenticity of banknotes on paper, these identifiers are called the digital watermark of an electronic text message. Digital watermarks of messages can be visually perceptible, for example, an image of a registered trademark of a manufacturer or an image of a sender's face, and visually not perceptible, for example, a binary sequence extracted from a received electronic message registered as a personal identification number (PIN) of the sender of electronic text messages.

Embedding with a sender in a certified electronic text message a digital watermark is performed using a secret key unknown to the violator. At the verification stage, a digital watermark is extracted from the received electronic text message using the same secret key, which is compared with the original digital watermark, and if they match, a decision is made that there is no distortion in the received electronic text message. An intruder who knows a digital watermark but does not know a secret key is not able to generate an electronic text message certified by a digital watermark, which, when verified, the receiver recognizes as genuine.

Known methods for generating and checking a digital watermarked electronic text message are described, for example, in the book: Bender W., Gruhl B., Morimoto N., Lu A. Techniques for data hiding / LAN systems journal. 1996. Vol. 35. Number 3. They consist in preliminary formation for the sender and recipient of the binary sequence of a digital watermark of length K bits and a binary sequence of a secret key of length N> K bits. The binary sequence of a digital watermark is the same for any electronic text message authenticated by the sender. To assure the sender of the electronic text message, his binary sequence is divided into blocks of characters with a length of N characters. In the binary representation of the characters of an electronic text message, there are binary bits that are not used in the usual operations of processing these messages. To generate an electronic text message certified by a digital watermark, the current message block is allocated. If the i-th bit, where i = 1, 2, ..., N, of the binary sequence of the secret key has a single value, then the value of the next bit of the binary sequence of the digital watermark is written to the unused binary bit of the i-th character of the current block of the electronic text message. After the last bit of the digital watermark sequence has been recorded, the current block of the electronic text message as transmitted by the digital watermark is transmitted to the recipient. The next block of the electronic text message is isolated and the subsequent actions are performed until a binary message sequence is received.

To verify the authenticity of the electronic text message received by the recipient, starting with the first character, the binary sequence of the received message is divided into received blocks of length N characters. The currently received electronic text message block is allocated. If the i-th bit, where i = 1, 2, ..., N, of the binary sequence of the secret key has a single value, then the value of the next bit of the received binary sequence of the digital watermark is read from the unused binary bit of the i-th character of the current received block of the electronic text message and compared with the value of the next bit of the binary sequence of the digital watermark. If during authentication all the values of the next bits of the received binary sequence of the digital watermark coincide with the values of the next bits of the binary sequence of the digital watermark, then the current received block of the electronic text message is recognized as authentic by the recipient. Then, the authentication steps of the next received block of the electronic text message are repeated, and so on until the complete reception of the entire binary sequence of the received message is completed. If during authentication all accepted blocks of an electronic text message are recognized as authentic, then all received message is considered authentic.

A disadvantage of the known methods for generating and checking a digital watermarked electronic text message is the low security of the digitally watermarked message from the intentional actions of external or potential internal violators (legal sender or recipient) to change the content of the message. If you intentionally change the content of an electronic text message authenticated by a digital watermark, an external intruder can change any binary bits of the message block symbols, except for an unused binary digit. The recipient of the modified message, performing the described verification steps, erroneously recognizes the received message as genuine. Thus, an external intruder has the ability to convert an electronic text message certified by a digital watermark into a false message. Therefore, the known methods do not provide protection of a digital watermarked electronic text message from an attack by an external intruder, called a first-order message spoofing attack. An unscrupulous sender of an electronic text message may act as an internal violator. He prepares two different electronic watermarked electronic text messages, transmits the first one to the recipient, and subsequently refuses him, claiming that he allegedly transmitted the second electronic watermark authenticated with a digital watermark, and the recipient replaced it with the first. Such an attack on the part of the internal sender-intruder is called a renegade attack and is potentially possible if the sender and the recipient respectively use the same binary sequence of the secret key to generate and verify a digital watermark. An unscrupulous recipient of an electronic text message certified by a digital watermark can also act as an internal violator. He accepts an electronic text message certified by a digital watermark from a bona fide sender and transmits it into another message that is beneficial for the recipient and certified by a digital watermark and claims that it was the message sent to him by the sender. Such an attack from the side of the internal intruder-receiver is called a remake attack and is potentially possible if the sender and receiver use the same binary sequence of the secret key to generate and verify the digital watermark.

The closest in technical essence to the claimed method of generating and verifying an electronic text message authenticated with a digital watermark is the method of generating and verifying an electronic message authenticated with a digital watermark according to RF patent 2258315, IPC ⁷ H04L 9/00 of 08/10/05. The prototype method of generating and verifying an electronic message authenticated by a digital watermark consists in preliminary generation of a secret key and a hash function with a binary output value for the sender and receiver of the binary sequence. Set the minimum allowable number K _{min of} genuine groups of binary sequences of the electronic message in the group of K received groups. And also set the maximum value of the probability P _err erroneous allocation of reference, corresponding to the first bit of the binary sequence a digital watermark in the electronic message sender.

To assure the sender of the electronic message using the hash function and the secret key, the kth is read out sequentially, where k = 1, 2, ..., K, the bit of the binary sequence of the digital watermark, the binary sequence of the next sample of the electronic message and the binary sequence of the secret key. The binary sequence of the next count of the electronic message is hashed using the hash function and the binary sequence of the secret key previously generated and the hashed value is compared with the kth bit of the binary sequence of the digital watermark.

If the hashed value coincides with the kth bit of the digital watermark binary sequence, the binary sequence of the next count of the electronic message is transmitted to the recipient as authenticated, and if the hashed value does not match the kth bit of the digital watermark binary sequence, the binary sequence of the next count of the electronic message is sequentially converted by changes of its least significant bits, for which they convert the binary sequence of the next count of electrons A message by sequentially changing its one, two, three, and so on low bits, hashes after each conversion the converted binary sequence of the next sample of the electronic message according to the previously generated hashing function and the binary sequence of the secret key and compares the hashed value with the kth bit of the digital binary sequence watermark.

The binary sequence of the next sample of the electronic message is converted until the hashed value of the converted binary sequence of the next sample of the electronic message coincides with the kth bit of the binary sequence of the digital watermark, and then the last converted binary sequence of the next sample of the electronic message is transmitted to the recipient as certified.

After verifying the binary sequence of the next count of the electronic message using the Kth bit of the binary sequence of the digital watermark, the kth bit of the binary sequence of the digital watermark and the binary sequence of the next count of the electronic message are read again, starting from the first to the Kth, and the following actions to certify the sender with a digital watermark of the message until binary sequences of successive samples of the electronic message arrive eniya.

After transmission of the electronic message certified by a digital watermark, a sample corresponding to the first bit of the binary sequence of the digital watermark from the sender of the electronic message is extracted from the received binary sequences of the subsequent samples of the electronic message, for which purpose the binary sequences of the next samples of the electronic message received by the receiver are hashed by the hash and binary functions private key sequences and compare sequences tion with the corresponding hashed values, starting with the first bit of the binary sequence values of the digital watermark to achieve their M consecutive matches.

Upon reaching M matches in a row, the first sample of K sequentially received binary sequences of the next samples of the electronic message is received corresponding to the first bit of the binary sequence of the digital watermark from the sender of the electronic message.

To verify the authenticity of the received electronic message with the recipient using pre-generated hash functions and the binary sequence of the secret key, K sequences of successive samples of the received electronic message are read sequentially and the binary sequences of the next samples of the received electronic message are hashed by the pre-generated hash function and the binary sequence of the secret key. The k-th hashed value is compared with the k-th bit of the binary sequence of the digital watermark and the number K _{from the} hashed binary sequences of successive samples of the electronic message from the K received samples coinciding with the values of the corresponding bits of the binary sequence of the digital watermark is calculated.

When K _with ≥K _{min, the} received binary sequences of the next samples of the electronic message are considered authentic to K, after which the steps to verify the authenticity of the next group of K received binary sequences of the next samples of the electronic message are repeated, and the actions of the recipient of the received electronic message are repeated until all reception is completed binary sequences of its next samples.

The disadvantage of the prototype of the claimed method of generating and verifying a digital watermarked electronic text message is the low security of the message, authenticated by the digital watermark of the sender, from the deliberate actions of external or potential internal violators to change the content of the message. This is due to the fact that an external intruder is able to change the content of an electronic text message in the form of a large-order spoofing attack L. In this attack, an external intruder observes a large number L≥10 ^-4 ... 10 ^-5 electronic text messages authenticated using the same binary digital watermark sequences and binary secret key sequences. With an unclassified binary sequence of a digital watermark, an external intruder is able to recognize a large number of order L · K of certified binary sequences of samples of electronic text messages. He has the opportunity to form a false electronic text message from this set of certified binary sequences of samples, which, with the described verification actions, the recipient will be mistakenly accepted as genuine.

The aim of the invention of the claimed technical solution is to develop a method for generating and checking an electronic text message authenticated with a digital watermark, which increases the security of the message authenticated by the sender's digital watermark from intentional actions by external or potential internal violators to change its content.

This goal is achieved by the fact that in the known method of generating and checking an electronic watermarked electronic message, which consists in preliminarily generating for the sender and recipient of the binary sequence a shared secret key and a hash function with a binary output value, the minimum allowable number K _{min of} genuine groups of binary sequences is set an electronic message received from the K groups of electronic messages binary sequence isolated K≥K groups _min sequence of keys, assure the sender of the electronic message using the pre-formed hash function and the binary sequence of the secret key and transmit it to the recipient, verify the authenticity of the electronic message received by the recipient using the pre-formed hash function and the binary sequence of the secret key, in addition, use the electronic text message a message, each character of which is represented as its specified voichnoy sequence. Additionally, the sender’s secret key is formed, consisting of the first, second, third and fourth binary sequences, as well as the recipient’s secret key, consisting of the first, second and third binary sequences, and the shared secret key is formed in the form of the first and second binary sequences. The first and second binary sequences of the sender’s secret key and the third binary sequence of the recipient’s secret key of length K bits are formed randomly and equally, and the k-th bits of the remaining binary sequences of the sender’s secret key of length K bits and the recipient’s secret key of length K bits are determined to correspond to the simultaneous equality on the one hand, the kth bit of the third binary sequence of the sender’s secret key and, on the other hand, the product of the kth bit of the first binary the sender’s secret key sequence and the kth bit of the second recipient’s private secret binary sequence, folded modulo 2 with the kth bit of the first recipient’s private secret key sequence and equality, on the one hand, the kth bit of the fourth sender’s secret binary key sequence and , on the other hand, the product of the kth bit of the second binary sequence of the sender’s secret key and the kth bit of the second binary sequence of the recipient’s secret key, modeled u 2 k-th bit of the third binary sequence secret key of the recipient.

Pre-set for the characters of an electronic text message, a set of replacement characters that do not change the visual perception of this message.

The minimum allowable number K _{min of} genuine groups of binary sequences of an electronic text message from K received groups is determined from the condition

- число сочетаний из К по µ, a L - число заверенных цифровым водяным знаком с помощью двоичных последовательностей общего секретного ключа и двоичных последовательностей секретного ключа отправителя электронных текстовых сообщений. Также предварительно устанавливают максимально допустимое значение вероятности P_ош ошибочного выделения двоичной последовательности символа, принадлежащего первой двоичной последовательности первой заверенной цифровым водяным знаком группы двоичных последовательностей, и устанавливают значение

, а действие

означает округление значения - log₂Р_ош до ближайшего целого.where P _add - pre-defined acceptable probability of acceptance by authentic To the accepted groups of binary sequences of electronic text messages that are not authentic,

is the number of combinations of K in μ, and L is the number certified with a digital watermark using binary sequences of the shared secret key and binary sequences of the secret key of the sender of electronic text messages. Also, the maximum permissible probability value _{Psh of the} erroneous selection of the binary sequence of a symbol belonging to the first binary sequence of the first binary watermarked group of binary sequences is pre-set, and the value is set

, and the action

means rounding the value - log ₂ Р _osh to the nearest integer.

To assure the sender with a digital watermark of an electronic text message, K groups of binary sequences are extracted from the binary sequence of the electronic text message using the first binary sequence of the shared secret key. Consistently k-th, where k = 1, 2, ..., K, the group of binary sequences is divided into the first and second parts, then the entire k-th group of binary sequences and its first and second parts are separately hashed by the previously generated hash function and the second binary shared secret key sequences. Then check the compliance of the hashed values of the entire k-th group of binary sequences and its first and second parts to the k-th bits of the first, second, third and fourth binary sequences of the sender's secret key. The correspondence of the hashed values of the entire kth group of binary sequences and its first and second parts to the kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key is established by simultaneously fulfilling the equality, on the one hand, of the hashed value of the first part of the kth group of binary sequences and, on the other hand, the product of the hashed value of the entire kth group of binary sequences and the kth bit of the second binary sequence of the sender’s secret key, folded modulo 2 with the kth bit of the first binary sequence of the sender’s secret key and the equality, on the one hand, of the hashed value of the second part of the kth group of binary sequences and, on the other hand, the product of the hashed value of the entire kth group of binary sequences and k -th bit of the fourth binary sequence of the sender’s secret key, folded modulo 2 with the kth bit of the third binary sequence of the sender’s secret key.

When the correspondence is established, the hashed value of the first part of the kth group of binary sequences is accepted as the next bit of the first binary sequence of the digital watermark of the electronic text message and as the next bit of the second binary sequence of the digital watermark of the electronic text message the hashed value of the second part of the kth group of binary sequences and transmit to the recipient the k-th group of binary sequences as digitally certified an infamous sign. When a mismatch is established, the characters in the kth group of binary sequences are successively replaced by the characters from the ones from the predefined set of replacement characters, after which the entire kth converted group of binary sequences and its first and second parts are hashed separately by the preformed hash function and the second binary shared secret key sequences.

Once again, the hashed values of the entire kth converted group of binary sequences and its first and second parts are checked for kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key, and the steps for replacing characters in the kth converted group of binary sequences are its hashing and checking the conformity of its hashed values is carried out before it is established, after which they are taken as the next bits of the first and second binary sequences of digits Vågå electronic watermark text message hashed values of the first and second parts of k-th band converted binary sequences, respectively, are transmitted to the recipient k-th converted binary sequence group as a certified digital watermark. The steps to certify the sender with a digital watermark of an electronic text message are repeated until its binary sequence arrives.

After transmitting the digital watermarked electronic text message from the binary sequence of the electronic text message received by the recipient, a binary sequence of a symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences is extracted, for which, from the received binary sequence of the electronic text message, starting with the binary sequence of the first character emit using the first binary n sequence common secret key K received groups of binary sequences. Consistently, the kth received group of binary sequences is divided into the first and second parts, the entire kth received group of binary sequences and its first and second parts are separately hashed by the preformed hash function and the second binary sequence of the shared secret key and the correspondence of the hashed values of the entire k received group of binary sequences and its first and second parts to k-th bits of the first, second and third binary sequences of the recipient's secret key . The correspondence of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key is established by performing the equality, on the one hand, of the hashed values of the second part of the kth received group of binary sequences and, on the other hand, the product of the hashed value of the entire kth received group of binary sequences and the kth bit of the third binary sequence of the recipient's secret key Folded modulo 2 k-th bit of the first binary sequence a private key of the recipient and the product of the first part of the hashed values k-th received group of binary sequences and the k-th bit of the second binary sequence secret key of the recipient.

When 1 <M≤K matches, the selected binary character sequence is taken as the binary character sequence belonging to the first binary sequence of the first binary watermarked group of binary sequences. Otherwise, the steps for extracting the binary sequence of the character belonging to the first binary sequence of the first digital watermarked group of binary sequences are repeated with the binary sequence of the next character of the received binary sequence of the electronic text message.

After highlighting the binary sequence of the symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences, the recipient checks the authenticity of the received electronic text message, for which starting from the binary sequence of the symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences using the first shared secret shared binary sequence ca K received groups of binary sequences, sequentially k-th received group of binary sequences is divided into first and second portions. The entire kth received group of binary sequences and its first and second parts are separately hashed by the preformed hash function and the second binary sequence of the shared secret key, the compliance of the hashed values of the entire kth received group of binary sequences and its first and second parts k- is checked ith bits of the first, second and third binary sequences of the recipient's secret key.

The correspondence of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key is established by performing the equality, on the one hand, of the hashed values of the second part of the kth received group of binary sequences and, on the other hand, the product of the hashed value of the entire kth received group of binary sequences and the kth bit of the third binary sequence of the recipient's secret key Folded modulo 2 k-th bit of the first binary sequence a private key of the recipient and the product of the first part of the hashed values k-th received group of binary sequences and the k-th bit of the second binary sequence secret key of the recipient.

When establishing the number of matches K _with ≥K _{min, the} received K groups of binary sequences of the electronic text message are considered authentic, and then the steps to verify the authenticity of the next K received groups of binary sequences are repeated until the entire binary sequence of the electronic text message is received.

The specified new set of actions performed due to the unpredictable dependence of the binary sequence of the electronic watermark authenticated by the digital watermark on the first and second binary sequences of the shared secret key, as well as on the dependence of the first and second binary sequences of the digital watermark on the binary sequence of the electronic text message, binary sender private key sequences and binary sequences the recipient’s key, and also due to the binary sequences of the recipient’s secret key unpredictable for the potential internal intruder-sender and the sender’s secret key binary sequences unpredictable to the potential internal intruder-recipient, it can increase the security of the electronic text message authenticated by the sender’s digital watermark actions of external or potential internal violators to change it content.

The claimed method is illustrated by drawings, which show:

- figure 1 is an algorithm for generating a digital watermarked electronic text message;

- figure 2 is a timing diagram of the formation of a digital watermark certified electronic text message;

- figure 3 is an example of a fragment of an electronic text message in the form of binary sequences of characters of the standard KOI8-R;

- figure 4 is a typical example of the hashing of the entire group of binary sequences and its first and second parts for the hash function and the second binary sequence of the shared secret key;

- figure 5 is an algorithm for extracting from a binary sequence received by a recipient of an electronic text message a binary sequence of a character belonging to a first binary sequence of a first group of binary sequences authenticated with a digital watermark;

- Fig.6 is a timing diagram of the allocation from the received by the recipient of a binary sequence of electronic text message binary sequence of a character belonging to the first binary sequence of the first digital watermarked group of binary sequences;

- Fig.7 - authentication algorithm of the received electronic text message, synchronized with a digital watermarked electronic text message;

- Fig. 8 is a timing chart of an authentication of a received electronic text message synchronized with a digital watermarked electronic text message;

- figure 9 is a graph showing the effect of the proposed method.

The implementation of the claimed method is as follows.

To protect the authenticity of electronic text messages transmitted over modern information and telecommunication networks, from the binary sequence of an electronic text message using the first and second binary sequences of the shared secret key and the first, second, third and fourth binary sequences of the sender’s secret key, it is calculated and embedded in the certified message authentication information called the first and second binary sequence of digital water sign of electronic text message. An algorithm for generating a digital watermarked electronic text message is shown in FIG.

The first and second binary sequences of the shared secret key are shown in FIGS. 2 (a) and 2 (b), respectively. Single bit values in the figures are shown in the form of shaded pulses, zero bit values in the form of unshaded pulses. The first and second binary sequences of the shared secret key are required to be impossible to calculate by an external intruder, who may be aware of electronic text messages certified with their use.

The first, second, third and fourth binary sequences of the sender’s secret key are shown in FIGS. 2 (c), 2 (d), 2 (e) and 2 (e), respectively.

A binary sequence view of an electronic text message is shown in FIG. 2 (g). The binary sequence of an electronic text message in accordance with the rules for its presentation in computer systems is divided into successive binary sequences, starting from the first to the last, each of which encodes one character of the electronic text message. Known rules for encoding characters in English and other alphabets, including the Russian alphabet, as well as numbers, punctuation marks, service characters, etc., such as ANSII, Windows-1251, KOI8-R, are defined in international standards, for example, such as RFC -2822, RFC-1489, ISO-8859-5, which is described, for example, in the book of M. Mamaev, S. Petrenko. Technologies for protecting information on the Internet. Special reference. - St. Petersburg: Peter, 2002, p. 50-51. In binary sequences of characters, the least significant bit is written first (on the left in FIG. 2 (g)), the highest bit is recorded in binary sequences last (on the right in FIG. 2 (g)).

In known methods for generating and verifying an electronic text message verified by a digital watermark, a preformed binary sequence of a digital watermark is bitwise embedded in the least significant bits of the binary sequences of the message, as described, for example, in the book by A.P. Romancev. A statistical method for revealing the steganographic concealment of information in sound files: Materials of the International Informatization Forum MFI-2000. - M .: CJSC "Informsvyazizdat", 2000, p.203-204.

An external intruder may try to destroy a digital watermark embedded in a certified electronic text message or make it undetectable by known methods of verifying digital watermarked messages. If the intruder managed to destroy the built-in digital watermark or make it undetectable, the recipient considers the received electronic text message to be authentic, even if its content has not changed.

To determine the binary sequence number of an electronic text message, starting from which it is necessary to start the extraction of the binary sequence of a digital watermark during verification, in the known methods for generating and checking an electronic text message verified by a digital watermark, the binary sequence of the digital watermark is embedded in the message sign. If during the authentication of the received electronic text message received by the recipient, the binary sequence of the digital watermark label is identified, then the beginning of the binary sequence of the digital watermark embedded in this message is uniquely determined. Therefore, if under the influence of random transmission errors or deliberately by an external intruder, one or more bits of the binary sequence of the authenticated electronic message, in which the binary sequence of the digital watermark mark is embedded, is distorted, then the mark will not be detected during authentication of the recipient of the electronic text message, and as a result Digital watermark will not be read. The binary sequence of the digital watermark label is generally well known, and therefore is easily detected and distorted by the intruder in a certified electronic text message. Increasing the resistance to the deliberate actions of the intruder can be achieved if you do not use a special binary sequence of the digital watermark label and determine the beginning of the digital watermark binary sequence integrated into the electronic text message using the binary digital watermark sequence itself using the shared secret key binary sequences known to the recipient and binary recipient secret key sequences.

If the authenticated electronic text message is embedded in which the binary sequence of the digital watermark is embedded, then in known methods, when checking the binary sequence of the digital watermark extracted from this message will not be identified with the reference binary sequence of the digital watermark of the electronic text message, since they require their matches accurate to bits. Therefore, an increase in resistance to the effects of random transmission errors or to the deliberate actions of an intruder can be achieved by using a binary digital watermark sequence that can be identified with a reference digital watermark binary sequence if there are distortions in one or more bits of the digital watermarked binary sequence electronic text message.

In the inventive method, to ensure the formation and verification of a digital watermark verified by an electronic text message, which increases the security of the message authenticated by a digital watermark, to the deliberate actions of violators to change the message content, the following sequence of actions is implemented.

Preliminary formation for the sender and recipient of the first and second binary sequences of a shared secret key is as follows. These sequences are generated using a random pulse generator, which generates random equally probable zero and single pulses, independent of each other. Moreover, the first binary sequence of the shared secret key is independent of the second binary sequence of the shared secret key. Methods of randomly generating binary sequences of the first and second binary sequences of a common secret key are known and described, for example, in the book: D. Knut. "The art of computer programming." - M .: Mir, 1977, v. 2, p. 22. The lengths of the first and second binary sequences of the shared secret key must be at least 64 bits, which is described, for example, in the book of M.D.Smid, D.K. Bransted. "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 45.

Preliminary generation of the sender’s secret key, consisting of the first, second, third and fourth binary sequences, as well as the recipient’s secret key, consisting of the first, second and third binary sequences, is as follows. First, the first and second binary sequences of the sender’s secret key, each with a length of K bits, and the third binary sequence of the recipient’s secret key with a length of K bits are randomly and equally likely generated. These sequences are formed using a random pulse generator, forming random equally probable zero and single pulses, independent of each other. Moreover, these binary sequences are independent of each other. The first and second binary sequences of the sender’s secret key of length K bits and the third binary sequence of the recipient’s secret key of length K bits are formed by randomly selecting the sequences of binary symbols generated by the random pulse generator. Methods of randomly generating binary sequences of the first and second binary sequences of the sender’s secret key of length K bits and the third binary sequence of the recipient’s secret key of length K bits are known and described, for example, in the book: D. Knut. "The art of computer programming." - M .: Mir, 1977, v. 2, p. 22.

Then, the kth bits of the remaining binary sequences of the sender’s secret key with a length of K bits and the recipient’s secret key with a length of K bits are determined by the simultaneous execution of two equalities. In the first of them, the identity, on the one hand, of the kth bit of the third binary sequence of the sender’s secret key and, on the other hand, of the product of the kth bit of the first binary sequence of the sender’s secret key and the kth bit of the second binary sequence of the recipient’s secret key must be satisfied , folded modulo 2 with the kth bit of the first binary sequence of the recipient's secret key. In the second equality, the identity, on the one hand, of the kth bit of the fourth binary sequence of the sender’s secret key and, on the other hand, of the product of the kth bit of the second binary sequence of the sender’s secret key and the kth bit of the second binary sequence of the recipient’s secret key must be satisfied, folded modulo 2 with the kth bit of the third binary sequence of the recipient's secret key. These actions of generating binary sequences of sender's private keys and binary sequences of recipient's private keys to provide increased protection against actions by external and potential internal intruders are known and described, for example, in the book Johansson T. On the construction of perfect authentication codes that permit arbitration. Advances in Cryptology. Proc. Crypt-93. Springer-Verlag. 1993. p. 343-354. Ways to perform the product of bit values, their addition modulo 2 and comparison are known and described, for example, in the book of A.L. Lantsov, L.N. Zvorykin, I.F. Osipov. "Digital devices on complementary TIR integrated circuits." - M.: Radio and Communications, 1983, pp. 153-164.

The preliminary generation of a hash function with a binary output value for the sender and receiver is as follows. Known methods for preliminary formation of the hash function are described, for example, in the book of M.D. Smid, D.K. Bransted. "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 49. They consist in generating a hash function according to the second binary sequence of the shared secret key, using the DES data encryption algorithm in ciphertext feedback mode or in output feedback mode. However, these methods of pre-generating a hash function generate a hash function with an output value of 64 bits. Therefore, to generate a hash function with a binary output value, it is proposed to convert the output value of 64 bits of the hash function generated in the known methods by modulo 2 calculation. As a result of this conversion, even output values of 64 bits will take a binary zero value, and odd output values of 64 length bits will take a binary single value. The conversion of a binary sequence by calculation modulo 2 is known and described, for example, in the book of B.A. Kalabekov. "Microprocessors and their use in signal transmission and processing systems." - M.: Radio and Communications, 1988, p. 10.

The preliminary establishment for the characters of an electronic text message of a set of replacement characters that do not change the visual perception of this message is as follows. In Russian, English and other alphabets there are a number of characters that have the same style, for example, the characters "o", "e", "a", "k", etc. However, in accordance with the rules of character encoding in encoding standards, such as, for example, ANSII, Windows-1251, KOI8-R, the binary sequences of these and similar characters of different alphabets in electronic text messages are different, as described, for example, in the book of M. Mamaev , S. Petrenko Internet Information Protection Technologies. Special reference. - St. Petersburg: Peter, 2002, p. 50-51. Therefore, for such characters of an electronic text message that do not change the visual perception of this message when they are read from the screen of an optoelectronic device or from a printed paper copy, one or more replacement characters are set in advance.

The preliminary establishment for the sender and recipient of the minimum allowable number K _{min of} genuine groups of binary sequences of an electronic text message from K received groups is as follows. The minimum allowable number K _{min of} genuine groups of binary sequences of an electronic text message from K. the accepted groups are determined from the condition

- число сочетаний из К по µ, а L - число заверенных цифровым водяным знаком с помощью двоичных последовательностей общего секретного ключа и двоичных последовательностей секретного ключа отправителя электронных текстовых сообщений. Например, величину допустимой вероятности принятия подлинными К принятых групп двоичных последовательностей электронного текстового сообщения, являющихся неподлинными, устанавливают равной Р_доп=10^-9, что рекомендуется, например, в государственном стандарте 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР, 1989. Следовательно, задав величину порядка атаки подмены, например, L=10⁶ и величину К=100, что рекомендуется в книге Окова И.Н. Аутентификация речевых сообщений и изображений в каналах связи. / Под ред. проф. В.Ф.Комаровича. - Издательство Санкт-Петербургского политехнического университета, 2006, стр.198, целесообразно установить величину K_min не менее 82.where P _add - pre-defined acceptable probability of acceptance by authentic To the accepted groups of binary sequences of electronic text messages that are not authentic,

is the number of combinations of K in μ, and L is the number certified with a digital watermark using binary sequences of the shared secret key and binary sequences of the secret key of the sender of electronic text messages. For example, the value of the admissible probability of acceptance by authentic K of accepted groups of binary sequences of electronic text messages that are not authentic is set to P _add = 10 ^-9 , which is recommended, for example, in state standard 28147-89. Information processing systems. Cryptographic protection. Cryptographic conversion algorithm. - M .: Gosstandart of the USSR, 1989. Therefore, setting the order of the substitution attack, for example, L = 10 ⁶ and the value of K = 100, which is recommended in the book of I. Okov. Authentication of voice messages and images in communication channels. / Ed. prof. V.F.Komarovich. - Publishing house of the St. Petersburg Polytechnic University, 2006, p.198, it is advisable to set the value of K _min not less than 82.

To assure the sender with a digital watermark of an electronic text message, K groups of binary sequences are extracted from the binary sequence of the electronic text message using the first binary sequence of the shared secret key. Known methods for extracting K groups of binary sequences from a binary sequence of an electronic text message using the first binary sequence of a shared secret key are described, for example, in the book Menezes A.J., Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. CRC Press, 1996, p. 345. The essence of these methods is that the first binary sequence of the shared secret key determines which binary sequences of characters from the binary sequence of the electronic text message are distributed between each of the K groups of binary sequences.

As an example of an electronic text message, a fragment of the text in Russian is presented: "dear edition! _ I confirm_ the authenticity of this text. Signature: authors", where the symbol "_" is a space. Figure 3 shows an example of the presentation of the beginning of this electronic text message in the form of binary sequences of characters encoded, for example, in accordance with the standard KOI8-R. A binary sequence view of the start of this electronic text message is shown in FIG. 2 (g).

2 (h) shows a typical example of allocating K groups of binary sequences from a binary sequence of an electronic text message using the first binary sequence of a shared secret key. It can be seen that in accordance with the first binary sequence of the shared secret key, the first group of binary sequences is formed from the first four binary sequences, the second group of binary sequences from the following five binary sequences, etc.

Consistently k-th, where k = 1, 2, ..., K, the group of binary sequences is divided into the first and second parts. Known methods for sequentially dividing the k-th group of binary sequences into the first and second parts are described, for example, in the book of B.A. Kalabekov. "Microprocessors and their use in signal transmission and processing systems." - M.: Radio and Communications, 1988, p. 70. Starting from the beginning of the group of binary sequences from the k-th group of binary sequences, a predetermined number of binary sequences is sequentially read into its first part, and the remaining binary sequences are sequentially read into its second part. For an even number of groups of binary sequences in the k-th group of binary sequences, the length of the first and second parts is set, for example, equal, and for an odd one, it is agreed in advance which part will be greater, for example, by one binary sequence of characters.

Figure 2 (h) shows a typical example of a sequential division into the first and second parts of the first, second and K-th groups of binary sequences. In the first group of binary sequences, the first and second parts include two binary sequences corresponding to the letters of the Russian alphabet "DO" and "PO", respectively. In the second group of binary sequences, the first part includes 2 binary sequences, and the second part includes 3 binary sequences. It can be seen that these binary sequences correspond to the letters and symbols "GA" and "Ya_R", respectively, where the symbol "_" is a space. Similarly, in the Kth group of binary sequences, the first part includes 2 binary sequences, and the second part includes 3 binary sequences.

The entire k-th group of binary sequences and its first and second parts are separately hashed by the previously generated hash function and the second binary sequence of the shared secret key. For this, for example, the hashed k-th group of binary sequences and separately its first and second parts are encrypted using the DES data encryption algorithm in ciphertext feedback mode using the second binary sequence of the shared secret key. The DES data encryption algorithm in ciphertext feedback mode using the second binary sequence of the shared secret key is described, for example, in the book by M.D.Smid, D.K. Bransted. "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 49. The algorithm indicates that if the length of the encrypted data is not a multiple of the standard length of the encrypted block of 64 bits, then the incomplete block is supplemented to the standard length by zero binary characters to the right. Then, the output value of 64 bits in length hash functions are converted by a modulo 2 calculation. The conversion of the output value by a modulo 2 calculation is known and described, for example, in the book of B. A. Kalabekov. "Microprocessors and their use in signal transmission and processing systems." - M.: Radio and Communications, 1988, p. 10.

Figure 4 shows a typical example of separate hashing of the entire k-th group of binary sequences and its first and second parts for the hash function and the second binary sequence of the secret key. For convenience of description, binary sequences are represented in decimal form, for example, binary sequence 0010 0111 0111 0111 of the first part of the first group of binary sequences in decimal representation corresponds to the number 228 × 238 = 54264 and its hashed value is equal to a single value. The hashed value of the entire kth group of binary sequences X _k in terms of the hash function and the second binary sequence of the shared secret key V2 is written as H _k = h (X _k , V2 _k ), and the hashed values of the first and second parts of the kth group of binary sequences X1 _k and X2 _k - in the form Н1 _k = h (X1 _k , V2 _k ) and Н2 _k = h _V2 (X2 _k , V2 _k ), respectively.

Figure 2 (s) shows a typical example of hashing the entire k-th group of binary sequences and its first and second parts in terms of the hash function and the second binary sequence of the shared secret key. The hashed values of the first group of binary sequences and its first part in this example take a single value, and the second part takes a zero value. The hashed values of the Kth group of binary sequences and its second part in this example take a single value, and the first part takes a zero value. On average, hashed values of binary sequences take a value of zero or one with a probability of 1/2.

Then check the compliance of the hashed values of the entire kth group of binary sequences and the hashed values of its first and second parts kth bits of the first, second, third and fourth binary sequences of the sender's secret key. The correspondence of the hashed values of the entire kth group of binary sequences and its first and second parts to the kth bits of the first, second, third and fourth binary sequences of the sender’s secret key is established by simultaneously fulfilling the equality, on the one hand, of the hashed value of the first part of the kth group of binary sequences and, on the other hand, the product of the hashed value of the entire kth group of binary sequences and the kth bit of the second binary sequence of the sender’s secret key, folded modulo 2 with the kth bit of the first binary sequence of the sender’s secret key and the equality, on the one hand, of the hashed value of the second part of the kth group of binary sequences and, on the other hand, the product of the hashed value of the entire kth group of binary sequences and k -th bit of the fourth binary sequence of the sender’s secret key, folded modulo 2 with the kth bit of the third binary sequence of the sender’s secret key. Known methods for verifying the correspondence of hashed values of the entire kth group of binary sequences and its first and second parts to the kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key are described, for example, in the book Johansson T. On the construction of perfect authentication codes that permit arbitration. Advances in Cryptology. Proc. Crypt-93. Springer-Verlag. 1993, p. 343-354. Known methods for performing the product of bit values, their addition modulo 2, and comparisons are described, for example, in the book by A.L. Lantsov, L.I. Zvorykin, I.F. Osipov. "Digital devices on complementary TIR integrated circuits." - M.: Radio and Communications, 1983, pp. 153-164.

For a typical example of the hash result of the first (k = 1) group of binary sequences H _k = h (X _k , V2 _k ) = 1, where V2 ₁ = 0, as shown in Fig.2b, its first part H1 _k = h (X1 _k , V2 _k ) = 1 and its second part Н2 _k = h (X2 _k , V2 _k ) = 0, the indicated correspondence is satisfied, i.e., the equalities H1 _k = T1 _k ⊕H _k ⊗T2 _k and H2 _K = T3 _k ⊕ H _k ⊗ T4 _k , where T1 _k , T2 _k , T3 _k and T4 _k are the kth bits of the first, second, third and fourth binary sequences of the sender’s secret key, respectively, equal to 1, 0, 1 and 1, respectively, as shown in figure 2 (c), 2 (d), 2 (e) and 2 (e) for k = 1. The symbols ⊗ and ⊕ mean operations of multiplication and addition, respectively, modulo 2.

When the correspondence is established, the hashed value of the first part of the kth group of binary sequences is accepted as the next bit of the first binary sequence of the digital watermark of the electronic text message and as the next bit of the second binary sequence of the digital watermark of the electronic text message the hashed value of the second part of the kth group of binary sequences and transmit to the recipient the k-th group of binary sequences as digitally certified an infamous sign. Methods of transferring the kth group of binary sequences to the recipient as a certified digital watermark are known and described, for example, in the book: A.G. Zyuko, D.D. Klovsky, M.V. Nazarov, L.M. Fink. "Theory of signal transmission." - M .: Radio and communications, 1986, p. 11.

For the typical example shown in FIGS. 2 (m) and 2 (n), when matching for the first group of binary sequences, the first bit of the first binary sequence of the digital watermark of the electronic text message is set to a single value, and the first bit of the second binary sequence of the digital water message the sign of the electronic text message to zero and transmit to the recipient unchanged the first group of binary sequences as a certified digital watermark, as shown in figure 2 (o).

When a mismatch is established, the characters in the kth group of binary sequences are successively replaced by the characters from the ones from the predefined set of replacement characters, after which the entire kth converted group of binary sequences and its first and second parts are hashed separately by the preformed hash function and the second binary shared secret key sequences.

For a typical example of a hash result of the second (k = 2) group of binary sequences H _k = h (X _k , V2 _k ) = 1, where V2 ₂ = 0, as shown in FIG. 2 (b), of its first part H1 _k = h (X1 _k , V2 _k ) = 1 and its second part Н2 _k = h (X2 _k , V2 _k ) = 0, the indicated correspondence does not hold, i.e., the equalities H1 _k = T1 _k ⊕ H _k ⊗ T2 _k and H2 _k = T3 _k ⊕ H _k ⊗ T4 _k , where T1 _k , T2 _k , T3 _k and T4 _k are the k-th bits of the first, second, third and fourth respectively binary sequences of the sender's secret key, equal to 1, 0, 0 and 1, respectively, as shown in FIGS. 2 (c), 2 (d), 2 (e) and 2 (e) for k = 2.

In the second group of binary sequences, for example, they search for the first character for which substitute characters are preset, and this character is changed to a substitute. In this case, the binary sequence corresponding to this symbol is replaced by the binary sequence of the symbol replacing it. If necessary, find the second, third, etc. characters for which substitute characters are predefined. Known methods for replacing one binary sequence of a symbol with another are described, for example, in the book of M.I.Zhaldak, I.N. Morse. "Fundamentals of Computer Science and Computer Engineering." K .: Vishcha School, 1985, page 47.

For example, figure 2 (k) shows that in the first part of the second group of binary sequences, the binary sequence of the character "a" of the Russian alphabet is replaced by the binary sequence of the character "a" of the English alphabet. In this case, the binary sequence corresponding to this symbol is replaced by the binary sequence of the symbol replacing it, as a result of which the second converted group of binary sequences in the typical example takes the form shown in Fig. 2 (k). As a result of repeated separate hashing of the entire second converted group of binary sequences and its first and second parts in terms of the hash function and the second binary sequence of the shared secret key, for example, H _k = h (X _k , V2 _k ) = 0, H1 _k = h ( X1 _k , V2 _k ) = 1 and H2 _k = h (X2 _k , V2 _k ) = 0, as shown in FIG. 2 (l).

Then, the correspondence of the hashed values of the entire kth converted group of binary sequences and its first and second parts to the kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key is checked again, and the steps are to replace the characters in the kth converted group of binary sequences , its hashing and verification of compliance of its hashed values is carried out before it is established.

The correspondence of the hashed values of the entire kth transformed group of binary sequences and its first and second parts to the kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key is established by simultaneously performing the equality, on the one hand, of the hashed value of the first part of the kth converted groups of binary sequences and, on the other hand, the product of the hashed value of the entire kth converted group of binary sequences and the kth bit of the second binary the sender’s secret key sequence folded modulo 2 with the kth bit of the first binary sender’s secret key sequence and, on the one hand, the hashed value of the second part of the kth transformed group of binary sequences and, on the other hand, the product of the hashed value of the entire k- of the transformed group of binary sequences and the kth bit of the fourth binary sequence of the sender's secret key, folded modulo 2 with the kth bit of the third binary sequence STI the sender's private key. Known methods for verifying the correspondence of hashed values of the entire kth converted group of binary sequences and its first and second parts to the kth bits of the first, second, third, and fourth binary sequences of the sender’s secret key are described, for example, in the book Johansson T. On the construction of perfect authentication codes that permit arbitration. Advances in Cryptology. Proc. Crypt-93. Springer-Verlag. 1993. p. 343-354. Known methods for performing the product of bit values, their addition modulo 2, and comparisons are described, for example, in the book by A.L. Lantsov, L.I. Zvorykin, I.F. Osipov. "Digital devices on complementary MIS integrated circuits", - M .: Radio and communications, 1983, pp. 153-164.

For a typical example of the hash result of the second (k = 2) transformed group of binary sequences H _k = h (X _k , V2 _k ) = 0, where V2 ₂ = 0, as shown in Fig.2b, its first part H1 _k = h ( X1 _k , V2 _k ) = 1 and its second part Н2 _k = h (X2 _k , V2 _k ) = 0, the indicated correspondence is satisfied, i.e., the equalities Н1 _k = Т1 _k ⊕H _k ⊗T2 _k and Н2 _k = T3 _k ⊕ H _k ⊗ T4 _k , where T1 _k , T2 _k , T3 _k and T4 _k are the k-th bits of the first, second, third and fourth binary sequences of the sender’s secret key, equal to 1, 0, 0 and 1, respectively, as shown in FIGS. 2 (c), 2 (d), 2 (e) and 2 (e) for k = 2.

After the correspondence is established, the hashed values of the first and second parts of the kth transformed group of binary sequences, respectively, are accepted as the next bits of the first and second binary sequences of the digital watermark of the electronic text message, and the recipient of the kth converted group of binary sequences is transmitted to the recipient as a certified digital watermark.

For the typical example shown in FIGS. 2 (m) and 2 (n), when this correspondence is fulfilled for the second converted group of binary sequences, the second bit of the first binary sequence of the digital watermark of the electronic text message is set to a single value, and the second bit of the second binary sequence digital watermark of an electronic text message to zero and transmit to the recipient a second converted group of binary sequences as digitally authenticated sign, as shown in figure 2 (o).

The methods for transferring the kth transformed group of binary sequences to the recipient as a digital watermark are known and described, for example, in the book: A.G. Zyuko, D.D. Klovsky, M.V. Nazarov, L.M. Fink. "Theory of signal transmission." - M .: Radio and communications, 1986, p. 11.

The steps to certify the sender with a digital watermark of an electronic text message are repeated until its binary sequence arrives.

The length of the binary sequence of an electronic text message can be arbitrarily large. With the growth of its length, the number K of groups of binary sequences proportionally grows, in each of which the recipient checks the authenticity of the received message. Therefore, the longer the message, the more difficult it is for the attacker to change its content in an undetectable way during verification. If the intruder divides the certified electronic text message into several parts, then thanks to the sender's assurance of each group of binary sequences, the recipient of any part of the certified message consisting of at least K groups of binary sequences is able to verify its authenticity.

After transmitting the digital watermarked electronic text message from the binary sequence of the electronic text message received by the recipient, a binary sequence of a symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences is extracted.

An algorithm for extracting from a binary sequence received by a recipient of an electronic text message a binary sequence of a character belonging to a first binary sequence of a first group of binary sequences authenticated with a digital watermark is shown in FIG. 5.

For example, FIG. 6 (e) shows that for a typical example, the received binary sequence of a digital watermarked electronic text message is shifted by one space character, and in the first bit of the Kth digital watermarked binary sequence occurred during transmission the error and the accepted character "I" was mistakenly converted to the character "o". Accordingly, Fig. 6 (g) shows the K received groups of binary sequences in the form of binary sequences of the symbols "dear edition".

, а действие

означает округление значения -log₂P_ош до ближайшего целого.In order to extract a binary sequence of a symbol from the first binary sequence of the first digital watermarked group of binary sequences from the binary text received by the recipient of the electronic text message, the maximum allowable probability value _{Psh of the} erroneous selection of the binary sequence of the symbol belonging to the first verified digital watermark of the binary sequence group is preliminarily set. , and set the value

, and the action

means rounding the value of -log ₂ P _od to the nearest integer.

The probability value of _Osh can be established, for example, of the order of 10 ^-3 ... 10 ^-4 . If, as a result of transmission channel errors or deliberate distortions of the authenticated electronic text message, the recipient cannot select the binary sequence of the character belonging to the first binary sequence of the first digital watermarked group of binary sequences, then the receiver will search for the desired binary character sequence in the next received binary sequence, and so on until the desired binary character sequence is highlighted. The probability of non-isolation of the required binary symbol sequence in β consecutive groups of K binary sequences is equal to P ^β _OSH . Since with increasing number of β probability P ^β _oui quickly approaching zero, it provides guaranteed allocation recipient binary symbol sequence belongs to a first binary sequence a first authenticated digital watermark group of binary sequences.

To select from the received binary sequence of the electronic text message a binary sequence of a character belonging to the first binary sequence of the first digital watermarked group of binary sequences, from the received binary sequence of the electronic text message, starting with the binary sequence of the first character, extract the common secret using the first binary sequence key K received groups of binary sequences.

Known methods for extracting K received groups of binary sequences from a received binary sequence of an electronic text message using the first binary sequence of a shared secret key are described, for example, in the book Menezes A.J., Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. CRC Press, 1996, p. 345. The essence of these methods is that the first binary sequence of the shared secret key determines which binary sequences of characters from the received binary sequence of the electronic text message are distributed between each of the K received groups of binary sequences.

For example, Fig. 6 (g) shows the allocated K received groups of binary sequences in the form of binary sequences of the _ _ dear_ edition.

Consistently, the kth received group of binary sequences is divided into the first and second parts. Known methods for sequentially dividing the kth received group of binary sequences into the first and second parts are described, for example, in the book of B.A. Kalabekov. "Microprocessors and their use in signal transmission and processing systems." - M.: Radio and Communications, 1988, p. 70. Starting from the beginning of the received group of binary sequences from the k-th received group of binary sequences, a predetermined number of binary sequences are sequentially read into the first part, and the remaining binary sequences are sequentially read into the second part. For an even number of groups of binary sequences, the bit length of the first and second parts is set, for example, equal, and for odd ones, it is agreed in advance which part will be more than one group of binary sequences according to a rule identical to the rule for the sender to divide into first and second parts k th group of binary sequences. For example, in Fig.6 (g) it is shown that the received K groups of binary sequences allocated to K are presented in the form: the first and second parts of the first received group of binary sequences consist of binary sequences of the characters "_e" and "op", the second received group is " og "and" aya_ "respectively, etc.

Then, the entire kth received group of binary sequences and its first and second parts are separately hashed according to the preformed hash function and the second binary sequence of the shared secret key.

по функции хэширования h() и второй двоичной последовательности общего секретного ключа V2 записывается в виде

а хэшированные значения первой и второй части k-ой принятой группы двоичных последовательностей

и

- в виде

и

соответственно.To do this, for example, the hashed kth received group of binary sequences and separately its first and second parts are encrypted using the DES data encryption algorithm in ciphertext feedback mode using the second binary sequence of the shared secret key. The DES data encryption algorithm in ciphertext feedback mode using the second binary sequence of the shared secret key is described, for example, in the book by M.D.Smid, D.K. Bransted. "Data Encryption Standard: Past and Future." TIIER, 1988, v. 76, No. 5, p. 49. The algorithm indicates that if the length of the encrypted data is not a multiple of the standard length of the encrypted block of 64 bits, then the incomplete block is supplemented to the standard length by zero binary characters to the right. Then, the output value of 64 bits in length hash functions are converted by a modulo 2 calculation. The conversion of the output value by a modulo 2 calculation is known and described, for example, in the book of B. A. Kalabekov. "Microprocessors and their use in signal transmission and processing systems." - M.: Radio and Communications, 1988, p. 10. The hashed value of the entire kth received group of binary sequences

by the hash function h () and the second binary sequence of the shared secret key, V2 is written as

and the hashed values of the first and second parts of the kth received group of binary sequences

and

- as

and

respectively.

6 (h) shows a typical example of hashing the entire k-th received group of binary sequences and its first and second parts for the hash function and the second binary sequence of the shared secret key. The hashed values of the first received group of binary sequences and its first part in this example take a single value, and the second part takes a zero value. The hashed values of the Kth received group of binary sequences and its second part in this example take a single value, and the first part takes a zero value.

Then check the compliance of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key. The correspondence of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key is established by performing the equality, on the one hand, of the hashed values of the second part of the kth received group of binary sequences and, on the other hand, the product of the hashed value of the entire kth received group of binary sequences and the kth bit of the third binary sequence of the recipient's secret key Folded modulo 2 k-th bit of the first binary sequence a private key of the recipient and the product of the first part of the hashed values k-th received group of binary sequences and the k-th bit of the second binary sequence secret key of the recipient.

Known methods for verifying the correspondence of hashed values of the entire kth group of binary sequences and its first and second parts to the kth bits of the first, second, and third binary sequences of the recipient's secret key are described, for example, in the book Johansson T. On the construction of perfect authentication codes that permit arbitration. Advances in Cryptology. Proc. Crypt-93. Springer-Verlag. 1993, p. 343-354. Known methods for performing the product of bit values, their addition modulo 2 and comparison are described, for example, in the book by A.L. Lantsov, L.N. Zvorykin, I.F. Osipov. "Digital devices on complementary TIR integrated circuits." - M.: Radio and Communications, 1983, pp. 153-164.

For a typical example of a hash result of the first (k = 1) received group of binary sequences

where V2 ₁ = 0, as shown in Fig.6 (h), its first part

and its second part

the indicated correspondence is satisfied, i.e., the equality

where R1 _k , R2 _k , R3 _k are the kth bits of the first, second and third, respectively, binary sequences of the recipient's secret key, equal to 1, 0, 1, respectively, as shown in Fig.6 (c), 6 (d), 6 (e) for k = 1.

For a typical example of a hash result of the second (k = 2) received group of binary sequences

where V2 ₂ = 0, as shown in Fig.6 (h), its first part

and its second part

the specified match does not hold, that is, the equality

where R1 _k , R2 _k , R3 _k are the kth bits of the first, second and third, respectively, binary sequences of the recipient's secret key, equal to 0, 1, 1, respectively, as shown in Fig.6 (c), 6 (d), 6 (e) for k = 2.

When 1 <M≤K matches, the selected binary character sequence is taken as the binary character sequence belonging to the first binary sequence of the first binary watermarked group of binary sequences.

Otherwise, the steps for extracting the binary sequence of the character belonging to the first binary sequence of the first digital watermarked group of binary sequences are repeated with the binary sequence of the next character of the received binary sequence of the electronic text message.

For example, for the K received groups of binary sequences in the form of binary sequences of the characters _ _ dear_ edition, as shown in FIG. 6 (i), a mismatch was found for the second, subsequent and K-th received group of binary sequences, and the number of matches turned out to be less than the number M. Therefore, a shift K of the received groups of binary sequences is performed by one binary sequence of a symbol, K of the received groups of binary sequences becomes corresponding to the received electronic text message ida "dorogaya_redaktsio", for which the number of matches is greater than the number of M.

After highlighting the binary sequence of the symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences, the recipient checks the authenticity of the received electronic text message, for which starting from the binary sequence of the symbol belonging to the first binary sequence of the first digital watermarked group of binary sequences using the first shared secret shared binary sequence ca By taking a group of binary sequences.

An authentication algorithm for a received electronic text message synchronized with a digital watermarked electronic text message is shown in FIG. 7.

Known methods for a recipient to extract an electronic text message from a received binary sequence from a binary sequence of a character belonging to the first binary sequence to the first authenticated digital watermark using the first binary sequence of the shared secret key K of the received groups of binary sequences are described, for example, in the book Menezes AJ, Oorschot PC, Vanstone SA Handbook of applied cryptography. CRC Press, 1996, p. 345. The essence of these methods is that the first binary sequence of the shared secret key determines which binary sequences of characters from the received binary sequence of the electronic text message are distributed between each of the K received groups of binary sequences.

For example, in Fig. 8 (e), it is shown that the first adopted group of binary sequences corresponds to the characters "doro", the second to "gaya_r", the K-th to "action".

Consistently, the kth received group of binary sequences is divided into the first and second parts. The entire kth received group of binary sequences and its first and second parts are separately hashed by the pre-formed hash function and the second binary sequence of the shared secret key. Check the compliance of the hashed values of the entire k-th received group of binary sequences and its first and second parts to the k-th bits of the first, second and third binary sequences of the recipient's secret key. The correspondence of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key is established by performing the equality, on the one hand, of the hashed values of the second part of the kth received group of binary sequences and, on the other hand, the product of the hashed value of the entire kth received group of binary sequences and the kth bit of the third binary sequence of the recipient's secret key Folded modulo 2 k-th bit of the first binary sequence a private key of the recipient and the product of the first part of the hashed values k-th received group of binary sequences and the k-th bit of the second binary sequence secret key of the recipient.

For example, in Fig. 8 (g) it is shown that the received K groups of binary sequences allocated to K are represented in the form: the first and second parts of the first received group of binary sequences consist of binary sequences of “do” and “ro” characters, the second received group is “ ha "and" i_r_ ", etc. On Fig (h) shows a typical example of the hash results of the entire k-th received group of binary sequences and its first and second parts for the hash function and the second binary sequence of the shared secret key. The hashed values of the first received group of binary sequences and its first part in this example take a single value, and the second part takes a zero value. The hashed values of the Kth received group of binary sequences and its first part in this example take a single value, and the second part takes a zero value.

For a typical example of a hash result of the first (k = 1) received group of binary sequences

where V2 ₁ = 0, as shown in Fig. 8 (b), of its first part

and its second part

the indicated correspondence is satisfied, i.e., the equality

where R1 _k , R2 _k , R3 _k are the kth bits of the first, second and third, respectively, binary sequences of the recipient's secret key, equal to 1, 0, 1, respectively, as shown in Fig.6 (c), 6 (d), 6 (e) for k = 1.

For a typical example of the hash result of the Kth (k = K) received group of binary sequences

where V2 _K = 0, as shown in Fig. 8 (b), of its first part

and its second part

the specified match does not hold, that is, the equality

where R1 _k , R2 _k , R3 _k are the kth bits of the first, second and third, respectively, binary sequences of the recipient's secret key, equal to 0, 0, 1, respectively, as shown in Figs. 8 (c), 8 (d), 8 (e) for k = K. Therefore, Fig. 8 (i) shows that when the correspondence is fulfilled, the number K _C increases by one, and if the number does not match, the number K _C remains unchanged.

Moreover, when performing the number of matches K _with ≥K _{min, the} received K groups of binary sequences of the electronic text message are considered authentic, and then the steps to verify the authenticity of the next K received groups of binary sequences are repeated until the entire binary sequence of the electronic text message is received.

For example, FIG. 8 (i) shows that K-1 matches were performed in the K received groups of binary sequences. Therefore, at a preset value, for example, K _min = K-1, the authenticity K of the received groups of binary sequences of the electronic text message is confirmed. Only one character is distorted in the received message, which does not change the meaning of the received electronic text message and allows the recipient to correctly perceive the meaning of the received electronic text message due to the high redundancy of the text messages.

The following K received groups of binary sequences of the electronic text message are processed similarly. If during authentication all K received groups of binary sequences of an electronic text message are considered authentic, then all received electronic text message is considered authentic.

Verification of the theoretical background of the claimed method for generating and verifying a message certified with a digital watermark was verified by its analytical studies.

The probability of acceptance by authentic K of accepted groups of binary sequences of an electronic text message that are not authentic is equal to

- число сочетаний из К по µ, a L - число известных злоумышленнику заверенных цифровым водяным знаком электронных текстовых сообщений. Для электронных текстовых сообщений предварительно задается Р_доп - допустимая вероятность принятия подлинными К принятых групп двоичных последовательностей электронного текстового сообщения, являющихся неподлинными. В системах передачи электронных текстовых сообщений должно выполняться Р_непод≤Р_доп. Обычно величина P_доп устанавливается равной 10^-9, что рекомендуется, например, в государственном стандарте 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР, 1989.Where

is the number of combinations from K by μ, and L is the number of electronic text messages certified by a digital watermark known to the attacker. For electronic text messages pre-specified _additional P - allowable probability of acceptance of genuine By taking a group of binary electronic text message sequences that are inauthentic. The electronic text messaging systems should be performed P _nepod ≤R _ext. Typically, the value of P _{add is} set equal to 10 ^-9 , which is recommended, for example, in state standard 28147-89. Information processing systems. Cryptographic protection. Cryptographic conversion algorithm. - M.: Gosstandart of the USSR, 1989.

Figure 9 shows the dependence of P _nep on the values of K-K _min for various values of K at a fixed value of L = 10 ⁶ . The studies were carried out at K = 500, K = 200, and K = 50. From the figure it is seen that the lowest allowable number K _min at P _ext = 10 ^-9 should be set so as to satisfy the relation P _nepod ≤R _additional, i.e. when K = 500 K _min value should be at least 320, for K = 200 - at least 154, and at K = 50 - at least 46.

The studies confirm that when using the proposed method for generating and verifying an electronic text message authenticated with a digital watermark, it increases its security against the deliberate actions of attackers to change its content.

Claims (6)

1. The method of generating and verifying an electronic message authenticated with a digital watermark, which consists in the fact that the binary secret public key sequence and the hash function with binary output value are first generated for the sender and recipient, and the minimum allowable number K _{min of} genuine groups of binary sequences of the electronic message is established from K received groups of electronic messages binary sequence isolated K≥K _min groups of binary sequences, assure at Dep Using a pre-formed hash function and a binary sequence of the secret key, and transmit it to the recipient, verify the authenticity of the received electronic message by the recipient using the pre-generated hash function and the binary sequence of the secret key, characterized in that the electronic message is electronic text message, each character of which is represented as its given binary after sequence, and additionally form the sender’s secret key, consisting of the first, second, third and fourth binary sequences, as well as the recipient’s secret key, consisting of the first, second and third binary sequences, and the shared secret key is formed in the form of the first and second binary sequences, pre-set for the characters of an electronic text message, a set of replacement characters that do not change the visual perception of this message, and for certification by the sender With an even watermark of an electronic text message, K groups of binary sequences are extracted from the binary sequence of the electronic text message using the first binary sequence of the shared secret key, sequentially k-th, where k = 1, 2, ..., K, the group of binary sequences is divided into the first and second parts, then the entire k-th group of binary sequences and its first and second parts are separately hashed by the previously generated hash functions and the second binary sequence shared secret key, check the compliance of the hashed values of the entire k-th group of binary sequences and the hashed values of its first and second parts to the k-th bits of the first, second, third and fourth binary sequences of the sender's secret key, when matching is taken as the next bit of the first binary digital watermark sequences of the electronic text message hashed value of the first part of the kth group of binary sequences and as a next bit the second binary sequence of the digital watermark of the electronic text message, the hashed value of the second part of the kth group of binary sequences, transmit to the recipient the kth group of binary sequences as a digital watermark, when a mismatch is established, the characters in the kth group of binary sequences are successively replaced by replacing from a pre-installed set of replacement characters, after which they re-hash separately the entire k-th converted group poo of binary sequences and its first and second parts according to the pre-formed hash function and the second binary sequence of the shared secret key, again check the hashed values of the entire k-th converted group of binary sequences and its first and second parts to the k-th bits of the first, second, third and the fourth binary sequences of the sender’s secret key, with the steps of replacing the characters in the kth transformed group of binary sequences, hashing and checking them correspondence of its hashed values is carried out until it is established, after which the hashed values of the first and second parts of the kth transformed group of binary sequences are received as the next bits of the first and second binary sequences of the digital watermark of the electronic text message, respectively, they transfer the kth converted group to the recipient binary sequences as certified by a digital watermark, and the actions of certification by the sender with a digital watermark are electro This text message is repeated until its binary sequence arrives, after transmitting the digital watermarked electronic text message from the received binary sequence of the electronic text message, the binary sequence of the character belonging to the first binary sequence of the first digital watermarked group of binary sequences is extracted, for which of the received binary sequence of the electronic text message, on different from the binary sequence of the first character, isolated using the first binary sequence of the shared secret key K of the received groups of binary sequences, the kth received group of binary sequences is sequentially divided into the first and second parts, the entire kth received group of binary sequences and its first and second the parts are separately hashed according to the pre-formed hash functions and the second binary sequence of the shared secret key; the values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient’s secret key, and when 1 <M≤K matches, the selected binary symbol sequence is taken as a binary symbol sequence, belonging to the first binary sequence of the first digital watermarked group of binary sequences, otherwise, the steps to extract the binary sequence of the character, The group of binary sequences belonging to the first binary sequence of the first watermarked digital watermark is repeated with the binary sequence of the next character of the received binary sequence of the electronic text message, after the binary sequence of the symbol belonging to the first binary sequence of the first binary watermark of the group of binary sequences is verified, the recipient is checked for authenticity of the received electronic text message for h starting from the binary sequence of the character belonging to the first binary sequence of the first digital watermarked group of binary sequences, allocate using the first binary sequence of the shared secret key K of the received groups of binary sequences, the kth received group of binary sequences is sequentially divided into the first and second parts, the entire k-th adopted group of binary sequences and its first and second parts are separately hashed using the hashed function and the second binary sequence of the shared secret key, verify compliance of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key, and when establishing the number of matches K _c ≥K _min consider K received groups of binary sequences of the electronic text message authentic, and then repeat the steps to verify the authenticity of the next K p accepted groups of binary sequences until receiving the complete binary sequence of the electronic text message. 2. The method according to claim 1, characterized in that the minimum allowable number K _{min of} genuine groups of binary sequences of an electronic text message from K received groups is determined from the condition

,
where P _add - pre-defined acceptable probability of acceptance by authentic To the accepted groups of binary sequences of electronic text messages that are not authentic,

is the number of combinations of K in μ, and L is the number certified with a digital watermark using binary sequences of the shared secret key and binary sequences of the secret key of the sender of electronic text messages. 3. The method according to claim 1, characterized in that the maximum allowable value of the probability P _{O of the} erroneous allocation of a binary sequence of a symbol belonging to the first binary sequence of the first binary watermarked group of binary sequences is set and the value is set

, and the action

means rounding the value - log ₂ Р _osh to the nearest integer. 4. The method according to claim 1, characterized in that the first and second binary sequences of the sender’s secret key and the third binary sequence of the recipient’s secret key of length K bits are preliminarily and equally probable, and the kth bits of the remaining binary sequences of the sender’s secret key of length K bits and the recipient’s secret key of length K bits are determined to correspond to the simultaneous equality on the one hand of the kth bit of the third binary sequence of the sender’s secret key and side of the product of the kth bit of the first binary sequence of the sender’s secret key and the kth bit of the second binary sequence of the recipient’s secret key, folded modulo 2 with the kth bit of the first binary sequence of the recipient’s secret key and equality on one side of the kth bit of the fourth the binary sequence of the sender’s secret key and on the other hand the product of the kth bit of the second binary sequence of the sender’s secret key and the kth bit of the second binary sequence is secret on the recipient's public key, modulo-2 to the k-th bit of the binary sequence of the third secret key of the recipient. 5. The method according to claim 1, characterized in that the correspondence of the hashed values of the entire kth group of binary sequences and its first and second parts to the kth bits of the first, second, third and fourth binary sequences of the sender’s secret key is established by simultaneously performing equality with one sides of the hashed value of the first part of the kth group of binary sequences and on the other hand the product of the hashed value of the entire kth group of binary sequences and the kth bit of the second binary sequence with a secret sender key, folded modulo 2 with the kth bit of the first binary sequence of the sender’s secret key, and the equality on the one hand of the hashed value of the second part of the kth group of binary sequences and on the other hand the product of the hashed value of the entire kth group of binary sequences and the kth bit of the fourth binary sequence of the sender’s secret key, folded modulo 2 with the kth bit of the third binary sequence of the sender’s secret key. 6. The method according to claim 1, characterized in that the correspondence of the hashed values of the entire kth received group of binary sequences and its first and second parts to the kth bits of the first, second and third binary sequences of the recipient's secret key is established by performing equality on one side of the hashed the values of the second part of the kth received group of binary sequences and, on the other hand, the product of the hashed value of the entire kth received group of binary sequences and the kth bit of the third binary sequence the secret key of the recipient, the addition modulo 2 k-th bit of the first binary sequence a private key of the recipient and the product of the first part of the hashed values k-th received group of binary sequences and the k-th bit of the second binary sequence secret key of the recipient.

Images