Elliptic Curve Cryptograpy
DSA Scheme

José de Jesús Angel Angel
CINVESTAV-IPN
México

This report shows how work the DSA Scheme using elliptic curves over a prime field. The DSA scheme is taken  from the document SEC1:Elliptic Curve Cryptography  Version 1.5, Working Draft February 18, 2005. (Standards for Efficient Cryptography). The main intention is to give a didactic way of the ECDSA. DSA is a signature scheme with appendix based on ECC.

Elliptic Curve  Primitives

The following functions are used to build some elliptic curve cryptographic  schemes.

This function accept  a point P={x,y},  and a prime number  p, the function gives the  point  {x mod p, y mod p}.

P[P_, 
        p_] := 
Module[{Q}, 
Q = {Mod[
              P[[1]], p], 
            Mod[P[[2]], p]}; 
Q]

The function Neg,  gives  the negative point -P={x, -y}, where P={x,y} is in  E((Subscript[𝔽, p])).

Neg[P_, 
        p_] := 
Module[{Q}, 
If[
          TrueQ[P == 𝒪], Q = 𝒪,  
          Q = {P[[1]], 
              Mod[-P[[2]], 
                p]} ]; 
Q]

This function sums two points P, Q  in E((Subscript[𝔽, p])),  the number a  comes  from  of the curve (y^2) = (x^3) + a x+b.

AddPoints[P_, Q_, p_, 
        a_] := 
Module[{λ, X3, Y3, 
          R}, 
If[
          P == 𝒪 ,   R = Q; 
          Return[R]]; 
If[
          Q == 𝒪 ,   R = P; 
          Return[R]]; 
If[
          P == Neg[Q, p] ,   R = 𝒪;  
          Return[R]]; 
If[
          TrueQ[P == 
              Q], λ = (3 P[[1]]^2 + a) (PowerMod[
                  2 P[[2]], -1, p]),  λ = (Q[[2]] - 
                  P[[2]]) (PowerMod[Q[[1]] - P[[1]], -1, 
                  p])]; 
λ = 
          Mod[λ, p]; 
X3 = 
          Mod[(λ^2) - P[[1]] - Q[[1]], 
            p]; 
Y3 = 
          Mod[λ (P[[1]] - X3) - P[[2]], 
            p]; 
R = {X3, 
            Y3}; 
R]

The  following  function gives  kP, where P is a point in  E((Subscript[𝔽, p])) and k is an integer greater of 1.

kP[P_, k_, p_, 
        a_] := 
Module[{binexp, len, H, 
          j}, 
Clear[H, j, len, 
          binexp]; 
binexp = IntegerDigits[k, 2]; 
        len = Length[binexp]; 
        H = P; 
For[j = 2, j ≤ len, 
          H = AddPoints[H, H, p, a]; 
          If[binexp[[j]] == 1, 
            H = AddPoints[H, P, p, 
                a]]; j++]; 
H]

The following examples show as function  kP works.

p = 2^192 - 2^64 - 1

r = 16^^ffffffffffffffffffffffff99def836146bc9b1b4d22831

b = 
      16^^64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1

X = 
      16^^188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012

Y = 
      16^^07192b95ffc8da78631011ed6b24cdd573f977a11e794811

kP[{X, Y}, 2, p, -3]

kP[{X, Y}, r + 2, p, -3]

kP[{X, Y}, 7, p, -3]

kP[{X, Y}, r + 7, p, -3]

Elliptic Curve Domain Parameters

The  elliptic curve domain parameters over  (Subscript[𝔽, p]) are a sextuple:  T=(p,a,b,G,n,h). Consisting of an integer p specifying the finite field (Subscript[𝔽, p]), two elements  a,b in (Subscript[𝔽, p]) specifying an elliptic curve E((Subscript[𝔽, p])) defined by the equation E:(y^2)=(x^3)+a x+b  (mod p), a  base point G=(x,y) on E((Subscript[𝔽, p])), a prime n which is the order of G, and an integer h which is the cofactor h=#E((Subscript[𝔽, p]))/n.

There exist a primitive to generate an elliptic curve domain parameters, or select one of the stardar T=(p,a,b,G,n,h) given in the satandar FIPS  186-2 or SEC 2.

FIPS  186-2,  Recommended Elliptic Curve Domain Parameters:

p192 = 
        2^192 - 2^64 - 1;

    x1 = 
        16^^188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012;

    y1 = 
        16^^07192b95ffc8da78631011ed6b24cdd573f977a11e794811;

    G1 = {x1, y1};

    a1 = -3;

    b1 = 
        16^^64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1;

    n1 = 
        16^^ffffffffffffffffffffffff99def836146bc9b1b4d22831;

    h1 = 1;

