1 /******************************************************************************
2 * Filename: sw_poly1305-donna-32.h
3 ******************************************************************************/
4 /*
5 poly1305 implementation using 32 bit * 32 bit = 64 bit multiplication and 64 bit addition
6 */
7
8 #if defined(_MSC_VER)
9 #define POLY1305_NOINLINE __declspec(noinline)
10 #elif defined(__GNUC__)
11 #define POLY1305_NOINLINE __attribute__((noinline))
12 #else
13 #define POLY1305_NOINLINE
14 #endif
15
16 #define poly1305_block_size 16
17
18 /* 17 + sizeof(size_t) + 14*sizeof(unsigned long) */
19 typedef struct
20 {
21 unsigned long r[5];
22 unsigned long h[5];
23 unsigned long pad[4];
24 size_t leftover;
25 unsigned char buffer[poly1305_block_size];
26 unsigned char final;
27 } poly1305_state_internal_t;
28
29 /* interpret four 8 bit unsigned integers as a 32 bit unsigned integer in little endian */
U8TO32(const unsigned char * p)30 static unsigned long U8TO32(const unsigned char *p)
31 {
32 return (((unsigned long)(p[0] & 0xff)) | ((unsigned long)(p[1] & 0xff) << 8) |
33 ((unsigned long)(p[2] & 0xff) << 16) | ((unsigned long)(p[3] & 0xff) << 24));
34 }
35
36 /* store a 32 bit unsigned integer as four 8 bit unsigned integers in little endian */
U32TO8(unsigned char * p,unsigned long v)37 static void U32TO8(unsigned char *p, unsigned long v)
38 {
39 p[0] = (v)&0xff;
40 p[1] = (v >> 8) & 0xff;
41 p[2] = (v >> 16) & 0xff;
42 p[3] = (v >> 24) & 0xff;
43 }
44
poly1305_init(poly1305_context * ctx,const unsigned char key[32])45 void poly1305_init(poly1305_context *ctx, const unsigned char key[32])
46 {
47 poly1305_state_internal_t *st = (poly1305_state_internal_t *)ctx;
48
49 /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
50 st->r[0] = (U8TO32(&key[0])) & 0x3ffffff;
51 st->r[1] = (U8TO32(&key[3]) >> 2) & 0x3ffff03;
52 st->r[2] = (U8TO32(&key[6]) >> 4) & 0x3ffc0ff;
53 st->r[3] = (U8TO32(&key[9]) >> 6) & 0x3f03fff;
54 st->r[4] = (U8TO32(&key[12]) >> 8) & 0x00fffff;
55
56 /* h = 0 */
57 st->h[0] = 0;
58 st->h[1] = 0;
59 st->h[2] = 0;
60 st->h[3] = 0;
61 st->h[4] = 0;
62
63 /* save pad for later */
64 st->pad[0] = U8TO32(&key[16]);
65 st->pad[1] = U8TO32(&key[20]);
66 st->pad[2] = U8TO32(&key[24]);
67 st->pad[3] = U8TO32(&key[28]);
68
69 st->leftover = 0;
70 st->final = 0;
71 }
72
poly1305_blocks(poly1305_state_internal_t * st,const unsigned char * m,size_t bytes)73 static void poly1305_blocks(poly1305_state_internal_t *st, const unsigned char *m, size_t bytes)
74 {
75 const unsigned long hibit = (st->final) ? 0 : (1UL << 24); /* 1 << 128 */
76 unsigned long r0, r1, r2, r3, r4;
77 unsigned long s1, s2, s3, s4;
78 unsigned long h0, h1, h2, h3, h4;
79 unsigned long long d0, d1, d2, d3, d4;
80 unsigned long c;
81
82 r0 = st->r[0];
83 r1 = st->r[1];
84 r2 = st->r[2];
85 r3 = st->r[3];
86 r4 = st->r[4];
87
88 s1 = r1 * 5;
89 s2 = r2 * 5;
90 s3 = r3 * 5;
91 s4 = r4 * 5;
92
93 h0 = st->h[0];
94 h1 = st->h[1];
95 h2 = st->h[2];
96 h3 = st->h[3];
97 h4 = st->h[4];
98
99 while (bytes >= poly1305_block_size)
100 {
101 /* h += m[i] */
102 h0 += (U8TO32(m + 0)) & 0x3ffffff;
103 h1 += (U8TO32(m + 3) >> 2) & 0x3ffffff;
104 h2 += (U8TO32(m + 6) >> 4) & 0x3ffffff;
105 h3 += (U8TO32(m + 9) >> 6) & 0x3ffffff;
106 h4 += (U8TO32(m + 12) >> 8) | hibit;
107
108 /* h *= r */
109 d0 = ((unsigned long long)h0 * r0) + ((unsigned long long)h1 * s4) + ((unsigned long long)h2 * s3) +
110 ((unsigned long long)h3 * s2) + ((unsigned long long)h4 * s1);
111 d1 = ((unsigned long long)h0 * r1) + ((unsigned long long)h1 * r0) + ((unsigned long long)h2 * s4) +
112 ((unsigned long long)h3 * s3) + ((unsigned long long)h4 * s2);
113 d2 = ((unsigned long long)h0 * r2) + ((unsigned long long)h1 * r1) + ((unsigned long long)h2 * r0) +
114 ((unsigned long long)h3 * s4) + ((unsigned long long)h4 * s3);
115 d3 = ((unsigned long long)h0 * r3) + ((unsigned long long)h1 * r2) + ((unsigned long long)h2 * r1) +
116 ((unsigned long long)h3 * r0) + ((unsigned long long)h4 * s4);
117 d4 = ((unsigned long long)h0 * r4) + ((unsigned long long)h1 * r3) + ((unsigned long long)h2 * r2) +
118 ((unsigned long long)h3 * r1) + ((unsigned long long)h4 * r0);
119
120 /* (partial) h %= p */
121 c = (unsigned long)(d0 >> 26);
122 h0 = (unsigned long)d0 & 0x3ffffff;
123 d1 += c;
124 c = (unsigned long)(d1 >> 26);
125 h1 = (unsigned long)d1 & 0x3ffffff;
126 d2 += c;
127 c = (unsigned long)(d2 >> 26);
128 h2 = (unsigned long)d2 & 0x3ffffff;
129 d3 += c;
130 c = (unsigned long)(d3 >> 26);
131 h3 = (unsigned long)d3 & 0x3ffffff;
132 d4 += c;
133 c = (unsigned long)(d4 >> 26);
134 h4 = (unsigned long)d4 & 0x3ffffff;
135 h0 += c * 5;
136 c = (h0 >> 26);
137 h0 = h0 & 0x3ffffff;
138 h1 += c;
139
140 m += poly1305_block_size;
141 bytes -= poly1305_block_size;
142 }
143
144 st->h[0] = h0;
145 st->h[1] = h1;
146 st->h[2] = h2;
147 st->h[3] = h3;
148 st->h[4] = h4;
149 }
150
poly1305_finish(poly1305_context * ctx,unsigned char mac[16])151 POLY1305_NOINLINE void poly1305_finish(poly1305_context *ctx, unsigned char mac[16])
152 {
153 poly1305_state_internal_t *st = (poly1305_state_internal_t *)ctx;
154 unsigned long h0, h1, h2, h3, h4, c;
155 unsigned long g0, g1, g2, g3, g4;
156 unsigned long long f;
157 unsigned long mask;
158
159 /* process the remaining block */
160 if (st->leftover)
161 {
162 size_t i = st->leftover;
163 st->buffer[i++] = 1;
164 for (; i < poly1305_block_size; i++)
165 {
166 st->buffer[i] = 0;
167 }
168 st->final = 1;
169 poly1305_blocks(st, st->buffer, poly1305_block_size);
170 }
171
172 /* fully carry h */
173 h0 = st->h[0];
174 h1 = st->h[1];
175 h2 = st->h[2];
176 h3 = st->h[3];
177 h4 = st->h[4];
178
179 c = h1 >> 26;
180 h1 = h1 & 0x3ffffff;
181 h2 += c;
182 c = h2 >> 26;
183 h2 = h2 & 0x3ffffff;
184 h3 += c;
185 c = h3 >> 26;
186 h3 = h3 & 0x3ffffff;
187 h4 += c;
188 c = h4 >> 26;
189 h4 = h4 & 0x3ffffff;
190 h0 += c * 5;
191 c = h0 >> 26;
192 h0 = h0 & 0x3ffffff;
193 h1 += c;
194
195 /* compute h + -p */
196 g0 = h0 + 5;
197 c = g0 >> 26;
198 g0 &= 0x3ffffff;
199 g1 = h1 + c;
200 c = g1 >> 26;
201 g1 &= 0x3ffffff;
202 g2 = h2 + c;
203 c = g2 >> 26;
204 g2 &= 0x3ffffff;
205 g3 = h3 + c;
206 c = g3 >> 26;
207 g3 &= 0x3ffffff;
208 g4 = h4 + c - (1UL << 26);
209
210 /* select h if h < p, or h + -p if h >= p */
211 mask = (g4 >> ((sizeof(unsigned long) * 8) - 1)) - 1;
212 g0 &= mask;
213 g1 &= mask;
214 g2 &= mask;
215 g3 &= mask;
216 g4 &= mask;
217 mask = ~mask;
218 h0 = (h0 & mask) | g0;
219 h1 = (h1 & mask) | g1;
220 h2 = (h2 & mask) | g2;
221 h3 = (h3 & mask) | g3;
222 h4 = (h4 & mask) | g4;
223
224 /* h = h % (2^128) */
225 h0 = ((h0) | (h1 << 26)) & 0xffffffff;
226 h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffff;
227 h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff;
228 h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffff;
229
230 /* mac = (h + pad) % (2^128) */
231 f = (unsigned long long)h0 + st->pad[0];
232 h0 = (unsigned long)f;
233 f = (unsigned long long)h1 + st->pad[1] + (f >> 32);
234 h1 = (unsigned long)f;
235 f = (unsigned long long)h2 + st->pad[2] + (f >> 32);
236 h2 = (unsigned long)f;
237 f = (unsigned long long)h3 + st->pad[3] + (f >> 32);
238 h3 = (unsigned long)f;
239
240 U32TO8(mac + 0, h0);
241 U32TO8(mac + 4, h1);
242 U32TO8(mac + 8, h2);
243 U32TO8(mac + 12, h3);
244
245 /* zero out the state */
246 st->h[0] = 0;
247 st->h[1] = 0;
248 st->h[2] = 0;
249 st->h[3] = 0;
250 st->h[4] = 0;
251 st->r[0] = 0;
252 st->r[1] = 0;
253 st->r[2] = 0;
254 st->r[3] = 0;
255 st->r[4] = 0;
256 st->pad[0] = 0;
257 st->pad[1] = 0;
258 st->pad[2] = 0;
259 st->pad[3] = 0;
260 }
261
