dsa_verify.c

/*
 * dsa_verify - http://opensource.implicit-link.com/
 * Copyright (c) 2010 Implicit Link
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <string.h>
#include <stdio.h>

#include "mp_math.h"
#include "sha1.h"

#include "dsa_verify.h"

#define MP_OP(op) if ((ret = (op)) != MP_OKAY) goto error;

/*char *debugMp (mp_int *d)
{
	char *ret = malloc(1024); // leak leak
	mp_tohex(d, ret);
	return ret;
}*/

int _dsa_verify_hash (mp_int *r, mp_int *s, mp_int *hash,
		mp_int *keyG, mp_int *keyP, mp_int *keyQ, mp_int *keyY)
{
	mp_int w, v, u1, u2;
	int ret;
	
	MP_OP(mp_init_multi(&w, &v, &u1, &u2, NULL));
	
	// neither r or s can be 0 or >q
	if (mp_iszero(r) == MP_YES || mp_iszero(s) == MP_YES || mp_cmp(r, keyQ) != MP_LT || mp_cmp(s, keyQ) != MP_LT) {
	   ret = -1;
	   goto error;
	}
	
	// w = 1/s mod q
	MP_OP(mp_invmod(s, keyQ, &w));
	
	// u1 = m * w mod q
	MP_OP(mp_mulmod(hash, &w, keyQ, &u1));
	
	// u2 = r*w mod q
	MP_OP(mp_mulmod(r, &w, keyQ, &u2));
	
	// v = g^u1 * y^u2 mod p mod q
	MP_OP(mp_exptmod(keyG, &u1, keyP, &u1));
	MP_OP(mp_exptmod(keyY, &u2, keyP, &u2));
	MP_OP(mp_mulmod(&u1, &u2, keyP, &v));
	MP_OP(mp_mod(&v, keyQ, &v));
	
	// if r = v then we're set
	ret = 0;
	if (mp_cmp(r, &v) == MP_EQ) ret = 1;
	
error:
	mp_clear_multi(&w, &v, &u1, &u2, NULL);
	return ret;
}

const unsigned char *read_key(mp_int* keyPart, const unsigned char* keyData)
{
	int len = keyData[0]*256 + keyData[1];
	mp_read_unsigned_bin(keyPart, keyData+2, len);
	return keyData+len+2;
}

int dsa_verify_blob(const char *data, int dataLen, const unsigned char* keyData, const char* sigR, const char* sigS)
{
	// dss1 hashing algorithm is actually sha1
	SHA1Context sha1;
	uint8_t sha1sum[SHA1HashSize];
	SHA1Reset(&sha1);

	SHA1Input(&sha1, (const unsigned char *) data, dataLen);
	SHA1Result(&sha1, sha1sum);

	mp_int hash, keyG, keyP, keyQ, keyY, r, s;
	mp_init_multi(&hash, &keyG, &keyP, &keyQ, &keyY, &r, &s, NULL);
	mp_read_unsigned_bin(&hash, sha1sum, sizeof(sha1sum));
	
	keyData = read_key(&keyY, keyData);
	keyData = read_key(&keyP, keyData);
	keyData = read_key(&keyQ, keyData);
	keyData = read_key(&keyG, keyData);
	mp_read_radix(&r, sigR, 16);
	mp_read_radix(&s, sigS, 16);
	
	return _dsa_verify_hash(&r, &s, &hash, &keyG, &keyP, &keyQ, &keyY);
}

#ifdef TEST

