A Public-key Algorithm Based On RSA And Kth Power Residue

In 1978, R. L. Rivest, A. Shamir and L. Adleman proposed the famous public-key cryptosystem, named RSA cryptosystem. Today RSA is the most commonly used public-key cryptosystem and the de facto standard.The security of RSA is based on the difficulty of factoring large integers. As factoring methods and computational power improving, we have to increase the size of large integers, which lower the speed of the RSA cryptosystem.In this thesis, we propose a public-key algorithm based on RSA and k th power residue theorem, named k-RSA public-key algorithm, whose security depends on the difficulties of factoring large integers and finding discrete logarithms. Compared to RSA, k-RSA public-key algorithm has faster encryption and decryption speed by using a smaller exponent. At the same time, it is still secure.The k-RSA public-key algorithm has high flexibility in parameter selection. Besides the basic functions of public-key algorithm, we can use k-RSA public-key algorithm to facilitate the realization of multi-level cryptosystem, secret share scheme (threshold scheme), multi-people digital signature, etc.In addition, we analyse the current problems of k-RSA public-key algorithm and provide a compromise solution for storage issues. In the solution we effectively overcome the storage problem by increasing a little computing cost.Finally, in order to enhance the security and efficiency of k-RSA public-key algorithm, we present a few ideas that can be carried out at the next step, such as more robust algorithm, more complex parameter settings, the introduction of parallel processing, etc.