2024022701-信息安全(二)——密码学

密码学的基本概念

密码学(Cryptology):

研究信息系统安全保密的科学。

密码编码学(Cryptography):

研究对信息进行编码,实现对信息的隐蔽。

密码分析学(Cryptanalytics) :

研究加密消息的破译或消息的伪造。

消息被称为明文(Plaintext)。

用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption),被加密的消息称为密文(Ciphertext),而把密文转变为明文的过程称为解密(Decryption)。

密码算法:

用于加密和解密的数学函数。
密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm)。\所传送消息的预定对象称为接收者(Receiver)。接收者对密文解密所采用的一组规则称为*解密算法(Decryption Algorithm)

加密过程
密码学的目的:Alice和Bob两个人在不安全的信道上进行通信,而破译者Oscar不能理解他们通信的内容。
在这里插入图片描述
加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key)。
在这里插入图片描述

密码体制
一个五元组(P,C,K,E,D)满足条件:

  1. P是可能明文的有限集;(明文空间)
  2. C是可能密文的有限集;(密文空间)
  3. K是一切可能密钥构成的有限集;(密钥空间)
  4. 任意k∈K,有一个加密算法ek∈E和相应的解密算法dk∈D,使得ek : P→C和dk : C→P分别为加密解密函数,满足dk(ek(x))=x,其中 x ∈P。

加密算法基本原理
代替:明文中的元素映射成另一个元素
置换 :重新排列
要求:不允许信息丢失,即算法可逆

基于密钥的算法,按照密钥的特点分类:
对称密码算法(symmetric cipher):加密密钥和解密密钥相同,或实质上等同,即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。
非对称密钥算法(asymmetric cipher):加密密钥和解密密钥不相同,从一个很难推出另一个。又称公开密钥算法(public-key cipher) 。

密码分析破解类型:

  1. 唯密文攻击
    密码分析者仅知道有限数量用同一个密钥加密的密文
  2. 已知明文攻击
    密码分析者除了拥有有限数量的密文外,还有数量限定的一些已知“明文—密文”对
  3. 选择明文攻击
    密码分析者除了拥有有限数量的密文外,还有机会使用注入了未知密钥的加密机,通过自由选择明文来获取所希望的“明文—密文”对。
  4. 选择密文攻击
    密码分析者除了拥有有限数量的密文外,还有机会使用注入了未知密钥的解密机,通过自由选择密文来获取所希望的“密文—明文”对。
  5. 选择文本攻击

密码的安全性
无条件安全(Unconditionally secure)
无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性。(除一次一密钥,都不是无条件安全)
计算上安全(Computationally secure)
破译的代价超出信息本身的价值
破译的时间超出了信息的有效期

现代密码学基本原则
设计加密系统时,总假定密码算法是可以公开的,需要保密的是密钥。“一切秘密在于密钥之中,而加密算法可以公开” 即Kerckhoff原则。

密码学的起源和发展三个阶段:
1949年之前:密码学是一门艺术

古典密码(classical cryptography)
隐写术(steganography):不同于加密。
如果把一封信锁在保险柜中,把保险柜藏在纽约的某个地方…,然后告诉你去看这封信。这并不是安全,而是隐藏。

1949~1975年:密码学成为科学

计算机使得基于复杂计算的密码成为可能
1949年Shannon的“The Communication Theory of Secret Systems”
1967年David Kahn的《The Codebreakers》
1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告
Smith,J.L.,The Design of Lucifer, A Cryptographic Device for Data Communication, 1971
Smith,J.L.,…,An Expremental Application of Cryptogrphy to a remotely Accessed Data System, Aug.1972
Feistel,H.,Cryptography and Computer Privacy, May 1973
数据的安全基于密钥而不是算法的保密

1976年以后:密码学的新方向——公钥密码学

1976年Diffie & Hellman的“New Directions in Cryptography”提出了不对称密钥密码
1977年Rivest,Shamir & Adleman提出了RSA公钥算法
90年代逐步出现椭圆曲线等其他公钥算法
公钥密码使得发送端和接收端无密钥传输的保密通信成为可能!
1977年DES正式成为标准80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等
90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS,Twofish,Serpent等出现
2001年Rijndael成为DES的替代者

