July 14, 2014 at 08:56Some mathematical problems of information security
Along with political, socio-economic, organizational, military, legal, special and information problems, the solution of which is provided for at the state and federal levels, there are mathematical problems in the information sphere that will be discussed in the work. The paper gives and concretizes some important concepts and basic provisions of information security and information protection. The main regulatory documents in this area are the Constitution of the Russian Federation - the basic law, the Federal Law on Security, the 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 a state of protection of its national interests in the information sphere. Information sphere - a set of information infrastructure of the country, information, entities involved in the collection, generation, distribution and use of information, as well as the regulatory system for the resulting public relations. The information sphere is a system-forming factor in the life of society, part of the social activity of society.
The aim of this work is the author’s desire to draw readers' attention to the primary mathematical problems in the field of information security and information protection, without which progress cannot be expected in the coming years (perhaps decades).
Description of the situation of information interaction (impact)
We consider a group of user subscribers Г = {u1, u2, ..., un}, located in different nodes of a communication network or a computer network, which exchange messages transmitted over insecure network channels. It is understood that messages may contain information that is not intended for a wide audience. The subscribers of the communication system would like to have access and contact with each other as the need arises in it, maintaining the confidentiality of their messages, ensuring that the message received on the receiving side is completely the same as that prepared and sent by the transmitting side, i.e. maintaining integrity. In addition to the aforementioned requirements, both communicating subscribers would not want to become participants in the “grandmaster attack”. They would like to know with a high level of certainty that they are communicating with each other, and not with dummies, be able to implement mutual authentication - establishing the authenticity of the sender by the recipient and vice versa. When fulfilling the above requirements for communication system services, the quality of message reception / transmission must be as stated.
Thus, reliability, integrity, confidentiality, accessibility should be ensured for 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 fairly complex algorithms, programs developed in the framework of theories of telecommunications, coding and cryptology.
In this paper, we consider the basic concepts and provisions of cryptology, which are 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, establishing the authenticity of subscribers and checking 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 (CGS), encrypting messages, the second - using an electronic digital signature (EDS), and the third task - establishing a match digests transmitted and generated by the recipient. The task of ensuring integrity is solved by the methods of code theory, coding / decoding of messages by error-correcting codes, correcting codes. Accessibility has been said before.
The general diagram 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 a communication session of subscribers using a single-key symmetric CGS, a key management system and a coding system
Secure information messaging technology
Information exchange technology includes subjects, objects, resources and processes. The subjects are the recipient and sender of the message, resources (financial, network, computing, temporary), objects: the message source that forms the message, the message itself, keys generated by the key system, encryption / decryption, encoding / decoding device, display or printer, there is a device for displaying a message in a form accessible to all subjects by recipients and senders.
The message processing sequence should be as shown in Fig. 1. This is due to the fact that in the presence / absence of distortions of the cipher message, its decryption in the first error situation is impossible. Therefore, on the recipient side of the message, you must first establish the presence of errors in the message and make corrections if there are errors. Only after eliminating the errors is it possible to successfully decrypt the message. In parallel with message processing, a digital signature is processed and verified.
Single Key Cryptographic System. Mandatory, necessary attributes of the communication session are the user ID, access password and, most importantly, the encryption key. In the classic 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 key pair to whom) and distributed (delivered) to subscribers. This is a key management task. For its successful solution, a secure (dedicated) key distribution channel is required. Often the key was delivered by a special diplomatic courier. The name of one of them, Theodore Nette, is widely known and has gone down in literature and history.
Two-key cryptographic system. In 1978, a publication appeared about a new type of CGS - a two-key system. It is also called an asymmetric , open-door system. The sender and receiver of the message use different keys. With a public key, it is computationally difficult to find a private key. In this system, each subscriber independently generates his own key pair: the public key e available to all senders , which all subscribers must use to create a cipher 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. Two-key systems have their drawbacks. Encryption in them is a rather slow process. The emergence of such two-key systems became possible due to the introduction of a new mathematical object into the information security circuit — a one - way function and, in many of these functions — functions with a secret input (with a loophole). Here is the point. 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 suppose a composite number N is given and it is necessary to determine its divisors. This task for large numbers (10 150 -10 300) at the present time it is practically not solved if there is no loophole (secret door). Such a loophole may be, for example, one of the divisors or the value of the Euler function of N.
In a two-key public-private key public service, the recipient of the message that sets the public key public key knows such a divider, i.e. he has a loophole.
Electronic Digital Signature (EDS) . In digital signatures, two keys are also used: the signature key is a private (non-public) key and the public (public) signature verification key.
The sender encrypts his message on the recipient's public key, and signs the cipher message with his private key. The public key of the sender's signature is accessible 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 the CGS . The main processes of secure information exchange are described in the encryption and digital signature standards GOST 28147 - 89 - for encryption and GOST 34.10 - 2012 - for digital signature.
With a secure information exchange of subscribers by messages, the following basic processes are implemented. CGS installation, generation of 4 keys (2 for encryption and 2 for digital signature of the recipient), message generation, message encryption, signing, encoding, sender transmission, environmental and / or intruder impact, message reception, decoding, decryption, digital signature verification, conversion convenient for perception by the recipient. We give a brief description of the processes.
CGS installation. Recipient A chooses 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, he selects a public key e A such that (e A , Φ (N A )) = 1, and calculates, using the extended Euclidean GCD algorithm, a private key d A such that e A d A ≡1 (mod Ф ( N A )).
The values (e A and N A ) and the nickname of the recipient are declared open and accessible on the network server for anyone who will send their messages to recipient A. The values d A , p A , F (N A ), and q Akept secret from everyone. An intruder’s access to any of these values leads to hacking.
Possible attack on the cipher message. Suppose the violator 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 of the function F Euler multiples (N A ) is also sufficient for the calculation of p A and q A .
The 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 residues m Bi e A (modN A ) = Bi are the cipher message blocks, and then they are sent to the recipient A. The
recipient, having encrypted message blocks, decrypts them using a private key, i.e. finds residues at Bi d A (modN A) = m Bi .
Mathematical problems of information security
Modeling of objects (networks of local, corporate, global, subscriber groups), processes for receiving / transmitting secure messages, information exchange and interaction is a vast area with its tasks and problems of various kinds for applications of algorithms for studying and improving information security.
The problems of protecting information exchange and information technology are reflected in mathematical theories, for example, in number theory. The central problem of the present is the factorization of large numbers.In cryptology, the tasks of cryptography, the selection of key information are associated with it, and in cryptanalysis, with attacks on two-key CGSs.
Such attacks are considered both from the side of intruders and from the side of cryptanalysts on their side. The purpose of the latter is to identify weaknesses in algorithms and crypto protocols. Discovered vulnerabilities are eliminated by improving the products, or if it is impossible to eliminate them, they switch to new, more advanced and modern tools.
Another important problem is to obtain prime numbers of high capacity and in massive quantities.In computer and communication networks, the exchange of secure messages requires key management systems for mass production of primes, which are randomly selected from the complete set. Earlier it was said that each subscriber of the network forms for himself at least 4 keys, which he must update at certain intervals. This means that the need for prime numbers is constant, as the number of users is only increasing. Almost every resident of developed countries and most of the inhabitants of developing countries have mobile phones today. Cellular communication systems cover more and more territories and stops of this process are not expected in the near future.
Closely related to the aforementioned problem is the problem of establishing the simplicity of a numberlarge capacity.
The discrete logarithm problem. The Diffie-Hellman Keying Protocol (DHDLP, 1976). Subscribers A and B choose a prime number p and a prime g with order p -1 modulo p, i.e. g p-1 ≡1 (mod p), but g n ≠ 1 (mod p), for any n
Information security of the state is a state of protection of its national interests in the information sphere. Information sphere - a set of information infrastructure of the country, information, entities involved in the collection, generation, distribution and use of information, as well as the regulatory system for the resulting public relations. The information sphere is a system-forming factor in the life of society, part of the social activity of society.
The aim of this work is the author’s desire to draw readers' attention to the primary mathematical problems in the field of information security and information protection, without which progress cannot be expected in the coming years (perhaps decades).
Description of the situation of information interaction (impact)
We consider a group of user subscribers Г = {u1, u2, ..., un}, located in different nodes of a communication network or a computer network, which exchange messages transmitted over insecure network channels. It is understood that messages may contain information that is not intended for a wide audience. The subscribers of the communication system would like to have access and contact with each other as the need arises in it, maintaining the confidentiality of their messages, ensuring that the message received on the receiving side is completely the same as that prepared and sent by the transmitting side, i.e. maintaining integrity. In addition to the aforementioned requirements, both communicating subscribers would not want to become participants in the “grandmaster attack”. They would like to know with a high level of certainty that they are communicating with each other, and not with dummies, be able to implement mutual authentication - establishing the authenticity of the sender by the recipient and vice versa. When fulfilling the above requirements for communication system services, the quality of message reception / transmission must be as stated.
Thus, reliability, integrity, confidentiality, accessibility should be ensured for 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 fairly complex algorithms, programs developed in the framework of theories of telecommunications, coding and cryptology.
In this paper, we consider the basic concepts and provisions of cryptology, which are 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, establishing the authenticity of subscribers and checking 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 (CGS), encrypting messages, the second - using an electronic digital signature (EDS), and the third task - establishing a match digests transmitted and generated by the recipient. The task of ensuring integrity is solved by the methods of code theory, coding / decoding of messages by error-correcting codes, correcting codes. Accessibility has been said before.
The general diagram 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 a communication session of subscribers using a single-key symmetric CGS, a key management system and a coding system
Secure information messaging technology
Information exchange technology includes subjects, objects, resources and processes. The subjects are the recipient and sender of the message, resources (financial, network, computing, temporary), objects: the message source that forms the message, the message itself, keys generated by the key system, encryption / decryption, encoding / decoding device, display or printer, there is a device for displaying a message in a form accessible to all subjects by recipients and senders.
The message processing sequence should be as shown in Fig. 1. This is due to the fact that in the presence / absence of distortions of the cipher message, its decryption in the first error situation is impossible. Therefore, on the recipient side of the message, you must first establish the presence of errors in the message and make corrections if there are errors. Only after eliminating the errors is it possible to successfully decrypt the message. In parallel with message processing, a digital signature is processed and verified.
Single Key Cryptographic System. Mandatory, necessary attributes of the communication session are the user ID, access password and, most importantly, the encryption key. In the classic 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 key pair to whom) and distributed (delivered) to subscribers. This is a key management task. For its successful solution, a secure (dedicated) key distribution channel is required. Often the key was delivered by a special diplomatic courier. The name of one of them, Theodore Nette, is widely known and has gone down in literature and history.
Two-key cryptographic system. In 1978, a publication appeared about a new type of CGS - a two-key system. It is also called an asymmetric , open-door system. The sender and receiver of the message use different keys. With a public key, it is computationally difficult to find a private key. In this system, each subscriber independently generates his own key pair: the public key e available to all senders , which all subscribers must use to create a cipher 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. Two-key systems have their drawbacks. Encryption in them is a rather slow process. The emergence of such two-key systems became possible due to the introduction of a new mathematical object into the information security circuit — a one - way function and, in many of these functions — functions with a secret input (with a loophole). Here is the point. 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 suppose a composite number N is given and it is necessary to determine its divisors. This task for large numbers (10 150 -10 300) at the present time it is practically not solved if there is no loophole (secret door). Such a loophole may be, for example, one of the divisors or the value of the Euler function of N.
In a two-key public-private key public service, the recipient of the message that sets the public key public key knows such a divider, i.e. he has a loophole.
Electronic Digital Signature (EDS) . In digital signatures, two keys are also used: the signature key is a private (non-public) key and the public (public) signature verification key.
The sender encrypts his message on the recipient's public key, and signs the cipher message with his private key. The public key of the sender's signature is accessible 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 the CGS . The main processes of secure information exchange are described in the encryption and digital signature standards GOST 28147 - 89 - for encryption and GOST 34.10 - 2012 - for digital signature.
With a secure information exchange of subscribers by messages, the following basic processes are implemented. CGS installation, generation of 4 keys (2 for encryption and 2 for digital signature of the recipient), message generation, message encryption, signing, encoding, sender transmission, environmental and / or intruder impact, message reception, decoding, decryption, digital signature verification, conversion convenient for perception by the recipient. We give a brief description of the processes.
CGS installation. Recipient A chooses 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, he selects a public key e A such that (e A , Φ (N A )) = 1, and calculates, using the extended Euclidean GCD algorithm, a private key d A such that e A d A ≡1 (mod Ф ( N A )).
The values (e A and N A ) and the nickname of the recipient are declared open and accessible on the network server for anyone who will send their messages to recipient A. The values d A , p A , F (N A ), and q Akept secret from everyone. An intruder’s access to any of these values leads to hacking.
Possible attack on the cipher message. Suppose the violator 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
The 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 residues m Bi e A (modN A ) = Bi are the cipher message blocks, and then they are sent to the recipient A. The
recipient, having encrypted message blocks, decrypts them using a private key, i.e. finds residues at Bi d A (modN A) = m Bi .
Mathematical problems of information security
Modeling of objects (networks of local, corporate, global, subscriber groups), processes for receiving / transmitting secure messages, information exchange and interaction is a vast area with its tasks and problems of various kinds for applications of algorithms for studying and improving information security.
The problems of protecting information exchange and information technology are reflected in mathematical theories, for example, in number theory. The central problem of the present is the factorization of large numbers.In cryptology, the tasks of cryptography, the selection of key information are associated with it, and in cryptanalysis, with attacks on two-key CGSs.
Such attacks are considered both from the side of intruders and from the side of cryptanalysts on their side. The purpose of the latter is to identify weaknesses in algorithms and crypto protocols. Discovered vulnerabilities are eliminated by improving the products, or if it is impossible to eliminate them, they switch to new, more advanced and modern tools.
Another important problem is to obtain prime numbers of high capacity and in massive quantities.In computer and communication networks, the exchange of secure messages requires key management systems for mass production of primes, which are randomly selected from the complete set. Earlier it was said that each subscriber of the network forms for himself at least 4 keys, which he must update at certain intervals. This means that the need for prime numbers is constant, as the number of users is only increasing. Almost every resident of developed countries and most of the inhabitants of developing countries have mobile phones today. Cellular communication systems cover more and more territories and stops of this process are not expected in the near future.
Closely related to the aforementioned problem is the problem of establishing the simplicity of a numberlarge capacity.
The discrete logarithm problem. The Diffie-Hellman Keying Protocol (DHDLP, 1976). Subscribers A and B choose a prime number p and a prime g with order p -1 modulo p, i.e. g p-1 ≡1 (mod p), but g n ≠ 1 (mod p), for any n
n (mod p), g m (mod p) and each of the subscribers sends the result of their calculations to the other. Next, both calculate the values of
The intruder can intercept and dispose of the values 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.
Similarthe discrete logarithm problem also exists for elliptic curves (EC) over finite fields (ECDLP, 1985 N. Koblitz, W. Miller). An abelian group formed by points of this curve appears on EC E (Fp). This group is cyclic and very large. In other words, given two points of EC E (Fp) over the field Fp, points P, Q∈E (Fp), it is required to find a number λ (if it exists) such that Q = [λ] P.