Method for transmitting encrypted messages

0001The invention relates to a method for transmitting encrypted messages, as defined in claim 1 or in claim 8.

0002The starting point for the invention are symmetrical encryption methods in which the encryption or decryption of data, the transmitter or the recipient needs the same key. Such methods have been used for quite some time in the military and industrial sectors. A well-known symmetric encryption method is the DES (Data Encryption Standard) DES algorithm developed by IBM and standardized in 1977. An introduction to the theory of symmetric encryption methods and an overview of the common methods can be found, inter alia, in A. Beutelsbacher "Cryptology", Vieweg Verlag, 1991.

0003Users of digital communications systems expect their confidential messages to be encrypted with such a high level of security that, ideally, only the recipient with the correct key can decrypt the encrypted message. On the other hand, there are u. a. state institutions, such as B. The police, who are interested in restricting the effects of cryptographic procedures, in order to decrypt the conversations and data of criminals or government-endangering organizations. The security level of symmetric encryption techniques can be reduced by limiting the maximum length of the cryptographic keys used. For example, the US government only allows the export of symmetric encryption techniques that use keys with a maximum effective length of only 40 bits. The key length is a measure of the size of the key space to be searched. For a key length of 40 bits, a maximum of 2 must be used⁴⁰ Different keys are tried before finding the right one.

0004It is known to apply symmetric encryption methods in so-called pay-TV systems, in which audio and video data selectively via a broadcast medium, such. B. satellite or broadband coaxial cable to be distributed to its customers. Typically, a key length of 40 bits is sufficient for the transmission of such data because the keys used frequently change (approximately every 10 seconds) and the overhead of the key space of size 2 is exhaustive⁴⁰ today is still a few weeks. This encryption method proves to be disadvantageous if, for example, confidential company data is to be distributed in the context of a business TV event with the same system. However, since the transmission of confidential company data, for example in an EXCEL file, can be done in less than 10 seconds and, in addition, the contents of the file can be valuable even after a few weeks, a corresponding expenditure for decrypting the data is always worthwhile.

0005The invention is therefore based on the object to provide a method for transmitting encrypted messages, in which, although conventional cryptographic keys are used with a predetermined length, but the message to be transmitted can be encrypted with a level of security that is higher than that with known Encryption method achievable.

0006The technical problem solves the invention once with the method steps of claim 1 and on the other with the method steps of claim 8.

0007Advantageous developments are specified in the subclaims.

0008As already mentioned, the method according to the invention is based on encryption methods which are known per se. The core idea of ​​the invention is to split the message into sub-messages, in particular of a random nature, to encrypt and transmit the sub-messages independently of each other so that the message is actually transmitted with a higher degree of security.

