A New Public Key Cryptosystem

Abstract

In this paper a new CCA secure public key cryptosystem is presented. The introduced cryptosystem is simple and based on the factorization problem. The cryptosystem has two public keys and two private keys. Therefore two encryption algorithms and two decryption algorithms are in this system. Here, we hide the message in a matrix. This situation makes a difficult puzzle for adversaries. In this method, the public encryption key is (e,r,𝑛), e and r are any prime numbers greater than 2 and less than n, n is a product of two large prime numbers. The decryption key is (d,s,𝑛). d and s are multiplicative inverses of e modulo ф(n) and r modulo ф(n) respectively. We should select another integer 𝑔 (< 2𝑚) and set the message 𝑚 and 𝑔 in a 2 ∗ 2 matrix 𝑋 as the determinant of X is odd. We encrypt the determinant of the matrix by raising it to the eth power modulo 𝑛. We also have to send 𝑔 for the decryption. 𝑔 is encrypted by raising it to the rth power modulo 𝑛. When we decrypt the first ciphertext by raising it to another power d modulo 𝑛 and the second ciphertext by raising it to another power s modulo 𝑛, we can find the message m. For an example, let 𝑝 = 7,𝑞 = 11, 𝑒 = 23, 𝑟 = 29. Then, 𝑛 = 𝑝𝑞 = 7 × 11 = 77,ф(𝑛) = 60. Then for the private keys, 𝑑 = 47 and 𝑠 = 29. Let the message, 𝑚 = 30 and 𝑔 = 7. Then, 𝑋 = ( 30 7 1 2 ). From the encryption equations, 𝐶1 ≡ [𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡(𝑋)𝑒] 𝑚𝑜𝑑 𝑛 ≡ 5323 𝑚𝑜𝑑 77 ≡ 58 and 𝐶2 ≡ [𝑔𝑟] 𝑚𝑜𝑑 𝑛 ≡ 729 𝑚𝑜𝑑 77 ≡ 63. The decryption equations are Determinant (𝑋) ≡ [𝐶1𝑑] 𝑚𝑜𝑑 𝑛 ≡ 5847 𝑚𝑜𝑑 77 ≡ 53 and 𝑔 ≡ [𝐶2𝑠] 𝑚𝑜𝑑 𝑛 ≡ 6329 𝑚𝑜𝑑 77 ≡ 7. Then, using 2𝑚 – 𝑔 = Determinant (𝑋), we can find 𝑚 = 30. If we use the fast exponentiation algorithm then the computational complexity of the cryptosystem is in polynomial time. The proposed cryptosystem is OW-CCA2 secure and also can use any standard security model to increase the security.