2022-12-16   28 m   4.2 k0 visits

RCTF2022 Crypto部分wp

不得不感慨这次RCTF Crypto的题目质量是真的高，每道题都能见到不一样的新考点，以至于做的时候翻了不少新的paper。确实也从做题过程中学到了不少东西。先写一下解出来的几道题目，剩下的下次有时间再慢慢总结复现吧。

Derek

题目关键源码：

Derek.py

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from LFSR import LFSR
from ctypes import c_uint64
from util import aes, nsplit
from Crypto.Util.Padding import pad


class Derek():
    def __init__(self, key, rnd=10):
        self.key = key
        self.rnd = rnd
        self.keys = list()
        self.generatekeys(self.key)

    def generatekeys(self, key: bytes) -> None:
        lfsr = LFSR(int.from_bytes(key, 'big'))
        for i in range(self.rnd):
            b = 0
            for j in range(128):
                b = (b << 1) + lfsr.next()
            self.keys.append(b.to_bytes(16, 'big'))

    def enc_block(self, x: int) -> int:
        x_bin = bin(x)[2:].rjust(128, '0')
        l, r = int(x_bin[:64], 2), int(x_bin[64:], 2)
        for i in range(self.rnd):
            magic = c_uint64(0xffffffffffffffff)
            for m in bytes([int(bin(byte)[2::].zfill(8)[8::-1], 2)
                            for byte in l.to_bytes(8, 'big')]):
                magic.value ^= c_uint64(m << 56).value
                for j in range(8):
                    if magic.value & 0x8000000000000000 != 0:
                        magic.value = magic.value << 1 ^ 0x1b
                    else:
                        magic.value = magic.value << 1
            magic.value ^= 0xffffffffffffffff
            t = bytes([int(bin(byte)[2::].zfill(8)[8::-1], 2)
                      for byte in bytes(magic)])
            t = aes(int(t.hex(), 16), self.keys[i]) & 0xffffffffffffffff
            t ^= aes(0xdeadbeefbaadf00d if i % 2 else 0xbaadf00ddeadbeef,
                     self.keys[i]) & 0xffffffffffffffff
            l, r = r ^ t, l
        l ^= int.from_bytes(self.key[:8], 'big')
        r ^= int.from_bytes(self.key[8:], 'big')
        l, r = r, l
        y = (l + (r << 64)) & 0xffffffffffffffffffffffffffffffff
        return y

    def dec_block(self, x: int) -> int:
        raise Exception('Unimplement')

    def encrypt(self, text: bytes) -> bytes:
        text_blocks = nsplit(pad(text, 16), 16)
        result = b''
        for block in text_blocks:
            block = int.from_bytes(block, 'big')
            result += self.enc_block(block).to_bytes(16, 'big')
        return result

    def decrypt(self, text: bytes) -> bytes:
        raise Exception('Unimplement')

LFSR.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LFSR():
    def __init__(self, init, mask=int.from_bytes(b'RCTF2022Hack4fun', 'big'), length=128):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        i = self.init & self.mask & self.lengthmask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

task.py

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
import os
from Derek import Derek

with open('flag.txt', 'rb') as f:
    flag = f.read()


banner = '''
██████╗ ███████╗██████╗ ███████╗██╗  ██╗
██╔══██╗██╔════╝██╔══██╗██╔════╝██║ ██╔╝
██║  ██║█████╗  ██████╔╝█████╗  █████╔╝ 
██║  ██║██╔══╝  ██╔══██╗██╔══╝  ██╔═██╗ 
██████╔╝███████╗██║  ██║███████╗██║  ██╗
╚═════╝ ╚══════╝╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝                            
'''
print(banner)
key = os.urandom(16)
derek = Derek(key, rnd=42)
while True:
    print(
        '| Option:\n|\t[E]ncrypt\n|\t[D]ecrypt\n|\t[G]et encrypted flag\n|\t[Q]uit')
    option = input('> ')
    if option.lower() == 'e':
        print(derek.encrypt(bytes.fromhex(
            (input('msg you want to encrypt (in hex) > ')))).hex())
    elif option.lower() == 'd':
        print('unimplement')
    elif option.lower() == 'g':
        print(derek.encrypt(flag).hex())
    else:
        exit()