p224 = 
        2^224 - 2^96 + 1;

    x2 = 
        16^^b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21;

    y2 = 
        16^^bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34;  

    G2 = {x2, y2};

    a2 = -3;

    b2 = 
        16^^b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4;

    n2 = 
        16^^ffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d;

    h2 = 1;

p256 = 
        2^256 - 2^224 + 2^192 + 2^96 - 1;

    x3 = 
        16^^6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296;

    y3 = 
        16^^4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5;

    G3 = {x3, y3};

    a3 = -3;

    b3 = 
        16^^4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5;

    n3 = 
        16^^ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551;

    h3 = 1;

p384 = 
        2^384 - 2^128 - 2^96 + 2^32 - 1;

    x4 = 
        16^^aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7;

    y4 = 
        16^^3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f;

    G4 = {x4, y4};

    a4 = -3;

    b4 = 
        16^^b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef;

    n4 = 
        16^^ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973;

    h4 = 1;

p521 = 2^521 - 1;

    x5 = 
        16^^c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66;

    y5 = 
        16^^11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650;

    G5 = {x5, y5};

    a5 = -3;

    b5 = 
        16^^051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00;

    n5 = 
        16^^1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409;

    h5 = 1;

HexDigits[
      1461501637330902918203684832716283019651637554291]

SEC 2: Recommended Elliptic Curve Domain Parameters Ver.1.0: (two)

p160k1 = 
        2^160 - 2^32 - 2^14 - 2^12 - 2^9 - 2^8 - 2^7 - 2^3 - 2^2 - 
          1;
x6 = 
        16^^3b4c382ce37aa192a4019e763036f4f5dd4d7ebb;
y6 = 
        16^^938cf935318fdced6bc28286531733c3f03c4fee;
G6 = {x6, y6};
a6 = 0;
b6 = 7;
n6 = 
        16^^00000000000000000001b8fa16dfab9aca16b6b3;
h6 = 1;

p160r1 = 2^160 - 2^31 - 1;
X = 
        16^^4a96b5688ef573284664698968c38bb913cbfc82;
Y = 
        16^^23a628553168947d59dcc912042351377ac5fb32;
G = {X, Y};
a = 
        16^^ffffffffffffffffffffffffffffffff7ffffffc;
b = 
        16^^1c97befc54bd7a8b65acf89f81d4d4adc565fa45;
n = 
        16^^00000000000000000001f4c8f927aed3ca752257;
h = 1;

Elliptic Curve Key Pair Generation Primitive

In this part are given the functions to generate an elliptic curve key pair, we supose have a valid elliptic curve domain parmeters T=(p,a,b,G,n,h).

This funtion select an integer d in the interval [1,r-1]

PrivateKey[
        n_] := 
Module[{PK}, 
SeedRandom[]; 
PK = 
          Random[Integer, {2, n - 2}]; 
PK]

n = 
      16^^ffffffffffffffffffffffff99def836146bc9b1b4d22831

PrivateKey[n]

This function generate the  Key  pair i.e.  the Public Key   Q=dG, with the Private Key d.

KeyPair[P_, p_, a_, 
        n_] := 
Module[{K, d}, 
d = 
          PrivateKey[n]; 
K = 
          kP[P, d, p, a]; 
{K, d}]

X = 
      16^^188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012

Y = 
      16^^07192b95ffc8da78631011ed6b24cdd573f977a11e794811

p = 2^192 - 2^64 - 1

KeyPair[{X, Y}, p, -3, r]

The next example is from GEC-2  document  for   Test Vectors for ECDH part with the  domain parameters secp160r1.

p = 2^160 - 2^31 - 1;
G = {X, Y};
X = 
        16^^4a96b5688ef573284664698968c38bb913cbfc82;
Y = 
        16^^23a628553168947d59dcc912042351377ac5fb32;
a = 
        16^^ffffffffffffffffffffffffffffffff7ffffffc;
b = 
        16^^1c97befc54bd7a8b65acf89f81d4d4adc565fa45;
n = 
        16^^00000000000000000001f4c8f927aed3ca752257;
h = 1;

d = 
      971761939728640320549601132085879836204587084162

HexDigits[d]

Q = kP[G, d, p, a]

The last Public Key Q, agrees with the public key given in the  document  GEC-2 page 45.

Hash Function SHA1

The  SHA1 Hash function. 
This code is only used for short messages.  A message have to had less of the 512 bits of length. The messages can be a string  Sha1["string"] or an octet string  Sha1[16^^616263abc].

