Hu Xiong＊, Ting Zhong, Guobin Zhu,Zhiguang Qin

Abstract: Different from traditional symmetric cryptography, public key cryptography allows each user to own a pair of public/private key pair. Given the public key of one user and the data to be encrypted, a ciphertext can be generated such that only the intended user is able to recover the data using his/her private key associated with public key involved in the encryption process.To really understand the philosophy behind the public key cryptography is not an easy task and sometimes it seems somewhat difficult, if not impossible, for the beginners without the knowledge of the abstract algebra and number theory. In this paper, we introduce briefly the basic definition of public key cryptography as well as the corresponding mathematical hard problems. Besides, we explain why the mathematical backgrounds, especially abstract algebra and number theory, matter in the study of public key cryptography.

Key words: public key cryptography; number theory;abstract algebra

1 Brief Review of Public Key Cryptography

In the symmetric cryptosystem, the secret keys used in the encryption and decryption are identical to each other. To ensure the communication between one pair of participants cannot be read by any other entities, it is desirable for each pair of participants to securely share an unique secret key. In this way, the key management in the symmetric cryptosystem is regarded as cumbersome. For instance, secret keys are needed in the system with users and secret keys are required to be maintained by each participant. To simplify the key management problem, public key cryptography[1]has been invented as one of the revolutionary milestone in the cryptography. In public key cryptography, each user owns a pair of public/private key pair. Concretely,the public key is distributed to everyone in the system,while the private key is kept secret by its owner. Given the message to be encrypted and the public key of the intended receiver, the ciphertext is able to be generated by carrying out the encryption algorithm.

In the decryption algorithm, only the secret key corresponding to the public key involved in the encryption algorithm is needed to perform the decryption algorithm. In this way, the key management in the symmetric cryptosystem has been significantly simplified in the public key cryptography. Considering the untouched advantage of public key cryptography,the Turing Awards are given to the invention[1]and first implementation[2]of public key cryptography in 2015[3]and 2002 respectively.

Despite the merits offered by the public key cryptography, it is not an easy task to understand the rationale behind public key cryptography because all the existing public key cryptosystems are constructed on the mathematical tools. In essence, public key cryptography can be regarded as an analogue of lock and key in the physical world. To realize the function of lock and key in the digital world, some abstract algebra and number theory are required. It is difficult, if not impossible, to really learn public key cryptography without the knowledge of these mathematical backgrounds.

2 How to Integrate Abstract Algebra and Number Theory Matter in the Study of Public Key Cryptography Elegantly

Fortunately, abstract algebra and number theory provide a promising mathematical background to construct public key cryptography. Intuitively, this kind of hard problems in abstract algebra and number theory,where no efficient general approach for solving these hard problems is known otherwise possessing some pre-selective secret, can be utilized in the construction of public key cryptography. On one hand, abstract algebra[4]refers to the study of algebraic structures including groups, rings and fields. On the other hand,number theory[5]mainly studies prime numbers and the properties of objects made out of integers. Traditionally,treatments of both abstract algebra and number theory have faced a dilemma: abstract algebra first or number theory first? Presenting number theory first immediately offers familiar concepts such as division, congruence,as well as intuition obtained from discussing with the integers. Furthermore, the definitions and axioms for number theory are less complicated comparing to the counterparts for abstract algebra. On the other hand,however, abstract algebra, such as groups, rings and fields, underlies number theory such as quotients by subgroups. The dilemma is solved by emphasizing congruence along with divisions. Congruence and divisions are steps up to number theory, while abstract structure in the abstract algebra can be instantiated by the congruence and divisions. Furthermore, the abstract algebra and number theory can be taught in a hybrid mode instead of discussing separately if we concentrating key points, i.e., congruence and divisions. In this way, we can integrate abstract algebra and number theory matter in the study of public key cryptography elegantly.