NSSCTF Round16

NSSCTF Round16 ——— Crypto 复现

pr

描述：CRT

from Crypto.Util.number import *
import random

flag=plaintext = 'NSSCTF{****************}'
charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
padding_length = 100 - len(plaintext)

for _ in range(padding_length):
    plaintext += random.choice(charset)

public_exponent = 31413537523
message = bytes_to_long(plaintext.encode())
assert message > (1 << 512)
assert message < (1 << 1024)

prime_p = getPrime(512)
prime_q = getPrime(512)
prime_r = getPrime(512)
n1 = prime_p * prime_q
n2 = prime_q * prime_r
ciphertext1 = pow(message, public_exponent, n1)
ciphertext2 = pow(message, public_exponent, n2)
print('c1=', ciphertext1)
print('c2=', ciphertext2)
print('p=', prime_p)
print('r=', prime_r)


'''
c1= 36918910341116680090654563538246204134840776220077189276689868322808977412566781872132517635399441578464309667998925236488280867210758507758915311644529399878185776345227817559234605958783077866016808605942558810445187434690812992072238407431218047312484354859724174751718700409405142819140636116559320641695
c2= 15601788304485903964195122196382181273808496834343051747331984997977255326224514191280515875796224074672957848566506948553165091090701291545031857563686815297483181025074113978465751897596411324331847008870832527695258040104858667684793196948970048750296571273364559767074262996595282324974180754813257013752
p= 12101696894052331138951718202838643670037274599483776996203693662637821825873973767235442427190607145999472731101517998719984942030184683388441121181962123
r= 10199001137987151966640837133782537428248507382360655526592866939552984259171772190788036403425837649697437126360866173688083643144865107648483668545682383
'''

真就止步CRT了

m被填充，很大，直接CRT算不出，利用 dp，dr 解

$$e*d\equiv 1\bmod (p-1)$$ $$d\equiv d_p\bmod (p-1)$$

所以有 $e*d_p\equiv 1\bmod (p-1)$

则，$d_p=e^{-1} \bmod (p-1)$ $d_r 同理$

再通过

$$m_p = c^{dp} \bmod p$$ $$m_r = c^{dr} \bmod r$$

求得 $m=crt([m_p,m_r],[p,r])$

exp：

from Crypto.Util.number import *
import gmpy2

e= 31413537523
c1= 36918910341116680090654563538246204134840776220077189276689868322808977412566781872132517635399441578464309667998925236488280867210758507758915311644529399878185776345227817559234605958783077866016808605942558810445187434690812992072238407431218047312484354859724174751718700409405142819140636116559320641695
c2= 15601788304485903964195122196382181273808496834343051747331984997977255326224514191280515875796224074672957848566506948553165091090701291545031857563686815297483181025074113978465751897596411324331847008870832527695258040104858667684793196948970048750296571273364559767074262996595282324974180754813257013752
p= 12101696894052331138951718202838643670037274599483776996203693662637821825873973767235442427190607145999472731101517998719984942030184683388441121181962123
r= 10199001137987151966640837133782537428248507382360655526592866939552984259171772190788036403425837649697437126360866173688083643144865107648483668545682383


dp = gmpy2.invert(e,p-1)
dr = gmpy2.invert(e,r-1)

mp = pow(c1,dp,p)
mr = pow(c2,dr,r)

m = crt([int(mp),int(mr)],[p,r])
flag = long_to_bytes(int(m))
print(flag)

# NSSCTF{yUanshEnx1ncHun2o23!}

考点：

1，dp、dq泄露

2，CRT

break

描述：私钥好像坏掉了，如何拿到里面的数据捏~

