Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks


presentation given on 19th september wednesday

Pooja Reddy

on 20 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ECDSA ALGORITHM AND IEEE 1609.2

DIGITAL SIGNATURES Message authentication protects two parties who exchange message from the third party but does not protect the two parties against each other.
Thus in situation where there is no complete trust between the sender and the receiver, something more than authentication is required.
The most attractive solution is " DIGITAL SIGNATURE ".
This is analogous to the hand signature in terms of inclusions, verification method, relationship and duplicity.
The requirements for the digital signature include:
It must be a bit pattern that depends on the message being signed.
It must be relatively easy to produce, recognize and verify the digital signature.
It must be computationally infeasible to forge a digital signature either by constructing a new message for an existing digital signature.
It must be practical to retain a copy of the digital signature the storage. INTRODUCTION Satisfying these properties the process of digital signatures is shown in the figure below: Figure 1: Digital Signature Process Figure 2 : Inclusion of keys in digital Signature Figure 3: Signing the Digest Digital Signature Schemes RSA digital signature scheme Figure 4: RSA digital signature Scheme The strength of RSA depends on the strength of the hashing algorithm used. This algorithm is prone to attacks such as key only attack, known message attack, chosen-message attack. ElGamal digital signature scheme Figure 5: ElGamal digital signature scheme Schnorr Digital Signature Scheme Figure 6 : Schnorr Digital Signature Scheme The problem with ElGamal Digital Signature Scheme is that the prime number p needs to be very large to guarantee that the discrete logarithmic problem is intractable for a given field. Digital signature Standard (DSS) Figure 7: DSS Scheme The DSS was adopted by NIST in 1994
DSS uses a DSA based on ElGamal scheme with some ideas from the Schnorr digital signature scheme.
Computation of DSS signatures is faster than the computation ofRSA signatures when using the same p
DSS signatures are smaller than ElGamal signatures because q is smaller than p. ELLIPTIC CURVE CRYPTOGRAPHY First and foremost, elliptic curves have nothing to do with ellipses.
Ellipses are formed by quadratic curves. Elliptic curves are always cubic.
Elliptic curves are called elliptic because of their relationship to elliptic integrals in mathematics.
An elliptic curve in its “standard form” is described by y^2 = x^3 + ax + b, for some fixed values for the parameters a and b.
This equation is also referred to as Weierstrass Equation
These curves are defined over finite fields. A finite field consists of a finite set of elements F together with two binary operations on F, called addition and multiplication, that satisfy certain arithmetic operations. Generally the order the field is the number of elements in the field.
If q is a prime number then there is essentially only one finite field of order q and is denoted as Fq. This field is known as prime field. If q=p^m where p is prime and m is a positive integer than p is called characteristic of Fq and m is called the extension degree of Fq.
Most of the standards that specify the ECC technique restrict the order of the finite field to be an odd prime (q=p) or a power of 2 (q=2^m) (Binary field).
If we observe the above equation we can observe that it provides the relationship between the cubic equation and the equation of a line i.e y^2 - x^3 = ax + b. From Mordell's theorem we can say that the total number of intersection points will be 3.
Given two points on the curve the third point can be found by means of the group operator, by convention called as addition (+).
Given two points P and Q we find the third point of intersection say R, by joining the points P and Q by a straight line and then the point where the line intersects the curve is the third point. The mirror image of this point with respect to the x-coordinate is P+Q. Thus we say that R = P+Q. This is shown in the figure 8. This is referred to as "Point addition "
The coordinates of the third point is given as x3 = c^2 - x1 - x2 and y3 = c(x1-x3) - y1 where c is the slope of the line given as c = (y2 - y1)/(x2-x1) in case of a prime field.
In case of a binary field the coordinates are x3={(y2+y1)/(x2+x1)}^2}+{(y2+y1)/(x2+x1)}+x1+x2+a; and y3={(y2+y1)/(x2+x1)}(x1+x3)+x3+y1.
If the third point of intersection does not exist, we say it is at infinity. This is denoted by O and this serves as an additive identity element for the group operator (i.e P + O = P). This generally happens when Q is the mirror reflection of P i.e Q = -P and the line joining P and Q becomes the tangent to the point P. This is shown in figure 9. This is referred to as "point Doubling".
In this case the coordinates of R is given as x3 = d^2 - 2(x1) and y3 = d(x1-x3) - y1 where d = (3(x1)^2+a)/2y1 for prime and x3=(x1)^2 + (b/(x1)^2) and y3 = (x1)^2 + { x1 + (y1/x1)}x3 + x3 in case of binary field.
If we define all the set of points on the curve by E(a,b), than we can say that E(a,b) is an abelian group because the operation of addition is commutative. Figure 8 : P +Q = R Figure 9 : P + P = R Given that the point P belongs to E(a,b) we can find P+P, P+P+P, P+P+P...+P for any arbitrary number of repeated invocations of the group operator.
Expressing the multiplicative group operator in terms of repeated addition i.e P+P+P+....+P = k X P for a given point it would become extremely difficult to recover k from p because of the discrete logarithmic problem.
The concept of elliptic curve over finite fields to be used in cryptography was suggested by Neal Koblitz.
Thus unlike RSA, ECC is going to deal with points and uses the addition operator. We know that the computational overhead of the RSA based approach increases with increase in the size of the key. Thus integer factorization becomes more and more efficient, RSA based methods have to handle longer and longer keys.
To overcome this problem the solution is to use ECC which provides the same type of security as RSA or Diffie hellman but with shorter keys.
The comparison of ECC and RSA is shown in the table below.
Thus we see that since ECC uses much smaller key sizes this can be employed in smart cards. Table 1: Comparison of key sizes to achieve equivalent level of security The mathematical basis for the security of elliptic curve crypto-systems is the computational intractability of the elliptic curve discrete logarithm problem (ECDLP).ECC is a relative of discrete logarithm cryptography. An elliptic curve E over Zp as in Figure 10 is defined in the Cartesian coordinate system by an equation of the form:
y^2 = x^3 + ax + b where a, b belong to Zp, and 4a^3 + 27b^2≠is not equal to 0 (mod p), together with a special point O, called the point at infinity.
The public key is a point on the curve and the private key is a random number. The public key is obtained by multiplying the private key with a generator point G in the curve. Figure 10: Elliptic Curve The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the DSA.
ECDSA was first proposed in 1992 by Scott Vanstone in response to NIST’s request for public comments on their first proposal for DSS.
It was accepted in 1998 as an ISO standard, accepted in 1999 as an ANSI standard (ANSI X9.62), and accepted in 2000 as an IEEE standard (IEEE 1363-2000) and a FIPS standard (FIPS 186-2).
Unlike the ordinary discrete logarithmic problem, or the factorization problem, ECDSA algorithm is known for elliptic curve discrete logarithmic problem (ECDLP).
The elliptic curve discrete logarithm problem can be stated as follows. Fix a prime p and an elliptic curve.
Q=xP, where xP represents the point P on elliptic curve added to itself x times. Then the elliptic curve discrete logarithm problem is to determine x given P and Q. It is relatively easy to calculate Q given x and P, but it is very hard to determine x given Q and P. It is for this reason ECDSA is used to provide security. Elliptic Curve Digital Signature Algorithm (ECDSA) Domain Parameters ECDSA requires that the private/public key pairs used for digital signature generation and verification be generated with respect to a particular set of elliptic curve domain parameters.
These domain parameters may be common to a group of users and may be public.
The domain parameters for ECDSA consist of a suitably chosen elliptic curve E defined over a finite field Fq of characteristic p and a base point G on the curve. The domain parameters consist of :
q, the size of the underlying field either q=p or q=2^m.
FR, a field representation indicator, used for the representation of the elements of Fq
a,b elliptic curve parameters
SEED which is an optional parameter, a bit string of length at least 160 bits and is used to generate the parameter b
G = (xg,yg) , is apoint in the the curve known as the base point.
n, is the order of the base point G, with n>2^160
h, is the order of the elliptic curve divided by the order of n of G i.e h=ord(E)/ord(G) The ECDSA signature scheme includes three phases
Key Generation
Signature generation
Signature Verification Key Generation In this phase we first obtain a set of elliptic curve domain parameters.
We select a random number 'd' which belongs to the interval [1,n-1]. Here d is considered as the private key.
Then we compute the public key Q = dG
Thus the private key is 'd' and the public key is (E,Q,G,n). Signature Verification Input : Message m and (d,Q)
1. Select a random number k [1,n −1]
2. Compute kG = (x1, y1) and r=x1 mod n if r = 0 goto 1
3. Compute s = k^(−1)(e + d × r) mod n with e = H(m) if s=0 goto 1
4. The signature of m is (r,s). Signature Generation input: (r,s), m, Q
1. Verify r, s [1,n −1]
2. Compute w = s^(−1) modn
3. Compute u1 = e × w modn and u2 = r × w modn with e = H(m)
4. Compute X1 = u1G + u2Q and V = X1 modn
5. If V = r then signature accepted. Start Get elliptic curve domain parameters Select the Private Key 'd' in the range [1,n-1] Compute the public key Q = dG Input : Message m and private d and public key Q Select k Compute kG=(x1,y1) and r=x1modn Compute s = k^(−1)(e + d × r) mod n Output message and signature (r,s) r = 0 s = 0 yes no yes no 1< r, s < n −1 Compute w = s^(−1) modn u1 = e × w modn
u2 = r × w modn with e = H(m) X1 = u1G + u2Q
V = X1 modn V = r ACCEPT REJECT Input: (r,s), m, Q If a signature (r, s) on a message m was indeed generated by the sender, then s=k^(−1)(H(m)+dr)(mod n).
Rearranging gives k=s^(−1)(H(m)+dr) (mod n)
=> kG=s^(−1)(H(m)+dr) G(mod n)
kG= (s^(−1)H(m)G+s^(−1)rdG) (mod n)
But we know that w=s^(-1)modn and Q = dG,
thus rearranging the above equation we get
(kG)modn= H(m)wG + rwQ (mod n)
(KG)modn= u1G+u2Q (mod n).
But r = (KG)modn and v = u1G+u2Q(modn) ,
so v = r as required. VERIFICATION OF THE ALGORITHM We start by selecting the domain parameters.
Domain parameters
Elliptic curve coefficients: a=1, b=1
Elliptic curve base point: g(13,7)
Order of elliptic curve base point G : n = 7 (since 7G =O, a point at infinity)
Co factor h =4 (h= N/n; curve has a total of N = 28 points)

