2023柏鹭杯

发表于 分类于 阅读次数： Waline： 本文字数： 766 阅读时长 ≈ 3 分钟

记录2023柏鹭杯——Crypto前两题

给附件加密是有点让人难受的

fractRSA

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
#python3
import sys 
sys.path.append("..") 
from Crypto.Util.number import *
from random import *
from sage.all import *
from  secret import flag1 as flag

num1 = 3
num2 = 5
while(num1<num2):
    num1 = getPrime(512)
    num2 = getPrime(512)
pt = bytes_to_long(flag) + num2

ring = RealField(1100)
num3 = ring(num1) / ring(num2)
print("num3 = ", num3)

while True:
    p = randint(2**511, num1)
    q = randint(2**511, num2)
    if isPrime(p) and isPrime(q) and p!=q:
        break
 
N = p*q
e = 65537
leak = pow(p-q, num1, num1*num2)
ct = pow(pt, e, N)

print("ct = ", ct)
print("N = ", N)
print("leak = ", leak)

"""
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371
"""

$\because num_3 = \frac{num_1}{num_2}$，把$num_3$展开为连分数，加上一些限制条件即可获得$num_1$，$num_2$

获得$num_1$，$num_2$后，求逆元，解$(p-q)^{num_1} \mod num_1\times num_2$

然后解方程得到$p,q$

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

num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371
e = 65537

def Get_num(num3):
    cf = continued_fraction(num3)     #实数转为连分数
    frac_list = cf.convergents()      #返回连分数对象的收敛分数列表，也就是分子分母
    for i in frac_list:
        temp = str(i).split('/')      #为了分成分子分母
        if len(temp) == 2:
            a = int(temp[0])       #取分子
            b = int(temp[1])       #取分母
            if a.bit_length() == 512 and b.bit_length() == 512 and isPrime(a) and isPrime(b):
                num1 = a
                num2 = b
                return num1,num2

num1,num2 = Get_num(num3)
# print(num1)
# print(num2)

d = gmpy2.invert(num1,(num1-1)*(num2-1))
p_q = int(pow(leak,d,num1*num2))

var('p q')
f1 = p - q == p_q
f2 = p*q == N
ans = solve([f1,f2],[p,q])
# print(ans)

p = 8397652354751369475047895816963473478350245201262315191356674989898449420511844471318815750077346111978800531467822072132495108840045942922000560423170719
q = 7366431105165493870863104020012521226567717006209783271191581404475809252591732063142219903159720601508017444435289526877689688795190667050592115689909567
d_ = gmpy2.invert(e,(p-1)*(q-1))
m = pow(ct,d_,p*q)
flag = long_to_bytes(int(m - num2))
print(flag)
#flag{ISEC-WeMu5tKe2pOn_70in5And#N3Ver@G1veUp!}

Vigenere2S

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# python2

import sys
sys.path.append("..") 
from secret import key,flag2 as flag

def _l(idx, s):
    return s[idx:] + s[:idx]
def mainProc(p, k1, k2):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    t = [[_l((i+j)%len(s), s) for j in range(len(s))] for i in range(len(s))]
    i1 = 0
    i2 = 0
    c = b""
    for a in p:
        c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]
        i1 = (i1 + 1) % len(k1)
        i2 = (i2 + 1) % len(k2)
    return c
res = mainProc(flag,key,key[::-1])
print(res)

#密文：6JnsNxHKJ8mkvhS{rMO_c9apMfHDHObq80PMu{_ww_r{rq

加密过程

1
2
3
4
5
6
7
8
9
10
11
def mainProc(p, k1, k2):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    t = [[_l((i+j)%len(s), s) for j in range(len(s))] for i in range(len(s))]
    i1 = 0
    i2 = 0
    c = b""
    for a in p:
        c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]
        i1 = (i1 + 1) % len(k1)
        i2 = (i2 + 1) % len(k2)
    return c

等同于下面这个加密过程

1
2
3
4
5
6
7
8
9
10
def mainProc(p, k1, k2):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    i1 = 0
    i2 = 0
    c = b""
    for a in p:
        c += long_to_bytes(s[(s.find(a) + s.find(k1[i1]) + s.find(k2[i2])) % len(s)])
        i1 = (i1 + 1) % len(k1)
        i2 = (i2 + 1) % len(k2)
    return c

本质是c += s[m + k1 + k2]，就是说密文中的字符，是明文字母在字符串s中的位置，再右移k1+k2位

有个隐藏信息，flag头是flag{ISEC-}

我们可以利用flag的头，和密文的前10位相减，即可得到移位量k1+k2，再把他移动回去即可求得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
from Crypto.Util.number import *


def decrypt(c,tmp):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    i = 0
    message = b""
    for a in c:
        message += long_to_bytes(s[(s.find(a) - tmp[i]) % 65])
        i = (i+1) % len(tmp)
    return message

m = b"flag{ISEC-"
c = b"6JnsNxHKJ8mkvhS{rMO_c9apMfHDHObq80PMu{_ww_r{rq"

tmp = []
for i in range(len(m)):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    index = s.find(c[i])							#先找到密文在字符串s中的位置
    tmp.append((index - s.find(m[i])) % len(s))		  #做减法

tmp = tmp + tmp[::-1]
print(tmp)
flag = decrypt(c,tmp)
print(flag)
#flag{ISEC-Afr1en7_1nN33d_1S_Afr9end_ind88d0o0}
-------------已经到底啦！-------------