Abstract: This paper briefly introduces the ideological and characteristics of the public key cryptosystem, and specifically introduces the theoretical foundation, working principle and specific implementation of the RSA algorithm, and how the algorithm is implemented. At the end of this article, some of the shortcomings and solutions of the RSA algorithm are summarized. Keywords: public key cryptosystem, public key, private key, RSA map Category: TP309.7 §1 Introduction With the gradual implementation of computer networking, Internet prospects are getting better and better, and the global economic development is entering the information economy era. The knowledge economy is beginning to see Ni. The confidentiality of computer information is more important, whether it is personal information communication or e-commerce development, is urgently needed to ensure the security of the Internet online information, need to guarantee information security. Information security technology is a comprehensive discipline. It involves information on informationism, computer science and cryptology. Its main task is to study the protection methods of information within the computer system and communication network to realize the security, confidentiality, and true realization of information within the system. And complete. Among them, the core of information security is a password technology. Password technology is a cross-discipline that integrates many disciplines such as mathematics, computer science, electronics and communications. It not only guarantees encryption of confidential information, but also enables digital signature, authentication, system security. It is one of the important sciences of modernization. This article will make some brief introduction to the public key cryptographic system and the current most popular RSA algorithm in the system. §2 Public key cryptographic system To illustrate public key cryptographic systems, first understand different encryption algorithms: current encryption algorithm can be divided into single key cryptographic algorithm and public key cryptographic algorithm. 2.1. The key password is also known as the symmetric password, is a comparison of conventional encryption methods, its encryption operation, the decryption operation is used by the same key, the transmitter and information of the sender and information of the information are transmitted and processing information. When it is necessary to hold this password (called symmetrical password). Therefore, both communications must get this key and keep the key secret. The security of the single key cryptographic system relies on the following two factors: First, the encryption algorithm must be strong enough, only based on the secret text, the decryption information is impossible; second, the security of the encryption method The secretability of the key, not the secretability of the algorithm, so we don't have to ensure the secret of the algorithm (in fact, many of the algorithms used in reality are public), but we must guarantee Secretability of the key. These features from the single key password We are easy to see that there are two main problems: first, key quantity problem. In a single key cryptograph, each pair of communicators need a pair of keys. When the user increases, it will inevitably bring the key amount, and therefore, in network communication, a large number of keys, store, and Allocation will be a problem that is difficult to solve. Second, the key distribution problem. In the single key password system, the encryption security is completely dependent on the protection of the key, but because the communication between the communication is the same key, people have to communicate the key, so in order to ensure safety, people must use some additional additional Safety channels to distribute the key, such as using a special messenger to transmit the key, the price of this approach is quite large, and it can be said to be very unrealistic, especially in computer network environments, people use network transfer encryption. Document, but there is a need for additional safety channel to distribute the key, which is obvious, which is very unhappy or even ridiculous. 2.2 Public key passwords For the disadvantage of this difficulty, it is more urgent and necessary to develop a new, more effective, and more advanced cryptographic system.
In this case, there is a new public key cryptographic system, which breaks through the key distribution problem that plagues countless scientists, in fact, people do not even distribute strict confidentiality in this system. The key, this breakthrough is also considered to be the greatest achievement of the password for two thousand years in the history of the code. This new idea is made in this century, two scholars and hellman of Stanford University, USA, the biggest difference between the system and the single key password is: in the public key cryptode system, encryption and decryption use of different Key (relative to the symmetric key, people calling a non-symmetric key), there is a mutual dependency between the two keys: that is, the information used in these key encryption can only be performed with another key. Decrypt. This allows both communication between communication without the need for a prior exchange key. Where the encryption key and algorithm are public, everyone can encrypt the file through this key and then send it to the recipient. This encryption key is also called a public key; after the recipient receives the encrypted file, it can use him. The decryption key is decrypted. This key is by his own private palm, and it does not need to be distributed, so it is called private key, which solves the problem of key distribution. To illustrate this idea, we can consider the following ratios: two people communicating in unsupport channels, assume that Alice and Bob (sender), they want to be able to communicate safely without being attached to their enemy Oscar destroyed. Alice thought of it, she used a lock (equivalent to the public key), which can be locked if anyone can lock, but only the Alice key (equivalent to private key) can be opened. Then Alice has sent countless ways such locks. When anyone wants to give her a letter, if you want to give her a letter, then use a Alice lock to send it to Alice, then anyone (including bob) I can't open the box in addition to the Alice with the key, so that even if Oscar can find Alice lock, even if oscar can intercept this box during communication, there is no alice, but he is not possible to open the box, and Alice's key and No need to distribute, so OSCAR will not get this "private key". As can be seen from the above, it can be seen that the idea of public key cryptosystem is not complicated, and the key issue to achieve it is how to determine the public key and private key and add / decryption algorithm, that is, how to find "Alice locks and keys. "The problem. We assume that in this system, the PK is an open information, used as an encryption key, and SK needs to be kept by the user himself and used as a decryption key. The encryption algorithm E and the decision algorithm D are also disclosed. Although SK and PK are paired, SK cannot be calculated according to PK. They must meet the conditions: 1 Encryption key PK After the clear text X is encrypted, the decryption key SK can be decrypted to restore clear text, or write as: DSK (EPK (X)) = X 2 Encryption key cannot be used Decryption, ie DPK (EPK (X)) ≠ x 3 can easily generate pairs of PK and SK on your computer. 4 From known PKs that cannot be derived from SK. 5 Encryption and decryption operations can be treated, ie: EPK (DSK (x)) = X can be seen from the above conditions, under the public key cryptographic system, the encryption key is not equal to the decryption key.
The encryption key may be disclosed to the outside, allowing any user to transmit information transmitted to this user with a public key encrypted, and the user's uniquely saved private key is confidential, and only it can restore, decrypt secret. Although the decryption key can be calculated by the encryption key, this algorithm is actually impossible, or although it is possible to calculate, it is not feasible to spend a long time. So publicize the encryption key and will not harm the key. This system is simple, however, how to find a suitable algorithm to achieve this system is a problem that really plasmunication passwords, because since PK and SK are a pair of mutual relationship, then One of the other is that it is very possible. If the enemy OSCar can derive SK from the PK, then this system is no longer safe. So how to find a suitable algorithm to generate suitable PK and SK, and make it impossible to derive SK from PK, it is urgently needed to solve the problem for cryptology. This problem even makes the development of public key cryptosystems have been stagnant for a long time. In order to solve this problem, cryptographers consider mathematically traveled one-way functions. Here we can give its informal definition: Alice's public encryption function should be easily calculated, calculate its inverse function (ie The decryption function) should be difficult (for those other than Alice). Many forms of forms Y = f (x), for a given self-variable X value, it is easy to calculate the value of the function y; and by a given Y value, in many cases, in many cases calculated according to function relationship f (x) X value is very difficult. This is easy to calculate but it is difficult to reverse the function, commonly referred to as a one-way function. In the encryption process, we hope that the encryption function E is a single single shot function so that you can decrypt. Although there is currently no function that can prove to be unidirectional, there are many single-shot functions that are considered one-way. For example, if the following function is considered one-way, assuming N is two large numbers P and Q product, B is a positive integer, then definition f: f (x) = xb mod N (if GCD (B, φ (n)) = 1, then in fact this is the RSA encryption function we need to say) If we want to construct a public key cryptographic system, only one unidirectional single swing function is not enough. From Alice's point of view, it is not necessary to be one-way because it needs to decrypt the information received in a valid manner. Therefore, Alice should have a trap, which contains secret information that is easy to find E. That is, Alice can effectively decrypt because it has additional secret knowledge, name SK, can provide you decrypt D. D. Therefore, we call a function as a unidirectional function, if it is a one-way function, and it is easy to find out after a certain knowledge of a particular trap. Consider the above function f (x) = xb mod n. We can know that its inverse function F -1 has similar forms F (x) = Xa MOD N, for suitable value a. The trap is the factor decomposition using N, which is effective to calculate the correct index a (for a given B). For convenience, we count the specific one-way function of a particular class. So randomly selected a function F belonging? As an open encryption function; its inverse function F -1 is a secret decryption function. Then the public key cryptographic system can be implemented. According to the above ideas regarding the unidirectional function, scholars put forward many methods of public key encryption, and their security is based on complex mathematical problems.
Depending on the mathematical problem based, at least the following three types of systems are currently considered to be safe and effective: large integer factor decomposition systems (representative RSAs), elliptical curves discrete logarithmic system (ECC) and discrete logarithmic systems (Representative DSA). §3 RSA Algorithm 3.1 Introduction The current most famous, the most widely used public key system RSA is in 1978, the Rivest, Shamir and Adleman, the US MIT (MIT) in the United States, gain digital signature and public key cryptosystem The method of the method "is proposed. It is a non-symmetrical (public key) cryptographic system based on the ratio, is a packet password system. Its name is from the three inventors. Its security is based on the difficulty of generic factor decomposition, and the problem of large integer factor decomposition is a mathematical difficult problem. So far, there is no effective way to solve it, so it can ensure the security of the RSA algorithm. The RSA system is the most typical method of the public key system, and most of the products and standards that use public key passwords encrypt and digital signatures are RSA algorithms. The RSA algorithm is the first algorithm that can be used for data encryption and digital signatures, so it provides a basic method for encryption and authentication of information on public networks. It is usually a pair of RSA keys, one of which is the confidential key, saved by the user; the other is the public key, open to the outside, can even register in the network server, people send it to individuals with public key encryption files Individuals can decrypt accept with private key. In order to improve the confidentiality strength, the RSA key is at least 500 seats, which is generally recommended for 1024 bits. This algorithm is based on the following two facts guarantees the security and effectiveness of the RSA algorithm: 1) It has been determined that the number of rapid algorithms are not the rigidity; 2) The rapid algorithm of the determination of the quality of the test is not found. 3.2 Working Principle 1) Two different large numbers P and q, calculate the product R = P * q; 2) An arbitrary selects a large integer E, E and (P-1) * (Q-1) mutual, Integer E makes an encryption key. Note: The selection of E is easy, for example, all the prime numbers greater than p and q are available. 3) Determine the decryption key D: D * E = 1 modulo (p - 1) * (Q - 1) According to E, P and Q can be easily calculated to calculate D. 4) Open integer R and E, but not disclosed D; 5) Encrypt the express text P (assuming the integer of P is an integer of a smaller than R) into ciphertext C, the calculation method is: c = pe modulo R 6) Red Decrypt Cipheet C For the express text p, the calculation method is: p = CD MODULO R However, it is not possible to calculate that D is calculated according to R and E (not p and q). Therefore, anyone can encrypt the plaintext, but only the authorized user (know D) can only decrypt the ciphertext. 3.3 Simple Example To illustrate the work of the algorithm, we will give a simple example below, apparent that we can only take a small number, but as mentioned above, in order to ensure safety, the number we use in actual application is large. More more. Example: P = 3, q = 5, then R = 15, (P-1) * (Q-1) = 8. Select E = 11 (greater than P and Q), calculate D = 3 by D * 11 = 1 modulo 8. It is assumed that it is an integer 13.
Then Cipen C is c = pe modulo r = 1311 modulo 15 = 1, 792, 160, 394, 037 modulo 15 = 7 restoration plain text P is: p = cd modulo r = 73 modulo 15 = 343 modulo 15 = 13 Because E and D mutual reverse, public key The encryption method also allows the encryption information to "sign" in such a manner to determine whether the signature is not forged. Suppose A and B want to perform data transmission, A and B, respectively, and the corresponding key is disclosed, but the decryption algorithm and the corresponding key are not disclosed. The encryption algorithms of A and B are ECA and ECB, respectively, and the decomposition algorithms are DCA and DCB, ECA, and DCA mutual reverse, ECB, and DCB. If A is sent to B, it is not simply transmitting ECB (P), but the decryption algorithm DCA is first applied to P, and then encrypt the result encrypt the result encryption. Ciphertext C is: c = ECB (DCA (P)) B receives C, it has been applied to its decryption algorithm DCB and encryption algorithm ECA, obtaining a clear text P: ECA (DCB (C)) = ECA (DCB (ECB (ECB (ECB DCA (P))))) = ECA (DCA (P)) / * DCB and ECB mutual offset * / = p / * DCB and ECB mutual offset * / like this B, determine that the message is indeed issued from A, because only When the encryption process utilizes the DCA algorithm, use ECA to get P, only A can only know the DCA algorithm, no one, even B can not fake A signs. 3.4 Advantages and Disadvantages 3.4.1 Advantages The RSA Algorithm is the first algorithm that can be used for encryption and digital signatures, and is easy to understand and operate. RSA is the most widely studied public key algorithm. From now on, it has been in the past two decades. It has experienced various attacks, and gradually accepts people, and is generally one of the best public key schemes. The encryption key and encryption algorithm of the algorithm are separated, making the key allocation easier. It is especially compliant with a computer network environment. For a large number of users on the Internet, the encryption key can be printed by phone book. If a user wants to communicate with another user, simply use the other party's encryption key from the public key to use it to encrypt the transmitted information. After the other party receives the information, the information is detached with only the decryption key known to know, understand the contents of the message. It can be seen that the RSA algorithm solves the problem of a large number of network user key management, which is the most prominent advantage of the public key cryptographic system relative to the symmetric cryptographic system. 3.4.2 Disadvantages 1) It is very troublesome to generate a key, which is limited to the number of techniques, so it is difficult to achieve one secret. 2) Safety, the security of RSA depends on the factor decomposition of the large number, but has no in theory to deal with the difficulty of deciphering RSA and the equivalent of the large number of decomposition, and most people in the cryptography are not NPC issues. At present, people have decomposed more than 140 decimal places, which requires a longer key, slower speed; in addition, people are actively looking for methods of attacking RSA, such as choosing secret attack, general attackers It is a message to make a message to sign the entity with the private key. Then, the information it wants can be obtained after calculation.
In fact, the attack is the same weakness, that is, there is a fact that the power retains the input multiplication structure: (XM) D = XD * MD MOD N has been mentioned, this inherent problem comes from the public key The most useful feature of the cryptographic system - everyone can use the public key. However, from the algorithm to solve this problem, there are two main measures: one is a good public key protocol to ensure that the entity does not decrypt the information generated by other entities during the work, and is not known for the information you know nothing. One is never sent to the random document signature sent by the stranger, first use One-Way Hash Function for the document as a Hash process, or simultaneously using different signature algorithms. In addition to utilizing public analog numbers, people also try some attacks using decryption index or φ (n), etc. 3) The speed is too slow, because the packet length of RSA is too large, to ensure safety, n at least 600 bitx or more, The calculation is very high, especially slower, more symmetrical cryptographic algorithms slowly, and with the development of large decomposition techniques, this length is also increasing, not conducive to standardization of data format. Currently, CAs are required in the SET (Secure Electronic Transaction) protocol to use a 2048-bit key, and other entities use 1024 bits of keys. For speed problems, people are currently widely used, and the public key password is used. The advantages and disadvantages are complementary: the single key password is fast, people use it to encrypt longer files, and then use RSA to encrypt the file key, extreme Good solution to the key distribution problem of the single key password. §4 Conclusion Currently, increasing e-commerce and other Internet applications make public key systems, mainly including access control of server resources and protection of e-commerce transactions, and rights protection, personal privacy, wireless transactions And content integrity (such as ensuring the authenticity of news reports or stock market). Public key technology has developed to today, in the market, the development trend is the integration of PKI and operating system, and PKI is an abbreviation of "public key infrastructure", meaning "public key infrastructure". The public key system is widely used in the fields of CA certification, digital signature and key exchange. The most widely used in public key plus algorithms is RSA. The initial philosophy and goal development of the RSA algorithm is to make the Internet safe and reliable, intended to solve the problem of utilizing public channel transmission distribution using the DES algorithm secret key. The actual results not only solve this problem well; also use RSA to complete the digital signature of the electronic text to resist the denial of the IC, and you can use the digital signature to find the attacker to the illegal tampering of the attacker. To protect the integrity of data information. So far, many encryption technologies have used RSA algorithms that have also been widely used in many ways of the Internet, including the security interface layer (SSL) standard (this standard must be used when the web browser establishes a secure Internet connection. Application. In addition, the RSA encryption system can also be applied to intelligent IC cards and network security products. However, the patent period of the RSA algorithm is about to end, and it is replaced by a cryptographic scheme based on an elliptic curve (ECC algorithm). Compared with the RSA algorithm, ECC has a relatively advantage, which makes the characteristics of ECC more suitable for the development trend of rapid response of today's e-commerce. In addition, a new quantum password is also in development. As for what encryption algorithm in practical applications should be used in conjunction with specific application environments and systems, it is not possible to make judgments according to their encryption strength. Because in addition to the encryption algorithm itself, the key is reasonable, and the combination of encryption efficiency and existing system and the input-output analysis should be considered in the actual environment. Encryption technology With the development of the network, there will be more secure and easier to implement algorithms, providing more powerful guarantees for information security. In the future, how will encryption technology go, we will wait and see.
