not_RSA [题目考点]
[题目文件] 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 λ = l c m ( p − 1 , q − 1 ) , L ( u ) = u − 1 n
Proof:
g ∈ Z ∗ n 2 , ∴ ∃ ( a , b ) , s . t . g = ( n + 1 ) a b n ( m o d n 2 )
c λ = ( n + 1 ) a m λ b n m λ r n λ = ( n + 1 ) a m λ = 1 + a m λ n ( m o d n 2 )
L ( c λ m o d n 2 ) = a m λ ,同理L ( g λ m o d n 2 ) = a λ ,证毕
本题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 ⋅ l c m ( p − 1 ) ( q − 1 ) ≡ 1 ( m o d n 2 ) ,所以c l c m → 二项式定理即可得m ⋅ l c m ( m o d n )
Complex Encode [题目考点]
[题目文件] Click Here to Download
[题解分析] 套娃题- -流程捋顺也就出来了
Step 1:RSA加密,且G C D ( p h i 1 , e 1 ) = r a n d o m . r a n d i n t ( 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 ,且发现G C D ( e 2 , p h i 2 ) = 41 ,因此先得到了m 41 2 ( m o d n 2 ) ,F p 2 , F q 2 上对c 2 开41次根,并对所有组合crt即可还原m 2 (b'flag{T0o_YoUn9_to0_4imP1e}'
),但无意义,该rsa系统返回值为m 41 2 ( m o d n 2 ) ,fine
Step 2中(r, s, k, q, m)均已知,可直接求出私钥x,也即为p 1
再对第一个RSA系统常规解密得到m 5 1 ,最后有限域开根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 m2 = bytes_to_long(b'flag{T0o_YoUn9_to0_4imP1e}' ) ran2 = 41 rsaEnc2 = pow(m2, ran2, n2) from base64 import b64decodesig = 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 hashlibHm = 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)])))