Public Key Cryptosystem and RSA Public Key Algorithm

Public Key Cryptosystem and RSA Public Key Algorithm

This paper briefly introduces the ideas and characteristics of public key cryptosystems, and specifies the theoretical basis of the RSA algorithm, the working principle and the specific implementation process, and illustrates how the algorithm is realized through a simple example. At the end of this paper, summarizes the RSA algorithm currently exists some shortcomings and solutions.

Keywords: public key cryptosystem , public key , private key , RSA

§1 Introduction

With the gradual realization of computer networking, the Internet prospect is getting better and better, the global economic development is entering the era of information economy, the knowledge economy is beginning to see the beginning of. The confidentiality of computer information is becoming more and more important, whether personal information communication or e-commerce development, there is an urgent need to ensure the security of information transmission on the Internet online, the need to ensure information security. Information security technology is a comprehensive discipline, which involves information theory, computer science and cryptography and other aspects of knowledge, its main task is to study the computer system and communication networks within the protection of information to achieve the security of the information within the system, confidentiality, truth and integrity. Among them, the core of information security is cryptography. Cryptography is a cross-discipline combining mathematics, computer science, electronics and communications and many other disciplines. It can not only ensure the encryption of confidential information, but also realize the functions of digital signature, identity authentication, system security and so on. It is one of the important sciences for modernization and development. In this paper, we will make some brief introduction to the public key cryptosystem and the most widely popular RSA algorithm in this system.

§2 Public key cryptosystem

To explain the public key cryptosystem, first of all to understand the different encryption algorithms: the current encryption algorithms can be divided into single-key cryptographic algorithms and public-key cryptographic algorithms according to the key method.

2.1. Single-key ciphers

Also known as symmetric ciphers, is a more traditional encryption, its encryption operations, decryption operations use the same key, the sender of the information and the receiver of the information in the transmission and processing of the information, you must *** with the same possession of the cipher (known as symmetric cipher). Therefore, both communicating parties must obtain this key and keep the key secret.

The security of a single-key cryptosystem relies on two factors: first, the encryption algorithm must be strong enough that decrypting the message based solely on the ciphertext itself is practically impossible; second, the security of the encryption method relies on the secrecy of the key, not the algorithm, and therefore there is no need to ensure the secrecy of the algorithm (in fact, many single-key cryptosystems used in reality systems in reality have algorithms that are publicly available), but we must ensure the secrecy of the key.

From these characteristics of single-key cryptography, we can easily see that it has two main problems: first, the key amount problem. In a single-key cryptosystem, every pair of communicators needs a pair of keys, when the number of users increases, it will inevitably bring about an exponential increase in the amount of keys, so in the network communication, a large number of keys generated ﹑ storage and distribution will be an intractable problem. Second, the key distribution problem. In single-key cryptosystems, the security of encryption is completely dependent on the protection of the key, but because the two sides of the communication are using the same key, and people have to communicate with each other the key, so in order to ensure the security, people have to use some other secure channel to distribute the key, for example, using a special messenger to transmit the key, the cost of this practice is quite large, and even can be said to be very unrealistic, especially in the In the computer network environment, people use the network to transmit encrypted files, but need another secure channel to distribute the key, it is obvious that this is very unwise and even ridiculous.

2.2 Public-key cryptography

Because single-key cryptosystems have such intractable drawbacks, the development of a new, more effective, and more advanced cryptosystems has become more urgent and necessary. In this case, a new public-key cryptography system has emerged, which breaks through to solve the key distribution problem that has plagued countless scientists, in fact, in this system, people do not even need to distribute the keys that need to be kept strictly confidential, and this breakthrough is also considered to be the greatest achievement in the history of cryptography in the past 2,000 years after the invention of the single-code substitution cipher.

This new idea was proposed in the 1970s by Diffie and Hellman, two scholars at Stanford University, and the biggest difference between this system and the single-key cipher is that:

