A nonlinear cryptosystem based on elliptic curves

A nonlinear cryptosystem based on elliptic curves* JOAN-JOSEP CLIMENT, FRANCISCO FERRÁNDEZ Departament de Ciència de la Computació i Intel·ligència Artificial Universitat d'Alacant Campus de Sant Vicent del Raspeig. Ap. de Correus 99, E-03080, Alacant SPAIN Abstract: - We propose a new system that is applicable to public key cryptography. The system is a variant of the Discrete Logarithm Problem (DLP) with the elements of a certain group, formed with points of an elliptic curve, and the elements of a certain finite field related to the curve. The nonlinear term refers to the coefficient that we use as the problem to solve because it is obtained with a nonlinear combination of two scalar elements chosen at random. Also, we expose the Diffie-Hellman key agreement protocol with this system act as the underlying mathematical problem. Key-Words: - Public key cryptography, elliptic curves, ECDLP, discrete logarithm problem, finite fields, DiffieHellman key agreement

1 Introduction The dramatical increase of the communications in last years requires the search of new cryptosystems more efficient and secure. Public key cryptography is the tool that provides the needed services in our World, where the digital communications is something usual. This system was born to interchange secret keys, and was devised by W. Diffie and M. Hellman in 1976 [3]. Nowadays it is used in many others applications, as information privacy, document signature, or person authentication. To make these services available is necessary to define mathematical problems that are applicable to public key cryptography, that is, problems whose direct computation is easy, but they are difficult to invert unless we have the secret key that makes this process easier. There are few problems in use that fulfill these characteristics. The more known ones are the Integer Factorization Problem (IFP), that consists of factorizing a huge number; and the Discrete Logarithm Problem (DLP), that consists of finding the logarithm of a huge number in a known base of a finite field. The IFP is the most used problem in Internet as the underlying problem of the well known system RSA. The DLP, less used, is the base of the DSS (Digital Signature Standard), digital signature scheme proposed some years ago as the standard for its use by North American governmental organizations. It is usually believed that both mathematical problems have the same “hardness”. This term determines the algorithm complexity or computational cost necessary to invert the problem without knowing the secret key. In 1985, it was introduced a third mathematical problem that increases dramatically the properties of the other ones, the Elliptic Curve Discrete Logarithm Problem (ECDLP); see [4],

[5] and [8]. It works in a similar way of the DLP, so its name. Consider a finite field Fq with characteristic greater than 3. An elliptic curve E over Fq is the set of all solutions ( x, y ) ∈ Fq × Fq to an equation

y 2 = x 3 + ax + b ,

where a, b ∈ Fq and 4a 3 + 27b 2 ≠ 0 , together with a special point O called the point at infinity. We denote the curve by E / Fq . It is well known that E / Fq with a binary operation, called addition of points and denoted by +, is an abelian group with O as the identity element. We denote the group by E ( Fq ) . The addition of points is defined as: Let be P = ( x1 , y1 ) ∈ E (Fq ) , then − P = ( x1 , − y1 ) . If

Q = ( x2 , y2 ) ∈ E (Fq ) , Q ≠ − P , then P + Q = ( x3 , y3 ) , with x3 = λ 2 − x1 − x2 y3 = λ ( x1 − x3 ) − y1 where ⎧⎪( y − y )( x − x ) −1 , if P ≠ Q λ = ⎨ 2 21 2 1 −1 ⎪⎩ (3 x1 + a )(2 y1 ) , if P = Q Defining the curve over a finite field with characteristic 2 or 3 is possible, but it is indifferent for our purposes. The ECDLP consists of the following: let be two points P, Q ∈ E (Fq ) , with kP = Q , determine the scalar k ∈ Fp , with p = # E (Fq ) . It is necessary that P be a generator of the group of points E ( Fq ) , or, at least, it generates a subgroup with similar number of points. It can be found more on elliptic curves in [1].