Ch[x_, y_, 
        z_] := 
Module[{S}, 
S = 
          BitOr[BitAnd[x, y], 
            BitAnd[BitNot[x], z]]; 
S]

Parity[x_, y_, 
        z_] := 
Module[{S}, 
S = 
          BitXor[BitXor[x, y], z]; 
S]

Maj[x_, y_, 
        z_] := 
Module[{S}, 
S = 
          BitXor[BitXor[BitAnd[x, y] , BitAnd[x, z]], 
            BitAnd[y, z]]; 
S]

HexDigits[b_] := 
      Module[{s = ToString[BaseForm[b, 16]]}, 
        StringDrop[
          s, {Part[StringPosition[s, "\n"], 1, 
              1], -1}]]

Padding[
        A_] := 
Module[{S1, W1, i, 
          j}, 
If[IntegerQ[A],  
          S1 = IntegerDigits[A, 256], 
          S1 = ToCharacterCode[A]]; 
l = 
          Length[S1]; 
W1 = 
          Table[0, {i, 16}]; 
For[i = 1,  
          i < Floor[l/4] + 1, 
W1[[i]] = 
            16^6*S1[[(i - 1)*4 + 1]] + 
              16^4*S1[[(i - 1)*4 + 2]] + 
              16^2*S1[[(i - 1)*4 + 3]] + 
              S1[[(i - 1)*4 + 
                    4]];   
i++]; 
For[j = 1, 
          j < Mod[l, 4] + 1, 
W1[[i]] = 
            W1[[i]] + (16^(8 - 2*j)*
                  S1[[((i - 1)*4 + 
                          j)]]); 
  j++]; 
W1[[i]] = 
          W1[[i]] + (2^((5 - j) 8 - 
                    1)); 
W1[[16]] = 
          l*8; 
W1]

S[A_, 
        n_] := 
Module[{S, S1, S2, 
          l}, 
S = IntegerDigits[A, 2]; 
        l = Length[S]; 
If[l < 32,  
          Do[S = Insert[S, 0, 1], {32 - l}]]; 
S1 = 
          RotateLeft[S, n]; 
        S2 = FromDigits[S1, 2]; 
S2]

\(\(\(
\)\(Sha1[A_] := 
      Module[{temp, W, H, i, a, b, c, d, e}, 
W = 
          Padding[A]; 
For[t = 17, \ 
          t < \((80 + 1)\), \ 
W = 
            Append[W, 
              S[BitXor[W[\([t - 16]\)], W[\([t - 14]\)], W[\([t - 8]\)], 
                  W[\([t - 3]\)]], 
                1]]
; \(t++\)]; 
h0 = 
          1732584193; \ \  (*67452301*) 
\ \ \ \ \ h1 = 
          4023233417; \ \  (*efcdab89*) 
\ \ \ \ \ h2 = 
          2562383102; \ \  (*98  badcfe*) 
\ \ \ \ \ h3 = 
          271733878; \ \  (*10325476*) 
\ \ \ \ h4 = 
          3285377520; \ \  (*c3d2e1f0*) 
a = h0\ ; 
        b = h1\ ; c = h2\ \ ; d = h3\ \ ; 
        e = h4\ ; 
For[i = 1, \ 
          i < 81, 
If[0 < i < 21, f = Ch[b, c, d]; 
            k = 1518500249, \ 
If[20 < i < 41, \ 
              f = Parity[b, c, d]; 
              k = 1859775393, \ 
If[40 < i < 61, \ 
                f = Maj[b, c, d]; 
                k = 2400959708, \ \ 
If[60 < i < 81, \ 
                  f = Parity[b, c, d]; 
                  k = 3395469782, \ \ 
]]]]; 
temp = 
            S[a, 5] + f + e + W[\([i]\)] + k; 
temp = 
            Mod[temp, 2^32]; 
e = d; 
d = 
            c\ ; 
c = S[b, 30]; 
b = 
            a; 
a = 
            temp;
\ ; \(i++\)]; 
H0 = 
          Mod[h0 + a, 2^32]; 
H1 = 
          Mod[h1 + b, 2^32]; 
H2 = 
          Mod[h2 + c, 2^32]; 
H3 = 
          Mod[h3 + d, 2^32]; 
H4 = 
          Mod[h4 + e, 2^32]; 
H = 
          H0*2^\((128)\) + H1*2^\((96)\) + H2*2^\((64)\) + H3*2^\((32)\) + 
            H4; 
\  (*\(Print["Hash hexadecimal = ", \ 
              HexDigits[H0], HexDigits[H1], HexDigits[H2], HexDigits[H3], 
              HexDigits[H4]];\)\ *) 
H]\)\)\)