In a public-key cryptosystem, encryption and decryption use different keys (as opposed to a symmetric key, which is called an asymmetric key), and there is a interdependence between these two keys: i.e., information encrypted with either key can only be decrypted with the other key. This allows the two parties to communicate confidentially without exchanging keys in advance. One of the encryption key and algorithm is open to the public, everyone can use this key to encrypt a file and then send it to the recipient, the encryption key is also known as the public key; and the recipient receives the encrypted file, it can be decrypted using his decryption key, which is privately managed by himself, and does not need to be distributed, and therefore also known as the private key, which solves the problem of key distribution.

To illustrate this idea, we can consider the following analogy:

Two people communicating in an insecure channel, assumed to be Alice (the recipient) and Bob (the sender), they want to be able to communicate securely without being destroyed by their adversary Oscar. Alice came up with a way to do this by using a lock (equivalent to a public key), which can be locked by anyone with a simple press. Anyone can lock it with a single click, but only Alice's key (equivalent to the private key) can open it. Then Alice sends countless such locks to the outside world. Anyone, such as Bob, who wants to send her a letter, only needs to find a box, and then use one of Alice's locks to lock it and then send it to Alice, and at this time, no one (including Bob himself) can open the box except Alice, who owns the key, so that even if Oscar can find Alice's locks, and even if Even if Oscar can find Alice's lock, and even if Oscar can intercept the box during the communication process, he can't open the box without Alice's key, which doesn't need to be distributed, so Oscar can't get the "private key".

From the above introduction, we can see that the idea of public key cryptography system is not complex, and the key to its realization is how to determine the public and private keys and encryption/decryption algorithms, that is to say, how to find the "Alice's lock and key" problem. We assume that in this system, PK is public information, used as the encryption key, and SK needs to be kept secret by the user, used as the decryption key. The encryption algorithm E and the decryption algorithm D are also public. Although SK and PK appear in pairs, SK can not be calculated from PK, they have to satisfy the following conditions:

① Encryption key PK encrypts the plaintext X, and then decrypts it with decryption key SK, the plaintext can be recovered, or it is written as DSK (EPK (X)) = X

② The encryption key can not be used for decryption, i.e. DPK (EPK (X)) ≠ X

③ On the computer, the encryption key can not be used for decryption, i.e. the decryption key can not be used for decryption, i.e. the encryption key can not be used for decryption.

③ Pairs of PK and SK can be easily generated on a computer.

④ It is practically impossible to derive SK from a known PK.

⑤ The operations of encryption and decryption can be swapped, i.e., EPK (DSK (X)) = X

It can be seen from the above conditions that encryption key does not equal to the decryption key in a public-key cryptosystem. The encryption key can be disclosed to the public, so that any user can send the information transmitted to this user with the public key encryption, while the only private key saved by this user is confidential, and only it can recover and decrypt the ciphertext. Although the decryption key can theoretically be deduced from the encryption key, this algorithm is designed to be practically impossible, or although it can be deduced, but it will take a long time and become infeasible. So making the encryption key public does not jeopardize the security of the key.

The idea of this system is simple, but how to find a suitable algorithm to implement this system is a really difficult problem for cryptographers, because since Pk and SK are a pair of keys that exist in a mutual relationship, it is very possible to derive the other from one of them, and if the adversary Oscar can derive SK from PK, then the system is no longer secure. Therefore, how to find a suitable algorithm to generate suitable Pk and SK, and make it impossible to derive SK from PK, is exactly a difficult problem that needs to be solved by cryptographers urgently. This problem has even stalled the development of public key cryptosystems for a long time.

To solve this problem, cryptographers considered the mathematical trapdoor one-way function, of which we can give an informal definition below:

Alice's public encryption function should be easy to compute, while computing its inverse (i.e., the decryption function) should be difficult (for anyone other than Alice). Many functions of the form Y = f (x) are easy to compute for a given value of the independent variable x; from a given value of Y, it is in many cases very difficult to compute the value of x according to the functional relation f (x). Functions that are easy to compute but difficult to invert are often called one-way functions. In encryption, we want the encryption function E to be a one-term one-shot function so that it can be decrypted. Although no function has yet been shown to be one-way, there are many one-shot functions that are considered one-way.

