Survey on NP-Hard Problems of Digital Signature Schemas

Survey on NP-Hard Problems of Digital Signature Schemas

Rashad Elhabob1 Abdalla Adel1 Ma'moun O_ mer 1

Computer science department Computer science department Faculty of Mathematical Sciences Faculty of Mathematical Sciences

Computer science department Faculty of Mathematical Sciences

University of Khartoum University of Khartoum University of Khartoum

Khartoum ,Sudan Khartoum ,Sudan Khartoum,Sudan

Dr. Hwida Elshousp Computer Science Department

Faculty of Mathematical Sciences University of Khartoum

Khartoum, Sudan

Abstract A study for public-key digital signature schemes that based on different mathematical NP hard problems. That problems influence in performance and reliability of digital signature schemes. In this paper we make a survey on mathematical NP hard problems of digital signature schemes and present the powerful and practical of some schemes depending on its security level.

KeywordsCryptography, Digital Signature, Hard Problem.

I. INTRODUCTION

Digital signature is a verification mechanism based on the public-key scheme, and it provides:

1. Data integrity (the assurance that data has not been changed by an unauthorized party).

2. Authentication (the assurance that the source of data is as claimed).

3. Non-repudiation (the assurance that an entity cannot deny commitments).

   Generally, every public-key digital signature schemes is based on a mathematical problem. This problem is known as NP (Non-deterministic polynomial) hard problem. The problem is considered to be an NP hard mathematical problem if the validity of a proposed solution can be checked only in polynomial time.

   Basically, public-key digital signature schemes are successfully classified into many major types depending on the NP mathematical hard problem shown in (Fig1). These problems are the integer factorization problem (IFP), the discrete logarithm problem (DLP), the Elliptic Curve discrete logarithm problem (ECDLP), the chaotic maps hard problem In the present e-commerce and e-government era, digital signatures have become more and more important According to this what the suitable schema used and in what class that algorithm fall after this study [1][4][6][7].

   Fig.1. major types public-key digital signature schemes depending on the NP mathematical hard problem [4]

   1. DIGITAL SIGNATURE BASED ON INTEGER

      FACTORIZATION

      The factoring a positive integer n means finding positive integers u and v such that the product of u and v equals n, and such that both u and v are greater than 1. Such u and v are called factors (or divisors) of n, and n =u .vis called a factorization of n. Positive integers that can be factored are called composites. Positive integers greater than 1 that cannot be factored are called primes. For example, n = 15 can be factored as the product of the primes u = 3 and v = 5, and n = 105 can be factored as the product of the prime u = 7 and the composite v = 15. A factorization of a composite number is not necessarily unique: n = 105 can also be factored as the product of the prime u = 5 and the composite v = 21. But the prime factorization of a number writing it as a product of prime numbers is unique, up to the order of the factors: n = 3 .

      1. 7 is the prime factorization of n = 105, and n D=5 is the prime factorization of n = 5[8][9].

         1. Rsa Digital Signature Scheme

            In the RSA digital signature algorithm, the private key is used to sign the message. The signed message will be sent to the receiver with the senders electronic signature. To verify the contents of digitally signed data, the recipient generates a new verification key from the signed message that was received, by using his public key, and compares the verified value with the original message value. If the two values match, then the message is verified and authenticated [4].

         2. The RSA Digital Signature Algorithms:

            1. Key generation algorithm (generated by receiver)

               1. Choose two prime numbers (p, q) randomly, secretly, and roughly of the same size.

               2. Compute the modulus n as follows: n = p q.

               3. Compute the (n), as follows: (n) = (p-1) (q-1).

               4. Choose the key e, such that 1 < e <(n), and GCD (e, (n)) = 1.

               5. Compute the private key d, such as d = e-1mod (n).

               6. Send the public (n, e).

            2. Signature and verification algorithms:

               1. Determine the message m to be signed such that 0 < m < n.

               2. Sign the message as follows: s = md mod n.

               3. Send the signature s with the message m to Bob (receiver).

            3. Verification (receiver):

      1. Obtain the keys (d, n).

      2. Obtain s, m from Alice.

      3. Compute u as follows: u = se mod n.

      4. Verify the message m as follows: is m= u-1?.

   2. DIGITAL SIGNATURE BASED ON DISCRETE

      LOGARITHM

      The Discrete Logarithm Problem (DLP) has been the subject of interest among many mathematicians and cryptographers in recent times because of its computational difficulty.

      Definition: The Discrete Logarithm Problem states: Given a multiplicative group G and elements g , h G, find an integer n, if it exists, such that gn = h . This number n is the discrete logarithm of h to the base g, written more concisely as n=logg(h).

      In 1976, Whitfield Diffie and Martin Hellman published a paper in which they proposed the Discrete Logarithm Problem as a good source of a one-way function [10]. That marked the inception of the Discrete Logarithm Problem in cryptography. For the purpose of this study, we may think of a one-way function as a function f : X Y for which given x X, it is easy to compute f(x), however, given y Y, it is difficult to compute a value x X such that f(x) = y, at least for most values of y [2]. In other words, from the standpoint of realistic computability, the function f is not invertible, without further information, and it is for this reason that such function is otherwise known as a trapdoor function.

      1. Digital Signature Algorithm (DSA):

         DSA is an alternative to the ElGamal signature scheme. Knowing that tow schemes based on same mathematical hard problem Discrete logarithm problems (DL), but DSA more security because its bases on complexity of the discrete logarithm problem in the field of Zp, where p is a prime [3].

      2. The DSA Algorithms:

         1. Key generation algorithm (generated by receiver)

            1. Choose a prime number (p), where 2L-1 <p < 2L for 512 L 1024 and L a multiple of 64.

            2. Choose a prime numbers (q), where q divisor of (p 1), and 2159 <q < 2160.

            3. Compute g as follows: g = (h(p-1)/q) mod p, where 1<h<(p 1), and g > 1.

            4. Choose a random integer x, with 0 <x <q.

            5. Compute y as follows: y = gxmod p.

            6. Send (p, q, g, and y)

         2. Signing and verifying algorithms

            1. Determine the message m to be signed such that: 0 < m

               < p.

            2. Choose a random integer k, with 0 < k < q.

            3. Compute r as follows r = (gk mod p) mod q.

            4. Compute s as follows: s = ((k-1) (SHA-1(m) + x r)) mod q.

            5. The signature is (r, s).

            6. Send the signature(r, s) and the message to the receiver.

            7. k-1 is a multiplicative inverse of k in Zq.

         3. Verifying (receive)

      1. Obtain the keys (p, q, g, and y).

      2. w = s-1 mod q.

      3. u1 = ((SHA-1(m)) w) mod q.

      4. u2 = (r w) mod q.

      5. v = ((gu1 yu2) mod p) mod q.

      6. Verify the message m as follows: is v= r?.

   3. DIGITAL SIGNATURE BASED ON ELLIPTIC

      CURVE

      Elliptic Curve provides public-key primitives using much shorter key lengths for a given security level than other cryptosystems such as RSA, Digital Signature Algorithm (DSA), or Diffie-Hellman. This is a decisive advantage in the context of embedded devices where resources (power, memory, frequency, bandwidth, etc.) are generally limited. Thus, many applications are currently switching to ECC as security requirements increase over the years and traditional key lengths become prohibitive in the embedded context.

      Elliptic Curves are mathematical constructions, An elliptic curve can be defined over any field (of real , relational or complex numbers ) , but generally speaking the elliptic curve used in cryptography are defined over finite fields[11]like what show in figure 2.

      Fig2: finite fields represented in graph[3]

      1. Finite Field

         A finite field consists of a finite set of elements together with two binary operations called addition and multiplication, which satisfy certain arithmetic properties. The order of a finite field is the number of elements in the field. There exists a finite field of order q if and only if q is a prime power. If q is a prime power, then there is essentially only one finite field of order q; this field is denoted by Fq. There are, however, many ways of representing the elements of Fq. Some representations may lead to more efficient implementations of the field arithmetic in hardware or in software. If q=pm where p is a prime and m is a positive integer, then p is called the characteristic of Fq and m is called the extension degree of Fq.

         1. Prime Field Fp:

            Let p be a prime number. The finite field Fp called a prime field, is comprised of the set of integers {0,1,2,.,p-1} with the following arithmetic operations:

            1. Addition: If a, b Fp then a+b=r, where r is the remainder when a+b is divided by p and 0 r p-1 known as addition modulo p.

            2. Multiplication: If a, b Fp then a.b=s, where s is the remainder when a.b is divided by p and 0 s p-1 known as multiplication modulo p.

            3. Inversion: If is a non-zero element in Fp, the inverse of modulo a modulop, denoted by a 1, is the unique integer c Fp for which a.c=1.

         2. Binary Field F2m :

         The field F2m, called a characteristic two finite field or a binary finite field, can be viewed as a vector space of dimension m over the field F2 which consists of the two elements 0 and1. That is, there exist m elements 0, 1,, m-1 in F2m such that each element can be uniquely written in Equation (1):

         = a0 0+a1 1+.+am-1 m-1, where ai {0,1}(1)

         Such a set {0, 1,, m-1} is called a basis of F2m over F2. Given such a basis, a field element can be represented as the bit string (a0 a1 .+am-1) Addition of field elements is performed by bitwise XOR- ing the vector representations. The multiplication rule depends on the basis selected. ANSI X9.62 permits two kinds of bases: polynomial bases and normal bases.

      2. Domain Parameters of ECDSA(elliptic curve DSA) :

         The domain parameters for ECDSA [3] consist of a suitably chosen elliptic curve E defined over a finite field Fq of characteristic p, and a base point G E(Fq). Domain parameters may either be shared by a group of entities, or specific to a single user. To summarize, domain parameters are comprised of:

         2

         1. a field size q, where either q=p, an odd prime, or q= m

         2. an indication FR (field representation) of the representation used for the elements of Fq

         3. (optional) a bit string seed E of length at least 160 bits

         4. two field elements a and b in Fq which define the equation of the elliptic curve E over Fq' (i.e., y2 = x3 + ax + b in the case p>3, and y2 + xy = x3 + ax + b in the case p=2)

         5. two field elements xG and yG in Fq which define a finite point G=(xG, y14) of prime order in E(Fq)

         6. the order of the point G, with n>2160 and n>4q and

         7. the cofactor h= E(Fq)/n.

      3. Elliptic Curves Digital Signature Algorithm over Finite Fields:

         The main operation is Point multiplication is achieved by two basic elliptic curve operations.

         • Point addition, adding two points J and K to obtain another point L i.e. L= J + K, require 1 inversion and 3 multiplication operation.

         • Point doubling, adding a point J to itself to obtain another point L i.e. L = 2J, requires 1 inversion and 4 multiplication operation.

         1. Key Pair generation

            Public key systems require the selection of a public key and a private key as inputs to the encryption and decryption schemes respectively . The public and private keys are algebraically related to each other by Q = [m]P where Q is the public key , m is the private key and P is the primitive (base) point of (P). The order of (P) is denoted by |(P)|.

            Input: all necessary parameter for P E (Fq) . Output: public key Q and private key m.

            1. Select a random m , 0 < m < |(P)|.

            2. Compute Q = [m]P. c)return (Q, m).

         2. Elliptic Curve Digital Signature Generation

            Input: All necessary parameters for P E(Fq) , private key k , message M , a suitable Hash function.

            Output: Signature (s0 , s1).

            1. Select a random m , 0 < m < |(P)|.

            2. Compute [M]P and treat the r-coordinate as integer im.

            3. Set s0 = im (mod|(P)|). if s0 = 0 go to step 1.

            4. Compute s1 = K-1(H(M)+Ks0) (mod|(P)|) . if s1 = 0 go to step 1.

            5. return (s0, s1).

         3. Elliptic Curve Digital Signature Verification

            Input: All necessary parameters for PE(Fq), public key Q, Signature (s0 , s1), the message M, the Hash function H. Output: r = {true, False} for the acceptance or the rejection of (s0, s1), respectively.

            1. Set r = False.

            2. if 0 < s0,s1 < |(P)| is satisfied then

            3. Compute t0 = s1-1s0(mod|(P)|) , t1 = s1-1H(M) (mod|(P)|).

            4. Compute T = [t0]P+[t1]Q.

            5. if T 0 then

            6. Treat the x-coordinate of T as an integer iT.

            7. if s0 iT (mod|(P)|) then

            8. r = True.

            9. end

            10. end

            11. end

            12. return r.

   4. DIGITAL SIGNATURE BASED ON CHOATIC MAPS From early times, cryptography based on chaos

      theory has been studied widely. Chaotic maps have been used in the design of symmetric encryption protocols, S-boxes, and hash functions. Recently, chaotic systems have also been used for key agreement schemes [13][14][15].

      1. Chaotic maps problems:

         Let P and Q be integers and p be prime. The general second-order linear recurrence relation is in this Equation (2):

         Ta (M) = P ×Ta1(M) +Q×Ta2(M) (a 2) (2)

         1. Calculate the following: x 21(r + _p2 (M,K) +RK2)r

            1)mod n

         2. Compute pv(x) = e = (e1, e2, . . . , et ), where ei {0, 1} for all i.

            Where Ta (M) GF(p) for all a. The recurrence relation

         3. Calculate the following: y = 21 u t

            uei r

            function of chaotic maps is defined to be in Equation (2)

            With initial conditions T0 (M) =1 and T1 (M) = M. It is easy to see that the chaotic maps function is a special type of

            p 2M,K+RK2r1mod n

         4. signature of M signed by the signer is (K,x,y).

         1. Signature Verification Phase:

         i=1 i

         second-order linear recurrence relation as defined in previous equation, with P = M and Q=1.

         The Chebyshev polynomials exhibit the following two important properties:

         1. The semi-group property:

            The verifier (destination) verify that (K, x, y) is a valid signature of M signed by the signer , he/she will first calculate pv(x) = e = (e1, e2, . . . , et ) and p(M,K), and then checks to see whether the following equivalence holds

            or not.

            Tr (Ts(x)) = cos(r cos1(cos(s cos1(x)))) = cos(rs

            cos1(x)) = Tsr (x) = Ts(Tr (x)) (3)

            (,) ()

            +

            = ()

            + ()

            =

            =

            where r and s are positive integer numbers and x [1, 1].

         2. When the degree a > 1, the Chebyshev polynomial map:

         (,)

         + (5)

         Ta(x): [1, 1] [1, 1] of degree a is a chaotic map with

         The verifier always accepts the signature as valid If the

         the invariant density f (x) = 1

         1×2

         forLyapunov exponent = ln a >0.

         (4)

         signer and verifier follow the signature protocol above, and the receiver is ensured that the message is indeed signed by the signer. Otherwise, the signature is invalid.

      2. Anew digital signature algorithm based on chaotic maps:

         Kai Chain and Wen-Chung Kuo propose a new Digital Signature Algorithm and give implementation of a digital signature algorithm based on both cryptographic and chaotic system characteristics [15].

         1. System Parameters

            First there will be exploring for system parameters as follow:

            • p(.) is a strong one-way hash function whose output is an integer of which the length is t -bit. Here, we assume t

              = 128 as the output length of the standard hash function.

            • pv(.) is a strong one-way hash function whose output is a vector which has t elements and every element belongs to {0,1}.

            • p(, ) is a strong one-way hash function whose input is two integers and , its output is an integer which length is t -bit.

            • p is a large prime such that a factor of p 1 is the product of two large primes p and q ex: n=p.qand n|p-1

            • g is an element in GF(p) whose order modulo p is n , and G is the multiplicative group generated by g. Note that the two large primes p and q are kept secret for all users in the system.

         2. Users Keys Generation Phase

            1. include set of keys u1,u2,u3,,ut [1,n]with t length that represent a set of private keys and after that calculate the corresponding public keys k1,k2,k3,,kt by : kiui 2 =1mod n

            2. choose a secret key u [1,n] randomly from the previous set

         3. Signature Generation Phase:

         To sign a message M the singer must implement this procedure:

         1. choose two integers R and r randomly such that gcd(r,n)=1 and compute K= TR()mod p.

         2. If p(M,K) = 0, then go to Step 1 and select another random number R; otherwise go to Step 3.

      3. Security analysis:

      The security of this schema depend on finding the key (K, x, y) and it have a good security because of computational complexity A drawback of our method is that it requires high computational resources.

   5. DIGITAL SIGNATURE BASED ON TWO NP-HARD

      PROBLEMS

      The securities of digital signature algorithms are based on the difficulty of solving some NP-hard problems. These algorithms stay secure as long as the problem, on which the algorithm is based, stays unsolvable. The most used hard problems for designing a signature algorithm are prime factorization (FAC) and Discrete Logarithm (DL) problems. For improving the security, the algorithms may be designed based on multiple hard problems. Definitely, the security of such algorithms is longer than algorithms based on a single problem. This is due to the need of solving both the problems simultaneously. Many digital signature algorithm have been designed based on both FAC and DL [5][17][18][19].

      1. MERDSA:

         KapilMadhur and others propose Modified ElGamal over RSA Digital Signature Algorithm (MERDSA)[20] proposed digital signature algorithms based on two hard problems-the prime factorization problem and the discrete logarithm problem. A new digital signature algorithm based on combined application of DL and FAC is described as follows:

         1. Key Generation

            1. Choose a large prime p such that computing discrete logarithms modulo p is difficult and two large prime numbers p1 and q1 such that p < n where n = p1 × q1.

            2. Choose random numbers k and v such that 1 < k, v <p1.

            3. Choose random number b such that 1 < b < n 1.

            4. Choose a primitive root g inZp .

            5. Calculate (n) = (p1 1) × (q1 1).

            6. Choose e and x such that e, x Z(n) .

            7. Calculate d such that d × e mod (n) = 1.

            8. Calculate c such that bx × c(mod)n = 1.

            9. Calculate u, w, and t as follows: u = gk mod p, w = gy mod p,

               t = uw mod p,

            10. Public key is (e, x, c, g) and private key is (k, v, t, b, d).

         2. Signature Generation:

            1. Choose an integer z such that 1 < z < (p 1) and it is relative prime to (p 1) i. e. gcd(z, p 1) = 1. z should be different for every message m and is not public. Here H (.) is a one way hash function.

            2. Calculate: h=gz mod p,

               s1 = H(m)d mod n,

               s2 = (H (m) × bs 1) mod n,

               s3 = ((((H (m) kw hv) × z1 )) mod (p 1)).

               If = 0 and/or s1 = 0 and/or s2 = 0 and/or s3 = 0 and/or H(m) (kw + hv) mod (p 1) then repeat step 1 and 2 else tuple (,h, s1, s2, s3) is the signature of m.

               Here kw, hv are additive inverse of kw and hv respectively and z1 is the multiplicative inverse of z with respect to mod (p 1).

         3. Signature Verification

            1. Calculates H (m) using the received message m at receivers end.

            2. If gH(m ) × s1×x ( ×hs 3 × s2 × cs 1 mod n) mod p Then the signature is valid else reject the signature.

      2. Security analysis:

      The performance of the proposed algorithm is found to be competitive to the most of the digital signature algorithms which are based on multiple hard problems, butIt is observed that if an oracle O breaks the FAC and DL then it can break the proposed algorithm also, if given the public key of the scheme and a message m.

   6. CONCLUSIONS

