首发于安全客
前言:
在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
- $b <== (2a)^\frac{q-5}{8}$
- $i <== 2ab^2$
- $x <==ab(i-1)$
- $return x$
Algorithm 2 Mu¨ller’s algorithm when $q \equiv 9 \pmod{ 16}$
方程,$x^2 = a \pmod{q}$,已知$a$,求$x$
- $b <== (2a)^\frac{q-1}{4}$
- $Find randomly d satisfying -b = η(d)$
- $u <== (2ad^2)^\frac{q-9}{16}$
- $i <== 2u^2d^2a$
- $x <== uda(i-1)$
- $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
题目:(数字太大,就省去了)
12345678910111213141516 |
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种可能,就能解出真正的密文了
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
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,也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论