For example, there is the following function that is considered one-way, assuming that n is the product of two large prime numbers p and q, and that b is a positive integer, then define f:

f (x ) = x b mod n

(if gcd(b,φ(n)) = 1, then in fact this is the RSA cryptographic function we will talk about below)

If we want to construct a public-key cryptosystem, it is not enough to give a one-way one-shot function. From Alice's point of view, it is not necessary for E to be unidirectional, because it needs to decrypt the received message in an efficient way. Therefore, Alice should have a trapdoor that contains secret information about your function that is easy to derive for E. That is, Alice can decrypt it efficiently because it has additional secret knowledge, i.e., SK, that can provide you with the ability to decrypt the function D. Thus, we call a function a trapdoor unidirectional if it is a unidirectional function and its inverse is easy to derive after having knowledge of a particular trapdoor.

Consider the function f (x) = ?xb mod n above. We can tell that its inverse function f -1 has a similar form f (x ) = xa?mod n for the right value of a. The trap is the one that efficiently computes the correct exponent a (for the given b), using the factorization of n.

For convenience, we count particular one-way functions of a certain type of trapdoor as ?. Then a randomly chosen function f belonging to ? , as the public encryption function; its inverse function f-1 is the secret decryption function. Then the public key cryptosystem can be realized.

According to the above ideas about the trapdoor one-way function, scholars have proposed many kinds of public-key encryption methods, and their security is based on complex mathematical puzzles. Depending on the mathematical puzzles on which they are based, at least the following three types of systems are currently considered secure and effective: large integer factorization systems (representative of RSA), elliptic curve discrete logarithmic systems (ECC), and discrete logarithmic systems (representative of DSA).

§3 The RSA algorithm

3.1 Introduction

The current best known and most widely used public key system, RSA, was introduced in 1978 by Rivest, Shamir, and Adleman of the Massachusetts Institute of Technology (MIT) in a paper titled "Methods for Obtaining Digital Signatures and Public Key Cryptosystems". It is an asymmetric (public key) cryptosystem based on number theory and is a packet cryptosystem. Its name comes from the initials of the three inventors. Its security is based on the difficulty of factorization of large integers, which is a well-known problem in mathematics, and so far there is no effective method 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 for encryption and digital signatures using public key ciphers use the RSA algorithm.

The RSA algorithm was the first algorithm that could be used for both data encryption and digital signatures, and as such it provides a fundamental method for encrypting and authenticating information on public networks. It is usually Mr. into a pair of RSA keys, one of which is a confidential key, kept by the user; the other is a public key, which can be disclosed to the public, and can even be registered in a network server, people encrypt files with the public key to send to the individual, and the individual can decrypt and accept it with the private key. To improve the strength of confidentiality, the RSA key is at least 500 bits long, and 1024 bits are generally recommended.

The algorithm is based on the following two facts, which guarantee the security effectiveness of the RSA algorithm:

1) There are already fast algorithms for determining whether a number is prime or not;

2) Fast algorithms have not yet been found for determining the prime factor of a composite number.

3.2 How it works

1)Arbitrarily choose two different large primes p and q, and compute the product r=p*q;

2)Arbitrarily choose a large integer e, e is mutually prime with (p-1)*(q-1), and the integer e is used as the encryption key. Note: e is easy to pick, e.g., all primes greater than p and q are available.

3) Determine the decryption key d: d * e = 1 modulo (p - 1) * (q - 1) d can be easily computed from e, p, and q.

4) Disclose the integers r and e, but not d;

5) Encrypt the plaintext P (assuming that P is an integer less than r) into the ciphertext C, computed as:

C = Pe modulo r

6) Decrypt the ciphertext C into the plaintext P by computing:

P = Cd modulo r