In this paper we give the reader basic concepts which are related to the concepts in digital signature cryptosystem. As well, we studied some digital signature schemes (Table I) which are based on different mathematical hard problems as classified earlier. Those classifications help the reader to be familiar with the public-key digital signature cryptosystem. On the other hand, the security protection of the discussed digital signature schemes depend on the mathematical NP- hard problems and the randomness of the output generated. As a result we recommend that to use two NP-hard problems digital signature and chaotic map as one problem because of its complexity and hardness to break.

TABLE I.Comparisons ofMathematical NP- hard problem in term of efficiency and performance

Mathematical NP- hard problem	Algorithm	Efficiency	Typical key size for high performance
INTEGER FACTORIZATI ON	RSA digital signature schema	Slower than other	large key size which is typically 1024 – Bit
ON DISCRETE LOGARITHM	DSA	System security depend on maintaining the confidentiality of private key	large key size which is typically 104 – Bit
ELLIPTIC CURVE	Elliptic Curves Digital Signature Algorithm over Finite Fields.	Its more difficult than other mathematical problems	Small key size which is typically 128 – Bit
CHAOTIC MAPS	Anew Digital Signature Algorithm based on chaotic maps	The system provides high level of security , in term of key size and execution time	Small key size which is typically 128 – Bit
COMBINATIO N OF TWONP- HARD PROBLEMS	MERDSA	The performance of the proposed algorithm is found to be competitive to the most of the digital signature algorithms which are based on multiple hard problems	large key size which is typically 1024 – Bit

