1 /******************************************************************************
2 *
3 * Copyright (C) 2006-2015 Broadcom Corporation
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at:
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 ******************************************************************************/
18
19 /******************************************************************************
20 *
21 * This file contains simple pairing algorithms using Elliptic Curve Cryptography for private public key
22 *
23 ******************************************************************************/
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include "p_256_ecc_pp.h"
28 #include "p_256_multprecision.h"
29
30 elliptic_curve_t curve;
31 elliptic_curve_t curve_p256;
32
p_256_init_point(Point * q)33 static void p_256_init_point(Point *q)
34 {
35 memset(q, 0, sizeof(Point));
36 }
37
p_256_copy_point(Point * q,Point * p)38 static void p_256_copy_point(Point *q, Point *p)
39 {
40 memcpy(q, p, sizeof(Point));
41 }
42
43 // q=2q
ECC_Double(Point * q,Point * p,uint32_t keyLength)44 static void ECC_Double(Point *q, Point *p, uint32_t keyLength)
45 {
46 DWORD t1[KEY_LENGTH_DWORDS_P256];
47 DWORD t2[KEY_LENGTH_DWORDS_P256];
48 DWORD t3[KEY_LENGTH_DWORDS_P256];
49 DWORD *x1;
50 DWORD *x3;
51 DWORD *y1;
52 DWORD *y3;
53 DWORD *z1;
54 DWORD *z3;
55
56 if (multiprecision_iszero(p->z, keyLength))
57 {
58 multiprecision_init(q->z, keyLength);
59 return; // return infinity
60 }
61
62 x1=p->x; y1=p->y; z1=p->z;
63 x3=q->x; y3=q->y; z3=q->z;
64
65 multiprecision_mersenns_squa_mod(t1, z1, keyLength); // t1=z1^2
66 multiprecision_sub_mod(t2, x1, t1, keyLength); // t2=x1-t1
67 multiprecision_add_mod(t1, x1, t1, keyLength); // t1=x1+t1
68 multiprecision_mersenns_mult_mod(t2, t1, t2, keyLength); // t2=t2*t1
69 multiprecision_lshift_mod(t3, t2, keyLength);
70 multiprecision_add_mod(t2, t3, t2, keyLength); // t2=3t2
71
72 multiprecision_mersenns_mult_mod(z3, y1, z1, keyLength); // z3=y1*z1
73 multiprecision_lshift_mod(z3, z3, keyLength);
74
75 multiprecision_mersenns_squa_mod(y3, y1, keyLength); // y3=y1^2
76 multiprecision_lshift_mod(y3, y3, keyLength);
77 multiprecision_mersenns_mult_mod(t3, y3, x1, keyLength); // t3=y3*x1=x1*y1^2
78 multiprecision_lshift_mod(t3, t3, keyLength);
79 multiprecision_mersenns_squa_mod(y3, y3, keyLength); // y3=y3^2=y1^4
80 multiprecision_lshift_mod(y3, y3, keyLength);
81
82 multiprecision_mersenns_squa_mod(x3, t2, keyLength); // x3=t2^2
83 multiprecision_lshift_mod(t1, t3, keyLength); // t1=2t3
84 multiprecision_sub_mod(x3, x3, t1, keyLength); // x3=x3-t1
85 multiprecision_sub_mod(t1, t3, x3, keyLength); // t1=t3-x3
86 multiprecision_mersenns_mult_mod(t1, t1, t2, keyLength); // t1=t1*t2
87 multiprecision_sub_mod(y3, t1, y3, keyLength); // y3=t1-y3
88 }
89
90 // q=q+p, zp must be 1
ECC_Add(Point * r,Point * p,Point * q,uint32_t keyLength)91 static void ECC_Add(Point *r, Point *p, Point *q, uint32_t keyLength)
92 {
93 DWORD t1[KEY_LENGTH_DWORDS_P256];
94 DWORD t2[KEY_LENGTH_DWORDS_P256];
95 DWORD *x1;
96 DWORD *x2;
97 DWORD *x3;
98 DWORD *y1;
99 DWORD *y2;
100 DWORD *y3;
101 DWORD *z1;
102 DWORD *z2;
103 DWORD *z3;
104
105 x1=p->x; y1=p->y; z1=p->z;
106 x2=q->x; y2=q->y; z2=q->z;
107 x3=r->x; y3=r->y; z3=r->z;
108
109 // if Q=infinity, return p
110 if (multiprecision_iszero(z2, keyLength))
111 {
112 p_256_copy_point(r, p);
113 return;
114 }
115
116 // if P=infinity, return q
117 if (multiprecision_iszero(z1, keyLength))
118 {
119 p_256_copy_point(r, q);
120 return;
121 }
122
123 multiprecision_mersenns_squa_mod(t1, z1, keyLength); // t1=z1^2
124 multiprecision_mersenns_mult_mod(t2, z1, t1, keyLength); // t2=t1*z1
125 multiprecision_mersenns_mult_mod(t1, x2, t1, keyLength); // t1=t1*x2
126 multiprecision_mersenns_mult_mod(t2, y2, t2, keyLength); // t2=t2*y2
127
128 multiprecision_sub_mod(t1, t1, x1, keyLength); // t1=t1-x1
129 multiprecision_sub_mod(t2, t2, y1, keyLength); // t2=t2-y1
130
131 if (multiprecision_iszero(t1, keyLength))
132 {
133 if (multiprecision_iszero(t2, keyLength))
134 {
135 ECC_Double(r, q, keyLength) ;
136 return;
137 }
138 else
139 {
140 multiprecision_init(z3, keyLength);
141 return; // return infinity
142 }
143 }
144
145 multiprecision_mersenns_mult_mod(z3, z1, t1, keyLength); // z3=z1*t1
146 multiprecision_mersenns_squa_mod(y3, t1, keyLength); // t3=t1^2
147 multiprecision_mersenns_mult_mod(z1, y3, t1, keyLength); // t4=t3*t1
148 multiprecision_mersenns_mult_mod(y3, y3, x1, keyLength); // t3=t3*x1
149 multiprecision_lshift_mod(t1, y3, keyLength); // t1=2*t3
150 multiprecision_mersenns_squa_mod(x3, t2, keyLength); // x3=t2^2
151 multiprecision_sub_mod(x3, x3, t1, keyLength); // x3=x3-t1
152 multiprecision_sub_mod(x3, x3, z1, keyLength); // x3=x3-t4
153 multiprecision_sub_mod(y3, y3, x3, keyLength); // t3=t3-x3
154 multiprecision_mersenns_mult_mod(y3, y3, t2, keyLength); // t3=t3*t2
155 multiprecision_mersenns_mult_mod(z1, z1, y1, keyLength); // t4=t4*t1
156 multiprecision_sub_mod(y3, y3, z1, keyLength);
157 }
158
159 // Computing the Non-Adjacent Form of a positive integer
ECC_NAF(uint8_t * naf,uint32_t * NumNAF,DWORD * k,uint32_t keyLength)160 static void ECC_NAF(uint8_t *naf, uint32_t *NumNAF, DWORD *k, uint32_t keyLength)
161 {
162 uint32_t sign;
163 int i=0;
164 int j;
165 uint32_t var;
166
167 while ((var = multiprecision_most_signbits(k, keyLength))>=1)
168 {
169 if (k[0] & 0x01) // k is odd
170 {
171 sign = (k[0] & 0x03); // 1 or 3
172
173 // k = k-naf[i]
174 if (sign == 1)
175 k[0] = k[0] & 0xFFFFFFFE;
176 else
177 {
178 k[0] = k[0] + 1;
179 if (k[0] == 0) //overflow
180 {
181 j = 1;
182 do
183 {
184 k[j]++;
185 } while (k[j++]==0); //overflow
186 }
187 }
188 }
189 else
190 sign = 0;
191
192 multiprecision_rshift(k, k, keyLength);
193 naf[i / 4] |= (sign) << ((i % 4) * 2);
194 i++;
195 }
196
197 *NumNAF=i;
198 }
199
200 // Binary Non-Adjacent Form for point multiplication
ECC_PointMult_Bin_NAF(Point * q,Point * p,DWORD * n,uint32_t keyLength)201 void ECC_PointMult_Bin_NAF(Point *q, Point *p, DWORD *n, uint32_t keyLength)
202 {
203 uint32_t sign;
204 UINT8 naf[256 / 4 +1];
205 uint32_t NumNaf;
206 Point minus_p;
207 Point r;
208 DWORD *modp;
209
210 if (keyLength == KEY_LENGTH_DWORDS_P256)
211 {
212 modp = curve_p256.p;
213 }
214 else
215 {
216 modp = curve.p;
217 }
218
219 p_256_init_point(&r);
220 multiprecision_init(p->z, keyLength);
221 p->z[0] = 1;
222
223 // initialization
224 p_256_init_point(q);
225
226 // -p
227 multiprecision_copy(minus_p.x, p->x, keyLength);
228 multiprecision_sub(minus_p.y, modp, p->y, keyLength);
229
230 multiprecision_init(minus_p.z, keyLength);
231 minus_p.z[0]=1;
232
233 // NAF
234 memset(naf, 0, sizeof(naf));
235 ECC_NAF(naf, &NumNaf, n, keyLength);
236
237 for (int i = NumNaf - 1; i >= 0; i--)
238 {
239 p_256_copy_point(&r, q);
240 ECC_Double(q, &r, keyLength);
241 sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03;
242
243 if (sign == 1)
244 {
245 p_256_copy_point(&r, q);
246 ECC_Add(q, &r, p, keyLength);
247 }
248 else if (sign == 3)
249 {
250 p_256_copy_point(&r, q);
251 ECC_Add(q, &r, &minus_p, keyLength);
252 }
253 }
254
255 multiprecision_inv_mod(minus_p.x, q->z, keyLength);
256 multiprecision_mersenns_squa_mod(q->z, minus_p.x, keyLength);
257 multiprecision_mersenns_mult_mod(q->x, q->x, q->z, keyLength);
258 multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, keyLength);
259 multiprecision_mersenns_mult_mod(q->y, q->y, q->z, keyLength);
260 }
261
262
263