Key – pair Generation
Select random number d in the range [1,n-1] = [1,6], say d=4.
Compute point Q = dG = 4G = 2(2G) =4(13,7)=2(2(13,7))=2(5,4)=(17,20).
Here d =4 is a private key and point Q = (17,20 ) is a public key.

Signature Generation
Select random number K in the range [1,n-1] = [1,6], say d=4.
Compute point (x1,y1) =kG = 3G =G+2G = 3(13,7) =(13,7) + 2(13,7) = (13,7) + (5,4) = (17,3); R = x1 (modn)=17mod7 =3.
Let us assume for now that the message digest value ‘e’ of the given message M is equal to 5. then, s= k^(-1)(e=dr)(modn)=1.
Signature is (r,s)=(3,1).
We send the message M along with its signature (3,1) to the recipient. An Example Of ECDSA Algorithm Signature verification
At the recipient, we have message M along with its signature (r,s)=(3,1). We compute the message digest value e for message M again for signature verification and e =5 (same as what we computed, or assumed, in signature generation).
w = s^(-1)(modn) = 1
U1 = e*w(modn) =5*1(mod 7) = 5
U2 = r*w(modn)=3*1(mod7)=3
(x1,y1)=u1G+u2Q = 5(13,7)+3(17,20)=(5,19)+(5,19)=2(5,19)=(17,3)
V=x1modn = 17mod 7 =3
Since v=r, the signature is valid and we accept the message, because the integrity of the message is maintained during transmission. ADVANTAGES OF ECDSA It provides greater security for a given key size.

