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