“not_RSA” in DASCTF
看了大佬的博客才知道是 Paillier cryptosystem，我太菜了…
直接使用现成的 Paillier cryptosystem 解密算法解决这题非常容易，分解n然后直接套 decrypt 函数就解开了…
题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from secret import flag,p,q
from sympy import isprime,nextprime
import random
m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)
c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)
print('c=',c)
print('n=',n)
|
主要加密过程是：
$$
\begin{aligned}
c&\equiv(g^m \ mod \ n^2)(r^n \ mod \ n^2) \ &(mod \ n^2) \\
&\equiv g^m r^n \ &(mod \ n^2)
\end{aligned}
$$
其中有
$$
\begin{aligned}
g^m&\equiv (n+1)^m \ &(mod \ n^2) \\
&\equiv C_m^0 n^0 + C_m^1 n^1 +C_m^2n^2+…+C_m^mn^m \ &(mod \ n^2) \\
&\equiv C_m^0 n^0 + C_m^1 n^1 \ &(mod \ n^2)\\
&\equiv 1 + mn \ &(mod \ n^2)
\end{aligned}
$$
所以得到$c\equiv g^m r^n\equiv (1 + mn)r^n \ (mod \ n^2)$
现在就要想办法消除掉 $r^n$ 的影响，不难发现 $r^n\ mod\ n = c\ mod\ n$。
所以我们需要由 $r^n\ mod\ n$ 得到 $r$ 的值或者 $r^n\ mod\ n^2$的值，才可以对 $r^n$ 在模 $n^2$ 下求逆元。这里我这个菜鸡想了好久…最终想到将 $r^n\ mod\ n$ 分别对 $n$ 的两个因数 $p,q$ 取模，然后再用中国剩余定理（CRT）合并，从而得到 $r$。
然后我们只需要计算 $r^n\ mod\ n^2$ 的逆元并与 $c$ 相乘，就得到 $(1+mn)\ mod\ n^2$，也就得到了 $m$。
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
|
from Crypto.Util.number import long_to_bytes, inverse
from functools import reduce
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
g = n+1
phi = (p-1)*(q-1)
rn = c % n
x1 = rn % p
d1 = inverse(q, p-1)
r1 = pow(x1, d1, p)
x2 = rn % q
d2 = inverse(p, q-1)
r2 = pow(x2, d2, q)
def CRT(m, a):
Num = len(m)
M = reduce(lambda x, y: x*y, m)
Mi = [M//i for i in m]
t = [inverse(Mi[i], m[i]) for i in range(Num)]
x = 0
for i in range(Num):
x += a[i]*t[i]*Mi[i]
return x % M
r = CRT([p, q], [r1, r2])
R = pow(r, n, n*n)
R_inv = inverse(R, n*n)
mn = (c*R_inv) % (n*n)
m = (mn-1)//n
print(long_to_bytes(m))
|
Paillier Crytposystem
选取素数 $p, q$，计算 $n=p\cdot q$，$\lambda =lcm(p-1,q-1)$，选取 $g\in\Z_{n^2}^*$满足 $g$ 的阶是 $n$ 的倍数。
其中公钥为：$n, g$，私钥为：$p, q,\lambda$。
加密时明文 $m<n$，选取随机的 $r \in \Z_n^*$，计算出密文 $c=g^m r^n \ mod \ n^2$。
解密时的密文 $c<n^2$，明文 $m=\cfrac{L(c^\lambda\ mod\ n^2)}{L(g^\lambda\ mod\ n^2)}\ (mod\ n)$，其中 $L(u)=\cfrac{u-1}{n}$。
在选取合适的 $g$ 的时候，需要判断 $g$ 的阶是否为 $n$ 的倍数，等价于判断 $GCD(L(g^\lambda\ mod\ n^2),n)=1$。
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
|
from Crypto.Util.number import*
from gmpy2 import lcm
class Paillier():
def __init__(self):
pass
def encrypt(self, m):
p, q = getPrime(512), getPrime(512)
n = p*q
self.n = n
assert m < n
Lcm = lcm(p-1, q-1)
g = getRandomRange(1, n*n)
while GCD(self.L(pow(g, Lcm, n*n)), n) != 1:
g = getRandomRange(1, n*n)
r = getRandomRange(1, n)
return (pow(g, m, n*n)*pow(r, n, n*n)) % (n*n), p, q, g
def decrypt(self, c, p, q, g):
n = p*q
assert c < n*n
Lcm = lcm(p-1, q-1)
self.n = n
self.d = inverse((p-1)*(q-1), n)
m_c = self.L(pow(c, Lcm, n*n))
m_g = self.L(pow(g, Lcm, n*n))
m = m_c*inverse(m_g, n) % n
return m
def L(self, u):
return (u-1)//self.n
m = bytes_to_long(b'flag{1234567890}')
P = Paillier()
c, p, q, g = P.encrypt(m)
M = P.decrypt(c, p, q, g)
print(long_to_bytes(M))
# b'flag{1234567890}'
|
使用 Paillier 解密就可以直接解这一题。
exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
from Crypto.Util.number import long_to_bytes,inverse
from gmpy2 import lcm
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
g = n+1
phi = (p-1)*(q-1)
def decrypt(c, p, q, g):
n = p*q
Lcm = lcm(p-1, q-1)
m_c = (pow(c, Lcm, n*n)-1)//n
m_g = (pow(g, Lcm, n*n)-1)//n
m = m_c*inverse(m_g, n) % n
return m
m=decrypt(c, p, q, g)
print(long_to_bytes(m))
#b'flag{5785203dbe6e8fd8bdbab860f5718155}'
|