obstacle的个人空间

These are the days we won't forget

部分密码题目复现,后续应该会把没复现的几道题补上吧(或许吧

费克特尔

1
2
3
c=670610235999012099846283721569059674725712804950807955010725968103642359765806
n=810544624661213367964996895060815354972889892659483948276203088055391907479553
e=65537

简单的RSA,借助yafu对n进行质因数分解得到多了质数p1,p2,p3等。那么phi=(p1-1)(p2-1)(p3-1)·····

后续就正常RSA那一套解就好了。flag:TGCTF{f4888_6abdc_9c2bd_9036bb}

宝宝RSA

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
from math import gcd
from Crypto.Util.number import *
from secret import flag

# PART1
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1 * q1
phi = (p1 - 1) * (q1 - 1)
m1 = bytes_to_long(flag[:len(flag) // 2])
e1 = getPrime(18)
while gcd(e1, phi) != 1:
e1 = getPrime(17)
c1 = pow(m1, e1, n1)

print("p1 =", p1)
print("q1 =", q1)
print("c1 =", c1)

# PART2
n2 = getPrime(512) * getPrime(512)
e2 = 3
m2 = bytes_to_long(flag[len(flag) // 2:])
c2 = pow(m2, e2, n2)

print("n2 =", n2)
print("c2 =", c2)
print("e2 =", e2)

# p1 = 8362851990079664018649774360159786938757293294328116561219351503022492961843907118845919317399785168488103775809531198339213009936918460080250107807031483
# q1 = 8312546034426788223492083178829355192676175323324230533451989649056072814335528263136523605276378801682321623998646291206494179416941978672637426346496531
# c1 = 39711973075443303473292859404026809299317446021917391206568511014894789946819103680496756934914058521250438186214943037578346772475409633145435232816799913236259074769958139045997486622505579239448395807857034154142067866860431132262060279168752474990452298895511880964765819538256786616223902867436130100322
# n2 = 103873139604388138367962901582343595570773101048733694603978570485894317088745160532049473181477976966240986994452119002966492405873949673076731730953232584747066494028393377311943117296014622567610739232596396108513639030323602579269952539931712136467116373246367352649143304819856986264023237676167338361059
# c2 = 51380982170049779703682835988073709896409264083198805522051459033730166821511419536113492522308604225188048202917930917221
# e2 = 3

思路:flag拆成两部分,分别求出前后两部分然后合并即可。

前半部分知道p和q也知道e的大致范围(相对来说比较小)直接爆破即可,后半部分e很小可以进行爆破。

代码:

前半部分

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 sympy import primerange
from math import gcd
from Crypto.Util.number import long_to_bytes
import gmpy2

# 17位素数范围:2^16到2^17-1
primes_17 = list(primerange(2**16, 2**17))
# 18位素数范围:2^17到2^18-1
primes_18 = list(primerange(2**17, 2**18))
candidates = primes_17 + primes_18
p1 = 8362851990079664018649774360159786938757293294328116561219351503022492961843907118845919317399785168488103775809531198339213009936918460080250107807031483
q1 = 8312546034426788223492083178829355192676175323324230533451989649056072814335528263136523605276378801682321623998646291206494179416941978672637426346496531
phi = (p1 - 1) * (q1 - 1)
valid_e = [e for e in candidates if gcd(e, phi) == 1]

c1 = 39711973075443303473292859404026809299317446021917391206568511014894789946819103680496756934914058521250438186214943037578346772475409633145435232816799913236259074769958139045997486622505579239448395807857034154142067866860431132262060279168752474990452298895511880964765819538256786616223902867436130100322
n1 = p1 * q1

for e in valid_e:
d = pow(e, -1, phi)
m1 = pow(c1, d, n1)
flag_part = long_to_bytes(m1)
if b'TGCTF' in flag_part: # 根据预期flag格式调整
print(flag_part.decode())
break
#TGCTF{!!3xP_Is_S

后半部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from sympy import primerange
from math import gcd
from Crypto.Util.number import long_to_bytes
import gmpy2




n2 = 103873139604388138367962901582343595570773101048733694603978570485894317088745160532049473181477976966240986994452119002966492405873949673076731730953232584747066494028393377311943117296014622567610739232596396108513639030323602579269952539931712136467116373246367352649143304819856986264023237676167338361059
c2 = 51380982170049779703682835988073709896409264083198805522051459033730166821511419536113492522308604225188048202917930917221
e2 = 3
k = 0
while 1:
res = gmpy2.iroot(k*n2+c2,e2)
if(res[1] == True):
print(bytes.fromhex(hex(res[0])[2:]))
break
k += 1
#m@ll_But_D@ng3r0}

tRwSiAns

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

def generate_key(bits=512):
p = getPrime(bits)
q = getPrime(bits)
return p * q, 3


def hash(x):
return int(hashlib.md5(str(x).encode()).hexdigest(), 16)


def encrypt(m, n, e):
x1, x2 = 307, 7
c1 = pow(m + hash(x1), e, n)
c2 = pow(m + hash(x2), e, n)
return c1, c2


m = bytes_to_long(FLAG)
n, e = generate_key()
c1, c2 = encrypt(m, n, e)
print(f"n = {n}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

n = 100885785256342169056765112203447042910886647238787490462506364977429519290706204521984596783537199842140535823208433284571495132415960381175163434675775328905396713032321690195499705998621049971024487732085874710868565606249892231863632731481840542506411757024315315311788336796336407286355303887021285839839
e = 3
c1 = 41973910895747673899187679417443865074160589754180118442365040608786257167532976519645413349472355652086604920132172274308809002827286937134629295632868623764934042989648498006706284984313078230848738989331579140105876643369041029438708179499450424414752031366276378743595588425043730563346092854896545408366
c2 = 41973912583926901518444642835111314526720967879172223986535984124576403651553273447618087600591347032422378272332279802860926604693828116337548053006928860031338938935746179912330961194768693506712533420818446672613053888256943921222915644107389736912059397747390472331492265060448066180414639931364582445814

Franklin-Reiter 相关消息攻击 两个密文对应的消息存在线性关系.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import long_to_bytes
import hashlib

def hash(x):
return int(hashlib.md5(str(x).encode()).hexdigest(), 16)

h1 = hash(307)
h2 = hash(7)


n = 100885785256342169056765112203447042910886647238787490462506364977429519290706204521984596783537199842140535823208433284571495132415960381175163434675775328905396713032321690195499705998621049971024487732085874710868565606249892231863632731481840542506411757024315315311788336796336407286355303887021285839839
e=3
delta = h1 - h2
c1 = 41973910895747673899187679417443865074160589754180118442365040608786257167532976519645413349472355652086604920132172274308809002827286937134629295632868623764934042989648498006706284984313078230848738989331579140105876643369041029438708179499450424414752031366276378743595588425043730563346092854896545408366
c2 = 41973912583926901518444642835111314526720967879172223986535984124576403651553273447618087600591347032422378272332279802860926604693828116337548053006928860031338938935746179912330961194768693506712533420818446672613053888256943921222915644107389736912059397747390472331492265060448066180414639931364582445814

R.<s> = PolynomialRing(Zmod(n))
f = (s+h1)^3 - c1
g = (s +h2)^3 - c2
flag = -gcd(f, g)[0]

print(long_to_bytes(int(flag)))
#TGCTF{RS4_Tw1nZ_d0You_th1nk_ItS_fun_2win?!!!1111111111}

LLLCG

咕咕咕,后续这题应该不搞了,大概去看LCG相关的题学习一下就好了

EZRSA

咕咕咕,这题emmmm也不搞了吧,学习一下p的低位泄露然后就过。

1.univariate

题目

描述

1
I love univariate polynomials...
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 secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q

m = bytes_to_long(flag.encode())
e = 65537
c = pow(m,e,n)

P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]

terms = [x**i for i in range(137)]

T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]

f = sum([term*coef for term,coef in zip(terms,coefs)])
w = pow(2,f(p),n)

with open('out.txt', 'w') as file:
file.write(f'{n = }\n')
file.write(f'{e = }\n')
file.write(f'{c = }\n')
file.write(f'{f = }\n')
file.write(f'{w = }\n')
n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221

思路:
根据题目描述univariate polynomials(单变量多项式),题目中也是反复利用p,所以可以从p开始下手。 从 w = pow(2,f(p),n)开始,这里也是我学习中感觉非常巧妙的地方,先了解前提知识费马小定理gcd(a,p)=1,$a^{p-1}\equiv 1\pmod{p}$,于是接下来就要构造出p-1。对f(p)模(p-1),就有f(p) = g(p)(p-1) + k。然后对w取p的模数。
$$
w = 2^{f(p)} = 2^{g(p)(p-1) + k} = \left(2^{g(p)(p-1)}\right) \cdot \left(2^k\right)=2^k \pmod{p}
$$
所以w除以p的模数就为2^k, 那么$w-2^{k}$​就为p的倍数,然后再与n取最大公约数就可以找出p从而解决RSA问题。即gcd(w-2^k,n).

代码(错误的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *

P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]

n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221


k = f % (x-1)
k_int=ZZ(k)
q = GCD(w -2^k_int, n)
p = n // q

print(long_to_bytes(int(pow(c, inverse(e, (p-1)*(q-1)), n))))

代码报错了,检查大概知道了原因在于k的值最后是负数,所以直接2^k不行。

正确部分

1
2
3
4
5
k = f % (x-1)

p = GCD(w * pow(2, -k, n) - 1, n)
q = n // p
#b'ictf{p-1_g0es_aB$olU7eLy_w1lD!!!}'

解释:当k是负数时, $2^{k}\pmod{n}$实际上是$2^{-\lvert k\rvert }\pmod{n}$的模逆元。这是因为指数运算是周期性的,且模逆元可以看作是将指数“翻转”到模数的范围内。pow(2, -k, n) 计算的是 $2^{k}\pmod{n}$ 的模逆元。如果 k是负数,这意味着我们正在寻找一个数 y 使得 $2^{k}*y\equiv 1\pmod{n}$,然后乘上w再减1就是与n有共同因子。勉强理解是这样,但我数学这方面并未深入研究,所以个人感觉纠错推导过程有点牵强,日后有新理解再做修改吧。

中国剩余定理(CRT)

在做题时遇到离散对数问题中碰到很多CRT相关知识,但最初了解比较浅显,现在准备再稍微细致的回顾一下。

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中$n_1$ $n_2$ ······$n_k$ 两两互质):

$$
\begin{cases} x\equiv a_1 \pmod{n_1}\\ x\equiv a_2 \pmod{n_2}\\ x\equiv a_3 \pmod{n_3}\\ ·····\\ ·····\\ ·····\\ x\equiv a_k \pmod{n_k} \end{cases}
$$

过程

1.计算所有模数的积 n;n=$n_1*n_2*···n_k$

2.对于第 i个方程:

​ a.计算$m_i=n/n_i$;

​ b.计算$m_i在模n_i意义下的逆元m_i^{-1}$; 逆元$m_im_i^{-1}\equiv 1\pmod{n_i}$

​ c.计算$c_i=m_im_i^{-1}$

3.方程组在模n意义下的唯一解为$x=\sum_{i=1}^{k}{a_ic_i}\pmod{n}$

代码

1
2
3
4
5
6
7
8
9
10
11
12

def CRT(k, a, r):
n = 1
ans = 0
for i in range(1, k + 1):
n = n * r[i]
for i in range(1, k + 1):
m = n // r[i]
b =y=0
exgcd(m, r[i], b, y) # b * m mod r[i] = 1 exgcd是另一个用来求逆元的自定义函数未标
ans = (ans + a[i] * m * b % n) % n
return (ans % n + n) % n

当然了上述代码可能更多用于算法题中,密码学里python有很多强大的库可以直接调用CRT

1
2
3
4
from sympy.ntheory.modular import crt
a_list=[a1,a2,a3,····ak]
n_list=[n1,n2,n3,····nk]
x,n=crt(n_list,c_list) //crt会返回一个元组(x,N)其中x就是我们所需要的通解,n就是所有模数(n1,n2等)的乘积

证明

虽然说密码学里直接秒了,但我还是觉得搞清背后逻辑会更有理解。

$当i\neq j时,有m_j\equiv 0 \pmod{n_i}$

$这是因为m_j=n/n_j$

$所以c_j \equiv 0 \pmod{n_i},c_i\equiv 1 \pmod{n_i} $

$ x \equiv \sum_{j=1}^{k}{a_jc_j} \equiv a_ic_i\equiv a_i\pmod{n_i}$

$对于任意的i的取值均符合x\equiv a_i \pmod{n_i}$

所以上述方法可行

RSA中leak=p^q%n + q^p%n问题

以ISCTF2024crypto蓝鲨的费马这道题为例子讲解自己学到的一个解决方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import libnum
import gmpy2
from Crypto.Util.number import *
flag=b'ISCTF{********}'
m=bytes_to_long(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=0x10001
c=pow(m,e,n)
d=inverse(e,(p-1)*(q-1))
leak = (d+(pow(p,q,n)+pow(q,p,n)))%n
print("c=", c)
print("n=", n)
print("leak=", leak)
"""
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
"""

$1.\text{leak} = d + p + q$ 其中 leak 简写为 L

$2. m = \text{pow}(c, d, n),即 m = c^d \mod n.$

$3.d = L - (p + q) .$

根据欧拉函数的定义:$\phi = (p - 1)(q - 1) = pq - p - q + 1$

由于 n = pq ,因此:$\phi = n + 1 - (p + q)$

根据欧拉定理:$c^\phi \equiv1 \mod n$

代入 $\phi$的表达式:$c^{n + 1 - (p + q)} \equiv 1 \mod n$

可以进一步推导:$c^{n + 1} \equiv c^{p + q} \mod n$

因此:$c^{n + 1} \equiv c^{p + q} \mod n$

已知 d = L - (p + q) ,代入 $c^d \mod n = m$ :

$c^{L - (p + q)} \mod n = m$

根据前面的推导:$c^{n + 1} \equiv c^{p + q} \mod n$

因此:$c^{L - (n + 1)} \mod n = m$

$m = \text{pow}(c, L - n - 1, n)$

1
2
3
4
5
6
7
8
9
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
from Crypto.Util.number import long_to_bytes, inverse
m=pow(c,leak-n-1,n)
print(m)
flag=long_to_bytes(m)
print(flag)
#b'ISCTF{u_got_it}'

总结一下hgame week2crypto部分。自己虽然学了一段时间,结果week1密码一道没做出来,还是非常遗憾的,所幸week2密码是ak了的

CRYPTO

1.ancient recall

题目:

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
import random

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
card = random.choice(tarot)
if card not in cards:
cards.append(card)
if card in Major_Arcana:
k = random.choice(reversals)
Value.append(tarot.index(card)^k)
if k == -1:
YOUR_initial_FATE.append("re-"+card)
else:
YOUR_initial_FATE.append(card)
else:
Value.append(tarot.index(card))
YOUR_initial_FATE.append(card)
else:
continue
print("Oops!lets reverse 1T!")

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")

YOUR_final_Value = Value
def Fortune_wheel(FATE):
FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
return FATEd

for i in range(250):
YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
YOUR_final_FATE.append(tarot[i%78])
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

emmmm,自己看不太懂,但题目应该比较简单,丢给ai直接解出来(

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
Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
def reverse_step(B):
B0, B1, B2, B3, B4 = B
numerator = B0 + B1 + B3 - B2 - B4
if numerator % 2 != 0:
raise ValueError("奇数无法整除")
A1 = numerator // 2
A0 = B0 - A1
A2 = B1 - A1
A3 = B2 - A2
A4 = B3 - A3
if A4 + A0 != B4:
raise ValueError("验证失败")
return [A0, A1, A2, A3, A4]
final_values = [
2532951952066291774890498369114195917240794704918210520571067085311474675019,
2532951952066291774890327666074100357898023013105443178881294700381509795270,
2532951952066291774890554459287276604903130315859258544173068376967072335730,
2532951952066291774890865328241532885391510162611534514014409174284299139015,
2532951952066291774890830662608134156017946376309989934175833913921142609334
]
current = final_values.copy()
for _ in range(250):
current = reverse_step(current)
def get_card(v):
for k in range(22):
if k ^ -1 == v:
return f"re-{Major_Arcana[k]}"
index = v % 78
card = tarot[index]
if card in Major_Arcana and v == index:
return card
return card
cards = [get_card(v) for v in current]
flag = "hgame{" + "&".join(cards).replace(" ", "_") + "}"
print(flag)
#hgame{re-The_Moon&re-The_Sun&Judgement&re-Temperance&Six_of_Cups}

2.Intergalactic Bound

题目:

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
return x3, y3


def mul_THCurve(n, P):
R = (0, 0)
while n > 0:
if n % 2 == 1:
R = add_THCurve(R, P)
P = add_THCurve(P, P)
n = n // 2
return R


p = getPrime(96)
a = randint(1, p)
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
x = randint(1, p)
Q = mul_THCurve(x, G)
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

add_THcurve部分符合符合https://www.hyperelliptic.org/EFD/g1p/auto-twistedhessian.html 的定义。 所以按照文章里套换元 x’=X/Z y’=Y/Z 得到 ax’^3+y’^3+z’^3=dx’y’z’这样构造出了齐次式子之后就可以构造椭圆曲线了。所以现在只需要求a的值即可代入脚本求解。因为

1
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p

利用G和Q构造方程解出a

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
p = 55099055368053948610276786301
Gx = 19663446762962927633037926740
Gy = 35074412430915656071777015320
Qx = 26805137673536635825884330180
Qy = 26376833112609309475951186883
# 计算 Gy^3 + 1 mod p
Gy_cubed = pow(Gy, 3, p)
Gy_cubed_plus_1 = (Gy_cubed + 1) % p
# 计算 Qy^3 + 1 mod p
Qy_cubed = pow(Qy, 3, p)
Qy_cubed_plus_1 = (Qy_cubed + 1) % p
# 计算分子:(Gy^3+1)*Qx*Qy - (Qy^3+1)*Gx*Gy mod p
term1 = (Gy_cubed_plus_1 * Qx) % p
term1 = (term1 * Qy) % p
term2 = (Qy_cubed_plus_1 * Gx) % p
term2 = (term2 * Gy) % p
numerator = (term1 - term2) % p
# 计算分母:Qx^3*Gx*Gy - Gx^3*Qx*Qy mod p
Qx_cubed = pow(Qx, 3, p)
term3 = (Qx_cubed * Gx) % p
term3 = (term3 * Gy) % p
Gx_cubed = pow(Gx, 3, p)
term4 = (Gx_cubed * Qx) % p
term4 = (term4 * Qy) % p
denominator = (term3 - term4) % p
# 计算逆元
inv_denominator = pow(denominator, -1, p)
a = (numerator * inv_denominator) % p
print(a)
#a=39081810733380615260725035189

求得a的值构建出椭圆曲线后使用 Pohlig Hellman 即可解出 Q = xG 中的 x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
a = 39081810733380615260725035189
p = 55099055368053948610276786301
P = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
d = (a * Q[0] ** 3 + Q[1] ** 3 + 1) * inverse(Q[0] * Q[1], p) % p
# construct ECC to get a solution of aX^3+Y^3+Z^3=dXYZ
R.<x,y,z> = Zmod(p)[]
cubic = a * x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
P_ord = P.order()
def Pohlig_Hellman(n, P, Q):
return discrete_log(Q, P, ord=n, operation='+')
x = Pohlig_Hellman(P_ord,P,Q)
print(x)
#x=2633177798829352921583206736
1
2
3
4
5
6
7
8
9
10
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
x = 2633177798829352921583206736
key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
decrypted_flag = unpad(cipher.decrypt(ciphertext), 16)
print(f"解密后的数据: {decrypted_flag}")
#解密后的数据: b'hgame{N0th1ng_bu7_up_Up_UP!}'

3.Spica

题目:

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 getPrime, long_to_bytes,bytes_to_long
from secrets import flag
from sage.all import *

def derive_M(n):
iota=0.035
Mbits=int(2 * iota * n^2 + n * log(n,2))
M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
return Integer(M)

m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A

with open("data.txt", "w") as file:
file.write(str(m) + "\n")
file.write(str(p) + "\n")
for item in h:
file.write(str(item) + "\n")

隐子集和问题(HSSP / Hidden Subset Sum Problem)。解题参考:https://yanmo312.github.io/2022/11/26/gemima_6/#%E4%B8%89%E3%80%81%E9%9A%90%E5%AD%90%E9%9B%86%E5%92%8C%E9%97%AE%E9%A2%98%EF%BC%88HSSP-Hidden-Subset-Sum-Problem%EF%BC%89

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
from Crypto.Util.number import *
from sage.all import *
import time
def read_data(filename):
with open(filename, 'r') as f:
m = int(f.readline().strip())
n = 70
p = int(f.readline().strip())
h_line = f.readline().strip()
w = list(map(int, h_line[1:-1].split(', ')))
return m, n, p, w
# 生成 orthoLattice 的相关函数
def orthoLattice(b, x0):
m = b.length()
M = Matrix(ZZ, m, m)
# 生成正交矩阵
for i in range(1, m):
M[i, i] = 1
M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
M[0, 0] = x0
for i in range(1, m):
M[i, 0] = mod(M[i, 0], x0)
return M
def allpmones(v):
return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)
def allones(v):
if all(vj in (0, 1) for vj in v):
return v
if all(vj in (0, -1) for vj in v):
return -v
return None
# 恢复只包含 {0,1} 或 {-1,0,1} 的向量
def recoverBinary(M5):
lv = [allones(vi) for vi in M5 if allones(vi)]
n = M5.nrows()
for v in lv:
for i in range(n):
nv = allones(M5[i] - v)
if nv and nv not in lv:
lv.append(nv)
nv = allones(M5[i] + v)
if nv and nv not in lv:
lv.append(nv)
return Matrix(lv)
def kernelLLL(M):
n = M.nrows()
m = M.ncols()
if m < 2 * n:
return M.right_kernel().matrix()
K = 2 ^ (m // 2) * M.height()
MB = Matrix(ZZ, m + n, m)
MB[:n] = K * M
MB[n:] = identity_matrix(m)
MB2 = MB.T.LLL().T
assert MB2[:n, : m - n] == 0
Ke = MB2[n:, : m - n].T
return Ke
def attack(m, n, p, w):
print("n =", n, "m =", m)
iota = 0.035
nx0 = int(2 * iota * n^2 + n * log(n, 2))
print("nx0 =", nx0)
x0 = p
b = vector(w)
M = orthoLattice(b, x0)
t = time.time()
M2 = M.LLL()
print("LLL step1: %.1f" % (time.time() - t))
MOrtho = M2[: m - n]
print("log(Height, 2) = ", int(log(MOrtho.height(), 2)))
t2 = time.time()
ke = kernelLLL(MOrtho)
print("Kernel: %.1f" % (time.time() - t2))
if n > 170:
return
beta = 2
tbk = time.time()
while beta < n:
if beta == 2:
M5 = ke.LLL()
else:
M5 = M5.BKZ(block_size=beta)
if len([True for v in M5 if allpmones(v)]) == n:
break
if beta == 2:
beta = 10
else:
beta += 10
print("BKZ beta=%d: %.1f" % (beta, time.time() - tbk))
t2 = time.time()
MB = recoverBinary(M5)
print("Recovery: %.1f" % (time.time() - t2))
print("Number of recovered vector = ", MB.nrows())
print("Number of recovered vector.T = ", MB.ncols())
return MB
m, n, p, w = read_data('data.txt')
res = attack(m, n, p, w)
def bits_to_long(bits):
return int(''.join(str(bit) for bit in bits), 2)
def extract_flags(MB):
flags = []
# 遍历 MB 的每一行,将每一行转换为一个二进制数字
for row in MB:
flag_bits = [int(element) for element in row] # 获取每行的二进制位
flag_long = bits_to_long(flag_bits) # 转换为整数
flag = long_to_bytes(flag_long) # 转换为字节串
flags.append(flag)
return flags
flags = extract_flags(res)
for flag in flags:
print(f"Recovered flag: {flag}")
#Recovered flag: b'hgame{U_f0und_3he_5pec14l_0n3!}'

感觉代码最后加个对flag的处理,判断只有符合hgame{}格式的flag输出会好点(但数据不是很大,还是一眼就从输出里找到正确flag)。输出部分还是很好找的是吧(

最后说明这是第一次尝试写wp,肯定有很多不足之处,会继续在日后一点一点完善这个过程。

懒惰的我终于开始初步学习密码学中格的相关内容了,虽然很早之前就看过了,但是由于东西实在是太多了根本看不下去,看了也不理解。现在再次开始密码学之路,这篇文章算是边学边理解的感悟吧。

格的认识

经过学长的点明后,对于我目前学习最初步的格来说就把格理解为线性向量,把线性代数的知识运用上去,无非就是换了很多全新的名词,本质上按线性向量去理解会轻松很多。所以说还是要有一定线代基础不然还是很难接受(但线代本身也确实很抽象😢)

problem

目前看过来分为svp(shortest vector problem)最短向量问题和cvp(closest vector problem)最近向量问题。两个名字看中文感觉就是一回事最短和最近,但事实上区别很大。

SVP

感觉正式讲法很难理解,我自己想法就是格中有一组基向量【b1,b2】以及很多点,要通过基向量找到一个点,使得这个点离原点最近,而λ1就是最短向量。有时候因为基的点分布并不理想,很多时候找出来的是最短向量λ1的倍数,这就是svp的宽松版本了。svp

CVP

在基中找一个点t,找到距离这个点最近的格点。换句话理解就是找到一个向量λ1使得t向量(蓝色线)与λ1相减后得到的向量μ最短。同样存在cvp的宽松版本,如图中2μ,只不过目前我对于宽松版本还未很好理解。cvp

LLL算法

嗯感觉这个原理非常复杂,想理解目前水平做不到,差不多想就是LLL是一个格基约化算法,作用是将上面图片中格变得更加整齐(就是把图中倾斜绿色点变得和坐标轴一样整齐)。反正目前做一些初步题大概就是按题目意思构造一个合理的格然后对格直接用LLL.( )会得到一个短向量,然后从这些向量中可以找到我们需要的,然后差不多就可以解出题目。所以不需要理解直接用吧😢然后顺带提一下BKZ算法,也是理解为更高级的LLL,直接用别管原理什么的。

前言:前段时间在写pta上面的代码题时遇到一个查找字符串字串的问题,一开始采取i,j循环遍历的方法暴力寻找,但是很可惜时间复杂度上出现问题,于是经过学习,初步尝试运用kmp算法来解决查找字符串字串中时间复杂度的问题。

对kmp的名称由来等就不展开描述了直接进入代码部分。

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
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0,i=1; // 当前最长前缀后缀长度
lps[0] = 0; // lps[0] 总是为 0
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0) // 不匹配时,根据 lps 数组更新 len
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
int* lps = (int*)malloc(M * sizeof(int)); // 创建 lps 数组
computeLPSArray(pat, M, lps);
int i = 0; // txt 的索引
int j = 0; // pat 的索引
while (i < N)
{
if (pat[j] == txt[i])
{
i++;
j++;
}
if (j == M)
{
printf("找到模式字符串 '%s' 的起始位置: %d\n", pat, i - j);
j = lps[j - 1];
}
else if(i < N && pat[j] != txt[i])
{
if (j != 0) // 字符不匹配
{
j = lps[j - 1];
} else
{
i++;
}
}
}
}
int main(){
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}

个人理解,掌握kmp算法的关键就是掌握lps数组的构造(网上大部分也称next数组,就把lps换成next),lps数组也就是找字串中的最大公共前后缀,它可以帮助我们查找子串时优化“回溯”过程,因为用i,j单纯暴力循环每次都要回到最初会有很多浪费,利用lps数组的构造就可以优化这个过程。具体概念理解,以及构造思路还需要在网络上自己找视频理解。

接下来是pta里面的一道题,运用kmp算法解决。

7-11 删除字符串中的子串

分数 10

作者 白洪欢

单位 浙江大学

输入2个字符串S1和S2,要求删除字符串S1中出现的所有子串S2,即结果字符串中不能包含S2。

输入格式:

输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串,对应S1和S2。

输出格式:

在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。

输入样例:

1
2
Tomcat is a male ccatat
cat

输出样例:

1
Tom is a male 

下面是通过代码

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 计算LPS(最长前缀后缀)数组
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0; // 当前最长前缀长度
lps[0] = 0; // lps[0] 总是为 0
int i = 1; // 从 lps[1] 开始计算
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1]; // 根据 lps 更新 len
} else {
lps[i] = 0;
i++;
}
}
}
}
// KMP搜索算法 - 查找并删除所有出现的子串
void KMPSearchAndDelete(char* txt, char* pat) {
int M = strlen(pat);
int N = strlen(txt);
int* lps = (int*)malloc(M * sizeof(int));
computeLPSArray(pat, M, lps);
int i = 0; // 主串的索引
int j = 0; // 模式串的索引
while (i < N) {
if (pat[j] == txt[i]) {
i++;
j++;
}
if (j == M) {
// 找到一个匹配,删除子串
memmove(&txt[i - j], &txt[i], N - i + 1); // 移动后面的字符
N -= j; // 更新主串长度
txt[N] = '\0'; // 确保以'\0'结束

// 重置j为0,继续寻找进一步的匹配
j = 0;
i = 0; // 从头再继续检查
} else if (i < N && pat[j] != txt[i]) {
if (j != 0) {
j = lps[j - 1]; // 根据lps调整j
} else {
i++;
}
}
}
free(lps); // 释放内存
}
int main() {
char s1[256]; // 增大数组大小以容纳更长的字符串
char s2[81];
fgets(s1, sizeof(s1), stdin);
s1[strcspn(s1, "\n")] = 0; // 去掉换行符
fgets(s2, sizeof(s2), stdin);
s2[strcspn(s2, "\n")] = 0; // 去掉换行符
// 持续删除子串直到找不到为止
while (strstr(s1, s2) != NULL) {
KMPSearchAndDelete(s1, s2); // 查找并删除子串
}
printf("%s\n", s1); // 输出结果
return 0;
}


