- Joined
- Nov 26, 2020
- Messages
- 716
The best thing a computer can do is generate a pseudo-random sequence, which, although it looks random, is actually not. The period of the pseudo-random sequence must be large enough for its subsequence of the required length to be aperiodic, i.e., to have a period that coincides with its length. For example, if you need a string of a million random bits, then you should not use a sequence generator to generate it, which repeats every 65536 bits.
A pseudo-random bit sequence should, as far as possible, be the same as a truly random one. It is necessary that the number of ones in it roughly coincides with the number of zeros, and half of all "stripes" (consecutive identical components of the sequence) have length I. one-fourth - length 2, one-eighth - length 4, etc. Except just listed , there are a number of generally accepted tests that allow you to check whether a given sequence is really pseudo-random.
Quite a lot of attention in mathematics is paid to the creation of good generators of pseudo-random sequences. Currently, it is possible to generate sequences with a period of the order of 2000-3000 bits. The problem is that all pseudo-random sequence generators, under certain conditions, give predictable results and correlations. This is exactly what cryptanalysts expect from pseudo-random sequences in order to launch an effective attack on cryptosystems where these sequences are used.
Cryptographically secure pseudo-random sequences
In cryptography, pseudo-random sequences are much more demanding than simply having certain signs of statistical randomness. For a pseudo-random sequence to be cryptographically secure, it must be unpredictable. This means that for a cryptographically secure pseudo-random bit sequence, it is impossible to say in advance what its next bit will be, even knowing the algorithm for generating this sequence and all its previous bits. Like any cryptographic algorithm, the generator of a cryptographically secure pseudo-random sequence can be attacked and cracked by a cryptanalyptcom. Cryptography teaches how to make such generators resistant to various types of cryptanalytic attacks.
Truly random sequences
A sequence is called no truly random if it cannot be reproduced. This means that if you run a truly random sequence generator twice with the same input, it will produce different random sequences. The main difficulty is to be able to distinguish a random sequence from a non-random one. If you encrypt a string of characters several times using a cryptographic algorithm corresponding to GOST 28147-89, you get a sequence that is very reminiscent of a truly random one. To prove its non-randomness, there is another way, apart from leasing the NSA of the corresponding computing power and an autopsy program. does not exist. However, your rental offer is unlikely to be taken seriously there.
Bad keys
When the sender chooses the key with which he encrypts his messages, his choice usually leaves much to be desired. For example, Petr Sergeevich Ivanov would rather use Ivanov as a key than & 7) g \ *. And not at all because he fundamentally does not want to comply with elementary safety rules. It's just that Ivanov remembers his last name much better than the gibberish of six randomly chosen characters. However, then he will not be helped to keep his correspondence in secret, even the most simple encryption algorithm in the world, especially if the keys used by Ivanov always coincide with the names of his closest relatives and he writes these keys on scraps of paper that he pastes on a computer. In a well-designed brute-force attack, a qualified cryptanatic will not try all keys sequentially, in sequence. He will first check those of them that mean something to Ivanov. This type of brute-force attack is poured into a commodity attack, since during it the adversary uses a dictionary of the most likely keys. This dictionary usually includes:
Name, surname, patronymic, initials, year of birth and other personal information related to this person. For example, in case of a dictionary attack against Peter Sergeevich Ivanov, the first thing to check is PSI, PSIPSI, PIVANOV, Pivanov, psivanov, peteri, pete I, IvanovP, peterivanov, Peter-Ivanov, etc. A
dictionary database made up of people's names, cartoon characters and mythical animals, curses, numbers (both in numbers and in words), titles of feature films, science fiction novels, asteroids, planets and rainbow colors, conventional abbreviations, etc. In total, for one specific person, such a database data has more than 60 thousand vocabulary units.
Words that are obtained by making various changes to the dictionary database compiled in the previous step. This includes the reverse order of writing a word, replacing the Latin letters o, l, z, s with the numbers 0, 1, 2 and 5, respectively, using the word in the plural, etc. This will give about a million more vocabulary units for testing as a possible key to the cipher.
Words obtained by replacing lowercase letters with uppercase letters. In principle, any number of letters can be substituted. For instance. together with the word Ivanov, the words iVanov, ivAnov, ivaNov, ivanOv, ivanoV, IVanov, IvAnov, IvaNov, IvanOv, IvanoV, etc. will be checked. However. the computing power of modern computers allows you to check only one-, two- and three-letter substitutions of lowercase letters for capital letters.
Words in various foreign languages. Although computer users mostly work with English-language operating systems (DOS, UNIX, Windows, and others), there are localized versions of common operating systems that allow the use of another language. This means that any phrase in the native language of its user can be submitted as a key to the input of the encryption program. It should also be borne in mind that the key can be transliterated from any language (for example, from Russian or Chinese) to English and then entered in this form into the encryption program.
A couple of words. Since the number of probable word pairs that a cryptographic key can make up is too large, in practice cryptanalysts usually limit themselves to three and four letter words.
Random keys
A good key is a random bit vector. For instance. if its length is 56 bits, it means that in the process of its generation, any of 2 56 (2 to the power of 56) possible keys can be obtained with the same probability. The source of random keys is usually either a natural random generator (a good analogy for such a generator is a small child who has just learned to walk - the time intervals between his falls are completely random). In addition, the source of the random key can be a cryptographically reliable pseudo-random bit sequence generator. It is better if the key generation process is automated. If you don't have a computer at hand to run a program that implements a pseudo-random generator, or your child has long since passed out of infancy,
Using a good random number generator is very important when generating cryptographic keys, however there is no need to argue too much about which of these generators is more random. It is more important to use strong encryption algorithms and reliable key procedures. If you are in doubt about the randomness of your key selection, you can use one of the key generation methods described later in this chapter.
All encryption algorithms contain so-called weak keys. This means that some of the keys to the cipher are less secure than others. Therefore, when generating keys, you need to automatically check them for strength and generate new ones instead of those that did not pass this test. For example, in the DES-algorithm there are only 24 unstable keys out of a total of 2 56, and therefore the probability of stumbling upon an unstable key is negligible. Besides, how does a cryptanalyst know that a weak key was used to encrypt a particular message or file? And the deliberate refusal to use unstable keys gives the adversary additional information about your cryptosystem, which is undesirable. On the other hand, testing keys for fragility is simple enough to be neglected.
Generating public keys is much more difficult than generating private keys, since public keys must have certain mathematical properties (for example, must be the product of two primes).
Using random keys is not always convenient. Sometimes the key needs to be stored in memory, but it is not so easy for a person to remember 36f9 67аЗ f9cb d931. In this case, for generation, you can use a certain rule that will be obvious to you, but inaccessible to an outsider. Two variants of such a rule:
Make a key from several words, separated by punctuation marks. For example, keys like Yankee'Go home are remembered very simply and for a long time.
Use a combination of letters as an acronym for the longer word. For example, the catchy name of the German wine Liebenfraumilch allows you to generate the key Lbnfrmlch! By dropping the vowels and adding an exclamation mark.
Password
A more attractive approach is that instead of a single word, a rather long, easy-to-remember sentence in Russian, English or another language is used, which is converted into a key. This expression is called a password in cryptography. Any one-way hash function can be used to convert the password to a pseudo-random bit key.
The password should be chosen long enough so that the key obtained as a result of its conversion is random. It is known from information theory that in an English sentence, each letter contains approximately 1.3 bits of information. Then, to get a 64-bit key, the password must be about 49 letters, which corresponds to an English phrase of 10 words.
The password needs to be easy to remember if desired, and at the same time it needs to be sufficiently unique. The quote from Kozma Prutkov, which everyone has heard, is hardly suitable, since his compositions are available in a form that can be reproduced on a computer, and therefore, can be used in a dictionary attack. It is better to use the work of a little-known poet or playwright, citing it with errors. A greater effect can be achieved if foreign words are present in the quote used to generate the key. Simple swear words are ideal for this purpose - you don't have to write them down to remember. It is enough to shake yourself on the finger with a hammer, and the password will automatically come to your mind. You just need to restrain yourself and not say it out loud so that strangers do not overhear.
A pseudo-random bit sequence should, as far as possible, be the same as a truly random one. It is necessary that the number of ones in it roughly coincides with the number of zeros, and half of all "stripes" (consecutive identical components of the sequence) have length I. one-fourth - length 2, one-eighth - length 4, etc. Except just listed , there are a number of generally accepted tests that allow you to check whether a given sequence is really pseudo-random.
Quite a lot of attention in mathematics is paid to the creation of good generators of pseudo-random sequences. Currently, it is possible to generate sequences with a period of the order of 2000-3000 bits. The problem is that all pseudo-random sequence generators, under certain conditions, give predictable results and correlations. This is exactly what cryptanalysts expect from pseudo-random sequences in order to launch an effective attack on cryptosystems where these sequences are used.
Cryptographically secure pseudo-random sequences
In cryptography, pseudo-random sequences are much more demanding than simply having certain signs of statistical randomness. For a pseudo-random sequence to be cryptographically secure, it must be unpredictable. This means that for a cryptographically secure pseudo-random bit sequence, it is impossible to say in advance what its next bit will be, even knowing the algorithm for generating this sequence and all its previous bits. Like any cryptographic algorithm, the generator of a cryptographically secure pseudo-random sequence can be attacked and cracked by a cryptanalyptcom. Cryptography teaches how to make such generators resistant to various types of cryptanalytic attacks.
Truly random sequences
A sequence is called no truly random if it cannot be reproduced. This means that if you run a truly random sequence generator twice with the same input, it will produce different random sequences. The main difficulty is to be able to distinguish a random sequence from a non-random one. If you encrypt a string of characters several times using a cryptographic algorithm corresponding to GOST 28147-89, you get a sequence that is very reminiscent of a truly random one. To prove its non-randomness, there is another way, apart from leasing the NSA of the corresponding computing power and an autopsy program. does not exist. However, your rental offer is unlikely to be taken seriously there.
Bad keys
When the sender chooses the key with which he encrypts his messages, his choice usually leaves much to be desired. For example, Petr Sergeevich Ivanov would rather use Ivanov as a key than & 7) g \ *. And not at all because he fundamentally does not want to comply with elementary safety rules. It's just that Ivanov remembers his last name much better than the gibberish of six randomly chosen characters. However, then he will not be helped to keep his correspondence in secret, even the most simple encryption algorithm in the world, especially if the keys used by Ivanov always coincide with the names of his closest relatives and he writes these keys on scraps of paper that he pastes on a computer. In a well-designed brute-force attack, a qualified cryptanatic will not try all keys sequentially, in sequence. He will first check those of them that mean something to Ivanov. This type of brute-force attack is poured into a commodity attack, since during it the adversary uses a dictionary of the most likely keys. This dictionary usually includes:
Name, surname, patronymic, initials, year of birth and other personal information related to this person. For example, in case of a dictionary attack against Peter Sergeevich Ivanov, the first thing to check is PSI, PSIPSI, PIVANOV, Pivanov, psivanov, peteri, pete I, IvanovP, peterivanov, Peter-Ivanov, etc. A
dictionary database made up of people's names, cartoon characters and mythical animals, curses, numbers (both in numbers and in words), titles of feature films, science fiction novels, asteroids, planets and rainbow colors, conventional abbreviations, etc. In total, for one specific person, such a database data has more than 60 thousand vocabulary units.
Words that are obtained by making various changes to the dictionary database compiled in the previous step. This includes the reverse order of writing a word, replacing the Latin letters o, l, z, s with the numbers 0, 1, 2 and 5, respectively, using the word in the plural, etc. This will give about a million more vocabulary units for testing as a possible key to the cipher.
Words obtained by replacing lowercase letters with uppercase letters. In principle, any number of letters can be substituted. For instance. together with the word Ivanov, the words iVanov, ivAnov, ivaNov, ivanOv, ivanoV, IVanov, IvAnov, IvaNov, IvanOv, IvanoV, etc. will be checked. However. the computing power of modern computers allows you to check only one-, two- and three-letter substitutions of lowercase letters for capital letters.
Words in various foreign languages. Although computer users mostly work with English-language operating systems (DOS, UNIX, Windows, and others), there are localized versions of common operating systems that allow the use of another language. This means that any phrase in the native language of its user can be submitted as a key to the input of the encryption program. It should also be borne in mind that the key can be transliterated from any language (for example, from Russian or Chinese) to English and then entered in this form into the encryption program.
A couple of words. Since the number of probable word pairs that a cryptographic key can make up is too large, in practice cryptanalysts usually limit themselves to three and four letter words.
Random keys
A good key is a random bit vector. For instance. if its length is 56 bits, it means that in the process of its generation, any of 2 56 (2 to the power of 56) possible keys can be obtained with the same probability. The source of random keys is usually either a natural random generator (a good analogy for such a generator is a small child who has just learned to walk - the time intervals between his falls are completely random). In addition, the source of the random key can be a cryptographically reliable pseudo-random bit sequence generator. It is better if the key generation process is automated. If you don't have a computer at hand to run a program that implements a pseudo-random generator, or your child has long since passed out of infancy,
Using a good random number generator is very important when generating cryptographic keys, however there is no need to argue too much about which of these generators is more random. It is more important to use strong encryption algorithms and reliable key procedures. If you are in doubt about the randomness of your key selection, you can use one of the key generation methods described later in this chapter.
All encryption algorithms contain so-called weak keys. This means that some of the keys to the cipher are less secure than others. Therefore, when generating keys, you need to automatically check them for strength and generate new ones instead of those that did not pass this test. For example, in the DES-algorithm there are only 24 unstable keys out of a total of 2 56, and therefore the probability of stumbling upon an unstable key is negligible. Besides, how does a cryptanalyst know that a weak key was used to encrypt a particular message or file? And the deliberate refusal to use unstable keys gives the adversary additional information about your cryptosystem, which is undesirable. On the other hand, testing keys for fragility is simple enough to be neglected.
Generating public keys is much more difficult than generating private keys, since public keys must have certain mathematical properties (for example, must be the product of two primes).
Using random keys is not always convenient. Sometimes the key needs to be stored in memory, but it is not so easy for a person to remember 36f9 67аЗ f9cb d931. In this case, for generation, you can use a certain rule that will be obvious to you, but inaccessible to an outsider. Two variants of such a rule:
Make a key from several words, separated by punctuation marks. For example, keys like Yankee'Go home are remembered very simply and for a long time.
Use a combination of letters as an acronym for the longer word. For example, the catchy name of the German wine Liebenfraumilch allows you to generate the key Lbnfrmlch! By dropping the vowels and adding an exclamation mark.
Password
A more attractive approach is that instead of a single word, a rather long, easy-to-remember sentence in Russian, English or another language is used, which is converted into a key. This expression is called a password in cryptography. Any one-way hash function can be used to convert the password to a pseudo-random bit key.
The password should be chosen long enough so that the key obtained as a result of its conversion is random. It is known from information theory that in an English sentence, each letter contains approximately 1.3 bits of information. Then, to get a 64-bit key, the password must be about 49 letters, which corresponds to an English phrase of 10 words.
The password needs to be easy to remember if desired, and at the same time it needs to be sufficiently unique. The quote from Kozma Prutkov, which everyone has heard, is hardly suitable, since his compositions are available in a form that can be reproduced on a computer, and therefore, can be used in a dictionary attack. It is better to use the work of a little-known poet or playwright, citing it with errors. A greater effect can be achieved if foreign words are present in the quote used to generate the key. Simple swear words are ideal for this purpose - you don't have to write them down to remember. It is enough to shake yourself on the finger with a hammer, and the password will automatically come to your mind. You just need to restrain yourself and not say it out loud so that strangers do not overhear.