经典密码体制

代替密码(substitution cipher)

就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。

简单代替密码(simple substitution cipher):
又称单字母密码(monoalphabetic cipher),明文的一个字符用相应的一个密文字符代替。

多字母密码(ployalphabetic cipher):
明文中的字符映射到密文空间的字符还依赖于它在上下文的位置。

恺撒密码(Caesar Cipher):
已知的最早(也是最简单的方式)的简单替代密码是朱里斯.恺撒所用的密码。恺撒密码是把字母表中的每个字母用该字母后面第3个字母进行代替。例如:
明文:meet me after the toga party
密文:PHHW PH DIWHU WKH WRJD SDUWS
既然字母表是循环的,因此Z后面的字母是A。能够通过列出所以可能性定义如下所示的变换:
在这里插入图片描述

移位密码(Shift cipher)
对每个明文字母p,恺撒加密可转化为移位密码,其中加密算法:
C = E§ = (p+k) mod (26),其中k在1~25之间取值。
解密算法是:p = D© = (C-k) mod (26)
如果已知密文是恺撒密码,则使用强行攻击密码分析容易取得结果
直接对所有25个可能的密钥进行尝试。

模运算
a+b mod n = (a mod n+b mod n) mod n
a-b mod n = (a mod n-b mod n) mod n
a×b mod n = (a mod n×b mod n) mod n

仿射密码算法:
P = C = Z26
K = (a,b) ∈K = Z26×Z26
加密
y = eK(x) = (ax+b) mod 26
要求唯一解的充要条件:gcd(a,26)=1
解密
dK (y) = (y – b) / a mod 26 = (y – b) a-1 mod 26
仿射密码算法例:
K = (7,3),则有7-1 mod 26 = 15
因此对任一明文x有:ek (x) = 7x + 3
解密:
dk (y) = 15 * (y – 3) mod 26 = 15y – 19 mod 26
= 15 * (7x + 3) – 19 = 105*x + 45 – 19
= 105x = x mod 26
仿射密码算法讨论:

首先,a = 1时,即是移位密码 (shift)
其次,如果K随意选择,可能会有问题
比如取K = (8,5) ,即y=8x+5 mod 26
明文a和n,记x1 = 0 (a),x2 = 13 (n),则y1= 5,y2 = 5 (F)
不同的明文被加密成相同的密文,这样在解密时就有歧义
那么,如何避免这种歧义的出现?
合理选取密钥
要求a和26互素,即gcd (a, 26) = 1
如果k = (a,b)中a和26不互素则会有歧义,若a和26有公因子gcd (a, 26)=d>1,则对明文x1=0和x2 =26/d的就相同密文
因为ax1+b≡b mod 26,而ax2+b=a×26/d+b=a/d×26+b≡b mod 26
即x1和x2被加密成相同的密文,所以解密时会混淆
这里,是否互素代表了什么性质呢?
互素才有“逆”
逆元,讨论在余数集合上进行
加法逆元:如果a + b≡0 mod n,互为加法逆元
则Zn中都有:0,0 1,n-1 2,n-2 … n/2,n/2
乘法逆元:如果a×b≡1 mod n,则a、b互为乘法逆元
如6×20≡1 mod 119
定义a的乘法逆元a-1,a-1a ≡ 1 mod n,显然可交换
由y = (ax + b) mod 26,
得x = dK (y) = (y - b) / a = a-1 (y - b) /a-1a = a-1 (y - b)
即x = a-1(ax + b - b) = a-1ax = x mod 26,x恢复了
乘法逆元如何构造?
3×9 ≡ 1 mod 26
5×?≡ 1 mod 26
并不是每个元素都有乘法逆元,概括为解方程 ax≡1 mod n

如何求乘法逆元:
一次同余方程ax ≡ b (mod m)这个方程有没有解,相当于问有没有那样一个整数x,使得对于某个整数y来说,有ax + my=b
推论:ax≡1 mod n有解 IFF (a, n) | 1,即a、n互素

