RSA-Public Key Cryptosystems Based on Quadratic Equations in Finite Field

Introduction

The idea of a public-key cryptography was put forward by Diffie and Hellman in 1976. Then, in 1977, Rivest, Shamir, and Adleman invented the well-known RSA Cryptosystem. Several public-key cryptosystems have been proposed, whose security is based on different computational problems. The most important are the RSA Cryptosystem (and variation of it), in which the security is based on the difficulty of factoring large integers; and the ElGAmal Cryptosystem (and it’s variations such as Elliptic Curve Cryptosystems) in which the security is based on the discrete logarithm problem (Diffie & Hellman, 1976).

Prior to Diffie and Hellman, the idea of public-key cryptography was already proposed by James Ellis in January 1970, in a paper entitled “ The Possibility of Non-secret Encryption”. This paper was not published in the open literature and was one of the five papers released by the GCHQ (British Government Communication Headquarters) officially in December 1997. also among these five papers was a 1973 paper written by Clifford Cocks, entitled “ A Note on Non-secret Encryption,” in which a public-key cryptosystem is described that is essentially the same as the RSA cryptosystem (Douglas, 2006).

A public-key cryptosystem can never provide unconditional security. This is because an opponent, on observing a ciphertext y, can encrypt each possible plaintext in turn using the public encryption rule (e_k) until he/she finds the unique x such that y = e_k (x) . It is helpful to think of a public-key in terms of an abstraction called a trapdoor one-way function. This notation can be defined as:

Bob’s public encryption function, (e_k), should be easy to compute. We have just noted that computing the inverse function (i.e., decrypting) should be hard (for anyone other than Bob). It is well known that a function that is easy to compute but hard to invert is often called a one-way function. In the context of encryption, we desire that (e_k) be an injective one-way function so that decryption can be performed. Unfortunately, although there are many injective functions * that are believed to be one-way, there currently do not exist such functions that can be proved to be one-way (Nimrod & Christos, 1989).

Example of a function (which is believed) to be one-way:

Suppose n is the product of two large primes p and q, and let b be a positive integer. Then define f: Zn→ Zn to bef(x) = x^b mod n.(if gcd(b, ф(n))=1, then this is in fact an RSA encryption function).

In the classical model of cryptography, Alice and Bob secretly choose the key (K). K then gives rise to an encryption rule (e_k) and a decryption rule (d_k). In these cryptosystems, (d_k) is either the same as (e_k), or easily derived from it. For example, in DES (Block Cipher Type), the decryption process is identical to encryption process, but the key schedule is reversed. A cryptosystem of this type is known as a symmetric-key cryptosystems, since exposure of either of (e_k) or (d_k) renders the system insecure. Figure 1 shows two-party communication using encryption, with a secure channel for key exchange. The decryption key can be efficiently computed from the encryption key.

Figure 1.

Encryption using secret key technique

One drawback of symmetric-key cryptosystem is that it requires the prior communication of the key (K) between Alice and Bob, using a secure channel before any cipher text is transmitted. In practice, this may be very difficult to achieve. For example, suppose Alice and Bob live far away from each other and they decide that they want to communicate electronically, using email. In a situation such as this, Alice and Bob may not have a reasonably secure channel.