030309

ABSTRACT The idea of Public Key Cryptosystem [PKC] was introduced by Diffie and Hellman in 1976, many PKC schemes have been proposed and broken. The trapdoor one way functions play the key role in the idea of PKC. Today, most successful PKC schemes are based on the perceived difficulty of certain computational problems. For eg., Difficulty of solving the Integer Factorization Problem depend over the ring Z n (where n is the product of two large primes) forms the ground of the basic RSA Cryptosystem. Elliptic curve cryptosystems are constructed over elliptic curves over some finite fields Fn , where n is either a prime or a power of 2. After the appearance of the RSA cryptosystems, many mathematicians and cryptographers have become interested in finding another suitable structure for PKC, and many PKCs have been proposed. In this direction, Koyama and Koyama et al. have constructed three different PKCs analogue to RSA based on singular cubic curves. However (the efficiency and security are two important demands of any cryptosystem) the cryptosystem presented by Koyama is not semantically secure and also not secure against low exponent attack, related message attack and partially known plaintext attack.

In this thesis, we propose an RSA type public key cryptosystem based on singular 2 3 2 cubic curve of the form Cn  0, b  : y  x  bx  mod n  . The security of the scheme is based on

its difficulty of factoring n, which is a product of two large primes p and q. The proposed scheme is not only semantically secure but also prevents the above said attacks. As far as efficiency is concerned the proposed scheme is more efficient than the scheme given by Koyama.

1

CHAPTER – I 1.1 General Introduction: Confidential Communication is one of the necessities of the Social Life. In this Context, some questions that need attention are: •

How can one transmit the message secretly, so that no unauthorized person gets knowledge of the message?

•

How can the sender ensure himself that the message arrives in the right hands exactly as it was transmitted?

•

How can the receiver ensure himself that the message is coming from the right person exactly as it was transmitted? Traditionally, there are two ways to solve such problems. One can disguise the

very existence of the message, perhaps by writings with invisible ink; or try to transmit the message via a trustworthy person. A different scientific approach to solve these problems is cryptography. Cryptography is the study of mathematical techniques related to aspects of information security. The concept of securing messages through cryptography has a long history of at least 4000 years. Ancient Egyptians enciphered some of their hieroglyphic writings on monuments. The first cryptosystem, named as “SCYTALE” was established in Greece in the 5th Century B.C. Julius Caesar is credited with using one of the earliest cryptographic systems to

2

send military messages to his Generals. He replaced every A by D, every B by E, and so on through the alphabet. The Greek writer Polybius devised a cryptosystem, in which he replaced letters to numbers. Arabs first wrote proper cryptology as early 900 A.D. and used it extensively in 1412. In 1460, Leon Alberti devised a cipher wheel. In 1585, Blaise De Vigenere described the polyalphabetic substitution cipher. In 1790, Jefferson, developed a cylinder comprised 26 disks, each with a random alphabets. The key was order of discs. In 1817, Wadsworth invented a disc, which was later developed by Wheatstone in 1860 and now known as Wheatstone disc. It generates a polyalphabetic cipher using two concentric wheels. Enigma Rotor machine, one of important class of machines, heavily used during World War II, comprised as series of rotor wheels with internal cross-connections, providing a substitution using a continuously alphabet. After the First World War, things begin to change. U.S. Army and Navy organizations, working secretly and confidentially, began to make fundamental advances in cryptography. During 30s and 40s, a few basic papers did appear in the public literature and several treatises on the subject were published, notable among these are the basic papers by Hill [10] on matrix-based cryptosystems. Claude Shannon published his two fundamental papers about communication theory. In 1948, A Mathematical Theory of Communication [32] and in 1949, Communication Theory of Secret Systems [33] appeared in the Bell System Technical Journal. From 1949 to 1967, the cryptographic literature was not in abundance. In that year a different sort of contribution appeared: David Kahn’s history, The Codebreakers. It did not contain any new technical ideas but it contains a remarkably complete history of what had

3

gone before, including mention of something that the U.S government still consider secret. to be written. Horst Feistel, who had earlier worked on identification friend or foe devices for the Air Force, took his life long passion for cryptography to IBM Watson Laboratory in Yorktown Height, New York. There he began development of what was to become the U.S. Data Encryption Standard (DES). By the early 1970s, Several technical reports on this subject by Feistel and his colleagues had been made public by IBM. In 1976, Whitfield Diffie and Martin Hellman presented their famous paper, New Direction in Cryptography [7]. In the last decades a lot of PKCs have been proposed, but nevertheless only a few cryptosystems namely RSA,ElGamal,Paillier etc., are used in practice. All those PKCs are based on number theoretic problems such as IFP ,DLP etc., . Inorder to increase the efficiency and security of PKCs, a lot of researchers have been searching for alternative cryptographic algoriths. 1.2. Over view of Thesis: In this thesis, we deal with the study and development of a PKC based on singular cubic curve that guarantees the semantic security. Here we overview the subject matter of each chapter. Chapter-I In this chapter we survey the back ground theory on which the subject matter of the rest of the thesis is based. First we review the basics of Abstract Algebra, Number theory and some computational problems such as Integer Factorization Problem, Discrete Logarithm

4

Problem. Also we review symmetric key cryptosystem, public key cryptosystem and digital signatures. Finally, we study the important security issues of a public key encryption schemes.

Chapter-II In this chapter , first we discuss some basic facts about the singular cubic curve over a finite field F p and over the ring Z .We present three RSA type cryptosystems proposed by Koyama et al. n based on singular cubic curves over Z n . Finally we discuss the security of these schemes and printout that these schemes are not semantically secure and also not secure against low exponent attack, partially known plaintext attack and linearly related message attack. Chapter-III In this chapter, we propose a new RSA type cryptosystem over singular cubic 2 3 2 curve Cn  0, b  : y  x  bx  mod n  along with an example. The security of the proposed

scheme is based on the RSA problem, more precisely on the difficulty of factoring n, where n is a product of large primes p and q. We analyze the semantic security of the proposed system. Finally, we analyze and compare our scheme with the Koyama scheme for security analysis and conclude that the linearly related message attack, partially known plaintext attack and low exponent attacks are not possible in our proposed scheme. 1.3. Mathematical Preliminaries:-

5

The purpose of this section is to present the algebraic, number theoretic definitions and results that are necessary for understanding the results in this thesis. All the theorems are quoted without proof, but with references to where a proof can be found. 1.3.1. Algebraic Preliminaries Definition 1.1:

A binary operation ‘.’ on a set S is a mapping from S x S to S. That is, ‘.’

is a rule which assigns to each ordered pair of elements from S an element of S. Definition 1.2:

A Group (G,.) or simply G consists of a set G with a binary operation ‘.’

on G satisfying the following properties. (i)

For every a,b,c ∈ G, a.(b.c) = (a.b).c (Associative)

(ii)

There is an element e ∈ G such that every a in G, a.e = e.a = a (Identity)

(iii)

For every a ∈ G, there is an element a −1 in G such that a.a −1 = a −1 .a = e (Inverse)

A group G is abelian (or commutative) if, further more (iv)

a.b = b.a, for all a,b ∈ G.

Definition 1.3:-

Let G be a group. If G has a finite number of elements, say n, then we say

