NAF(Non-adjacent form) w-NAF及其在curve25519-dalek中scalar的实现

本文主要是介绍NAF(Non-adjacent form) w-NAF及其在curve25519-dalek中scalar的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 引言

The non-adjacent form (NAF) of a number is a unique signed-digit representation. Like the name suggests, non-zero values cannot be adjacent. For example:
$0\ 1\ 1\ 1)_2 = 4 + 2 + 1 = 7$
$1\ 0\ −1\ 1)_2 = 8 − 2 + 1 = 7$
$1\ −1\ 1\ 1)_2 = 8 − 4 + 2 + 1 = 7$
$1\ 0\ 0\ −1)_2 = 8 − 1 = 7$

All are valid signed-digit representations of 7, but only the final representation, $1\ 0\ 0\ −1)_2$ , is in NAF.

NAF即以一组有符号数字表示，且非零值不可相邻（即每个非零值的左右相邻位必须均为0）。NAF表示的数字，可保证Hamming weight值最小，且相比于普通的二进制表示，其非零值比率可控制在1/3以内。

2. NAF的优势

因以NAF表示的数字相比于以二进制形式表示的数字，其非零值的个数有效减少了（由1/2减为1/3）。非零值个数的减少，将提高某些算法的效率。比如密码学中应用中，可减少exponentiation幂算法中的乘法运算数量（该数量取决于非零值的位数）。
exponentiation幂运算通常表示由基数 $b$ 和指数 $n 组成$ ：
$b^n=b\times b...\times b$

NAF中的1即表示与基数 $b$ 的一次乘积运算，-1表示与基数的倒数 $\frac{1}{b}$ 的乘法运算。

3. 转NAF算法

将普通二进制数字表示转换为NAF表示的算法如下：

 Input     E = (em − 1 em − 2 ··· e1 e0)2Output     Z = (zm zm − 1 ··· z1 z0)NAFi ← 0while E > 0 doif E is odd thenzi ← 2 − (E mod 4)E ← E − zielsezi ← 0E ← E/2i ← i + 1return z

特别的，对于以 $w$ 进制表示的NAF，通称为width-w NAF。具体定义见书《Guide to Elliptic Curve Cryptography》中Definition 3.32：
在这里插入图片描述
具体的算法实现为：

上面算法中2.1步骤中的 $k\ mods\ 2^w$ ，对应的结果区间在 $2^{w-1}, 2^{w-1}-1]$ 。

举例为，下面例子中上面有横杠的数字表示的即为负数：
在这里插入图片描述
观察可发现： $w$ 值越大，NAF中非零值的个数越少。

3. curve25519-dalek中scalar的NAF

以NAF形式表示的位数最多比以二进制形式表示的位数多一位。因此，需保证scalar以二进制表示时，其最高位保持为0值，而相应的NAF表示时，最多只有256位。

针对算法：在这里插入图片描述
上面算法中2.1步骤中的 $k\ mods\ 2^w$ 相当于求 $u$ ，使得 $u\equiv k(mod\ 2^w)$ ， $u$ 对应的结果区间在 $2^{w-1}, 2^{w-1})$ 。

在curve25519-dalek的实际代码实现中，具体的思路为已知 $k=(k_mk_{m-1}...k_{w+1}k_wk_{w-1}...k_1k_0)_2$ ，求相应的 $NAF_w(k)=(n_m....n_1n_0)_w$ ：
1）将k以二进制表示为 $k=(k_mk_{m-1}...k_{w+1}k_wk_{w-1}...k_1k_0)_2=\sum_{i=0}^{w-1}k_i2^i+2^w*\sum_{i=0}k_{i+w}2^i$ ，其中 $\sum_{i=0}^{w-1}k_i2^i\equiv k\ mod\ 2^w$ 。
2）若 $k\ mod\ 2^w$ 为奇数，且 $k\ mod\ 2^w < 2^{w-1}$ 时， $n_0=k\ mod\ 2^w$ ，对于其中的 $k=k-n_0$ 计算，其实即为 $k = k > > w$ 。
3）若 $k\ mod\ 2^w$ 为奇数，且 $k\ mod\ 2^w \ge 2^{w-1}$ 时， $n_0=k\ mod\ 2^w-2^w$ ，对于其中的 $k=k-n_0$ 计算，其实即为 $k=k-n_0=\sum_{i=0}^{w-1}k_i2^i+2^w*\sum_{i=0}k_{i+2}2^i-(k\ mod\ 2^w-2^w)\equiv k\ mod\ 2^w+2^w*\sum_{i=0}k_{i+w}2^i-(k\ mod\ 2^w-2^w)\equiv 2^w+2^w*\sum_{i=0}k_{i+w}2^i$ ，最终可有 $k = k > > w, c a r r y = 1$ 。
4）若 $k\ mod\ 2^w$ 为偶数，则有 $n_0=0$ ， $k = k > > 1$ 。

具体代码实现为：

    pub(crate) fn non_adjacent_form(&self, w: usize) -> [i8; 256] {// required by the NAF definitiondebug_assert!( w >= 2 );// required so that the NAF digits fit in i8debug_assert!( w <= 8 );use byteorder::{ByteOrder, LittleEndian};let mut naf = [0i8; 256];let mut x_u64 = [0u64; 5];LittleEndian::read_u64_into(&self.bytes, &mut x_u64[0..4]);let width = 1 << w;let window_mask = width - 1;let mut pos = 0;let mut carry = 0;while pos < 256 {// Construct a buffer of bits of the scalar, starting at bit `pos`let u64_idx = pos / 64;let bit_idx = pos % 64;let bit_buf: u64;if bit_idx < 64 - w {// This window's bits are contained in a single u64bit_buf = x_u64[u64_idx] >> bit_idx;} else {// Combine the current u64's bits with the bits from the next u64bit_buf = (x_u64[u64_idx] >> bit_idx) | (x_u64[1+u64_idx] << (64 - bit_idx));}// Add the carry into the current windowlet window = carry + (bit_buf & window_mask);if window & 1 == 0 {// If the window value is even, preserve the carry and continue.// Why is the carry preserved?// If carry == 0 and window & 1 == 0, then the next carry should be 0// If carry == 1 and window & 1 == 0, then bit_buf & 1 == 1 so the next carry should be 1pos += 1;continue;}if window < width/2 {carry = 0;naf[pos] = window as i8;} else {carry = 1;naf[pos] = (window as i8).wrapping_sub(width as i8);}pos += w;}naf}

参考资料：
[1] https://en.wikipedia.org/wiki/Non-adjacent_form
[2] 《Guide to Elliptic Curve Cryptography》

这篇关于NAF(Non-adjacent form) w-NAF及其在curve25519-dalek中scalar的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！