pri-break.pem:
Bc8tSTrvGJm2oYuCzIz+Yg4nwwKBgQDiYUawe5Y+rPbFhVOMVB8ZByfMa4LjeSDd
Z23jEGvylBHSeyvFCQq3ISUE40k1D2XmmeaZML3a1nUn6ORIWGaG2phcwrWLkR6n
ubVmb1QJSzgzmFHGnL56KHByZxD9q6DPB+o6gGWt8/6ddBl2NIZU/1btdPQgojfA
XXJFzR92RQKBgQC7qlB0U7m2U4FdG9eelSd+WSKNUVllZAuHji7jgh7Ox6La9xN5
miGZ1yvP44yX218OJ9Zi08o6vIrM6Eil45KzTtGm4iuIn8CMpox+5eUtoxyvxa9r
s2Wu+IRZN9zCME+p+qI8/TG27dIyDzsdgNqcUo8ESls7uW5/FEA7bYTCiQKBgQC7
1KybeB+kZ0zlfIdi8tVOpeI+uaHDbdh3+/5wHUsD3hmfg7VAag0q/2RA1vkB/oG1
QVLVHl0Yu0I/1/u5jyeakrtClAegAsvlrK+3i321rGS4YpTPb3SX1P/f3GZ7o7Ds
touA+NHk8IL9T7xkmJYw5h/RLG32ucH6aU6MXfLR5QKBgD/skfdFxGWxhHk6U1mS
27IM9jJNg9xLz5nxzkqPPhLn+rdgIIuTuQtv++eEjEP++7ZV10rg5yKVJd/bxy8H
2IN7aQo7kZWulHTQDZMFwgOhn0u6glJi+qC8bWzYDFOQSFrY9XQ3vwKMspqm+697
xM+dMUW0LML6oUE9ZjEiAY/5
-----END PRIVATE KEY-----

c = 6081370370545409218106271903400346695565292992689150366474451604281551878507114813906275593034729563149286993189430514737137534129570304832172520820901940874698337733991868650159489601159238582002010625666203730677577976307606665760650563172302688129824842780090723167480409842707790983962415315804311334507726664838464859751689906850572044873633896253285381878416855505301919877714965930289139921111644393144686543207867970807469735534838601255712764863973853116693691206791007433101433703535127367245739289103650669095061417223994665200039533840922696282929063608853551346533188464573323230476645532002621795338655

这题是真让我体会到 理解原理 的重要性

我们在网上常见的手撕私钥给出的例子：

3082025d  	# Begin Sequence: len=0x025d
0201  		# Version: (len=0x01)
00
028181		# n: (len=0x81)
0203		# e: (len=0x03)
028180		# d: (len=0x80)
0241		# p: (len=0x41)
0241		# q: (len=0x41)
0240		# d mod (p-1): (len=0x40)
0241		# d mod (q-1): (len=0x41)
0241		# (inverse of q) mod p: (len=0x41)		(  (1/q)mod p,即 q^(-1) mod p  )
			# End Sequence
    

这是n为1024位的例子
02 表示短整形 （512位用短整形）
0281 表示长整形  （1024位用长整形）
上面最后两位都表示长度

这里我们测出 c 为 2046 位

所以猜测 n 为 2048位，p、q分别为 1024 位

将私钥手动转化为 十六进制 ：

05cf2d493aef1899b6a18b82cc8cfe620e27c302818100e26146b07b963eacf6c585538c541f190727cc6b82e37920dd676de3106bf29411d27b2bc5090ab7212504e349350f65e699e69930bddad67527e8e448586686da985cc2b58b911ea7b9b5666f54094b38339851c69cbe7a2870726710fdaba0cf07ea3a8065adf3fe9d741976348654ff56ed74f420a237c05d7245cd1f764502818100bbaa507453b9b653815d1bd79e95277e59228d515965640b878e2ee3821ecec7a2daf713799a2199d72bcfe38c97db5f0e27d662d3ca3abc8acce848a5e392b34ed1a6e22b889fc08ca68c7ee5e52da31cafc5af6bb365aef8845937dcc2304fa9faa23cfd31b6edd2320f3b1d80da9c528f044a5b3bb96e7f14403b6d84c28902818100bbd4ac9b781fa4674ce57c8762f2d54ea5e23eb9a1c36dd877fbfe701d4b03de199f83b5406a0d2aff6440d6f901fe81b54152d51e5d18bb423fd7fbb98f279a92bb429407a002cbe5acafb78b7db5ac64b86294cf6f7497d4ffdfdc667ba3b0ecb68b80f8d1e4f082fd4fbc64989630e61fd12c6df6b9c1fa694e8c5df2d1e50281803fec91f745c465b184793a535992dbb20cf6324d83dc4bcf99f1ce4a8f3e12e7fab760208b93b90b6ffbe7848c43fefbb655d74ae0e7229525dfdbc72f07d8837b690a3b9195ae9474d00d9305c203a19f4bba825262faa0bc6d6cd80c5390485ad8f57437bf028cb29aa6fbaf7bc4cf9d3145b42cc2faa1413d663122018ff9

