Cryptosystem Vulnerability to Attacks and How to Overcome Them

4.3 Conclusion

PKI allows participants to authenticate each other and use information from public key certificates to encrypt and decrypt information. In particular, it allows electronic transactions to take place with confidentiality, integrity, authenticity and non-repudiation without the need to exchange secret information beforehand.

As analyzed above, the hierarchical PKI architecture is very suitable for deployment in tightly managed organizations and the bridge CA architecture is the most suitable architecture to link PKIs implemented with different architectures. Indeed, these are two typical architectures applied by most countries in the world.

Each architecture has its own strengths and weaknesses. The bridge CA architecture has the advantage that units can deploy immediately and freely develop CAs. However, investing in building a bridge CA system will be very complicated and expensive. For example, China has applied this architecture for 3 years but still has many unresolved problems, or the US has implemented it for 7 years but it is still not really promising. On the contrary, the Korean-style decentralized PKI model has the advantage of being simple to deploy, easy to manage and convenient for users, each person only needs one set of keys for all authentication services. According to data up to May 2006, China has 77 CAs but only ranks 57/191 in e-government while Korea has only 6 CAs but ranks very high at 5/191.

At the first workshop on the topic "Application of digital signatures and digital signature certification services" organized by the Ministry of Information and Communications on April 6, 2006 and at the workshop "Organizational model and policy for developing the national certification system" organized by the Ministry of Information and Communications on May 25, 2006, most of the participating experts agreed that with a small country like Vietnam, it is advisable to choose a centralized PKI model with a tree-like hierarchy, that is, a common national CA organization (Root CA) and below that is a system of sub-CAs. This model is both simple and easy to deploy and manage, suitable for countries that are just starting out. Furthermore, in the "Workshop on sharing experiences on building a CA system" organized in mid-May 2006, Hungarian experts (a country with very strong certification services) also recommended that Vietnam should choose a tree-like PKI model similar to the model that Hungary is applying. In addition, there are also opinions that Vietnam should develop 2 CA systems (like Malaysia and some other countries in the region), 1 public CA system for people and private organizations, 1 CA for state agencies. Having 2 CAs operating in parallel is also a solution in case one CA collapses or is broken.

Thus, the authentication system on the hierarchical PKI model needs to be studied for practical implementation. First of all, one of the top concerns is the public key cryptosystem (especially RSA), the core of PKI must truly provide security. Chapters 5 and 6 will focus on research and analysis on this issue.

Chapter 5

Analysis of some vulnerabilities in the RSA cryptosystem

The content of this chapter focuses on analyzing the risks of attacks that cause damage to the RSA encryption system, thereby providing solutions to install a secure encryption system.

5.1 Overview of RSA cryptosystem

5.1.1 Introduction

Information technology plays an increasingly important role in many human activities, especially in the field of information security. In order to ensure the authenticity and reliability of information transmitted over the network, information security issues during the process of exchanging and storing data are extremely important, which means that information must be protected by a secure code system.

The original symmetric encryption systems did a good job of securing information. These encryption systems all used the same secret key in both the encryption and decryption processes, and therefore securing information means securing that shared key. However, if there are many groups of people in the system who need to exchange confidential information with each other, the number of shared keys that need to be kept secret is very large, making it difficult to manage and exchange. Moreover, if this key is revealed, many people who share that key will be affected.

Asymmetric encryption systems were invented to solve this problem by using two types of keys in the same key pair, a private key and a public key. The public key is widely published and used to encrypt information, while the private key is held by only one person and is used to decrypt information encrypted with the public key. The important feature is that it is impossible to find the decryption key when only knowing the encryption key within an acceptable time. Moreover, if one person reveals his decryption key, it does not affect the others.

The most popular asymmetric encryption algorithm today is RSA [48]. This algorithm was first described in 1977 by three mathematicians, Ron Rivest, Adi Shamir and Len Adleman, at the Massachusetts Institute of Technology (MIT) and was patented by MIT in the United States in 1983. The algorithm was not widely used at first due to its slow computing power at that time, but is now applied in many fields such as electronic signatures and authentication used in banking systems, e-commerce, and e-government.

5.1.2 Algorithm

The RSA algorithm is described as follows:

(1) Choose 2 distinct large prime numbers 𝑝 and 𝑞 . (2) Calculate 𝑛 = 𝑝𝑞 and 𝜑(𝑛) = (𝑝 – 1)(𝑞 – 1) .

(3) Randomly select an integer 𝑒 (1 < 𝑒 < 𝜑) such that 𝑔𝑐𝑑(𝑒, 𝜑) = 1 .

(4) Calculate 𝑑 so that 𝑑𝑒 ≡ 1 (𝑚𝑜𝑑 𝜑(𝑛)) . (5) Announce (𝑛, 𝑒) and keep secret (𝑝, 𝑞, 𝑑) .

