羊城杯2023

Match
Created At :
Count:2k Views 👀 :
  1. Danger_RSA
  2. Easy_3L
  3. SigninCrypto
  4. XOR贯穿始终
  5. esyRSA

菜就多练

Danger_RSA

from Crypto.Util.number import *

m = bytes_to_long(flag)
def get_key(a, nbit):
    assert a >= 2
    while True:
        X = getRandomInteger(nbit // a)
        s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))
        p = X ** a + s
        if isPrime(p):
            return (p, s)

p, s = get_key(a, 1024)
q, t = get_key(a, 1024)

N = p * q
e = s * t
c = pow(m, e, N)
print("N =", N)
print("e =", e)
print("c =", c)
# N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
# e = 11079917583
# c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766

可以找到出处：

2023 CryptoCTF wp by lingfeng (medium分类——1)_c_ling_feng的博客-CSDN博客

e可以分解：

e_list = [3, 7, 7, 19, 691, 5741]

所以s和t的大小范围可以大致确定，通过从2枚举可以知道a=4，故s,t = (120561,91903)或(101577,109079)

由N的位数可以确定X的位数为256，验证了a=4

接着计算p、q：

$p = X^4 + s$

$q = Y^4 + t$

因s和t相对很小，对n开4次方得$X\cdot Y$整体

$p\cdot q \approx (X\cdot Y)^4$

再列方程

$n = (X^4 + s)\cdot (Y^4 + t) = (X\cdot Y)^4 + tX^4 + sY^4 + st$

由此解方程得到X、Y：

N = ...
e = 11079917583
c = ...

s = 120561
t = 91903

XY = int(iroot(N,4)[0])
X,Y = var('X,Y')
f1 = X * Y == XY
f2 = XY**4 + X**4 * t + Y**4 * s + s * t == N
solve([f1, f2], [X,Y])
#X == 47783641287938625512681830427927501009821495321018170621907812035456872958654
#Y == 44416071018427916652440592614276227563515579156219730344722242565477265479486

接着生成p、q后，发现e、phi不互素，有限域开方：

d=inverse(e//21,p-1)
m_21=pow(c,d,N)
e=21
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-m_21
mps=f.monic().roots()8
for i in mps:
    flag=long_to_bytes(int(i[0]))
    if b'CTF' in flag:
        print(flag)
#b'DASCTF{C0nsTruct!n9_Techn1qUe2_f0r_RSA_Pr1me_EnC2ypt10N}'

Easy_3L

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

m = bytes_to_long(flag)

def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h

def encrypt1(m):
    a = getPrime(250)
    b = getRandomNBitInteger(240)
    n = getPrime(512)
    seed = m
    s = [0] * 6
    s[0] = seed
    for i in range(1, 6):
        s[i] = (s[i - 1] * a + b) % n
    return s

def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c

s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])

p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)

# S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
# S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
# S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
# S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
# p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
# h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
# c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
  1. NRTU解出s[3]
  2. LCG求出a、b后求s[0]

模板题。


S1 = ...
S2 = ...
S4 = ...
S5 = ...

p = ...
h = ...
c = ...

m = matrix([[1, h],[0, p]])

print(m.LLL())
f, g = m.LLL()[0][0],m.LLL()[0][1]
f = abs(f)
g = abs(g) #注意取正值
a = c*f % p % g
S3 = inverse_mod(f,g)*a % g
print(S3)
#10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606

output = []
output.append(S1)
output.append(S2)
output.append(S3)
output.append(S4)
output.append(S5)

t = []
for i in range(len(output)-1):
    t.append(output[i+1] - output[i])
n_list = []

i = 2
while i<len(t)-1:
    n_list.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i]*t[i-2]-t[i-1]*t[i-1])))
    i+=1

#只有一个n
n = 12433235385460084327215142269091752668477278692416805859007828624838647815241707248797912107322868748847211061641608674422095027981318008221949510129177787

a = inverse((output[1] - output[0]), n) * (output[2] - output[1]) % n
b = output[1] - a*output[0] % n

flag = inverse(a, n) * (output[0] - b) % n
print(long_to_bytes(flag))
#b'DASCTF{NTRU_L0G_a6e_S1mpLe}'