一个奇怪的Feistel结构，42轮密钥加密，提供了任意加密的功能。看起来无从下手，于是结合题目名搜了一会儿，发现了Big Brother Is Watching You_ A Closer Look at Backdoor Construction，里面正好提到了Derek以及Feistel密码里存在的一种后门攻击。大致意思就是，Derek指代密码算法的设计者，在Feistel加密中故意留下一个后门用于窃取关键信息，而密码算法的使用者对此不得而知。论文里边提到了一种ZUGZWANG的Feistel网络，构造特定的输入可以使得每轮密文L部分陷入到两种不同的后门值中，一直持续到n轮结束，然后通过最后的密钥异或过程能提取出主密钥。

大致研究了一些论文里对后门的描述，发现跟本题的结构类似。0xdeadbeefbaadf00d与0xbaadf00ddeadbeef是两个后门值（对应奇偶轮数），只要让每轮中的aes加密前t等于对应的后门值，那么两次aes的异或值为0，aes起不到任何作用，t最终为0。产生的影响即是，本轮仅仅只做了一个LR交换，而每轮正好只对L进行计算，那么正好符合后门值奇偶轮数的交替，将影响一直传播到42轮结束。此时，再做一个简单的异或即可提取出主密钥key，然后用于解密。

思路就是这样，然后问题就是如何让自己的输入陷入到后门值中。在aes前面还有一块儿处理算法，也不是很难，稍微逆一下还是能写出逆算法的。然后提取出key之后，还要实现一下解密算法用于解密flag。

贴一下自己写的脚本吧。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from pwn import *
from Crypto.Util.number import *
from ctypes import c_uint64
from Derek import Derek

context.log_level = 'debug'

sh=remote('94.74.90.243',42000)
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud = lambda a     :sh.recvuntil(str(a),drop=True)

def getinput(target):
    s=list(bytes.fromhex(target))
    s[0]^=0x1b
    magic=int(''.join([ bin(b)[2::].zfill(8)[8::-1] for b in s][::-1]),2)
    magic = c_uint64(magic)
    magic.value ^= 0xffffffffffffffff
    t=magic.value
    ms=[]
    for i in range(8):
        tmpm=''
        for j in range(8):
            if t&1:
                t=((t^0x1b)>>1)|0x8000000000000000
                t=t&0xffffffffffffffff
                tmpm+='1'
            else:
                t=t>>1
                t=t&0xffffffffffffffff
                tmpm+='0'
        tmpm=int(tmpm[::-1],2)
        ms.append(tmpm^0xff)
    ms=ms[::-1]
    ms=bytes([ int(bin(m)[2::].zfill(8)[8::-1], 2) for m in ms])
    ms=int.from_bytes(ms,'big')
    return ms

backdoor_l="baadf00ddeadbeef"
backdoor_r="deadbeefbaadf00d"
l=getinput(backdoor_l)
r=getinput(backdoor_r)
backdoor=hex((l<<64)+r)[2:].zfill(32)
print(backdoor)

#send backdoor
sla('> ','E')
sla('> ',backdoor)
enc_backdoor=bytes.fromhex(rl().strip().decode())
key=xor(enc_backdoor[:16],bytes.fromhex(backdoor))
print(key.hex())

sla('> ','G')
enc_flag=bytes.fromhex(rl().strip().decode())
derek=Derek(key,rnd=42)
flag=derek.decrypt(enc_flag)
print(flag)
sh.interactive()
#b'RCTF{3asy_backd0or_wiTh_CRC_r3ver3s1ng}\t\t\t\t\t\t\t\t\t'