In which, 𝑛 is called 𝑚𝑜𝑑𝑢𝑙𝑜 , 𝑒 is the public exponent (also known as the encryption exponent) and 𝑑 is the secret exponent (also known as the decryption exponent). The set (𝑛, 𝑒) is called the public key and (𝑛, 𝑑) is called the secret key. This key pair is symmetric, meaning that one key is used for encryption and the other key is used for decryption and vice versa.

The two processes of encoding and decoding are similar. Specifically, as follows:

 Encryption : B wants to send message 𝑀 to A, B will convert 𝑀 to 𝑚 < 𝑛 using some two-way function agreed upon with A. B already knows 𝑛 and 𝑒 (sent by A), so B will calculate 𝑐 = 𝑚 𝑒 𝑚𝑜𝑑 𝑛 and then send this c to A.

 Decryption : When receiving 𝑐 from B and knowing the secret key 𝑑 , A will calculate

𝑚 = 𝑐 𝑑 𝑚𝑜𝑑 𝑛 . Using the two-way function agreed with B, A will find 𝑀

from 𝑚 calculated above.

It is easy to see that the main operations used in the RSA encryption system are multiplication and exponentiation 𝑚𝑜𝑑𝑢𝑙𝑜 . Therefore, the encryption speed of RSA is very slow, about 1000 times slower than the encryption speed of symmetric encryption systems.

5.1.3 Important applications

The invention of the RSA cryptosystem was a revolution in information security technology because it eliminated the hassle of distributing shared keys for encryption and decryption in symmetric cryptosystems. The RSA cryptosystem uses a pair of keys: a public key for encryption and a private key for decryption. This flexibility gives RSA many important applications, especially the following:

 Creating a secure cover for text: RSA's encryption speed is very slow, so RSA is often not used to encrypt large text. Therefore, RSA is often used in combination with high-speed symmetric encryption systems such as DES, AES, IDEA,

… to create a secure shell for the text. Symmetric encryption systems will encrypt the text with a secret key and RSA will encrypt this secret key. Thus, symmetric encryption systems have overcome the slow encryption speed of RSA and RSA has overcome the difficulty in transferring the key to the recipient of symmetric encryption systems.

 Subject authentication: encryption keys are publicly announced, so it is inevitable that one individual will impersonate another individual to send a message to a third individual. In other words, how can we “sign” electronic messages so that the recipient knows exactly who the message is from and so that the sender does not shirk responsibility for the message he sent? In short, RSA in particular and public key encryption in general have provided an effective tool for “signing electronic documents”, in which signing a document means encrypting it with the individual’s own secret key (presented in Chapter 2).

In addition, RSA is also used in security protocols such as IP data security (IPSEC/IKE), data transmission security (TLS/SSL), email security (PGP), end-to-end connection security (SSH), conference service security (SILC), ...

5.2 Vulnerability of the cryptosystem to attacks and how to overcome them

The RSA cryptosystem is built on the basis of exponential codes and takes advantage of the difficulty of factoring a large number into prime numbers, which is considered impossible (within acceptable time). The time required to factorize an integer 𝑛 into prime numbers using the fastest algorithm available today on a computer with a speed of 10 5 calculations/second is also extremely long [1, pp.5-6]:

Table 5.1. Time to factorize a large number into prime factors

So, if we choose the digits 𝑝 and 𝑞 to have about 100 decimal places, then 𝑛 will have about 200 decimal places. To factor such a large integer with today's fastest algorithms and with the most modern computers, we would need billions of years!

To shorten the time, people can mobilize many computers to analyze a given number 𝑛 . A typical example is the number 𝑛, which is 128 decimal places long, was analyzed on April 26, 1994 by a total international effort (via the Internet) using 1600 workstations, mainframes and supercomputers for 8 consecutive months.

Therefore, the reality shows that the RSA public key cryptosystem is very secure because it is rare to have the conditions to mobilize such a large computational force. In addition, due to its simplicity in design and implementation, RSA is widely used and is probably the most used among the algorithms with public keys. That is also why it has undergone many challenges, reviews, and careful surveys of the community and has obtained many test evidences of its safety.

However, with more than 30 years of existence as the most popular public key cryptosystem, RSA has faced careful examination under various types of attacks by professional cryptanalysts and in fact, RSA can be broken if people do not know how to use it properly [11].

The following section details some common attacks and how to mitigate them.

5.2.1 Vulnerability to Prime Factorization Attacks

Although public key encryption has solved the limitations of secret encryption, due to the widespread dissemination of public keys, it is inevitable that others will find ways to analyze them in order to control confidential information. The popular public key encryption system RSA mainly exploits the problem of factoring the number 𝑛 into prime numbers and considers solving this problem impossible when 𝑛 is large in the range

Acceptable time. Algorithms for factoring prime numbers can be divided into two groups :

Group of techniques

special analysis​​​

know

(special purpose) : understanding

These algorithms rely on unknown prime factors, which are good when the prime factors chosen to construct the cipher are small. This group includes the trial division method, the 𝑝–1 method , and Pollard's "𝑟𝑕𝑜" method, the

Group of techniques

general purpose : understanding​​​​