ecdsa.c

00001 /**
00002  * @file ecdsa.c
00003  * @brief ECDSA (Elliptic Curve Digital Signature Algorithm)
00004  *
00005  * @section License
00006  *
00007  * Copyright (C) 2010-2017 Oryx Embedded SARL. All rights reserved.
00008  *
00009  * This file is part of CycloneCrypto Open.
00010  *
00011  * This program is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU General Public License
00013  * as published by the Free Software Foundation; either version 2
00014  * of the License, or (at your option) any later version.
00015  *
00016  * This program is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  * GNU General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU General Public License
00022  * along with this program; if not, write to the Free Software Foundation,
00023  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00024  *
00025  * @author Oryx Embedded SARL (www.oryx-embedded.com)
00026  * @version 1.7.6
00027  **/
00028 
00029 //Switch to the appropriate trace level
00030 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
00031 
00032 //Dependencies
00033 #include <stdlib.h>
00034 #include "crypto.h"
00035 #include "ecdsa.h"
00036 #include "mpi.h"
00037 #include "asn1.h"
00038 #include "debug.h"
00039 
00040 //Check crypto library configuration
00041 #if (ECDSA_SUPPORT == ENABLED)
00042 
00043 //ECDSA with SHA-1 OID (1.2.840.10045.4.1)
00044 const uint8_t ECDSA_WITH_SHA1_OID[7] = {0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x04, 0x01};
00045 //ECDSA with SHA-224 OID (1.2.840.10045.4.3.1)
00046 const uint8_t ECDSA_WITH_SHA224_OID[8] = {0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x04, 0x03, 0x01};
00047 //ECDSA with SHA-224 OID (1.2.840.10045.4.3.2)
00048 const uint8_t ECDSA_WITH_SHA256_OID[8] = {0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x04, 0x03, 0x02};
00049 //ECDSA with SHA-384 OID (1.2.840.10045.4.3.3)
00050 const uint8_t ECDSA_WITH_SHA384_OID[8] = {0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x04, 0x03, 0x03};
00051 //ECDSA with SHA-512 OID (1.2.840.10045.4.3.4)
00052 const uint8_t ECDSA_WITH_SHA512_OID[8] = {0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x04, 0x03, 0x04};
00053 //ECDSA with SHA-3-224 OID (2.16.840.1.101.3.4.3.9)
00054 const uint8_t ECDSA_WITH_SHA3_224_OID[9] = {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x03, 0x09};
00055 //ECDSA with SHA-3-256 OID (2.16.840.1.101.3.4.3.10)
00056 const uint8_t ECDSA_WITH_SHA3_256_OID[9] = {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x03, 0x0A};
00057 //ECDSA with SHA-3-384 OID (2.16.840.1.101.3.4.3.11)
00058 const uint8_t ECDSA_WITH_SHA3_384_OID[9] = {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x03, 0x0B};
00059 //ECDSA with SHA-3-512 OID (2.16.840.1.101.3.4.3.12)
00060 const uint8_t ECDSA_WITH_SHA3_512_OID[9] = {0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x03, 0x0C};
00061 
00062 
00063 /**
00064  * @brief Initialize an ECDSA signature
00065  * @param[in] signature Pointer to the ECDSA signature to initialize
00066  **/
00067 
00068 void ecdsaInitSignature(EcdsaSignature *signature)
00069 {
00070    //Initialize multiple precision integers
00071    mpiInit(&signature->r);
00072    mpiInit(&signature->s);
00073 }
00074 
00075 
00076 /**
00077  * @brief Release an ECDSA signature
00078  * @param[in] signature Pointer to the ECDSA signature to free
00079  **/
00080 
00081 void ecdsaFreeSignature(EcdsaSignature *signature)
00082 {
00083    //Release multiple precision integers
00084    mpiFree(&signature->r);
00085    mpiFree(&signature->s);
00086 }
00087 
00088 
00089 /**
00090  * @brief Encode ECDSA signature using ASN.1
00091  * @param[in] signature (R, S) integer pair
00092  * @param[out] data Pointer to the buffer where to store the resulting ASN.1 structure
00093  * @param[out] length Length of the ASN.1 structure
00094  * @return Error code
00095  **/
00096 
00097 error_t ecdsaWriteSignature(const EcdsaSignature *signature, uint8_t *data, size_t *length)
00098 {
00099    error_t error;
00100    size_t k;
00101    size_t n;
00102    size_t rLen;
00103    size_t sLen;
00104    Asn1Tag tag;
00105 
00106    //Debug message
00107    TRACE_DEBUG("Writing ECDSA signature...\r\n");
00108 
00109    //Dump (R, S) integer pair
00110    TRACE_DEBUG("  r:\r\n");
00111    TRACE_DEBUG_MPI("    ", &signature->r);
00112    TRACE_DEBUG("  s:\r\n");
00113    TRACE_DEBUG_MPI("    ", &signature->s);
00114 
00115    //Calculate the length of R
00116    rLen = mpiGetByteLength(&signature->r);
00117    //Calculate the length of S
00118    sLen = mpiGetByteLength(&signature->s);
00119 
00120    //Make sure the (R, S) integer pair is valid
00121    if(rLen == 0 || sLen == 0)
00122       return ERROR_INVALID_LENGTH;
00123 
00124    //R and S are always encoded in the smallest possible number of octets
00125    if(mpiGetBitValue(&signature->r, (rLen * 8) - 1))
00126       rLen++;
00127    if(mpiGetBitValue(&signature->s, (sLen * 8) - 1))
00128       sLen++;
00129 
00130    //The first pass computes the length of the ASN.1 sequence
00131    n = 0;
00132 
00133    //The parameter R is encapsulated within an ASN.1 structure
00134    tag.constructed = FALSE;
00135    tag.objClass = ASN1_CLASS_UNIVERSAL;
00136    tag.objType = ASN1_TYPE_INTEGER;
00137    tag.length = rLen;
00138    tag.value = NULL;
00139 
00140    //Compute the length of the corresponding ASN.1 structure
00141    error = asn1WriteTag(&tag, FALSE, NULL, NULL);
00142    //Any error to report?
00143    if(error)
00144       return error;
00145 
00146    //Update the length of the ASN.1 sequence
00147    n += tag.totalLength;
00148 
00149    //The parameter S is encapsulated within an ASN.1 structure
00150    tag.constructed = FALSE;
00151    tag.objClass = ASN1_CLASS_UNIVERSAL;
00152    tag.objType = ASN1_TYPE_INTEGER;
00153    tag.length = sLen;
00154    tag.value = NULL;
00155 
00156    //Compute the length of the corresponding ASN.1 structure
00157    error = asn1WriteTag(&tag, FALSE, NULL, NULL);
00158    //Any error to report?
00159    if(error)
00160       return error;
00161 
00162    //Update the length of the ASN.1 sequence
00163    n += tag.totalLength;
00164 
00165    //The second pass encodes the ASN.1 structure
00166    k = 0;
00167 
00168    //The (R, S) integer pair is encapsulated within a sequence
00169    tag.constructed = TRUE;
00170    tag.objClass = ASN1_CLASS_UNIVERSAL;
00171    tag.objType = ASN1_TYPE_SEQUENCE;
00172    tag.length = n;
00173    tag.value = NULL;
00174 
00175    //Write the corresponding ASN.1 tag
00176    error = asn1WriteTag(&tag, FALSE, data + k, &n);
00177    //Any error to report?
00178    if(error)
00179       return error;
00180 
00181    //Advance write pointer
00182    k += n;
00183 
00184    //Encode the parameter R using ASN.1
00185    tag.constructed = FALSE;
00186    tag.objClass = ASN1_CLASS_UNIVERSAL;
00187    tag.objType = ASN1_TYPE_INTEGER;
00188    tag.length = rLen;
00189    tag.value = NULL;
00190 
00191    //Write the corresponding ASN.1 tag
00192    error = asn1WriteTag(&tag, FALSE, data + k, &n);
00193    //Any error to report?
00194    if(error)
00195       return error;
00196 
00197    //Advance write pointer
00198    k += n;
00199 
00200    //Convert R to an octet string
00201    error = mpiWriteRaw(&signature->r, data + k, rLen);
00202    //Any error to report?
00203    if(error)
00204       return error;
00205 
00206    //Advance write pointer
00207    k += rLen;
00208 
00209    //Encode the parameter S using ASN.1
00210    tag.constructed = FALSE;
00211    tag.objClass = ASN1_CLASS_UNIVERSAL;
00212    tag.objType = ASN1_TYPE_INTEGER;
00213    tag.length = sLen;
00214    tag.value = NULL;
00215 
00216    //Write the corresponding ASN.1 tag
00217    error = asn1WriteTag(&tag, FALSE, data + k, &n);
00218    //Any error to report?
00219    if(error)
00220       return error;
00221 
00222    //Advance write pointer
00223    k += n;
00224 
00225    //Convert S to an octet string
00226    error = mpiWriteRaw(&signature->s, data + k, sLen);
00227    //Any error to report?
00228    if(error)
00229       return error;
00230 
00231    //Advance write pointer
00232    k += sLen;
00233 
00234    //Dump ECDSA signature
00235    TRACE_DEBUG("  signature:\r\n");
00236    TRACE_DEBUG_ARRAY("    ", data, k);
00237 
00238    //Total length of the ASN.1 structure
00239    *length = k;
00240    //Successful processing
00241    return NO_ERROR;
00242 }
00243 
00244 
00245 /**
00246  * @brief Read an ASN.1 encoded ECDSA signature
00247  * @param[in] data Pointer to the ASN.1 structure to decode
00248  * @param[in] length Length of the ASN.1 structure
00249  * @param[out] signature (R, S) integer pair
00250  * @return Error code
00251  **/
00252 
00253 error_t ecdsaReadSignature(const uint8_t *data, size_t length, EcdsaSignature *signature)
00254 {
00255    error_t error;
00256    Asn1Tag tag;
00257 
00258    //Debug message
00259    TRACE_DEBUG("Reading ECDSA signature...\r\n");
00260 
00261    //Dump ECDSA signature
00262    TRACE_DEBUG("  signature:\r\n");
00263    TRACE_DEBUG_ARRAY("    ", data, length);
00264 
00265    //Start of exception handling block
00266    do
00267    {
00268       //Display ASN.1 structure
00269       error = asn1DumpObject(data, length, 0);
00270       //Any error to report?
00271       if(error)
00272          break;
00273 
00274       //Read the contents of the ASN.1 structure
00275       error = asn1ReadTag(data, length, &tag);
00276       //Failed to decode ASN.1 tag?
00277       if(error)
00278          break;
00279 
00280       //Enforce encoding, class and type
00281       error = asn1CheckTag(&tag, TRUE, ASN1_CLASS_UNIVERSAL, ASN1_TYPE_SEQUENCE);
00282       //The tag does not match the criteria?
00283       if(error)
00284          break;
00285 
00286       //Point to the first field
00287       data = tag.value;
00288       length = tag.length;
00289 
00290       //Read the parameter R
00291       error = asn1ReadTag(data, length, &tag);
00292       //Failed to decode ASN.1 tag?
00293       if(error)
00294          break;
00295 
00296       //Enforce encoding, class and type
00297       error = asn1CheckTag(&tag, FALSE, ASN1_CLASS_UNIVERSAL, ASN1_TYPE_INTEGER);
00298       //The tag does not match the criteria?
00299       if(error)
00300          break;
00301 
00302       //Convert the octet string to a multiple precision integer
00303       error = mpiReadRaw(&signature->r, tag.value, tag.length);
00304       //Any error to report?
00305       if(error)
00306          break;
00307 
00308       //Point to the next field
00309       data += tag.totalLength;
00310       length -= tag.totalLength;
00311 
00312       //Read the parameter S
00313       error = asn1ReadTag(data, length, &tag);
00314       //Failed to decode ASN.1 tag?
00315       if(error)
00316          break;
00317 
00318       //Enforce encoding, class and type
00319       error = asn1CheckTag(&tag, FALSE, ASN1_CLASS_UNIVERSAL, ASN1_TYPE_INTEGER);
00320       //The tag does not match the criteria?
00321       if(error)
00322          break;
00323 
00324       //Convert the octet string to a multiple precision integer
00325       error = mpiReadRaw(&signature->s, tag.value, tag.length);
00326       //Any error to report?
00327       if(error)
00328          break;
00329 
00330       //Dump (R, S) integer pair
00331       TRACE_DEBUG("  r:\r\n");
00332       TRACE_DEBUG_MPI("    ", &signature->r);
00333       TRACE_DEBUG("  s:\r\n");
00334       TRACE_DEBUG_MPI("    ", &signature->s);
00335 
00336       //End of exception handling block
00337    } while(0);
00338 
00339    //Clean up side effects if necessary
00340    if(error)
00341       ecdsaFreeSignature(signature);
00342 
00343    //Return status code
00344    return error;
00345 }
00346 
00347 
00348 /**
00349  * @brief ECDSA signature generation
00350  * @param[in] params EC domain parameters
00351  * @param[in] prngAlgo PRNG algorithm
00352  * @param[in] prngContext Pointer to the PRNG context
00353  * @param[in] privateKey Signer's ECDSA private key
00354  * @param[in] digest Digest of the message to be signed
00355  * @param[in] digestLength Length in octets of the digest
00356  * @param[out] signature (R, S) integer pair
00357  * @return Error code
00358  **/
00359 
00360 error_t ecdsaGenerateSignature(const EcDomainParameters *params,
00361    const PrngAlgo *prngAlgo, void *prngContext, const Mpi *privateKey,
00362    const uint8_t *digest, size_t digestLength, EcdsaSignature *signature)
00363 {
00364    error_t error;
00365    uint_t n;
00366    Mpi k;
00367    Mpi z;
00368    EcPoint r1;
00369 
00370    //Check parameters
00371    if(params == NULL || privateKey == NULL || digest == NULL || signature == NULL)
00372       return ERROR_INVALID_PARAMETER;
00373 
00374    //Debug message
00375    TRACE_DEBUG("ECDSA signature generation...\r\n");
00376    TRACE_DEBUG("  private key:\r\n");
00377    TRACE_DEBUG_MPI("    ", privateKey);
00378    TRACE_DEBUG("  digest:\r\n");
00379    TRACE_DEBUG_ARRAY("    ", digest, digestLength);
00380 
00381    //Initialize multiple precision integers
00382    mpiInit(&k);
00383    mpiInit(&z);
00384    //Initialize EC point
00385    ecInit(&r1);
00386 
00387    //Let N be the bit length of q
00388    n = mpiGetBitLength(&params->q);
00389 
00390    //Generated a pseudorandom number
00391    MPI_CHECK(mpiRand(&k, n, prngAlgo, prngContext));
00392 
00393    //Make sure that 0 < k < q
00394    if(mpiComp(&k, &params->q) >= 0)
00395       mpiShiftRight(&k, 1);
00396 
00397    //Debug message
00398    TRACE_DEBUG("  k:\r\n");
00399    TRACE_DEBUG_MPI("    ", &k);
00400 
00401    //Compute N = MIN(N, outlen)
00402    n = MIN(n, digestLength * 8);
00403 
00404    //Convert the digest to a multiple precision integer
00405    MPI_CHECK(mpiReadRaw(&z, digest, (n + 7) / 8));
00406 
00407    //Keep the leftmost N bits of the hash value
00408    if(n % 8)
00409    {
00410       MPI_CHECK(mpiShiftRight(&z, 8 - (n % 8)));
00411    }
00412 
00413    //Debug message
00414    TRACE_DEBUG("  z:\r\n");
00415    TRACE_DEBUG_MPI("    ", &z);
00416 
00417    //Compute R1 = (x1, y1) = k.G
00418    EC_CHECK(ecMult(params, &r1, &k, &params->g));
00419    EC_CHECK(ecAffinify(params, &r1, &r1));
00420 
00421    //Debug message
00422    TRACE_DEBUG("  x1:\r\n");
00423    TRACE_DEBUG_MPI("    ", &r1.x);
00424    TRACE_DEBUG("  y1:\r\n");
00425    TRACE_DEBUG_MPI("    ", &r1.y);
00426 
00427    //Compute r = x1 mod q
00428    MPI_CHECK(mpiMod(&signature->r, &r1.x, &params->q));
00429 
00430    //Compute k ^ -1 mod q
00431    MPI_CHECK(mpiInvMod(&k, &k, &params->q));
00432 
00433    //Compute s = k ^ -1 * (z + x * r) mod q
00434    MPI_CHECK(mpiMul(&signature->s, privateKey, &signature->r));
00435    MPI_CHECK(mpiAdd(&signature->s, &signature->s, &z));
00436    MPI_CHECK(mpiMod(&signature->s, &signature->s, &params->q));
00437    MPI_CHECK(mpiMulMod(&signature->s, &signature->s, &k, &params->q));
00438 
00439    //Dump ECDSA signature
00440    TRACE_DEBUG("  r:\r\n");
00441    TRACE_DEBUG_MPI("    ", &signature->r);
00442    TRACE_DEBUG("  s:\r\n");
00443    TRACE_DEBUG_MPI("    ", &signature->s);
00444 
00445 end:
00446    //Release multiple precision integers
00447    mpiFree(&k);
00448    mpiFree(&z);
00449    //Release EC point
00450    ecFree(&r1);
00451 
00452    //Clean up side effects if necessary
00453    if(error)
00454    {
00455       //Release (R, S) integer pair
00456       mpiFree(&signature->r);
00457       mpiFree(&signature->s);
00458    }
00459 
00460    //Return status code
00461    return error;
00462 }
00463 
00464 
00465 /**
00466  * @brief ECDSA signature verification
00467  * @param[in] params EC domain parameters
00468  * @param[in] publicKey Signer's ECDSA public key
00469  * @param[in] digest Digest of the message whose signature is to be verified
00470  * @param[in] digestLength Length in octets of the digest
00471  * @param[in] signature (R, S) integer pair
00472  * @return Error code
00473  **/
00474 
00475 error_t ecdsaVerifySignature(const EcDomainParameters *params, const EcPoint *publicKey,
00476    const uint8_t *digest, size_t digestLength, const EcdsaSignature *signature)
00477 {
00478    error_t error;
00479    uint_t n;
00480    Mpi w;
00481    Mpi z;
00482    Mpi u1;
00483    Mpi u2;
00484    Mpi v;
00485    EcPoint v0;
00486    EcPoint v1;
00487 
00488    //Check parameters
00489    if(params == NULL || publicKey == NULL || digest == NULL || signature == NULL)
00490       return ERROR_INVALID_PARAMETER;
00491 
00492    //Debug message
00493    TRACE_DEBUG("ECDSA signature verification...\r\n");
00494    TRACE_DEBUG("  public key X:\r\n");
00495    TRACE_DEBUG_MPI("    ", &publicKey->x);
00496    TRACE_DEBUG("  public key Y:\r\n");
00497    TRACE_DEBUG_MPI("    ", &publicKey->y);
00498    TRACE_DEBUG("  digest:\r\n");
00499    TRACE_DEBUG_ARRAY("    ", digest, digestLength);
00500    TRACE_DEBUG("  r:\r\n");
00501    TRACE_DEBUG_MPI("    ", &signature->r);
00502    TRACE_DEBUG("  s:\r\n");
00503    TRACE_DEBUG_MPI("    ", &signature->s);
00504 
00505    //The verifier shall check that 0 < r < q and 0 < s < q. If either
00506    //condition is violated, the signature shall be rejected as invalid
00507    if(mpiCompInt(&signature->r, 0) <= 0 || mpiComp(&signature->r, &params->q) >= 0)
00508       return ERROR_INVALID_SIGNATURE;
00509    if(mpiCompInt(&signature->s, 0) <= 0 || mpiComp(&signature->s, &params->q) >= 0)
00510       return ERROR_INVALID_SIGNATURE;
00511 
00512    //Initialize multiple precision integers
00513    mpiInit(&w);
00514    mpiInit(&z);
00515    mpiInit(&u1);
00516    mpiInit(&u2);
00517    mpiInit(&v);
00518    //Initialize EC points
00519    ecInit(&v0);
00520    ecInit(&v1);
00521 
00522    //Let N be the bit length of q
00523    n = mpiGetBitLength(&params->q);
00524    //Compute N = MIN(N, outlen)
00525    n = MIN(n, digestLength * 8);
00526 
00527    //Convert the digest to a multiple precision integer
00528    MPI_CHECK(mpiReadRaw(&z, digest, (n + 7) / 8));
00529 
00530    //Keep the leftmost N bits of the hash value
00531    if(n % 8)
00532    {
00533       MPI_CHECK(mpiShiftRight(&z, 8 - (n % 8)));
00534    }
00535 
00536    //Compute w = s ^ -1 mod q
00537    MPI_CHECK(mpiInvMod(&w, &signature->s, &params->q));
00538    //Compute u1 = z * w mod q
00539    MPI_CHECK(mpiMulMod(&u1, &z, &w, &params->q));
00540    //Compute u2 = r * w mod q
00541    MPI_CHECK(mpiMulMod(&u2, &signature->r, &w, &params->q));
00542 
00543    //Compute V0 = (x0, y0) = u1.G + u2.Q
00544    EC_CHECK(ecProjectify(params, &v1, publicKey));
00545    EC_CHECK(ecTwinMult(params, &v0, &u1, &params->g, &u2, &v1));
00546    EC_CHECK(ecAffinify(params, &v0, &v0));
00547 
00548    //Debug message
00549    TRACE_DEBUG("  x0:\r\n");
00550    TRACE_DEBUG_MPI("    ", &v0.x);
00551    TRACE_DEBUG("  y0:\r\n");
00552    TRACE_DEBUG_MPI("    ", &v0.y);
00553 
00554    //Compute v = x0 mod q
00555    MPI_CHECK(mpiMod(&v, &v0.x, &params->q));
00556 
00557    //Debug message
00558    TRACE_DEBUG("  v:\r\n");
00559    TRACE_DEBUG_MPI("    ", &v);
00560 
00561    //If v = r, then the signature is verified. If v does not equal r,
00562    //then the message or the signature may have been modified
00563    if(!mpiComp(&v, &signature->r))
00564       error = NO_ERROR;
00565    else
00566       error = ERROR_INVALID_SIGNATURE;
00567 
00568 end:
00569    //Release multiple precision integers
00570    mpiFree(&w);
00571    mpiFree(&z);
00572    mpiFree(&u1);
00573    mpiFree(&u2);
00574    mpiFree(&v);
00575    //Release EC points
00576    ecFree(&v0);
00577    ecFree(&v1);
00578 
00579    //Return status code
00580    return error;
00581 }
00582 
00583 #endif
00584