By: Dr. Muhammad Asyraf Asbullah

Mathematics, Centre of Foundation Studies for Agricultural Science,

Universiti Putra Malaysia

 

Introduction

 

Post-1990's, the exponentially growing common medium for transporting information is through electronic means. Currently, the internet assumes this role. The internet: is a worldwide network that is being shared amongst people all around the globe. The internet contains many entities, indistinguishable from countries or nations, with users of varied interests and intentions, in every aspect imaginable. We could send emails or communicate with people, do monetary transactions through electronic commerce, and purchase items online with just simple clicks. Nowadays, our daily activities and conversation are dependent on internet connectivity. Such internet dependencies led us to consider the security and privacy of communication in cyberspace since it may easily be compromised by the authorities, hackers, or terrorists. Some view them as the adversary of the system. Hence, it is necessary and important to establish a system or environment that guarantees the security of internet users from any type of adversary.

 

         Cryptography provides a means to ensure that our privacy and confidential information is secured. It is of great interest to analyse the strengths and weaknesses of encryption and decryption processes. In classical terminology, encryption is a conversion procedure of information that changes its readable state into another type of information yet appears to be nonsense. When we enter the computer age, the technologies evolve rapidly; therefore, the definition of encryption is also amended. In modern terminology, we may say that encryption is a process of converting ordinary information (i.e., known as plaintext) into an unintelligible form (i.e., called a ciphertext). Conversely, decryption is the reverse process of encryption, which functions to recover the intended or actual plaintext from its corresponding ciphertext.

 

            Apparently, both the encryptor (sender) and the decryptor (receiver) must have 'the key' to successfully perform their operation, respectively. The encryptor uses the key to scramble ordinary plaintext information such as a readable message or any meaningful data) and turns it into ciphertext. This very same key is also being used by the decryptor to recover the original plaintext from its ciphertext. Consequently, no matter how obscure the algorithm for encryption and decryption is, it could be problematic if the key is not safe in the first place. This is the basic concept known as Kerckhoffs' principle, which states that the security level of encrypted information is as strong as the security of its key.

 

