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 19444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji /****************************************************************************** 20444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 21444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * This file contains simple pairing algorithms 22444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji * 23444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji ******************************************************************************/ 24444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 25444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include <string.h> 26444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include "bt_target.h" 27444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include "p_256_ecc_pp.h" 28444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji#include "p_256_multprecision.h" 29444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 30444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_init(DWORD *c, uint32_t keyLength) 31444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 32444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 33444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i] = 0; 34444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 35444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 36444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_copy(DWORD *c, DWORD *a, uint32_t keyLength) 37444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 38444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 39444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i] = a[i]; 40444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 41444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 42444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojiint multiprecision_compare(DWORD *a, DWORD *b, uint32_t keyLength) 43444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 44444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (int i = keyLength - 1; i >= 0; i--) 45444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 46444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (a[i] > b[i]) 47444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return 1; 48444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (a[i] < b[i]) 49444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return -1; 50444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 51444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return 0; 52444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 53444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 54444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojiint multiprecision_iszero(DWORD *a, uint32_t keyLength) 55444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 56444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 57444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (a[i]) 58444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return 0; 59444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 60444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return 1; 61444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 62444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 63444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiUINT32 multiprecision_dword_bits(DWORD a) 64444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 65444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint32_t i; 66444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (i = 0; i < DWORD_BITS; i++, a >>= 1) 67444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (a == 0) 68444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji break; 69444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 70444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return i; 71444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 72444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 73444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiUINT32 multiprecision_most_signdwords(DWORD *a, uint32_t keyLength) 74444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 75444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji int i; 76444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (i = keyLength - 1; i >= 0; i--) 77444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (a[i]) 78444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji break; 79444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return (i + 1); 80444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 81444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 82444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiUINT32 multiprecision_most_signbits(DWORD *a, uint32_t keyLength) 83444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 84444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji int aMostSignDWORDs; 85444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 86444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji aMostSignDWORDs = multiprecision_most_signdwords(a, keyLength); 87444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (aMostSignDWORDs == 0) 88444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return 0; 89444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 90444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return (((aMostSignDWORDs-1) << DWORD_BITS_SHIFT) + 91444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_dword_bits(a[aMostSignDWORDs-1]) ); 92444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 93444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 94444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiDWORD multiprecision_add(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 95444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 96444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD carrier; 97444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD temp; 98444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 99444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier=0; 100444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 101444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 102444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji temp = a[i] + carrier; 103444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier = (temp < carrier); 104444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji temp += b[i]; 105444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier |= (temp < b[i]); 106444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i]=temp; 107444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 108444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 109444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return carrier; 110444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 111444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 112444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji//c=a-b 113444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiDWORD multiprecision_sub(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 114444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 115444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD borrow; 116444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD temp; 117444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 118444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji borrow=0; 119444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i=0; i < keyLength; i++) 120444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 121444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji temp = a[i] - borrow; 122444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji borrow = (temp > a[i]); 123444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i] = temp - b[i]; 124444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji borrow |= (c[i] > temp); 125444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 126444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 127444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return borrow; 128444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 129444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 130444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c = a << 1 131444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_lshift_mod(DWORD * c, DWORD * a, uint32_t keyLength) 132444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 133444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD carrier; 134444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp; 135444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 136444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (keyLength == KEY_LENGTH_DWORDS_P192) 137444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 138444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve.p; 139444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 140444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (keyLength == KEY_LENGTH_DWORDS_P256) 141444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 142444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve_p256.p; 143444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 144444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 145444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return; 146444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 147444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier = multiprecision_lshift(c, a, keyLength); 148444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (carrier) 149444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 150444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, keyLength); 151444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 152444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (multiprecision_compare(c, modp, keyLength)>=0) 153444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 154444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, keyLength); 155444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 156444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 157444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 158444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c=a>>1 159444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_rshift(DWORD * c, DWORD * a, uint32_t keyLength) 160444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 161444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji int j; 162444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD b = 1; 163444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 164444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji j = DWORD_BITS - b; 165444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 166444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD carrier = 0; 167444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD temp; 168444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (int i = keyLength-1; i >= 0; i--) 169444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 170444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji temp = a[i]; // in case of c==a 171444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i] = (temp >> b) | carrier; 172444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier = temp << j; 173444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 174444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 175444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 176444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// Curve specific optimization when p is a pseudo-Mersenns prime, p=2^(KEY_LENGTH_BITS)-omega 177444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_mersenns_mult_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 178444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 179444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD cc[2*KEY_LENGTH_DWORDS_P256]; 180444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 181444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_mult(cc, a, b, keyLength); 182444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (keyLength == 6) 183444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 184444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_fast_mod(c, cc); 185444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 186444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (keyLength == 8) 187444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 188444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_fast_mod_P256(c, cc); 189444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 190444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 191444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 192444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// Curve specific optimization when p is a pseudo-Mersenns prime 193444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_mersenns_squa_mod(DWORD *c, DWORD *a, uint32_t keyLength) 194444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 195444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_mersenns_mult_mod(c, a, a, keyLength); 196444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 197444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 198444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c=(a+b) mod p, b<p, a<p 199444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_add_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 200444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 201444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD carrier; 202444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp; 203444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 204444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (keyLength == KEY_LENGTH_DWORDS_P192) 205444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 206444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve.p; 207444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 208444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (keyLength == KEY_LENGTH_DWORDS_P256) 209444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 210444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve_p256.p; 211444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 212444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 213444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return; 214444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 215444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier = multiprecision_add(c, a, b, keyLength); 216444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (carrier) 217444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 218444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, keyLength); 219444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 220444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (multiprecision_compare(c, modp, keyLength) >= 0) 221444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 222444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, keyLength); 223444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 224444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 225444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 226444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c=(a-b) mod p, a<p, b<p 227444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_sub_mod(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 228444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 229444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD borrow; 230444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp; 231444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 232444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (keyLength == KEY_LENGTH_DWORDS_P192) 233444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 234444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve.p; 235444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 236444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if(keyLength == KEY_LENGTH_DWORDS_P256) 237444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 238444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve_p256.p; 239444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 240444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 241444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return; 242444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 243444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji borrow = multiprecision_sub(c, a, b, keyLength); 244444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if(borrow) 245444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_add(c, c, modp, keyLength); 246444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 247444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 248444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c=a<<b, b<DWORD_BITS, c has a buffer size of NumDWORDs+1 249444a8da807abaf5f9e813ce70c56a79160495fb3Satya CallojiDWORD multiprecision_lshift(DWORD * c, DWORD * a, uint32_t keyLength) 250444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 251444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji int j; 252444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint32_t b = 1; 253444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji j = DWORD_BITS - b; 254444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 255444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD carrier = 0; 256444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD temp; 257444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 258444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 259444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 260444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji temp = a[i]; // in case c==a 261444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i] = (temp << b) | carrier; 262444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji carrier = temp >> j; 263444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 264444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 265444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji return carrier; 266444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 267444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 268444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji// c=a*b; c must have a buffer of 2*Key_LENGTH_DWORDS, c != a != b 269444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_mult(DWORD *c, DWORD *a, DWORD *b, uint32_t keyLength) 270444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 271444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD W; 272444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD U; 273444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD V; 274444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 275444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = V = W = 0; 276444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_init(c, keyLength); 277444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 278444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji //assume little endian right now 279444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t i = 0; i < keyLength; i++) 280444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 281444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = 0; 282444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji for (uint32_t j = 0; j < keyLength; j++) 283444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 284444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint64_t result; 285444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji result = ((UINT64)a[i]) * ((uint64_t) b[j]); 286444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji W = result >> 32; 287444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = a[i] * b[j]; 288444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = V + U; 289444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (V < U); 290444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += W; 291444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = V + c[i+j]; 292444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (V < c[i+j]); 293444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i+j] = V; 294444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 295444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[i+keyLength] = U; 296444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 297444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 298444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 299444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_fast_mod(DWORD *c, DWORD *a) 300444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 301444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD U; 302444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD V; 303444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp = curve.p; 304444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 305444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] = a[0] + a[6]; 306444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U=c[0] < a[0]; 307444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] += a[10]; 308444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[0] < a[10]; 309444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 310444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] = a[1] + U; 311444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = c[1] < a[1]; 312444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] += a[7]; 313444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[1] < a[7]; 314444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] += a[11]; 315444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[1]< a[11]; 316444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 317444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] = a[2] + U; 318444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = c[2] < a[2]; 319444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += a[6]; 320444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[2] < a[6]; 321444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += a[8]; 322444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[2] < a[8]; 323444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += a[10]; 324444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[2] < a[10]; 325444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 326444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] = a[3]+U; 327444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = c[3] < a[3]; 328444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += a[7]; 329444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[3] < a[7]; 330444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += a[9]; 331444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[3] < a[9]; 332444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += a[11]; 333444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[3] < a[11]; 334444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 335444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] = a[4]+U; 336444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = c[4] < a[4]; 337444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += a[8]; 338444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[4] < a[8]; 339444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += a[10]; 340444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[4] < a[10]; 341444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 342444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] = a[5]+U; 343444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = c[5] < a[5]; 344444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += a[9]; 345444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[5] < a[9]; 346444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += a[11]; 347444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += c[5] < a[11]; 348444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 349444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] += U; 350444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[0] < U; 351444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] += V; 352444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[1] < V; 353444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += V; 354444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[2] < V; 355444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += U; 356444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[2] < U; 357444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += V; 358444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[3] < V; 359444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += V; 360444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[4] < V; 361444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += V; 362444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji V = c[5] < V; 363444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 364444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (V) 365444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 366444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192); 367444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 368444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if(multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P192) >= 0) 369444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 370444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P192); 371444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 372444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 373444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 374444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_fast_mod_P256(DWORD *c, DWORD *a) 375444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 376444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD A; 377444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD B; 378444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD C; 379444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD D; 380444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD E; 381444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD F; 382444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD G; 383444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UA; 384444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UB; 385444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UC; 386444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UD; 387444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UE; 388444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UF; 389444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji uint8_t UG; 390444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD U; 391444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp = curve_p256.p; 392444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 393444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // C = a[13] + a[14] + a[15]; 394444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji C = a[13]; 395444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji C += a[14]; 396444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UC = (C < a[14]); 397444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji C += a[15]; 398444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UC += (C < a[15]); 399444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 400444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // E = a[8] + a[9]; 401444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji E = a[8]; 402444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji E += a[9]; 403444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UE = (E < a[9]); 404444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 405444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // F = a[9] + a[10]; 406444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji F = a[9]; 407444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji F += a[10]; 408444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UF = (F < a[10]); 409444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 410444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // G = a[10] + a[11] 411444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji G = a[10]; 412444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji G += a[11]; 413444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UG = (G < a[11]); 414444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 415444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // B = a[12] + a[13] + a[14] + a[15] == C + a[12] 416444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji B = C; 417444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UB = UC; 418444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji B += a[12]; 419444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UB += (B < a[12]); 420444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 421444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // A = a[11] + a[12] + a[13] + a[14] == B + a[11] - a[15] 422444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A = B; 423444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UA = UB; 424444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A += a[11]; 425444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UA += (A < a[11]); 426444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UA -= (A < a[15]); 427444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A -= a[15]; 428444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 429444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji // D = a[10] + a[11] + a[12] + a[13] == A + a[10] - a[14] 430444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji D = A; 431444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UD = UA; 432444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji D += a[10]; 433444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UD += (D < a[10]); 434444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UD -= (D < a[14]); 435444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji D -= a[14]; 436444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 437444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] = a[0]; 438444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] += E; 439444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[0] < E); 440444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UE; 441444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[0] < A); 442444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UA; 443444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[0] -= A; 444444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 445444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 446444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 447444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 448444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 449444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[1] < UU); 450444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] = a[1] - UU; 451444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 452444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 453444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 454444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] = a[1] + U; 455444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[1] < a[1]); 456444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 457444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 458444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] += F; 459444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[1] < F); 460444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UF; 461444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[1] < B); 462444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UB; 463444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[1] -= B; 464444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 465444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 466444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 467444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 468444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 469444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[2] < UU); 470444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] = a[2] - UU; 471444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 472444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 473444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 474444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] = a[2] + U; 475444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[2] < a[2]); 476444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 477444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 478444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] += G; 479444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[2] < G); 480444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UG; 481444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[2] < C); 482444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UC; 483444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[2] -= C; 484444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 485444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 486444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 487444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 488444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 489444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[3] < UU); 490444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] = a[3] - UU; 491444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 492444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 493444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 494444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] = a[3] + U; 495444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[3] < a[3]); 496444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 497444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 498444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += A; 499444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[3] < A); 500444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UA; 501444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += a[11]; 502444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[3] < a[11]); 503444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] += a[12]; 504444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[3] < a[12]); 505444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[3] < a[14]); 506444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] -= a[14]; 507444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[3] < a[15]); 508444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] -= a[15]; 509444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[3] < E); 510444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UE; 511444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[3] -= E; 512444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 513444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 514444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 515444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 516444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 517444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[4] < UU); 518444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] = a[4] - UU; 519444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 520444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 521444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 522444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] = a[4] + U; 523444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[4] < a[4]); 524444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 525444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 526444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += B; 527444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[4] < B); 528444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UB; 529444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[4] < a[15]); 530444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] -= a[15]; 531444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += a[12]; 532444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[4] < a[12]); 533444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] += a[13]; 534444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[4] < a[13]); 535444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[4] < F); 536444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UF; 537444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[4] -= F; 538444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 539444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 540444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 541444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 542444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 543444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[5] < UU); 544444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] = a[5] - UU; 545444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 546444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 547444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 548444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] = a[5] + U; 549444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[5] < a[5]); 550444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 551444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 552444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += C; 553444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[5] < C); 554444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UC; 555444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += a[13]; 556444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[5] < a[13]); 557444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] += a[14]; 558444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[5] < a[14]); 559444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[5] < G); 560444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UG; 561444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[5] -= G; 562444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 563444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 564444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 565444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 566444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 567444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[6] < UU); 568444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] = a[6] - UU; 569444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 570444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 571444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 572444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] = a[6] + U; 573444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[6] < a[6]); 574444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 575444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 576444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] += C; 577444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[6] < C); 578444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += UC; 579444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] += a[14]; 580444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[6] < a[14]); 581444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] += a[14]; 582444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[6] < a[14]); 583444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] += a[15]; 584444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[6] < a[15]); 585444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[6] < E); 586444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UE; 587444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[6] -= E; 588444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 589444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 590444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 591444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD UU; 592444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji UU = 0 - U; 593444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (a[7] < UU); 594444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] = a[7] - UU; 595444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 596444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 597444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 598444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] = a[7] + U; 599444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U = (c[7] < a[7]); 600444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 601444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 602444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] += a[15]; 603444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[7] < a[15]); 604444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] += a[15]; 605444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[7] < a[15]); 606444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] += a[15]; 607444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[7] < a[15]); 608444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] += a[8]; 609444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U += (c[7] < a[8]); 610444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= (c[7] < D); 611444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U -= UD; 612444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji c[7] -= D; 613444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 614444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (U & 0x80000000) 615444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 616444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji while (U) 617444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 618444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_add(c, c, modp, KEY_LENGTH_DWORDS_P256); 619444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U++; 620444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 621444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 622444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else if (U) 623444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 624444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji while (U) 625444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 626444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256); 627444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji U--; 628444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 629444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 630444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 631444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (multiprecision_compare(c, modp, KEY_LENGTH_DWORDS_P256)>=0) 632444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(c, c, modp, KEY_LENGTH_DWORDS_P256); 633444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 634444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 635444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 636444a8da807abaf5f9e813ce70c56a79160495fb3Satya Callojivoid multiprecision_inv_mod(DWORD *aminus, DWORD *u, uint32_t keyLength) 637444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji{ 638444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD v[KEY_LENGTH_DWORDS_P256]; 639444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD A[KEY_LENGTH_DWORDS_P256+1]; 640444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD C[KEY_LENGTH_DWORDS_P256+1]; 641444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji DWORD *modp; 642444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 643444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if(keyLength == KEY_LENGTH_DWORDS_P256) 644444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 645444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve_p256.p; 646444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 647444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 648444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 649444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji modp = curve.p; 650444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 651444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 652444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_copy(v, modp, keyLength); 653444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_init(A, keyLength); 654444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_init(C, keyLength); 655444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A[0] = 1; 656444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 657444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji while (!multiprecision_iszero(u, keyLength)) 658444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 659444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji while (!(u[0] & 0x01)) // u is even 660444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 661444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(u, u, keyLength); 662444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if(!(A[0] & 0x01)) // A is even 663444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(A, A, keyLength); 664444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 665444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 666444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A[keyLength]=multiprecision_add(A, A, modp, keyLength); // A =A+p 667444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(A, A, keyLength); 668444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji A[keyLength-1] |= (A[keyLength]<<31); 669444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 670444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 671444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 672444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji while (!(v[0] & 0x01)) // v is even 673444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 674444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(v, v, keyLength); 675444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (!(C[0] & 0x01)) // C is even 676444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 677444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(C, C, keyLength); 678444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 679444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 680444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 681444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji C[keyLength] = multiprecision_add(C, C, modp, keyLength); // C =C+p 682444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_rshift(C, C, keyLength); 683444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji C[keyLength-1] |= (C[keyLength] << 31); 684444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 685444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 686444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 687444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (multiprecision_compare(u, v, keyLength) >= 0) 688444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 689444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(u, u, v, keyLength); 690444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub_mod(A, A, C, keyLength); 691444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 692444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 693444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji { 694444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(v, v, u, keyLength); 695444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub_mod(C, C, A, keyLength); 696444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 697444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji } 698444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 699444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji if (multiprecision_compare(C, modp, keyLength) >= 0) 700444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_sub(aminus, C, modp, keyLength); 701444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji else 702444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji multiprecision_copy(aminus, C, keyLength); 703444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji} 704444a8da807abaf5f9e813ce70c56a79160495fb3Satya Calloji 705