that the order of G is n. we write this symbolically by O(G) = n, and in this case we say G is a finite group. Definition 1.4:-

A non empty subset H of a finite group G is a sub group if H is a group

with the same binary operation as G.

6

Definition 1.5:-

A group G is said to be cyclic if there exists an element g ∈ G such that

every element of G can be written as g n for some integer n. In this case, g is called a generator of G. If H is a sub group of the cyclic group G, then H is called a cyclic sub group of G. Definition 1.6:-

A homomorphism from (G1, . ) to (G2,*) is a mapping f from G1 to G2

such that f(a.b) = f(a) * f(b), for all a,b ∈ G1. Definition 1.7:-

Let (G1,.) and (G2,*) be groups and let f be a homomorphism from G1 to

G2. If f is both onto and one-to-one, then f is called an isomorphism. If f is an isomorphism, then G1 and G2 are said to be isomorphic, and we write G1 ≅ G2. Definition 1.8:-

A ring (R,+, .) or simply R consists of a set R with two binary operations,

denoted by + and . called addition and multiplication, which satisfy the following axioms. (i)

(a + b)+c = a+(b + c) for all a ,b ,c ∈ R (associativity of addition)

(ii)

There exists an element a ∈ R such that 0 + a = a for all a ∈ R (existence of additive)

(iii)

For each a ∈ R, there exists x ∈ R such that a + x = 0 (existence of additive inverse)

(iv)

a + b = b + a for all a,b ∈ R (commutative of addition).

(v)

(a.b).c = a.(b.c) for all a,b,c ∈ R (associativity of multiplication)

(vi)

a.(b+c) = (a.b) + (a.c) and (a+b).c = (a.c) + (b.c) for all a,b,c ∈ R (distributive).

Definition 1.9:-

Let R be a ring. Then R is said to be commutative ring if a.b = b.a for all

a,b ∈ R

7

Definition 1.10:-

A non empty set S is a subring of a ring R if S is a subset of R and if S

itself is a ring with respect to the addition and multiplication of R. Number Theoretic Preliminaries: The set of integers {…….. -2,-1, 0, 1, 2,……} is denoted by the symbol Z. Definition 1.11:-

Let a,b be integers. Then a divides b(equivalently : a is a divisor of b, or

a is a factor of b) if there exists an integer c such that b = ac. If a divides b, then we write a/b. Definition 1.12:-

“Division algorithm for integers : If a and b are integers with b≥1, then

ordinary division of a by b yields integers q(the quotient) and r (the remainder) such that a = qb + r, where 0 ≤ r < b. Moreover, q and r are unique. The remainder of the division is denoted by a mod b, and the quotient is denoted a div b. Definition 1.13:-

If a and b are integers, then a is said to be congruent to b modulo n, write

a ≡ b(mod n), if n divides (a-b). The integer n is called the modulus of the congruence. Definition 1.14:-

The eqivalance class modulo n of an integer b is the set of all integers

congruent to b modulo n. Definition 1.15:-

The ring of integers modulo n, denoted by Zn, is the set of (equivalence

classes of) the integers {0,1,2,…….. n-1}. Addition, subtraction and multiplication in Z n are performed modulo n. Definition 1.16:integer x

∈

An integer b

∈

Zn is said to be invertible or a unit of Zn if there is an

Zn, such that bx ≡ 1(mod n). If such an x exists, then it is referred to as the

multiplicative inverse of b in Zn, and denoted by b-1.

8

Theorem 1.1 (Chinese Remainder Theorem) Suppose n1,n2 , …nr are r positive integers that are pair-wise coprime, and let a1,a2….. ar denote any r integers. Then the congruence’s x ≡ a1 (mod n1) x ≡ a2 (mod n2) …….. x ≡ ar (mod nr) modulo n = n1.n2…… nr.

have a common solution which is unique

A Proof can be found in [21].

Definition 1.17:

The multiplicative group of Zn is Zn* = {a ∈ Zn / gcd (a,n)=1}.

Definition 1.18:

Let a ∈ Zn*. The order of a, denoted O(a), is the least positive integer k

such that ak ≡ 1(mod n). Fermat’s Theorem 1.2 :Let p be a prime. If gcd(p,a) = 1,then a p-1 ≡ 1(mod p). A proof can be found in [31]. Definition 1.19:-

The Euler Totient Function  (n) is the number of positive integers less

than or equal to n that are coprime to n. Theorem 1.3 (Euler’s Theorem):Let n ≥ 2. If gcd (a,n)= 1 then a ( n )  1 (mod n). A proof can be found in [31]. 1.4. Computational Primitives:Number theory is the source of several computational problems that serve as primitives in the design of cryptographic schemes. The security of many cryptographic techniques depends upon the hardness (intractability) of a certain computational problem.

9

Here we define only two computational problems namely “Integer Factorization”, “Discrete Logarithm” problems, which are the most widely – used computational problems in pubic key cryptographic schemes. 1.4.1. The Integer Factorization Problem:The problem of Integer Factorization Problem is one of the oldest in number theory and the advent of computers has stimulated considerable progress in recent years. This section focuses on the current knowledge on algorithms for Integer Factorization Problem. The integer factorization problem can be informally defined as follows: e e e “Given a positive integer n, find its prime factorization, that is, write n = p1 1 . p 22 ... p nn where pi

are pairwise distinct primes and each ei ≥ 1 ”. This problem is believed to be hard for general n, where n is large. Some ingenious methods have been devised in an attempt to factorize large composite numbers n. The three methods that are most effective on very large numbers are the quadratic sieve, the elliptic curve method and the number field sieve. Other well known methods that were precursors include pollard’s ρ-method and P-1 method, William’s P+1 method, the continued fraction algorithm, and of course, trial division. A good overview of factoring methods can be found in [17]. We remark that the integer factorization problem and its related computational problems were used to build up various cryptographic schemes such as RSA [29], Rabin [30], Okamoto and Uchiyama [22] and Paillier [26]. 1.4.2. The Discrete Logarithm Problem :-

10

Another widely used computational problem is the Discrete Logarithm Problem. Let G be a finite cyclic group of order n with generator g. For a more concrete approach, one may find it convenient to think of G as the multiplicative group of integers modulo p (for p prime). Definition 1.20:-

Let G be a finite cyclic group of order n. Let g be a generator of G, and

y ∈ G. The Discrete Logarithm of y to the base g, denoted by log g y is the unique integer x, 0≤ x ≤n-1, such that y = g x . The Discrete logarithm problem, which we simply call the “DLP”, can be informally defined as follows: Definition 1.21:-

* * Given a prime p, a generator g of Z p , and an element y ∈ Z p find the

integer x, 0 ≤x ≤ p-2 such that y = g x mod p. As in the case of factorization, efficient techniques exist for solving the discrete logarithm problem when the group G has a particular structure, an example of such a technique being the Polling – Hellman algorithm [27], which efficiently computes discrete logarithms when the group G has order n = p1a1 . p 2a2 ... p rar where p1 , p2 ,...., pr are primes less than or equal to a small bound B. A good overview of techniques for calculating discrete logarithms can be found in [18]. 1.5. Cryptographic Schemes:-

11