However it is impossible to compute d based on only r and e (not p and q). Therefore, anyone can encrypt the plaintext, but only authorized users (who know d) can decrypt the ciphertext.

3.3 Simple Example

To illustrate how the algorithm works, we give a simple example below. Obviously we can only take very small numbers here, but as mentioned above, in practice we use much larger numbers for security purposes.

Example: Pick p=3, q=5, then r=15, (p-1)*(q-1)=8. Pick e=11 (a prime number greater than p and q), and compute d = 3 by saying d * 11 = 1 modulo 8.

Assuming that the plaintext is the integer 13, the ciphertext C is

C = Pe modulo r

= 1311 modulo 15

= 1,792,160,394,037 modulo 15

= 7

The recovered plaintext P is:

P = Cd modulo r

= 73 modulo 15

= 343 modulo 15

= 13

Because e and d are inverse, public-key cryptography also allows encrypted messages to be "signed" in such a way that the receiver can be sure that the signature is not forged.

Suppose A and B want to transmit data using public-key encryption, and A and B disclose the encryption algorithm and corresponding key, but not the decryption algorithm and corresponding key. the encryption algorithms for A and B are ECA and ECB, and the decryption algorithms for A and B are DCA and DCB, which are mutually inversive, and ECB and DCB, respectively. If A wants to send plaintext P to B, instead of simply sending ECB (P), it first applies its decryption algorithm DCA to P, and then sends the result encrypted with the encryption algorithm ECB.

The ciphertext C is:

C = ECB (DCA (P))

B receives C, and then applies its decryption algorithm DCB and encryption algorithm ECA to get the plaintext P:

ECA (DCB (C))

= ECA (DCB (ECB (DCA (P))/））））

= ECA (DCA(P))/*DCB and ECB cancel each other out*/

=

P? /*DCB and ECB cancel each other out*/

This way B is sure that the message is indeed sent from A, because only if the encryption process utilizes the DCA algorithm, with ECA can P be obtained, and only A knows about the DCA algorithm, and nobody else, not even B, can forge A's signature.

3.4 Advantages and Disadvantages

3.4.1 Advantages

The RSA algorithm is the first algorithm that can be used for both encryption and digital signature, and it is also easy to understand and operate.RSA is the most widely researched public-key algorithm, and it has been nearly two decades since it was proposed, and it has experienced a variety of attacks, and it has gradually been accepted by the people, and is generally recognized as one of the most excellent current public-key program. The encryption key and encryption algorithm of this algorithm are separated, which makes the key distribution more convenient. It is especially compatible with the computer network environment. For a large number of users on the Internet, the encryption key can be printed out in the form of a phone book. If a user wants to communicate confidentially with another user, he only needs to find out the other party's encryption key from the public key book and use it to encrypt and send out the transmitted message. When the other party receives the message, he decrypts it with the decryption key known only to himself and learns the content of the message. This shows that the RSA algorithm solves the problem of key management for a large number of network users, which is the most prominent advantage of public key cryptosystems over symmetric cryptosystems.

3.4.2 Disadvantages

1) It is troublesome to generate keys, which is limited by the prime number generation technique, and thus it is difficult to achieve one secret at a time.

2) Security, the security of RSA depends on the factorization of large numbers, but there is no theoretical proof that the difficulty of deciphering RSA is equal to the difficulty of factorization of large numbers, and most of the cryptographic community tends to think that factorization is not an NPC problem. At present, people have been able to decompose more than 140 decimal digits of large prime numbers, which requires the use of longer keys and slower speed; in addition, people are now actively looking for ways to attack RSA, such as the choice of ciphertext attack, the general attacker is a bit of camouflage of a particular message (Blind), so that the entity that owns the private key to sign. Then, after the calculation can get the information it wants. In fact, the attacks exploit the same weakness, namely the fact that there exists a multiplying power that preserves the multiplicative structure of the input:

( XM )d = Xd *Md mod n

