密码学算法 - Tonelli-Shanks 算法

当你在椭圆曲线上进行加密操作时需要计算某个点的平方根但又发现这个点在有限域中没有平方根时别担心这时候 Tonelli-Shanks 算法 就像一把灵巧的钥匙能帮你在无解的荒漠中精准定位那唯一的坐标点。欢迎来到《密码学核心算法实战》的 Tonelli-Shanks 专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。Tonelli-Shanks算法 Tonelli-Shanks 算法用于求解形如x 2 ≡ a ( m o d p ) x^2 \equiv a \pmod{p}x2≡a(modp)的同余方程其中 $ p $ 是奇素数$ a $ 是模 $ p $ 下的平方数。Tonelli-Shanks算法的操作 输入一个整数 $ a $ 和一个奇素数 $ p $满足 $ a $ 是模 $ p $ 下的平方数。则 $ (\frac{a}{p}) 1 $。输出一个整数 $ x $满足 $ x^2 \equiv a \pmod{p} $。算法步骤将 $ p-1 $ 分解为 $ Q \cdot 2^s $其中 $ Q $ 是奇数。如果s 1 s 1s1即 $ p \equiv 3 \pmod{4} $则直接计算 $ x \equiv \pm a^{\frac{p1}{4}} \pmod{p} $找到一个非平方数 $ z $即满足 $ (\frac{z}{p}) -1 $ 的整数令 $ c \equiv z^Q \pmod{p} $。令 $ x \equiv a^{\frac{Q1}{2}} \pmod{p} t \equiv a^Q \pmod{p} m s $。循环如果 $ t \equiv 1 \pmod{p} $则返回 $ x $。否则找一个最小的 $ i $使得 $ t{2i} \equiv 1 \pmod{p} $重复平方。令 $ b \equiv c{2{m-i-1}} \pmod{p} $更新 $ x \equiv x \cdot b \pmod{p} t \equiv t \cdot b^2 \pmod{p} c \equiv b^2 \pmod{p} m i $。如果x xx是一个解那么第二个解为p − x p - xp−x。Tonelli-Shanks算法的原理 已知p − 1 Q ⋅ 2 s r ≡ a Q 1 2 ( m o d p ) t ≡ a Q ( m o d p ) \begin{align*} p - 1 Q \cdot 2^s \\ r \equiv a^{\frac{Q1}{2}} \pmod{p} \\ t \equiv a^Q \pmod{p} \end{align*}p−1Q⋅2sr≡a2Q1​(modp)t≡aQ(modp)​所以r 2 ≡ a t ( m o d p ) r^2 \equiv at \pmod{p}r2≡at(modp)对于每次迭代都为真。如果t ≡ 1 ( m o d p ) t \equiv 1 \pmod{p}t≡1(modp)则r 2 ≡ a ( m o d p ) r^2 \equiv a \pmod{p}r2≡a(modp)并且x ≡ ± r ( m o d p ) x \equiv \pm r \pmod{p}x≡±r(modp)算法结束。如果t ≢ 1 ( m o d p ) t \not\equiv 1 \pmod{p}t≡1(modp)那么认为z zz为模p pp的平方非剩余。令c ≡ z Q ( m o d p ) c \equiv z^Q \pmod{p}c≡zQ(modp)那么c 2 s ≡ z Q ⋅ 2 s ≡ z p − 1 ≡ 1 ( m o d p ) c^{2^s} \equiv z^{Q \cdot 2^s} \equiv z^{p-1} \equiv 1 \pmod{p}c2s≡zQ⋅2s≡zp−1≡1(modp)并且c 2 s − 1 ≡ z Q ⋅ 2 s − 1 ≡ z p − 1 2 ≡ − 1 ( m o d p ) c^{2^{s-1}} \equiv z^{Q \cdot 2^{s-1}} \equiv z^{\frac{p-1}{2}} \equiv -1 \pmod{p}c2s−1≡zQ⋅2s−1≡z2p−1​≡−1(modp)所以c cc的乘法阶为2 s 2^s2s。同理有t 2 s ≡ 1 ( m o d p ) t^{2^s} \equiv 1 \pmod{p}t2s≡1(modp)所以t tt的乘法阶整除2 s 2^s2s。假设t tt的乘法阶为2 s ∗ 2^{s^*}2s∗由于a aa是模p pp的平方剩余所以t ≡ a Q ≡ 1 ( m o d p ) t \equiv a^Q \equiv 1 \pmod{p}t≡aQ≡1(modp)也是一个平方所以s ∗ s − 1 s^* s - 1s∗s−1。之后令b ≡ c 2 s − s ∗ − 1 ( m o d p ) r ∗ ≡ r ⋅ b ( m o d p ) c ∗ ≡ b 2 ( m o d p ) t ∗ ≡ t ⋅ c ∗ ( m o d p ) \begin{align*}b \equiv c^{2^{s - s^* - 1}} \pmod{p} \\ r^* \equiv r \cdot b \pmod{p} \\ c^* \equiv b^2 \pmod{p} \\ t^* \equiv t \cdot c^* \pmod{p} \end{align*}b≡c2s−s∗−1(modp)r∗≡r⋅b(modp)c∗≡b2(modp)t∗≡t⋅c∗(modp)​和上述一致有( r ∗ ) 2 ≡ a t ∗ ( m o d p ) (r^*)^2 \equiv a t^* \pmod{p}(r∗)2≡at∗(modp)成立。然而t tt和c ∗ c^*c∗的阶都是2 s ∗ 2^{s^*}2s∗所以t ∗ t^*t∗的阶数为2 s ∗ ∗ 2^{s^**}2s∗∗满足s ∗ ∗ s ∗ s^** s^*s∗∗s∗。如果s ∗ ∗ 0 s^** 0s∗∗0则t ∗ ≡ 1 ( m o d p ) t^* \equiv 1 \pmod{p}t∗≡1(modp)并且x ≡ ± r ∗ ( m o d p ) x \equiv \pm r^* \pmod{p}x≡±r∗(modp)算法结束。否则用r ∗ r^*r∗、t ∗ t^*t∗和c ∗ c^*c∗替换r rr、t tt和c cc继续迭代重新开始循环直到s ∗ … ∗ s^{* \ldots *}s∗…∗。因此一系列的s ss是属于严格减少的算法一定会终止。Tonelli-Shanks算法的实现 看懂了吗下面是 Tonelli-Shanks 算法的一个简单实现deftonelli_shanks(n,p):ifn0:return0ifpow(n,(p-1)//2,p)!1:# 如果 n 不是模 p 的平方剩余则没有解print(No square root exists)returnNoneifp%43:# 如果 p ≡ 3 (mod 4)直接计算平方根returnpow(n,(p1)//4,p)qp-1# 将 p-1 分解为 Q * 2^ss0whileq%20:s1q//2# 找到一个非平方数 zz2whilepow(z,(p-1)//2,p)!p-1:z1cpow(z,q,p)xpow(n,(q1)//2,p)tpow(n,q,p)ms# 开始迭代whilet!1:i1t2pow(t,2,p)whilet2!1:t2pow(t2,2,p)i1bpow(c,1(m-i-1),p)# c^(2^(m-i-1))x(x*b)%p t(t*b*b)%p c(b*b)%p mireturnx,p-xSageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimportsolve_mod,var# sage环境中才生效# solve_mod 中已经有 Tonelli-Shanks 算法的实现了直接用就好xvar(x)# 一定要记得定义变量不然会报错的哦mod7fx**2-4rsolve_mod(f,mod)怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