The word cryptology stems from Greek meaning “hidden word”, and is the umbrella term used to describe the entire field of secret communications. Cryptology splits into two subdivisions: Cryptography and Cryptanalysis. Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, data origin authentication and non-repudiation. The cryptanalyst seeks to undo the cryptographer’s by breaking cipher or by forging coded signals that will be accepted as authentic. General information on cryptography can be found in [19], [36] and [35]; the cryptography can be divided into the areas of symmetric-key cryptography and public-key cryptography. We will pay particular attention to PKC. Thus, we give formal definition of a cryptosystem. Definition 1.22:-

A Cryptosystem is a five-tuple (M,C,K,E,D), where the following

conditions are satisfied. 1. M is a finite set of possible plaintexts or messages.

2. C is a finite set of possible ciphertexts or cryptograms 3. K is a finite set of possible keys. 4. For each k ∈ K, there is an encryption rule Ek ∈ E and a corresponding decryption rule

Dk ∈ D. Each Ek : M → C and Dk : C → M are functions such that Dk(Ek(m))=m for every message m ∈ M.

12

The main property is of property 4. It is the property that enables a user to decrypt a received ciphertext, since Dk(Ek(m)) = m for all messages m ∈ M. For unambiguous decryption it is obviously required that Ek(m1) ≠ Ek(m2) if m1≠ m2. Otherwise if Ek(m1) = Ek(m2) if m1 ≠ m2, decryption is not unique, and therefore it is not possible for a user to decide whether the intended message was m1 or m2 upon receipt of Ek(m1) = Ek(m2).

1.6. Classical Cryptosystems (Symmetric-Key Cryptosystems): The classical goal of cryptography is privacy: two party (sender S and receiver R) wish to communicate privately, so that an adversary knows nothing about what was communicated. A standard cryptographic solution to the privacy problem is classical cryptosystems. Classical cryptosystems provide secure communication for a pair of users. In classical key cryptosystem, the encryption key can be calculated from the decryption key and vice versa. In most cryptosystems, the encryption key and decryption key are the same. These cryptosystems, also called secret key cryptosystems, single key cryptosystem, or one key cryptosystems, require that the sender and the receiver agree on a key before they can communicate securely. The security of the classical key cryptosystem rests in the key; divulging the key means, that anyone can encrypt and decrypt the messages. As long as the key remains secret, the communication remains secret. Classical Cryptosystem Consists of the following:•

A plaintext space P of all possible plaintexts P.

13

•

A ciphertext space C of all possible ciphertexts C.

•

A key space K in which each K determines an encryption algorithm Ek and a decryption algorithm Dk such that Dk(Ek(P)) = P; where P ∈ P.

Secret Channel

ChannelCh Key

S

Plaintext

Key

Encryption

Ciphertext

Decryption

Plaintext

R

Intruder Fig – 1: Classical Cryptosystem

Using symmetric cryptosystem, it is safe to send encrypted message without fear of interception because an interceptor is unlikely to be able to decipher the message; 14

however, with this advantage, symmetric cryptosystems also have the following problems: •

Sender and receiver share a common secret key, which must be transmitted before an encryption procedure can start.

•

There is always a problem of how to transfer the common secret key. How do you send the secret key from the sender to the recipient securely? If you could send the secret key securely, then, in theory, you would not need the symmetric cryptosystem for your communication?

•

Classical cryptosystems are unable to deal the dispute between the sender and receiver, as to what message, if any was sent. In classical cryptosystems, third party cannot verify who actually send the message. Because the secret key is common, however the receiver has the ability to produce any ciphertext that could have been produced by the sender.

•

Key management is the major problem in classical cryptosystem. In classical cryptosystems, every pair of users has to have an exclusive secret key; n users need n.(n-1)/2 different keys. The following fig shows the key management of the Six users A, B,C,D,E and F in classical cryptosystem.

15

A F

B

E D

C

Fig – 2 : Key Management in Classical Cryptosystem

•

We can achieve authentication and message integrity by using classical cryptosystems, but no one other than the receiver can check the message integrity and authenticity of the message.

1.7. Public Key Cryptosystems:Keeping in view the above drawbacks of classical Cryptosystems and to answer all the question, Whitefield Diffie and Martin Hellman proposed in 1976, a new type of cryptosystem which is called now, as public key cryptosystem [PKC]. The invention of public key cryptography is the most important event in the field of cryptography and provided answers to all the above problems of key managements and digital signatures. A public key cryptosystem is a pair of families {Ek} and {Dk}, K ∈ key space K of algorithms representing invertible transformations. Ek : P → C and Dk : C → P.

16

•

For every K, Ek is the inverse of Dk.

•

For every K, it is easy to compute Ek and Dk.

•

For almost every K, each easily computed algorithm equivalent to Dk is computationally infeasible to derive from Ek.

•

For every K, it is feasible to compute inverse pairs Ek and Dk from K.

Sender

P C

Receiver

C P

Encryption

Transmission

Decryption

Fig-3 : Public Key Cryptsystem

Because of the third property, the encryption key Ek of each user can be made public without compromising the security of his private decryption key Dk. The public key cryptographic system is therefore split into two parts, a family of encryption transformations and a family of decryption transformations in such a way that, given a member of one family, it is infeasible to find the corresponding member of the other.

17

The fourth property guarantees that there is a feasible way of computing corresponding pairs of inverse transformations when no constraint is placed on what either the encryption or decryption transformation is to be. In this cryptosystem, there is no need to send the secret key via secure channel. Every user A in the system has one pair of keys, a public key EKA for encryption and private key DKA for decryption. All public keys are publicly available; they might be stored in public file, as in a phone book. On the other hands, the private keys are kept secret; only the owner knows them. Of course, the user B’s public key EKB should not compromise the secrecy of the private key DKB. This important property is guaranteed by the idea of a trapdoor one-way function which can be informally defined as follows. Definition 1.23:

One-way function:

A one way function is a function f: X → Y such that for each x ∈ X (domain), it is easy to compute f(x); but for all y ∈ Y (range), it is computationally infeasible to find any x such that y = f(x). Definition 1.24:

Trapdoor One-way function:-

A trapdoor One-way function is a one way function f with the additional property that gives some extra information (called the Trapdoor Information), it becomes computationally feasible to compute an x for any y ∈ Y such that y = f(x). Let us now suppose that we have a public key cryptosystem. Consider the user A wants to send the message m to B. The process works as follows. 18

•

A looks up the pubic key EKB of B, encrypts the message m as EKB( m ) = C and send the ciphertext C to B.

•

B is able to decrypt the ciphertext C, since he exclusively knows the key DKB. He gets m = DKB (EKB(m)).

•

No other user can decipher EKB (m), since one can recover DKB from EKB and EKB (m).

Public Key Cryptosystem has the following noteworthy advantages. •

No secret key exchange among the users. Every user needs relatively few keys.

•

New user can join the system without disturbing the old users.

•

Communication in a secure way over the open channels for peoples who have never met.

•

Digital signature schemes.

Some well-known public key cryptosystems are described below: 1) RSA Public Key Cryptosystem (2) ElGamal Public Key Cryptosystem. 1.7.1 RSA Public Key Cryptosystem In 1977, three people who were to make the single most spectacular contribution to the public key cryptography: Ronald Rivest, Adi Shamir and Leonard Adleman took up the challenge of producing a full-fledged public key cryptosystem, which is called as RSA cryptosystem[29].

