Hyperbolic Cryptosystem

Hyperbolic Cryptosystem based on matrices Bay :Abdelhakim Chillali June 7, 2009 Abstract:We propose a new problem that is applicable to public key cryptography. Based on the hyperbolic curve discrete logarithm problem (HCDLP), it uses certain elements formed by to matrices with elements in a finite field. Key words: Public key cryptography, Hyperbolic curve discrete logarithm problem, Finite field, Diffie-Hellman key...

1

Introduction

Public key cryptographic is the fundamental technology in secure communications. It was devised by Diffie and Hellman in 1976 to secret key distribution. The mathematical problems more used are the discrete logarithm problem (DLP). In 1985 the elliptic curve discrete logarithm problem (ECDLP) was proposed independently by Koblitz and Miller. In this paper, we present the hyperbolic curve discrete logarithm problem as a new cryptographic scheme. Consider a finite field L = Fq with characteristic p. where a, b ∈ L∗ , let x, y ∈ L, we denote: L∗ multiplicatif group of L.   x y a −1 b −1 . Myx = y x b +1 a +1 G = {Myx det(Myx ) = 1} Gq = G mod p. Myx11 4Myx22 = Myx33 with:

(

x3 = y3 =

(1) :

b2 x1 x2 +a2 y1 y2 ab2 x1 y2 +x2 y1 a

Myx 4 Myx 4 ....Myx = Myx 4l . | {z } lf ois

2

Mk =

k +1 2k k2 −1 2k

−1 +1

k2 −1 2k k2 +1 2k

−1 +1

! , k ∈ L∗ .

m = |Gq | The next theorem whose proof is evident. Theorem 1. The set Gq with the operator 4 defined by (1) is a abelien group. x The identity element is M0a , that if M = Myx then N = M−y is the inversible element of M . 1

Remark 1. The HCDLP consists of following for two elements M, N ∈ Gq , determine the scaler k ∈ Zm such that M 4k = N . It is necessary that M be a generator of the group Gq . Assumption 1. Given a group Gq and tow elements M and N ∈ Gq , there exists non polynomial time algorithm θ(logq) deciding the integer k such that M 4k = N if such a k exists. Assumption 2. Given a group Gq and θ(logq) elements Ni on Gq , there exists non polynomial time algorithm (θ(logq)) deciding the integers ki , such that 4k

θ(logq) =M N14k1 4N24k2 4.......4Nθ(logq)

if such ki exist, where M is a random element on Gq .

2

Key distribution protocols

Let Myx be a generator of the group Gq . A take a private key 1 < l < m, and computes Myxll = Myx 4l , then he transmits Myxll to B. Similar, B takes a private key 1 < t < m, and computes Myxtt = Myx 4t and transmits Myxtt to A. Then A and B compute Myxtltl = Myxtt 4l and Myxltlt = Myxll 4t respectively. Theorem 2.

xlt ylt xtl ytl + = + mod p a b a b

Prof: Evident The secret key is α =

3

xtl a

+

ytl b

mod p

Description of The hyperbolic cryptosystem

Let L = Fq with q = pn . 1)Space of lights: P = Gq . 2)Space of quantified: C = Gq . 3)Space of the keys: K = L∗ . 4)Function of encryption:∀α ∈ K , eα :

P Myx

−→ 7−→

C eα (Mxy ) = Myx 4Mα

5)Function of decryption:∀α ∈ K , dα :

C Myx

−→ 7−→

P dα (Mxy ) = Myx 4M−α

Remark 2. dα oeα (Myx ) = Myx 4Mα 4M−α = Myx Secret key : α Public keys: Espace of lights P Espace of quantified C 2

Espace of the keys K Myx a generator of the group P Fonction of coding eα Fonction of deciphering dα Remark 3. The Myxll , Myxtt and m are public and can known by another person, but to obtain the private key α, it is necessary to solve the problem of the discrete logarithm in Gq , what returns the discovery of the difficult key α.

4

Numerical Example for HCDLP p = 41, a = 2, b = 5, n = 1, m = 40 26 G41 =< M31 >, The identity element is M02