欧几里德算法(求最大公约数):
基于定理:对于任何非负的整数a和非负的整数b:
gcd (a,b) = gcd (b,a mod b)
例如: gcd (55,22) = gcd (22,55 mod 22) = gcd (22,11) = 11
扩展欧几里德算法(求乘法逆元)例:
方式一
求7关于96的乘法逆元

QX1X2X3Y1Y2Y3
1096017
130171-0*13=10–1*13= -1396-7*13=5
11-1350-1*1= -11- 1*(-13)= 147-1*5=2
2-11421-2*0=1-13-2*14= -415-2*2=1
由于Y3=1,所以算法中止,故乘法逆元为-41 mod 96 = 55
即7×55 ≡1 mod 96
方式二
求22mod31的逆元
iriqixiyi
-13110
02201
1911-1
242-23
3125-7
当ri=1,则5x31+(-7)x 22 =1 mod 31
则逆元为(-7)+ 31 = 24
(PS:第一行为被除数,默认XiYi为 1 0 ,第二行为除数,默认XiYi为 0 1 个人觉得方式二好理解一些)
在这里插入图片描述
任意的单表代替密码算法:
设P=C=Z26,K是由26个符号0,1,…,25的所有可能置换组成。任意π∈K,定义eπ(x)= π(x)=y 且dπ(y)=π-1(y)=x, π-1是π的逆置换。
注:
密钥空间K很大,k=26! ≈ 4×1026,破译者穷举搜索不行的(每微秒搜索加密一次需要6.4×1012年)。移位密码、乘数密码、仿射密码算法都是替换密码的特例。
任意的单表代替密码算法可由统计的方式破译

简单代替密码(simple substitution cipher):
又称单字母密码(monoalphabetic cipher),明文的一个字符用相应的一个密文字符代替。

多字母密码(ployalphabetic cipher):
明文中的字符映射到密文空间的字符还依赖于它在上下文的位置。

多字母代替密码:Playfair
Playfair:将明文中的双字母组合作为一个单元对待,并将这些单元转换为密文的双字母组合。
5×5变换矩阵: I与J视为同一字符
加密规则:按成对字母加密
相同对中的字母加分隔符(如x)
在这里插入图片描述
balloon ->ba lx lo on
同行取右边: he -> EC
同列取下边: dm -> MT
其他取交叉: kt > MQ,OD > TR

Hill密码:
基于矩阵的线性变换,由数学家Lester Hill于1929年研制
Z26上的线性变换
例:x=(x1,x2),y=(y1,y2)
在这里插入图片描述定义:y1=11x1+3x2 mod 26,y2= 8x1+7x2 mod 26

Vigenére密码:
是一种多表移位代替密码
设d为一固定的正整数,d个移位代换π=(π1,π2,…,πd) 由密钥序列K=(k1,k2,…,kd)给定,第i+td个明文字母由表i决定,即密钥ki决定
ek(xi+td) = (xi+td + ki) mod q = y,dk(yi+td) = (xi+td-ki) mod q = x
例子:q=26, x=polyalphabetic cipher, K=RADIO
明文 x= p o lya l phab e t i cc i pher
密钥 k= R ADIO RADIO RADIO RADIO
密文 y= GOOGO CPKTP NTLKQ ZPKMF

One-Time Pad一次一密:
Joseph Mauborgne提出使用与消息一样长且无重复的随机密钥来加密消息,密钥只对一个消息加解密,之后弃之不用;每条新消息都需要与其等长的新密钥,这就是一次一密,它是不可攻破的。
运算基于二进制数据而非字母
加密:ci = pi ⊕ ki, pi是明文第i个二进制位, ki是密钥第i个二进制位,ci是密文第i个二进制位, ⊕是异或运算
密文是通过对明文和密钥的逐位异或而成的,根据异或运算的性质,解密过程为pi = ci ⊕ ki,
给出任何长度与密文一样的明文,都存在着一个密钥产生这个明文。如果用穷举法搜索所有可能的密钥,会得到大量可读、清楚的明文,但是无法确定哪个才是真正所需的,因而这种密码不可破。
一次一密的两个限制
产生大规模随机密钥有实际困难
密钥的分配和保护无法保证

