|
848
|
1 /* Copyright 2008, Google Inc. |
|
|
2 * All rights reserved. |
|
|
3 * |
|
|
4 * Redistribution and use in source and binary forms, with or without |
|
|
5 * modification, are permitted provided that the following conditions are |
|
|
6 * met: |
|
|
7 * |
|
|
8 * * Redistributions of source code must retain the above copyright |
|
|
9 * notice, this list of conditions and the following disclaimer. |
|
|
10 * * Redistributions in binary form must reproduce the above |
|
|
11 * copyright notice, this list of conditions and the following disclaimer |
|
|
12 * in the documentation and/or other materials provided with the |
|
|
13 * distribution. |
|
|
14 * * Neither the name of Google Inc. nor the names of its |
|
|
15 * contributors may be used to endorse or promote products derived from |
|
|
16 * this software without specific prior written permission. |
|
|
17 * |
|
|
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
|
|
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
|
|
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
|
|
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
|
|
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
|
|
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
|
|
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
|
|
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
|
|
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
|
|
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
|
|
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
|
|
29 * |
|
|
30 * curve25519-donna: Curve25519 elliptic curve, public key function |
|
|
31 * |
|
|
32 * http://code.google.com/p/curve25519-donna/ |
|
|
33 * |
|
|
34 * Adam Langley <[email protected]> |
|
|
35 * |
|
|
36 * Derived from public domain C code by Daniel J. Bernstein <[email protected]> |
|
|
37 * |
|
|
38 * More information about curve25519 can be found here |
|
|
39 * http://cr.yp.to/ecdh.html |
|
|
40 * |
|
|
41 * djb's sample implementation of curve25519 is written in a special assembly |
|
|
42 * language called qhasm and uses the floating point registers. |
|
|
43 * |
|
|
44 * This is, almost, a clean room reimplementation from the curve25519 paper. It |
|
|
45 * uses many of the tricks described therein. Only the crecip function is taken |
|
|
46 * from the sample implementation. |
|
|
47 */ |
|
|
48 |
|
|
49 #include <string.h> |
|
|
50 #include <stdint.h> |
|
|
51 |
|
|
52 #ifdef _MSC_VER |
|
|
53 #define inline __inline |
|
|
54 #endif |
|
|
55 |
|
|
56 typedef uint8_t u8; |
|
|
57 typedef int32_t s32; |
|
|
58 typedef int64_t limb; |
|
|
59 |
|
|
60 /* Field element representation: |
|
|
61 * |
|
|
62 * Field elements are written as an array of signed, 64-bit limbs, least |
|
|
63 * significant first. The value of the field element is: |
|
|
64 * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ... |
|
|
65 * |
|
|
66 * i.e. the limbs are 26, 25, 26, 25, ... bits wide. |
|
|
67 */ |
|
|
68 |
|
|
69 /* Sum two numbers: output += in */ |
|
|
70 static void fsum(limb *output, const limb *in) { |
|
|
71 unsigned i; |
|
|
72 for (i = 0; i < 10; i += 2) { |
|
|
73 output[0+i] = (output[0+i] + in[0+i]); |
|
|
74 output[1+i] = (output[1+i] + in[1+i]); |
|
|
75 } |
|
|
76 } |
|
|
77 |
|
|
78 /* Find the difference of two numbers: output = in - output |
|
|
79 * (note the order of the arguments!) |
|
|
80 */ |
|
|
81 static void fdifference(limb *output, const limb *in) { |
|
|
82 unsigned i; |
|
|
83 for (i = 0; i < 10; ++i) { |
|
|
84 output[i] = (in[i] - output[i]); |
|
|
85 } |
|
|
86 } |
|
|
87 |
|
|
88 /* Multiply a number by a scalar: output = in * scalar */ |
|
|
89 static void fscalar_product(limb *output, const limb *in, const limb scalar) { |
|
|
90 unsigned i; |
|
|
91 for (i = 0; i < 10; ++i) { |
|
|
92 output[i] = in[i] * scalar; |
|
|
93 } |
|
|
94 } |
|
|
95 |
|
|
96 /* Multiply two numbers: output = in2 * in |
|
|
97 * |
|
|
98 * output must be distinct to both inputs. The inputs are reduced coefficient |
|
|
99 * form, the output is not. |
|
|
100 */ |
|
|
101 static void fproduct(limb *output, const limb *in2, const limb *in) { |
|
|
102 output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]); |
|
|
103 output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) + |
|
|
104 ((limb) ((s32) in2[1])) * ((s32) in[0]); |
|
|
105 output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) + |
|
|
106 ((limb) ((s32) in2[0])) * ((s32) in[2]) + |
|
|
107 ((limb) ((s32) in2[2])) * ((s32) in[0]); |
|
|
108 output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) + |
|
|
109 ((limb) ((s32) in2[2])) * ((s32) in[1]) + |
|
|
110 ((limb) ((s32) in2[0])) * ((s32) in[3]) + |
|
|
111 ((limb) ((s32) in2[3])) * ((s32) in[0]); |
|
|
112 output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) + |
|
|
113 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) + |
|
|
114 ((limb) ((s32) in2[3])) * ((s32) in[1])) + |
|
|
115 ((limb) ((s32) in2[0])) * ((s32) in[4]) + |
|
|
116 ((limb) ((s32) in2[4])) * ((s32) in[0]); |
|
|
117 output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) + |
|
|
118 ((limb) ((s32) in2[3])) * ((s32) in[2]) + |
|
|
119 ((limb) ((s32) in2[1])) * ((s32) in[4]) + |
|
|
120 ((limb) ((s32) in2[4])) * ((s32) in[1]) + |
|
|
121 ((limb) ((s32) in2[0])) * ((s32) in[5]) + |
|
|
122 ((limb) ((s32) in2[5])) * ((s32) in[0]); |
|
|
123 output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) + |
|
|
124 ((limb) ((s32) in2[1])) * ((s32) in[5]) + |
|
|
125 ((limb) ((s32) in2[5])) * ((s32) in[1])) + |
|
|
126 ((limb) ((s32) in2[2])) * ((s32) in[4]) + |
|
|
127 ((limb) ((s32) in2[4])) * ((s32) in[2]) + |
|
|
128 ((limb) ((s32) in2[0])) * ((s32) in[6]) + |
|
|
129 ((limb) ((s32) in2[6])) * ((s32) in[0]); |
|
|
130 output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) + |
|
|
131 ((limb) ((s32) in2[4])) * ((s32) in[3]) + |
|
|
132 ((limb) ((s32) in2[2])) * ((s32) in[5]) + |
|
|
133 ((limb) ((s32) in2[5])) * ((s32) in[2]) + |
|
|
134 ((limb) ((s32) in2[1])) * ((s32) in[6]) + |
|
|
135 ((limb) ((s32) in2[6])) * ((s32) in[1]) + |
|
|
136 ((limb) ((s32) in2[0])) * ((s32) in[7]) + |
|
|
137 ((limb) ((s32) in2[7])) * ((s32) in[0]); |
|
|
138 output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) + |
|
|
139 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) + |
|
|
140 ((limb) ((s32) in2[5])) * ((s32) in[3]) + |
|
|
141 ((limb) ((s32) in2[1])) * ((s32) in[7]) + |
|
|
142 ((limb) ((s32) in2[7])) * ((s32) in[1])) + |
|
|
143 ((limb) ((s32) in2[2])) * ((s32) in[6]) + |
|
|
144 ((limb) ((s32) in2[6])) * ((s32) in[2]) + |
|
|
145 ((limb) ((s32) in2[0])) * ((s32) in[8]) + |
|
|
146 ((limb) ((s32) in2[8])) * ((s32) in[0]); |
|
|
147 output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) + |
|
|
148 ((limb) ((s32) in2[5])) * ((s32) in[4]) + |
|
|
149 ((limb) ((s32) in2[3])) * ((s32) in[6]) + |
|
|
150 ((limb) ((s32) in2[6])) * ((s32) in[3]) + |
|
|