Exchange of the key deprived between A and B: A take a private key: l = 13 < 39 Calculation: 13 26 413 M23 = M31

Send to B: 13 M23

And calculation: 13 15 413 M18 = M10

B take a private key: t = 21 < 39 Calculation: 15 26 421 M10 = M31

Send to A: 15 M10

And calculation: 13 13 421 M18 = M23

Calculation of the secret key: α=

13 18 + = 6 mod 41 2 5

Message with envoy: 28 23 34 me = {M18 , M40 , M27 , M36 }

Encryption: Mxy M28 18 M04 M23 27 M34 36

x  e6 (My )  39 40  1 0  15 37  39 17  28 13  17 30  28 25 27 30

3

Message received:  28 mr = { 27

25 30

  28 , 17

13 30

  15 , 39

37 17

  39 , 1

Decryption: Mxy 39 40  1 0 15 37  39 17 28 25  27 30 28 13 17 30 

d6 (Myx ) 

M28 18



M04



M34 36



M23 27

Remark 4. 15 13 26 M 26 M logM31 10 = 21 , logM31 23 = 13

5

Example for cryptography p = 3, a = b = 1, n = 3, m = 26. α root of the polynomial X 3 + 2X + 1 P = G27 , C = G27 , K = F∗27 Mα2α+2 a generator of the group P 2

Exchange of the key deprived between A and B: A take a private key: l = 12 < 25 Calculation: 4l Mαα+1 = Mα2α+2 2 2

Send to B: Mαα+1 2 And calculation:

2

2

+2 2α +2 4l Mα2α 2 +2α+2 = M2α2 +α+1

B take a private key: t = 20 < 25 Calculation:

2

2α +2 2α+2 4t M2α 2 +α+1 = Mα2

Send to A:

2

2α +2 M2α 2 +α+1

And calculation:

2

+2 α+1 4t Mα2α 2 +2α+2 = Mα2

Calculation of the secret key: β = 2α2 + 2 + α2 + 2α + 2 = 2α + 1 2

+2 eβ (Myx ) = Myx 4Mα2α 2 +2α+2

4

40 0

 }

2

2α +2 dβ (Myx ) = Myx 4M2α 2 +α+1

Lets x = iα2 + jα + k and y = lα2 + mα + n, we denote Myx bay ijklmn. Table of the Symbol Encryption Mxy 001000 010112 010220 012210 012122 122110 122222 202120 202212 011101 011201 112200 112102 002001 020112 020220 021210 021122 211110 211222 101120 101212 022101 022201 221200 221102

Symbol a b c d e f g h i j k l m n o p q r s t u v w x y z

eβ (Myx ) 202120 010220 012210 211110 010112 021210 112102 011101 001000 221102 202212 122110 022101 101212 021122 020112 020220 122222 221200 012122 002001 022201 101120 112200 011201 211222

Encrypt Symbol h c d s b q m j a z i f w v r o p g y e n x u l k t

Let’s crypt the message me with A, which will be sent to B. Example me:=”bonjour”. A transforms the message m to the following message with reference to table, it sends the message to B mr:=”crvzrng”. Remark 5. We implemented the encryption, decryption..in maple.

References [1] Akiyama, K., Goto, A.:(2006). A Public-key Cryptosystem using Algebraic Surfaces (Extended Abstract). PQCrypto Workshop Record. [2] Akiyama, K., Goto, A.:(2008).An improvement of the algebric surface Publickey Cryptosystem,Proceedings of SCIS. [3] Miller, V.:(1986). Use of elliptic curves in cryptography, in:Advances in cryptography-CRYPTO 85, Lecture Notes In Computer Science, vol. 218, Springer-Verlag, 1986, pp. 417-426. [4] Koblitz, N.:(1987). Elliptic Curve Cryptosystems, Mathematics of Computation 48 203-209.

5

[5] Joan-Josep, C., Francisco, F., Jos´e-Francisco, V., Antonio, Z.:(2006). A nonlineear elliptic curve cryptosystem based on matrices, Mathematics of Computation 174 150-164. Dept. of Mathematics. FST of fes E-mail address: [email protected]

6