* This work was partially supported by Generalitat Valenciana grant number GV04B-462

The usual sizes for the private keys in the IFP or DLP are around 1024 binary digits. For a similar hardness in the ECDLP it is only necessary key sizes of 160 bits [6]. The reason is that it is known algorithms of subexponential order that solve the IFP or the DLP, as the Index-Calculus attack; but the fastest algorithms that solves the ECDLP are the square root algorithms, as the Pollard-ρ, of exponential order. These algorithms can always be applied to a group. An ECDLP with a hardness of 160 bits can be reduced to another one of roughly 80 bits, that is, the algorithm will require 280 iterations to break the cryptosystem, i.e., to find the secret key. For more information about key sizes, see [6]. For square root algorithms, see [10]. Even though this primary advantage, the requirements to set up the systems based on elliptic curves are greater than the other ones. To define them it is also necessary to obtain the number of points of the elliptic curve. This number must be prime, or contain a great prime factor, in order to avoid some attacks, as the Pohlig-Hellman attack. The unique way known to compute that number is the Schoof algorithm [9], of polynomial order, but with a very high computational cost. To palliate this problem, it have been devised another ways, as the methods of complex multiplication, but they do not allow us to choose the elliptic curve at random. The common solution is to use a few curves with its cardinal already computed, as the elliptic curves proposed by NIST for North American government use. See [2]. Motivated for these impediments, we present a new mathematical problem whose inherent hardness is based on the ECDLP, that is, it is solved in a similar number of iterations but every step implies a greater computational effort. Thus, it is possible to use the same elliptic curves, but as a part of certain elements. The computation required does not have to suppose an appreciable increase in the encryption process using fast exponentiation algorithms, but it must augment significantly the time of deciphering. The rest of the paper is organized as follows: section 2 shows the system description, including the DiffieHellman key agreement protocol. Section 3 is divided in several subsections in which the element used as the problem is reduced; it is calculated its maximum order; it is analyzed the coefficient that determines it; its distribution is characterized in an empirical form showing some of the experimental data; and finally in this section, it is given some solutions to the problem of the repetitions that it set out. At last, in section 4 a several conclusions about the system are given.

2 Description of the system

Let E / Fq be an elliptic curve with p = # E (Fq ) a prime number. We consider the set ⎧⎪⎛ a P ⎞ ⎫⎪ ξ = ⎨⎜ ⎟ a, b ∈ Fp , P ∈ E (Fq ) ⎬ b⎠ ⎪⎩⎝ ⎭⎪ and define a binary operation as the formal matrix multiplication, that is, ⎛ a P ⎞⎛ c Q ⎞ ⎛ ac aQ + Pd ⎞ (1) ⎜ ⎟⎜ ⎟=⎜ ⎟ b ⎠⎝ d⎠ ⎝ bd ⎠ ⎝ The next result is easy to prove. Theorem 1: The formal matrix multiplication defined by (1) is associative and have identity element. Proof: It is easy to see that ( M 1M 2 ) M 3 = M 1 ( M 2 M 3 ) for all M 1 , M 2 , M 3 ∈ ξ . MI = M = IM for all M ∈ ξ where

⎛1 O⎞ I =⎜ ⎟ ∈ξ . ■ 1⎠ ⎝ Notice that, for example, ⎛ 0 P ⎞⎛ c Q ⎞ ⎛ 1 O ⎞ ⎜ ⎟⎜ ⎟≠⎜ ⎟ 1⎠ b ⎠⎝ d⎠ ⎝ ⎝ for every b, c, d ∈ Fp and P, Q ∈ E (Fq ) , so there exist

noninvertible elements in ξ . To get that all elements have symmetric, we must consider those that contain an invertible elements a and b. So we define the subset ζ ⊂ ξ formed by ⎧⎪⎛ a P ⎞ ⎫⎪ ⎟ ∈ ξ | a, b ≠ 0 ⎬ b⎠ ⎩⎪⎝ ⎭⎪

