nacl/signing/
fe25519.rs

1// Copyright(c) 2018, 2021 3NSoft Inc.
2//
3// This program is free software: you can redistribute it and/or modify
4// it under the terms of the GNU Lesser General Public License as published by
5// the Free Software Foundation, either version 3 of the License, or
6// (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful,
9// but WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11// GNU Lesser General Public License for more details.
12//
13// You should have received a copy of the GNU Lesser General Public License
14// along with this program.  If not, see <http://www.gnu.org/licenses/>.
15
16//! This module provides functionality found in
17//! crypto_sign/ed25519/ref/fe25519.c
18
19use crate::util::ops::{ subw };
20
21/// Analog of struct fe25519 in crypto_sign/ed25519/ref/fe25519.h
22pub struct Fe25519 {
23	pub v: [u32; 32],
24}
25
26#[inline]
27pub fn make_fe25519() -> Fe25519 {
28	Fe25519 { v: [0; 32] }
29}
30
31#[inline]
32pub fn make_copy_fe25519(x: &Fe25519) -> Fe25519 {
33	let mut copy = make_fe25519();
34	copy.v.copy_from_slice(&x.v);
35	copy
36}
37
38#[inline]
39pub fn fe25519_cp(r: &mut Fe25519, x: &Fe25519) {
40	r.v.copy_from_slice(&x.v);
41}
42
43/// Analog of equal in crypto_sign/ed25519/ref/fe25519.c
44/// All inputs are 16-bit.
45#[inline]
46fn equal(a: u32, b: u32) -> u32 {
47	let mut x = a ^ b; /* 0: yes; 1..65535: no */
48	x = subw!( x, 1 as u32 ); /* 4294967295: yes; 0..65534: no */
49	x >>= 31; /* 1: yes; 0: no */
50	x
51}
52
53/// Analog of ge in crypto_sign/ed25519/ref/fe25519.c
54/// All inputs are 16-bit.
55#[inline]
56fn ge(a: u32, b: u32) -> u32 {
57	let mut x = a;
58	x = subw!( x, b ); /* 0..65535: yes; 4294901761..4294967295: no */
59	x >>= 31; /* 0: yes; 1: no */
60	x ^= 1; /* 1: yes; 0: no */
61	x
62}
63
64/// Analog of times19 in crypto_sign/ed25519/ref/fe25519.c
65#[inline]
66fn times19(a: u32) -> u32 {
67	(a << 4) + (a << 1) + a
68}
69
70/// Analog of times38 in crypto_sign/ed25519/ref/fe25519.c
71#[inline]
72fn times38(a: u32) -> u32 {
73	(a << 5) + (a << 2) + (a << 1)
74}
75
76/// Analog of reduce_add_sub in crypto_sign/ed25519/ref/fe25519.c
77fn reduce_add_sub(r: &mut Fe25519) {
78	for _ in 0..4 {
79		let mut t = r.v[31] >> 7;
80		r.v[31] &= 127;
81		t = times19(t);
82		r.v[0] += t;
83		for i in 0..31 {
84			t = r.v[i] >> 8;
85			r.v[i+1] += t;
86			r.v[i] &= 255;
87		}
88	}
89}
90
91/// Analog of reduce_mul in crypto_sign/ed25519/ref/fe25519.c
92fn reduce_mul(r: &mut Fe25519) {
93	for _ in 0..2 {
94		let mut t = r.v[31] >> 7;
95		r.v[31] &= 127;
96		t = times19(t);
97		r.v[0] += t;
98		for i in 0..31 {
99			t = r.v[i] >> 8;
100			r.v[i+1] += t;
101			r.v[i] &= 255;
102		}
103	}
104}
105
106/// Analog of fe25519_freeze in crypto_sign/ed25519/ref/fe25519.c
107/// reduction modulo 2^255-19
108fn fe25519_freeze(r: &mut Fe25519) {
109	let mut m = equal(r.v[31],127);
110	let mut i: usize = 30;
111	while i > 0 {
112		m &= equal(r.v[i],255);
113		i -= 1;
114	}
115	m &= ge(r.v[0],237);
116
117	m = 0 - m;
118
119	r.v[31] -= m&127;
120	i = 30;
121	while i > 0 {
122		r.v[i] -= m&255;
123		i -= 1;
124	}
125	r.v[0] -= m&237;
126}
127
128/// Analog of fe25519_unpack in crypto_sign/ed25519/ref/fe25519.c
129pub fn fe25519_unpack(r: &mut Fe25519, x: &[u8]) {
130	for i in 0..32 { r.v[i] = x[i] as u32; }
131	r.v[31] &= 127;
132}
133
134/// Analog of fe25519_unpack in crypto_sign/ed25519/ref/fe25519.c
135/// Assumes input x being reduced below 2^255
136pub fn fe25519_pack(r: &mut [u8], x: &Fe25519) {
137	let mut y = make_copy_fe25519(x);
138	fe25519_freeze(&mut y);
139	for i in 0..32 { r[i] = y.v[i] as u8; }
140}
141
142/// Analog of fe25519_iseq_vartime in crypto_sign/ed25519/ref/fe25519.c
143pub fn fe25519_iseq_vartime(x: &Fe25519, y: &Fe25519) -> bool {
144	let mut t1 = make_copy_fe25519(x);
145	let mut t2 = make_copy_fe25519(y);
146	fe25519_freeze(&mut t1);
147	fe25519_freeze(&mut t2);
148	for i in 0..32 {
149		if t1.v[i] != t2.v[i] { return false; }
150	}
151	true
152}
153
154/// Analog of fe25519_cmov in crypto_sign/ed25519/ref/fe25519.c
155pub fn fe25519_cmov(r: &mut Fe25519, x: &Fe25519, b: u8) {
156  let mut mask: u32 = b as u32;
157  mask = subw!( 0 as u32, mask );
158  for i in 0..32 { r.v[i] ^= mask & (x.v[i] ^ r.v[i]); }
159}
160
161/// Analog of fe25519_getparity in crypto_sign/ed25519/ref/fe25519.c
162pub fn fe25519_getparity(x: &Fe25519) -> u8 {
163	let mut t = make_copy_fe25519(x);
164	fe25519_freeze(&mut t);
165	(t.v[0] & 1) as u8
166}
167
168/// Analog of fe25519_setone in crypto_sign/ed25519/ref/fe25519.c
169pub fn fe25519_setone(r: &mut Fe25519) {
170	r.v[0] = 1;
171	for i in 1..32 { r.v[i] = 0; }
172}
173
174/// Analog of fe25519_setzero in crypto_sign/ed25519/ref/fe25519.c
175pub fn fe25519_setzero(r: &mut Fe25519) {
176	for i in 0..32 { r.v[i]=0; }
177}
178
179const ZERO_FE25519: Fe25519 = Fe25519 { v: [0; 32] };
180
181/// Analog of fe25519_neg in crypto_sign/ed25519/ref/fe25519.c
182pub fn fe25519_neg(r: &mut Fe25519, x: &Fe25519) {
183	let t = make_copy_fe25519(x);
184	fe25519_sub(r, &ZERO_FE25519, &t);
185}
186
187/// Analog of fe25519_add in crypto_sign/ed25519/ref/fe25519.c
188pub fn fe25519_add(r: &mut Fe25519, x: &Fe25519, y: &Fe25519) {
189	for i in 0..32 { r.v[i] = x.v[i] + y.v[i]; }
190	reduce_add_sub(r);
191}
192
193/// Analog of fe25519_sub in crypto_sign/ed25519/ref/fe25519.c
194pub fn fe25519_sub(r: &mut Fe25519, x: &Fe25519, y: &Fe25519) {
195	let mut t: [u32; 32] = [0; 32];
196	t[0] = x.v[0] + 0x1da;
197	t[31] = x.v[31] + 0xfe;
198	for i in 1..31 { t[i] = x.v[i] + 0x1fe; }
199	for i in 0..32 { r.v[i] = t[i] - y.v[i]; }
200	reduce_add_sub(r);
201}
202
203/// Analog of fe25519_mul in crypto_sign/ed25519/ref/fe25519.c
204pub fn fe25519_mul(r: &mut Fe25519, x: &Fe25519, y: &Fe25519) {
205	let mut t: [u32; 63] = [0; 63];
206
207	for i in 0..32 {
208		for j in 0..32 {
209			t[i+j] += x.v[i] * y.v[j];
210		}
211	}
212
213	for i in 32..63 {
214		r.v[i-32] = t[i-32] + times38(t[i]);
215	}
216	r.v[31] = t[31]; // result now in r[0]...r[31]
217
218	reduce_mul(r);
219}
220
221/// Analog of fe25519_square in crypto_sign/ed25519/ref/fe25519.c
222#[inline]
223pub fn fe25519_square(r: &mut Fe25519, x: &Fe25519) {
224	fe25519_mul(r, x, x);
225}
226
227// pub fn fe25519_square_same(x: &mut Fe25519, t: &mut Fe25519) {
228// 	t.v.copy_from_slice(&x.v);
229// 	fe25519_mul(x, t, t);
230// }
231
232/// Analog of fe25519_invert in crypto_sign/ed25519/ref/fe25519.c
233pub fn fe25519_invert(r: &mut Fe25519, x: &Fe25519) {
234	let mut z2 = make_fe25519();
235	let mut z9 = make_fe25519();
236	let mut z11 = make_fe25519();
237	let mut z2_5_0 = make_fe25519();
238	let mut z2_10_0 = make_fe25519();
239	let mut z2_20_0 = make_fe25519();
240	let mut z2_50_0 = make_fe25519();
241	let mut z2_100_0 = make_fe25519();
242	let mut t0 = make_fe25519();
243	let mut t1 = make_fe25519();
244	
245	/* 2 */ fe25519_square(&mut z2, x);
246	/* 4 */ fe25519_square(&mut t1, &z2);
247	/* 8 */ fe25519_square(&mut t0, &t1);
248	/* 9 */ fe25519_mul(&mut z9, &t0, x);
249	/* 11 */ fe25519_mul(&mut z11, &z9, &z2);
250	/* 22 */ fe25519_square(&mut t0, &z11);
251	/* 2^5 - 2^0 = 31 */ fe25519_mul(&mut z2_5_0, &t0, &z9);
252
253	/* 2^6 - 2^1 */ fe25519_square(&mut t0, &z2_5_0);
254	/* 2^7 - 2^2 */ fe25519_square(&mut t1, &t0);
255	/* 2^8 - 2^3 */ fe25519_square(&mut t0, &t1);
256	/* 2^9 - 2^4 */ fe25519_square(&mut t1, &t0);
257	/* 2^10 - 2^5 */ fe25519_square(&mut t0, &t1);
258	/* 2^10 - 2^0 */ fe25519_mul(&mut z2_10_0, &t0, &z2_5_0);
259
260	/* 2^11 - 2^1 */ fe25519_square(&mut t0, &z2_10_0);
261	/* 2^12 - 2^2 */ fe25519_square(&mut t1, &t0);
262	/* 2^20 - 2^10 */ for _ in 1..5 { fe25519_square(&mut t0, &t1); fe25519_square(&mut t1, &t0); }
263	/* 2^20 - 2^0 */ fe25519_mul(&mut z2_20_0, &t1, &z2_10_0);
264
265	/* 2^21 - 2^1 */ fe25519_square(&mut t0, &z2_20_0);
266	/* 2^22 - 2^2 */ fe25519_square(&mut t1, &t0);
267	/* 2^40 - 2^20 */ for _ in 1..10 { fe25519_square(&mut t0, &t1); fe25519_square(&mut t1, &t0); }
268	/* 2^40 - 2^0 */ fe25519_mul(&mut t0, &t1, &z2_20_0);
269
270	/* 2^41 - 2^1 */ fe25519_square(&mut t1, &t0);
271	/* 2^42 - 2^2 */ fe25519_square(&mut t0, &t1);
272	/* 2^50 - 2^10 */ for _ in 1..5 { fe25519_square(&mut t1, &t0); fe25519_square(&mut t0, &t1); }
273	/* 2^50 - 2^0 */ fe25519_mul(&mut z2_50_0, &t0, &z2_10_0);
274
275	/* 2^51 - 2^1 */ fe25519_square(&mut t0, &z2_50_0);
276	/* 2^52 - 2^2 */ fe25519_square(&mut t1, &t0);
277	/* 2^100 - 2^50 */ for _ in 1..25 { fe25519_square(&mut t0, &t1); fe25519_square(&mut t1, &t0); }
278	/* 2^100 - 2^0 */ fe25519_mul(&mut z2_100_0, &t1, &z2_50_0);
279
280	/* 2^101 - 2^1 */ fe25519_square(&mut t1, &z2_100_0);
281	/* 2^102 - 2^2 */ fe25519_square(&mut t0, &t1);
282	/* 2^200 - 2^100 */ for _ in 1..50 { fe25519_square(&mut t1, &t0); fe25519_square(&mut t0, &t1); }
283	/* 2^200 - 2^0 */ fe25519_mul(&mut t1, &t0, &z2_100_0);
284
285	/* 2^201 - 2^1 */ fe25519_square(&mut t0, &t1);
286	/* 2^202 - 2^2 */ fe25519_square(&mut t1, &t0);
287	/* 2^250 - 2^50 */ for _ in 1..25 { fe25519_square(&mut t0, &t1); fe25519_square(&mut t1, &t0); }
288	/* 2^250 - 2^0 */ fe25519_mul(&mut t0, &t1, &z2_50_0);
289
290	/* 2^251 - 2^1 */ fe25519_square(&mut t1, &t0);
291	/* 2^252 - 2^2 */ fe25519_square(&mut t0, &t1);
292	/* 2^253 - 2^3 */ fe25519_square(&mut t1, &t0);
293	/* 2^254 - 2^4 */ fe25519_square(&mut t0, &t1);
294	/* 2^255 - 2^5 */ fe25519_square(&mut t1, &t0);
295	/* 2^255 - 21 */ fe25519_mul(r, &t1, &z11);
296}
297
298/// Analog of fe25519_pow2523 in crypto_sign/ed25519/ref/fe25519.c
299pub fn fe25519_pow2523(r: &mut Fe25519, x: &Fe25519) {
300	let mut z2 = make_fe25519();
301	let mut z9 = make_fe25519();
302	let mut z11 = make_fe25519();
303	let mut z2_5_0 = make_fe25519();
304	let mut z2_10_0 = make_fe25519();
305	let mut z2_20_0 = make_fe25519();
306	let mut z2_50_0 = make_fe25519();
307	let mut z2_100_0 = make_fe25519();
308	let mut t = make_fe25519();
309	let mut t2 = make_fe25519();
310
311	/* 2 */ fe25519_square(&mut z2, x);
312	/* 4 */ fe25519_square(&mut t, &z2);
313	/* 8 */ fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2);
314	/* 9 */ fe25519_mul(&mut z9, &t, x);
315	/* 11 */ fe25519_mul(&mut z11, &z9, &z2);
316	/* 22 */ fe25519_square(&mut t, &z11);
317	/* 2^5 - 2^0 = 31 */ fe25519_mul(&mut z2_5_0, &t, &z9);
318
319	/* 2^6 - 2^1 */ fe25519_square(&mut t, &z2_5_0);
320	/* 2^10 - 2^5 */ for _ in 1..5 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
321	/* 2^10 - 2^0 */ fe25519_mul(&mut z2_10_0, &t, &z2_5_0);
322
323	/* 2^11 - 2^1 */ fe25519_square(&mut t, &z2_10_0);
324	/* 2^20 - 2^10 */ for _ in 1..10 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
325	/* 2^20 - 2^0 */ fe25519_mul(&mut z2_20_0, &t, &z2_10_0);
326
327	/* 2^21 - 2^1 */ fe25519_square(&mut t, &z2_20_0);
328	/* 2^40 - 2^20 */ for _ in 1..20 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
329	/* 2^40 - 2^0 */ fe25519_mul(&mut t2, &t, &z2_20_0); fe25519_cp(&mut t, &t2);
330
331	/* 2^41 - 2^1 */ fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2);
332	/* 2^50 - 2^10 */ for _ in 1..10 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
333	/* 2^50 - 2^0 */ fe25519_mul(&mut z2_50_0, &t, &z2_10_0);
334
335	/* 2^51 - 2^1 */ fe25519_square(&mut t, &z2_50_0);
336	/* 2^100 - 2^50 */ for _ in 1..50 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
337	/* 2^100 - 2^0 */ fe25519_mul(&mut z2_100_0, &t, &z2_50_0);
338
339	/* 2^101 - 2^1 */ fe25519_square(&mut t, &z2_100_0);
340	/* 2^200 - 2^100 */ for _ in 1..100 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
341	/* 2^200 - 2^0 */ fe25519_mul(&mut t2, &t, &z2_100_0); fe25519_cp(&mut t, &t2);
342
343	/* 2^201 - 2^1 */ fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2);
344	/* 2^250 - 2^50 */ for _ in 1..50 { fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2); }
345	/* 2^250 - 2^0 */ fe25519_mul(&mut t2, &t, &z2_50_0); fe25519_cp(&mut t, &t2);
346
347	/* 2^251 - 2^1 */ fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2);
348	/* 2^252 - 2^2 */ fe25519_square(&mut t2, &t); fe25519_cp(&mut t, &t2);
349	/* 2^252 - 3 */ fe25519_mul(r, &t, x);
350}
351
nacl/signing/fe25519.rs

nacl/signing/
fe25519.rs