19

RSA cryptosystem is based upon the difficulty of factorization of two large primes. In this cryptosystem, we assume there is a key center. The key center •

Generates two large distinct prime p and q , each roughly of the same size.

•

Calculates n = p.q and  (n) = (p-1).(q-1).

•

For every user, selects randomly, integer; l<e<  ie gcd(e,  (n))=1

•

Computes d, the multiplicative inverse of e (mod φ (n) ), by Euclidean algorithm. The pair (e,n) is the public key or the encryption key and the pair (d,n) is the

secret key or the decryption key of the user A. If a user B encrypts a message m for the user A, then B should do the following: •

Represents the message as an integer in the interval [0, n-1].

•

Computes C= me mod n.

•

Sends the ciphertext C to the user A.

•

A recovers the message m by computing Cd mod n, using his secret key d.

1.7.2. ElGamal Cryptosystem:In 1984,Taher ElGamal [8] proposed a cryptosystem based on the difficulty of finding discrete logarithm. This cryptosystem can be based on family of groups for which the discrete logarithm is considered intractable. Usually a subgroup Gq of order q of Z p ,where p is a

20

large primes satisfying q / p  1 .We present the construction in the group Z p ,where p is a large prime. Key generation : The receiver B chooses large prime p and a generator g of the multiplicative * group Z p of the integers modulo p. B also selects a random integer  ,1    p  2 , and

computes h  g  .He publicizes his public key PK B  ( p, g , h) while keeps his private key SK B   Encryption : Using B’s public key PK B , the sender A encrypts her message m, (0  m  p ) for B. A does the following : Select a random integer k , 0  k  p  2 ,computes x  g k , y  m.h k and send this ciphertext C  ( x, y ) to B. Decryption : Upon receiving the ciphertext C from A, B decrypts it by using his private key

SK B (  ) and recovers the plaintext m by computing m 

y . x

1.8. Digital Signatures:We use physical signature in common practice for authentication. As we move to the world where our decisions and agreements are communicated electronically, we need to replicate these procedures. Public Key Cryptography (PKC) provides mechanisms for such procedures through digital signature schemes. In order to establish the authenticity of the 21

electronic message before a message is sent out, the sender of the message would sign it using a Digital Signature Schemes (DSS) and then encrypt the message using encryption algorithm. Thus, a digital signature scheme proves the authenticity of the message as well as the authenticity of the sender. A digital signature scheme is one of the most important cryptographic tools in PKC, essential in various security services. Digital signatures have the same role for the digital message that the handwritten signatures have for documents on paper. A digital signature scheme consists of the following. 

A key generation algorithm ,which is a method to produce public key and private keys.



A signature generation algorithm, which is a method of producing a digital signature.



A signature verification algorithm, which is a method for verifying a digital signature. The crucial difference from a hand written signature is that the digital signature

is a data string which intimately connected with the message with some originating entity, whereas the handwritten signature adjoined to the message and always looks the same. Consequently, no one can alter the digital signature without everyone being able to see that the document has been changed. Thus, the digital signature ensures the integrity of the signed document. For, the digital signature is altered at all, and then the application of the public key to the altered signed message yields a plaintext, which will appear very random. This property of the digital signature implies that the signature is not reusable and unforgeable. Nobody, except the signer can sign a document. Hence, the recipient is convinced that the signer deliberately signed the document. The digital signature ensures the authenticity of the signer.

22

Finally, these two properties (unforgeability and authenticity) ensure the non-repudiation of the signature. The signer cannot deny later that he did not sign the message.

Not reusable

Signer

Message

Integrity

Non-repudiation

Unforgeable

Authenticity

Fig – 4 : Properties of Digital Signature The ability to construct a digital signature scheme is a great advantage of Public key cryptography over symmetric cryptography. 1.8.1 The RSA Signature Scheme:The RSA signature scheme was the first digital signature scheme with message recovery. RSA digital signature scheme is one of the most practical and versatile techniques available. The message space, signing space, signature space and ciphertext space for this scheme belong to Zn = {0,1,2,…, n – 1} where n = p.q is the product of two randomly chosen large prime numbers. To signs a message m ∈ M

•

Any user A computes m* ∈ ξ (m).

•

Applying his secret key d, he computes s* = (m*) d mod n.

•

The number s* is the signature of the user A for the message m.

23

To verify the signature s* and to recover the message m. •

Any user B applying the public key e of the user A computes m* = (s*)e mod n.

•

Verify that m* ∈ M ξ ;if not reject the signature.

•

B recovers the message m = ξ −1 (m*)

1.9 Security:The primary goal of cryptography is to keep the plaintext secret, from the eavesdroppers trying to get some information about the plaintext. Adversaries may also be active and try to modify the message. Then, cryptography is expected to guarantee the integrity of the message. Over the years, many different types of attacks on cryptographic primitives and protocols have been identified. The objective of the following attacks is to systematically recover plaintext from ciphertext or even more drastically, to deduce the decryption key.: 1. A cipher text – only attack is one where the adversary (or cryptanalyst) tries to deduce the

decryption key or plaintext by only observing ciphertext. Any encryption scheme vulnerable to this type of attack is considered to be completely insecure. 2. A known-plaintext attack is one where the adversary chooses plaintext as the given

corresponding ciphertext. This type of attack is typically only marginally more difficult to mount.

24

3. A chosen-plaintext attack is one where the adversary has a quantity of plaintext and

corresponding ciphertext. Subsequently, the adversary uses any information deducted in order to recover plaintext corresponding to previously unseen ciphertext. 4. An adaptive chosen-plaintext attack is a chosen-plaintext attack wherein the choice of

plaintext may depend on the ciphertext received from previous requests. 5. A chosen – ciphertext attack is one where the adversary selects the ciphertext and is then

given the corresponding plaintext. One way to mount such an attack is for the adversary to gain access to the equipment used for decryption. The objective is then to be able, without access to such equipment, to deduce the plaintext from different ciphertext. 6. An adaptive chosen – ciphertext attack is a chosen – ciphertext attack where the choice

of ciphertext may depend on the plaintext received from previous requests.

Semantic security : The semantic security notions of PKC was introduced by Goldwasser and Micali [9] and is defined as follows. A public key encryption scheme is said to be semantically secure if, for all probability distributions over the message space, whatever a passive adversary can compute in expected polynomial time about the plaintext gives the ciphertext, it can also compute in expected polynomial time without the ciphertext.

25

Inventively, a public key encryption scheme is semantically secure if the ciphertext does not leak any partial information whatsoever about the plaintext can be computed in expected polynomial time.

CHAPTER II Introduction: The idea of Public Key Cryptosystem [PKC] was introduced by Diffie and Hellman in 1976; many PKC schemes have been proposed and broken. The trapdoor one way functions play the key role in the idea of PKC. Today, most successful PKC schemes are based on the perceived difficulty of certain computational problems. For eg. Difficulty of solving the Integer Factorization Problem depend over the ring zn (where n is the product of two large primes) forms the ground of the basic RSA Cryptosystem. However, the efficiency and security are two important goals for any cryptosystem. The details about all kinds of attacks and security notions can be found in [1]. Goldwasser and Micalli [9] introduced a security notion, namely semantic security. The standard RSA [29] was not semantically secure. Later, in 1994, Bellare and Rogaway