ζ = ⎨⎜

⎛a P⎞ It is easy to see that if M = ⎜ ⎟ ∈ ζ , then b⎠ ⎝ ⎛ a −1 −b −1a −1 P ⎞ M −1 = ⎜ ⎟ ∈ζ . b −1 ⎠ ⎝ As we can see, the set ζ with the operation defined is a group. Also, it can be verified easily that it is not an abelian group. We have constructed a group using the formal matrix multiplication with this set without any kind of artifice. This is possible because the missing element of the matrix prevents the multiplication of points of the curve, operation not defined. Once determined the group, the system is described: Let be the subgroup of order p − 1 generated for a known element ⎛a P⎞ M =⎜ ⎟ ∈ζ ; b⎠ ⎝

the system consists of finding the scalar k ≥ 0 solely from P ( k ) , term obtained when the power k of M is computed: k

⎛ a P ⎞ ⎛ ak P(k ) ⎞ M =⎜ ⎟, ⎟ =⎜ b⎠ ⎝ bk ⎠ ⎝ where ⎛ k −1 ⎞ P ( k ) = ⎜ ∑ a k −1−i bi ⎟ P = c ( k ) P for k ≥ 1 , (2) ⎝ i =0 ⎠ and P (0) = O , that is, c (0) = 0 . We refer to the element c ( k ) as the coefficient in a general way. Later we will see how to choose the elements a and b in the sense that M generates a subgroup of maximum order, that is, of p − 1 elements. k

The elements a k and b k are excluded of the problem, otherwise it would be reduced directly to the DLP. Nevertheless, it exists an inherent problem to this exclusion: the element M may be a generator of ζ and so it may be unique for k ∈ [0, p − 2] , but P ( k ) is not unique for that values of k, even though it exists exactly p different points in the elliptic curve and all of them are generators because p is a prime number. Later we will see how to avoid this problem. Once the system is set up, we will see its applicability to the Diffie-Hellman key agreement protocol. Let be the subgroup of order p − 1 generated by the element ⎛a P⎞ M =⎜ ⎟ ∈ζ . b⎠ ⎝ This element is public. Alice takes a private key k ∈ Fp , computes ⎛ ak P(k ) ⎞ Mk =⎜ ⎟, bk ⎠ ⎝ extracts the element P ( k ) and sends it to Bob. Then, he takes a private key m, computes ⎛ am P(m) ⎞ Mm =⎜ ⎟, bm ⎠ ⎝ extracts the element P ( m ) and transmits it to Alice. She then computes k (k ) ⎛ a P(m) ⎞ ⎛ ak ( P(m) ) ⎞ ⎟ ⎜ ⎟ =⎜ b ⎠ ⎜⎝ ⎝ b k ⎟⎠

and considers the element computes

(P )

(m) (k )

. And last, Bob

(P )

m ⎛ am P(k ) ⎞ ⎟ =⎜ ⎜ b ⎠ ⎝

⎛a ⎜ ⎝

(k ) ( m)

bm

⎞ ⎟ ⎟ ⎠

and considers the element ( P ( k ) )

(m)

. The protocol works

correctly as a consequence of the next theorem. Theorem 2: With the notation above, the next holds

(P )

( m) ( k )

= ( P(k ) )

( m)

.

(3)

Proof: By (2) we have k −1 (k ) ( P(m) ) = ⎛⎜ ∑ a k −1−ibi ⎞⎟ P (m) = c(k ) P (m) = c(k ) c( m) P ⎝ i =0 ⎠ and m −1 (m) ( P(k ) ) = ⎛⎜ ∑ a m−1−ibi ⎞⎟ P (k ) = c( m) P( k ) = c( m) c(k ) P . ⎝ i =0 ⎠ (k ) (m) As c , c ∈ Fp , it holds that c ( k ) c ( m ) = c ( m ) c ( k ) and so