It provides effective and compact implementations for cryptographic operations requiring smaller chips.

Due to smaller chips less heat generation and less power consumption.

It is mostly suitable for machines having low bandwidth, low computing power, less memory.

It has easier hardware implementations FUTURE SCOPE We have observed that ECDSA algorithm focuses only on the authentication part of security. But in today’s scenario both privacy and confidentiality play a vital role.
The concept of privacy can be included by means of the concept of pseudo names.
The concept of confidentiality is possible by means of using some encryption techniques. Intelligent transportation system (ITS) has provided a set of standards for vehicular communication with main focus on development of safety, Traffic efficiency and infotainment related applications.
Some of the popular architectures of VANETS are WAVE by IEEE, CALIM by ISO C2CNet by GeoNet and many more. VANET Architecture and Protocol stack WAVE – Wireless Access in Vehicular Environments IEEE introduced a complete protocol stack of 1609 protocol family and named it WAVE.

This standard is further divided into the following sub-standards.

P1609.1, Resource Manager supports DSRC applications using the IEEE 802.11a communication technology

P1609.2, Create an Application Services (Layer 7) standard for 5.9 GHz DSRC applications

P1609.3, IP Network Services-Support multiple protocol stacks, one for the traditional DSRC, one for streaming audio/video, and another for TCP/IP