[2] presented some variants of RSA, which were semantically secure against chosen

ciphertext attack. In Pointcheval scheme [28], small exponent e cannot be used for the security point of view because of the related massage attack. After the appearance of the RSA cryptosystems, many mathematicians and cryptographers have become interested in finding another suitable structure for PKC, and many PKC have been proposed. Koblitz[ ] and Miller [ ] independently proposed the Elliptic curve cryptography, a method of utilizing a DLP over the

26

points on an elliptic curve. In the same direction, Koyama and Koyama et. al. have constructed three different PKCs analogue to RSA based on singular cubic curves. 2.1 Contributions of the chapter: In this chapter we discuss some basic facts about the singular cubic curve over a finite field Fp and over the ring Z n .We review three RSA type cryptosystems proposed by Koyama et al. based on singular cubic curves over Z n . Also we address some of the attacks which are possible in the Koyama scheme. 2.2 Singular Cubic Curve: In this section we discuss some basic facts about singular cubic curve over the finite field Fp

and over the ring

Zn

, where n is the product of two distinct odd primes greater than 3.

2.2.1. Singular Cubic Curves Over F p Consider the congruence equation solutions Fp

of

 x, y   Fp  Fp

to (1) denoted by

be a finite field with p elements and Fp*

denoted by #

Fp*

y 2  axy  x 3  bx 2 mod p   1

C p  a, b 

27

The set of all

is called singular cubic curve over

be the multiplicative group of

Fp*  p  1.

.

Fp

Fp

where

. Clearly the order

A non singular part of a singular cubic curve, denoted by solutions

 x, y   Fp  Fp

C p (a , b )

,is defined as the set of

to equation (1), excluding a singular point (0,0), but including the point

at infinity, denoted by O. An addition

on



is given by the chord –and– tangent law similar to that for

C p (a , b )

elliptic curves. 

The sum

x3 , y3  of



x1 , y1  and



x2 , y2  in Fp

is computed as follows.

x3   2  a  b  x1  x2 y3    x1  x3   y1

(2)

where  y2  y1  x x  2 1

if ( x1 , y1 )   x2 , y2 

2  3x1  2bx1  ay1  2 y1  ax1

if  x1 , y1    x2 , y2 

 

Note that

C p  a, b 

The multiplication

is a finite abelian group. [11], [34].



C p  a, b 

on

is defined by

6 4 4 4 44 7 4 4 4 4 4 8 k   x, y    x, y    x, y   .....   x, y 

A group

C p  a, b 

is isomorphic to

and [20] for the curves



y  x



Fp*

(

k

times) over

C p  a, b 

.

. The isomorphic relationship is generally described in [11]

y   x   x 3 over Fp ,

28

where

 ,   Fp ,

which is equivalent to

equation

(1)

with

a     mod p

  0 and    a   0  ,

,

we

b   mod p. When b  0

can

put

and the simplified relationship is carried out explicitly in the following

theorem. * Theorem 2.1: The mapping  : C p  a, 0   Fp defined by

 : O  1 and  x, y   1 

 1 : Fp*  C p  a, 0 

a group isomorphism. The group isomorphism mapping



a 2v 

 v  1

 1 :1  O and v   

Hence an order of

2

,

C p  a, 0 

3



# C p  a, 0   p  1

Cn  a , b  ,

over p

Zn

a, b  Z n ,

or (0, 0) mod Cn  a , b 

,q

Z n   1, 2, 3,....n  1 and Z n*

. A non singular part of a singular cubic curve over

is defined as the set of solutions , where

.

Zn

Let n be the product of two large primes p and q (>3) and Zn

is defined by

. 

is denoted by

2.2.2. Singular Cubic Curves over

multiplicative group of

is



a 3v

 v  1

ax x3  2 y y

 x, y   Z n  Z n

to the equation

Zn

be a

denoted by

y 2  axy  x 3  bx 2

excluding a singular points which are either congruent to (0, 0) mod

but including a point at infinity O. By Chinese Remainder Theorem,

is isomorphic to

C p ( a, b)  Cq ( a, b)

. An addition operation on

chord and tangent method.

29

Cn  a , b 

is defined by

Although the addition is not always defined, the probability of such a case is negligibly small for large p and q.

By Theorem2.1 and Chinese Remainder Theorem the following

Theorem holds. Theorem 2.2 [ ]: For



x1 , y1  and  xi , yi

i

1



satisfying



xi , yi   i   x1 , y1 

over

Cn  a , 0  ,

we have

i

axi  ax    1  1   mod n  , i.e yi y1  

xi  x1     mod n    3 yi  y1 

2.3. RSA type schemes based on singular cubic curves:Singular cubic curve was first used by Koyama for the construction of RSA type PublicKey Cryptosystem. Koyama and Koyama et al. [13,14,16] have constructed three different Public Key Cryptosystems analogue to RSA over singular cubic curves. Three RSA type schemes based on singular cubic curve over

Zn

are proposed as follows.

Scheme I [16]: This

cryptosystem

is

based

Cn  0, b  : y 2  x 3  bx 2  mod n    4 

encryption key

e

chosen

p, q

where

such that

decryption key d is chosen such that private keys are

on

the n  p.q

 e, N 

singular

curve

of

the

form

is the product of two large primes. The

 1 where N  l cm  p  1, p  1, q  1, q  1 .

ed  1 mod N .

The

The public key is the pair (n, e) and the

and d. To encrypt a plaintext pair

30

cubic

M   mx , m y  ,

the sender first computes

b

m 2y  mx3 mx2

 mod n 

Cn  0, b  .

on the singular cubic curve

The complete ciphertext is (

 m ,m 

The receiver, who knows the decryption key d, can get the plaintext d   cx , c y    mx , m y 

over the singular cubic curve

x

y

C, b

).

by computing

Cn  0, b  .

Scheme II [14]: This cryptosystem is based on the singular cubic curve of the form: Cn

 a, 0 

 y 2  axy  x 3  mod n   (5) where n  pq

is the product of two large primes.

The encryption key e is chosen such that  e, N   1 where N  lcm( p  1, q  1). The decryption key d is chosensuch that ed  1mod N . The public key is the pair (n, e) and the private keys are d, p and q. To encrypt a plain text pair

a

mx3  m3y

curve

mx my

 mod n 

Cn  a , 0 

and then the ciphertext is computed as

. The complete ciphertext is (

C, a

d can get the plaintext  mx , m y  , by computing curve

C n  a, 0 

M   mx , m y 

, the sender first computes

on the singular cubic

C  eM

). The receiver who knows the decryption key d ⊗(c x , c y

) =(m

x

, my

)

over the singular cubic

.

Scheme III [13]: The cryptosystem is based on the singular cubic curve of the form:

31

Cn   , 







y  x



y   x   x 3  mod n   (6) where n  pq

large primes. The encryption key

e

is chosen such that (e, N) = 1 where N =

The decryption key d is chosen such that

randomly and computes

C  eM