1.图片

往typora插入图片,图片文件夹一定要和创建的.md文件夹放在同一个文件夹下。不然文件移动位置后图片会因找不到地址而消失

1
2
格式![提示文字](图片地址)      即先!然后快捷键ctrl+k
例如:![伊蕾娜](D:\blog\source\images\Elaina.jpg)

问题

相信很多人尝试上面图片的插入方法会遇到在typora能正常显示图片,但在网页上图片却无法加载。这是因为上述地址如D:\blog\source\images\Elaina.jpg为本地地址,而hexo+github搭建的博客并不能访问本地地址所以自然无法成功。

解决

最简单粗暴的方法就是直接将图片拖到typora中,typora会直接创建博客文章同名的文件夹存放图片。但是就是感觉文章写多了有点乱乱的。

typora功能初步尝试

1.标题

一级标题:ctrl+1或#
二级标题:ctrl+2或##
剩下的三级四级等就可以以此类推了

2.文字

删除线:alt+shift+5 示例 ~~~~
加粗:ctrl+B 示例 加粗
斜体:ctrl+I 示例 斜体
下划线:ctrl+U 示例 下划线
高亮:==中间内容==

3.表情包

:smile: :100: :heart: 快捷键:windows+;

4.表格

week2 week3 week4

快捷键:ctrl+t

5.引用

一级应用

二级引用

瑞典厨师长

6.代码

1
插入不确定代码,快捷键:ctrl+shift+k

7.分隔线


*** 然后回车

8.源代码模式

ctrl+/,退出一样

9.跳转

1.跳转到外部

bilibili
屑魔女的个人博客

1
快捷键:ctrl+k      格式[提示文字](网址)

2.跳转到内部

[博客](#my first blog)

1
快捷键:CTRL+k     [提示文字](#标题)

10.自动链接

使用<>然后括号里链接会自动转化为超链接

11.图片

往typora插入图片,图片文件夹一定要和创建的.md文件夹放在同一个文件夹下。不然文件移动位置后图片会因找不到地址而消失

1
2
格式![提示文字](图片地址)      即先!然后快捷键ctrl+k
例如:![伊蕾娜](D:\blog\source\images\Elaina.jpg)

伊蕾娜

尝试用typora写一篇博客,此文章仅做测试使用

0%