SigninCrypto

from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from flag import flag
from key import key
from iv import iv
import os
import hashlib
import secrets

K1= key
hint1 = os.urandom(2) * 8
xor =bytes_to_long(hint1)^bytes_to_long(K1)
print(xor)

def Rand():
    rseed = secrets.randbits(1024)
    List1 = []
    List2 = []
    seed(rseed)
    for i in range(624):
        rand16 = getrandbits(16)
        List1.append(rand16)
    seed(rseed)
    for i in range(312):
        rand64 = getrandbits(64)
        List2.append(rand64)
    with open("task.txt", "w") as file:
        for rand16 in List1:
            file.write(hex(rand16)+ "\n")
        for rand64 in List2:
            file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")
Rand()

K2 = long_to_bytes(getrandbits(64))
K3 = flag[:8]

KEY = K1 + K2 + K3

IV=iv

IV1=IV[:len(IV)//2]
IV2=IV[len(IV)//2:]

digest1 = hashlib.sha512(IV1).digest().hex()
digest2 = hashlib.sha512(IV2).digest().hex()

digest=digest1+digest2
hint2=(bytes_to_long(IV)<<32)^bytes_to_long(os.urandom(8))
print(hex(bytes_to_long((digest.encode()))))
print(hint2)


mode = DES3.MODE_CBC
des3 = DES3.new(KEY, mode, IV)

pad_len = 8 - len(flag) % 8
padding = bytes([pad_len]) * pad_len
flag += padding

cipher = des3.encrypt(flag)

ciphertext=cipher.hex()
print(ciphertext)

xor_hint1_K1 = 334648638865560142973669981316964458403
print(long_to_bytes(xor_hint1_K1))
#b'\xfb\xc2\xfb\xc2\xfb\xc2\xfb\xc2\x9f\xa3\x88\xa1\x8f\xa4\x9f\xa3'

有重复的部分，说明hint1 = b’\xfb\xc2’ * 8，从而得到K1：

hint1 = long_to_bytes(xor_hint1_K1)[:2]*8
print(long_to_bytes(xor_hint1_K1 ^ bytes_to_long(hint1)))
#b'dasctfda'

K2最后来求。先看K3：

K3 = flag[:8]
#K3 = b'dasctf{' + b'?'

flag前7位固定为：”DASCTF{“，还差一位，可以爆破。

再来求IV：

digest = long_to_bytes(digest_encode)
print(digest[:len(digest)//2])
print(digest[len(digest)//2:])

发现digest的前后两半相同，说明IV1 == IV2。输出下hint2的信息，出现了b’GWHT’，32位，属于原IV中的一部分。输出下hint2的位数，95位，那么可以知道原IV64位，所以IV1 = IV2 = b’GWHT’，IV = b’GWHTGWHT’。

至此还剩下K2，涉及到预测随机数，但是16位的。

首先对于64位的随机数，其生成是由32位的随机数堆叠而成的，下面举例：

random.seed(0)
a=random.getrandbits(32)
b=random.getrandbits(32)

print((b<<32)+a)
random.seed(0)

print(random.getrandbits(64))
#7106521602475165645
#7106521602475165645

先生成的32位的数放在低位，后生成的32位的数放在高位，组合得到64位。

那16位的随机数生成原理呢，是否类似？下面举例：

random.seed(0)
a=random.getrandbits(16)
b=random.getrandbits(16)
print(bin(a))
print(bin(b))

random.seed(0)
c=random.getrandbits(32)
d=random.getrandbits(32)
print(bin(c))
print(bin(d))
'''
0b1101100000101100
0b110001010011111
0b11011000001011000000011111001101
0b1100010100111110110111110111110
'''

可以看到，每个16位的随机数是由生成的32位的随机数取高16位得到的。

再回到题目来:

for i in range(624):
        rand16 = getrandbits(16)
        List1.append(rand16)
for rand16 in List1:
        file.write(hex(rand16)+ "\n")

等于知道了624个32位随机数的高16位

for i in range(312):
        rand64 = getrandbits(64)
        List2.append(rand64)
for rand64 in List2:
        file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")

难理解可以通过举例知道，等价知道了624个32位数的低16位.

所以进行拼接就得到了624个完整的32位随机数，最后预测随机数得到K3就能解flag了：

f = open('C:\\Users\\lenovo\\Desktop\\task.txt').read()
data = [eval(i) for i in f]
data2 = []
for d in data[-312:]:
    a,b = d&0xffff,(d>>16)&0xffff
    data2.append(a)
    data2.append(b)
rc = RandCrack()
for a,b in zip(data,data2):
    t = (a<<16)+b
    rc.submit(t)
K2 = rc.predict_getrandbits(64)
print(K2)
print(long_to_bytes(K2))
#8623025688911679118
#b'w\xab$-d\xa6\x0e\x8e'

最后爆破出K3的最后一位解DES3即可

ciphertext = 'a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1'

K1 = b'dasctfda'
K2 = b'w\xab$-d\xa6\x0e\x8e'
K3_ = b'DASCTF{'
IV = b'GWHTGWHT'

for i in (string.ascii_letters + string.digits + '@' + '*'):
    K3 = K3_ + i.encode()
    Key = K1 + K2 + K3
    mode = DES3.MODE_CBC
    des3 = DES3.new(Key,mode,IV)
    m = des3.decrypt(bytes.fromhex(ciphertext))
    if b'DASCTF' in m:
        print(Key)
        print(m)
        break
        
#b'dasctfdaw\xab$-d\xa6\x0e\x8eDASCTF{8'
#b'DASCTF{8e5ee461-f4e1-4af2-8632-c9d62f4dc073}\x04\x04\x04\x04'

XOR贯穿始终

msg解核心价值观编码得到：

C0ngr4tulati0n5_y0u_fou^d_m3

压缩包密码，后面还有用处。打开压缩包，加密脚本：

from gmpy2 import gcd
from Crypto.Util.number import getPrime
from secret import enflag

p = getPrime(512)
q = getPrime(512)
n = q * p
phi = (p - 1) * (q - 1)
e = getPrime(17)
assert gcd(e, phi) == 1
# 以上信息生成了私钥文件,但文件被损坏了你能提取有用信息吗

c = pow(enflag, e, n)
print('c = ' + str(c))

'''
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
'''

私钥.pem:

-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbIL
SuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYE
N4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuW
eZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESv
IgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn
/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbn
jxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5
X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaA
UETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25u
Gz3++w==
-----END PRIVATE KEY-----

提示文件被损坏，手动获取私钥，可参考

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

首先按行将私钥信息转16进制，得到：

private_key = '''MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbIL
SuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYE
N4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuW
eZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESv
IgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn
/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbn
jxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5
X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaA
UETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25u
Gz3++w=='''
private_key = private_key.split("\n")
for i in private_key:
   print(base64.b64decode(i).hex())

30820277020100300d06092a864886f70d0101010500048202613082025d02010002818100b9ad332fb6b87d59b5b20b
4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece6604
37803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb96
79979923c2531ff487f9ba2500ade48995c315d913020301000102818100974ebb2da0bb0afb3603970c3e17d8b044af
22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127
fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e7
8f18d4d3b68f5765d10b701f0361024100ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb9
5fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9024100cad4c29d017e30ddabd60680
5044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e
1b3dfefb

3082025d  	# Begin Sequence: len=0x025d
0201  		# Version: (len=0x01)
00
028181		# n: (len=0x81)
0203		# e: (len=0x03)
010001
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)		
            # End Sequence

参考RSA | Lazzaro (lazzzaro.github.io)

根据规则可得到数据：

n = 0x00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
e = 0x010001
d = 0x00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
p = 0x00ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9

解RSA发现flag不全对，注意题目的XOR，再与之前得到的”C0ngr4tulati0n5_y0u_fou^d_m3”异或得到最终flag：

m = pow(c,d,n)
key = bytes_to_long(b'C0ngr4tulati0n5_y0u_fou^d_m3')
print(long_to_bytes(m^key))
#b'DASCTF{0e2874af5e422482378640e61d919e9a}'

esyRSA

from gmpy2 import invert
from md5 import md5
from secret import p, q

e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)

print n, e, d
print "Flag: DASCTF
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com

©2022-2023 Luino

Built with Hexo and 3-hexo theme

github