Sha1["abc"]

Sha1["a"]

Sha1["The quick brown fox jumps over the lazy dog"]

Sha1["The quick brown fox jumps over the lazy cog"]

Sha1[""]

Sha1["Jose de Jesus Angel Angel"]

Test Vector from the document  GEC-2: Test Vector for SEC1,  page 47.  CA7C0F8C 3FFA87A9 6E1B74AC 8E6AF594 347BB40A 00000001

Sha1[16^^ca7c0f8c3ffa87a96e1b74ac8e6af594347bb40a00000001]

Elliptic Curve Digital Signature Scheme

The elliptic curve Digital Signature Scheme is a signature scheme with appendix  based on ECC. It is designed to be existentially unforgeable , even in the presence of an adversary capable of launching chosen-message attacks. The scheme consist in three parts, Scheme Setup, Key Deployment,  Signing Operation, Varifying Opetarion and alternative Verifying Operation.

Scheme Setup:  Entities U and V should perform the following setup procedure to prepare to use ECDSA  scheme.

1.- U  should establish which of the hash functions supported to use when generating signatures. Let Hash denote the hash function chosen, and hashlen denote the length on octets of the hash values produced using Hash.

2.- U and V should establish  elliptic curve domain parameters T=(p,a,b,G,n,h), or (m,f(x),a,b,G,n,h) at the desired security level. The elliptic curve domain parameters T should be generated using the primitives specified in section 3.1.1.1 or 3.1.2.1 in the SEC 1 Standard. U should receive an assurance that the  elliptic curve domain parameters T are valid using one of the methods specified in section 3.1.1.2 or 3.1.2.2 in the SEC 1 Standard.

3.- V should  obtain in an authentic manner the hash function Hash and elliptic curve domain parameters T established by U, also V wish to must receive an assurance that the elliptic curve domain parameters T are valid using one of the methods specified in section 3.1.1.2 or 3.1.2.2 of the SEC 1 Standard.

The example is taken of the document  GEC 2: Test Vectors for SEC 1,Test Vectors for ECDSA, Example Using Elliptic Curve Domain Parameters over (Subscript[𝔽, p]). This example uses the domain The elliptic curve domain parameters secp160r1 as specified in   SEC 2: Recommended Elliptic Curve Domain Parameters.

p = 2^160 - 2^31 - 1;
X = 
        16^^4a96b5688ef573284664698968c38bb913cbfc82;
Y = 
        16^^23a628553168947d59dcc912042351377ac5fb32;
G = {X, Y};
a = 
        16^^ffffffffffffffffffffffffffffffff7ffffffc;
b = 
        16^^1c97befc54bd7a8b65acf89f81d4d4adc565fa45;
n = 
        16^^00000000000000000001f4c8f927aed3ca752257;
h = 1;

Key Deployment:  Entities U and V should perform the following  key deployment procedure to prepare to use ECDSA.

1.- U should establish an elliptic curve key pair ((Subscript[d, U]),(Subscript[Q, U])) associated with the elliptic curve domain parameters T established during the setup procedure, to use with the signature scheme. The key pair should be generated using the primitive specified in section 3.2.1 of the SEC 1 Standard.

du = 
      971761939728640320549601132085879836204587084162
HexDigits[du]

Qu = kP[G, du, p, a]

2.- V should obtain in an authentic manner that the elliptic curve public key (Subscript[Q, U]) selected by U.

3.- V may wish to must receive an assurance that the elliptic curve public key (Subscript[Q, U]) is valid using one the following methods:

There are four acceptable methods for validation of elliptic curve public key:
a.-  Entity U performs validation of the elliptic curve public key with the next primitive:

Validate[Q_, p_, a_, 
        b_] := 
Module[{XQ, YQ}, 
If[
          Q == 𝒪 ,  
          Return["invalid"]]; 
XQ = 
          Q[[1]]; 
YQ = 
          Q[[2]]; 
If[(1 < XQ < p - 1) && (1 < 
                YQ < p - 1) && (PowerMod[YQ, 2, p] == 
                Mod[PowerMod[XQ, 3, p] + Mod[a*XQ, p] + b, p]),  
          Return[True]];
]

(b.- Entity U  generates the elliptic curve public key itself using a trusted system.)

(c.- Entity U receives assurance in an authentic manner that a party trusted with respect to U´s use of the elliptic curve public key has performed validation of the public key using the method a.)