REFERENCES

1. Yadav .Srivastava. and Trehan , DIGITAL SIGNATURE, international journal of engineering and management sciences ,p I.J.E.M.S., VOL.3(2) 2012: 115 118

2. McCurley K.S., The Discrete Logarithm Problem, Cryptology and Computational Number Theory, volume 42, pages 49-74, American Mathematical Society, 1990.

3. D. Johnson, A. Menezes, S. Vanstone, The Elliptic Curve Digital Signature Algorithm (ECDSA), Certicom Corporation, 2001.

4. M. Ahmad , Comparison Study On Np-Hard Problem Based Digital Signature Schemes , International Science and Technology Conference, Istanbul, 7-9 December 2011.

5. Swati Verma1,* and Birendra Kumar Sharma2, A New Digital Signature Scheme Based on Two Hard Problems, International Journal of Pure and Applied Sciences and Technology, pp. 55-59, 5(2) (2011).

6. Fashoto S.G, Gbadeyan J.A and Okeyinka E.A, Application of Digital Signature for Securing Communication Using RSA Scheme based on MD5, Proceedings of the International Conference on Software Engineering and Intelligent Systems , Ota, Nigeria, July 5th-9th , 2010.

7. GunjanJain , Digital Signature Algorithm, International Journal of Innovations in Computing, (ISSN : 2319-8257) Vol. 1 Issue 1

