1444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji/****************************************************************************** 2444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 3444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * Copyright (C) 2006-2015 Broadcom Corporation 4444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 5444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * Licensed under the Apache License, Version 2.0 (the "License"); 6444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * you may not use this file except in compliance with the License. 7444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * You may obtain a copy of the License at: 8444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 9444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * http://www.apache.org/licenses/LICENSE-2.0 10444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 11444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * Unless required by applicable law or agreed to in writing, software 12444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * distributed under the License is distributed on an "AS IS" BASIS, 13444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * See the License for the specific language governing permissions and 15444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * limitations under the License. 16444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 17444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji ******************************************************************************/ 18444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 199ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson/******************************************************************************* 209ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson * 219ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson * This file contains simple pairing algorithms using Elliptic Curve 229ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson * Cryptography for private public key 239ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson * 249ca07091a1f07ea201cee0504dab6a1d7073d429Myles Watson ******************************************************************************/ 25911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson#include "p_256_ecc_pp.h" 26444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include <stdio.h> 27444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include <stdlib.h> 28444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include <string.h> 29444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include "p_256_multprecision.h" 30444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 31444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojielliptic_curve_t curve; 32444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojielliptic_curve_t curve_p256; 33444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 34911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonstatic void p_256_init_point(Point* q) { memset(q, 0, sizeof(Point)); } 35444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 36911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonstatic void p_256_copy_point(Point* q, Point* p) { 37911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson memcpy(q, p, sizeof(Point)); 38444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 39444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 40444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// q=2q 41911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonstatic void ECC_Double(Point* q, Point* p, uint32_t keyLength) { 42911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t t1[KEY_LENGTH_DWORDS_P256]; 43911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t t2[KEY_LENGTH_DWORDS_P256]; 44911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t t3[KEY_LENGTH_DWORDS_P256]; 45911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* x1; 46911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* x3; 47911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* y1; 48911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* y3; 49911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* z1; 50911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* z3; 51911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 52911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (multiprecision_iszero(p->z, keyLength)) { 53911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_init(q->z, keyLength); 54911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson return; // return infinity 55911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 56911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 57911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson x1 = p->x; 58911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson y1 = p->y; 59911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson z1 = p->z; 60911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson x3 = q->x; 61911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson y3 = q->y; 62911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson z3 = q->z; 63911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 64911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(t1, z1, keyLength); // t1=z1^2 65911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(t2, x1, t1, keyLength); // t2=x1-t1 66911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_add_mod(t1, x1, t1, keyLength); // t1=x1+t1 67911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t2, t1, t2, keyLength); // t2=t2*t1 68911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(t3, t2, keyLength); 69911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_add_mod(t2, t3, t2, keyLength); // t2=3t2 70911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 71911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(z3, y1, z1, keyLength); // z3=y1*z1 72911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(z3, z3, keyLength); 73911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 74911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(y3, y1, keyLength); // y3=y1^2 75911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(y3, y3, keyLength); 76911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t3, y3, x1, keyLength); // t3=y3*x1=x1*y1^2 77911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(t3, t3, keyLength); 78911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(y3, y3, keyLength); // y3=y3^2=y1^4 79911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(y3, y3, keyLength); 80911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 81911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(x3, t2, keyLength); // x3=t2^2 82911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(t1, t3, keyLength); // t1=2t3 83911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(x3, x3, t1, keyLength); // x3=x3-t1 84911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(t1, t3, x3, keyLength); // t1=t3-x3 85911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t1, t1, t2, keyLength); // t1=t1*t2 86911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(y3, t1, y3, keyLength); // y3=t1-y3 87444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 88444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 89444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// q=q+p, zp must be 1 90911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonstatic void ECC_Add(Point* r, Point* p, Point* q, uint32_t keyLength) { 91911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t t1[KEY_LENGTH_DWORDS_P256]; 92911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t t2[KEY_LENGTH_DWORDS_P256]; 93911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* x1; 94911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* x2; 95911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* x3; 96911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* y1; 97911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* y2; 98911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* y3; 99911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* z1; 100911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* z2; 101911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* z3; 102911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 103911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson x1 = p->x; 104911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson y1 = p->y; 105911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson z1 = p->z; 106911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson x2 = q->x; 107911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson y2 = q->y; 108911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson z2 = q->z; 109911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson x3 = r->x; 110911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson y3 = r->y; 111911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson z3 = r->z; 112911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 113911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // if Q=infinity, return p 114911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (multiprecision_iszero(z2, keyLength)) { 115911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_copy_point(r, p); 116911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson return; 117911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 118911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 119911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // if P=infinity, return q 120911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (multiprecision_iszero(z1, keyLength)) { 121911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_copy_point(r, q); 122911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson return; 123911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 124911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 125911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(t1, z1, keyLength); // t1=z1^2 126911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t2, z1, t1, keyLength); // t2=t1*z1 127911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t1, x2, t1, keyLength); // t1=t1*x2 128911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(t2, y2, t2, keyLength); // t2=t2*y2 129911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 130911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(t1, t1, x1, keyLength); // t1=t1-x1 131911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(t2, t2, y1, keyLength); // t2=t2-y1 132911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 133911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (multiprecision_iszero(t1, keyLength)) { 134911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (multiprecision_iszero(t2, keyLength)) { 135911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson ECC_Double(r, q, keyLength); 136911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson return; 137911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } else { 138911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_init(z3, keyLength); 139911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson return; // return infinity 140444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 141911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 142911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 143911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(z3, z1, t1, keyLength); // z3=z1*t1 144911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(y3, t1, keyLength); // t3=t1^2 145911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(z1, y3, t1, keyLength); // t4=t3*t1 146911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(y3, y3, x1, keyLength); // t3=t3*x1 147911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_lshift_mod(t1, y3, keyLength); // t1=2*t3 148911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(x3, t2, keyLength); // x3=t2^2 149911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(x3, x3, t1, keyLength); // x3=x3-t1 150911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(x3, x3, z1, keyLength); // x3=x3-t4 151911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(y3, y3, x3, keyLength); // t3=t3-x3 152911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(y3, y3, t2, keyLength); // t3=t3*t2 153911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(z1, z1, y1, keyLength); // t4=t4*t1 154911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub_mod(y3, y3, z1, keyLength); 155444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 156444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 157444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// Computing the Non-Adjacent Form of a positive integer 158911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonstatic void ECC_NAF(uint8_t* naf, uint32_t* NumNAF, uint32_t* k, 159911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t keyLength) { 160911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t sign; 161911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson int i = 0; 162911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson int j; 163911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t var; 164911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 165911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson while ((var = multiprecision_most_signbits(k, keyLength)) >= 1) { 166911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (k[0] & 0x01) // k is odd 167444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 168911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson sign = (k[0] & 0x03); // 1 or 3 169911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 170911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // k = k-naf[i] 171911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (sign == 1) 172911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson k[0] = k[0] & 0xFFFFFFFE; 173911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson else { 174911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson k[0] = k[0] + 1; 175911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (k[0] == 0) // overflow 176444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 177911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson j = 1; 178911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson do { 179911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson k[j]++; 180911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } while (k[j++] == 0); // overflow 181444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 182911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 183911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } else 184911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson sign = 0; 185444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 186911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_rshift(k, k, keyLength); 187911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson naf[i / 4] |= (sign) << ((i % 4) * 2); 188911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson i++; 189911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 190444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 191911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson *NumNAF = i; 192444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 193444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 194444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// Binary Non-Adjacent Form for point multiplication 195911d1ae03efec2d54c3b1b605589d790d1745488Myles Watsonvoid ECC_PointMult_Bin_NAF(Point* q, Point* p, uint32_t* n, 196911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t keyLength) { 197911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t sign; 198911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint8_t naf[256 / 4 + 1]; 199911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t NumNaf; 200911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson Point minus_p; 201911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson Point r; 202911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson uint32_t* modp; 203911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 204911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (keyLength == KEY_LENGTH_DWORDS_P256) { 205911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson modp = curve_p256.p; 206911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } else { 207911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson modp = curve.p; 208911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 209911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 210911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_init_point(&r); 211911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_init(p->z, keyLength); 212911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p->z[0] = 1; 213911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 214911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // initialization 215911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_init_point(q); 216911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 217911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // -p 218911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_copy(minus_p.x, p->x, keyLength); 219911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_sub(minus_p.y, modp, p->y, keyLength); 220911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 221911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_init(minus_p.z, keyLength); 222911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson minus_p.z[0] = 1; 223911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 224911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson // NAF 225911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson memset(naf, 0, sizeof(naf)); 226911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson ECC_NAF(naf, &NumNaf, n, keyLength); 227911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 228911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson for (int i = NumNaf - 1; i >= 0; i--) { 229911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_copy_point(&r, q); 230911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson ECC_Double(q, &r, keyLength); 231911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03; 232911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson 233911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson if (sign == 1) { 234911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_copy_point(&r, q); 235911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson ECC_Add(q, &r, p, keyLength); 236911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } else if (sign == 3) { 237911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson p_256_copy_point(&r, q); 238911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson ECC_Add(q, &r, &minus_p, keyLength); 239444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 240911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson } 241444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 242911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_inv_mod(minus_p.x, q->z, keyLength); 243911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_squa_mod(q->z, minus_p.x, keyLength); 244911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(q->x, q->x, q->z, keyLength); 245911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, keyLength); 246911d1ae03efec2d54c3b1b605589d790d1745488Myles Watson multiprecision_mersenns_mult_mod(q->y, q->y, q->z, keyLength); 247444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 2488ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach 2498ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbachbool ECC_ValidatePoint(const Point& pt) { 2508ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach const size_t kl = KEY_LENGTH_DWORDS_P256; 2518ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach p_256_init_curve(kl); 2528ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach 2538ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach // Ensure y^2 = x^3 + a*x + b (mod p); a = -3 2548ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach 2558ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach // y^2 mod p 2568ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach uint32_t y2_mod[kl] = {0}; 2578ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach multiprecision_mersenns_squa_mod(y2_mod, (uint32_t*)pt.y, kl); 2588ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach 2598ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach // Right hand side calculation 2608ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach uint32_t rhs[kl] = {0}; 2618ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach multiprecision_mersenns_squa_mod(rhs, (uint32_t*)pt.x, kl); 2628ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach uint32_t three[kl] = {0}; 2638ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach three[0] = 3; 2648ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach multiprecision_sub_mod(rhs, rhs, three, kl); 2658ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach multiprecision_mersenns_mult_mod(rhs, rhs, (uint32_t*)pt.x, kl); 2668ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach multiprecision_add_mod(rhs, rhs, curve_p256.b, kl); 2678ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach 2688ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach return multiprecision_compare(rhs, y2_mod, kl) == 0; 2698ce47dd6fc20961d278148c374e9aad6f981e97eAndre Eisenbach} 270