DE19707288A1 - Cipher system for enciphering data - Google Patents

Abstract

The system splits a data block and joins the single characters in a different sequence. Preferably, each character of the data block is cyclically shifted according to an individual key in a character table. The necessary keys are generated by a mathematical function which uses the single characters of the password and the data as parameters. The used function is composed from mathematical terms which does not permit an explicit representation of the parameters.

Description

The invention relates to a device according to the preamble of claim 1.

To ensure the safest possible data transmission, the data to be backed up Information encoded using pseudo-random keys.

It is known to keep confidential information with special mathematical functions encrypt. So z. B. RSA (U.S. Patent No. 4,405,829) an algorithm that results in a certain mixing of the plain text leads. Many other processes, including DES, use a mathematically reversible function for encryption that leads to a relative Security of the ciphertext leads.

The disadvantages of these systems lie in the reversibility of the function that is absolutely necessary Encryption, otherwise decoding would not be possible. Of course this is the Function not only reversible for the appointed but also for the uninitiated decipherer. A restriction of the passwords to a maximum length of 32 characters leaves the successive Exhaustion does not come completely from the efficiency range of professional decipherers. Also In some established systems, particular importance is attached to secrecy System parts laid. However, this limitation is not for professional use acceptable, because by "reverse engineering", ie by decompiling those mentioned System parts can be analyzed. Because of the high cost of decompilation programs, this is System analysis method, of course, highly inefficient for private individuals. This is the only way possible these coding programs without major danger to the system of a wide To provide population strata. The security of the ciphertext is therefore from Equipment of the unauthorized decipherer and thus the above mentioned Algorithms in which e.g. B. a system part must not be kept secret for large companies applicable.

In addition, poorly chosen output parameters for the coding often endanger the Ciphertext. If you ignore ciphering errors, the short period length is the Most established systems are the main break-in point for cryptanalysts.

The object of the invention is to enable the use of an arbitrarily long password that firstly, cannot be derived from an unauthorized deciphered text and secondly, all of them Characters of the ASCII character set may contain. In addition, a short password may allow security of the system. It is also an object of the invention that the complexity of the Encryption system can be adapted to the computing power of the respective time. So that's it Main object of the invention to secure any type of computerized data and unbreakable encrypt.

This object is achieved by a device with the features of claim 1.  

The password can have a variable length (one to 1,457,664 characters) and cannot be from the Sub keys are derived. A password the length of which is very short may compromise the security of the Do not endanger the system. When creating the password, the entire ASCII character set may be used be used. The complexity of the subkey can affect the computing power of each Time should be adjusted and should be as close as possible to a stochastic random sequence.

Material recorded by the uncalled decipherer does not give it an advantage. The complete system structure may be publicly known.

All that remains for the uninitiated decipherer is to try out the passwords to get the code crack. The ciphertext is no longer than the plaintext. There is a review that the Can clearly identify communication partners.  

The Enigma MM encryption system 1. Structure of the Enigma MM

The Enigma MM consists of an introductory polyalphabetic cipher PS ₀ and 32 TpaC coding blocks. The encryption PS ₀ uses the key S ₀ and serves to subject the plain text in 4-kilobyte blocks to an input encryption. I will talk about the formation of the keys and the exact sequence of PS ₀ after the explanation of the TpaC's. As inputs, these transposition polyalphabetic coding blocks require an input intermediate secret text (T _n ), a key with a length of 1024 bytes (B _n ) and a key with a length of 4 kB (S _n ). As output, they provide an intermediate output secret text (T _{n + 1} ), which is passed as input to the TpaC (n + 1) until n has reached the value 32. The output of the TpaC (32) is the final ciphertext.

A TpaC essentially consists of three parts: first, the splitter, which divides the input text into three parts depending on the frequency, the bit transitions occurring in the key B _n , and second, the reconjugator, which in turn depends on the key B _n , these three parts and thirdly, the polyalphabetic cipher PS _n , which ensures that the key B _n cannot be found out by permuting the original text.

1.1 The splinter

