1 /*
2 Ignores top bit of h.
3 */
4
5 void
fe25519_frombytes(fe25519 h,const unsigned char * s)6 fe25519_frombytes(fe25519 h, const unsigned char *s)
7 {
8 int64_t h0 = load_4(s);
9 int64_t h1 = load_3(s + 4) << 6;
10 int64_t h2 = load_3(s + 7) << 5;
11 int64_t h3 = load_3(s + 10) << 3;
12 int64_t h4 = load_3(s + 13) << 2;
13 int64_t h5 = load_4(s + 16);
14 int64_t h6 = load_3(s + 20) << 7;
15 int64_t h7 = load_3(s + 23) << 5;
16 int64_t h8 = load_3(s + 26) << 4;
17 int64_t h9 = (load_3(s + 29) & 8388607) << 2;
18
19 int64_t carry0;
20 int64_t carry1;
21 int64_t carry2;
22 int64_t carry3;
23 int64_t carry4;
24 int64_t carry5;
25 int64_t carry6;
26 int64_t carry7;
27 int64_t carry8;
28 int64_t carry9;
29
30 carry9 = (h9 + (int64_t)(1L << 24)) >> 25;
31 h0 += carry9 * 19;
32 h9 -= carry9 * ((uint64_t) 1L << 25);
33 carry1 = (h1 + (int64_t)(1L << 24)) >> 25;
34 h2 += carry1;
35 h1 -= carry1 * ((uint64_t) 1L << 25);
36 carry3 = (h3 + (int64_t)(1L << 24)) >> 25;
37 h4 += carry3;
38 h3 -= carry3 * ((uint64_t) 1L << 25);
39 carry5 = (h5 + (int64_t)(1L << 24)) >> 25;
40 h6 += carry5;
41 h5 -= carry5 * ((uint64_t) 1L << 25);
42 carry7 = (h7 + (int64_t)(1L << 24)) >> 25;
43 h8 += carry7;
44 h7 -= carry7 * ((uint64_t) 1L << 25);
45
46 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
47 h1 += carry0;
48 h0 -= carry0 * ((uint64_t) 1L << 26);
49 carry2 = (h2 + (int64_t)(1L << 25)) >> 26;
50 h3 += carry2;
51 h2 -= carry2 * ((uint64_t) 1L << 26);
52 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
53 h5 += carry4;
54 h4 -= carry4 * ((uint64_t) 1L << 26);
55 carry6 = (h6 + (int64_t)(1L << 25)) >> 26;
56 h7 += carry6;
57 h6 -= carry6 * ((uint64_t) 1L << 26);
58 carry8 = (h8 + (int64_t)(1L << 25)) >> 26;
59 h9 += carry8;
60 h8 -= carry8 * ((uint64_t) 1L << 26);
61
62 h[0] = (int32_t) h0;
63 h[1] = (int32_t) h1;
64 h[2] = (int32_t) h2;
65 h[3] = (int32_t) h3;
66 h[4] = (int32_t) h4;
67 h[5] = (int32_t) h5;
68 h[6] = (int32_t) h6;
69 h[7] = (int32_t) h7;
70 h[8] = (int32_t) h8;
71 h[9] = (int32_t) h9;
72 }
73
74 /*
75 Preconditions:
76 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
77
78 Write p=2^255-19; q=floor(h/p).
79 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
80
81 Proof:
82 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
83 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
84
85 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
86 Then 0<y<1.
87
88 Write r=h-pq.
89 Have 0<=r<=p-1=2^255-20.
90 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
91
92 Write x=r+19(2^-255)r+y.
93 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
94
95 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
96 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
97 */
98
99 static void
fe25519_reduce(fe25519 h,const fe25519 f)100 fe25519_reduce(fe25519 h, const fe25519 f)
101 {
102 int32_t h0 = f[0];
103 int32_t h1 = f[1];
104 int32_t h2 = f[2];
105 int32_t h3 = f[3];
106 int32_t h4 = f[4];
107 int32_t h5 = f[5];
108 int32_t h6 = f[6];
109 int32_t h7 = f[7];
110 int32_t h8 = f[8];
111 int32_t h9 = f[9];
112
113 int32_t q;
114 int32_t carry0, carry1, carry2, carry3, carry4, carry5, carry6, carry7, carry8, carry9;
115
116 q = (19 * h9 + ((uint32_t) 1L << 24)) >> 25;
117 q = (h0 + q) >> 26;
118 q = (h1 + q) >> 25;
119 q = (h2 + q) >> 26;
120 q = (h3 + q) >> 25;
121 q = (h4 + q) >> 26;
122 q = (h5 + q) >> 25;
123 q = (h6 + q) >> 26;
124 q = (h7 + q) >> 25;
125 q = (h8 + q) >> 26;
126 q = (h9 + q) >> 25;
127
128 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
129 h0 += 19 * q;
130 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
131
132 carry0 = h0 >> 26;
133 h1 += carry0;
134 h0 -= carry0 * ((uint32_t) 1L << 26);
135 carry1 = h1 >> 25;
136 h2 += carry1;
137 h1 -= carry1 * ((uint32_t) 1L << 25);
138 carry2 = h2 >> 26;
139 h3 += carry2;
140 h2 -= carry2 * ((uint32_t) 1L << 26);
141 carry3 = h3 >> 25;
142 h4 += carry3;
143 h3 -= carry3 * ((uint32_t) 1L << 25);
144 carry4 = h4 >> 26;
145 h5 += carry4;
146 h4 -= carry4 * ((uint32_t) 1L << 26);
147 carry5 = h5 >> 25;
148 h6 += carry5;
149 h5 -= carry5 * ((uint32_t) 1L << 25);
150 carry6 = h6 >> 26;
151 h7 += carry6;
152 h6 -= carry6 * ((uint32_t) 1L << 26);
153 carry7 = h7 >> 25;
154 h8 += carry7;
155 h7 -= carry7 * ((uint32_t) 1L << 25);
156 carry8 = h8 >> 26;
157 h9 += carry8;
158 h8 -= carry8 * ((uint32_t) 1L << 26);
159 carry9 = h9 >> 25;
160 h9 -= carry9 * ((uint32_t) 1L << 25);
161
162 h[0] = h0;
163 h[1] = h1;
164 h[2] = h2;
165 h[3] = h3;
166 h[4] = h4;
167 h[5] = h5;
168 h[6] = h6;
169 h[7] = h7;
170 h[8] = h8;
171 h[9] = h9;
172 }
173
174 /*
175 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
176 Have h0+...+2^230 h9 between 0 and 2^255-1;
177 evidently 2^255 h10-2^255 q = 0.
178
179 Goal: Output h0+...+2^230 h9.
180 */
181
182 void
fe25519_tobytes(unsigned char * s,const fe25519 h)183 fe25519_tobytes(unsigned char *s, const fe25519 h)
184 {
185 fe25519 t;
186
187 fe25519_reduce(t, h);
188 s[0] = t[0] >> 0;
189 s[1] = t[0] >> 8;
190 s[2] = t[0] >> 16;
191 s[3] = (t[0] >> 24) | (t[1] * ((uint32_t) 1 << 2));
192 s[4] = t[1] >> 6;
193 s[5] = t[1] >> 14;
194 s[6] = (t[1] >> 22) | (t[2] * ((uint32_t) 1 << 3));
195 s[7] = t[2] >> 5;
196 s[8] = t[2] >> 13;
197 s[9] = (t[2] >> 21) | (t[3] * ((uint32_t) 1 << 5));
198 s[10] = t[3] >> 3;
199 s[11] = t[3] >> 11;
200 s[12] = (t[3] >> 19) | (t[4] * ((uint32_t) 1 << 6));
201 s[13] = t[4] >> 2;
202 s[14] = t[4] >> 10;
203 s[15] = t[4] >> 18;
204 s[16] = t[5] >> 0;
205 s[17] = t[5] >> 8;
206 s[18] = t[5] >> 16;
207 s[19] = (t[5] >> 24) | (t[6] * ((uint32_t) 1 << 1));
208 s[20] = t[6] >> 7;
209 s[21] = t[6] >> 15;
210 s[22] = (t[6] >> 23) | (t[7] * ((uint32_t) 1 << 3));
211 s[23] = t[7] >> 5;
212 s[24] = t[7] >> 13;
213 s[25] = (t[7] >> 21) | (t[8] * ((uint32_t) 1 << 4));
214 s[26] = t[8] >> 4;
215 s[27] = t[8] >> 12;
216 s[28] = (t[8] >> 20) | (t[9] * ((uint32_t) 1 << 6));
217 s[29] = t[9] >> 2;
218 s[30] = t[9] >> 10;
219 s[31] = t[9] >> 18;
220 }
221