(3) is verified. ■

c(k ) To analyze the system, we must do a study of the element P ( k ) and so, of the coefficient c ( k ) .

3 Study of the coefficient

Reduction of the element P ( k )

3.1

Theorem 3: Let P ( k ) be the element defined in (2), if 0 ≤ t ≤ k then P ( k ) = a t P ( k −t ) + P ( t ) b k −t . Proof: Let be M ∈ ζ . Clearly we have

M t M k −t = M k , that is, ⎛ a t P (t ) ⎞⎛ a k −t P ( k −t ) ⎞ ⎛ a k P ( k ) ⎞ ⎜ ⎟⎜ ⎟=⎜ ⎟, bt ⎠⎝ b k −t ⎠ ⎝ bk ⎠ ⎝ thus a t P ( k −t ) + P ( t ) b k −t = P ( k ) . ■ To reduce the summatory obtained of c ( k ) , we will construct an equivalent expression to a summatory of powers founded in the next lemma. Lemma 1: Let g be a generator of the multiplicative group Fp* , the following holds β −α s

∑ gα i =0

+ is

= ( g β + s − g α )( g s − 1) , −1

where α < β and s > 0 . As a consequence of lemma 1, we have that c ( k ) = (b k − a k )(b − a ) −1 , with a ≠ b .

(4)

3.2

Maximum order of the elements of ζ

It is necessary to determine the scalars a and b that we can use such that the order of an element of ζ reach the maximum value possible. Theorem 4: Let be ⎛a P⎞ M =⎜ ⎟ ∈ζ , b⎠ ⎝ if mcm(o( a), o(b)) = p − 1 and a ≠ b then o( M ) = p − 1 . Proof: We have to verify that p − 1 is the least positive integer that accomplish M p −1 = I . We have that a p −1 = a o ( a )· j = 1 j = 1 , and it happens the same for b. Also, because p − 1 is the least common multiple of the orders of both elements, it cannot exist a number h < p − 1 that holds a h = b h = 1 . So, we must prove only

P ( p −1) = c ( p −1) P = O for all that P ≠ O . As ( p −1) o( P ) = p ≠ c , then we must prove that c ( p −1) = 0 . By (4), and applying Fermat’s “little” theorem p −1 g ≡ 1 mod p , we have that: c ( p −1) = (b p −1 − a p −1 )(b − a) −1 = (1 − 1)(b − a) −1 =0. ■

3.3

(5)

Analysis of the coefficient c ( k )

By the definition of the system, we know that c (0) = 0 and c (1) = 1 . On the other hand, as we have seen in (5), c ( p −1) = 0 , with a ≠ b . Otherwise, that is, if a = b , then c ( p −1) ≠ 0 because c ( p −1) = a p − 2 + a p −3 a + " + a p − 2

= ( p − 1)a p − 2 = ( p − 1)a −1 and this expression is equal to zero only if p = 1 . Moreover, it could be applied immediately the reduction c ( k ) = ka k −1 . However, the rest of the possible values of c ( k ) for a fixed elements a and b are not unique in the interval [0, p − 1] ; in fact, they can only take p − 1 possible values because c ( p −1) turn to be 0 as a consequence of reaching the order of the element that includes it. We can see by (4) that c ( k ) will be equal to a certain value µ when the next relation holds: (b k − a k )(b − a ) −1 = µ b k − a k = µ (b − a) b(b k −1 − µ ) = a (a k −1 − µ )