The splitter first analyzes the subkey B _n by counting how many bit transitions (01, 10, 11, 00) there are in each case. A bit can only be an element of a transition, and of course its bits must be adjacent. Example: (010) is not [01] and [10] but only [01] (processing of links). If the frequencies (| [01] | = a; | [11] | + | [00] | = b; | [10] | = c) are now known, the input text is cut into three groups T ₁ to T ₃ . The cut between T ₁ and T ₂ occurs after the a-th position (start of counting at the beginning of the block), and between T ₂ and T ₃ at the (a + b) -th position.

The truth value of the equation (a + b + c) -4096 = 0 is now checked for error detection. If it is 1, the decomposition was correct, but if it is 0, an error occurred during the calculation and the decomposition must be carried out again. The length of the subkey B _n results from the following consideration: The plain text is transferred to the splitter in blocks of 4 kilobytes. So we need 4096 transitions to map each character to a subtext. We need 2 bits for each transition, i.e. 8192 bits for the entire block. In order to save storage space, these bits are not saved as decimal values, but rather in bytes. Eg [10], [01], [11], [00] would be saved as 10011100 = 156 = £ (see ASCII table). We can accommodate 4 transitions in one byte and thus the length of the binary key

hold tight.  

1.2 The Reconjugator

After the plaintext is available in three partial texts T _n1 , T _n2 and T _n3 , the work of the reconjugator begins by placing a pointer to the first character of each partial text and the still empty intermediate secret text (Zgt _n ), and then the first bit transition from B _n analyzed. If this is [01], the reconjugator writes the first character from T _n1 to the first position of Zgt _n and then shifts the pointers to Zgt _n and T _n1 by one character each. This prevents a character from a partial text from appearing twice in the intermediate secret text or from two characters (e.g. from T _n2 and T _n3 ) being written to the same position in Zgt _n .

Now consider the second bit transition: If this is again [01], the character to which the pointer * T _n1 points (meanwhile this points to the second character) is written to the position in Zgt _n to the * Zgt _n (i.e. to position 2) shows. The pointers * T _n1 and * Zgt _{n are} then moved forward by one character each.

Now follows z. For example, a transition [10], the first character of T _n3 (* T _n3 still points to the first character) is written to the position to which * Zgt _n (here: third position) points.

This procedure is repeated until * Zgt _{n is set} to the 4097th character (termination NULL byte). Now we have a character string with a length of 4096 bytes, which is now passed to the polyalphabetic encryption PS _n . To check the conjugation, the pointer positions of * T _n1 , * T _n2 and * T _{n3 are} analyzed. These must each point to the a-th character of T _n1 , the b-th character of T _n2 and the c-th character of T _n3 .

Now the question remains why the transitions [00] and [11] are combined. All possible transitions have the same frequencies on average. If, however, [00] and [11] are combined, a certain asymmetry is obtained which, if the transitions [00] and [11] are additionally assigned to the partial text T _n2 , represents a difficult obstacle for the uninitiated decipherer. If there are transitions [00] and [11] in the key B _n , it follows that there are 2 ^b keys that would lead to the same result.

In total there are three states on the 4096 positions: [01]; ([00], [11]) or [10]; the number of all possibilities = status ^positions = 3 ⁴⁰⁹⁶ possible keys. Now we consider all positions where [00] or [11] is (number is b). At these locations, only two states, either [00] or [11], can be assumed. Since the above rule also applies here, one can say that states ^positions = 2 ^b different keys lead to the same result. With an expected value for b of approx.

this would lead to 2 ¹³⁶⁵ possible keys, of which only one allows a conclusion to the correct password.

This trick does not improve the security of the ciphertext, but even reduces the possibilities by a factor of 2 ¹³⁶⁵ , but it makes it extremely difficult to derive the correct key from an unauthorized decoded ciphertext in order to find the next partial key or even the password close. The deeper connection between B _n , S _n and password is discussed after the explanation of the final polyalphabetic cipher PS _n . The following definition should be noted for the reconjugator:
Def .: In [01] the current character (pointed to by * Tn1) is taken from T _n1 and placed in the next position in Zgt _n .
At [00] or [11] the current character is taken from T _n2 and placed in the next position in Zgt _n .
In [10] the current character is taken from T _n3 and placed in the next position in Zgt _n .

1.3. The final polyalphabetic cipher PS _n