mx3  m 2y   mx m y mx   mx  m y 

on the singular cubic curve

M   mx , m y  ,

 mod n 

Cn   ,   .

over the singular cubic curve

the sender first chooses

then the ciphertext is computed as

The complete ciphertext is

receiver, who knows the decryption key d can get the plain text d   c x , c y    mx , m y 

l cm ( p  1, q  1).

The public key is the pair (n, e) and the

ed  1 mod N .

private keys are d, p and q. To encrypt a plaintext pair



is the product of two

 C, ,   .

The

 m , m  by computing x

y

Cn   ,   .

Seng et al. [5] have given the following two equivalence relations for the schemes I, II and III mentioned above.

Reduction of Scheme II to Scheme I: - The transformation

the curve

C n  a, 0 

to the curve

Cn  0, b  with b  4a 2

Scheme II to Scheme I.

32

 x, y    

x, y 

a 2

 x 

will transform

. Using this transformation one can reduce

Reduction of Scheme III to Scheme I: - The transformation

Cn   ,  

transform the curve

      x, y  x 2  

will

2

Cn  0, b 

to the curve

 x, y 

with

    . 2  

b

Using this

transformation, one can reduce scheme III to scheme I. 2.4. G-RSA Cryptosystem:Kouichi et al. generalized the S-Paillier [4] and D-RSA [28] cryptosystem which enhanced the RSA cryptosystem to be semantically secure using one way function f where f is a function

encrypted by

Z*n

This is known as G-RSA cryptosystem. In this cryptosystem, a message m is

Zn  Zn .

c

0

 r e  mod n  , c1  f

 r

. The ciphertext is decrypted by computing

by computing

m

c

1

 f ( r )  c01



 mc0  mod n  ,

where r is randomly chosen element of

r  c0d  mod n 

first and then plaintext is obtained

  mod n  .

Let OW be a class of one way function

f : Zn  Zn.

The one way-ness assumption of G-

RSA cryptosystem is that, for any probabilistic polynomial time algorithm

AGOW  RSA ,

the

OW  mc0 mod n : AG  RSA

 c0 , c1 

probability PrrR zn 

 n, e 

 RSApublic , f  OW , r  R zn* , c0  r e mod n, c1  f

is negligible in log n.

33

 r

 1

A semantic security adversary stage

AGSS1RSA

and the guess stage

AGSS2RSA

AGSS RSA

against the G-RSA cryptosystem consists of the find

. The semantic security of G-RSA cryptosystem is that, for

any probabilistic polynomial time algorithm

AGSS RSA ,

the probability

  n, e   RSApublic , f  OW ,  m0 , m1 ,8t   AGSS1RSA  e, n  , b   1,1 , r  PR Z n* , 

2 Pr 

SS e  c0  r mod n, C1  f  r   mb c0 mod n; AG 2RSA  c0 , c1  , m0 , m1 , st  b

 1 

is negligible in log n. Kouichi et al. defined two problems called C-RSA+OW problem D-RSA+OW problem, in order to investigate the security of G-RSA cryptosystem based on a one way function

f : Zn  Zn.

The computational C-RSA+OW problem is to compute the value of f(r) for given RSA public key (e,n) and the random ciphertext

c0  r e  mod n 

C-RSA+OW Assumption: For any probabilistic polynomial time algorithm Prr

* R Zn

AC  RSAOW ,

the probability

[(n, e)  RSApublic , f  OW , c  r e mod n; AC  RSAOW (c)  f (r )] is negligible in log n.

The decisional version of C-RSA+OW problem is to distinguish whether an element ( x, y )  Z n  Z n comes from the distribution (r e mod n, f (r )) for r  Z n* .

34

D-RSA+OW Assumption: For any probabilistic polynomial time algorithm AC − RSA+OW , the probability Pr[( x, y )  Z n  Z n : AD  RSAOW ( x, y )  1]  Pr[r  Z n* , x  r e mod n, f  OW , y  f (r ) : AD  RSAOW ( x, y )  1 is negligible in log n. Following two theorems proves the one way-ness and semantic security of G-RSA cryptosystem. Theorem2.3: The encryption function of G-RSA cryptosystem is one-way if and only if the C –RSA+OW assumption. Theorem2.4: The G-RSA cryptosystem is semantically secure if and only if the D-RSA+OW assumption holds. 2.5. Security Analysis : The schemes proposed by Koyamma et.al., are not semantically secure and also not secure against low exponent attack, related message attack and partially known plain text attack. we discuss how these attacks are admissible in the Koyama’s schemes are described in section 3.4.

35

CHAPTER III The schemes proposed by Koyama [14] and Koyama et al.[13,16] which are described in chapter II are not semantically secure and also are not secure against low exponent attack[15], related message attack [5,23]and partially known plain text attack[3,24].It is therefore natural to curb said above three security weakness within the Koyama schemes[13,14,16]. With this purpose, we propose an RSA type public key cryptosystem based on the singular cubic curve

Cn  0, b  : y 2  x 3  bx 2  mod n  by following the line of Sahdeyo Padhya et al [25].The security of the scheme is based on the RSA problem, more precisely on the difficulty of factoring n, which is a product of large primes p and q. 3.1. Contributions of the chapter: * In this chapter, first we define an isomorphism from Cn (o, b) to Fp and then we propose

an RSA type PKC over the singular cubic curve Cn (o, b) . We present an example of the proposed scheme. Finally we discuss the efficiency and security of the proposed scheme. 3.2. Proposed Scheme:In this section we propose a public key cryptosystem based on the singular cubic curve

Cn  0, b  : y 2  x 3  bx 2  mod n  . First we define an isomorphism from

C p  0, b  to Fp*

36

and inverse of that are as follows:

Theorem 3.1: - The mapping

 : C p  0, b   Fp*

defined by

a group isomorphism. The group isomorphism mapping



b3v



 v  1

b ,  v 1

 1 :1  O and v  

 3

  

and

 :O 1

 x, y   1 

 1 : Fp*  C p  0, b 

b y2  x x3

is

is defined by

. By using Theorem 3.1 and Chinese Remainder Theorem,

the following theorem holds.  x1 , y1 

Theorem 3.2: - For

and  xi , yi 

satisfying



xi , yi   i   x1 , y1  over Cn  0, b 

, we have

i

b  b 1    1   (mod n) xi  x1  .

Now we propose a semantically secure encryption scheme over the singular cubic curve Cn  0, b 

. The security of the proposed scheme is based on the RSA problem, more precisely on

the difficulty of factoring n, which is the product of two large prime p and q. Let a plaintext  m ,m  x

y

be an integer pair, where

plaintext  m , m  to x

y

Z*n

mx , m y  Z n* and mx3  m y2  mod n  .

First we transform the

and then encrypt the isomorphic image of  m , m  . x

y

Key Generation: To generate keys, receiver R selects two large primes p, q and computes

37

n = pq. Receiver determines an integer computes

dp

and

dq

such that

less than

e



and

gcd  e,   n    1

d p  e 1  mod p  1 and d q  e 1  mod q  1 .

d

public key is (e, n) and the secret key is

p

, d q , p, q  .

. He then

Now the R’s

More over a one way function

is used as a system parameter.

f : Z n*  Z n*

Encryption: M   mx , m y  ,

To encrypt the message pair r  Z n* and sends the ciphertext

 c0 , c1 , c 

sender S, first chooses a random integer

to the receiver R with the receiver’s public key (e, n)

where 1)

