密码分析：NTRU签名方案与服务器辅助RSA协议的安全挑战

### 密码分析：NTRU签名方案与服务器辅助RSA协议的攻击与防范 #### 1. NTRU签名方案的伪造示例 在密码学中，签名的安全性至关重要。下面我们来看一个利用公钥伪造NTRU签名方案（NSS）签名的示例。 - **参数设定**：设定参数遵循NSS251 - 3 - SHA1 - 1的定义，具体参数为 \(N = 251\)，\(p = 3\)，\(q = 128\)，\(V_m = 32\)，\(Devi_{min} = 55\)，\(Devi_{max} = 87\)，\(f_0 = 1\)，\(g_0 = 1 - 2X\)。公钥 \(h = f^{-1} * g \pmod{q}\) 如下： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 1 | 21 | -59 | -54 | 1 | -33 | -13 | -11 | -21 | 11 | -30 | 31 | -7 | 18 | -61 | 85 | | 1 | 3 | 41 | 52 | -39 | -30 | 4 | -36 | 41 | -11 | 56 | 46 | -7 | -7 | 7 | -8 | 16 | | 2 | -58 | -5 | 32 | -3 | -29 | 59 | 54 | -25 | 53 | 48 | 47 | 32 | -5 | 28 | -9 | -9 | | 3 | 37 | 24 | -50 | 17 | -26 | -58 | 10 | 39 | 4 | -23 | -55 | -63 | -29 | -19 | 0 | 31 | | 4 | 10 | 16 | -25 | 28 | 29 | -62 | 24 | 27 | 57 | 31 | 62 | -61 | 35 | 39 | -27 | 5 | | 5 | 17 | -22 | 22 | 28 | 32 | 41 | 14 | -62 | -18 | -58 | 15 | 61 | 25 | 9 | 63 | -9 | | 6 | 47 | 30 | 0 | 58 | 58 | -60 | 13 | 55 | 4 | 9 | -62 | 11 | 58 | -34 | -39 | 13 | | 7 | 40 | 27 | 36 | -15 | 24 | -31 | 37 | 23 | 31 | 55 | -12 | -20 | 43 | -61 | 1 | 27 | | 8 | -44 | -10 | 11 | 58 | -63 | -51 | -46 | -21 | -6 | -28 | -17 | -58 | -28 | 6 | 21 | -58 | | 9 | 58 | -3 | 10 | -8 | -26 | 48 | 12 | 64 | 2 | 14 | -55 | -20 | -33 | -24 | -40 | 6 | | a | -13 | 42 | 56 | -23 | -63 | 26 | -52 | -29 | -4 | 35 | 12 | -19 | -24 | 47 | -21 | 60 | | b | -15 | -17 | 63 | 62 | 55 | 17 | -61 | 5 | 30 | 24 | -32 | -44 | 17 | 29 | -63 | 57 | | c | 60 | -25 | -47 | -51 | 2 | 11 | -35 | -44 | -15 | -5 | 7 | -9 | 43 | 36 | -18 | -60 | | d | -53 | -2 | -44 | 33 | -27 | -35 | -17 | 5 | -17 | 14 | 0 | 2 | -6 | 49 | 29 | -48 | | e | -31 | 64 | -8 | 64 | -46 | 12 | 36 | -57 | 23 | -9 | 39 | 45 | 19 | 54 | -21 | 49 | | f | -7 | -43 | 40 | 60 | -45 | 20 | -50 | 5 | 54 | -13 | -45 | 待签名的消息如下： | | 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f | | --- | --- | | 0 | 0 0 0 0 0 0 0 0 1 0 0 0 - 0 0 1 0 0 0 0 0 0 0 - 1 1 0 0 0 0 - - | | 2 | 0 0 0 0 0 0 0 - 0 0 0 1 0 1 0 0 0 0 0 0 - 0 0 0 0 1 0 - - 0 0 - | | 4 | 0 0 0 - - - 0 0 - 0 0 0 0 1 0 0 0 0 - - 1 0 1 0 0 0 0 0 1 0 0 0 | | 6 | 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 - 1 0 0 0 0 - 0 0 0 1 0 0 - 0 0 0 | | 8 | 0 0 1 0 - 0 0 - 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 - 0 | | a | 0 0 1 - - 0 0 0 0 0 0 - - - 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 - 0 0 | | c | 0 0 0 0 0 - 0 0 0 0 0 0 0 0 1 1 0 1 - 0 - 0 0 0 - 0 0 1 0 0 0 0 | | e | 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - 0 0 0 1 0 0 0 0 0 1 | - **初始签名的寻找**：通过对 \(s\) 和 \(t\) 施加 \(k = 95\) 个约束条件来寻找初始签名 \((s'', t'')\)。为了清晰起见，在这个例子中，我们对 \(s''\) 的前 95 个系数和 \(t''\) 的后 95 个系数施加这些约束。从众多可能的 \((s'', t'')\) 中，我们可以得到 \(s''\) 和 \(t''\) 的值。 - \(s''\) 的值如下： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | -1 | | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | | 3 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | -1 | -1 | 0 | 0 | -1 | | 4 | 0 | 0 | 0 | -1 | -1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | | 5 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 56 | 0 | | 6 | -2 | 38 | 32 | -41 | -32 | 38 | -4 | -21 | -4 | 8 | -47 | -57 | -40 | 27 | 3 | 39 | | 7 | -44 | 14 | 33 | 52 | -5 | 34 | 57 | 4 | 16 | -4 | -45 | -18 | -23 | -58 | -22 | 6 | | 8 | 56 | 59 | 5 | -57 | -33 | -55 | 19 | -41 | 52 | 26 | 50 | -54 | 2 | 57 | -27 | -30 | | 9 | 47 | 9 | 36 | -42 | -17 | -50 | -7 | -44 | -55 | -47 | -30 | -45 | -39 | 34 | 36 | 7 | | a | -32 | -19 | 4 | 23 | -43 | -40 | -3 | 59 | 22 | -52 | 46 | 42 | 24 | -12 | -19 | 7 | | b | 24 | -43 | 64 | -41 | 54 | -31 | -13 | -31 | -49 | -55 | 57 | -54 | -56 | -60 | -48 | -20 | | c | -36 | 26 | 4 | 18 | 16 | -61 | 33 | 45 | -16 | 53 | 59 | 64 | -60 | -13 | 35 | -47 | | d | -23 | 50 | 45 | 44 | -52 | 53 | 49 | -29 | -52 | 35 | 54 | 53 | -15 | 50 | -18 | 26 | | e | -7 | -1 | 30 | -50 | -17 | -14 | -54 | 31 | -59 | 35 | -21 | -44 | -14 | 62 | -15 | -5 | | f | 36 | 27 | -6 | 6 | 36 | 29 | -12 | 1 | 58 | 19 | 21 | - \(t''\) 的值如下： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 25 | -30 | 15 | 62 | 49 | -24 | -24 | -12 | 15 | -17 | 33 | 24 | -61 | 64 | -16 | -57 | | 1 | -31 | 18 | 23 | -29 | 27 | 39 | -20 | -35 | -13 | 2 | -54 | 39 | 36 | -33 | 16 | -13 | | 2 | -20 | -45 | -20 | -3 | 25 | 10 | 54 | -37 | -33 | 41 | -41 | -47 | -31 | -15 | 31 | -14 | | 3 | -52 | 16 | -45 | -10 | -56 | -22 | -42 | 52 | 8 | -20 | 55 | 13 | 30 | 32 | -28 | 41 | | 4 | -57 | 25 | 49 | -14 | 52 | -38 | -41 | -35 | 22 | -36 | -27 | -13 | 36 | 35 | 45 | -10 | | 5 | 54 | -31 | -9 | 3 | -57 | -37 | 9 | -9 | -16 | -60 | -59 | 14 | 18 | 26 | -45 | 25 | | 6 | 12 | -40 | 11 | 31 | 41 | 5 | -37 | 9 | 12 | -21 | -45 | 4 | 42 | -18 | -2 | -29 | | 7 | -52 | 4 | 19 | 54 | 57 | 52 | -23 | -34 | -31 | -63 | -60 | -51 | -14 | 42 | 2 | 13 | | 8 | 56 | -16 | 30 | 44 | 14 | -37 | -8 | 51 | 33 | 26 | 9 | -12 | -62 | 47 | 14 | 3 | | 9 | -50 | 18 | -10 | -33 | 24 | -48 | -4 | 60 | -50 | 26 | 60 | 26 | 0 | 0 | -1 | -1 | | a | 0 | 0 | 1 | 0 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | -1 | 0 | | b | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | -1 | 1 | -1 | -1 | 0 | | c | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | | d | 1 | 1 | 0 | -1 | -1 | -1 | 0 | 0 | -1 | -1 | 0 | 1 | 1 | 0 | 0 | 0 | | e | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | f | 0 | -1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 此时，\(s''\) 和 \(t''\) 与 \((f_0 * m)\) 和 \((g_0 * m)\) 的偏差模式如下（每个星号表示一个偏差）： - \(s''\) 的偏差模式： ``` ................................................................ ..............................*.*******.**..*.**.*.***.***..***. ***.*******.*...**..******...*****...*.*********.***.*********.* .**.*...****.**.****.***.*.*.*.***.***.***.***..*...**.**** ``` - \(t''\) 的偏差模式： ``` ...**...*....****.**..***.*...***.*.**..***.**.***.**..**..**.*. ****..****.*.***.***.****.****.*.******.***....**.*..******.**** ****..****..***.***...*.**.*.................................... ........................................................... ``` 此时，\(s''\) 和 \(t''\) 分别有 108 和 98 个偏差。 - **格基规约处理**：对 \(s''\) 的第 95 到 169 个系数位置和 \(t''\) 的第 81 到 155 个系数位置应用格基规约（即 \(s\) 中最左边的 75 个未约束系数和 \(t\) 中最右边的 75 个未约束系数，总共 150 列）。得到 \(s\) 和 \(t\) 的值如下： - \(s\) 的值： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | -4 | 0 | 0 | 4 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -4 | 4 | 4 | 0 | 0 | 0 | 0 | -4 | -4 | | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -4 | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | | 3 | 0 | 0 | 0 | 0 | -4 | 0 | 0 | 0 | 0 | 4 | 0 | -4 | -4 | 0 | 0 | -4 | | 4 | 0 | 0 | 0 | -4 | -4 | -4 | 0 | 0 | -4 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | | 5 | 0 | 0 | -4 | -4 | 4 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | -30 | 0 | | 6 | 9 | -26 | 21 | -54 | 39 | 33 | 21 | -6 | -47 | 9 | 43 | -42 | 12 | 33 | -50 | -49 | | 7 | 13 | -24 | 3 | 6 | -63 | -19 | 12 | 33 | 6 | 7 | -30 | -36 | -28 | -12 | -12 | 0 | | 8 | 9 | 57 | 28 | 24 | -52 | 12 | 18 | 20 | 6 | -33 | 15 | 51 | 9 | -33 | -3 | -9 | | 9 | -30 | -17 | -27 | -21 | 6 | 9 | -27 | 0 | -36 | -18 | -42 | -9 | 57 | 3 | 38 | 36 | | a | 36 | -18 | -47 | 35 | 47 | -15 | 27 | 63 | 3 | -12 | -30 | -22 | -56 | -40 | 10 | 57 | | b | -49 | -16 | 58 | 20 | -53 | -26 | -19 | 29 | -46 | 51 | 0 | -49 | -36 | -29 | 15 | -47 | | c | -42 | 12 | -52 | 51 | 40 | 47 | 42 | -30 | 51 | -53 | -11 | 6 | -39 | 51 | 13 | -9 | | d | -40 | -51 | -29 | 26 | -32 | 44 | 3 | 27 | -35 | -9 | 55 | -58 | -60 | 0 | -62 | -17 | | e | 51 | -26 | 30 | -43 | -50 | 7 | -10 | -8 | -29 | 5 | 36 | 18 | -30 | -46 | -21 | 42 | | f | 61 | 25 | 39 | 56 | 5 | 27 | 56 | 29 | 51 | 19 | 59 | - \(t\) 的值： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | -37 | 41 | -52 | 21 | 57 | -57 | -56 | -63 | -53 | -2 | 5 | 40 | -38 | 57 | -62 | 18 | | 1 | 7 | 57 | -61 | -32 | 18 | -6 | 32 | 33 | 37 | -30 | 36 | 62 | -27 | -15 | 54 | -4 | | 2 | -34 | -31 | -51 | 24 | -25 | -8 | 62 | 57 | 38 | 28 | -1 | 25 | -50 | -63 | -63 | -12 | | 3 | 18 | -10 | -6 | 2 | -39 | -29 | 54 | -13 | -62 | 55 | 34 | -35 | -28 | -60 | -26 | 39 | | 4 | -2 | -17 | -44 | -53 | -38 | -63 | 1 | -19 | -54 | 52 | 53 | -61 | 50 | 10 | -36 | 33 | | 5 | -27 | -21 | 53 | 19 | 3 | 40 | 25 | 31 | -33 | -12 | -54 | -27 | 58 | 4 | 36 | -15 | | 6 | 21 | -20 | -5 | -48 | 36 | 21 | -30 | 42 | 4 | -5 | 16 | -56 | 0 | -33 | -41 | -21 | | 7 | -39 | 1 | 30 | 18 | -6 | 11 | -43 | 6 | -27 | 64 | 4 | -6 | -10 | 2 | 59 | -3 | | 8 | 30 | -6 | -8 | -20 | -31 | 20 | 3 | 17 | -43 | -15 | -6 | -15 | 15 | -9 | 30 | -3 | | 9 | -36 | 52 | 19 | -3 | -12 | -9 | -48 | -48 | 27 | -18 | 12 | 15 | 0 | 0 | -4 | -4 | | a | 0 | 0 | 4 | 0 | 4 | -4 | 0 | 0 | 0 | 0 | 0 | -4 | 4 | 4 | -4 | 0 | | b | 0 | 4 | 4 | 0 | 0 | 4 | 4 | 0 | 0 | 0 | 4 | -4 | 4 | -4 | -4 | 0 | | c | 0 | 0 | 0 | 0 | 0 | -4 | -4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | -4 | | d | 4 | 4 | 0 | -4 | -4 | -4 | 0 | 0 | -4 | -4 | 0 | 4 | 4 | 0 | 0 | 0 | | e | 0 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | | f | 0 | -4 | 0 | 0 | 4 | 4 | 0 | 0 | 0 | 0 | 4 | \(s\) 和 \(t\) 的偏差模式如下： - \(s\) 的偏差模式： ``` ................................................................ ................................................................ ............................................*.*.*****.***.**.*.* ..*.*....**....*******..*.**..**...*******...*.***.**.**.** ``` - \(t\) 的偏差模式： ``` ***...*...******..**..******..**.*..****.**..**..*.***.**..***** ****.********.*...............................................*. ................................................................ ........................................................... ``` 这样，我们得到的 \(s\) 和 \(t\) 与 \((f_0 * m)\) 和 \((g_0 * m)\) 分别有 47 和 54 个偏差。这些值甚至低于建议的参数值 \(Devi_{min} = 55\)，这表明我们的伪造签名可以通过更严格的偏差要求。不过，这个例子中的 \(s\) 和 \(t\) 的系数分布在模 \(q\) 下非常不寻常，验证者可以很容易地检测到，但一般情况下并非如此。我们可以通过以下两种方法使 \(s\) 和 \(t\) 的系数分布更正常： 1. 约束随机系数位置。 2. 模 \(q\) 下更随机地分布 \(s''\) 和 \(t''\) 的约束系数的值，而不是将它们都设为 -1、0 或 1。 #### 2. \(w_1\) 和 \(w_2\) 的确定 以下是确定 \(w_1\) 和 \(w_2\) 的伪代码： ```python # 初始化 w2，使其有 32 个 +1 和 32 个 -1 let w2 have 32 +1’s and 32 -1’s # 初始化 w1 数组为 0 set w1[] to 0 # 计算 s = f * (mes + 3 w2) compute s = f * (mes + 3 w2) # 计算 t = g * (mes + 3 w2) compute t = g * (mes + 3 w2) # 对 s 和 t 进行模 q 约简 reduce s and t modulo q # 对 s 和 t 进行模 p 约简 reduce s and t modulo p # 创建 w1，第一次尝试 for(i=0;i<N;i++) if(s[i] != mes[i] AND t[i] != mes[i] AND s[i] == t[i]) w1[i] = (mes[i] - s[i]) mod p if(s[i] != mes[i] AND t[i] != mes[i] AND s[i] != t[i]) w1[i] = 1 or -1 with 50% probability loop # 创建 w1，第二次尝试 for(i=0;i<N;i++) if(s[i] != mes[i] AND t[i] == mes[i]) w1[i] = (mes[i] - s[i]) mod p with 1/4 probability if(s[i] == mes[i] AND t[i] != mes[i]) w1[i] = (mes[i] - t[i]) mod p with 1/4 probability if(w1 has more than 25 nonzero coefficients) break out of the loop loop # 修改 w2 以防止平均攻击 for(i=0;i<N;i++) with probability 1/p, w2[i] = w2[i] - (mes[i] + w1[i]) w = w1 + 3 w2 ``` #### 3. 服务器辅助RSA协议的背景 在当今的密码学应用中，芯片卡或智能卡等小型设备在数据计算、存储和保护方面发挥着重要作用。然而，大部分廉价卡片的计算能力有限，难以完成公钥密码系统所需的复杂操作。为了解决这个问题，“服务器辅助秘密计算”（SASC）协议应运而生。在SASC协议中，客户端（智能卡）可以借助不可信的强大服务器的计算能力来执行秘密计算，同时不泄露自身的秘密信息。 ##### 3.1 RSA - S1服务器辅助协议 RSA - S1协议是一种用于计算RSA签名 \(x^d \pmod{N}\) 的服务器辅助协议，其具体步骤如下： 1. 智能卡随机选择一个向量 \(f = (f_1, \ldots, f_m) \in B_{k, \ell, m}\)，其中 \(B_{k, \ell, m}\) 是满足特定条件的向量集合，要求 \(\gcd(f_1, \ldots, f_m, \phi(N)) = 1\) 且 \(\sum_{i = 1}^{m} wt(f_i) = k\)，\(wt(f)\) 表示整数 \(f\) 的汉明重量（即二进制数字之和）。 2. 智能卡随机选择一个向量 \(d = (d_1, \ldots, d_m) \in [\phi(N)]^m\)，使得 \(\sum_{i = 1}^{m} f_id_i \equiv d \pmod{\phi(N)}\)。如果无法满足该条件，则返回步骤1重新选择。 3. 智能卡请求服务器计算并返回 \(z_i \equiv x^{d_i} \pmod{N}\)，其中 \(i = 1, \ldots, m\)。 4. 智能卡计算 \(x^d \equiv \prod_{i = 1}^{m} z_i^{f_i} \pmod{N}\)。 由于内存限制，智能卡在步骤4主要有两种计算方式： - **平方 - 乘法方法**：最多需要 \(k\ell\) 次模乘法，所需内存较少。 - **另一种算法**：可以高效计算 \(\prod_{i = 1}^{m} z_i^{f_i} \pmod{N}\)，但需要更多内存。使用该算法时，可以优化参数选择，将 \(f_i \in [2^{\ell}]\) 替换为 \(f_i \in [h]\)（\(h\) 为小整数），此时算法最多需要 \(m + h - 3\) 次模乘法，并需要临时存储 \(m\) 或 \(h - 1\) 个元素。 该协议需要传输大约 \(2m \log N\) 位的数据，由于廉价智能卡的带宽通常为 9600 波特，因此 \(m\) 的值必须限制在较低水平。例如，对于 1024 位的模数，\(m = 50\) 时传输数据就需要 10.7 秒。 ##### 3.2 RSA - S1的被动攻击 一旦 \(f_i\) 被泄露，RSA - S1协议就会被破解。因为 \(\sum_{i = 1}^{m} f_id_i\) 与RSA私钥 \(d\) 模 \(\phi(N)\) 同余，从而可以对任何消息进行签名，并且可以通过公钥 \(e\) 进行验证。此外，还可以从 \(e\sum_{i = 1}^{m} f_id_i - 1\) （它是 \(\phi(N)\) 的非零倍数）在随机多项式时间内恢复 \(N\) 的因式分解。 最初，协议设计者认为唯一可能的被动攻击是对 \(f_i\) 进行穷举搜索，其复杂度约为 \(C = \binom{m\ell}{k}\)。但实际上，可以设计出更高效的中间相遇被动攻击。Pfitzmarmann和Waidner提出的一种攻击，将 \((f_1, \ldots, f_m)\) 拆分为 \((g_1, \ldots, g_m) + (h_1, \ldots, h_m)\)，使得 \(\sum wt(g_i) \leq \sum wt(h_i) = \lceil k/2 \rceil\)，攻击的时间和空间复杂度约为 \(\binom{m\ell}{\lceil k/2 \rceil}\)。通过Coppersmith的技巧，还可以进一步将复杂度提高到约 \(\sqrt{k} \binom{\lceil m\ell/2 \rceil}{\lceil k/2 \rceil}\)，大致为穷举搜索复杂度的平方根。 Merkle和Werchner证明了在通用模型下，任何一轮被动通用攻击RSA - S1的复杂度至少为 \(\Omega(\sqrt{C})\)。 ##### 3.3 格的基本概念 本攻击方法基于格基规约，这是公钥密码分析中常用的工具。下面简要介绍格的基本概念： - **格的定义**：格是 \((\mathbb{Z}^n, +)\) 的任何子群，对于一组向量 \(b_1, \ldots, b_d \in \mathbb{Z}^n\)，由它们张成的格 \(L(b_1, \ldots, b_d)\) 是所有整数线性组合 \(\sum_{i = 1}^{d} n_ib_i\)（\(n_i \in \mathbb{Z}\)）的集合。 - **格的基**：格 \(L\) 的基是一组线性无关的向量 \(b_1, \ldots, b_d\)，使得 \(L = L(b_1, \ldots, b_d)\)。格的所有基具有相同的元素个数（称为格的秩或维数）和相同的 \(d\) 维体积（称为格的体积或行列式）。 - **最短向量问题（SVP）**：给定格 \(L\) 的一个基，找到一个非零向量 \(v \in L\)，使得其欧几里得范数 \(\|v\|\) 最小。已知最短格向量的欧几里得范数总是小于 \(\sqrt{d} \text{vol}(L)^{1/d}\)，但目前普遍认为不存在多项式时间算法来解决SVP问题。不过，存在一些多项式时间算法可以近似求解SVP，如Schnorr算法。 下面是RSA - S1协议的流程图： ```mermaid graph TD; A[选择向量 f] --> B[选择向量 d]; B -->|不满足条件| A; B -->|满足条件| C[请求服务器计算 zi]; C --> D[计算 x^d]; ``` 综上所述，NTRU签名方案存在签名伪造的风险，而RSA - S1服务器辅助协议也面临多种攻击威胁。在密码学应用中，我们需要不断研究和改进这些协议，以提高其安全性。同时，对于格基规约等工具的应用也需要深入研究，以更好地应对各种攻击。在后续内容中，我们将继续探讨针对RSA - S1协议的新攻击方法以及相关分析。 #### 4. 对RSA - S1协议的攻击分析 ##### 4.1 Merkle攻击的分析 Merkle去年在ACM CCS ’00上提出了一种基于格的多轮被动攻击，该攻击在实践中对许多参数选择都取得了成功。他的论文对攻击进行了分析，其灵感来源于解决子集和问题的著名格基方法，但分析存在一定的技术问题，假设的参数分布与协议实际诱导的分布不一致。 我们对Merkle攻击的一个轻微变体进行了简单分析，该分析能够解释实验结果，并为某些参数选择提供可证明的结果。具体来说，我们考虑的攻击变体在基本原理上与Merkle的攻击相似，但在一些细节上进行了调整，以更好地适应协议的实际参数分布。 通过对攻击过程的详细分析，我们发现该攻击利用了协议中向量 \(f\) 和 \(d\) 的选择特性，以及格基规约算法的性质。在多轮攻击中，攻击者收集多个签名过程中的信息，构建一个格，并通过格基规约算法寻找格中的短向量，从而尝试恢复出 \(f_i\) 的值。 以下是Merkle攻击变体的大致步骤： 1. **多轮信息收集**：攻击者在多轮协议执行过程中，收集服务器返回的 \(z_i\) 值以及相关的签名信息。 2. **构建格**：根据收集到的信息，构建一个合适的格，使得 \(f_i\) 的值与格中的向量存在某种关联。 3. **格基规约**：使用格基规约算法（如Schnorr算法）对构建的格进行规约，寻找格中的短向量。 4. **恢复 \(f_i\) 值**：通过分析规约后的格向量，尝试恢复出 \(f_i\) 的值。 通过这种分析，我们能够更好地理解攻击的原理和效果，为评估协议的安全性提供了更准确的依据。 ##### 4.2 新的基于格的被动攻击 本文的主要贡献是提出了一种新的基于格的被动攻击，该攻击仅在使用非常小的公钥指数 \(e\) 时有效。与Merkle的多轮攻击不同，这种新攻击是单轮攻击，即只需要协议的一次执行就足够了。 当使用非常小的公钥指数 \(e\) 时，协议中的签名验证步骤（即检查 \((x^d)^e \pmod{N}\) 是否等于 \(x\)）变得可行，但也为攻击者创造了机会。攻击者可以利用这个条件，结合格基规约算法，尝试恢复RSA私钥 \(d\)。 新攻击的具体步骤如下： 1. **单轮信息收集**：攻击者在协议的一次执行过程中，收集服务器返回的 \(z_i\) 值以及相关的签名信息。 2. **构建格**：根据收集到的信息和公钥指数 \(e\) 的特性，构建一个特定的格。 3. **格基规约**：使用格基规约算法对构建的格进行规约，寻找格中的短向量。 4. **恢复私钥 \(d\)**：通过分析规约后的格向量，尝试恢复出RSA私钥 \(d\)。 由于该攻击是单轮攻击，所以之前提出的更新私钥分解的对策（即每次签名时更新 \(f\) 和 \(d\) 的选择）对其无效。这表明在设计协议的安全对策时，需要综合考虑各种攻击场景，避免出现新的安全漏洞。 有趣的是，Merkle和Werchner在PKC ’98上证明了RSA - S1协议在通用模型下对单轮被动攻击是安全的，但我们的新攻击表明，这种安全证明在实际应用中可能存在局限性。这也提醒我们，在评估协议的安全性时，不能仅仅依赖于通用模型的证明，还需要考虑实际的攻击场景和参数选择。 以下是新攻击的流程图： ```mermaid graph TD; A[单轮信息收集] --> B[构建格]; B --> C[格基规约]; C --> D[恢复私钥 d]; ``` #### 5. 攻击对协议安全性的影响及对策探讨 ##### 5.1 攻击对协议安全性的影响 我们提出的新攻击和对Merkle攻击的分析表明，RSA - S1服务器辅助协议面临着严重的安全威胁。新的单轮被动攻击能够在使用非常小的公钥指数时恢复私钥，而Merkle的多轮被动攻击在许多参数选择下也能成功。 这些攻击的存在使得协议的原有安全假设受到质疑，特别是在实际应用中，当参数选择不合理时，协议可能会被轻易破解。例如，如果公钥指数 \(e\) 选择过小，就会触发新的单轮被动攻击；而如果不恰当的更新私钥分解，就会给Merkle攻击创造机会。 此外，这些攻击结果也对通用模型下的安全证明提出了挑战。虽然Merkle和Werchner证明了协议在通用模型下对单轮被动攻击是安全的，但我们的实际攻击表明，通用模型可能无法准确反映协议在实际环境中的安全性。 ##### 5.2 对策探讨 为了提高RSA - S1协议的安全性，我们需要重新审视之前提出的对策，并考虑新的解决方案。 - **公钥指数选择**：公钥指数 \(e\) 的选择需要谨慎。如果选择过小，会引发新的单轮被动攻击；但如果选择过大，签名验证步骤会变得不可行。因此，需要在安全性和计算效率之间找到一个平衡点。 - **私钥分解更新**：更新私钥分解的对策在一定程度上可以防止某些攻击，但也会引发新的问题，如Merkle的多轮被动攻击。因此，需要设计更合理的私钥分解更新策略，例如结合其他加密技术或随机化方法，增加攻击者获取有用信息的难度。 - **签名验证改进**：签名验证是协议中的重要环节，但目前的验证方法存在一定的局限性。可以考虑引入更复杂的验证机制，如多因素验证或零知识证明，以提高验证的安全性。 以下是不同对策的对比表格： | 对策 | 优点 | 缺点 | | --- | --- | --- | | 合理选择公钥指数 | 平衡安全性和计算效率 | 需要精确的参数选择，难以确定最佳值 | | 改进私钥分解更新策略 | 增加攻击者获取信息的难度 | 实现复杂度较高，可能影响协议效率 | | 引入复杂验证机制 | 提高验证的安全性 | 增加计算和通信开销 | #### 6. 总结 本文深入研究了NTRU签名方案和RSA - S1服务器辅助协议的安全性。在NTRU签名方案中，我们展示了如何利用公钥伪造签名，并通过格基规约技术降低伪造签名的偏差，使其能够通过更严格的验证。同时，我们还给出了确定 \(w_1\) 和 \(w_2\) 的伪代码，为相关研究提供了参考。 对于RSA - S1服务器辅助协议，我们分析了现有的被动攻击，包括Merkle的多轮被动攻击和我们提出的新的单轮被动攻击。这些攻击表明，协议在安全性方面存在严重的漏洞，特别是在参数选择不合理的情况下。我们对Merkle攻击的变体进行了简单分析，为攻击的有效性提供了理论支持，并指出了通用模型下安全证明的局限性。 为了提高协议的安全性，我们探讨了多种对策，包括合理选择公钥指数、改进私钥分解更新策略和引入复杂验证机制。在实际应用中，需要综合考虑这些对策，根据具体的应用场景和安全需求，选择最合适的安全方案。 总之，密码学协议的安全性是一个复杂的问题，需要不断地研究和改进。我们的研究为NTRU签名方案和RSA - S1协议的安全分析和改进提供了有价值的参考，希望能够引起更多研究者的关注，共同推动密码学领域的发展。