After the reconjugator has done his work, he transfers the intermediate secret text Zgt _n to the module PS _n . This receives the 4096 byte long text Zgt _n and the key S _n as input. As output it delivers a 4096 byte long string which is passed as input to TpaC (n + 1) as long as the condition n <32 is fulfilled. If n = 32, the output is transferred to a module that combines the individual 4096 byte strings to form the overall secret text and provides them with check bytes. The actual polyalphabetic encryption is relatively simple mathematically. The decimal values of Zgt _n and S _{n are written} together and modulo 256 added. The decimal result is then converted back into an ASCII character. In order to make coding in the stochastic sense unbreakable, the key must meet the following conditions, as already formulated by AN Kolmogorov:
"For every finite substring [of the key S _n ] there is no shorter algorithmic description than the listing of the substring - no substring can be compressed into a shorter description".

The subkeys thus form a kind of "template" that is added to the actual secret text. The length of this individual "template" corresponds to that of the secret text. If this is to be deciphered without being called, all possible templates must be tried out if the password is unknown. This means that you have to shift each character by all possible values (256 pieces) to get the correct result. With a block length of 4096 bytes, the number of possible individual keys is 256 ⁴⁰⁹⁶ . Unauthorized deciphering is impossible without certain help, because you can generate any possible plain text from a secret text and any individual key. Decoding by means of an analysis of character frequencies or the analysis of periodic occurrence of character pairs is therefore ineffective. Even in the case of a partial compromise of plain text / cipher text, this does not immediately lead to the disclosure of the entire plain text. Encrypting with individual keys makes it extremely difficult, if not impossible, to decipher unrequested. The separation of key and password by a one-way function leads to additional security.

2. The key generation module Sem 2.1 Demands on the semester

In the following paragraph, I would like to go into the formation of the individual subkeys B _n (1024 bytes) and S _n (4096 bytes). All keys are generated by a function that enables the keys to be easily derived from the password, but not from them. In addition, the function must produce a key that, in the sequence of its individual characters, corresponds as far as possible to the above requirements (Kolmogorov), i.e. produces an almost random sequence of numbers from the parameters (password) that are transferred, but this depends to a large extent on the password and the date . The last requirement for the key generation module (sem) is:
If the output parameters are changed slightly, a completely different key (and partial key) is produced, which has different values than its predecessor in at least 98% of the places.

2.2. The structure of the sem

As an input, the sem requires a password in the form of an arbitrarily long string Pw and the date. It provides the keys S _n and B _n as output. Since the plain text is not encrypted with the Enigma MM with a function that should be really involved, but with an individual key, we do not have to pay attention to the reversibility of the function that produces the key (it is even not desired), however, it must be ensured that the appointed decipherer can understand the formation of each partial key. It follows that the formation of the keys for the encryption and for the decryption must be identical.

Since the user of the Enigma MM has the option of using an arbitrarily long password, Pw must be brought into a suitable form at the beginning. For practical reasons, we restrict this "any length" to a length of 1,457,664 characters. This length was chosen because it corresponds to the length of the largest character string that can still be stored on a 3.5 '' floppy disk. The number of possible passwords can be calculated with the following consideration: If the password is one character long, we have 256 options for the assignment. If the password has a length of two, we already have 256 ² options available plus the 256 options that we would have if it were not just two characters but one. This results in the series:

We now have the password in the form of a character string, the length of which is variable. However, since we need fixed-length strings as output, we have to try to change Pw so that it delivers fixed-length results without losing information. This is possible if you break down the password and pass the fragments as parameters to a function that can handle a variable number of parameters. The password is broken down as follows: First, the length n of Pw is recorded and analyzed. Then the decimal value of each character dec (Pw) _{x is} calculated, divided by 255 (hence: 0 <= u _k <= 1; D _k = {1,2,..., N}), in u ₁ , u _2,. . ., u _n saved and transferred to the following function. In addition, the date is broken down into its individual components and also transferred to the function according to the following example:

d _n is thus from the interval D = [0; 9];