实现的Derek的decrypt函数如下：

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
def dec_block(self, x: int) -> int:
    l=(x>>64)&0xffffffffffffffff
    r=x&0xffffffffffffffff
    l ^= int.from_bytes(self.key[:8], 'big')
    r ^= int.from_bytes(self.key[8:], 'big')
    for i in range(self.rnd-1,-1,-1):
        prev_l = r
        magic = c_uint64(0xffffffffffffffff)
        for m in bytes([int(bin(byte)[2::].zfill(8)[8::-1], 2)
                        for byte in prev_l.to_bytes(8, 'big')]):
            magic.value ^= c_uint64(m << 56).value
            for j in range(8):
                if magic.value & 0x8000000000000000 != 0:
                    magic.value = magic.value << 1 ^ 0x1b
                else:
                    magic.value = magic.value << 1
        magic.value ^= 0xffffffffffffffff
        t = bytes([int(bin(byte)[2::].zfill(8)[8::-1], 2)
                  for byte in bytes(magic)])
        t = aes(int(t.hex(), 16), self.keys[i]) & 0xffffffffffffffff
        t ^= aes(0xdeadbeefbaadf00d if i % 2 else 0xbaadf00ddeadbeef,
                 self.keys[i]) & 0xffffffffffffffff
        prev_r = l^t
        l, r = prev_l, prev_r
    return ((l<<64)+r) & 0xffffffffffffffffffffffffffffffff

def decrypt(self, text: bytes) -> bytes:
    text_blocks = nsplit(text, 16)
    result = b''
    for block in text_blocks:
        block = int.from_bytes(block, 'big')
        result += self.dec_block(block).to_bytes(16, 'big')
    return result

Clearlove

题目源码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from Crypto.Util.number import *

with open('flag.txt', 'rb') as f:
    msg = f.read()

junk_msg = [os.urandom(120) for i in range(65536)]
for i in range(len(msg)):
    junk_msg[i] = junk_msg[i][:i] + bytes([msg[i]]) + junk_msg[i][i+1:]

p = 990367536408524906540912485167816012092796554403092639917950993714265910699138052663068131070259292593771612112016905904144038137551264432483487958987773403759866096258076571660618998739176702013853258687325567753038298889168254166361474202422033630403618955865472205722190830457928271527937
g = 745013838642250986737914025336862504661062017981819269513542907265222774830330586097756124678061002877695509685688964126565784246358161149675046363463274308162223776270434432888284419417479549219965033745142547821863438374478028783067286583042510995247992045551680383288951502770625897136683

Zp = Zmod(p)
g = Zp(g)
junk_msg = [Zp(bytes_to_long(msg)) for msg in junk_msg] 
junk_cipher = []

for i in range(65536):
    junk_cipher.append(ZZ(sum(junk_msg[j] * g^(i*j) for j in range(65536))))