置换密码(permutation cipher)

又称换位密码(transposition cipher),明文的字母保持相同,但顺序被打乱了。

斯巴达密码棒

公元前405年,雅典和斯巴达之间的战争已进入尾声。斯巴达急需摸清波斯帝国的具体行动计划。斯巴达军队捕获了一名从波斯帝国回雅典送信的信使。可他身上除了一条布满希腊字母字样的普通腰带外,什么也没有。
斯巴达统帅把注意力集中到了那条腰带上,他反复琢磨那些乱码似的文字,却怎么也解不出来。最后当他无意中把腰带呈螺旋形缠绕在手中的剑鞘上时,原来腰带上那些杂乱无章的字母,竟组成了一段文字。它告诉雅典,波斯准备在斯巴达发起最后攻击时,突然对斯巴达军队进行袭击。

栅栏技术:
在这种密码中最简单的是栅栏技术,在该密码中以对角线顺序写下明文,并以行的顺序读出。
例如:以深度为2的栅栏密码加密消息“meet me after the toga party”,写出如下形式:

mematrhtgpry
etefeteoaat
被加密的消息为:mematrhtgpryetefeteoaat

置换密码:
更为复杂的方式是以一个矩形逐行写出消息,再逐列读出该消息。
该方法以行的顺序排列。列的阶则成为该算法的密钥。密钥包含3方面信息::行宽、列高、读出顺序
例:
|key | 4| 3| 1| 2| 5| 6| 7|
|–|–|–|–|–|–|–|–|–|
|plaintext: |a | t | t | a| c| k| p|
| | o| s | t| p | o | n| e|
| | d| u | n| t| i| l| t|
|| w | o | a | m |x | y| z|
ciphertext :TTNAAPTMTSUOAODWCOIXPETZ

完全保留字符的统计信息
使用多轮加密可提高安全性

Rotor Machines转轮密码机:
在现代密码系统出现之前,转轮密码机是最为广泛使用的多重加密器,尤其是在第二次世界大战中。
代表:German Enigma, Japanese Purple
转轮机使用了一组相互独立的旋转圆筒,可以通过电脉冲,每个圆筒有26个输入和26个输出,每个输入仅与一个输出相连,一个圆筒就定义了一个单表代换。
每按下一个键,圆筒旋转一个位置,内部连线相应改变,就定义了不同的单表代换密码,经过26个明文字母,圆筒回到初始状态,就得到一个周期为26的多表代换密码。
3个圆筒的转轮机就有263=17576个不同的代换字母表

Enigma的使用

发信人首先要调节三个转子的方向,而这个转子的初始方向就是密钥,是收发双方必须预先约定好的,然后依次键入明文,并把显示器上灯泡闪亮的字母依次记下来,最后把记录下的闪亮字母按照顺序用正常的电报方式发送出去。
收信方收到电文后,只要也使用一台恩尼格玛,按照原来的约定,把转子的方向调整到和发信方相同的初始方向上,然后依次键入收到的密文,显示器上自动闪亮的字母就是明文了。
加密的关键在于转子的初始方向。如果敌人收到了完整的密文,还是可以通过不断试验转动转子方向来找到这个密匙,特别是如果破译者同时使用许多台机器同时进行这项工作,那么所需要的时间就会大大缩短。对付这样暴力破译法(即一个一个尝试所有可能性的方法),可以通过增加转子的数量来对付,因为只要每增加一个转子,就能使试验的数量乘上26倍!
由于增加转子就会增加机器的体积和成本,恩尼格玛密码机的三个转子是可以拆卸下来并互相交换位置,这样一来初始方向的可能性一下就增加了六倍。假设三个转子的编号为1、2、3,那么它们可以被放成123-132-213-231-312-321这六种不同位置。
恩尼格玛还有一道保障安全的关卡,在键盘和第一个转子之间有块连接板。通过这块连接板可以用一根连线把某个字母和另一个字母连接起来,这样这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最多可以有六根,后期的恩尼格玛甚至达到十根连线,这样就可以使6对字母的信号两两互换,其他没有插上连线的字母则保持不变。当然连接板上的连线状况也是收发双方预先约定好的。
转子的初始方向、转子之间的相互位置以及连接板的连线状况组成了恩尼格玛三道牢不可破的保密防线,其中连接板是一个简单替换密码系统,而不停转动的转子,虽然数量不多,但却使整个系统变成了复式替换系统。