c0  r e mod n

2)

 my2  c1  f  r    c mod n.  m3   0 x  

3)

b

4)

c  b  r 2 mod n.

m 2y  mx3 mx2



.

mod n

.



The complete ciphertext is

 c0 , c1 , c 

. It is clear that the ciphertext does not belong to any

corresponding point on the singular cubic curve

Cn  0, b 

information about the plaintext.

38

. Also the ciphertext c does not leak any

Decryption: The receiver R computes the original plaintext by using his/her secrete key after getting  c0 , c1 , c 

the ciphertext

1)

d

as below:

d

rp  c0 p mod p and rq  c0 q mod q.

By the pair  r , r  p

q

and via

Chinese Remainder Theorem, compute the value of r. 



2.

b  c  r 2 mod n.

3.

m

m y2 mx3

mod n   c1  f  r   c01 mod n.

Now by using the isomorphism mapping for singular cubic curve defined above he/she then

computes the original plaintext  m , m  by x

y

mx 

b mod n v 1

and

my 

b3v

 v  1

3

mod n

.

3.3. Example: Following is a very simple example to understand our proposed cryptosystem. Let

p  5, q  11  n  55,   n   40

Key Generation: - Let

e  3, d p 

Let the plaintext pair = (2, 3) i.e.

1 1  mod 4   3 and d p   mod10   7 3 3

mx  2 and m y  3

39

Encryption: To encrypt the message pair (2,3), the sender S chooses the parameter

r  7,

then proceeds as follows. 1.

co  7 3 mod 55  13

2.

c1  f  7   

3.

b

4.

c   14  49  mod 55  8.

 32 3  2

.



 13 mod 55  f  7   49. 

32  23 mod 55  14. 22

Sender sends the complete ciphertext  13, f  7   49, 8  to R. Decryption: To get the plaintext after having the ciphertext, R proceeds as follows: 1.

rp  133 mod 55  2 and rq  137 mod11  7.

By the pair  r , r  and via Chinese

Remainder theorem, R computes the value of 

p

q

r  7.



2.

b  8  7 2 mod 55  14.

3.

m

m y2 mx3

mod n   f  7   49  f  7   131 mod 55  8.

original plaintext  m , m  x

y

by mx 

He/she than computes the

14 143  8 mod 55  2 and m y  mod 55  3. 8 1 73

3.4. Security & Efficiency Analysis:

40

he/she

In this section , we prove that our scheme is semantically secure and how the above said attacks are not possible in our scheme is described as follows. Semantic Security: The proposed cryptosystem is semantically secure against chosen plaintext attack in the Decisional GRSA problem is as follows. In order to determine any information f  r

about the plaintext m from the ciphertext, attacker need to have some information about mod n where r is randomly chosen element in f  r   mod n 

about the value of information about information about

Zn*.

The only way to ascertain any information

is to first compute r (it is not sufficient to compute some partial

it is necessary to have complete information about r in order to obtain any

r;

f  r   mod n 

, as r is randomly chosen). It is not possible without knowing

the secret key d or solving the G-RSA problem. Also, in the Koyama scheme the message dependent variable b gives some information about the plaintext, but, in the proposed scheme we keep it secret which is known by the authorized receiver only. Without knowing the value b attacker neither uses Theorem 3.1 nor the addition operation over the exact singular cubic curve. Secure Against Partially Known Plaintext Attack. In the Koyama scheme, knowing one ordinate

mx or my

in a plaintext pair

 m ,m  x

one

y

can compute the whole plaintext under with the help of corresponding ciphertext. In brief, the attack is as follows. Let

plaintext

n, e

be a public key for scheme [16] and

M   mx , m y 

, i.e.

e   mx , m y    c x , c y 

41

C   cx , c y 

. Assume that

be the encryption of the

mx

is known and

my

is

unknown. Let

. Then we compute

my  y

eM

2 3 over Z [ y ] /  y  mx  bmx , n  by using the

addition law of singular cubic curve. For the Koyama scheme, by induction technique, it can be shown that for any Finally, for

of order 2 in

Zn ,

k   mx , y    uk , vk y 

ve  0  mod n 

if

Cn  0, b 

. However, if

, which means that

where

 ue , ve y 

, we get the relation

k e

y  c y ve1  mod n 

in

k

uk

and

  cx , c y 

ve  0  mod n 

d  c  M , i.e. C  M

vk

are two positive integers.

which can be solved for then the ciphertext

C

is a point

hence M is always computable.

But, in our scheme, we hide the parameter b and the ciphertext is not a permutation of the plaintext pair

 m , m  on the same curve. Also, with the help of the ciphertext, none but the x

y

receiver can compute the addition parameter b. And hence he can’t use the addition operation. So, the attacker neither can use the above said transformation nor Theorem 3.1. Thus we conclude that the partially known plaintext attack is not admissible in our scheme. Security Against Linearly Related Plaintext Attack:The Koyama schemes [13,14,16] become insecure if two linearly related plaintexts are encrypted with the same public key [3,5,23]. In brief the attack is as below.

Let

relations:

M   mx , m y 

and



M '  mx' , m 'y

 be two plaintexts linearly related by the known

mx'   mx   m'y   m y   , where  ,  ,  ,   Z n* .

42

Assume that the encryption of the plaintexts  m , m  x

y

and

 m ,m  ' x

are given by

' y

(cx , c y )  e  ( mx , m y )(mod n) (cx' , c 'y )  e  ( mx' , m 'y )(mod n)



cn  0, b  andcn 0, b '

From the above ciphertext we can derive the curves

mx3  bmx2  m 2y  0  mod n  and

point must lie. Thus we have

  mx   

3

 b '   mx       m y     0  mod n  2

2

By the above two equations, we can write

  x 

x  

3

 upon which the





 b '   x      2 x 3  bx 2   2 2

2 

as a polynomial

my



in

mx

with

.

By using the addition formula on singular cubic curve, it is clear that

  mx   m y  mod n  . Now let 6.

Thus

f

 x

f  mx   0  mod n 

 x 3  bx 2    x 

on

2

 mod n 

Z  x  /  n, f

e   x,   x     h  x  , j  x   mod n over Z  x  /  n, f

 x 

h  mx   cx  mod n 

j  mx   c y  mod n 

43

.

 x 

.

which is a polynomial of degree

Next,

we

compute

Then we have following equations:

Finally, we compute k  x  mx 

m

x

. This gives us the plain text

, my   M ,

between

gcd  h  x   cx , f

 x 

which is a linear polynomial of the form

mx.

After knowing the half of the plaintext m y by   mx   m y .

we can compute the other half

M and M '

we can compute the plaintext

M'

Finally, by the linear relation

.

Again to apply such type attack, the knowledge of parameter b is necessary. In the proposed scheme we hide the parameter b, so that no one can apply the above attack in our scheme. It is therefore, our scheme is secure against linearly related plaintext attack. Security Against Low Exponent Attack:Finally, as the G-RSA [12] scheme is secure against low exponent attack, we assert that the proposed scheme is also secure against low exponent attack. Efficiency of the proposed scheme We consider the scheme [14] over the curve

