 Open Access
 Total Downloads : 201
 Authors : Abdalla Adel, Rashad Elhabob, Ma’Moun Omer, Dr. Hwida Elshoush
 Paper ID : IJERTV3IS110591
 Volume & Issue : Volume 03, Issue 11 (November 2014)
 Published (First Online): 18112014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Survey on NPHard 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 publickey 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 publickey scheme, and it provides:

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

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

Nonrepudiation (the assurance that an entity cannot deny commitments).
Generally, every publickey digital signature schemes is based on a mathematical problem. This problem is known as NP (Nondeterministic 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, publickey 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 ecommerce and egovernment 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 publickey digital signature schemes depending on the NP mathematical hard problem [4]

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 .

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

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].

The RSA Digital Signature Algorithms:

Key generation algorithm (generated by receiver)

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

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

Compute the (n), as follows: (n) = (p1) (q1).

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

Compute the private key d, such as d = e1mod (n).

Send the public (n, e).


Signature and verification algorithms:

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

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

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


Verification (receiver):



Obtain the keys (d, n).

Obtain s, m from Alice.

Compute u as follows: u = se mod n.

Verify the message m as follows: is m= u1?.


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 oneway function [10]. That marked the inception of the Discrete Logarithm Problem in cryptography. For the purpose of this study, we may think of a oneway 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.

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].

The DSA Algorithms:

Key generation algorithm (generated by receiver)

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

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

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

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

Compute y as follows: y = gxmod p.

Send (p, q, g, and y)


Signing and verifying algorithms

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

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

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

Compute s as follows: s = ((k1) (SHA1(m) + x r)) mod q.

The signature is (r, s).

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

k1 is a multiplicative inverse of k in Zq.


Verifying (receive)


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

w = s1 mod q.

u1 = ((SHA1(m)) w) mod q.

u2 = (r w) mod q.

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

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


DIGITAL SIGNATURE BASED ON ELLIPTIC
CURVE
Elliptic Curve provides publickey primitives using much shorter key lengths for a given security level than other cryptosystems such as RSA, Digital Signature Algorithm (DSA), or DiffieHellman. 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]

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.

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,.,p1} with the following arithmetic operations:

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

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

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


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,, m1 in F2m such that each element can be uniquely written in Equation (1):
= a0 0+a1 1+.+am1 m1, where ai {0,1}(1)
Such a set {0, 1,, m1} is called a basis of F2m over F2. Given such a basis, a field element can be represented as the bit string (a0 a1 .+am1) 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.


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

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

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

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

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)

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

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

the cofactor h= E(Fq)/n.


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.

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.

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

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


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).

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

Compute [M]P and treat the rcoordinate as integer im.

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

Compute s1 = K1(H(M)+Ks0) (mod(P)) . if s1 = 0 go to step 1.

return (s0, s1).


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.

Set r = False.

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

Compute t0 = s11s0(mod(P)) , t1 = s11H(M) (mod(P)).

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

if T 0 then

Treat the xcoordinate of T as an integer iT.

if s0 iT (mod(P)) then

r = True.

end

end

end

return r.




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, Sboxes, and hash functions. Recently, chaotic systems have also been used for key agreement schemes [13][14][15].

Chaotic maps problems:
Let P and Q be integers and p be prime. The general secondorder linear recurrence relation is in this Equation (2):
Ta (M) = P Ã—Ta1(M) +QÃ—Ta2(M) (a 2) (2)

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

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

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

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

Signature Verification Phase:
i=1 i
secondorder linear recurrence relation as defined in previous equation, with P = M and Q=1.
The Chebyshev polynomials exhibit the following two important properties:

The semigroup 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].

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.


Anew digital signature algorithm based on chaotic maps:
Kai Chain and WenChung Kuo propose a new Digital Signature Algorithm and give implementation of a digital signature algorithm based on both cryptographic and chaotic system characteristics [15].

System Parameters
First there will be exploring for system parameters as follow:

p(.) is a strong oneway 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 oneway hash function whose output is a vector which has t elements and every element belongs to {0,1}.

p(, ) is a strong oneway 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 np1

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.


Users Keys Generation Phase

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

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


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

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

If p(M,K) = 0, then go to Step 1 and select another random number R; otherwise go to Step 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.


DIGITAL SIGNATURE BASED ON TWO NPHARD
PROBLEMS
The securities of digital signature algorithms are based on the difficulty of solving some NPhard 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].

MERDSA:
KapilMadhur and others propose Modified ElGamal over RSA Digital Signature Algorithm (MERDSA)[20] proposed digital signature algorithms based on two hard problemsthe 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:

Key Generation

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.

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

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

Choose a primitive root g inZp .

Calculate (n) = (p1 1) Ã— (q1 1).

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

Calculate d such that d Ã— e mod (n) = 1.

Calculate c such that bx Ã— c(mod)n = 1.

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

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


Signature Generation:

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.

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).


Signature Verification

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

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



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.


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 publickey 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 NPhard 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

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

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

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

M. Ahmad , Comparison Study On NpHard Problem Based Digital Signature Schemes , International Science and Technology Conference, Istanbul, 79 December 2011.

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. 5559, 5(2) (2011).

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 5th9th , 2010.

GunjanJain , Digital Signature Algorithm, International Journal of Innovations in Computing, (ISSN : 23198257) Vol. 1 Issue 1

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

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): 222225, 2008

Diffie, W. and Hellman, M., New Directions in Cryptography, IEEE Trans. Information Theory (1976), 472492

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

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

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

Kai Chain Â·WenChung Kuo , A new digital signature scheme based on chaotic maps, An International Journal of Nonlinear ,Dynamics and Chaos in Engineering Systems ,ISSN 0924090X , 22 July 2013

Christophe Guyeuxand Jacques M. Bahi , Topological chaos and chaotic iterations Application to Hash functions ,
[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