As mentioned earlier, this inherent problem arises from the most useful feature of a public-key cryptosystem -- everyone has access to the public key. However, this problem cannot be solved algorithmically, and there are two main measures: one is to use a good public key agreement, to ensure that during the work process the entity does not decrypt information arbitrarily generated by other entities, and does not sign information of which it knows nothing; the other is to never sign a random document sent by a stranger, and when signing, first use the One-Way Hash Function to make a HASH on the document, or use different signing algorithms at the same time. Or use different signature algorithms at the same time. In addition to the use of public **** modulus, people also try to use some of the decryption index or φ (n) and so on attacks.

3) too slow, due to the RSA group length is too large, in order to ensure security, n at least 600 bitx or more, so that the cost of computing is very high, especially slow, slower than the symmetric cryptographic algorithms several orders of magnitude slower; and with the development of large number of decomposition techniques, this length is still increasing, is not conducive to the standardization of the data format. At present, the SET (Secure Electronic Transaction) protocol requires CA to use 2048-bit-long key, and other entities use 1024-bit key. In order to speed problems, people are now widely used single, public key cipher combined use of methods, advantages and disadvantages complementary: single key cipher encryption speed, people use it to encrypt longer files, and then use RSA to give the file key encryption, excellent solution to the single key cipher key distribution problems.

§4 Concluding Remarks

Currently, the increasingly surging demand for e-commerce and other Internet applications has led to the popularization of public key systems, and the amount of demand mainly includes access control to server resources and protection of e-commerce transactions, as well as rights protection, personal privacy, wireless transactions, and content integrity (e.g., guaranteeing the authenticity of a news report or a stock ticker), and so on. The development of public key technology to today, the obvious development trend in the market is the integration of PKI and the operating system, PKI is the abbreviation of "Public

Key Infrastructure", which means "Public Key Infrastructure". PKI is an acronym for "Public Key Infrastructure", meaning "Public Key Infrastructure". Public key systems are widely used in areas such as CA authentication, digital signatures, and key exchange.

The most widely used public key encryption algorithm is RSA. The initial concept and goal of the RSA algorithm is to make the Internet safe and reliable, aiming to solve the DES algorithm secret key using the open channel transmission and distribution of the problem. The actual result is not only a good solution to this problem; RSA can also be used to complete the digital signature of the message to resist the denial and denial of the message; at the same time, digital signatures can also be used to more easily find the attacker's illegal tampering with the message in order to protect the integrity of the data and information. So far, many kinds of encryption technology uses the RSA algorithm, the algorithm has also been widely used in many aspects of the Internet, including the application of the Secure Interface Layer (SSL) standard (the standard is a web browser must be used to establish a secure Internet connection). In addition, RSA encryption systems are used in smart IC cards and network security products.

However, the RSA algorithm is currently approaching the end of its patent term, and has been replaced by an elliptic curve-based cryptography scheme (ECC algorithm). ECC has relative advantages over the RSA algorithm, which makes its characteristics more suitable for today's e-commerce development trend that requires rapid response. In addition, a new type of quantum cipher is being developed.

As for what kind of encryption algorithm should be used in practical applications, it should be combined with specific application environments and systems, and should not be based on its encryption strength to make a judgment. Because in addition to the encryption algorithm itself, the key reasonable distribution, encryption efficiency and the existing system of the combination of input and output analysis should be in the actual environment of specific considerations. Encryption technology with the development of network updates, there will be more secure and easier to implement algorithms continue to produce, for information security to provide a stronger guarantee. In the future, we will wait and see what will happen to encryption technology.

References:

[1] Douglas R. Stinson, Principles and Practice of Cryptography. Beijing:Electronic Industry Press,2003,2:131-132

[2] Simon. Singer. Cipher Stories. Haikou:Hainan Publishing House,2001,1:271-272

[3]The RSA Algorithm for Cryptographic Algorithms. Encryption algorithm of RSA algorithm. /yumdq/dzsw/a2.htm

[5]Hacker Intermediate Tutorial Series X. /jiaocheng/10.html