关于微信公众号

首发于安全客

前言：

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

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

On r-th Root Extraction Algorithm in Fq

On r-th Root Extraction Algorithm

引言：

我们让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(rlog_3q)$ 要高。但是，由于Cipolla Lehmer需要繁琐的扩展字段算法，当s比较小时，the Adleman-Manders-Miller algorithm 要比之更为有效。

另一方面，在某些情况下还存在比 Tonelli-Shanks 计算更快的其他方法来做开方运算。例子就是当 $q\equiv 3 \pmod {4}$.

$c$时$F_q$中的二次剩余时，$c$的其中一个根就是$c^\frac{q+1}{4}$，利用欧拓很容易证明$(c^\frac{q+1}{4})^2 = c$

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

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

开二次根算法：

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

Algorithm 1 Atkin’s algorithm when $q \equiv 5 \pmod{ 8}$

方程，$x^2 = a \pmod{q}$，已知a，求x

1. $b <== (2a)^\frac{q-5}{8}$
2. $i <== 2ab^2$
3. $x <==ab(i-1)$
4. $return x$

Algorithm 2 Mu¨ller’s algorithm when $q \equiv 9 \pmod{ 16}$

方程，$x^2 = a \pmod{q}$，已知$a$，求$x$

1. $b <== (2a)^\frac{q-1}{4}$
2. $Find randomly d satisfying -b = η(d)$
3. $u <== (2ad^2)^\frac{q-9}{16}$
4. $i <== 2u^2d^2a$
5. $x <== uda(i-1)$
6. $retrun x$

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

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

在有限域中 Fq 开 $r^s$ 根 [ $q \equiv lr^s + 1 \pmod{ r^{s+1})}$ ]

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

即会满足$q \equiv lr^s + 1 \pmod{r^{s+1}}$

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

证明：

我们设一个$l$，满足$gcd(l,r)=1$,那么存在$β (0≤β<l)$，满足 $rβ+r−1 \equiv 0 \pmod{ l}$即存在$α$，满足 $rβ + r−1 = lα.$

然后，我们设一个 $ζ$ 为，

$ζ = (c^a)^\frac{q-1}{r^2}$

则有

$ζ = (c^a)^\frac{q-1}{r^2}$

= $(c^a)^\frac{q-1}{r^2}c^{rβ+r-1-lα} = c^{r-1}c^{rβ}(c^α)^\frac{q-1}{r^s}c^{-lα}$

= $c^{r-1}{c^β(c^α)^\frac{q-1-lr^s}{r^{s+1}}}^r = c^{r-1}b^r$

其中，$b = c^β(c^α)^\frac{q-1-lr^s}{r^{s+1}}$

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

利用：

在域$F_q$中，我们令 $ξ $为 一个$r^2$阶本原单位根，$ξ$可以通过公式$ξ = d^\frac{q-1}{r^s}$

计算得到，其中$d$为域$F_q$中的非$r$次幂，这样的$d$可以随机选取，在域$F_q$中找到它的概率为$\frac{r-1}{r}$

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

$ξ^{r^{s-t}} = ζ^i, ζ = (ξ^{r^{s-t}})^j$

因为$ζ = (ξ^{r^{s-t}})^j = ζ^{ij}$, 所以我们有 $ij \equiv 1 \pmod{r^t}$

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

定理2：定义$u \equiv j·(r^t −1)·r^{s−t−1} \equiv −jr^{s−t−1} \pmod{ r^{s−1}}$. 那么在域$F_q$中$c$的一个$r$次根为 $cbξ^u$ ，其中$b$在定理1中给出。

证明：

(由于 $ξ = d^\frac{q-1}{r^s}$ ,由费马小定理，在$F_q$中 $ξ^{r^s} = 1 $易证 )

证毕。

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

注2：cb的值可以化成

其中$α$是一个整数$（0<α<r）$，满足$1+α^\frac{q-1}{r^s}\equiv 0 \pmod{r}$所以b也可以表示为