Cn  a , 0 

to compare with our scheme for the

security analysis and show that the said above attacks not admissible in our proposed scheme. The decryption speed of the proposed scheme is faster than that of G-RSA scheme.

In the scheme given by Koyama, the

encryption

process.

Where

as,

et h

power of in

44

our

mx3 my2

under modulo n is computed during

proposed

scheme,

the

triples

like

r

e

mod n, f

 r  mod n, r 2 mod n 

are computed well in advance.

Because of this pre-

computation, the encryption process requires only two multiplications and one addition modulo n. This feature makes the encryption process more efficient than the scheme given by Koyama, although, our decryption process remains approximately as efficient as the scheme given by Koyama.

CHAPTER IV Conclusions

45

References: 1) M.Bellare, A.Desai, D.Pointcheval, and P.Rogaway, “Relation among notions of security

for public key encryption schemes,” in Cryto’98, LNCS 1462, pp26-45, Springer Verlag, 1998. 2) M.Bellare and P.Rogaway, “Optimal asymmetric encryption – how to encrypt with

RSA,” in Eurocrypt’94, LNCS 950, pp 92-111, Springer Verlag, 1995.

46

3) D.Blichenbacher, “On the security of KMOV public key cryptosystem,” in Crypto’97,

LNCS 1294, pp.235-248, 1997. 4) D.Catalano, R.Gennaro, N.Howgraw-Crahan, and P.Nguyen, “Paillier’s cryptosystem

revisited,” in ACM Conference on Computer and Communication Security, pp. 206-214,2001. 5) S.K.Chua, K.H.Leung, S.Ling, “Attack on RS-type cryptosystem based on singular cubic

curves over Z/nZ*,” Theoretical Computer Science, vol.220, pp. 19-27,1999. 6) W. Diffie, “The first ten years of Public Key Cryptography”, in Contemporary

Cryptology: The Science of Information Integrity, Editor, Simmons G.J. IEEE Press, New York. p.p 135-175,1988. 7) W.Diffie and M.Hellmann, “New direction in cryptography,” IEEE Transactions on

Information Theory, vol.22,pp. 644-654, 1976. 8) T.ElGamal, “A public key cryptosystem and a signature scheme based on discrete

logarithms,” IEEE Transactions on Information Theroy, vol.31, no.4, pp. 469-472, 1985. 9) S.Goldwasser and M.Micali, “Probabilistic encryption,” Journal of Computer and

System Sciences, Vol.28, pp 270-299,1984. 10)L.Hill, “Cryptography in an algebraic alphabet”, American Mathematical Monthly – 36,

p.p.15-30,1929. 11)D.Husemaller, “Elliptic curves,” Graduate Text in Mathematics, Springer Verlag, 1987. 12)S.Kouichi and T.Takagi, “New semantically secure public key cryptosystems from RSA-

Primitive,” in PKC’2002, LNCS 2274, pp.1-16,2002. 13) K.Koyama and H.Kuwakado, “A new RSA-type scheme based on singular cubic curves ( y  ax)( y  bx)  x 3 (mod n) ,” IEICE Transactinos on Fundamental, Vol.E79-A,

47

pp. 49-53, 1996. 14)K.Koyama,

“Fast

RSA-type

schemes

based

on

singular

cubic

curves

y 2  axy  x3 (mod n) ” in EUROCYPT’95, LNCS 921, pp.329-340, Springer Verlag,1995.

15)K.Kurosawa, K.Kada, S.Tsuji, “Low exponent attack against elliptic curve RSA,

“Information Processing Letters, vol.53, pp. 77-83,1995. 16)H.Kuwakado, K.Koyama, Y.Tsuruoka, “A new RSA-type scheme based on singular

cubic curves y 2  x 3  bx 2 (mod n) ” IEICE Transactions on Fundamental, vol,E78-A, pp.27-33, 1995. 17)W.Mao, “ Modern Cryptography”, Theory and Practice, Prentice Hall,2004 18)O.M.Maurer, “ Towards the equivalence of breaking the Diffie-Hellman protocol and

discrete logarithms”.in Y.G.Desmedt editor, In advance in cryptology – CRYPTO’94, pages 271-281, Springer Verlag, 1994. 19)A.J.Menezes,

P.C.Van

Oorschot,

and

S.A.Vanstone,

“Handbook

of

Applied

Cryptography”, CRC Press, 1996. 20)A.Menezes,

“Elliptic

curve

public-key

cryptosystem”,

Kluwer

Academic

Publisher,1993. 21)I.Niven, H.Zukerman, and H.Mongomery, “ An introduction to theory of numbers”,

Wiley Publications, 1991. 22)T.Okamoto and S.Uchiyama, “ A New Public-key Cryptosystems as secure as

Factoring”, Advances in Cryptology – Proceedings of EUROCRYPT’98, LNCS 1403, Pages 308-318, Springer Verlag,1998. 23)S.Padhye,

“On

Security

of

Koyama

48

Scheme”,

eprint Archieve-2005/153,

http://eprint.iacr.org/2005/153.pdf. 24)S.Padhye, “Partial known plaintext attack on Koyama scheme,” Information Processing

Letters, vol.96, no.3, pp. 96-100, 2005. 25)S.Padhye and B.K.Sharma, “A Fast Semantically Secure Public Key Cryptosystem

Based on Factoring”, International Journal of Network Security, Vol.3, No.2, pp.144150, 2006. 26)P.Paillier, “ Public-Key Cryptosystems based on composite residuosity classes”,

Advances in Cryptology, Proceedings of EUROCRYPT’99, LNCS 1592, PAGES 223238, Springer Verlag,1999. 27)S.Pohlig and M.E.Hellman, “ An improved algorithm for computing logarithms over GF

(P) and its cryptographic significance”, IEEE Transactions on Information Theory, Vol.24, pages 106-110, IEE 1998. 28)D.Pointcheval, “New public key cryptosystem based on the dependent-RSA problem,” in

Eurocrypt’99, LNCS 1592, pp.239-254, 1999. 29)R.L.Rivest, A.Shamir, L.Adlemann, “A Method for obtaining digital signatures and

public key cryptosystem,” Communication of the ACM, vol.1, no.2 pp.120-126, 1978. 30)M.O.Rabin, “Digitalized Signatures and Publickey functions as intractable as

factorization”, MIT / LCS / TR-212, MIT Lab for Computer Science, 1979. 31)K.H.Rosen, “Elementary number Theory and its applications”, Wiley Publication, 1993. 32)C.E.Shannon, “A mathematical theory of communication”, Bell System Technical

Journal – 27(4), p.p. 379-423,1948. 33)C.E.Shannon, “Communication theory of secrecy systems”, Bell System Technical

Journal – 28(4), p.p. 656-715,1949. 34)J.H.Silverman, “The arithmetic of elliptic curve,” Graduate Text in Mathematics,

49

vol.106, Springer Berlin,1986. 35)G.J.Simmons , “Contemporary Crytography”, The Science of Information Intergrity,

IEEE Press, 1992. 36)D.R.Stinson, “Cryptography theory and practice”, CRC Press, 1995.

50