密码学学习笔记：浅析On r-th Root Extraction Algorithm in Fq

 

前言：

在NCTF上遇到了一道出题人用来压轴的RSA，与正常RSA加密不同的是，本题的e是φ(p)和φ(q)的一个因子。在出题人给出hint后，我找到了一篇paper，侥幸用paper中提到的算法拿到了一血~

该算法可以在有限域Fq中开r次根，但需要s，满足r^s整除q-1，即r^s | q-1，并且s要小。

 

On r-th Root Extraction Algorithm in Fq

paper： https://eprint.iacr.org/2013/117.pdf

引言：

我们让r为一个大于1的整数，那么有现存的两种算法用来在有限域Fq中开r^s次根， the Adleman-Manders-Miller algorithm 和 the Cipolla-Lehmer algorithms

假设r<<log q ，由于 the Adleman-Manders-Miller algorithm 要求s满足 r^s | q-1 并且 r^(s+1) 不能整除 q-1，所以它的时间复杂度O(logrlog4 q) 比 the Cipolla-Lehmer algorithms 的时间复杂度O(rlog3 q) 要高。但是，由于Cipolla Lehmer需要繁琐的扩展字段算法，当s比较小时，the Adleman-Manders-Miller algorithm 要比之更为有效。

另一方面，在某些情况下还存在比 Tonelli-Shanks 计算更快的其他方法来做开方运算。例子就是当 q ≡ 3 (mod 4).

当c时Fq中的二次剩余时，c的其中一个根就是，利用欧拓很容易证明

当s=2，3时，也有类似的方法， Atkin , Mu¨ller and Kong et al ，他们的方法在这种情况下， 要比Tonelli-Shanks and the Cipolla-Lehmer 表现得更为出色。

但是作者认为这些方法不能很好的解决普遍的情况，所以作者展示了一种，新的开根的方法，只用一个预计算好的基元，一次指数运算，并且在s很小的时候十分高效。

开二次根算法：

有一些高效的公式，分别当 q ≡ 5 (mod 8) ，或者 q ≡ 9 (mod 16) 。如果q ≡ 5 (mod 8) ，属于 q ≡ 1 (mod 4), 的一种特殊情况， Atkin 有一种只进行一次指数运算的高效的公式。

Algorithm 1 Atkin’s algorithm when q ≡ 5 (mod 8)

方程，x^2 = a mod (q)，已知a，求x

Algorithm 2 Mu¨ller’s algorithm when q ≡ 9 (mod 16)

方程，x^2 = a mod (q)，已知a，求x

其中第二步有个神奇的东西 η(d) ，paper中给的定义是

，然鹅想不出怎么让它等于-b，（还求大师傅们指点~）

在有限域中 Fq 开 r^s 根 [ q ≡ lr^s + 1 (mod r^(s+1)) ]

首先我们需要一个质数q，并且有一个r，满足 r | (q-1)，（如果r与q-1互质，那问题就很简单了，r的逆用欧拓很快就能找到）然后会存在一个s，s是满足的最大的正整数

即会满足

定理1：在域Fq中，给定一个r次幂c，存在一个b，使得c^(r-1)·b^r 具有r^t阶，（t<s）

证明：

我们设一个l，满足gcd(l,r)=1,那么存在β (0≤β<l)，满足 rβ+r−1 ≡ 0 (mod l) 即存在α，满足 rβ + r−1 = lα.

然后，我们设一个 ζ 为，

则有

 

其中，

因为c是域Fq中的r次幂，故ζ拥有r^t阶，(0≤t<s) （为啥这里t就小于s了，求指点~）

利用：

在域Fq中，我们令 ξ 为 一个r^2阶本原单位根，ξ可以通过公式计算得到，其中d为域Fq中的非r次幂，这样的d可以随机选取，在域Fq中找到它的概率为(r-1)/r

由此，我们设是一个r^t阶的本原单位根，则存在一对唯一确定的i，j满足

因为

所以我们有

由此我们将展现一个新的定理，在合适的情况下，我们用一次指数运算可以找到r次剩余的一个r次根，

