GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/signify/sc25519.c Lines: 91 129 70.5 %
Date: 2017-11-13 Branches: 52 78 66.7 %

Line Branch Exec Source
1
/* $OpenBSD: sc25519.c,v 1.1 2014/07/22 00:41:19 deraadt Exp $ */
2
3
/*
4
 * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange,
5
 * Peter Schwabe, Bo-Yin Yang.
6
 * Copied from supercop-20130419/crypto_sign/ed25519/ref/sc25519.c
7
 */
8
9
#include "sc25519.h"
10
11
/*Arithmetic modulo the group order m = 2^252 +  27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
12
13
static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
14
                                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
15
16
static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
17
                                     0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F};
18
19
static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
20
{
21
  unsigned int x = a;
22
21376
  x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
23
10688
  x >>= 31; /* 0: no; 1: yes */
24
10688
  return x;
25
}
26
27
/* Reduce coefficients of r before calling reduce_add_sub */
28
static void reduce_add_sub(sc25519 *r)
29
{
30
  crypto_uint32 pb = 0;
31
  crypto_uint32 b;
32
  crypto_uint32 mask;
33
  int i;
34
456
  unsigned char t[32];
35
36
15048
  for(i=0;i<32;i++)
37
  {
38
7296
    pb += m[i];
39
7296
    b = lt(r->v[i],pb);
40
7296
    t[i] = r->v[i]-pb+(b<<8);
41
    pb = b;
42
  }
43
228
  mask = b - 1;
44
15048
  for(i=0;i<32;i++)
45
7296
    r->v[i] ^= mask & (r->v[i] ^ t[i]);
46
228
}
47
48
/* Reduce coefficients of x before calling barrett_reduce */
49
static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64])
50
{
51
  /* See HAC, Alg. 14.42 */
52
  int i,j;
53
212
  crypto_uint32 q2[66];
54
106
  crypto_uint32 *q3 = q2 + 33;
55
106
  crypto_uint32 r1[33];
56
106
  crypto_uint32 r2[33];
57
  crypto_uint32 carry;
58
  crypto_uint32 pb = 0;
59
  crypto_uint32 b;
60
61
14204
  for (i = 0;i < 66;++i) q2[i] = 0;
62
7208
  for (i = 0;i < 33;++i) r2[i] = 0;
63
64
7208
  for(i=0;i<33;i++)
65
237864
    for(j=0;j<33;j++)
66
178292
      if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
67
106
  carry = q2[31] >> 8;
68
106
  q2[32] += carry;
69
106
  carry = q2[32] >> 8;
70
106
  q2[33] += carry;
71
72
7208
  for(i=0;i<33;i++)r1[i] = x[i];
73
6996
  for(i=0;i<32;i++)
74
230656
    for(j=0;j<33;j++)
75
171296
      if(i+j < 33) r2[i+j] += m[i]*q3[j];
76
77
6996
  for(i=0;i<32;i++)
78
  {
79
3392
    carry = r2[i] >> 8;
80
3392
    r2[i+1] += carry;
81
3392
    r2[i] &= 0xff;
82
  }
83
84
6996
  for(i=0;i<32;i++)
85
  {
86
3392
    pb += r2[i];
87
3392
    b = lt(r1[i],pb);
88
3392
    r->v[i] = r1[i]-pb+(b<<8);
89
    pb = b;
90
  }
91
92
  /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
93
   * If so: Handle  it here!
94
   */
95
96
106
  reduce_add_sub(r);
97
106
  reduce_add_sub(r);
98
106
}
99
100
void sc25519_from32bytes(sc25519 *r, const unsigned char x[32])
101
{
102
  int i;
103
74
  crypto_uint32 t[64];
104
2442
  for(i=0;i<32;i++) t[i] = x[i];
105
2442
  for(i=32;i<64;++i) t[i] = 0;
106
37
  barrett_reduce(r, t);
107
37
}
108
109
void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16])
110
{
111
  int i;
112
  for(i=0;i<16;i++) r->v[i] = x[i];
113
}
114
115
void sc25519_from64bytes(sc25519 *r, const unsigned char x[64])
116
{
117
  int i;
118
106
  crypto_uint32 t[64];
119
6890
  for(i=0;i<64;i++) t[i] = x[i];
120
53
  barrett_reduce(r, t);
121
53
}
122
123
void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x)
124
{
125
  int i;
126
  for(i=0;i<16;i++)
127
    r->v[i] = x->v[i];
128
  for(i=0;i<16;i++)
129
    r->v[16+i] = 0;
130
}
131
132
void sc25519_to32bytes(unsigned char r[32], const sc25519 *x)
133
{
134
  int i;
135
1072
  for(i=0;i<32;i++) r[i] = x->v[i];
136
16
}
137
138
int sc25519_iszero_vartime(const sc25519 *x)
139
{
140
  int i;
141
  for(i=0;i<32;i++)
142
    if(x->v[i] != 0) return 0;
143
  return 1;
144
}
145
146
int sc25519_isshort_vartime(const sc25519 *x)
147
{
148
  int i;
149
  for(i=31;i>15;i--)
150
    if(x->v[i] != 0) return 0;
151
  return 1;
152
}
153
154
int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y)
155
{
156
  int i;
157
  for(i=31;i>=0;i--)
158
  {
159
    if(x->v[i] < y->v[i]) return 1;
160
    if(x->v[i] > y->v[i]) return 0;
161
  }
162
  return 0;
163
}
164
165
void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y)
166
{
167
  int i, carry;
168
1072
  for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
169
1024
  for(i=0;i<31;i++)
170
  {
171
496
    carry = r->v[i] >> 8;
172
496
    r->v[i+1] += carry;
173
496
    r->v[i] &= 0xff;
174
  }
175
16
  reduce_add_sub(r);
176
16
}
177
178
void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y)
179
{
180
  crypto_uint32 b = 0;
181
  crypto_uint32 t;
182
  int i;
183
  for(i=0;i<32;i++)
184
  {
185
    t = x->v[i] - y->v[i] - b;
186
    r->v[i] = t & 255;
187
    b = (t >> 8) & 1;
188
  }
189
}
190
191
void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y)
192
{
193
  int i,j,carry;
194
32
  crypto_uint32 t[64];
195
2080
  for(i=0;i<64;i++)t[i] = 0;
196
197
1056
  for(i=0;i<32;i++)
198
33792
    for(j=0;j<32;j++)
199
16384
      t[i+j] += x->v[i] * y->v[j];
200
201
  /* Reduce coefficients */
202
2048
  for(i=0;i<63;i++)
203
  {
204
1008
    carry = t[i] >> 8;
205
1008
    t[i+1] += carry;
206
1008
    t[i] &= 0xff;
207
  }
208
209
16
  barrett_reduce(r, t);
210
16
}
211
212
void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y)
213
{
214
  sc25519 t;
215
  sc25519_from_shortsc(&t, y);
216
  sc25519_mul(r, x, &t);
217
}
218
219
void sc25519_window3(signed char r[85], const sc25519 *s)
220
{
221
  char carry;
222
  int i;
223
368
  for(i=0;i<10;i++)
224
  {
225
    r[8*i+0]  =  s->v[3*i+0]       & 7;
226
    r[8*i+1]  = (s->v[3*i+0] >> 3) & 7;
227
    r[8*i+2]  = (s->v[3*i+0] >> 6) & 7;
228
    r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
229
    r[8*i+3]  = (s->v[3*i+1] >> 1) & 7;
230
    r[8*i+4]  = (s->v[3*i+1] >> 4) & 7;
231
160
    r[8*i+5]  = (s->v[3*i+1] >> 7) & 7;
232
160
    r[8*i+5] ^= (s->v[3*i+2] << 1) & 7;
233
160
    r[8*i+6]  = (s->v[3*i+2] >> 2) & 7;
234
160
    r[8*i+7]  = (s->v[3*i+2] >> 5) & 7;
235
  }
236
  r[8*i+0]  =  s->v[3*i+0]       & 7;
237
  r[8*i+1]  = (s->v[3*i+0] >> 3) & 7;
238
  r[8*i+2]  = (s->v[3*i+0] >> 6) & 7;
239
  r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
240
  r[8*i+3]  = (s->v[3*i+1] >> 1) & 7;
241
  r[8*i+4]  = (s->v[3*i+1] >> 4) & 7;
242
243
  /* Making it signed */
244
  carry = 0;
245
2720
  for(i=0;i<84;i++)
246
  {
247
1344
    r[i] += carry;
248
1344
    r[i+1] += r[i] >> 3;
249
1344
    r[i] &= 7;
250
1344
    carry = r[i] >> 2;
251
1344
    r[i] -= carry<<3;
252
  }
253
16
  r[84] += carry;
254
16
}
255
256
void sc25519_window5(signed char r[51], const sc25519 *s)
257
{
258
  char carry;
259
  int i;
260
  for(i=0;i<6;i++)
261
  {
262
    r[8*i+0]  =  s->v[5*i+0]       & 31;
263
    r[8*i+1]  = (s->v[5*i+0] >> 5) & 31;
264
    r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
265
    r[8*i+2]  = (s->v[5*i+1] >> 2) & 31;
266
    r[8*i+3]  = (s->v[5*i+1] >> 7) & 31;
267
    r[8*i+3] ^= (s->v[5*i+2] << 1) & 31;
268
    r[8*i+4]  = (s->v[5*i+2] >> 4) & 31;
269
    r[8*i+4] ^= (s->v[5*i+3] << 4) & 31;
270
    r[8*i+5]  = (s->v[5*i+3] >> 1) & 31;
271
    r[8*i+6]  = (s->v[5*i+3] >> 6) & 31;
272
    r[8*i+6] ^= (s->v[5*i+4] << 2) & 31;
273
    r[8*i+7]  = (s->v[5*i+4] >> 3) & 31;
274
  }
275
  r[8*i+0]  =  s->v[5*i+0]       & 31;
276
  r[8*i+1]  = (s->v[5*i+0] >> 5) & 31;
277
  r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
278
  r[8*i+2]  = (s->v[5*i+1] >> 2) & 31;
279
280
  /* Making it signed */
281
  carry = 0;
282
  for(i=0;i<50;i++)
283
  {
284
    r[i] += carry;
285
    r[i+1] += r[i] >> 5;
286
    r[i] &= 31;
287
    carry = r[i] >> 4;
288
    r[i] -= carry<<5;
289
  }
290
  r[50] += carry;
291
}
292
293
void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2)
294
{
295
  int i;
296
1365
  for(i=0;i<31;i++)
297
  {
298
651
    r[4*i]   = ( s1->v[i]       & 3) ^ (( s2->v[i]       & 3) << 2);
299
651
    r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
300
651
    r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
301
651
    r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
302
  }
303
21
  r[124] = ( s1->v[31]       & 3) ^ (( s2->v[31]       & 3) << 2);
304
21
  r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
305
21
  r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
306
21
}