Some mathematical problems of information security
Along with political, socio-economic, organizational, military, legal, special and informational problems, the solution of which is provided for at the state, federal level, there are mathematical problems in the information sphere, which will be discussed in the paper. The paper presents and specifies some important concepts and basic provisions of information security and information security. The main regulatory documents in this area are the Constitution of the Russian Federation - the basic law, the Federal Law on Security, Military Doctrine and the Doctrine of Information Security, as well as the governing documents of the Federal Service for Technical and Export Control (RD FSTEC)
Information security of the state is the state of protection of its national interests in the information sphere. Information sphere - a set of information infrastructure of the country, information, entities engaged in the collection, formation, dissemination and use of information, as well as the system of regulation of the resulting public relations. The information sphere is a system-forming factor in the life of a society, part of the social activity of a society.
The purpose of writing is to strive to focus the attention of readers on the priority mathematical problems in the field of information security and information protection, without solving which progress in the coming years (possibly a decade) cannot be expected.
Description of the situation of information interaction (impact)
')
We consider a group of user subscribers G = {u1, u2, ..., un}, located in different nodes of a communication network or a computer network that exchange messages transmitted over unprotected network channels. It is clear that messages may contain information that is not intended for a wide audience. Subscribers of the communication system would like to have access and contact with each other as the need arises, preserve the confidentiality of their messages, and ensure that the message received at the receiving side matches the one that was prepared and sent by the sending party, i.e. preserve integrity. In addition to the above-mentioned requirements, both communicating subscribers would not like to become participants in the “grandmaster attack”. With a high level of confidence, they would like to know that they communicate with each other, and not with figureheads, to be able to implement mutual authentication - authentication of the sender by the recipient and vice versa. When fulfilling the above requirements for communication system services, the quality of the message reception / transmission should be as stated.
Thus, reliability, integrity, confidentiality, availability should be provided to each pair of communicating users in any communication network. The fulfillment of these requirements in networks is provided by various means, software and hardware complexes that implement quite complex algorithms, programs developed in the framework of the theories of telecommunications, coding and cryptology.
The proposed paper discusses the basic concepts and provisions of cryptology, representing closely interacting cryptography and cryptographic analysis with adjacent steganology: formed by steganography and steganographic analysis. The tasks of information exchange, in particular, cryptography and coding theory are the tasks of ensuring confidentiality, authenticating subscribers and verifying the integrity of messages, ensuring the accessibility of subjects to objects and resources, which is achieved by the distribution and delimitation of access. The first task (confidentiality) is solved by using a cryptographic system (CRS), encrypting messages, the second is using an electronic digital signature (EDS), and the third task is to establish the coincidence of digests transmitted and generated by the recipient. The task of ensuring integrity is solved by methods of the theory of codes, encoding / decoding messages with error correction codes, correction codes. About accessibility already mentioned earlier.
The general scheme of the implementation of a communication session between a pair of subscribers (point-to-point) is presented in Figure 1.
Figure 1 - Scheme of the implementation of the communication session of subscribers using a single-key symmetric KGS, key management system and coding system
Secure messaging technology
Information exchange technology includes subjects, objects, resources and processes. The subjects are the recipient and the sender of the message, resources (financial, network, computational, temporary), objects: the source of the message that forms the message, the message itself, the keys generated by the key system, the encryption / decryption device, the encoder / decoder, the display or the printer There is a device for displaying a message in a form that is accessible to all subjects by recipients and senders.
The sequence of processing the message should be as shown in Figure 1. This is due to the fact that in the presence / absence of distortions of the encryption message, its decryption in the first situation with errors is impossible. Therefore, it is necessary to preset the presence of errors in the message on the recipient side of the message and make corrections if there are any errors. Only after the elimination of errors is it possible to successfully decrypt the message. In parallel with the processing of the message, a digital signature is processed and verified.
Single-key cryptographic system . The required, necessary session attributes are the user ID, the access password and, most importantly, the encryption key. In the classical traditional cryptographic system (CGS), the sender and receiver both use the same key for encryption and decryption. For this reason, such encryption systems are called single-key ( symmetric ). It is clear that both parties must have the key before the communication session, i.e. the key must be developed, distributed (which pair of keys to whom) and distributed (delivered) to subscribers. This is a key management task. For its successful solution requires a secure (dedicated) channel key distribution. Often the key was delivered by a special diplomat. The name of one of them, Theodore Netta, is widely known and entered into literature and history.
Two-key cryptographic system. In 1978, a publication appeared on a new type of CHS - a two-key system. They also call it an asymmetric , system with open doors. The sender and recipient of the message use different keys. Using a public key it is computationally very difficult to find a private key. In this system, each subscriber independently generates his own key pair: the public key available to all senders, which all subscribers must use to create the encryption message, and the recipient's private private key d , which the recipient keeps secret from everyone, does not disclose it.
In such systems, there is no need to distribute keys, which, of course, simplifies the new technology of secure communication. But nothing is given for nothing. The two-key systems have their drawbacks. Encryption in them is quite a slow process. The emergence of such two-key systems became possible due to the introduction into the circulation of information security of a new mathematical object — a one - way function and, in a set of such functions, functions with a secret entrance (with a loophole). The point here is this. We can easily multiply a pair of numbers p and q and get one number N = pq. The calculations here are directed in one direction. Now let's say a composite number N is given and it is necessary to define its divisors. This problem for large numbers (10 150 -10 300 ) is currently practically not solved, if there is no loophole (secret door). Such a loophole could be, for example, one of the dividers or the value of the Euler function from N.
In a two-key public-secretary public address system, the recipient of the messages, which establishes the PSC, such a divisor knows he has a loophole.
Electronic digital signature (EDS) . Digital signatures also use two keys: the signature key is private (not disclosed) and the public (public) signature verification key.
The sender encrypts his message in the recipient’s public key, and signs the encryption message with his private key. The public key of the sender's signature is available to everyone and the recipient, using it and verifying the digital signature, makes sure that the message is sent and signed by this sender.
Processes in CGS . The main processes of secure information exchange are described in encryption standards and digital signatures GOST 28147 - 89 - for encryption and GOST 34.10 - 2012 - for digital signatures.
With secure information exchange of subscribers, the following basic processes are implemented. Setting CGS, generating 4 keys (2 for encryption and 2 for digital signature of the recipient), generating a message, encrypting a message, signing, encoding, sending by the sender, environmental impact and / or intruder, receiving a message, decoding, decrypting, verifying a digital signature, converting in a form convenient for perception by the recipient. We give a brief description of the processes.
Installation of CGS. Recipient A selects two large primes p A and q A , multiplies them and gets the cipher module N A , and also calculates the value of the Euler function F (N A ). After that, it selects the public key eA such that (eA, Φ (NA)) = 1, and calculates, using the Euclidean extended god algorithm, the private key dA, such that eA dA ≡1 (mod F ( N A )).
Values (e A and N A ) and the recipient's nickname are declared on the network server open and accessible to all who will send their messages to the recipient A. The values of d A , p A , F (N A ), and q A are kept secret from all . Access of the intruder to any of these values leads to cracking of the CHS.
Possible attack on the cipher message. Suppose the infringer knows F (N A ), and e A d A - 1 is divided by F (N A ). Knowledge of F (N A ) provides the calculation of p A and q A , sincep A + q A = N A + 1 - F (N A ); p A - q A = [(p A + q A ) 2 + 4F (N A )] 0.5 . It can be shown that the values are multiple Euler functions F (N A ) are also sufficient for calculating p A and q A.
Sender B converts the generated message into a numerical form (binary form) and breaks it into blocks of length [log2N A ] = m Bi - blocks of the source text. After that, the remains of m Bi e A (modN A ) = Bi are the cipher message blocks, and then sent to recipient A.
The recipient, having encrypted message blocks, decrypts them using the private key, i.e. finds residues of Bi d A (modN A ) = m Bi .
Mathematical problems of information security
Object modeling (networks of local, corporate, global, subscriber groups), processes of receiving / transmitting protected messages, information exchange and interaction is a vast area with its own tasks and problems of various nature for applications of algorithms for studying and improving information security.
The problems of protecting information exchange and information technology are also reflected in mathematical theories, for example, in number theory. The central problem of the present time is the problem of the expansion of large numbers into factors. In cryptology, it is associated with the tasks of cryptography, the selection of key information, and in cryptanalysis - with attacks on two-key CGS.
Such attacks are considered both by the violators and by their cryptanalyst analysts. The purpose of the latter is to identify the weak points of the algorithms and crypto protocols. Detected vulnerabilities are eliminated by improving products, or if it is impossible to eliminate them, they move to new, more sophisticated and modern means.
Another important problem is to obtain prime numbers of high resolution and in mass quantities. In computer networks and communication networks, the exchange of secure messages requires from the key management systems the mass production of prime numbers, which are selected from the full set at random. Earlier it was said that each subscriber of the network generates for himself at least 4 keys, which he must update at regular intervals. This means that the need for primes exists all the time, as the number of users is only increasing. Today almost every inhabitant of developed countries and the majority of people in developing countries have mobile phones. Cellular communication systems cover all large areas and the stopping of this process is not expected in the near future.
Closely to the named problem is adjacent the problem of establishing the simplicity of a number of large bit depth.
The problem of discrete logarithm. Diffie-Hellman key provisioning protocol (DHDLP, 1976). Subscribers A and B choose the prime number p and the prime g with the order p -1 modulo p, i.e. g p-1 ≡1 (mod p), but g n ≠ 1 (mod p), for any n <p -1. Subscribers A and B choose prime numbers n <p and m <p, respectively. Then the residuals g n (mod p), g m (mod p) are calculated and each of the subscribers sends the result of their calculations to the other. Then both calculate the values ofA: k ≡ g nm (g m ) n (mod p) , and B: k ≡ g nm ≡ (g n ) m (mod p), i.e. Subscribers now have the same key values that were not transmitted over a communication channel through the network and could not be intercepted there. It turned out symmetrical CGS.
The intruder can intercept and have the values of g n (mod p), g m (mod p), but using them to quickly obtain n and m or k ≡ g nm (mod p) is not enough.
A similar problem of the discrete logarithm exists for elliptic curves (EC) over finite fields (ECDLP, 1985 N.N. Koblitz, V. Miller). On the EC E (Fp) there is an Abelian group formed by the points of this curve. This group is cyclic and of very large order. In other words, for given two points, EC E (Fp) over the field Fp, points P, Q∈E (Fp) need to find a number λ (if it exists) such that Q = [λ] P.
Information security of the state is the state of protection of its national interests in the information sphere. Information sphere - a set of information infrastructure of the country, information, entities engaged in the collection, formation, dissemination and use of information, as well as the system of regulation of the resulting public relations. The information sphere is a system-forming factor in the life of a society, part of the social activity of a society.
The purpose of writing is to strive to focus the attention of readers on the priority mathematical problems in the field of information security and information protection, without solving which progress in the coming years (possibly a decade) cannot be expected.
Description of the situation of information interaction (impact)
')
We consider a group of user subscribers G = {u1, u2, ..., un}, located in different nodes of a communication network or a computer network that exchange messages transmitted over unprotected network channels. It is clear that messages may contain information that is not intended for a wide audience. Subscribers of the communication system would like to have access and contact with each other as the need arises, preserve the confidentiality of their messages, and ensure that the message received at the receiving side matches the one that was prepared and sent by the sending party, i.e. preserve integrity. In addition to the above-mentioned requirements, both communicating subscribers would not like to become participants in the “grandmaster attack”. With a high level of confidence, they would like to know that they communicate with each other, and not with figureheads, to be able to implement mutual authentication - authentication of the sender by the recipient and vice versa. When fulfilling the above requirements for communication system services, the quality of the message reception / transmission should be as stated.
Thus, reliability, integrity, confidentiality, availability should be provided to each pair of communicating users in any communication network. The fulfillment of these requirements in networks is provided by various means, software and hardware complexes that implement quite complex algorithms, programs developed in the framework of the theories of telecommunications, coding and cryptology.
The proposed paper discusses the basic concepts and provisions of cryptology, representing closely interacting cryptography and cryptographic analysis with adjacent steganology: formed by steganography and steganographic analysis. The tasks of information exchange, in particular, cryptography and coding theory are the tasks of ensuring confidentiality, authenticating subscribers and verifying the integrity of messages, ensuring the accessibility of subjects to objects and resources, which is achieved by the distribution and delimitation of access. The first task (confidentiality) is solved by using a cryptographic system (CRS), encrypting messages, the second is using an electronic digital signature (EDS), and the third task is to establish the coincidence of digests transmitted and generated by the recipient. The task of ensuring integrity is solved by methods of the theory of codes, encoding / decoding messages with error correction codes, correction codes. About accessibility already mentioned earlier.
The general scheme of the implementation of a communication session between a pair of subscribers (point-to-point) is presented in Figure 1.
Figure 1 - Scheme of the implementation of the communication session of subscribers using a single-key symmetric KGS, key management system and coding system
Secure messaging technology
Information exchange technology includes subjects, objects, resources and processes. The subjects are the recipient and the sender of the message, resources (financial, network, computational, temporary), objects: the source of the message that forms the message, the message itself, the keys generated by the key system, the encryption / decryption device, the encoder / decoder, the display or the printer There is a device for displaying a message in a form that is accessible to all subjects by recipients and senders.
The sequence of processing the message should be as shown in Figure 1. This is due to the fact that in the presence / absence of distortions of the encryption message, its decryption in the first situation with errors is impossible. Therefore, it is necessary to preset the presence of errors in the message on the recipient side of the message and make corrections if there are any errors. Only after the elimination of errors is it possible to successfully decrypt the message. In parallel with the processing of the message, a digital signature is processed and verified.
Single-key cryptographic system . The required, necessary session attributes are the user ID, the access password and, most importantly, the encryption key. In the classical traditional cryptographic system (CGS), the sender and receiver both use the same key for encryption and decryption. For this reason, such encryption systems are called single-key ( symmetric ). It is clear that both parties must have the key before the communication session, i.e. the key must be developed, distributed (which pair of keys to whom) and distributed (delivered) to subscribers. This is a key management task. For its successful solution requires a secure (dedicated) channel key distribution. Often the key was delivered by a special diplomat. The name of one of them, Theodore Netta, is widely known and entered into literature and history.
Two-key cryptographic system. In 1978, a publication appeared on a new type of CHS - a two-key system. They also call it an asymmetric , system with open doors. The sender and recipient of the message use different keys. Using a public key it is computationally very difficult to find a private key. In this system, each subscriber independently generates his own key pair: the public key available to all senders, which all subscribers must use to create the encryption message, and the recipient's private private key d , which the recipient keeps secret from everyone, does not disclose it.
In such systems, there is no need to distribute keys, which, of course, simplifies the new technology of secure communication. But nothing is given for nothing. The two-key systems have their drawbacks. Encryption in them is quite a slow process. The emergence of such two-key systems became possible due to the introduction into the circulation of information security of a new mathematical object — a one - way function and, in a set of such functions, functions with a secret entrance (with a loophole). The point here is this. We can easily multiply a pair of numbers p and q and get one number N = pq. The calculations here are directed in one direction. Now let's say a composite number N is given and it is necessary to define its divisors. This problem for large numbers (10 150 -10 300 ) is currently practically not solved, if there is no loophole (secret door). Such a loophole could be, for example, one of the dividers or the value of the Euler function from N.
In a two-key public-secretary public address system, the recipient of the messages, which establishes the PSC, such a divisor knows he has a loophole.
Electronic digital signature (EDS) . Digital signatures also use two keys: the signature key is private (not disclosed) and the public (public) signature verification key.
The sender encrypts his message in the recipient’s public key, and signs the encryption message with his private key. The public key of the sender's signature is available to everyone and the recipient, using it and verifying the digital signature, makes sure that the message is sent and signed by this sender.
Processes in CGS . The main processes of secure information exchange are described in encryption standards and digital signatures GOST 28147 - 89 - for encryption and GOST 34.10 - 2012 - for digital signatures.
With secure information exchange of subscribers, the following basic processes are implemented. Setting CGS, generating 4 keys (2 for encryption and 2 for digital signature of the recipient), generating a message, encrypting a message, signing, encoding, sending by the sender, environmental impact and / or intruder, receiving a message, decoding, decrypting, verifying a digital signature, converting in a form convenient for perception by the recipient. We give a brief description of the processes.
Installation of CGS. Recipient A selects two large primes p A and q A , multiplies them and gets the cipher module N A , and also calculates the value of the Euler function F (N A ). After that, it selects the public key eA such that (eA, Φ (NA)) = 1, and calculates, using the Euclidean extended god algorithm, the private key dA, such that eA dA ≡1 (mod F ( N A )).
Values (e A and N A ) and the recipient's nickname are declared on the network server open and accessible to all who will send their messages to the recipient A. The values of d A , p A , F (N A ), and q A are kept secret from all . Access of the intruder to any of these values leads to cracking of the CHS.
Possible attack on the cipher message. Suppose the infringer knows F (N A ), and e A d A - 1 is divided by F (N A ). Knowledge of F (N A ) provides the calculation of p A and q A , since
Sender B converts the generated message into a numerical form (binary form) and breaks it into blocks of length [log2N A ] = m Bi - blocks of the source text. After that, the remains of m Bi e A (modN A ) = Bi are the cipher message blocks, and then sent to recipient A.
The recipient, having encrypted message blocks, decrypts them using the private key, i.e. finds residues of Bi d A (modN A ) = m Bi .
Mathematical problems of information security
Object modeling (networks of local, corporate, global, subscriber groups), processes of receiving / transmitting protected messages, information exchange and interaction is a vast area with its own tasks and problems of various nature for applications of algorithms for studying and improving information security.
The problems of protecting information exchange and information technology are also reflected in mathematical theories, for example, in number theory. The central problem of the present time is the problem of the expansion of large numbers into factors. In cryptology, it is associated with the tasks of cryptography, the selection of key information, and in cryptanalysis - with attacks on two-key CGS.
Such attacks are considered both by the violators and by their cryptanalyst analysts. The purpose of the latter is to identify the weak points of the algorithms and crypto protocols. Detected vulnerabilities are eliminated by improving products, or if it is impossible to eliminate them, they move to new, more sophisticated and modern means.
Another important problem is to obtain prime numbers of high resolution and in mass quantities. In computer networks and communication networks, the exchange of secure messages requires from the key management systems the mass production of prime numbers, which are selected from the full set at random. Earlier it was said that each subscriber of the network generates for himself at least 4 keys, which he must update at regular intervals. This means that the need for primes exists all the time, as the number of users is only increasing. Today almost every inhabitant of developed countries and the majority of people in developing countries have mobile phones. Cellular communication systems cover all large areas and the stopping of this process is not expected in the near future.
Closely to the named problem is adjacent the problem of establishing the simplicity of a number of large bit depth.
The problem of discrete logarithm. Diffie-Hellman key provisioning protocol (DHDLP, 1976). Subscribers A and B choose the prime number p and the prime g with the order p -1 modulo p, i.e. g p-1 ≡1 (mod p), but g n ≠ 1 (mod p), for any n <p -1. Subscribers A and B choose prime numbers n <p and m <p, respectively. Then the residuals g n (mod p), g m (mod p) are calculated and each of the subscribers sends the result of their calculations to the other. Then both calculate the values of
The intruder can intercept and have the values of g n (mod p), g m (mod p), but using them to quickly obtain n and m or k ≡ g nm (mod p) is not enough.
A similar problem of the discrete logarithm exists for elliptic curves (EC) over finite fields (ECDLP, 1985 N.N. Koblitz, V. Miller). On the EC E (Fp) there is an Abelian group formed by the points of this curve. This group is cyclic and of very large order. In other words, for given two points, EC E (Fp) over the field Fp, points P, Q∈E (Fp) need to find a number λ (if it exists) such that Q = [λ] P.
Source: https://habr.com/ru/post/229717/
All Articles