not_RSA

[题目考点]

  • Paillier cryptosystem

[题目文件]

Click Here to Download

[题解分析]

从$Z_{n}\times Z_{n}^{}$到$Z_{n^{2}}^{}$存在双射关系$(x,y)\rightarrow g^{x}y^{n}(mod\ n^{2})$

Paillier cryptosystem系统加解密流程如下：

which $\lambda =lcm(p-1,q-1),L(u)=\frac{u-1}{n}$

Proof：

$g\in Z_{n^{2}}^{*},\quad\therefore \exists(a, b),s.t.\ g=(n+1)^{a}b^{n}(mod\ n^{2})$

$c^{\lambda}=(n+1)^{am\lambda}b^{nm\lambda}r^{n\lambda}=(n+1)^{am\lambda}=1+am\lambda n(mod\ n^{2})$

$L(c^{\lambda}\ mod\ n^{2})=am\lambda$，同理$L(g^{\lambda}\ mod\ n^{2})=a\lambda$，证毕

本题$g=n+1$，且n可以直接Fermat分解得到pq，按上述方法解密即可

[exp]

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
n = p * q
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
lcm = ((p - 1) * (q - 1)) // GCD(p - 1, q - 1)
a = (pow(c, lcm, n * n) - 1) // n
b = (pow(n + 1, lcm, n * n) - 1) // n
m = long_to_bytes((a * inverse(b, n)) % n)
print(m)

[More]

单从这道题本身来看，其实不了解这个密码系统也可，因为$g=n+1$，且$r^{n\cdot lcm(p-1)(q-1)}\equiv 1(mod\ n^{2})$，所以$c^{lcm}\rightarrow$ 二项式定理即可得$m\cdot lcm(mod\ n)$

Complex Encode

[题目考点]

  • 有限域开根
  • 其他RSA/DSA基础知识

[题目文件]

Click Here to Download

[题解分析]

套娃题- -流程捋顺也就出来了

Step 1：RSA加密，且$GCD(phi_{1},e_{1})=random.randint(3, 12)$，$p_{1}$作为泄露信息进入Step2

Step 2：$p_{1}$作为DSA Signature的私钥，对rsaEncode2(false_flag)签名，并返回

1
2
sig = r.to_bytes(205, 'big') + s.to_bytes(205, 'big') + k.to_bytes(205, 'big')+ q.to_bytes(205, 'big')
f.write("dsaEncode :"+base64.b64encode(sig).decode()+"\n")

Step 3：Step 2中的rsaEncode2(false_flag)来自于第二个RSA加密系统的返回值，可以看到gen_prime时用了next_prime，费马分解得到$p_{2},q_{2}$，且发现$GCD(e_{2},phi_{2})=41$，因此先得到了$m_{2}^{41}(mod\ n_{2})$，$F_{p_{2}},F_{q_{2}}$上对$c_{2}$开41次根，并对所有组合crt即可还原$m_{2}$（b'flag{T0o_YoUn9_to0_4imP1e}'），但无意义，该rsa系统返回值为$m_{2}^{41}(mod\ n_{2})$，fine

Step 2中(r, s, k, q, m)均已知，可直接求出私钥x，也即为$p_{1}$

再对第一个RSA系统常规解密得到$m_{1}^{5}$，最后有限域开根crt拿到flag

[exp]

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
# 第二个RSA解密略
m2 = bytes_to_long(b'flag{T0o_YoUn9_to0_4imP1e}')
ran2 = 41
rsaEnc2 = pow(m2, ran2, n2)

from base64 import b64decode
sig = b'...'
sig = b64decode(sig)
r = bytes_to_long(sig[:205])
s = bytes_to_long(sig[205:410])
k = bytes_to_long(sig[410:615])
q = bytes_to_long(sig[615:820])

import hashlib
Hm = int.from_bytes(hashlib.md5(str(rsaEnc2).encode('utf-8')).hexdigest().encode(), 'big')
x = ((s * k - Hm) % q) * inverse(r, q)
n1 = ...
p1 = x % q
q1 = n1 // p1
e1 = 0x12a316381
c1 = ...
assert(GCD(e1, (p1 - 1)*(q1 - 1)) == 5)
d1 = inverse(e1 // 5, (p1 - 1) * (q1 - 1))
m1_5 = pow(c1, d1, n1)

PP.<x> = PolynomialRing(Zmod(p1))
fp = x^5 - (m1_5 % p1)
m1_p = fp.roots()
PQ.<y> = PolynomialRing(Zmod(q1))
fq = y^5 - (m1_5 % q1)
m1_q = fq.roots()

tmp = []
for i in m1_p:
    for j in m1_q:
        tmp.append((i[0], j[0]))

for (m1p, m1q) in tmp:
    print(long_to_bytes(crt([int(m1p), int(m1q)], [int(p1), int(q1)])))
# b'flag{2a4d55342b46289d1f624d3083c5e2de}'