可以看出有3段 028181 和 1段 028180 ，我们知 0281是长整形，后面是81还是80是数据的长度决定，而不是他们决定是哪段数据

我们可以知道私钥按顺序列出我们需要的数据为：n、e、d、p、q、dp、dq、qinvp

所以我们得到的是最后四位数据：q、dp、dq、qinvp

有点上面那题的考点了

$$m\equiv c^{d_q} \bmod q$$

exp:

from Crypto.Util.number import *

q = 0xe26146b07b963eacf6c585538c541f190727cc6b82e37920dd676de3106bf29411d27b2bc5090ab7212504e349350f65e699e69930bddad67527e8e448586686da985cc2b58b911ea7b9b5666f54094b38339851c69cbe7a2870726710fdaba0cf07ea3a8065adf3fe9d741976348654ff56ed74f420a237c05d7245cd1f7645
dp = 0xbbaa507453b9b653815d1bd79e95277e59228d515965640b878e2ee3821ecec7a2daf713799a2199d72bcfe38c97db5f0e27d662d3ca3abc8acce848a5e392b34ed1a6e22b889fc08ca68c7ee5e52da31cafc5af6bb365aef8845937dcc2304fa9faa23cfd31b6edd2320f3b1d80da9c528f044a5b3bb96e7f14403b6d84c289
dq = 0xbbd4ac9b781fa4674ce57c8762f2d54ea5e23eb9a1c36dd877fbfe701d4b03de199f83b5406a0d2aff6440d6f901fe81b54152d51e5d18bb423fd7fbb98f279a92bb429407a002cbe5acafb78b7db5ac64b86294cf6f7497d4ffdfdc667ba3b0ecb68b80f8d1e4f082fd4fbc64989630e61fd12c6df6b9c1fa694e8c5df2d1e5
qinvp = 0x3fec91f745c465b184793a535992dbb20cf6324d83dc4bcf99f1ce4a8f3e12e7fab760208b93b90b6ffbe7848c43fefbb655d74ae0e7229525dfdbc72f07d8837b690a3b9195ae9474d00d9305c203a19f4bba825262faa0bc6d6cd80c5390485ad8f57437bf028cb29aa6fbaf7bc4cf9d3145b42cc2faa1413d663122018ff9
c = 6081370370545409218106271903400346695565292992689150366474451604281551878507114813906275593034729563149286993189430514737137534129570304832172520820901940874698337733991868650159489601159238582002010625666203730677577976307606665760650563172302688129824842780090723167480409842707790983962415315804311334507726664838464859751689906850572044873633896253285381878416855505301919877714965930289139921111644393144686543207867970807469735534838601255712764863973853116693691206791007433101433703535127367245739289103650669095061417223994665200039533840922696282929063608853551346533188464573323230476645532002621795338655

m = pow(c,dq,q)
print(long_to_bytes(m))

# flag{oi!_you_find___what_i_Wa1t_talK_y0n!!!}

考点：

1，手撕私钥

2，dp、dq泄露

参考链接：

(PKCS1) RSA 公私钥 pem 文件解析 - 知乎 (zhihu.com)

手撕PEM密钥（RSA） | Tover’ Blog

NSSCTF Round16 | DexterJie’Blog