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

首发于安全客

前言:

在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 表现得更为出色。

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中给的定义是

problem

,然鹅想不出怎么让它等于$-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中给出。

证明:

2

(由于 $ξ = 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的值可以化成

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}$)

这里有个表table

最底下一样有例外,此时也就以为着$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}$

Our cube root algorithm

解读一下:$ξ = 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$

验证:

check

成功~

以下同

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}$)

Algorithm 4 Our 5-th root algorithm

例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

题目:(数字太大,就省去了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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,

context

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

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

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

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

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

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

sol

在有限域$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种可能,就能解出真正的密文了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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)

flag

总结

这一次借NCTF了解了在域中开根的一种高效方法,

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

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

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

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


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

文章标题:密码学学习笔记 之 浅析On r-th Root Extraction Algorithm in Fq

文章字数:3.2k

本文作者:Van1sh

发布时间:2019-12-04, 14:30:46

最后更新:2020-06-05, 13:45:15

原始链接:http://jayxv.github.io/2019/12/04/密码学学习笔记之浅析On r-th Root Extraction Algorithm in Fq/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