(d.- Entity U receives assurance in an authentic manner that a pary trusted with respect to U´s use of the elliptic curve piblic generate the public key using a trusted system.)

Validate[Qu, p, a, b]

Signing Operation:  Entities U should sign a messages using ECDSA  using the keys and parameters established during the setup procedure and the deployment procedure as follows:

Input: An  octet string M which is the message to be signed.
Output: A signature S=(r,s) on M consisting of a pair of integers r and s,   or "invalid".

1.- U select an ephemeral elliptic curve key pair  (k,R) with R=(XR, YR) associated with the elliptic curve domain parameters T established during the setup procedure using the key pair generation primitive specified in the standard SEC1.

k = 
      702232148019446860144825009548118511996283736794

R = kP[G, k, p, a]

2.- Convert the field element XR to an integer using the conversion routine specified in SEC1.

XR = R[[1]]

3.- Set  r = XR mod n. If r = 0, return to step 1.

r = Mod[XR, p]
HexDigits[r]

4.- Use the hash function selected during the setup procedure to compute the hash value  H=Hash(M) of the length hashlen octets. If the hash output "invalid" output "invalid" and stop.

5.-      Derive an integer e from H as follows:
5.1.-   Convert the octet string H to a bit string H' using the conversion routine specified in the standard SEC1.
5.2.-   Set E'=H' if  Ceiling[(Subscript[Log, 2]) n] >= 8(hashlen),  and set E' equal to the leftmost (Subscript[Log, 2]) n  bits of H' if Ceiling[(Subscript[Log, 2]) n] < 8(hashlen).
5.3.-  Convert the bit string E' to an octet string E using the conversion routine  specified in the standard SEC1.
5.4.-  Convert the octet  string E to an integer  e using the conversion routine  specified in the standard SEC1.

M = "abc"
Sha1[M]
HexDigits[Sha1[M]]

e = Sha1[M]

6.-  compute  s = k^(-1) ( e + du  r ) mod n

p = 2^160 - 2^31 - 1;

    n = 
        16^^0100000000000000000001F4C8F927AED3CA752257;

    k = 
        702232148019446860144825009548118511996283736794;

    e = 
        968236873715988614170569073515315707566766479517;

    du = 
        971761939728640320549601132085879836204587084162;

    r = 
        1176954224688105769566774212902092897866168635793;

    kinv = PowerMod[k, -1, n];

    s = Mod[kinv (e + du* r), n]

If  s = 0,  return to step 1.

7.- Output  S=(r , s)

r
s

Verifying  Operation:  Entities V should verify signed  messages from entity U  using ECDSA  using the keys and parameters established during the setup procedure and the deployment procedure as follows:

Input:  An octet string M which is the message, and  U's purported signature S = (r,s) on M.
Output:   And indication of whether the purported signature on M is "valid" or "invalid".

1.-  If r and s are not both integers in the interval [1,  n-1], output  "invalid" and stop.

2.- Use the hash function selected during the setup procedure to compute the hash value  H=Hash(M) of the length hashlen octets. If the hash output "invalid" output "invalid" and stop.

3.-      Derive an integer e from H as follows:
3.1.-   Convert the octet string H to a bit string H' using the conversion routine specified in the standard SEC1.
3.2.-   Set E'=H' if  Ceiling[(Subscript[Log, 2]) n] >= 8(hashlen),  and set E' equal to the leftmost (Subscript[Log, 2]) n  bits of H' if Ceiling[(Subscript[Log, 2]) n] < 8(hashlen).
3.3.-  Convert the bit string E' to an octet string E using the conversion routine  specified in the standard SEC1.
3.4.-  Convert the octet  string E to an integer  e using the conversion routine  specified in the standard SEC1.

4.- Compute  u1= e s^{-1} mod n  and  u2= r s^{-1} mod n.

sinv = PowerMod[s, -1, n];
u1 = Mod[e*sinv, n]
u2 = Mod[r*sinv, n]

5.- Compute  R= (XR, YR) = u1G + u2 (Subscript[Q, U])

u1G = kP[G, u1, p, a]

Qu = kP[G, du, p, a]

u2Qu = kP[Qu, u2, p, a]

R = AddPoints[u1G, u2Qu, p, a]

If  R= 𝒪, output "invalid" and stop.

6.-  Convert the field  element XR to an integer XR' using the conversion routine specified in the standard SEC1.

7.- Sea v = XR' mod n.

v = R[[1]]

8.- Compare v and  r. If  v = r, output  "valid", if  v != r, output "invalid".

r == v