$b = cb/c = c^\frac{l+a^\frac{q-1}{r^s}-r}{r}$

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

举例与算法

终于到实例环节了~

例1 $q \equiv lr + 1 \pmod{ r^2} 0 < l < r$:

在这种情况下，$s=1$,所以$t=u=0$，所以$r$次根$c$可以表示为$cbξ^u = cb = c^\frac{l+a^\frac{q-1}{r^s}}{r}$

其中α需要满足$1+a^\frac{q-1}{r}\equiv 0\pmod {r}$ 当$r = 2，s=1$就意味着，$ q \equiv 3 \pmod{ 4}$ ，$α$在这里可以算出是1，带入公式，$c$的一个二次根就是众所周知的$c^\frac{p+1}{4}$，（Rabin解密~）

当$r = 3，s=1$ 就意味着 $q \equiv 4 \pmod{ 9}$ 或者 $q \equiv 7 \pmod{ 9}$，先算出$α$，然后带入公式

$c^\frac{1+2\frac{q-1}{3}}{3}= c^\frac{2q+1}{9}$，（$当 q \equiv 4 \pmod{ 9}$) 或是$c^\frac{1+1^\frac{q-3}{3}}{3} = c^\frac{q+2}{9} $（当 $q \equiv 7 \pmod{ 9}$)

这里有个表

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

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

例2 $q \equiv lr^2 + 1 \pmod{ r^3} 0 < l < r$:

当$s=2$.那么$ζ = (c^α)^\frac{q-1}{r^2}=1$)或者 是一个$r$阶本原单位根 （$ζ$是$r^t$阶，$t$=0 or 1），同时$ξ$也是一个$r^2$阶的本原单位根（原根）满足：$ξ^{r^2-t} = ζ^i 即 (ξ^{r^2-t})^j =ζ $ with $ij\equiv 1 \pmod{r^t}$

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

Algorithm 3 Our cube root algorithm when $q \equiv 1 \pmod{ 9}$ and $q ̸\equiv 1 \pmod{ 27}$

$x^3\equiv c \pmod{ q}$ $ (q = 9l + 1 \pmod{ 27}$ with $ l = 1,2, i.e.$, $q \equiv 10,19 \pmod{ 27}$

解读一下：$ξ = d^\frac{q-1}{r^s}$，其中$d$在域$F_q$种不是一个$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 \equiv 1 \pmod{ 25}$and$ q \equiv 1 \pmod{ 125}$

$x^5=c \pmod{ q}$($q \equiv 25l + 1 \pmod{ 125}$with$ l = 1,2,3,4, $i.e., $q \equiv 26,51,76,101 \pmod{ 125}$)

例3 $q \equiv lr^3 + 1 \pmod{ r^4} 0 < l < r:$

当$s=3$，$ζ = (c^α)^\frac{q-1}{r^3} = 1$ 有$r^t$阶$（t=0,1,2）$，同时 $ξ $是一个$r^3 $阶的原根 ，满足：

$ξ^{r^3-t} = ζ^i $ and $(ξ^{r^3-t})^j = ζ$ with $ij \equiv 1 \pmod {r^t}$

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

$u \equiv −jr \pmod{ r^2}$, 当$t=2$， $u \equiv −j \pmod{ r^2}$,

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

实战

回到开头说的NCTF crypto全场两解（大佬都去隔壁打D3了~）的压轴——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 \equiv c \pmod{ n}$分解成同余式组

$m^e \equiv c \pmod{ p}$

$m^e \equiv c \pmod{ q}$

求出$m_1$和$m_2$，再用CRT就好了

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

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

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

然而一共有$e^2$种情况

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

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

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

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

由费马小定理$(x^\frac{q-1}{n})^n = x^{q-1} = 1$ 所以我们有n次单位根$x^\frac{q-1}{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了解了在域中开根的一种高效方法，

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

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

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

但是这个方法的限制有点多，soreatu师傅给出的方法应该比较具有普适性，膜

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com