16de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root/* 26de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * Copyright 2013 The Android Open Source Project 36de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * 46de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * Redistribution and use in source and binary forms, with or without 56de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * modification, are permitted provided that the following conditions are met: 66de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * * Redistributions of source code must retain the above copyright 76de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * notice, this list of conditions and the following disclaimer. 86de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * * Redistributions in binary form must reproduce the above copyright 96de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * notice, this list of conditions and the following disclaimer in the 106de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * documentation and/or other materials provided with the distribution. 116de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * * Neither the name of Google Inc. nor the names of its contributors may 126de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * be used to endorse or promote products derived from this software 136de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * without specific prior written permission. 146de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * 156de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR 166de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 176de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 186de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 196de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 206de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 216de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 226de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 236de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 246de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 256de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root */ 266de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 276de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// This is an implementation of the P256 elliptic curve group. It's written to 286de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// be portable 32-bit, although it's still constant-time. 296de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// 306de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// WARNING: Implementing these functions in a constant-time manner is far from 316de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// obvious. Be careful when touching this code. 326de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// 336de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background. 346de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 356de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root#include <assert.h> 366de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root#include <stdint.h> 376de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root#include <string.h> 386de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root#include <stdio.h> 396de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 40fca75c837bebfbd51927156158de36fc517742f7Mattias Nissler#include "constrainedcrypto/p256.h" 416de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 426de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootconst p256_int SECP256r1_n = // curve order 436de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root {{0xfc632551, 0xf3b9cac2, 0xa7179e84, 0xbce6faad, -1, -1, 0, -1}}; 446de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 456de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootconst p256_int SECP256r1_p = // curve field size 466de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root {{-1, -1, -1, 0, 0, 0, 1, -1 }}; 476de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 486de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootconst p256_int SECP256r1_b = // curve b 496de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root {{0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0, 506de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8}}; 516de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 526de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_init(p256_int* a) { 536de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root memset(a, 0, sizeof(*a)); 546de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 556de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 566de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_clear(p256_int* a) { p256_init(a); } 576de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 586de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_get_bit(const p256_int* scalar, int bit) { 596de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return (P256_DIGIT(scalar, bit / P256_BITSPERDIGIT) 606de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root >> (bit & (P256_BITSPERDIGIT - 1))) & 1; 616de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 626de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 636de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_is_zero(const p256_int* a) { 646de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i, result = 0; 656de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) result |= P256_DIGIT(a, i); 666de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return !result; 676de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 686de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 696de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// top, c[] += a[] * b 706de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// Returns new top 716de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootstatic p256_digit mulAdd(const p256_int* a, 726de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit b, 736de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top, 746de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit* c) { 756de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 766de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_ddigit carry = 0; 776de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 786de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 796de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += *c; 806de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += (p256_ddigit)P256_DIGIT(a, i) * b; 816de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root *c++ = (p256_digit)carry; 826de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry >>= P256_BITSPERDIGIT; 836de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 846de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return top + (p256_digit)carry; 856de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 866de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 876de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// top, c[] -= top_a, a[] 886de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootstatic p256_digit subTop(p256_digit top_a, 896de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_digit* a, 906de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top_c, 916de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit* c) { 926de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 936de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sddigit borrow = 0; 946de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 956de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 966de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow += *c; 976de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow -= *a++; 986de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root *c++ = (p256_digit)borrow; 996de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow >>= P256_BITSPERDIGIT; 1006de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 1016de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow += top_c; 1026de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow -= top_a; 1036de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top_c = (p256_digit)borrow; 1046de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root assert((borrow >> P256_BITSPERDIGIT) == 0); 1056de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return top_c; 1066de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 1076de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1086de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// top, c[] -= MOD[] & mask (0 or -1) 1096de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// returns new top. 1106de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootstatic p256_digit subM(const p256_int* MOD, 1116de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top, 1126de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit* c, 1136de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit mask) { 1146de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 1156de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sddigit borrow = 0; 1166de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 1176de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow += *c; 1186de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow -= P256_DIGIT(MOD, i) & mask; 1196de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root *c++ = (p256_digit)borrow; 1206de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow >>= P256_BITSPERDIGIT; 1216de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 1226de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return top + (p256_digit)borrow; 1236de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 1246de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1256de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// top, c[] += MOD[] & mask (0 or -1) 1266de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// returns new top. 1276de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootstatic p256_digit addM(const p256_int* MOD, 1286de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top, 1296de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit* c, 1306de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit mask) { 1316de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 1326de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_ddigit carry = 0; 1336de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 1346de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += *c; 1356de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += P256_DIGIT(MOD, i) & mask; 1366de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root *c++ = (p256_digit)carry; 1376de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry >>= P256_BITSPERDIGIT; 1386de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 1396de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return top + (p256_digit)carry; 1406de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 1416de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1426de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// c = a * b mod MOD. c can be a and/or b. 1436de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_modmul(const p256_int* MOD, 1446de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_int* a, 1456de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_digit top_b, 1466de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_int* b, 1476de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int* c) { 1486de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit tmp[P256_NDIGITS * 2 + 1] = { 0 }; 1496de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top = 0; 1506de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 1516de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1526de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Multiply/add into tmp. 1536de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 1546de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (i) tmp[i + P256_NDIGITS - 1] = top; 1556de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = mulAdd(a, P256_DIGIT(b, i), 0, tmp + i); 1566de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 1576de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1586de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Multiply/add top digit 1596de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root tmp[i + P256_NDIGITS - 1] = top; 1606de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = mulAdd(a, top_b, 0, tmp + i); 1616de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1626de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Reduce tmp, digit by digit. 1636de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (; i >= 0; --i) { 1646de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit reducer[P256_NDIGITS] = { 0 }; 1656de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top_reducer; 1666de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1676de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // top can be any value at this point. 1686de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Guestimate reducer as top * MOD, since msw of MOD is -1. 1696de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top_reducer = mulAdd(MOD, top, 0, reducer); 1706de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1716de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Subtract reducer from top | tmp. 1726de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = subTop(top_reducer, reducer, top, tmp + i); 1736de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1746de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // top is now either 0 or 1. Make it 0, fixed-timing. 1756de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root assert(top <= 1); 1766de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1776de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = subM(MOD, top, tmp + i, ~(top - 1)); 1786de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1796de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root assert(top == 0); 1806de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1816de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // We have now reduced the top digit off tmp. Fetch new top digit. 1826de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = tmp[i + P256_NDIGITS - 1]; 1836de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 1846de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1856de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // tmp might still be larger than MOD, yet same bit length. 1866de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Make sure it is less, fixed-timing. 1876de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root addM(MOD, 0, tmp, subM(MOD, 0, tmp, -1)); 1886de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1896de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root memcpy(c, tmp, P256_NBYTES); 1906de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 1916de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_is_odd(const p256_int* a) { return P256_DIGIT(a, 0) & 1; } 1926de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_is_even(const p256_int* a) { return !(P256_DIGIT(a, 0) & 1); } 1936de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1946de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootp256_digit p256_shl(const p256_int* a, int n, p256_int* b) { 1956de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 1966de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit top = P256_DIGIT(a, P256_NDIGITS - 1); 1976de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 1986de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root n %= P256_BITSPERDIGIT; 1996de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = P256_NDIGITS - 1; i > 0; --i) { 2006de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit accu = (P256_DIGIT(a, i) << n); 2016de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root accu |= (P256_DIGIT(a, i - 1) >> (P256_BITSPERDIGIT - n)); 2026de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = accu; 2036de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2046de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = (P256_DIGIT(a, i) << n); 2056de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2066de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root top = (p256_digit)((((p256_ddigit)top) << n) >> P256_BITSPERDIGIT); 2076de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2086de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return top; 2096de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2106de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2116de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_shr(const p256_int* a, int n, p256_int* b) { 2126de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2136de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2146de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root n %= P256_BITSPERDIGIT; 2156de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS - 1; ++i) { 2166de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit accu = (P256_DIGIT(a, i) >> n); 2176de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - n)); 2186de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = accu; 2196de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2206de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> n); 2216de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2226de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2236de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootstatic void p256_shr1(const p256_int* a, int highbit, p256_int* b) { 2246de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2256de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2266de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS - 1; ++i) { 2276de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit accu = (P256_DIGIT(a, i) >> 1); 2286de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - 1)); 2296de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = accu; 2306de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2316de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> 1) | 2326de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root (highbit << (P256_BITSPERDIGIT - 1)); 2336de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2346de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2356de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// Return -1, 0, 1 for a < b, a == b or a > b respectively. 2366de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_cmp(const p256_int* a, const p256_int* b) { 2376de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2386de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sddigit borrow = 0; 2396de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_digit notzero = 0; 2406de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2416de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 2426de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i); 2436de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Track whether any result digit is ever not zero. 2446de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // Relies on !!(non-zero) evaluating to 1, e.g., !!(-1) evaluating to 1. 2456de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root notzero |= !!((p256_digit)borrow); 2466de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow >>= P256_BITSPERDIGIT; 2476de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2486de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return (int)borrow | notzero; 2496de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2506de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2516de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// c = a - b. Returns borrow: 0 or -1. 2526de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_sub(const p256_int* a, const p256_int* b, p256_int* c) { 2536de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2546de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sddigit borrow = 0; 2556de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2566de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 2576de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i); 2586de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (c) P256_DIGIT(c, i) = (p256_digit)borrow; 2596de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root borrow >>= P256_BITSPERDIGIT; 2606de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2616de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return (int)borrow; 2626de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2636de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2646de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// c = a + b. Returns carry: 0 or 1. 2656de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_add(const p256_int* a, const p256_int* b, p256_int* c) { 2666de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2676de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_ddigit carry = 0; 2686de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2696de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 2706de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += (p256_ddigit)P256_DIGIT(a, i) + P256_DIGIT(b, i); 2716de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (c) P256_DIGIT(c, i) = (p256_digit)carry; 2726de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry >>= P256_BITSPERDIGIT; 2736de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2746de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return (int)carry; 2756de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2766de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2776de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// b = a + d. Returns carry, 0 or 1. 2786de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_add_d(const p256_int* a, p256_digit d, p256_int* b) { 2796de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 2806de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_ddigit carry = d; 2816de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2826de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = 0; i < P256_NDIGITS; ++i) { 2836de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry += (p256_ddigit)P256_DIGIT(a, i); 2846de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (b) P256_DIGIT(b, i) = (p256_digit)carry; 2856de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root carry >>= P256_BITSPERDIGIT; 2866de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 2876de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return (int)carry; 2886de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 2896de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2906de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// b = 1/a mod MOD, binary euclid. 2916de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_modinv_vartime(const p256_int* MOD, 2926de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_int* a, 2936de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int* b) { 2946de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int R = P256_ZERO; 2956de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int S = P256_ONE; 2966de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int U = *MOD; 2976de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int V = *a; 2986de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 2996de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (;;) { 3006de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_is_even(&U)) { 3016de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&U, 0, &U); 3026de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_is_even(&R)) { 3036de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&R, 0, &R); 3046de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } else { 3056de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // R = (R+MOD)/2 3066de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&R, p256_add(&R, MOD, &R), &R); 3076de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3086de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } else if (p256_is_even(&V)) { 3096de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&V, 0, &V); 3106de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_is_even(&S)) { 3116de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&S, 0, &S); 3126de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } else { 3136de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root // S = (S+MOD)/2 3146de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_shr1(&S, p256_add(&S, MOD, &S) , &S); 3156de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3166de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } else { // U,V both odd. 3176de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (!p256_sub(&V, &U, NULL)) { 3186de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sub(&V, &U, &V); 3196de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_sub(&S, &R, &S)) p256_add(&S, MOD, &S); 3206de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_is_zero(&V)) break; // done. 3216de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } else { 3226de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sub(&U, &V, &U); 3236de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_sub(&R, &S, &R)) p256_add(&R, MOD, &R); 3246de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3256de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3266de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3276de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3286de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_mod(MOD, &R, b); 3296de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 3306de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3316de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_mod(const p256_int* MOD, 3326de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const p256_int* in, 3336de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int* out) { 3346de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (out != in) *out = *in; 3356de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root addM(MOD, 0, P256_DIGITS(out), subM(MOD, 0, P256_DIGITS(out), -1)); 3366de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 3376de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3386de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// Verify y^2 == x^3 - 3x + b mod p 3396de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root// and 0 < x < p and 0 < y < p 3406de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootint p256_is_valid_point(const p256_int* x, const p256_int* y) { 3416de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_int y2, x3; 3426de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3436de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_cmp(&SECP256r1_p, x) <= 0 || 3446de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_cmp(&SECP256r1_p, y) <= 0 || 3456de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_is_zero(x) || 3466de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_is_zero(y)) return 0; 3476de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3486de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_modmul(&SECP256r1_p, y, 0, y, &y2); // y^2 3496de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3506de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_modmul(&SECP256r1_p, x, 0, x, &x3); // x^2 3516de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_modmul(&SECP256r1_p, x, 0, &x3, &x3); // x^3 3526de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - x 3536de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - 2x 3546de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3); // x^3 - 3x 3556de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root if (p256_add(&x3, &SECP256r1_b, &x3)) // x^3 - 3x + b 3566de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p256_sub(&x3, &SECP256r1_p, &x3); 3576de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3586de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root return p256_cmp(&y2, &x3) == 0; 3596de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 3606de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3616de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Rootvoid p256_from_bin(const uint8_t src[P256_NBYTES], p256_int* dst) { 3626de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root int i; 3636de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root const uint8_t* p = &src[0]; 3646de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root 3656de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root for (i = P256_NDIGITS - 1; i >= 0; --i) { 3666de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root P256_DIGIT(dst, i) = 3676de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root (p[0] << 24) | 3686de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root (p[1] << 16) | 3696de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root (p[2] << 8) | 3706de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p[3]; 3716de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root p += 4; 3726de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root } 3736de2e5a9f46dcd05c5bbc407ddac8fb05a82c78fKenny Root} 374