This function can be continued in itself and can therefore take any number of parameters. x, u ₁ to u _n and d ₁ to d ₈ are considered by the function as a degree. The initial term is necessary in order to maintain as much mixing as possible with short passwords, i.e. with a small n. As a result, the function always returns a value between 0 and 1. In order to determine the starting value q ₀ for x, we form the checksums from u ₁ to u _n , calculate the mean value from it and multiply it by 10. q is passed with an accuracy of 15 decimal places. Now comes the function Sf [l, q ₁ , f (x, u ₁ , u ₂ ,..., U _n )], which is defined as follows:

To complete the key generation process, the ProcSB [n] procedure is defined as follows:

ProcSB [n] is carried out 32 times (for n = 1 to n = 32). Then we have B ₁ to B ₃₂ and S ₁ to S ₃₂ available.

This results in the performance characteristics of the sem:

• - There is an efficient method for calculating the sub-keys B _n , S _n , E _m and S _m from the password Pw.
• - There is no efficient method for calculating Pw from the sub-keys B _n , S _n , E _m or S _m .
• - The strings of the keys B _n , S _n , E _m and S _m generated from Pw cannot be reduced in efficient time by today's computers to their equation and their parameters (password) and should be the condition of Kolmogorov, as far as it can be done by mathematical means is possible to fulfill.
• - Minor changes in the password result in a modification at least 98% of the characters in the ciphertext.
• - The keys generated depend on the date.

3. The decoding

The keys S ₀ to S ₃₂ and B ₁ to B _{32 are} required for decoding. In addition, you need the 4096 byte input text Egt. The module mentioned in 1.3, which is used for the encryption to merge the individual source secret text blocks, is used here to decompose the overall secret text. To do this, certain check bytes must first be removed and then the text broken down into 4096 byte input secret texts (Egt).

The decryption proceeds in the following way: First, the inverses from S ₀ to S ₃₂ with respect to the addition modulo 256 are determined. The definition of the inverse is as follows:
Each element of the key S _n linked with its inverse results in the neutral element of the addition modulo 256.

(S _n ) _x + ((S _n ) ⁻ ¹ ) _x = 0 = 256 modulo 256.

It follows:

((S _n ) ⁻ ¹ ) _x = (256 - (S _n ) _x ) modulo 256.

Since the difference between 256 and (S _n ) _{x is} always less than 256 and greater than or equal to zero (all elements of S _n are from the set {0, 1, 2,..., 255}), the final modulo 256 can be omitted. The formula for ((S _m ) ⁻ ¹ ) _{x is} :

((S _n ) ⁻ ¹ ) _x = 256 - (S _n ) _x .

Now the modules of the TpaCs are processed in reverse order. First you put the key (S _n ) ⁻ ¹ over the input secret text Egt and add this modulo 256. If correctly executed, the intermediate secret text Zgt (n) results.

Now the bit transitions of the key B _{n are} analyzed and then three string chains of length a (T _n1 ), b (T _n2 ) and c (T _n3 ) are created. The analysis of B _n is analogous to that discussed in 1.1. Now the key B _{n is placed} on the character string Zgt (n), so that each bit transition from B _n can be assigned a character from Zgt (n), e.g. E.g .: Zgt (n) = "Hallo_!"

Subsequently, each character assigned to a [01] transition is written in turn (processing of links) in T _n1 . The same happens with the characters that have been assigned to a [00] or [11] or [10] transition, but they are written after T _n2 or T _n3 . The strings T _n1 , T _n2 and T _{n3 are then connected} to one another in succession, and the interim secret text Zgt (n-1) is obtained, which is passed on to the TpaC⁻ ¹ (n-1).

Finally, a module again ensures that the 4096 byte long plain texts are attached to one another and provided with test bits.

Claims (4)

1. Encryption system for encrypting all types of data, characterized in that the data block is first split and then the individual characters are reassembled in a different order (see drawing). 2. Device according to claim 1, characterized in that each character of the data block is cyclically shifted according to an individual key in a character table (drawing: PS _n ). 3. Apparatus according to claim 1 or 2, characterized in that the required keys (B _n and S _n ) are generated by a mathematical function that uses the individual characters of the password and the date as a parameter. 4. The device according to claim 3, characterized in that the function used in claim 3 mathematical terms that do not explicitly represent the parameters allow.