Enigma的破解

“暴力破译法”还原明文,需要试验多少种可能性:
三个转子不同的方向组成了26x26x26=17576种可能性;
三个转子间不同的相对位置为6种可能性;
连接板上两两交换6对字母的可能性则是异常庞大,有100391791500种;
于是一共有17576x6x100391791500,其结果大约为10,000,000,000,000,000!即一亿亿种可能性!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/268779.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【CSS】(浮动定位)易忘知识点汇总

浮动特性 加了浮动之后的元素,会具有很多特性,需要我们掌握的. 1、浮动元素会脱离标准流(脱标:浮动的盒子不再保留原先的位置) 2、浮动的元素会一行内显示并且元素顶部对齐 注意: 浮动的元素是互相贴靠在一起的(不会有缝隙)&…

用于游戏开发的顶级 PYTHON 框架

一、说明 我们试图用python开发游戏,一旦产生这个念头,就伴随这样一个问题:当今用于构建游戏的领先 Python 框架有哪些?python下,支持游戏开发平台有哪些优势?我们在这篇博文中告诉你。 二、高级游戏平台简…

nginx使用详解--缓存

Nginx 是一个功能强大的 Web 服务器和反向代理服务器,它可以用于实现静态内容的缓存,缓存可以分为客户端缓存和服务端缓存。 客户端缓存 客户端缓存指的是浏览器缓存, 浏览器缓存是最快的缓存, 因为它直接从本地获取(但有可能需要发送一个协商缓存的请…

NOIP 2009普及组初赛试题及解析

NOIP 2009普及组初赛试题及解析 一. 单项选择题 (共20题,每题1.5分,共计30分。每题有且仅有一个正确答案.)。二. 问题求解(共2题,每题5分,共计10分)三. 阅读程序写结果(共…

【精选】Java项目介绍和界面搭建——拼图小游戏 上

🍬 博主介绍👨‍🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏 …

MYSQL---日志

1.日志的概述 日志是MySQL数据库的重要组成部分。日志文件中记录着MySQL数据库运行期间发生的变化;也就是说用来记录MySQL数据库的客户端连接状况、SQL语句的执行情况和错误信息等。当数据库遭到意外的损坏时,可以通过日志查看文件出错的原因&#xff0…

【Web】速谈FastJson反序列化中JdbcRowSetImpl的利用

目录 简要原理分析 exp 前文:【Web】速谈FastJson反序列化中TemplatesImpl的利用 简要原理分析 前文的TemplatesImpl链存在严重限制,即JSON.parseObject()需要开启Feature.SupportNonPublicField fastjson的第二条链JdbcRowSetImpl,主要…

2024年,只有搞颜色的P站真正关心网站性能

2024 年,大家觉得一个网站 JS 文件的平均大小应该是多少?1MB、5MB、10MB,还是更加大呢? 近年来,层出不穷的现代化前端技术让人眼花缭乱,让网站拥有了更多的交互和丰富的功能,再加上终端设备的配置越来越高,许多网站似乎不用再过分担心性能问题 —— 常常打开网站就要下…

EI论文部分复现:含VSC-HVDC的交直流系统内点法最优潮流计算Simulink模型!

适用平台:MatlabSimulink;复现内容:VSC-HVDC模型 简介 高压直流传输系统主要包括换流站、输电线路和终端设备,其中换流站起着关键作用,他可以实现交流整流和直流逆变。常见的HVDC系统有全桥式、半桥式和两水平VSC等。…

spring boot学习第十三篇:使用spring security控制权限

该文章同时也讲到了如何使用swagger。 1、pom.xml文件内容如下&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instanc…

PackagingTool_x64_v2.0.1.0图片转档打包二进制文件合并字库生成图片软件介绍

继去年12月份发布的打包软件PackagingTool v1.4.0.2之后&#xff0c;今年再度投入精力&#xff0c;完善了软件功能&#xff0c;同时开发了几个更加实用的工具&#xff0c;可助力UI界面的设计开发。当前最新版本为PackagingTool_x64_v2.0.1.0&#xff0c;该版本主界面如下&#…

二叉树(C/C++)

本篇将较为详细的介绍二叉树的相关知识&#xff0c;以及二叉树的实现。对于二叉树的相关知识&#xff0c;本篇介绍了其概念、特殊的二叉树、性质还有存储结构。 接着对于实现二叉树的每个函数都有其思路讲解&#xff0c;主要的函数分为&#xff1a;遍历&#xff1a;前中后序遍历…

什么是网络安全、信息安全、计算机安全,有何区别?

这三个概念都存在&#xff0c;一般人可能会混为一谈。 究竟它们之间是什么关系&#xff1f;并列&#xff1f;交叉&#xff1f; 可能从广义上来说它们都可以用来表示安全security这样一个笼统的概念。 但如果从狭义上理解&#xff0c;它们应该是有区别的&#xff0c;区别在哪呢&…

buuctf misc做题笔记

喵喵喵 使用stegsolve.jar&#xff0c;按BGR顺序提取出一个png图片&#xff0c;是一个只显示一半的二维码&#xff0c;修改图片高度显示全部二维码&#xff0c;解析出一个百度网盘地址&#xff0c;https://pan.baidu.com/s/1pLT2J4f 下载得到压缩包flag.rar。解压成功&#xf…

MQL5学习之简单移动平均线MA的编写

昨天还是有点高估自己了&#xff0c;MACD相对较难一点&#xff0c;改学MA的编写&#xff0c;首先明确MA的计算&#xff0c;假如有4个值&#xff0c;p[1&#xff0c;2&#xff0c; 3&#xff0c; 4], period3, 则v[0]p[0], v[1]p[1],v[2](p[0]p[1]p[2])/32, v[3](v[2]*3p[3]-p…

lv20 QT主窗口4

熟悉创建主窗口项目 1 QAction 2 主窗口 菜单栏&#xff1a;fileMenu menuBar()->addMenu(tr("&File")); 工具栏&#xff1a;fileToolBar addToolBar(tr("File")); 浮动窗&#xff1a;QDockWidget *dockWidget new QDockWidget(tr("Dock W…

HTTP Cookie 你了解多少?

Cookie是什么&#xff1f; 先给大家举个例子&#xff0c;F12 打开浏览器的页面之后&#xff0c;我们能在 Response Headers 的字段里面看到一个header 叫做 Set-Cookie&#xff0c;如下所示 图中包含的 Set-Cookie 为 Set-Cookie:uuid_tt_dd10_20293537580-1709432565344-232…

HTTP有什么缺陷,HTTPS是怎么解决的

缺陷 HTTP是明文的&#xff0c;谁都能看得懂&#xff0c;HTTPS是加了TLS/SSL加密的&#xff0c;这样就不容易被拦截和攻击了。 SSL是TLS的前身&#xff0c;他俩都是加密安全协议。前者大部分浏览器都不支持了&#xff0c;后者现在用的多。 对称加密 通信双方握有加密解密算法…

如何利用pynlpir进行中文分词并保留段落信息

一、引言 nlpir是由张华平博士开发的中文自然处理工具&#xff0c;可以对中文文本进行分词、聚类分析等&#xff0c;它既有在线的中文数据大数据语义智能分析平台&#xff0c;也有相关的python包pynlpir&#xff0c;其github的地址是&#xff1a; Pynlpir在Github上的地址 这…

Manacher

Manacher #include<bits/stdc.h> using namespace std; ​ const int N 1e6 9; char s[N]; int p[N]; int mian() {cin >> s 1;int n strlen(s 1);for (int i 2 * n 1; i > 1; --i)s[i] (i & 1) ? # : s[i >> 1];s[0] ^, s[2 * n 2] $;in…