int main()
{
	char *message = \
		"I think computer viruses should count as life. I think it\n" \
		" says something about human nature that the only form of\n" \
		" life we have created so far is purely destructive. We've\n" \
		" created life in our own image.\n";
	
	const char publicKey[] = {
		0x00, 0x80, // pub is 128 bytes
		0x4e, 0xf3, 0xae, 0x38, 0xfb, 0x09, 0x7e, 0x2c, 0xd1, 0x58, 0x33, 0x0a, 0x27, 0xba, 0x5c, 0x2a, 
		0xa0, 0x33, 0x46, 0xcf, 0xe4, 0x8a, 0xbc, 0x3e, 0xdd, 0x72, 0xda, 0xbb, 0x3a, 0xf9, 0x4f, 0x89, 
		0x73, 0xd4, 0x78, 0xd5, 0xdb, 0x6b, 0xa8, 0xc8, 0x02, 0x99, 0x47, 0x3e, 0xb9, 0xdc, 0xb8, 0x6e, 
		0xda, 0x2d, 0x8d, 0xda, 0xec, 0x08, 0x21, 0x81, 0x47, 0x38, 0x1e, 0xe2, 0x87, 0xcd, 0x3d, 0x3f, 
		0x19, 0x1f, 0x20, 0xd3, 0x53, 0xc7, 0x1a, 0x9a, 0x0c, 0x64, 0xa8, 0xa3, 0x68, 0xb5, 0xb8, 0x33, 
		0x8b, 0xe1, 0x5b, 0xf6, 0x3a, 0xe1, 0xf1, 0x7c, 0x47, 0x87, 0xf1, 0x31, 0xf6, 0xb9, 0x97, 0x9f, 
		0xb2, 0xc1, 0xc6, 0x9c, 0x1e, 0xce, 0x8b, 0x4e, 0x0d, 0x16, 0x0c, 0xa9, 0xa0, 0x3f, 0xa8, 0x96, 
		0x34, 0x68, 0xba, 0x7c, 0xc5, 0x6a, 0xdb, 0xe1, 0x18, 0x94, 0x5a, 0x85, 0x0f, 0xe8, 0x28, 0xf8,
		0x00, 0x81, // P is 129 bytes
		0x00, 0xf6, 0x34, 0xeb, 0x73, 0xb0, 0x1a, 0x68, 0x47, 0x72, 0x95, 0x7b, 0x15, 0x63, 0xec, 0x11, 
		0x98, 0x23, 0x81, 0x91, 0x4f, 0x94, 0x85, 0xee, 0x42, 0x52, 0x5e, 0x88, 0x89, 0x55, 0x41, 0xf7, 
		0xff, 0x56, 0xa7, 0x2d, 0xb3, 0x05, 0xbe, 0x34, 0xc5, 0xa1, 0xb3, 0x6b, 0x96, 0xa0, 0x2a, 0x04, 
		0xe1, 0x69, 0x9a, 0x69, 0xc9, 0x29, 0xdf, 0x60, 0x19, 0x5b, 0x36, 0x64, 0xcc, 0x3c, 0x5a, 0x24, 
		0xe1, 0xc2, 0x2b, 0xad, 0x4f, 0x44, 0x0f, 0xa9, 0xc4, 0x2e, 0x27, 0xd5, 0x58, 0x3a, 0xac, 0x2c, 
		0x9f, 0xfa, 0x67, 0x26, 0xf2, 0xd8, 0x07, 0xe7, 0x25, 0x35, 0xd1, 0xd2, 0x81, 0x95, 0x49, 0xe9, 
		0x13, 0x52, 0xfc, 0xe5, 0x30, 0xbc, 0x1b, 0x61, 0xdb, 0x34, 0xc7, 0x97, 0x8b, 0x15, 0xb8, 0x3d, 
		0x92, 0x02, 0xfe, 0x2f, 0x62, 0x90, 0x95, 0xc4, 0x9a, 0x6c, 0x86, 0x55, 0xee, 0x41, 0x7d, 0xb4, 
		0x05,
		0x00, 0x15, // Q is 21 bytes
		0x00, 0xe4, 0x3d, 0xd6, 0x3f, 0xc7, 0x4a, 0xc9, 0x39, 0x3e, 0xbb, 0x73, 0xa5, 0xf5, 0x5b, 0x50, 
		0x80, 0xd6, 0xec, 0xdd, 0xdd,
		0x00, 0x81, // G is 129 bytes
		0x00, 0xab, 0xdd, 0x5c, 0x6c, 0x12, 0xc6, 0x18, 0xd8, 0xec, 0x46, 0x22, 0x8b, 0x05, 0xfc, 0x33, 
		0x63, 0x21, 0x2d, 0x84, 0x1c, 0x2b, 0x58, 0xda, 0xba, 0xe9, 0x73, 0x48, 0x19, 0x63, 0x53, 0x8a, 
		0xeb, 0xb4, 0xfe, 0xe7, 0x25, 0x8c, 0xc0, 0x6f, 0x4e, 0xd7, 0x0b, 0x7d, 0x45, 0x2b, 0xcc, 0xc9, 
		0x39, 0x77, 0x7f, 0x2e, 0x8c, 0x90, 0xd8, 0xcb, 0x62, 0x9d, 0x23, 0x9a, 0x9f, 0x52, 0x42, 0x1e, 
		0x6f, 0xb2, 0xed, 0x98, 0x34, 0x51, 0x5b, 0x6f, 0x41, 0x3e, 0x70, 0xc7, 0x31, 0x13, 0x9a, 0x55, 
		0x91, 0x8a, 0x44, 0x45, 0x9d, 0x5e, 0x5e, 0xa1, 0x42, 0x94, 0x45, 0x1e, 0x58, 0x27, 0xe9, 0x3e, 
		0x45, 0x8a, 0x0b, 0xf6, 0x05, 0x01, 0x0a, 0xa2, 0x0d, 0xbd, 0x1a, 0xd3, 0x61, 0x8e, 0xa7, 0x38, 
		0x69, 0xf8, 0x0c, 0x90, 0xf8, 0x75, 0xb3, 0xfe, 0x6b, 0x18, 0xce, 0x5a, 0x69, 0x8b, 0x84, 0xd2, 
		0x5a
	};
	
	return dsa_verify_blob(
		message, strlen(message),
		publicKey,
		"D795D68F0CFB19F8A5C042B6427DB8132D1403D1",
		"5D1E9010B9B0605BA6F0983CF49A14FD6F18892D");
}

#endif