hgame2020 RSA？

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from Crypto.Util.number import *
import gmpy2
from flag import flag

p = getPrime(256)
q = getPrime(256)
r = getPrime(512)
e = 2
m = bytes_to_long(flag)

n = p * q + r
c = pow(m, e, n)

with open('task', 'w') as f:
    f.write("c =  {}\n".format(str(c)))
    f.write("e =  {}\n".format(str(e)))
    f.write("q =  {}\n".format(str(q)))
    f.write("n =  {}\n".format(str(n)))

虽然有pow但不是RSA，因为n是素数
我觉得判断的原因就是p * q为非素数，再加上一个素数，就得到素数
后面知道是利用Tonelli–Shanks算法求解二次剩余问题。

已知n、c求m
参考：https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
https://blog.csdn.net/wmdcstdio/article/details/49862189?locationNum=15

Tonelli–Shanks算法

Tonellii - Shanks算法(Shanks称为RESSOL算法)在模运算中用于求解$r^2≡n (mod \ p)$的一个全等，其中p是质数:即求n模p的平方根。
Tonelli–Shanks不可用于复合模：求平方根模的复合数是一个与大整数分解等价的计算问题。

核心

给予一个非零n和一个奇素数p，欧拉判别法告诉我们n有一个平方根（例如，n是一个二次剩余）那么有:

相反，如果一个数z没有平方根（不满足二次剩余），则有：

我们不难发现z，因为在1和p-1之间的接近一半的的整数有这种性质，所以我们假定我们有这样的非二次剩余。
通过(通常情况下)重复除以2，我们可以把p-1写作$Q2^S$，而且此处Q为奇数，注意到如果我们尝试

接着$R^2\equiv n^{Q+1}(mod\ p)=(n)(n^Q)(mod\ p)$
如果$t\equiv n^Q\equiv 1 (mod\ p)$
那么R是n的一个平方根。否则对于M=S，我们有R和t满足

$R^2\equiv nt(mod\ p)$;和
t是一个1的$2^{M-1}$根（因为）
关键就是这里，如果满足此时t=1，那么R就是需要求解的r

如果我给一个R和t对于特定的M满足先前提到的（R不是n的平方根），我们能简单地计算出另外的R和t，且对于M-1满足先前提到的关系,这样我们能重复这一过程知道t变成1的2的$2^0$次方根，例如，t=1，在这时R是一个n的一个平方根。

我们可以检查t是否是1的一个$2^{M-2}$根通过开{M-1}次方，和检查是否等于1。如果是，那我们不需要做任何事，相同的R和t就可以了。但如果不是，${\displaystyle t^{2^{M-2}}}$一定要是-1（因为将它开方得到1，1模p只能有两个平方根1和-1）

为了找到一对新的R和t，我们能把R乘一个待定的因数b。接下来t一定要被因数$b^2$为了保证$R^2\equiv nt(mod\ p)$, 所以我们需要去找到一个因数$b^2$，以达成$tb^2$是一个1的$2^{M-2}$根，或者相同地，$b^2$是一个-1的$2^{M-2}$根。

关键的就是利用$z$，这个已知的非二次剩余数，欧拉判别法应用如上所示，${z^{Q}}$是-1的${2^{S-1}}$根，通过重复对${z^{Q}}$开方，我们可以得到一个$-1的2^i$次方根的序列。我们可以选择一个合适的去作为b，通过一点点变量维护和琐碎的情况压缩（翻不动），算法就有了。

例子

求解这样的全等式：$r^2\equiv 5(mod\ 41)$

41是一个所需要的素数，并且$41\equiv 1(mod\ 4)$ 5是一个通过欧拉判别法得知的二次剩余数：$5^{\frac{41-1}{2}}=5^{20}=1$(正如之前，在${\displaystyle (\mathbb {Z} /41\mathbb {Z} )^{\times }}$ (41模整数的乘法群)被暗中$mod\ 41$)

类似的等于关系下面会多次出现，因为其实还隐藏了mod41

1.$p-1=40=5*2^3$，所以$Q \leftarrow\ 5$ , $S \leftarrow\ 3$
2.找到z

• $2{\frac{41-1}{2}}=1$，所以2是一个二次剩余数
• $3{\frac{41-1}{2}}=40=-1$，所以3是一个二次非剩余数，令$z \leftarrow\ 3$

3.令

• $M \leftarrow\ S=3$
• $c \leftarrow\ z^Q=3^5=38$
• $t \leftarrow\ n^Q=5^5=9$
• $R \leftarrow\ n^{\frac{Q+1}{2}}=5^{\frac{5+1}{2}}=2$

4.循环

• 第一次迭代：
• $t \neq\ 1$，所以我们没完成
• ${\displaystyle t^{2^{1}}=40}, {\displaystyle t^{2^{2}}=1} 所以 {\displaystyle i\leftarrow 2}$
• ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$
• ${\displaystyle M\leftarrow i=2}$
• ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$
• ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$
• ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$

/n

• 二次迭代：
• ${\displaystyle t\neq 1}$, 所以我们还未完成
• ${\displaystyle t^{2^{1}}=1}$所以 ${\displaystyle i\leftarrow 1}$
• ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$
• ${\displaystyle M\leftarrow i=1}$
• ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$
• ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$
• ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$

/n

三次迭代

• $t=1$，我们完成了，返回值$r=R=28$

的确，$28^2\equiv 5(mod\ 41)和(-28)^2\equiv13^2\equiv5(mod\ 41)$,所以这个算法最终产生了两个同余解

脚本

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

from Crypto.Util.number import *

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)
 
def tonelli(n, p):
    assert legendre(n, p) == 1, "not a square (mod p)"
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r

n = 2166906408965390116437761185603075699086315246646982132520792868301615462732707695943058783211233589602162482847874299962577512765886861573898075548033678
p = 7236834786093916009325417235344284284391050287273422058348241360770131423240807259717864686885012301293921328397391157761688776563780348734483657156421779

res = tonelli(n, p)
print(long_to_bytes(res))
#b'hgame{eaa5262c-4631-46ef-a97b-53277ab7e1d8}'