1139776Simp/* 222521Sdyson * Copyright 2011-2021 The OpenSSL Project Authors. All Rights Reserved. 31541Srgrimes * 41541Srgrimes * Licensed under the Apache License 2.0 (the "License"). You may not use 51541Srgrimes * this file except in compliance with the License. You can obtain a copy 61541Srgrimes * in the file LICENSE in the source distribution or at 71541Srgrimes * https://www.openssl.org/source/license.html 81541Srgrimes */ 91541Srgrimes 101541Srgrimes/* Copyright 2011 Google Inc. 111541Srgrimes * 121541Srgrimes * Licensed under the Apache License, Version 2.0 (the "License"); 131541Srgrimes * 141541Srgrimes * you may not use this file except in compliance with the License. 151541Srgrimes * You may obtain a copy of the License at 161541Srgrimes * 171541Srgrimes * http://www.apache.org/licenses/LICENSE-2.0 181541Srgrimes * 191541Srgrimes * Unless required by applicable law or agreed to in writing, software 201541Srgrimes * distributed under the License is distributed on an "AS IS" BASIS, 211541Srgrimes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 221541Srgrimes * See the License for the specific language governing permissions and 231541Srgrimes * limitations under the License. 241541Srgrimes */ 251541Srgrimes 261541Srgrimes/* 271541Srgrimes * ECDSA low level APIs are deprecated for public use, but still ok for 281541Srgrimes * internal use. 291541Srgrimes */ 301541Srgrimes#include "internal/deprecated.h" 311541Srgrimes 3222521Sdyson#include <openssl/opensslconf.h> 331541Srgrimes 3450477Speter/* 351541Srgrimes * Common utility functions for ecp_nistp224.c, ecp_nistp256.c, ecp_nistp521.c. 361541Srgrimes */ 371541Srgrimes 381541Srgrimes#include <stddef.h> 391541Srgrimes#include "ec_local.h" 401541Srgrimes 411541Srgrimes/* 421541Srgrimes * Convert an array of points into affine coordinates. (If the point at 4376166Smarkm * infinity is found (Z = 0), it remains unchanged.) This function is 4476166Smarkm * essentially an equivalent to EC_POINTs_make_affine(), but works with the 453034Sdg * internal representation of points as used by ecp_nistp###.c rather than 4676166Smarkm * with (BIGNUM-based) EC_POINT data structures. point_array is the 4789316Salfred * input/output buffer ('num' points in projective form, i.e. three 4876166Smarkm * coordinates each), based on an internal representation of field elements 4976166Smarkm * of size 'felem_size'. tmp_felems needs to point to a temporary array of 5076166Smarkm * 'num'+1 field elements for storage of intermediate values. 511541Srgrimes */ 5276166Smarkmvoid 531541Srgrimesossl_ec_GFp_nistp_points_make_affine_internal(size_t num, void *point_array, 541541Srgrimes size_t felem_size, 5576166Smarkm void *tmp_felems, 5676166Smarkm void (*felem_one) (void *out), 5777031Sru int (*felem_is_zero) (const void 581541Srgrimes *in), 5930354Sphk void (*felem_assign) (void *out, 6030354Sphk const void 61116271Sphk *in), 62116271Sphk void (*felem_square) (void *out, 63116271Sphk const void 6412335Sbde *in), 65138489Sphk void (*felem_mul) (void *out, 66138489Sphk const void 67138489Sphk *in1, 68138489Sphk const void 69138489Sphk *in2), 70138489Sphk void (*felem_inv) (void *out, 71138489Sphk const void 72138489Sphk *in), 73138489Sphk void (*felem_contract) (void 74138489Sphk *out, 75138489Sphk const 76138489Sphk void 77138489Sphk *in)) 78138489Sphk{ 79138489Sphk int i = 0; 80138489Sphk 81138489Sphk#define tmp_felem(I) (&((char *)tmp_felems)[(I) * felem_size]) 82138489Sphk#define X(I) (&((char *)point_array)[3*(I) * felem_size]) 83138489Sphk#define Y(I) (&((char *)point_array)[(3*(I) + 1) * felem_size]) 84138489Sphk#define Z(I) (&((char *)point_array)[(3*(I) + 2) * felem_size]) 85138489Sphk 86138489Sphk if (!felem_is_zero(Z(0))) 87138489Sphk felem_assign(tmp_felem(0), Z(0)); 88138489Sphk else 891541Srgrimes felem_one(tmp_felem(0)); 901541Srgrimes for (i = 1; i < (int)num; i++) { 911541Srgrimes if (!felem_is_zero(Z(i))) 9212769Sphk felem_mul(tmp_felem(i), tmp_felem(i - 1), Z(i)); 93138489Sphk else 941541Srgrimes felem_assign(tmp_felem(i), tmp_felem(i - 1)); 951541Srgrimes } 961541Srgrimes /* 971541Srgrimes * Now each tmp_felem(i) is the product of Z(0) .. Z(i), skipping any 981541Srgrimes * zero-valued factors: if Z(i) = 0, we essentially pretend that Z(i) = 1 9916312Sdg */ 100138489Sphk 101138489Sphk felem_inv(tmp_felem(num - 1), tmp_felem(num - 1)); 1021541Srgrimes for (i = num - 1; i >= 0; i--) { 103138489Sphk if (i > 0) 104138489Sphk /* 1051541Srgrimes * tmp_felem(i-1) is the product of Z(0) .. Z(i-1), tmp_felem(i) 106138489Sphk * is the inverse of the product of Z(0) .. Z(i) 107138489Sphk */ 108138489Sphk /* 1/Z(i) */ 109138489Sphk felem_mul(tmp_felem(num), tmp_felem(i - 1), tmp_felem(i)); 1103496Sphk else 1111541Srgrimes felem_assign(tmp_felem(num), tmp_felem(0)); /* 1/Z(0) */ 1121541Srgrimes 113138489Sphk if (!felem_is_zero(Z(i))) { 1141541Srgrimes if (i > 0) 11586872Sdillon /* 11686872Sdillon * For next iteration, replace tmp_felem(i-1) by its inverse 11786872Sdillon */ 11886872Sdillon felem_mul(tmp_felem(i - 1), tmp_felem(i), Z(i)); 119109153Sdillon 12069149Sjlemon /* 12183366Sjulian * Convert point (X, Y, Z) into affine form (X/(Z^2), Y/(Z^3), 1) 1221541Srgrimes */ 12369149Sjlemon felem_square(Z(i), tmp_felem(num)); /* 1/(Z^2) */ 1241541Srgrimes felem_mul(X(i), X(i), Z(i)); /* X/(Z^2) */ 12516312Sdg felem_mul(Z(i), Z(i), tmp_felem(num)); /* 1/(Z^3) */ 126111119Simp felem_mul(Y(i), Y(i), Z(i)); /* Y/(Z^3) */ 12716312Sdg felem_contract(X(i), X(i)); 12816312Sdg felem_contract(Y(i), Y(i)); 129111119Simp felem_one(Z(i)); 13016312Sdg } else { 131138290Sphk if (i > 0) 13216312Sdg /* 13330354Sphk * For next iteration, replace tmp_felem(i-1) by its inverse 13416312Sdg */ 13583366Sjulian felem_assign(tmp_felem(i - 1), tmp_felem(i)); 1361541Srgrimes } 13716312Sdg } 1381541Srgrimes} 13916312Sdg 1401541Srgrimes/*- 141101308Sjeff * This function looks at 5+1 scalar bits (5 current, 1 adjacent less 1421541Srgrimes * significant bit), and recodes them into a signed digit for use in fast point 1431541Srgrimes * multiplication: the use of signed rather than unsigned digits means that 1441541Srgrimes * fewer points need to be precomputed, given that point inversion is easy 1451541Srgrimes * (a precomputed point dP makes -dP available as well). 14689306Salfred * 14789306Salfred * BACKGROUND: 1481541Srgrimes * 1491541Srgrimes * Signed digits for multiplication were introduced by Booth ("A signed binary 1501541Srgrimes * multiplication technique", Quart. Journ. Mech. and Applied Math., vol. IV, 15122521Sdyson * pt. 2 (1951), pp. 236-240), in that case for multiplication of integers. 1521541Srgrimes * Booth's original encoding did not generally improve the density of nonzero 153138489Sphk * digits over the binary representation, and was merely meant to simplify the 15483366Sjulian * handling of signed factors given in two's complement; but it has since been 1551541Srgrimes * shown to be the basis of various signed-digit representations that do have 1561541Srgrimes * further advantages, including the wNAF, using the following general approach: 1571541Srgrimes * 15812769Sphk * (1) Given a binary representation 15983366Sjulian * 1601541Srgrimes * b_k ... b_2 b_1 b_0, 1611541Srgrimes * 16283366Sjulian * of a nonnegative integer (b_k in {0, 1}), rewrite it in digits 0, 1, -1 1631541Srgrimes * by using bit-wise subtraction as follows: 1641541Srgrimes * 1651541Srgrimes * b_k b_(k-1) ... b_2 b_1 b_0 1661541Srgrimes * - b_k ... b_3 b_2 b_1 b_0 16722521Sdyson * ----------------------------------------- 1681541Srgrimes * s_(k+1) s_k ... s_3 s_2 s_1 s_0 1691541Srgrimes * 1701541Srgrimes * A left-shift followed by subtraction of the original value yields a new 1711541Srgrimes * representation of the same value, using signed bits s_i = b_(i-1) - b_i. 1721541Srgrimes * This representation from Booth's paper has since appeared in the 1731541Srgrimes * literature under a variety of different names including "reversed binary 1741541Srgrimes * form", "alternating greedy expansion", "mutual opposite form", and 1751541Srgrimes * "sign-alternating {+-1}-representation". 1768876Srgrimes * 1771541Srgrimes * An interesting property is that among the nonzero bits, values 1 and -1 1781541Srgrimes * strictly alternate. 1791541Srgrimes * 18076688Siedowse * (2) Various window schemes can be applied to the Booth representation of 181132023Salfred * integers: for example, right-to-left sliding windows yield the wNAF 1823496Sphk * (a signed-digit encoding independently discovered by various researchers 1831541Srgrimes * in the 1990s), and left-to-right sliding windows yield a left-to-right 1841541Srgrimes * equivalent of the wNAF (independently discovered by various researchers 1851541Srgrimes * around 2004). 1861541Srgrimes * 1871541Srgrimes * To prevent leaking information through side channels in point multiplication, 1881541Srgrimes * we need to recode the given integer into a regular pattern: sliding windows 1891541Srgrimes * as in wNAFs won't do, we need their fixed-window equivalent -- which is a few 190109153Sdillon * decades older: we'll be using the so-called "modified Booth encoding" due to 1911541Srgrimes * MacSorley ("High-speed arithmetic in binary computers", Proc. IRE, vol. 49 1921541Srgrimes * (1961), pp. 67-91), in a radix-2^5 setting. That is, we always combine five 1931541Srgrimes * signed bits into a signed digit: 1941541Srgrimes * 19583366Sjulian * s_(5j + 4) s_(5j + 3) s_(5j + 2) s_(5j + 1) s_(5j) 1961541Srgrimes * 1971541Srgrimes * The sign-alternating property implies that the resulting digit values are 1981541Srgrimes * integers from -16 to 16. 19930354Sphk * 2001541Srgrimes * Of course, we don't actually need to compute the signed digits s_i as an 2011541Srgrimes * intermediate step (that's just a nice way to see how this scheme relates 2021541Srgrimes * to the wNAF): a direct computation obtains the recoded digit from the 2031541Srgrimes * six bits b_(5j + 4) ... b_(5j - 1). 20412769Sphk * 205144058Sjeff * This function takes those six bits as an integer (0 .. 63), writing the 2061541Srgrimes * recoded digit to *sign (0 for positive, 1 for negative) and *digit (absolute 207144058Sjeff * value, in the range 0 .. 16). Note that this integer essentially provides 2081541Srgrimes * the input bits "shifted to the left" by one position: for example, the input 209132023Salfred * to compute the least significant recoded digit, given that there's no bit 2101541Srgrimes * b_-1, has to be b_4 b_3 b_2 b_1 b_0 0. 2111541Srgrimes * 2121541Srgrimes */ 2131541Srgrimesvoid ossl_ec_GFp_nistp_recode_scalar_bits(unsigned char *sign, 2141541Srgrimes unsigned char *digit, unsigned char in) 2151541Srgrimes{ 2161541Srgrimes unsigned char s, d; 2171541Srgrimes 21883366Sjulian s = ~((in >> 5) - 1); /* sets all bits to MSB(in), 'in' seen as 2191541Srgrimes * 6-bit value */ 2201541Srgrimes d = (1 << 6) - in - 1; 2211541Srgrimes d = (d & s) | (in & ~s); 2221541Srgrimes d = (d >> 1) + (d & 1); 22312769Sphk 22483366Sjulian *sign = s & 1; 2251541Srgrimes *digit = d; 2261541Srgrimes} 22783366Sjulian