Definition 1. (Kerckhoffs' Principle). The security of any cryptosystem should depend only on its key's secrecy, not the secrecy of the cryptosystem algorithm itself.

 

           This is because it is much easier to maintain the secrecy of a key instead of an algorithm. If the key is exposed, it is easier to change the key instead of replacing the used algorithm. Accordingly, returning a new key after a certain period is good practice. Furthermore, sharing the same algorithm publicly between the communicating parties is much more practical.

 

           As suggested by Kerckhoffs's principle, the details of any cryptographic algorithm need to be public knowledge, which is the contrast to the concept of the `security by obscurity, except the secrecy for key (Katz and Lindell, 2008). It is natural to assume that the adversary knows everything about the algorithm in modern cryptography philosophy. Therefore, the key is the only information that needs to be kept secret.

 

Asymmetric Encryption

 

In the classical system, the secret key is supposedly shared symmetrically between the sender and the receiver. The key must be shared or distributed securely to both parties to maintain secrecy. However, exchanging secret keys is problematic when the number of users gets larger since more keys are needed to be delivered to various parties. Diffie and Hellman (1976) have come up with the notion of asymmetric encryption to tackle this problem.

Definition 2.  (Diffie and Hellman, 1976). Let  denote the message space,  denote the ciphertext space,  denote the key space,  denote the plaintext and  denote the ciphertext. Asymmetric encryption scheme is defined as follows.

1. Key generation algorithm is a probabilistic algorithm that will generate a public key denoted as  and private key as  
2. Encryption algorithm is a probabilistic algorithm that takes a message  and the public key , to produce a ciphertext  as a function of .
3. Decryption algorithm is a deterministic algorithm which is given the ciphertext  and the private key , will output . That is .

 

            Basically, if a cryptosystem uses the same secret keys and is shared by both; sender and receiver, it is called a symmetric cryptosystem. Suppose a cryptosystem involves a private key and a public key. In that case, the cryptosystem is known as an asymmetric cryptosystem or commonly referred to as a public-key cryptosystem.

Definition 3. (Proof of Correctness). For each pair of key  output by the algorithm , and for every message  and ciphertext  then .

 

As defined by Definition 3, the proof of correctness suggests that the decryption is the reversal operation of encryption and should be proved to be correct to return the plaintext from its ciphertext. The trapdoor information is auxiliary information that allows the inverse to be easily computed (Hoffstein et al., 2008). For instance, the private key is the trapdoor information to the encryption function. Without the correct private key, one will not do the decryption. On the contrary, decryption is easy with the right private key.

 

Definition 5. (Trapdoor One-way Function). A trapdoor one-way function is a piece of information that allows the inverse for the one-way function to be easily computed (i.e. it is easy to compute the value of  by using trapdoor information).

            Since we cannot prove the existence of the one-way function, we always can show that a problem is indeed hard corresponding to the concept of the one-way function.

Definition 6. (Cryptographic Hard Problem). A cryptographic hard problem is defined as a concrete mathematical object which is easy to compute in one direction, but very hard to invert.

            Basically, a hard cryptographic problem is widely believed to be hard. Cryptographically speaking, the word ‘hard’ from Definition 6 refers to the difficulty level for solving a certain mathematical problem, including with the help of state-of-the-art technology. The terminology of the hard cryptographic problem provides confidence to the designing process. The security measured depends on how difficult its related hard problem could be. Suppose the correct steps are taken, and the appropriate parameters are chosen. In that case, solving hard problems might be infeasible, even via brute force. This is the main ingredient for designing and constructing a public key cryptosystem.

 

           Remark that from Definition 6, it does not necessarily mean that no one has figured out how to do the inversion, but it is rather shown that there exists no efficient algorithm that runs in a reasonable time (i.e. in polynomial time) that can do such operation (Katz and Lindell, 2008). Thus, if the effort to solve a stated mathematical problem exceeds a certain amount of time (i.e. in exponential time), then we say that such a mathematical problem is considered intractable, even using the most powerful tools available. On the other hand, suppose the stated mathematical problem can be solved below or within a certain polynomial-time range. The cryptosystem that relies upon such problems is considered insecure (Galbraith, 2012).

 

            To date, one of the most celebrated problems in mathematics, particularly in number theory, is known as the integer factorization problem and exhibits properties of a hard cryptographic problem. It is assumed to be very difficult to solve and is supported by decades of evidence for its hardness. In addition, it is widely believed that the integer factorization problem is a suitable candidate for a one-way function. For most cases in cryptography, the problem is to find the prime factors  and  from . Furthermore, this problem is still being considered a very difficult problem, which cannot be solved in polynomial time.

Conclusion

In the beginning, we have elaborated on why it is necessary to ensure the security of the key from both theoretical and practical points of view. We then further discussed the basic principle of asymmetric encryption designs, consisting of three important algorithms: the key generation algorithm, the encryption algorithm, and the decryption algorithm. In addition, it is customary for any cryptosystem to provide proof of correctness for their algorithms. This meant to show how the algorithms used for decryption could always decrypt the encrypted data of intended messages. Finally, we ended with an explanation on a mathematical object called the hard cryptographic problems, which are basically used as parts of the designing process for asymmetric encryption and for any modern cryptosystem in general.

 

References

Diffie, W., and Hellman, M. E. (1976). New directions in cryptography. Information Theory, IEEE Transactions on, 22(6), 644-654.

Galbraith, S. D. (2012). Mathematics of public key cryptography. Cambridge University Press.

Hoffstein, J., Pipher, J. C., Silverman, J. H., and Silverman, J. H. (2008). An introduction to mathematical cryptography (pp. 18-50). New York: Springer.

Katz, J., and Lindell, Y. (2014). Introduction to modern cryptography. CRC Press.

 

Tarikh Input: 11/09/2022 | Kemaskini: 11/09/2022 | hasniah