0009For this purpose, first the message to be transmitted in T submessages m₁ ... m_T disassembled. Subsequently, each partial message m_i with an individual key k_i the length l according to the regulation<maths id="math0001" num=""><math display="block"><mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> : = E (k</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>, m</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0902568A2_D0001.tif" /></maths> encrypted so that the total message to be transmitted is actually encrypted with a key of length L, where L> 1. In this way, the total message to be transmitted is encrypted with a higher level of security. The degree of security can be further increased if the sub-messages have the character of a random value, so that a criminal person who wishes to decrypt the encrypted message will have his or her individual key k_i, with which the respective partial message m_i has to be encrypted. For a key length of l and T randomly formed submessages - this corresponds to an actual key length of l * T - the size of the keyspace to be searched is thus 2^{l * T}, Without application of the inventive method, the size of the key space to be searched would be only 2^l, A random number or random value can be understood according to the invention to be a random bit sequence.

0010The so encrypted sub-messages c_i are transmitted to a receiving device.

0011In the receiving device, each partial message m_i with the individual key k_iwith which it has been previously encrypted, decrypted. Thereafter, the original message is reconstructed from the decoded part messages again.

0012An advantage of the method according to the invention is that existing devices and systems for encryption and decryption, which offer only a relatively low degree of security due to used cryptographic keys with a predetermined length, can be used to transmit highly sensitive data with a higher degree of security.

0013There are several known algorithms with which the message to be transmitted can be decomposed into T randomly formed partial messages. Such algorithms can, for. B. based on an additive, exclusive-OR or a multiplicative link.

0014The algorithms for calculating the submessages and the mathematical structures used to compute the original message use finite mathematical structures.

0015In order to make the system resistant to the loss of individual submessages in the transmission path, the message to be transmitted can be decomposed into T submessages using a known (p, T) Threshold method. The sub-messages are in turn encrypted and transmitted using individual cryptographic keys. Since the sub-messages have been generated by means of a (p, T) Threshold method, the receiving device can reconstruct the original message from p decrypted submessages, where p &lt;T. In other words, due to the applied threshold method, the receiving device is able to reconstruct the overall message, even if partial messages have been destroyed or lost during the transmission.

0016According to an alternative embodiment of the invention, it is possible to transmit data at a slightly higher data transfer rate with a higher degree of security. This is achieved by replacing at most T-1 submessages with a value whose length is smaller than the length of the respective submessage. Subsequently, the respective values ​​and the remaining partial messages are encrypted with an individual key. The encrypted values ​​and sub-messages are transmitted to a receiving device where they are decrypted and reassembled into the overall message. Methods for reducing the partial messages are known to the person skilled in the art. For example, the partial message m_i from a value x_i be formed by the value x_i repeatedly (concatenated) until the length of m is reached, where <maths id="math0002" num=""><math display="inline"><mrow><msub><mrow><mtext>m</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = x</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>∥x</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>∥x</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>... ∥x</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow></math><img file="EP0902568A2_D0002.tif" /></maths>,

0017For a longer message, it may be useful to divide it into several data blocks before the message is split into T submessages. The inventive method is then applied to each data block.

0018In order to further increase the security level of a message to be transmitted, the individual keys are recalculated for each data block. This method is known inter alia from pay-TV systems in which the keys used are changed frequently.

0019The invention will be explained in more detail with reference to two embodiments.

0020The following example is intended to make clear how the degree of security for a message m to be transmitted can be doubled. Assume that the individual cryptographic keys used have a key length of 1 bits, where 1 = 40. It is further assumed that the message m to be encrypted is a binary message comprising several bits. In order to be able to disassemble the message m to be encrypted into submessages, a sum algorithm according to the rule is created<maths id="math0003" num=""><math display="block"><mrow><msub><mrow><mtext>m = m</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> + m</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> : = (m - r) + r</mtext></mrow></math><img file="EP0902568A2_D0003.tif" /></maths> applied. In this example, therefore, the total message in two sub-messages m₁ and m₂ disassembled. Where r is a bit sequence generated in a random number generator. With the help of the random number r, the two sub-messages can also be expressed as random values, ie m₁ by m - r and m₂ through r. What is important in the decomposition described above is that each submessage considered by itself is a random number (for example, a random 64-bit sequence if the message space consists of 64-bit words). Subsequently, each sub-message is retrieved using a per se known symmetric encryption method that uses individual keys of length l according to the protocol<maths id="math0004" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> : = E (k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>, m</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow></mtd></mtr><mtr><mtd><mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> : = E (k</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>, m</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>)</mtext></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0902568A2_D0004.tif" /></maths> ciphered, where k₁ and k₂ two independent keys are, for example, each having a key length of l = 40 bits. The ciphertext c₁ and c₂ the submessages m₁ and m₂ are transmitted to a receiving device. Only if the receiving device is able to m the two ciphertext of the sub-messages₁ and m₂ to decrypt, the original message m can be reconstructed. Therefore, each of the 2^l possible key k₁pointing to the ciphered submessage c₁ applied a plain text m₁ results with each of the 2^l possible key k₂pointing to the ciphered submessage c₂ applied a plain text m₁ delivers, be combined. Then it is tested whether the decoded part m₁ and m₂ together make a meaningful text. In other words 2^{2 * l} possible key pairs are tried to see if the plain text makes sense. The inventive method causes, although the encryption system uses only keys of length l, the entire text m has a degree of security as if it had been encrypted with a key of length 2l.

0021In order to increase the security level of a message to be encrypted according to the invention, ie to lengthen the actual key length l apparently to a total length T xl, the message m must be decomposed into T randomly formed partial messages. In the following example three decomposition rules are defined:<maths id="math0005" num="(1),"><math display="block"><mrow><msub><mrow><mtext>m = m</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>+ m</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>+ M ...</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><msub><mrow><mtext>+ m</mtext></mrow><mrow><mtext>T</mtext></mrow></msub><msub><mrow><mtext>: = (Mr</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) + (- r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>) + .. + (- r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><msub><mrow><mtext>) + (R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>+ r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>+ ... + r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0902568A2_D0005.tif" /></maths> where r₁, r₂ ... r_T-1 Random numbers are. To avoid calculation errors, such calculations are best modulo a fixed number, z. B. 2⁶⁴ , carry out. The T submessages are then used with T independent keys k₁, k₂ ... k_T encrypted.<maths id="math0006" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><mtable><mlabeledtr><mtext>(2)</mtext><mtd><mrow><msub><mrow><mtext>m = m</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> ⊕ m</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> ⊕..⊕m</mtext></mrow><mrow><mtext>T</mtext></mrow></msub><msub><mrow><mtext> = (m ⊕ r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) ⊕ r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> ⊕..⊕ r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><msub><mrow><mtext> ⊕ (r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> ⊕ r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> ⊕..⊕ r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><mtext>)</mtext></mrow></mtd></mlabeledtr></mtable></mrow></mtd></mtr><mtr><mtd><mrow><mtable><mlabeledtr><mtext>(3)</mtext><mtd><mrow><msub><mrow><mtext>m = m</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>* m</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>* ... * m</mtext></mrow><mrow><mtext>T</mtext></mrow></msub><msub><mrow><mtext> = (m / r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) * (1 / r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>) * ... * (1 / r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><msub><mrow><mtext>) * (R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>* r</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>* ... * r</mtext></mrow><mrow><mtext>T-1</mtext></mrow></msub><mtext>)</mtext></mrow></mtd></mlabeledtr></mtable></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0902568A2_D0006.tif" /></maths>

0022In order to be able to reconstruct the original message m in the receiving device even if partial messages are destroyed or lost during the transmission, a per se known (p, T) Threshold method (also called a secret sharing scheme) is applied to the messages m to decompose T partial messages. The (p, T) -Threshold method is described inter alia in the literature "Modern methods of cryptography", Vieweg Verlag, 1995, Beutelspacher, Schwenk, Wolfenstetter. In one possible (2, T) Threshold method, a linear straight line having a predetermined slope is used on which the submessages lie. With such a graph, it is possible to reconstruct the original message m from two correctly received partial messages.

0023Although the degree of security of a message to be transmitted when using conventional keys can be improved by the method described above; but this requires a higher data transfer rate. For example, the data transfer rate is doubled when the message is split into two sub-messages.

0024According to a second embodiment, it is possible to eliminate the disadvantage of a higher data transmission rate. This can be achieved in our example in that, after the message m has been divided into two sub-messages, only the sub-message m₁ encrypted with an individual key and transmitted in full length. The partial message m₂ formed of a shorter value, after which only the shorter value is encrypted and transmitted. In this way, data transfer rate is reduced. Method for determining a value from which the partial message m₂ can be derived and whose length is shorter than the length of the partial message m₂, are well known. For example, one uses a value representing a randomly generated bit sequence, the partial message m₂ is described by repeating the value. Another possibility, the partial message m₂ is to select a shorter value in the form of a bit sequence which is input as a seed value into a pseudorandom number generator which generates a pseudorandom number r. Instead of the encrypted partial message m, as in our first example₁ represented by the term m-r and the encrypted partial message m₂ , which is represented by the value r to transmit, although now the encrypted partial message m₁ unchanged, but instead of the partial message m₂ now becomes the start value, which is a shorter bit sequence than the partial message m₂ , encrypted and transmitted. If the same pseudo-random generator is used in the receiving device, the pseudo-random sequence or pseudo-random number r can be calculated with the aid of the transmitted starting value, from which in turn the partial messages m₁ and m₂ can be calculated.