def generate_params(beta):
    n = 1024
    delta = 0.642

    p_upper_bound = 1 << (n // 2)
    p_lower_bound = p_upper_bound >> 1
    p = random_prime(p_upper_bound, lbound=p_lower_bound)
    pqdiff_upper_bound = 1 << int(n * beta)
    '''
    Jinx: QUADRA KILL
    '''
    pqdiff_lower_bound = pqdiff_upper_bound * 0.7777777
    q = next_prime(p + random_prime(pqdiff_upper_bound, lbound=pqdiff_lower_bound))
    N = p * q
    AAHPH = (p^2 - 1) * (q^2 - 1)

    d_upper_bound = 1 << (int(n * delta))
    d_lower_bound = d_upper_bound >> 1
    while True:
        d = random_prime(d_upper_bound, lbound=d_lower_bound)
        if gcd(d, AAHPH) == 1:
            e = inverse_mod(d, AAHPH)
            if gcd(e, AAHPH) == 1:
                break
    return (N, e), (N, e, d, p, q)

'''
EDG.Clearlove
'''
beta = 0.4396

pk, sk = generate_params(beta)
N, e, d, p, q = sk
print('PLEASE WAIT...')
ZN = Zmod(N)
garbage_cipher = [ZN(jc) ^ e for jc in junk_cipher]

N, e = pk
troll = list(map(str, garbage_cipher)) + ['-' * 77, f'{N = }', f'{e = }']

e, d, g = 'Clearlove', 'LeeSin', '4396'
EDG = '\n'.join(troll)
with open('output.txt', 'w') as f:
    f.write(EDG)

首先肯定是要分解N的，然后观察参数的生成过程，发现定义了一个pq差值的界，那么大概率是以此为突破口。于是去找相关的论文，找到了Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits这篇论文，正好针对本题这种RSA变体。论文针对小|p-q|提出了一种连分数方法和CopperSmith方法，其临界条件分别为和。后者临界是比前者要大的，而本题数据只能满足后者，因此考虑采用CopperSmith攻击。

首先考虑如下关系： 定义，然后引入新的变量以降低xy项的指数，即。

然后与其它类似基于CopperSmith的攻击类似，构造多项式： 其中m和t是与参数有关的常量。然后对H中的多项式中包含的xy用u-1替换，并以某种偏序对单项式排列（实际上在生成G, H的过程中已经排好了）。再将上界代入单项式中得到矩阵L，对该矩阵构成的格进行LLL规约，可以重构出一些短向量构成的多项式，它们有公共根, 通过groebner基或者消元方法可以解得，进而与结合分解。

一些细节感兴趣可以具体去查看论文。

然后本题我在实际运行时发现m设置太小时分解不出来，自己测试了m=7时大概能分解delta=0.62左右的数据，delta再高一点就不行了。遂直接设置m=10，格规约等计算也是很耗时，跑了很久才跑出来。

分解N这一块儿的代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
lines=open('output3.txt','r').readlines()
cs=[ int(lines[i].strip()) for i in range(65536)]
exec(lines[65537].strip())
exec(lines[65538].strip())

delta=0.642
beta=0.4396
alpha=int(e).bit_length()/int(N).bit_length()

assert (delta < (2-sqrt(2*alpha*beta)))

P.<x, y, u> = PolynomialRing(ZZ)
X = 2 * ceil(N ^ (alpha + delta - 2))
Y = ceil(N ^ (2 * beta))
U = 2 * ceil(N ^ (alpha + delta + 2 * beta - 2))
tau = (2 - delta - 2 * beta) / (2 * beta)

m = 10
t = ceil(tau * m)
A = - ( (N - 1) ^ 2)
f = u + A * x

def replace_func(f):
    res=0
    for coe,exp in zip(f.coefficients(),f.exponents()):
        mi=min(exp[0],exp[1])
        tmp=coe * (u-1)^mi * x^(exp[0]-mi) * y^(exp[1]-mi) * u^exp[2]
        res+=tmp
    return res

polys=[]
for k in range(m + 1):
    for i in range(m - k + 1):
        g = x^i * f^k * e^(m-k)
        polys.append(g)

for i in range(1, t + 1):
    for k in range(floor(m/t) * i, m + 1):
        h = y^i * f^k * e^(m-k)
        polys.append(replace_func(h))

print(len(polys))

monomials=[]
for poly in polys:
    for v in poly.monomials():
        if v not in monomials:
            monomials.append(v)

mat = [[0 for j in range(len(monomials))] for i in range(len(polys))]
print(monomials)
for i, poly in enumerate(polys):
    for j, mono in enumerate(monomials):
        mat[i][j] = poly.monomial_coefficient(mono)*mono(X,Y,U)

#print(mat)
mat = Matrix(ZZ, mat)
mat = mat.LLL()
#open('mat2.txt','w').write(str(list(mat)))
#mat=eval(open('mat.txt','r').read())
print('LLL done!')
pols = []

for i in range(len(polys)):
    f = sum(mat[i][k] / monomials[k](X, Y, U) * monomials[k] for k in range(len(monomials)))
    pols.append(f)

print(len(pols))

pols = [u-x*y-1]+pols
#for i in range(len(pols)-1,3,-1):
for i in range(80,3,-1):
    print(i)
    try:
        v=Ideal(pols[:i]).variety(ring=ZZ)
        if len(v)>0:
           print(v)
           y=int(v[0]['y'])
           pmq=sqrt(y)
           print(pmq)
           P.<p>=PolynomialRing(ZZ)
           f=p^2+p*pmq-N
           print(f.roots())
    except Exception as e:
        print(e)
        pass


'''
[{u: -1695166360783623077154052389508246716761861722024404817214394600789803790403714200440369940787684400663494200881068944398548897575845907495606656469179282707827170529419212760406144142733347243197128881554680855071165806986096732724661579030640404199847619606235708970363609649328202045644653634610040799601597995193052707889314808055275816604399932498458439501479692477453686448515572462746542145553884637351688240966459098085476680544150909930373794916747700646448303, y: 7893799151870106368997715597004629614318877379147732503688536007499549221939769093779781858805544426360289846440239798972043620324852053072235936828334755393166491885822031250207242929799675100359166402558473234456030844109650292442936161876265905285215187501954746170896, x: -214746578696776713987299905475467568414024070212204855203647033887737055875538527514031663379363545097645608173370365619963730797249459248088432091685347829523013133246951132387167391403870749702699}]
[(-10145464108117104949338515959842773933364500202544475266126577386047458426369581988106804702576518219589482814270717140789491480763576506436948323698765533, 1), (10145464108117104946528925393253025011804035401616805446033365549148734952013370668386041469047007957274792466373040522919369708124243037663040944850113697, 1)]
'''

N分解之后，对garbage_cipher解RSA可以得到junk_cipher向量。该向量的构成形式如下： 然而这里n=65536，中间这个矩阵实在太大，根本就构建不出来，更别说求解了。然后我当时思路就断这儿了。后幸得队内高人指点，看到一篇博客，这才发现原来这就是个范德蒙方阵。而对于由1的n次根w构成的范德蒙方阵，其求逆也有简便的方法： 题目里是模域，而我们惊奇地发现给出的数据正好满足，那么可以直接用以上的逆矩阵求法。由于flag只在junk_message向量的前几十个元素中，我们无需求出整个逆矩阵去与junk_cipher向量相乘，只需要算前几十行即可，这样就在可以接受的时空复杂度范围内了。

后面这一块儿的解题过程如下：

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
from Crypto.Util.number import *
from tqdm import tqdm


lines=open('output3.txt','r').readlines()
cs=[ int(lines[i].strip()) for i in range(65536)]
exec(lines[65537].strip())
exec(lines[65538].strip())

P=10145464108117104946528925393253025011804035401616805446033365549148734952013370668386041469047007957274792466373040522919369708124243037663040944850113697
Q=N//P
d=inverse(e,(P-1)*(Q-1))
ZN=Zmod(N)
n=65536
jc=[pow(c,d,N) for c in cs[:n]]
#open('jc.txt','w').write(str(jc))
#jc=eval(open('jc.txt','r').read())
print('-----')
p = 990367536408524906540912485167816012092796554403092639917950993714265910699138052663068131070259292593771612112016905904144038137551264432483487958987773403759866096258076571660618998739176702013853258687325567753038298889168254166361474202422033630403618955865472205722190830457928271527937
g = 745013838642250986737914025336862504661062017981819269513542907265222774830330586097756124678061002877695509685688964126565784246358161149675046363463274308162223776270434432888284419417479549219965033745142547821863438374478028783067286583042510995247992045551680383288951502770625897136683
Zp = Zmod(p)
g = Zp(g)

flag=b''
jc=vector(Zp,jc)
for i in range(100):
    print(i)
    v=Zp(n)^-1*vector(Zp,[ g^-(i*j) for j in range(n)])
    jm=long_to_bytes(int(v*jc))
    flag+=bytes([jm[i]])
    print(flag)
print(flag)
#RCTF{G00d_J06_UR_cRypT0_ma5T3r__1997_L0VE_ZMJ_FOR3VER}

easyRSA

题目源码：

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
from Crypto.Util.number import getPrime, inverse, bytes_to_long

with open('flag.txt', 'rb') as f:
    flag = f.read()


def v(k):
    if k == 0:
        return 2
    if k == 1:
        return r
    return (r * v(k - 1) - v(k - 2)) % (N * N)


def encrypt(m, e, N):
    c = (1 + m * N) * v(e) % (N * N)
    return c


p = getPrime(512)
q = getPrime(512)
N = p * q
d = getPrime(512)
r = getPrime(512)
e = inverse(d, (p * p - 1) * (q * q - 1))
c = encrypt(bytes_to_long(flag), e, N)
print(f"e = {e}")
print(f"c = {c}")
print(f"N = {N}")

参考论文Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves.

论文4节中提到一种针对形式的连分数攻击，需要满足条件为： 代入题目数据计算发现右边为513bits，而d为512bits。因此对,连分数展开可以找到一个近似逼近等于。然后，与N=pq结合可以求出p和q。

然后题中的加密方式其实是基于Lucas序列的一种RSA变体。在拿到分解出的p和q之后，可以很轻松地利用该论文中2.3节的解密方法进行解密。求v的时候可以把迭代递归转化成矩阵相乘。

连分数分解：

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
from Crypto.Util.number import *
from gmpy2 import iroot
from tqdm import tqdm

e = 3121363059746835628022404544403822724460605553641332612055010587129451973002475126644668174294955070747985002800863652917895939538596303356113483509581841527286351537287500304267975061675901109982875778527827742120878835367386538561039072391997357702421691095861694681707017921391244519593945584755632901987840338065879901115934561426583008838453244051629340056867760923894623105542463500022221236457852502822707466528439969484890601953615303609725566617126458934095119670087068752543521167517461730977044465374505011791902510131823556603316457085145886999220426746234986984619161299098173535371540923264898459106461
c = 3023313363629909506923927199426293187583112749147539699346723655095868214179291222441307436555352537055690155418715652987685459938250844145450675418187664719327350488160722838989675928696633353180233455017609936874014883975932740217672705286265535646106053294507962613498142617741362730709360885118905440314573392981528077265110441270212385951070591696827167771592664502652520790612367259434545169836933571343480057141790292296952743986731389468760364416344837575740236416472589700581583016227273449673820568427641136163703116276104550877191839851640920430919278802098196408637904780725723268371465670950321881886863
N = 101946888552605033726177837709738163930032970477361664394564134626639467843553634920510447339985842689387519517553714582991506722045078696771986052246306068257957261478416093188640437503481862825381241480405463985516598520453211217206308826779669980833596066677262549841524134539729279446910817169620871929289

bound=int(sqrt((2*N^3-18*N^2)//e))
print(bound.bit_length())

c = continued_fraction(e/(N^2 - 9*N//4 + 1))
p,q = var('p q')
f1 = p * q - N
for i in tqdm(range(2,len(c))):
    k = c.numerator(i)
    d = c.denominator(i)
    w = (e * d - 1) // k
    if (N+1)^2 - w + 1  < 0:
        continue
    if iroot((N+1)^2 - w ,2)[1]:
        print(int(d).bit_length())
        W = int(iroot((N+1)^2 - w ,2)[0])
        f2 = p + q - W
        print(solve([f1,f2],[p,q]))
        break

Lucas解密：

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 *

p = 11183005686209595001928972121695860070092013480977374483129957127854844677143979460482157275466240702921372008061294251388860670887956597721784208073814949
q = 9116233275131173602739752692268079943189703035300573582575042083296621527313939933344455320687281588438414528000594454794847729159565419506066306192152661

e = 3121363059746835628022404544403822724460605553641332612055010587129451973002475126644668174294955070747985002800863652917895939538596303356113483509581841527286351537287500304267975061675901109982875778527827742120878835367386538561039072391997357702421691095861694681707017921391244519593945584755632901987840338065879901115934561426583008838453244051629340056867760923894623105542463500022221236457852502822707466528439969484890601953615303609725566617126458934095119670087068752543521167517461730977044465374505011791902510131823556603316457085145886999220426746234986984619161299098173535371540923264898459106461
c = 3023313363629909506923927199426293187583112749147539699346723655095868214179291222441307436555352537055690155418715652987685459938250844145450675418187664719327350488160722838989675928696633353180233455017609936874014883975932740217672705286265535646106053294507962613498142617741362730709360885118905440314573392981528077265110441270212385951070591696827167771592664502652520790612367259434545169836933571343480057141790292296952743986731389468760364416344837575740236416472589700581583016227273449673820568427641136163703116276104550877191839851640920430919278802098196408637904780725723268371465670950321881886863
N = 101946888552605033726177837709738163930032970477361664394564134626639467843553634920510447339985842689387519517553714582991506722045078696771986052246306068257957261478416093188640437503481862825381241480405463985516598520453211217206308826779669980833596066677262549841524134539729279446910817169620871929289
d = int(inverse(e,(p**2-1)*(q**2-1)))

def seq(r , k , n):
    init_v = vector(Zmod(n) , [2 , r])
    M = Matrix(Zmod(n) , [
        [0 , -1],
        [1 , r ]
    ])
    ret = ( init_v * M^(k-1))[1]
    return ret

invp=inverse(p,q)
invq=inverse(q,p)
ip=legendre_symbol(c^2-4,p)
dpip=inverse(int(e),p-ip)
iq=legendre_symbol(c^2-4,q)
dqiq=inverse(int(e),q-iq)
rp=int(seq(c%p,dpip,p))
rq=int(seq(c%q,dqiq,q))
r=(rp+p*(rp-rq)*invp)%N

vp=int(seq(r,e,p^2))
vq=int(seq(r,e,q^2))
tp=c*inverse(vp,p^2)%p^2
mp=((tp-1)//p)*invq%p
tq=c*inverse(vq,q^2)%q^2
mq=((tq-1)//q)*invp%q
m=(mp+p*(mq-mp)*invp)%N
print(long_to_bytes(m))
b'RCTF{eAsy_1uca5_se9uEnce_a6ea27d4177d}'

Guess

题目源码：

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
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint, choices
from string import ascii_uppercase, digits
import signal

with open('flag.txt', 'rb') as f:
    flag = f.read()

signal.alarm(300)

q = getPrime(160)
while True:
    key = "rctf_" + "".join(choices(ascii_uppercase + digits, k=15))
    x = bytes_to_long("".join(sorted(key)).encode())
    if x < q:
        break
l = 2
T = []
U = []
for i in range(90):
    t = randint(1, q)
    #u = (x * t - randint(1, q >> l)) % q
    u = x * t - randint(1, q >> l)
    T.append(t)
    U.append(u)

print(f"q = {q}")
print(f"T = {T}")
print(f"U = {U}")

guess = int(input("x = ").strip())
if guess == x:
    print(flag)

随机值影响很小，u//t可以得到x的近似值，测试一下然后发现直接发送u//t+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
from pwn import *
import re
import string
from Crypto.Util.number import *

#context.log_level = 'debug'

sh=remote('190.92.234.114',23334)
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud = lambda a     :sh.recvuntil(str(a),drop=True)

for _ in range(3):
	exec(rl().decode().strip())

arr=[u//t for u,t in zip(U,T)]
print(long_to_bytes(arr[0]))
#b'269FFIIIKMPQRSS_cfrs'
sla('x = ',str(arr[0]+1))

sh.interactive()
#RCTF{h0p3_this_gUes5_cHal1eNge_is_N0T_gue5sY}

RCTF2022 Crypto部分wp

https://litao6666.github.io/202212/4446a1ac.html

Author

zealot

Posted on

2022-12-16

Updated on

2022-12-16

Licensed under

Catalogue

×