• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /******************************************************************************
2  *
3  *  Copyright 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
22  *  Cryptography for private public key
23  *
24  ******************************************************************************/
25 #include "p_256_ecc_pp.h"
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include "p_256_multprecision.h"
30 
31 elliptic_curve_t curve;
32 elliptic_curve_t curve_p256;
33 
p_256_init_point(Point * q)34 static void p_256_init_point(Point* q) { memset(q, 0, sizeof(Point)); }
35 
p_256_copy_point(Point * q,Point * p)36 static void p_256_copy_point(Point* q, Point* p) {
37   memcpy(q, p, sizeof(Point));
38 }
39 
40 // q=2q
ECC_Double(Point * q,Point * p,uint32_t keyLength)41 static void ECC_Double(Point* q, Point* p, uint32_t keyLength) {
42   uint32_t t1[KEY_LENGTH_DWORDS_P256];
43   uint32_t t2[KEY_LENGTH_DWORDS_P256];
44   uint32_t t3[KEY_LENGTH_DWORDS_P256];
45   uint32_t* x1;
46   uint32_t* x3;
47   uint32_t* y1;
48   uint32_t* y3;
49   uint32_t* z1;
50   uint32_t* z3;
51 
52   if (multiprecision_iszero(p->z, keyLength)) {
53     multiprecision_init(q->z, keyLength);
54     return;  // return infinity
55   }
56 
57   x1 = p->x;
58   y1 = p->y;
59   z1 = p->z;
60   x3 = q->x;
61   y3 = q->y;
62   z3 = q->z;
63 
64   multiprecision_mersenns_squa_mod(t1, z1, keyLength);      // t1=z1^2
65   multiprecision_sub_mod(t2, x1, t1, keyLength);            // t2=x1-t1
66   multiprecision_add_mod(t1, x1, t1, keyLength);            // t1=x1+t1
67   multiprecision_mersenns_mult_mod(t2, t1, t2, keyLength);  // t2=t2*t1
68   multiprecision_lshift_mod(t3, t2, keyLength);
69   multiprecision_add_mod(t2, t3, t2, keyLength);  // t2=3t2
70 
71   multiprecision_mersenns_mult_mod(z3, y1, z1, keyLength);  // z3=y1*z1
72   multiprecision_lshift_mod(z3, z3, keyLength);
73 
74   multiprecision_mersenns_squa_mod(y3, y1, keyLength);  // y3=y1^2
75   multiprecision_lshift_mod(y3, y3, keyLength);
76   multiprecision_mersenns_mult_mod(t3, y3, x1, keyLength);  // t3=y3*x1=x1*y1^2
77   multiprecision_lshift_mod(t3, t3, keyLength);
78   multiprecision_mersenns_squa_mod(y3, y3, keyLength);  // y3=y3^2=y1^4
79   multiprecision_lshift_mod(y3, y3, keyLength);
80 
81   multiprecision_mersenns_squa_mod(x3, t2, keyLength);      // x3=t2^2
82   multiprecision_lshift_mod(t1, t3, keyLength);             // t1=2t3
83   multiprecision_sub_mod(x3, x3, t1, keyLength);            // x3=x3-t1
84   multiprecision_sub_mod(t1, t3, x3, keyLength);            // t1=t3-x3
85   multiprecision_mersenns_mult_mod(t1, t1, t2, keyLength);  // t1=t1*t2
86   multiprecision_sub_mod(y3, t1, y3, keyLength);            // y3=t1-y3
87 }
88 
89 // q=q+p,     zp must be 1
ECC_Add(Point * r,Point * p,Point * q,uint32_t keyLength)90 static void ECC_Add(Point* r, Point* p, Point* q, uint32_t keyLength) {
91   uint32_t t1[KEY_LENGTH_DWORDS_P256];
92   uint32_t t2[KEY_LENGTH_DWORDS_P256];
93   uint32_t* x1;
94   uint32_t* x2;
95   uint32_t* x3;
96   uint32_t* y1;
97   uint32_t* y2;
98   uint32_t* y3;
99   uint32_t* z1;
100   uint32_t* z2;
101   uint32_t* z3;
102 
103   x1 = p->x;
104   y1 = p->y;
105   z1 = p->z;
106   x2 = q->x;
107   y2 = q->y;
108   z2 = q->z;
109   x3 = r->x;
110   y3 = r->y;
111   z3 = r->z;
112 
113   // if Q=infinity, return p
114   if (multiprecision_iszero(z2, keyLength)) {
115     p_256_copy_point(r, p);
116     return;
117   }
118 
119   // if P=infinity, return q
120   if (multiprecision_iszero(z1, keyLength)) {
121     p_256_copy_point(r, q);
122     return;
123   }
124 
125   multiprecision_mersenns_squa_mod(t1, z1, keyLength);      // t1=z1^2
126   multiprecision_mersenns_mult_mod(t2, z1, t1, keyLength);  // t2=t1*z1
127   multiprecision_mersenns_mult_mod(t1, x2, t1, keyLength);  // t1=t1*x2
128   multiprecision_mersenns_mult_mod(t2, y2, t2, keyLength);  // t2=t2*y2
129 
130   multiprecision_sub_mod(t1, t1, x1, keyLength);  // t1=t1-x1
131   multiprecision_sub_mod(t2, t2, y1, keyLength);  // t2=t2-y1
132 
133   if (multiprecision_iszero(t1, keyLength)) {
134     if (multiprecision_iszero(t2, keyLength)) {
135       ECC_Double(r, q, keyLength);
136       return;
137     } else {
138       multiprecision_init(z3, keyLength);
139       return;  // return infinity
140     }
141   }
142 
143   multiprecision_mersenns_mult_mod(z3, z1, t1, keyLength);  // z3=z1*t1
144   multiprecision_mersenns_squa_mod(y3, t1, keyLength);      // t3=t1^2
145   multiprecision_mersenns_mult_mod(z1, y3, t1, keyLength);  // t4=t3*t1
146   multiprecision_mersenns_mult_mod(y3, y3, x1, keyLength);  // t3=t3*x1
147   multiprecision_lshift_mod(t1, y3, keyLength);             // t1=2*t3
148   multiprecision_mersenns_squa_mod(x3, t2, keyLength);      // x3=t2^2
149   multiprecision_sub_mod(x3, x3, t1, keyLength);            // x3=x3-t1
150   multiprecision_sub_mod(x3, x3, z1, keyLength);            // x3=x3-t4
151   multiprecision_sub_mod(y3, y3, x3, keyLength);            // t3=t3-x3
152   multiprecision_mersenns_mult_mod(y3, y3, t2, keyLength);  // t3=t3*t2
153   multiprecision_mersenns_mult_mod(z1, z1, y1, keyLength);  // t4=t4*t1
154   multiprecision_sub_mod(y3, y3, z1, keyLength);
155 }
156 
157 // Computing the Non-Adjacent Form of a positive integer
ECC_NAF(uint8_t * naf,uint32_t * NumNAF,uint32_t * k,uint32_t keyLength)158 static void ECC_NAF(uint8_t* naf, uint32_t* NumNAF, uint32_t* k,
159                     uint32_t keyLength) {
160   uint32_t sign;
161   int i = 0;
162   int j;
163   uint32_t var;
164 
165   while ((var = multiprecision_most_signbits(k, keyLength)) >= 1) {
166     if (k[0] & 0x01)  // k is odd
167     {
168       sign = (k[0] & 0x03);  // 1 or 3
169 
170       // k = k-naf[i]
171       if (sign == 1)
172         k[0] = k[0] & 0xFFFFFFFE;
173       else {
174         k[0] = k[0] + 1;
175         if (k[0] == 0)  // overflow
176         {
177           j = 1;
178           do {
179             k[j]++;
180           } while (k[j++] == 0);  // overflow
181         }
182       }
183     } else
184       sign = 0;
185 
186     multiprecision_rshift(k, k, keyLength);
187     naf[i / 4] |= (sign) << ((i % 4) * 2);
188     i++;
189   }
190 
191   *NumNAF = i;
192 }
193 
194 // Binary Non-Adjacent Form for point multiplication
ECC_PointMult_Bin_NAF(Point * q,Point * p,uint32_t * n,uint32_t keyLength)195 void ECC_PointMult_Bin_NAF(Point* q, Point* p, uint32_t* n,
196                            uint32_t keyLength) {
197   uint32_t sign;
198   uint8_t naf[256 / 4 + 1];
199   uint32_t NumNaf;
200   Point minus_p;
201   Point r;
202   uint32_t* modp;
203 
204   if (keyLength == KEY_LENGTH_DWORDS_P256) {
205     modp = curve_p256.p;
206   } else {
207     modp = curve.p;
208   }
209 
210   p_256_init_point(&r);
211   multiprecision_init(p->z, keyLength);
212   p->z[0] = 1;
213 
214   // initialization
215   p_256_init_point(q);
216 
217   // -p
218   multiprecision_copy(minus_p.x, p->x, keyLength);
219   multiprecision_sub(minus_p.y, modp, p->y, keyLength);
220 
221   multiprecision_init(minus_p.z, keyLength);
222   minus_p.z[0] = 1;
223 
224   // NAF
225   memset(naf, 0, sizeof(naf));
226   ECC_NAF(naf, &NumNaf, n, keyLength);
227 
228   for (int i = NumNaf - 1; i >= 0; i--) {
229     p_256_copy_point(&r, q);
230     ECC_Double(q, &r, keyLength);
231     sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03;
232 
233     if (sign == 1) {
234       p_256_copy_point(&r, q);
235       ECC_Add(q, &r, p, keyLength);
236     } else if (sign == 3) {
237       p_256_copy_point(&r, q);
238       ECC_Add(q, &r, &minus_p, keyLength);
239     }
240   }
241 
242   multiprecision_inv_mod(minus_p.x, q->z, keyLength);
243   multiprecision_mersenns_squa_mod(q->z, minus_p.x, keyLength);
244   multiprecision_mersenns_mult_mod(q->x, q->x, q->z, keyLength);
245   multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, keyLength);
246   multiprecision_mersenns_mult_mod(q->y, q->y, q->z, keyLength);
247 }
248 
ECC_ValidatePoint(const Point & pt)249 bool ECC_ValidatePoint(const Point& pt) {
250   const size_t kl = KEY_LENGTH_DWORDS_P256;
251   p_256_init_curve(kl);
252 
253   // Ensure y^2 = x^3 + a*x + b (mod p); a = -3
254 
255   // y^2 mod p
256   uint32_t y2_mod[kl] = {0};
257   multiprecision_mersenns_squa_mod(y2_mod, (uint32_t*)pt.y, kl);
258 
259   // Right hand side calculation
260   uint32_t rhs[kl] = {0};
261   multiprecision_mersenns_squa_mod(rhs, (uint32_t*)pt.x, kl);
262   uint32_t three[kl] = {0};
263   three[0] = 3;
264   multiprecision_sub_mod(rhs, rhs, three, kl);
265   multiprecision_mersenns_mult_mod(rhs, rhs, (uint32_t*)pt.x, kl);
266   multiprecision_add_mod(rhs, rhs, curve_p256.b, kl);
267 
268   return multiprecision_compare(rhs, y2_mod, kl) == 0;
269 }
270