In the same way, a k = b k when c ( k ) = 0 holds, and this value occurs more frequently than the others; for this reason, we do not have to use the zero value of c ( k ) ; furthermore, we cannot use most of the cryptographic protocols. To verify that frecuency, let we see next theorem. Theorem 5: Let k ∈ ]0, p − 1[ be the least value, if exist, such that c ( k ) = 0 , with a ≠ b and a, b ≠ 0 , then p −1 k | p − 1 and c ( k ⋅l ) = 0 with l ≤ , that is, the zero k p −1 value occurs times. k Proof: If c ( k ) = 0 then a k = b k , so any multiple of k vanish the coefficient: c ( k ⋅l ) = (b k ⋅l − a k ⋅l )(b − a) −1

( = ( (b )

) − (b ) ) (b − a )

= (b k )l − (a k )l (b − a) −1 k l

k l

−1

=0 To proof that k | p − 1 it is necessary to see that it does not exist more values, apart of multiples of k, that vanish the coefficient. Suppose that exists d ∈ ]k , p − 1[ such that k /| d , that is, d is not a multiple of k and, however, holds that c ( d ) = 0 , then, if we choose the greater value of l such that k ⋅ l < d , occurs: ad = bd a k ⋅l a d − k ⋅l = b k ⋅l b d − k ⋅l a k ⋅l a d − k ⋅l = a k ⋅l b d − k ⋅l a d − k ⋅l = b d − k ⋅l and so c ( d − k ⋅l ) = 0 , with d − k ⋅ l < k . This is a contradiction because k was the least value that vanish the coefficient. ■

3.4

Empirical distribution of the coefficient

The distribution of the coefficient is founded greatly on the distribution of the discrete logarithm, so its characterization seems infeasible. This carry us to an experimental study of its behaviour. To do the tests, we have gone through all the values of c ( k ) for k ∈ [0, p − 2] . As we have seen in section 3.3, the value c ( k ) = 0 occurs more frecuently than the others, so it has been excluded of the estatistical computations. According to the study, the arithmetic average of the quantity of elements that do not appear any time gets close asymptotically to 36’8%. This value is the same as the percentage of elements that appear only once. The

quantity of different elements that appear twice gets close to 18’4%, that is, the half. The quantity of different elements that appear three times gets close to 6’1%, that is, the third part of those that appear twice, and so on. We define a random variable X, that measures the number of repetitions linked to a computed value of c ( k ) . We have that P ( X = 1) = 0'368

P ( X = 2) = 0'368 P ( X = 3) = 0'183 P ( X = 4) = 0'061 " and so we define the quantity function 0'368 f ( x) = P( X = x) = x. x! To be defined correctly we must have 0'368 ∑i f ( xi ) = ∑i x ! xi = 1 , i so we adjust the initial probability and we obtain that P ( X = 1) = 0'3678794411714423 . This conjecture carry us to get the maximum quantity of repetitions that we hold it takes place according to the size of p. To occur a certain number of repetitions, it is necessary that exists, at least, one value that could take that number of repetitions, that is, 0'368 f ( x) p = xp ≥ 1 . x! Applying logarithms we get ⎛ 0'368 ⎞ xp ⎟ ≥ log10 1 log10 ⎜ ⎝ x! ⎠ 0'368 log10 + log10 p ≥ 0 ( x − 1)! 0'368 log10 ≥ − log10 p ( x − 1)! For an instance, we consider a value that can repeat 10 times. We have that ⎛ 0'368 ⎞ log10 ⎜ ⎟ ≈ −6 , ⎝ (10 − 1)! ⎠ so that value will exists if p have roughly 6 decimal digits, that is, log10 p ≈ 6 . The tests points out that the variability is high with very small values of p, but the given results are verified as p increases its size. It is obvious that we are interested in the values of the coefficient that appear once because a naive exhaustive search will need to go through all the values in the interval [0, p − 2] . If the coefficient appear twice, the probability carry us to go through half of the values,

and so on. Regarding that the hardness measurement of a problem is usually measured in logarithmic scale, this do not represents a great reduction. On the other hand, those values of the coefficient that do not appear, do not suppose an obstacle on the hardness of the problem. This is because we cannot avoid them since we do not know them. In a practice implementation where, for an instance, p ≈ 2200 , that is, 200 bits, a value could take roughly the same value at most 49 times; this reduces the problem to an equivalent one with hardness of about 2200 / 49 ≈ 2194 but without repetitions. Nevertheless, a naive exhaustive search is not used in practice, but an attack of square root is performed because this is always applicable to any group. So, if the size of the initial problem was p = 2100 , then the size of the equivalent problem will be 2100 / 49 ≈ 297 , as we can see, a hardness reduction of only 3 bits. This would happen when we consider the worst case, that is, if we choose a value of the coefficient having the maximum quantity of repetitions. This is almost impossible. If we compute the expected value of the number of repetitions, we will get: 0'368 2 E ( X ) = ∑ xi f ( xi ) = ∑ xi = 2 . xi ! i i Now, if we divide the hardness of the problem outlined by the expected number of repetitions regarding square root algorithms, then we obtain an equivalent problem of 2100 / 2 ≈ 299 '6 . This value is much more realistic than the previous one and, as we can see, produce a reduction of the problem almost imperceptible. To obtain a reliable estatistical data it is necessary thousands of tests. We show a sample in table 1. For different values of p, a and b, the principal (the most wide) column shows a number series that means, in order, the quantity of values that the coefficient do not take (0), the quantity of values that the coefficient take once (1), the quantity of values that the coefficient take twice (2), and so on until the maximum number of repetitions (9 in this case). The column c ( k ) = 0 points out the times that happen c ( k ) = 0 for those values of a, b and p. For example: for p = 26099 , a = 18024 and b = 3550 , the column 0 points out that there is 9648 elements of Fp that do not appear, that is, c ( k ) is never equal to these elements. The column 1 points out that c ( k ) is equal to 9508 elements of Fp only once. The column 2 points out that it exists 4843 elements of Fp that c ( k ) take twice, and so on.

Table 1 p 4831 5197 6863 8563 9739 17231 18713 22567 23993 24593 25703 26099 27581 30757 35923 37691 38377 39869 40519 40759 41491 42323 44617 48073 48299 48869 49211 49391 49727 58189 64693 65323 69109 94049 102983 131249 145349 162989 163433 183437 227453 252691 275129 313739 347251 382919 397433 452269 514739 545647 558563 560411 641681 764587 842383 843209 886493 907363 924877 967819

a 3247 2962 798 8231 7046 10267 9916 5066 6185 10194 17509 18204 327 6159 7021 9988 1286 30116 34114 24454 7474 19855 17284 28829 42067 12361 15642 40591 39054 18496 27274 48536 28990 73755 55335 101132 26173 96698 159535 1446 100432 79508 44529 251677 59478 252791 334120 325585 448899 284344 200697 268678 156712 377150 184490 806199 761262 670163 629500 479809

times that the elements of

b 575 2087 2115 577 8016 2123 7328 13068 1820 68 11267 3550 6286 1070 30786 19367 34641 23486 31241 36574 21873 21020 40422 259 26408 33411 5040 38521 42591 48411 60073 46914 6975 22721 1723 38334 68048 48091 5766 278 217114 18325 93897 119252 23916 342929 287208 380077 120496 370804 87423 223845 435027 135721 508180 14579 883767 54478 878310 368329

0 1876 1910 2528 3180 3568 6377 6842 8321 8824 8928 9455 9648 10147 11329 13332 13889 13949 14708 14944 15080 15245 15564 16536 17704 17548 17964 18134 18185 18158 21383 23828 24041 25457 34670 37678 48230 53584 60396 60089 67497 83402 93360 101535 115350 127125 140867 146134 166365 189374 200544 205481 206391 236656 281152 309962 310323 326216 333635 340576 356307

1 1694 1914 2520 3099 3624 6233 6930 8257 8805 9200 9460 9508 10165 11287 12996 13798 14235 14500 14808 14914 15302 15604 16155 17646 17753 18003 17998 18124 18460 21461 23733 23987 25321 34538 38222 48390 53276 59528 60192 67413 84092 92640 100275 115580 129255 140838 146337 166296 189254 201189 205478 205544 235592 281551 309552 310021 325796 334290 339196 354852

2 826 955 1263 1567 1764 3257 3450 4173 4474 4560 4717 4834 5021 5641 6678 7010 7215 7486 7519 7424 7597 7714 8391 8855 9471 8979 9172 9130 9206 10696 11929 12060 12800 17240 18838 24112 26824 29668 30061 33840 41784 46350 51380 57624 63135 70501 73053 83431 94882 99795 102724 103594 117688 140519 155238 154977 163672 166406 170848 179364

3 294 321 415 560 577 1047 1148 1394 1430 1392 1582 1622 1733 1946 2256 2254 2314 2458 2491 2572 2559 2656 2646 2942 2706 2998 2977 3018 2970 3496 3987 4020 4251 5814 6328 8020 8924 10216 9953 11228 13928 14940 16863 19240 20910 23419 24371 27587 31447 33921 34344 34270 39120 46785 51934 51929 53820 55810 57008 59265

4 112 77 112 132 176 251 282 340 372 480 399 390 406 444 516 607 572 596 612 614 645 629 726 773 697 749 750 747 752 954 974 971 1014 1420 1546 2004 2176 2532 2545 2757 3404 4590 4102 4766 5385 5941 6085 6928 7899 8253 8467 8563 10288 11813 12500 12903 13630 13918 13896 14469

Fp appear in c ( k ) 5 28 14 22 24 24 53 52 68 65 32 71 82 99 85 132 114 78 90 117 110 121 128 138 122 82 142 140 156 150 162 209 195 218 298 312 410 480 548 488 592 690 735 763 972 1215 1102 1212 1381 1571 1629 1733 1726 1896 2271 2694 2570 2856 2745 2808 2910

6

c(k ) = 0 7

8

9

5 2 5 12 8 11 19 17 14 9 22 12 15 13 26 24 40 17 25 24 25 41 27 37 27 28 32 26 41 42 60 52 68 52 96 91 93 124 45 196 180 210 211 211 236 260 264 281 277 368 438 438 419 430 486 484 564

2 3 0

1

1

1

3 2 3 0 3 1

2

4

0

4 2 3 0 4 6 7 5 8 6 13 24 4 12 16 28 30 14 24 15 33 24 37 41 48 49 39 72 51 60 59 66 60 52 66

2

4 1 1 1

2

1 8 1

2 5 4 7 10 3 4 4

1 1

5 4 7 6 12 8 21

1

1 2

14 1 1 1 1 1 2 1 1 16 1 2 1 1 6 1 13 2 1 2 1 1 3 1 41 1 1 1 2 1 1 1 1 2 2 1 4 4 1 1 2 15 7 2 15 1 1 1 1 3 1 1 8 1 2 1 2 1 4 3

3.5

Searching for coefficients without repetitions

As we have seen, more than the third part of the values of the coefficient appears only once, and also, the repetitions produce a reduction of the problem almost imperceptible. Even though, it is convenient to avoid repetitions. We are going to transform the problem of obtaining the repetitions of a given coefficient, which is a hard task considering its apparent behaviour highly random, in the problem of obtaining the roots of a polynomial in a finite field. Once a value k is selected and the coefficient c ( k ) obtained, we have to determine whether or not exist any value t ≠ k such that c ( t ) = c ( k ) . If this holds, then we will have that (bt − a t )(b − a ) −1 = (b k − a k )(b − a) −1 and thus bt − a t − (b k − a k ) = 0 . (6) To set out the system, we choose a generator g of the multiplicative group of Fp . We know it exists because p is a prime number. Then we select two values i and j that act as the exponents of g, that is, g i = a and g j = b . Last, we take a value k at random. Now we can see equation (6) as ( g j )t − ( g i )t = ( ( g j ) k − ( g i ) k ) , thus ( g t ) j − ( g t )i = ( ( g j ) k − ( g i ) k ) , and, after compute the right side term, we can write it as z j − zi − γ = 0 . Now, the problem consists of determining whether the trinomial f ( z ) = z j − z i − γ have one or more roots. We know it has one, obviously z = g k , because we have used it to construct the equation, but determining if it have more roots can be a very hard task because the order of the finite field is very high. An easy form would be to take j = 3 and i ∈ [1, 2] , that is a = g or a = g 2 and b = g 3 , so f ( z ) would be a polynomial of third degree, and, as we know that it has a root in z = g k , we can do h( z ) = f ( z )( z − g k ) −1 where h( z ) is of second degree. Now we must verify that the discriminant of this polynomial is not a quadratic residue, that is, D ( h( z ) ) ∉ Fp , to prove that is irreducible and so, the unique root of f ( z ) is that we have. By means of a simple mechanism of proofs and refutations, we might not take a long time to find an

appropriate value of k because the amount of coefficients that appear only once exceeds the third part. Nevertheless, to give explicitly the value of the generator with i and j, and so the relation linking a and b, could facilitate in a certain measurement the search of k from c ( k ) . Another, and more elaborated technique, consists of taking i = 1 , that is, g = a , thus the trinomial takes the form f ( z ) = z j − z − γ . The use of the element a as a generator does not involve an easier form to find the relation between a and b because the element b can take any value of Fp excluding the zero and a, so the cost of finding it would be similar to the search of i and j from any generator. However, to determine whether this trinomial have a unique root requires algorithms for searching roots on polynomial theory in finite fields. These have a high algorithmic complexity and so they are inefficient in practice. For more information see [7].

4 Conclusions The search for systems that are able to increase the hardness of the problems that already exist, but without incrementing the size of these, have carried us to design a new system that link the discrete logarithm problem of certain elements with the elliptic curves. We have used elliptic curves because they represent nowadays the best mathematical problem applicable to public key cryptography. The goal have been to create a problem harder to solve than the ECDLP but without the computation requirements for setting it up. The new system is founded on two problems; this is an advantage because to solve one of them do not suppose that the problem is solved, but only a part. We have analyzed the troubles that can reduce the hardness of the system, as the repetitions of the coefficient, giving solutions to avoid them. The study of this system supplies a base to approach new problems with better properties than the known ones, in the sense that they permit to define cryptosystems of higher hardness with the minimum requirements as possible.

References: [1] I. Blake, G. Seroussi, N. Smart. Elliptic Curves in Cryptography. London Mathematical Society Lecture Note Series 265, Cambridge University Press, 1999 [2] M. Brown, D. Hankerson, J. López and A. Menezes. Software Implementation of the NIST Elliptic Curves over Prime Fields, Centre of

Applied Cryptographic Research, University of Waterloo, Technical report CORR 2000-56, 2000 [3] W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol.22, No.6, 1976, pp. 644-654 [4] D. Johnson and A. Menezes, The Elliptic Curve Digital Signature Algorithm (ECDSA), Centre of Applied Cryptographic Research, University of Waterloo, Technical Report CORR 99-34, 1999 [5] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, Vol.48, pp. 203-209, 1987 [6] N. Koblitz, A. Menezes and S. Vanstone, The State of Elliptic Curve Cryptography, Designs, Codes and Cryptography, Vol.19, pp. 173-193, 2000 [7] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, 1994 [8] V. Miller, Use of elliptic curves in cryptography, CRYPTO 85, 1985 [9] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of Computation, Vol.44, No.170, 1985, pp. 483-494 [10] E. Teske, Square-Root Algorithms for the Discrete Logarithm Problem (A Survey), Centre for Applied Cryptographic Research, University of Waterloo, Technical Report CORR 2001-07, 2001