P1609.4, Medium Access Control (MAC) Extension Services IEEE P1609.2-Security Services for Applications and Management Messages This standard specify the security services that are optimized for the vehicular environment.
This includes sending and receiving of signed, encrypted or both the messages.
The wave architecture is as shown in the figure.
The entities within the architecture are going to communicate by means of service access points.
The security sub-system maintains security related information for the higher layers and for the WME (Wave Management Entity) in a series of SDS (Security Data Stores).
The Security subsystem also maintains security related information that is of relevance to the entire security subsystem in a global SDS.
Each device has a CME (Certificate Management Entity) which is responsible for communication with CA (Certificate Authority) for processing security management messages. Certificate Hierarchy The certificate authority issues the digital certificate. The digital certificate consists of at least one public key and a list of permissions associated with the public key.
The entity using the private key is referred to as certificate subject.
The entity that issues the certificate or CRL is referred to as certificate authority (CA).
The entities that send message using 1609.2 are referred to as end entities. They are four different types of CA and three different types of entities as shown in the figure.
Communication between an end entity an CA involves two certificates.
1. CA certificate
2. Certificate Signing Request (CSR) Root CA Message CA WSA CA Identified not localized Identified WSA Signer PSID and SSP Identifier Geographic Region PSID, SSP and Priority PSID and Priority PSID Permitted Subject Types Certificate hierarchy and permissions fields for communications certificates CA End
entities IEEE P1609.2 The 1609.2 system is intended to support a range of applications, including low latency safety-of-life communications between vehicles, improvised traffic flow.
This system is designed to provide industry strength, standards- based, bandwidth optimized cryptographic communications security for individual messages to support broad cast of safety messages
Since bandwidth is more constrained over the 5.9 Ghz airlink than internet, the designers choose to design security mechanism rather than reuse the existing system.
This is used for WSA's for broadcast application and for unicast application with a small number of message exchanges
If an application needs to communicate with a server over internet, the application may need to support a standard internet security protocol. One such protocol is ECDSA.
An assumption made in 1609.2 is that the device needs to provide a minimum of 95% accuracy in time. CONCLUSION WAVE is not flexible in terms of MAC and PHY as the only option in this layer is 802.11p. This focuses more on short range communication and every vehicle must have a 802.11p interface.
Though this restricts the degree of freedom open simulators assist researchers to use other options at the MAC layer.
Further research has been conducted on this architecture and the solutions to overcome the flaws have been found. THANK YOU REFERENCES IEEE, “IEEE Trial-Use Standard for Wireless Access in Vehicular Environments - Security Services for Applications and Management Messages,” IEEE Std 1609.2, 2011.
Koblitz N., “Elliptic Curve Cryptosystems”, Mathematics of Computation, vol. 48, 1987.
Johnson D., Menezes A., Vanstone S., “The Elliptic Curve Digital Signature Algorithm (ECDSA)”, International Journal of Informatics Security, vol. 1, no. 1,pp. 36-63, 2001
Petit . J,"Analysis of ECDSA Authentication Processing in VANETs ",IEEE conference publication
S. Manvi, M. Kakkasageri, and D. Adiga, “Message authentication in vehicular ad hoc networks: Ecdsa based approach,” in Future Computer and Communication, 2009. ICFCC 2009. International Conference on, april 2009, pp. 16 –20.
Subhashree Behera, Bharati Mishra, Priyadarshini Nayakand Debasish Jena,A Secure and Efficient Message Authentication Protocol for Vehicular Ad Hoc Networks with Privacy Preservation(MAPWPP),IEEE,2011
Hu Junru, The Improved Elliptic Curve Digital Signature Algorithm,2011 International Conference on Electronic & Mechanical Engineering and Information Technology
Elliptic curve and elliptic curve DSA, wikipedia
Cryptography and network security by, B. Forouzan
Digital Media Processing: DSP Algorithms Using CBy Hazarathaiah Malepati
Full transcript