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