8. ARJEN K. LENSTRA , Integer Factoring, Designs, Codes and Cryptography, 19, 101128 (2000)

9. Ismail E.S, N.M.F. Tahat and R.R Ahmad , A New Digital Signature Scheme Based on Factoring and Discrete Logarithms, Journal of Mathematics and Statistics 4 (4): 222-225, 2008

10. Diffie, W. and Hellman, M., New Directions in Cryptography, IEEE Trans. Information Theory (1976), 472-492

[11] M. W. Paryasto, S. Sutikno, A. Sasongko, Issues in Elliptic Curve Cryptography Implementation, Internetworking Indonesia Journal, Vol. 1, No. 1, 2009.

1. He, D., Chen, Y., Chen, J.: Cryptanalysis and improvement of an extended chaotic maps-based key agreement protocol. Nonlinear Dyn.69(3), 11491157 (2012).

2. Lee, C.C., Chen, C.L., Wu, C.Y., Huang, S.Y.: An extended chaotic maps-based key agreement protocol with user anonymity. Nonlinear Dyn.69(1), 7987 (2012).

3. Zhang, L.: Cryptanalysis of the public key encryption based on multiple chaotic systems. Chaos Solitons Fractals 37(3), 669674 (2008).

4. Kai Chain ·Wen-Chung Kuo , A new digital signature scheme based on chaotic maps, An International Journal of Nonlinear ,Dynamics and Chaos in Engineering Systems ,ISSN 0924-090X , 22 July 2013

5. Christophe Guyeuxand Jacques M. Bahi , Topological chaos and chaotic iterations Application to Hash functions ,

[17] Z. Shao. Security of a new digital signature scheme based on factoring and discrete logarithms. International Journal of Computer Mathematics, 82(10):1215-1219, 2005.

[18] S.F. Tzeng, C.Y. Yang, and M.S. Hwang.A new digital signature scheme based on factoring and discrete logarithms. International Journal of Computer Mathematics, 81(1):9-14, 2004.

[19] S. Wei. A New Digital Signature Scheme Based on Factoring and Discrete Logarithms.Progress on Cryptography, pages 107-111, 2004.

[20] M. Kapil,y. Jitendra and v. Ashish , Modified ElGamal over RSA Digital Signature Algorithm (MERDSA), International Journal of Advanced Research in Computer Science and Software Engineering, Volume 2, Issue 8, August 2012