1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis 2 * 3 * LibTomCrypt is a library that provides various cryptographic 4 * algorithms in a highly modular and flexible manner. 5 * 6 * The library is free for all purposes without any express 7 * guarantee it works. 8 * 9 * Tom St Denis, tomstdenis (at) gmail.com, http://libtomcrypt.com 10 */ 11 12 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b 13 * 14 * All curves taken from NIST recommendation paper of July 1999 15 * Available at http://csrc.nist.gov/cryptval/dss.htm 16 */ 17 #include "tomcrypt.h" 18 19 /** 20 @file ecc_verify_hash.c 21 ECC Crypto, Tom St Denis 22 */ 23 24 #ifdef MECC 25 26 /* verify 27 * 28 * w = s^-1 mod n 29 * u1 = xw 30 * u2 = rw 31 * X = u1*G + u2*Q 32 * v = X_x1 mod n 33 * accept if v == r 34 */ 35 36 /** 37 Verify an ECC signature 38 @param sig The signature to verify 39 @param siglen The length of the signature (octets) 40 @param hash The hash (message digest) that was signed 41 @param hashlen The length of the hash (octets) 42 @param stat Result of signature, 1==valid, 0==invalid 43 @param key The corresponding public ECC key 44 @return CRYPT_OK if successful (even if the signature is not valid) 45 */ 46 int ecc_verify_hash(const unsigned char *sig, unsigned long siglen, 47 const unsigned char *hash, unsigned long hashlen, 48 int *stat, ecc_key *key) 49 { 50 ecc_point *mG, *mQ; 51 void *r, *s, *v, *w, *u1, *u2, *e, *p, *m; 52 void *mp; 53 int err; 54 55 LTC_ARGCHK(sig != NULL); 56 LTC_ARGCHK(hash != NULL); 57 LTC_ARGCHK(stat != NULL); 58 LTC_ARGCHK(key != NULL); 59 60 /* default to invalid signature */ 61 *stat = 0; 62 mp = NULL; 63 64 /* is the IDX valid ? */ 65 if (ltc_ecc_is_valid_idx(key->idx) != 1) { 66 return CRYPT_PK_INVALID_TYPE; 67 } 68 69 /* allocate ints */ 70 if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL)) != CRYPT_OK) { 71 return CRYPT_MEM; 72 } 73 74 /* allocate points */ 75 mG = ltc_ecc_new_point(); 76 mQ = ltc_ecc_new_point(); 77 if (mQ == NULL || mG == NULL) { 78 err = CRYPT_MEM; 79 goto error; 80 } 81 82 /* parse header */ 83 if ((err = der_decode_sequence_multi(sig, siglen, 84 LTC_ASN1_INTEGER, 1UL, r, 85 LTC_ASN1_INTEGER, 1UL, s, 86 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { 87 goto error; 88 } 89 90 /* get the order */ 91 if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK) { goto error; } 92 93 /* get the modulus */ 94 if ((err = mp_read_radix(m, (char *)key->dp->prime, 16)) != CRYPT_OK) { goto error; } 95 96 /* check for zero */ 97 if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) { 98 err = CRYPT_INVALID_PACKET; 99 goto error; 100 } 101 102 /* read hash */ 103 if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, (int)hashlen)) != CRYPT_OK) { goto error; } 104 105 /* w = s^-1 mod n */ 106 if ((err = mp_invmod(s, p, w)) != CRYPT_OK) { goto error; } 107 108 /* u1 = ew */ 109 if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK) { goto error; } 110 111 /* u2 = rw */ 112 if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK) { goto error; } 113 114 /* find mG and mQ */ 115 if ((err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16)) != CRYPT_OK) { goto error; } 116 if ((err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16)) != CRYPT_OK) { goto error; } 117 if ((err = mp_set(mG->z, 1)) != CRYPT_OK) { goto error; } 118 119 if ((err = mp_copy(key->pubkey.x, mQ->x)) != CRYPT_OK) { goto error; } 120 if ((err = mp_copy(key->pubkey.y, mQ->y)) != CRYPT_OK) { goto error; } 121 if ((err = mp_copy(key->pubkey.z, mQ->z)) != CRYPT_OK) { goto error; } 122 123 /* compute u1*mG + u2*mQ = mG */ 124 if (ltc_mp.ecc_mul2add == NULL) { 125 if ((err = ltc_mp.ecc_ptmul(u1, mG, mG, m, 0)) != CRYPT_OK) { goto error; } 126 if ((err = ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0)) != CRYPT_OK) { goto error; } 127 128 /* find the montgomery mp */ 129 if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK) { goto error; } 130 131 /* add them */ 132 if ((err = ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp)) != CRYPT_OK) { goto error; } 133 134 /* reduce */ 135 if ((err = ltc_mp.ecc_map(mG, m, mp)) != CRYPT_OK) { goto error; } 136 } else { 137 /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */ 138 if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m)) != CRYPT_OK) { goto error; } 139 } 140 141 /* v = X_x1 mod n */ 142 if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK) { goto error; } 143 144 /* does v == r */ 145 if (mp_cmp(v, r) == LTC_MP_EQ) { 146 *stat = 1; 147 } 148 149 /* clear up and return */ 150 err = CRYPT_OK; 151 error: 152 ltc_ecc_del_point(mG); 153 ltc_ecc_del_point(mQ); 154 mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL); 155 if (mp != NULL) { 156 mp_montgomery_free(mp); 157 } 158 return err; 159 } 160 161 #endif 162 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_verify_hash.c,v $ */ 163 /* $Revision: 1.12 $ */ 164 /* $Date: 2006/12/04 05:07:59 $ */ 165 166