定理2：定义u ≡ j·(r^t −1)·r^(s−t−1 ) ≡−jr^(s−t−1) (mod r^(s−1)). 那么在域Fq中c的一个r次根为 cbξ^u ，其中b在定理1中给出。

证明：

（由于，由费马小定理，故在域Fq中 易证，）

证毕。

注1： rβ + r −1 = lα 即 r(β + l) + r −1 = l(α + r)。这说明，α （mod r ）是确定的，β（mod l）是确定的，所以对于任意的α 满足 ,都有唯一确定的β满足 。作者在这里还加了一句，事实上，条件rβ + r−1−lα = 0 可以转化为 rβ + r−1−lα ≡ 0 (mod (q-1)/r） 因为 （难道是欧拉判别定理的推广？）

注2：cb的值可以化成

其中α是一个整数（0<α<r），满足所以b也可以表示为

注3：对于 ij ≡ 1 (mod r^t) ，当r^t很大（t>1 并且在r^t阶循环群中的离散对数很难处理）时，其中的i和j找起来是比较困难的，所以这个方法适合在r和t都比较小的时候，也可以被视作是另一个版本的Adleman-Manders-Miller algorithm。

举例与算法

终于到实例环节了~

例1 q ≡ lr + 1 (mod r^2) 0 < l < r:

在这种情况下，s=1,所以t=u=0，所以r次根c可以表示为cbξ^u = cb = 其中α需要满足

当r = 2，s=1就意味着， q ≡ 3 (mod 4) ，α在这里可以算出是1，带入公式，c的一个二次根就是众所周知的 ，（Rabin解密~）

当r = 3，s=1 就意味着 q ≡ 4 (mod 9) 或者 q ≡ 7 (mod 9) ，先算出α，然后带入公式，（当 q ≡ 4 (mod 9）

或是（当 q ≡ 7 (mod 9)）

这里有个表

最底下一样有例外，此时也就以为着r=0，r=0.还有啥根可开~

可见，当s=1时，在 q ≡ 1 (mod r) 并且 q !≡ 1 (mod r^2) 时，即q的(r-1) 种情况都可以借该公式进行一次指数运算就可开根，得到一个解。（推理过程一知半解的，但是结论用起来是真的香）

例2 q ≡ lr^2 + 1 (mod r^3) 0 < l < r:

当s=2.那么或者 是一个r阶本原单位根 （ζ是r^t阶，t=0 or 1），同时ξ也是一个r^2阶的本原单位根（原根）满足：即 。

因此，r次根可以表示为 cbξ^u ，具体的值上文已给，当t=0，u=0，x=cb是一个r次根，当t=1,u ≡−j (mod r) ，x= cbξ^−j是一个r次根。（所以我们还是希望t=0，这样计算就会极其方便~）

Algorithm 3 Our cube root algorithm when q ≡ 1 (mod 9) and q ̸≡ 1 (mod 27)

x^3=c (mod q) （ (q = 9l + 1 (mod 27) with l = 1,2, i.e., q ≡ 10,19 (mod 27)) ）

解读一下：

，其中d在域Fq种不是一个r次幂（遍历一下，随便取一个就好）。

ζ=c^r−1·b^r = c^2·b^3=X^2b

如果，ζ=1，则说明t=0，那么x=cb=X

如果，ζ=B=ξ^r，那么t=j=1,x=cbξ^-j=cbξ^2=XA^2

否则，j=2,x=cbξ^-j=cbξ^-2=XA

验证：

成功~

以下同

Algorithm 4 Our 5-th root algorithm when q ≡ 1 (mod 25) and q ̸≡ 1 (mod 125)

x^5=c (mod q)  (q = 25l + 1 (mod 125) with l = 1,2,3,4, i.e., q ≡ 26,51,76,101 (mod 125))

例3 q ≡ lr^3 + 1 (mod r^4) 0 < l < r:

当s=3，有r^t阶（t=0,1,2），同时 ξ 是一个r^3 阶的原根 ，满足：

所以，c的r次根可以表示为cbξ^u，当t=0，u=0,x=cb即是c的一个r次根，当t=1，

u ≡ −jr (mod r^2), 当t=2， u ≡ −j (mod r^2),

计算过程类比上文，只是要考虑的（u）的情况增加到了r^2种。

实战

回到开头说的NCTF crypto全场两解（大佬都去隔壁打D^3了~）的压轴——easyrsa

题目：（数字太大，就省去了）

from rsav import * 
 
e = 0x1337 
p =  
q =  
n = p * q 
 
 
''' 
assert(flag.startswith('NCTF')) 
m = int.from_bytes(flag.encode(), 'big') 
assert(m.bit_length() > 1337) 
 
c = pow(m, e, n) 
print(c)''' 
c= 

解题思路：

很普通的加密手段，然后p,q都给了，其中，e|q-1；e|p-1

唯一难点就在e是φ(n)的一个因子所以根本无法求出私钥d

第一步是类似rabin，先将m^e ≡ c (mod n)分解成同余式组

m^e ≡ c (mod p)

m^e ≡ c (mod q)

求出m1和m2，再用CRT就好了

至于m的求解，本题的条件正好符合上文的例1，

于是我们先遍历出α，然后就可以求得m1了，

再算出另一个α，得到m2，然后CRT走一波，就可以出明文的一种情况了，

然而一共有e^2种情况

当e=2，rabin解密，有e^2种情况，因为同余方程组里的每一个方程都有两种情况。

当e=3，每个就有三种，CRT后一共就有3^2种

根据hint2，里面有提供当找到一种解后找到其余解的算法

原理在这 https://crypto.stackexchange.com/questions/63614/finding-the-n-th-root-of-unity-in-a-finite-field

在有限域Fq中，乘法子群的阶为q-1，如果n不满足n|q-1，那么n次单位根只有1本身，如果n满足n|q-1，那么就有n个单位根。

由费马小定理

所以我们有n次单位根

当我们这个n次单位根不等于1时，我们就可以利用它和我们找到的一个根来生成一个阶为n的循环群，这个群里所有的元素即为我们想要的所有的根。

这样我们构造exp，遍历这0x1337*0x1337=24196561种可能，就能解出真正的密文了

import gmpy2 
 
def n2s(x): 
    try: 
        try: 
            flag = hex(x)[2:].decode("hex") 
        except: 
            flag = hex(x)[2:-1].decode("hex") 
    except: 
        flag='' 
    return flag 
 
def onemod(p,r): 
    t=p-2 
    while pow(t,(p-1)/r,p)==1: t-=1 
    return pow(t,(p-1)/r,p) 
 
def solution(p,root):  
    g=onemod(p,0x1337) 
    may=[] 
    for i in range(0x1337): 
        may.append(root*pow(g,i,p)%p) 
    return may 
 
c =  
 
p =  
 
q =  
e = 0x1337 
n = p*q 
 
c_p = pow(c,(1+3307*(p-1)/e)/e,p)  #p对应的α=3307 
print "find one" 
C1=solution(p,c_p)[::-1]   #逆序，问题不大，只是跑过一次，发现答案在两千多万次后 
print "find all" 
c_q = pow(c,(1+(2649*(q-1)/e))/e,q) #q对应的α=2649 
print "find another" 
C2=solution(q,c_q)[::-1] 
print "find all" 
a= gmpy2.invert(p,q) 
b = gmpy2.invert(q,p) 
#x = (b*q*c_p+a*p*c_q)%n 
flag=0 
for i in C1: 
    for j in C2: 
        flag+=1 
        if flag%1000000 == 0: 
            print flag 
        x = (b*q*i+a*p*j)%n 
        if "NCTF" in n2s(x): 
            print n2s(x) 
            exit(0)

 

总结

这一次借NCTF了解了在域中开根的一种高效方法，这种方法似乎比出题人soreatu师傅的预期解还要高效~

并且有幸拿到了一个一血，不得不说，这公式，真香~

另外感谢这次NCTF，在这次密码学的赛题中学到了很多，另外一道childrsa也很有意思（有意思在我意外的发现了其中一个神奇规律23333）

最后再次感谢soreatu师傅制作的优质赛题以及赛后详细的wp与指点~