annotate curve25519-donna.c @ 1434:27b9ddb06b09

Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 11:53:32 +0800
parents d3925ed45a85
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* Copyright 2008, Google Inc.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 * All rights reserved.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * Redistribution and use in source and binary forms, with or without
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 * modification, are permitted provided that the following conditions are
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * met:
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * * Redistributions of source code must retain the above copyright
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 * notice, this list of conditions and the following disclaimer.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * * Redistributions in binary form must reproduce the above
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * copyright notice, this list of conditions and the following disclaimer
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 * in the documentation and/or other materials provided with the
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * distribution.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 * * Neither the name of Google Inc. nor the names of its
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 * contributors may be used to endorse or promote products derived from
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 * this software without specific prior written permission.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 * curve25519-donna: Curve25519 elliptic curve, public key function
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 * http://code.google.com/p/curve25519-donna/
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 * Adam Langley <[email protected]>
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 * Derived from public domain C code by Daniel J. Bernstein <[email protected]>
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 * More information about curve25519 can be found here
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 * http://cr.yp.to/ecdh.html
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 * djb's sample implementation of curve25519 is written in a special assembly
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 * language called qhasm and uses the floating point registers.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 * This is, almost, a clean room reimplementation from the curve25519 paper. It
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 * uses many of the tricks described therein. Only the crecip function is taken
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
46 * from the sample implementation. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 #include <string.h>
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 #include <stdint.h>
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 #ifdef _MSC_VER
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 #define inline __inline
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 #endif
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 typedef uint8_t u8;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 typedef int32_t s32;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 typedef int64_t limb;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 /* Field element representation:
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 * Field elements are written as an array of signed, 64-bit limbs, least
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 * significant first. The value of the field element is:
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ...
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 *
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
65 * i.e. the limbs are 26, 25, 26, 25, ... bits wide. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 /* Sum two numbers: output += in */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 static void fsum(limb *output, const limb *in) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 unsigned i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 for (i = 0; i < 10; i += 2) {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
71 output[0+i] = output[0+i] + in[0+i];
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
72 output[1+i] = output[1+i] + in[1+i];
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 /* Find the difference of two numbers: output = in - output
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
77 * (note the order of the arguments!). */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 static void fdifference(limb *output, const limb *in) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 unsigned i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 for (i = 0; i < 10; ++i) {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
81 output[i] = in[i] - output[i];
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 /* Multiply a number by a scalar: output = in * scalar */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 static void fscalar_product(limb *output, const limb *in, const limb scalar) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 unsigned i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 for (i = 0; i < 10; ++i) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89 output[i] = in[i] * scalar;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 /* Multiply two numbers: output = in2 * in
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95 * output must be distinct to both inputs. The inputs are reduced coefficient
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 * form, the output is not.
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
97 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
98 * output[x] <= 14 * the largest product of the input limbs. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 static void fproduct(limb *output, const limb *in2, const limb *in) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
100 output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
101 output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102 ((limb) ((s32) in2[1])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103 output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 ((limb) ((s32) in2[0])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105 ((limb) ((s32) in2[2])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 ((limb) ((s32) in2[2])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108 ((limb) ((s32) in2[0])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
109 ((limb) ((s32) in2[3])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110 output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
111 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
112 ((limb) ((s32) in2[3])) * ((s32) in[1])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
113 ((limb) ((s32) in2[0])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 ((limb) ((s32) in2[4])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115 output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116 ((limb) ((s32) in2[3])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 ((limb) ((s32) in2[1])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118 ((limb) ((s32) in2[4])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
119 ((limb) ((s32) in2[0])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120 ((limb) ((s32) in2[5])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 ((limb) ((s32) in2[1])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123 ((limb) ((s32) in2[5])) * ((s32) in[1])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
124 ((limb) ((s32) in2[2])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 ((limb) ((s32) in2[4])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 ((limb) ((s32) in2[0])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 ((limb) ((s32) in2[6])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
128 output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129 ((limb) ((s32) in2[4])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130 ((limb) ((s32) in2[2])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
131 ((limb) ((s32) in2[5])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 ((limb) ((s32) in2[1])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133 ((limb) ((s32) in2[6])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134 ((limb) ((s32) in2[0])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 ((limb) ((s32) in2[7])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
136 output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
137 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
138 ((limb) ((s32) in2[5])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
139 ((limb) ((s32) in2[1])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
140 ((limb) ((s32) in2[7])) * ((s32) in[1])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
141 ((limb) ((s32) in2[2])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
142 ((limb) ((s32) in2[6])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
143 ((limb) ((s32) in2[0])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
144 ((limb) ((s32) in2[8])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
145 output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
146 ((limb) ((s32) in2[5])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
147 ((limb) ((s32) in2[3])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
148 ((limb) ((s32) in2[6])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
149 ((limb) ((s32) in2[2])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
150 ((limb) ((s32) in2[7])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
151 ((limb) ((s32) in2[1])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
152 ((limb) ((s32) in2[8])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
153 ((limb) ((s32) in2[0])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
154 ((limb) ((s32) in2[9])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
155 output[10] = 2 * (((limb) ((s32) in2[5])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
156 ((limb) ((s32) in2[3])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
157 ((limb) ((s32) in2[7])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
158 ((limb) ((s32) in2[1])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
159 ((limb) ((s32) in2[9])) * ((s32) in[1])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
160 ((limb) ((s32) in2[4])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
161 ((limb) ((s32) in2[6])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
162 ((limb) ((s32) in2[2])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
163 ((limb) ((s32) in2[8])) * ((s32) in[2]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
164 output[11] = ((limb) ((s32) in2[5])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
165 ((limb) ((s32) in2[6])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
166 ((limb) ((s32) in2[4])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
167 ((limb) ((s32) in2[7])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
168 ((limb) ((s32) in2[3])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
169 ((limb) ((s32) in2[8])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
170 ((limb) ((s32) in2[2])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
171 ((limb) ((s32) in2[9])) * ((s32) in[2]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
172 output[12] = ((limb) ((s32) in2[6])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
173 2 * (((limb) ((s32) in2[5])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
174 ((limb) ((s32) in2[7])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
175 ((limb) ((s32) in2[3])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
176 ((limb) ((s32) in2[9])) * ((s32) in[3])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
177 ((limb) ((s32) in2[4])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
178 ((limb) ((s32) in2[8])) * ((s32) in[4]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
179 output[13] = ((limb) ((s32) in2[6])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
180 ((limb) ((s32) in2[7])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
181 ((limb) ((s32) in2[5])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
182 ((limb) ((s32) in2[8])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
183 ((limb) ((s32) in2[4])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
184 ((limb) ((s32) in2[9])) * ((s32) in[4]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
185 output[14] = 2 * (((limb) ((s32) in2[7])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
186 ((limb) ((s32) in2[5])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
187 ((limb) ((s32) in2[9])) * ((s32) in[5])) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
188 ((limb) ((s32) in2[6])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
189 ((limb) ((s32) in2[8])) * ((s32) in[6]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
190 output[15] = ((limb) ((s32) in2[7])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
191 ((limb) ((s32) in2[8])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
192 ((limb) ((s32) in2[6])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
193 ((limb) ((s32) in2[9])) * ((s32) in[6]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
194 output[16] = ((limb) ((s32) in2[8])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
195 2 * (((limb) ((s32) in2[7])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
196 ((limb) ((s32) in2[9])) * ((s32) in[7]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
197 output[17] = ((limb) ((s32) in2[8])) * ((s32) in[9]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
198 ((limb) ((s32) in2[9])) * ((s32) in[8]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
199 output[18] = 2 * ((limb) ((s32) in2[9])) * ((s32) in[9]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
200 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
201
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
202 /* Reduce a long form to a short form by taking the input mod 2^255 - 19.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
203 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
204 * On entry: |output[i]| < 14*2^54
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
205 * On exit: |output[0..8]| < 280*2^54 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
206 static void freduce_degree(limb *output) {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
207 /* Each of these shifts and adds ends up multiplying the value by 19.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
208 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
209 * For output[0..8], the absolute entry value is < 14*2^54 and we add, at
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
210 * most, 19*14*2^54 thus, on exit, |output[0..8]| < 280*2^54. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
211 output[8] += output[18] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
212 output[8] += output[18] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
213 output[8] += output[18];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
214 output[7] += output[17] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
215 output[7] += output[17] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
216 output[7] += output[17];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
217 output[6] += output[16] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
218 output[6] += output[16] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
219 output[6] += output[16];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
220 output[5] += output[15] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
221 output[5] += output[15] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
222 output[5] += output[15];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
223 output[4] += output[14] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
224 output[4] += output[14] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
225 output[4] += output[14];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
226 output[3] += output[13] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
227 output[3] += output[13] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
228 output[3] += output[13];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
229 output[2] += output[12] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
230 output[2] += output[12] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
231 output[2] += output[12];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
232 output[1] += output[11] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
233 output[1] += output[11] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
234 output[1] += output[11];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
235 output[0] += output[10] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
236 output[0] += output[10] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
237 output[0] += output[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
238 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
239
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
240 #if (-1 & 3) != 3
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
241 #error "This code only works on a two's complement system"
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
242 #endif
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
243
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
244 /* return v / 2^26, using only shifts and adds.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
245 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
246 * On entry: v can take any value. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
247 static inline limb
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
248 div_by_2_26(const limb v)
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
249 {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
250 /* High word of v; no shift needed. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
251 const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
252 /* Set to all 1s if v was negative; else set to 0s. */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
253 const int32_t sign = ((int32_t) highword) >> 31;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
254 /* Set to 0x3ffffff if v was negative; else set to 0. */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
255 const int32_t roundoff = ((uint32_t) sign) >> 6;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
256 /* Should return v / (1<<26) */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
257 return (v + roundoff) >> 26;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
258 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
259
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
260 /* return v / (2^25), using only shifts and adds.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
261 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
262 * On entry: v can take any value. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
263 static inline limb
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
264 div_by_2_25(const limb v)
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
265 {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
266 /* High word of v; no shift needed*/
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
267 const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
268 /* Set to all 1s if v was negative; else set to 0s. */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
269 const int32_t sign = ((int32_t) highword) >> 31;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
270 /* Set to 0x1ffffff if v was negative; else set to 0. */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
271 const int32_t roundoff = ((uint32_t) sign) >> 7;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
272 /* Should return v / (1<<25) */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
273 return (v + roundoff) >> 25;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
274 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
275
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
276 /* Reduce all coefficients of the short form input so that |x| < 2^26.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
277 *
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
278 * On entry: |output[i]| < 280*2^54 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
279 static void freduce_coefficients(limb *output) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
280 unsigned i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
281
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
282 output[10] = 0;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
283
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
284 for (i = 0; i < 10; i += 2) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
285 limb over = div_by_2_26(output[i]);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
286 /* The entry condition (that |output[i]| < 280*2^54) means that over is, at
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
287 * most, 280*2^28 in the first iteration of this loop. This is added to the
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
288 * next limb and we can approximate the resulting bound of that limb by
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
289 * 281*2^54. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
290 output[i] -= over << 26;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
291 output[i+1] += over;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
292
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
293 /* For the first iteration, |output[i+1]| < 281*2^54, thus |over| <
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
294 * 281*2^29. When this is added to the next limb, the resulting bound can
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
295 * be approximated as 281*2^54.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
296 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
297 * For subsequent iterations of the loop, 281*2^54 remains a conservative
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
298 * bound and no overflow occurs. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
299 over = div_by_2_25(output[i+1]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
300 output[i+1] -= over << 25;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
301 output[i+2] += over;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
302 }
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
303 /* Now |output[10]| < 281*2^29 and all other coefficients are reduced. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
304 output[0] += output[10] << 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
305 output[0] += output[10] << 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
306 output[0] += output[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
307
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
308 output[10] = 0;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
309
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
310 /* Now output[1..9] are reduced, and |output[0]| < 2^26 + 19*281*2^29
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
311 * So |over| will be no more than 2^16. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
312 {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
313 limb over = div_by_2_26(output[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
314 output[0] -= over << 26;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
315 output[1] += over;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
316 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
317
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
318 /* Now output[0,2..9] are reduced, and |output[1]| < 2^25 + 2^16 < 2^26. The
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
319 * bound on |output[1]| is sufficient to meet our needs. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
320 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
321
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
322 /* A helpful wrapper around fproduct: output = in * in2.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
323 *
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
324 * On entry: |in[i]| < 2^27 and |in2[i]| < 2^27.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
325 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
326 * output must be distinct to both inputs. The output is reduced degree
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
327 * (indeed, one need only provide storage for 10 limbs) and |output[i]| < 2^26. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
328 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
329 fmul(limb *output, const limb *in, const limb *in2) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
330 limb t[19];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
331 fproduct(t, in, in2);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
332 /* |t[i]| < 14*2^54 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
333 freduce_degree(t);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
334 freduce_coefficients(t);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
335 /* |t[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
336 memcpy(output, t, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
337 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
338
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
339 /* Square a number: output = in**2
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
340 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
341 * output must be distinct from the input. The inputs are reduced coefficient
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
342 * form, the output is not.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
343 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
344 * output[x] <= 14 * the largest product of the input limbs. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
345 static void fsquare_inner(limb *output, const limb *in) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
346 output[0] = ((limb) ((s32) in[0])) * ((s32) in[0]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
347 output[1] = 2 * ((limb) ((s32) in[0])) * ((s32) in[1]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
348 output[2] = 2 * (((limb) ((s32) in[1])) * ((s32) in[1]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
349 ((limb) ((s32) in[0])) * ((s32) in[2]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
350 output[3] = 2 * (((limb) ((s32) in[1])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
351 ((limb) ((s32) in[0])) * ((s32) in[3]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
352 output[4] = ((limb) ((s32) in[2])) * ((s32) in[2]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
353 4 * ((limb) ((s32) in[1])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
354 2 * ((limb) ((s32) in[0])) * ((s32) in[4]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
355 output[5] = 2 * (((limb) ((s32) in[2])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
356 ((limb) ((s32) in[1])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
357 ((limb) ((s32) in[0])) * ((s32) in[5]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
358 output[6] = 2 * (((limb) ((s32) in[3])) * ((s32) in[3]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
359 ((limb) ((s32) in[2])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
360 ((limb) ((s32) in[0])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
361 2 * ((limb) ((s32) in[1])) * ((s32) in[5]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
362 output[7] = 2 * (((limb) ((s32) in[3])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
363 ((limb) ((s32) in[2])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
364 ((limb) ((s32) in[1])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
365 ((limb) ((s32) in[0])) * ((s32) in[7]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
366 output[8] = ((limb) ((s32) in[4])) * ((s32) in[4]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
367 2 * (((limb) ((s32) in[2])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
368 ((limb) ((s32) in[0])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
369 2 * (((limb) ((s32) in[1])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
370 ((limb) ((s32) in[3])) * ((s32) in[5])));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
371 output[9] = 2 * (((limb) ((s32) in[4])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
372 ((limb) ((s32) in[3])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
373 ((limb) ((s32) in[2])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
374 ((limb) ((s32) in[1])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
375 ((limb) ((s32) in[0])) * ((s32) in[9]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
376 output[10] = 2 * (((limb) ((s32) in[5])) * ((s32) in[5]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
377 ((limb) ((s32) in[4])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
378 ((limb) ((s32) in[2])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
379 2 * (((limb) ((s32) in[3])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
380 ((limb) ((s32) in[1])) * ((s32) in[9])));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
381 output[11] = 2 * (((limb) ((s32) in[5])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
382 ((limb) ((s32) in[4])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
383 ((limb) ((s32) in[3])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
384 ((limb) ((s32) in[2])) * ((s32) in[9]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
385 output[12] = ((limb) ((s32) in[6])) * ((s32) in[6]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
386 2 * (((limb) ((s32) in[4])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
387 2 * (((limb) ((s32) in[5])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
388 ((limb) ((s32) in[3])) * ((s32) in[9])));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
389 output[13] = 2 * (((limb) ((s32) in[6])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
390 ((limb) ((s32) in[5])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
391 ((limb) ((s32) in[4])) * ((s32) in[9]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
392 output[14] = 2 * (((limb) ((s32) in[7])) * ((s32) in[7]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
393 ((limb) ((s32) in[6])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
394 2 * ((limb) ((s32) in[5])) * ((s32) in[9]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
395 output[15] = 2 * (((limb) ((s32) in[7])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
396 ((limb) ((s32) in[6])) * ((s32) in[9]));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
397 output[16] = ((limb) ((s32) in[8])) * ((s32) in[8]) +
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
398 4 * ((limb) ((s32) in[7])) * ((s32) in[9]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
399 output[17] = 2 * ((limb) ((s32) in[8])) * ((s32) in[9]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
400 output[18] = 2 * ((limb) ((s32) in[9])) * ((s32) in[9]);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
401 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
402
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
403 /* fsquare sets output = in^2.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
404 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
405 * On entry: The |in| argument is in reduced coefficients form and |in[i]| <
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
406 * 2^27.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
407 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
408 * On exit: The |output| argument is in reduced coefficients form (indeed, one
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
409 * need only provide storage for 10 limbs) and |out[i]| < 2^26. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
410 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
411 fsquare(limb *output, const limb *in) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
412 limb t[19];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
413 fsquare_inner(t, in);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
414 /* |t[i]| < 14*2^54 because the largest product of two limbs will be <
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
415 * 2^(27+27) and fsquare_inner adds together, at most, 14 of those
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
416 * products. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
417 freduce_degree(t);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
418 freduce_coefficients(t);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
419 /* |t[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
420 memcpy(output, t, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
421 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
422
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
423 /* Take a little-endian, 32-byte number and expand it into polynomial form */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
424 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
425 fexpand(limb *output, const u8 *input) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
426 #define F(n,start,shift,mask) \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
427 output[n] = ((((limb) input[start + 0]) | \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
428 ((limb) input[start + 1]) << 8 | \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
429 ((limb) input[start + 2]) << 16 | \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
430 ((limb) input[start + 3]) << 24) >> shift) & mask;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
431 F(0, 0, 0, 0x3ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
432 F(1, 3, 2, 0x1ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
433 F(2, 6, 3, 0x3ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
434 F(3, 9, 5, 0x1ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
435 F(4, 12, 6, 0x3ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
436 F(5, 16, 0, 0x1ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
437 F(6, 19, 1, 0x3ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
438 F(7, 22, 3, 0x1ffffff);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
439 F(8, 25, 4, 0x3ffffff);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
440 F(9, 28, 6, 0x1ffffff);
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
441 #undef F
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
442 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
443
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
444 #if (-32 >> 1) != -16
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
445 #error "This code only works when >> does sign-extension on negative numbers"
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
446 #endif
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
447
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
448 /* s32_eq returns 0xffffffff iff a == b and zero otherwise. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
449 static s32 s32_eq(s32 a, s32 b) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
450 a = ~(a ^ b);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
451 a &= a << 16;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
452 a &= a << 8;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
453 a &= a << 4;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
454 a &= a << 2;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
455 a &= a << 1;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
456 return a >> 31;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
457 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
458
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
459 /* s32_gte returns 0xffffffff if a >= b and zero otherwise, where a and b are
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
460 * both non-negative. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
461 static s32 s32_gte(s32 a, s32 b) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
462 a -= b;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
463 /* a >= 0 iff a >= b. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
464 return ~(a >> 31);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
465 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
466
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
467 /* Take a fully reduced polynomial form number and contract it into a
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
468 * little-endian, 32-byte array.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
469 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
470 * On entry: |input_limbs[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
471 static void
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
472 fcontract(u8 *output, limb *input_limbs) {
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
473 int i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
474 int j;
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
475 s32 input[10];
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
476 s32 mask;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
477
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
478 /* |input_limbs[i]| < 2^26, so it's valid to convert to an s32. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
479 for (i = 0; i < 10; i++) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
480 input[i] = input_limbs[i];
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
481 }
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
482
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
483 for (j = 0; j < 2; ++j) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
484 for (i = 0; i < 9; ++i) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
485 if ((i & 1) == 1) {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
486 /* This calculation is a time-invariant way to make input[i]
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
487 * non-negative by borrowing from the next-larger limb. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
488 const s32 mask = input[i] >> 31;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
489 const s32 carry = -((input[i] & mask) >> 25);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
490 input[i] = input[i] + (carry << 25);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
491 input[i+1] = input[i+1] - carry;
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
492 } else {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
493 const s32 mask = input[i] >> 31;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
494 const s32 carry = -((input[i] & mask) >> 26);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
495 input[i] = input[i] + (carry << 26);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
496 input[i+1] = input[i+1] - carry;
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
497 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
498 }
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
499
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
500 /* There's no greater limb for input[9] to borrow from, but we can multiply
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
501 * by 19 and borrow from input[0], which is valid mod 2^255-19. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
502 {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
503 const s32 mask = input[9] >> 31;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
504 const s32 carry = -((input[9] & mask) >> 25);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
505 input[9] = input[9] + (carry << 25);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
506 input[0] = input[0] - (carry * 19);
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
507 }
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
508
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
509 /* After the first iteration, input[1..9] are non-negative and fit within
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
510 * 25 or 26 bits, depending on position. However, input[0] may be
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
511 * negative. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
512 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
513
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
514 /* The first borrow-propagation pass above ended with every limb
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
515 except (possibly) input[0] non-negative.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
516
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
517 If input[0] was negative after the first pass, then it was because of a
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
518 carry from input[9]. On entry, input[9] < 2^26 so the carry was, at most,
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
519 one, since (2**26-1) >> 25 = 1. Thus input[0] >= -19.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
520
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
521 In the second pass, each limb is decreased by at most one. Thus the second
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
522 borrow-propagation pass could only have wrapped around to decrease
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
523 input[0] again if the first pass left input[0] negative *and* input[1]
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
524 through input[9] were all zero. In that case, input[1] is now 2^25 - 1,
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
525 and this last borrow-propagation step will leave input[1] non-negative. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
526 {
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
527 const s32 mask = input[0] >> 31;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
528 const s32 carry = -((input[0] & mask) >> 26);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
529 input[0] = input[0] + (carry << 26);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
530 input[1] = input[1] - carry;
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
531 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
532
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
533 /* All input[i] are now non-negative. However, there might be values between
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
534 * 2^25 and 2^26 in a limb which is, nominally, 25 bits wide. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
535 for (j = 0; j < 2; j++) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
536 for (i = 0; i < 9; i++) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
537 if ((i & 1) == 1) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
538 const s32 carry = input[i] >> 25;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
539 input[i] &= 0x1ffffff;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
540 input[i+1] += carry;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
541 } else {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
542 const s32 carry = input[i] >> 26;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
543 input[i] &= 0x3ffffff;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
544 input[i+1] += carry;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
545 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
546 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
547
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
548 {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
549 const s32 carry = input[9] >> 25;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
550 input[9] &= 0x1ffffff;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
551 input[0] += 19*carry;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
552 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
553 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
554
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
555 /* If the first carry-chain pass, just above, ended up with a carry from
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
556 * input[9], and that caused input[0] to be out-of-bounds, then input[0] was
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
557 * < 2^26 + 2*19, because the carry was, at most, two.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
558 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
559 * If the second pass carried from input[9] again then input[0] is < 2*19 and
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
560 * the input[9] -> input[0] carry didn't push input[0] out of bounds. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
561
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
562 /* It still remains the case that input might be between 2^255-19 and 2^255.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
563 * In this case, input[1..9] must take their maximum value and input[0] must
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
564 * be >= (2^255-19) & 0x3ffffff, which is 0x3ffffed. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
565 mask = s32_gte(input[0], 0x3ffffed);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
566 for (i = 1; i < 10; i++) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
567 if ((i & 1) == 1) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
568 mask &= s32_eq(input[i], 0x1ffffff);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
569 } else {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
570 mask &= s32_eq(input[i], 0x3ffffff);
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
571 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
572 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
573
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
574 /* mask is either 0xffffffff (if input >= 2^255-19) and zero otherwise. Thus
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
575 * this conditionally subtracts 2^255-19. */
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
576 input[0] -= mask & 0x3ffffed;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
577
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
578 for (i = 1; i < 10; i++) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
579 if ((i & 1) == 1) {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
580 input[i] -= mask & 0x1ffffff;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
581 } else {
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
582 input[i] -= mask & 0x3ffffff;
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
583 }
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
584 }
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
585
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
586 input[1] <<= 2;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
587 input[2] <<= 3;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
588 input[3] <<= 5;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
589 input[4] <<= 6;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
590 input[6] <<= 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
591 input[7] <<= 3;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
592 input[8] <<= 4;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
593 input[9] <<= 6;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
594 #define F(i, s) \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
595 output[s+0] |= input[i] & 0xff; \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
596 output[s+1] = (input[i] >> 8) & 0xff; \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
597 output[s+2] = (input[i] >> 16) & 0xff; \
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
598 output[s+3] = (input[i] >> 24) & 0xff;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
599 output[0] = 0;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
600 output[16] = 0;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
601 F(0,0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
602 F(1,3);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
603 F(2,6);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
604 F(3,9);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
605 F(4,12);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
606 F(5,16);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
607 F(6,19);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
608 F(7,22);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
609 F(8,25);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
610 F(9,28);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
611 #undef F
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
612 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
613
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
614 /* Input: Q, Q', Q-Q'
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
615 * Output: 2Q, Q+Q'
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
616 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
617 * x2 z3: long form
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
618 * x3 z3: long form
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
619 * x z: short form, destroyed
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
620 * xprime zprime: short form, destroyed
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
621 * qmqp: short form, preserved
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
622 *
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
623 * On entry and exit, the absolute value of the limbs of all inputs and outputs
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
624 * are < 2^26. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
625 static void fmonty(limb *x2, limb *z2, /* output 2Q */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
626 limb *x3, limb *z3, /* output Q + Q' */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
627 limb *x, limb *z, /* input Q */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
628 limb *xprime, limb *zprime, /* input Q' */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
629 const limb *qmqp /* input Q - Q' */) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
630 limb origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19],
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
631 zzprime[19], zzzprime[19], xxxprime[19];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
632
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
633 memcpy(origx, x, 10 * sizeof(limb));
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
634 fsum(x, z);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
635 /* |x[i]| < 2^27 */
1038
d3925ed45a85 Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents: 848
diff changeset
636 fdifference(z, origx); /* does x - z */
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
637 /* |z[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
638
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
639 memcpy(origxprime, xprime, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
640 fsum(xprime, zprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
641 /* |xprime[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
642 fdifference(zprime, origxprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
643 /* |zprime[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
644 fproduct(xxprime, xprime, z);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
645 /* |xxprime[i]| < 14*2^54: the largest product of two limbs will be <
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
646 * 2^(27+27) and fproduct adds together, at most, 14 of those products.
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
647 * (Approximating that to 2^58 doesn't work out.) */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
648 fproduct(zzprime, x, zprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
649 /* |zzprime[i]| < 14*2^54 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
650 freduce_degree(xxprime);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
651 freduce_coefficients(xxprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
652 /* |xxprime[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
653 freduce_degree(zzprime);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
654 freduce_coefficients(zzprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
655 /* |zzprime[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
656 memcpy(origxprime, xxprime, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
657 fsum(xxprime, zzprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
658 /* |xxprime[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
659 fdifference(zzprime, origxprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
660 /* |zzprime[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
661 fsquare(xxxprime, xxprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
662 /* |xxxprime[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
663 fsquare(zzzprime, zzprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
664 /* |zzzprime[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
665 fproduct(zzprime, zzzprime, qmqp);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
666 /* |zzprime[i]| < 14*2^52 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
667 freduce_degree(zzprime);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
668 freduce_coefficients(zzprime);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
669 /* |zzprime[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
670 memcpy(x3, xxxprime, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
671 memcpy(z3, zzprime, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
672
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
673 fsquare(xx, x);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
674 /* |xx[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
675 fsquare(zz, z);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
676 /* |zz[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
677 fproduct(x2, xx, zz);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
678 /* |x2[i]| < 14*2^52 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
679 freduce_degree(x2);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
680 freduce_coefficients(x2);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
681 /* |x2[i]| < 2^26 */
1038
d3925ed45a85 Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents: 848
diff changeset
682 fdifference(zz, xx); /* does zz = xx - zz */
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
683 /* |zz[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
684 memset(zzz + 10, 0, sizeof(limb) * 9);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
685 fscalar_product(zzz, zz, 121665);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
686 /* |zzz[i]| < 2^(27+17) */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
687 /* No need to call freduce_degree here:
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
688 fscalar_product doesn't increase the degree of its input. */
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
689 freduce_coefficients(zzz);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
690 /* |zzz[i]| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
691 fsum(zzz, xx);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
692 /* |zzz[i]| < 2^27 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
693 fproduct(z2, zz, zzz);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
694 /* |z2[i]| < 14*2^(26+27) */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
695 freduce_degree(z2);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
696 freduce_coefficients(z2);
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
697 /* |z2|i| < 2^26 */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
698 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
699
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
700 /* Conditionally swap two reduced-form limb arrays if 'iswap' is 1, but leave
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
701 * them unchanged if 'iswap' is 0. Runs in data-invariant time to avoid
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
702 * side-channel attacks.
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
703 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
704 * NOTE that this function requires that 'iswap' be 1 or 0; other values give
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
705 * wrong results. Also, the two limb arrays must be in reduced-coefficient,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
706 * reduced-degree form: the values in a[10..19] or b[10..19] aren't swapped,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
707 * and all all values in a[0..9],b[0..9] must have magnitude less than
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
708 * INT32_MAX. */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
709 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
710 swap_conditional(limb a[19], limb b[19], limb iswap) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
711 unsigned i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
712 const s32 swap = (s32) -iswap;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
713
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
714 for (i = 0; i < 10; ++i) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
715 const s32 x = swap & ( ((s32)a[i]) ^ ((s32)b[i]) );
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
716 a[i] = ((s32)a[i]) ^ x;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
717 b[i] = ((s32)b[i]) ^ x;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
718 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
719 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
720
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
721 /* Calculates nQ where Q is the x-coordinate of a point on the curve
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
722 *
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
723 * resultx/resultz: the x coordinate of the resulting curve point (short form)
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
724 * n: a little endian, 32-byte number
1434
27b9ddb06b09 Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents: 1038
diff changeset
725 * q: a point of the curve (short form) */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
726 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
727 cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
728 limb a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0};
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
729 limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
730 limb e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1};
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
731 limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
732
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
733 unsigned i, j;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
734
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
735 memcpy(nqpqx, q, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
736
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
737 for (i = 0; i < 32; ++i) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
738 u8 byte = n[31 - i];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
739 for (j = 0; j < 8; ++j) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
740 const limb bit = byte >> 7;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
741
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
742 swap_conditional(nqx, nqpqx, bit);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
743 swap_conditional(nqz, nqpqz, bit);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
744 fmonty(nqx2, nqz2,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
745 nqpqx2, nqpqz2,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
746 nqx, nqz,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
747 nqpqx, nqpqz,
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
748 q);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
749 swap_conditional(nqx2, nqpqx2, bit);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
750 swap_conditional(nqz2, nqpqz2, bit);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
751
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
752 t = nqx;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
753 nqx = nqx2;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
754 nqx2 = t;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
755 t = nqz;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
756 nqz = nqz2;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
757 nqz2 = t;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
758 t = nqpqx;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
759 nqpqx = nqpqx2;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
760 nqpqx2 = t;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
761 t = nqpqz;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
762 nqpqz = nqpqz2;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
763 nqpqz2 = t;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
764
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
765 byte <<= 1;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
766 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
767 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
768
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
769 memcpy(resultx, nqx, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
770 memcpy(resultz, nqz, sizeof(limb) * 10);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
771 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
772
1038
d3925ed45a85 Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents: 848
diff changeset
773 /* -----------------------------------------------------------------------------
d3925ed45a85 Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents: 848
diff changeset
774 * Shamelessly copied from djb's code
d3925ed45a85 Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents: 848
diff changeset
775 * ----------------------------------------------------------------------------- */
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
776 static void
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
777 crecip(limb *out, const limb *z) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
778 limb z2[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
779 limb z9[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
780 limb z11[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
781 limb z2_5_0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
782 limb z2_10_0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
783 limb z2_20_0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
784 limb z2_50_0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
785 limb z2_100_0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
786 limb t0[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
787 limb t1[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
788 int i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
789
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
790 /* 2 */ fsquare(z2,z);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
791 /* 4 */ fsquare(t1,z2);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
792 /* 8 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
793 /* 9 */ fmul(z9,t0,z);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
794 /* 11 */ fmul(z11,z9,z2);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
795 /* 22 */ fsquare(t0,z11);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
796 /* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
797
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
798 /* 2^6 - 2^1 */ fsquare(t0,z2_5_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
799 /* 2^7 - 2^2 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
800 /* 2^8 - 2^3 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
801 /* 2^9 - 2^4 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
802 /* 2^10 - 2^5 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
803 /* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
804
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
805 /* 2^11 - 2^1 */ fsquare(t0,z2_10_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
806 /* 2^12 - 2^2 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
807 /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
808 /* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
809
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
810 /* 2^21 - 2^1 */ fsquare(t0,z2_20_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
811 /* 2^22 - 2^2 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
812 /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
813 /* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
814
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
815 /* 2^41 - 2^1 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
816 /* 2^42 - 2^2 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
817 /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
818 /* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
819
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
820 /* 2^51 - 2^1 */ fsquare(t0,z2_50_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
821 /* 2^52 - 2^2 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
822 /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
823 /* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
824
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
825 /* 2^101 - 2^1 */ fsquare(t1,z2_100_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
826 /* 2^102 - 2^2 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
827 /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
828 /* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
829
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
830 /* 2^201 - 2^1 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
831 /* 2^202 - 2^2 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
832 /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
833 /* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
834
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
835 /* 2^251 - 2^1 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
836 /* 2^252 - 2^2 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
837 /* 2^253 - 2^3 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
838 /* 2^254 - 2^4 */ fsquare(t0,t1);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
839 /* 2^255 - 2^5 */ fsquare(t1,t0);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
840 /* 2^255 - 21 */ fmul(out,t1,z11);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
841 }
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
842
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
843 int
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
844 curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
845 limb bp[10], x[10], z[11], zmone[10];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
846 uint8_t e[32];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
847 int i;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
848
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
849 for (i = 0; i < 32; ++i) e[i] = secret[i];
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
850 e[0] &= 248;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
851 e[31] &= 127;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
852 e[31] |= 64;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
853
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
854 fexpand(bp, basepoint);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
855 cmult(x, z, e, bp);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
856 crecip(zmone, z);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
857 fmul(z, x, zmone);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
858 fcontract(mypublic, z);
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
859 return 0;
6c69e7df3621 curve25519
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
860 }