【CTF-编程-NC】最长公共前缀

题目

最长公共前缀

欢迎来到编程世界！

你将连接到一个交互式服务。
在每一轮中，服务端会给出一个字符串数组，你的任务是找出这些字符串的最长公共前缀。

如果不存在公共前缀，请输出空字符串。

请使用NC连接

连接测试

编写代码

# -*- coding: utf-8 -*-""" CTF挑战：最长公共前缀求解脚本 功能： 1. 与CTF服务器建立TCP连接 2. 接收服务器发送的字符串数组挑战 3. 计算最长公共前缀 4. 将结果发送回服务器 5. 重复步骤2-4直到获得flag 使用说明： 直接运行脚本即可自动与服务器交互 python solve.py """# 导入必要的模块importsocket# 用于网络通信，创建和管理TCP连接importre# 用于正则表达式，提取字符串数组deflongestCommonPrefix(strs):""" 计算字符串数组的最长公共前缀 参数： strs (list[str]): 待计算最长公共前缀的字符串数组 返回： str: 所有字符串的最长公共前缀，如果不存在公共前缀则返回空字符串 算法思路： 1. 边界情况处理：如果字符串数组为空，直接返回空字符串 2. 初始化前缀为第一个字符串 3. 遍历剩余所有字符串，与当前前缀进行比较 4. 如果当前前缀与字符串不匹配，则逐步缩短前缀长度 5. 当前缀为空或所有字符串都匹配时，返回当前前缀 时间复杂度：O(S)，其中S是所有字符串中字符的总数量 空间复杂度：O(1)，只使用常量额外空间 """# 边界情况：如果字符串数组为空，直接返回空字符串ifnotstrs:return""# 初始化前缀为第一个字符串prefix=strs[0]# 遍历字符串数组中的剩余字符串forsinstrs[1:]:# 当当前前缀与字符串不匹配且前缀不为空时，缩短前缀# s[:len(prefix)] 获取字符串s中与当前前缀长度相同的前缀部分whiles[:len(prefix)]!=prefixandprefix:prefix=prefix[:-1]# 前缀缩短一个字符（去掉最后一个字符）# 如果前缀为空，说明没有公共前缀，直接跳出循环ifnotprefix:break# 返回找到的最长公共前缀returnprefixdefmain():""" 主函数，负责与CTF服务器建立连接并处理交互 功能： 1. 建立TCP连接到指定的CTF服务器 2. 接收服务器发送的挑战数据 3. 提取数据中的字符串数组 4. 计算最长公共前缀 5. 将结果发送回服务器 6. 循环处理直到收到flag或服务器关闭连接 网络交互流程： - 客户端：建立TCP连接 - 服务器：发送欢迎信息和第一轮挑战 - 客户端：提取字符串数组，计算最长公共前缀并发送结果 - 服务器：验证结果，发送下一轮挑战或flag - 重复上述步骤直到收到flag """# 服务器配置参数host='challenge.qsnctf.com'# CTF服务器的主机名port=33183# CTF服务器的端口号# 创建TCP socket并建立连接# 使用with语句自动管理socket资源，确保连接正确关闭withsocket.socket(socket.AF_INET,socket.SOCK_STREAM)ass:# 连接到服务器s.connect((host,port))# 主交互循环whileTrue:# 接收服务器发送的数据# 缓冲区大小设置为4096字节，确保能接收完整的挑战数据# 将接收到的字节数据解码为UTF-8字符串data=s.recv(4096).decode()# 打印接收到的数据，用于调试和观察交互过程print("Received:",data)# 检查接收到的数据中是否包含flag# 如果包含flag，说明挑战已完成，打印提示并退出循环if"flag"indata.lower():print("Flag found!")break# 使用正则表达式提取数据中的字符串数组# 正则表达式r'"([^"]+)"'的含义：# - " 匹配双引号# - ([^"]+) 捕获组，匹配一个或多个非双引号字符# - " 匹配双引号# 该正则表达式可以提取所有被双引号包围的字符串matches=re.findall(r'"([^"]+)"',data)# 如果成功提取到字符串数组ifmatches:# 将提取到的字符串列表赋值给strs变量strs=matches# 打印提取到的字符串数组，用于调试print("Extracted strings:",strs)# 调用longestCommonPrefix函数计算最长公共前缀result=longestCommonPrefix(strs)# 打印计算结果，用于调试print("Result:",result)# 将结果发送回服务器# 结果末尾添加换行符，符合服务器预期的输入格式# 将字符串编码为字节后发送s.sendall((result+'\n').encode())# 检查服务器是否发送了结束信号elif"bye"indata.lower():print("Session ended by server.")break# 继续循环，等待服务器发送下一轮数据# 这种情况可能发生在：# 1. 服务器发送的是欢迎信息或提示信息# 2. 服务器发送的数据中没有包含字符串数组# 3. 网络延迟导致数据未完全接收# 程序入口点# 当脚本直接被执行时，__name__变量的值为"__main__"# 当脚本被作为模块导入时，__name__变量的值为模块名# 这个条件判断确保只有当脚本直接执行时才会调用main函数if__name__=="__main__":# 调用主函数，开始与CTF服务器交互main()

运行结果

Received: You need tofindthe longest common prefix of given strings Received: Round1:["tfeqjen","tfebdanqawa","tfistnpbbwy","tfxkudi","tfvrelo","tfmtkbkkxmy"]>Extracted strings:['tfeqjen','tfebdanqawa','tfistnpbbwy','tfxkudi','tfvrelo','tfmtkbkkxmy']Result: tf Received: Correct!Received: Round2:["uuwxsvzqi","uuwxvsvsmbfc","uuwxtvwvhiutj","uuwxcdwycs"]>Extracted strings:['uuwxsvzqi','uuwxvsvsmbfc','uuwxtvwvhiutj','uuwxcdwycs']Result: uuwx Received: Correct!Received: Round3:["tiiocjaomhqy","tiiomwyve","tiiorputurrxl","tiioxfuftbhf","tiioytlormcpk","tiiowerlzkgqd","tiiodmaighekq"]>Extracted strings:['tiiocjaomhqy','tiiomwyve','tiiorputurrxl','tiioxfuftbhf','tiioytlormcpk','tiiowerlzkgqd','tiiodmaighekq']Result: tiio Received: Correct!Received:......Round999:["rujzfbdoffdjm","rujzfwztbox","rujzftmybjno","rujzfjfkuh","rujzfskwipcm","rujzfouxpnaf","rujzfiyzgzi","rujzfpzexl"]>Extracted strings:['rujzfbdoffdjm','rujzfwztbox','rujzftmybjno','rujzfjfkuh','rujzfskwipcm','rujzfouxpnaf','rujzfiyzgzi','rujzfpzexl']Result: rujzf Received: Correct!Received: Round1000:["tobdgdp","tlflzhqlp","kvqvr","uxffyjktz","wftoonzv","adqoshyq","vjgpilxg"]>Extracted strings:['tobdgdp','tlflzhqlp','kvqvr','uxffyjktz','wftoonzv','adqoshyq','vjgpilxg']Result: Received: Correct!Received: Congratulations!Here is your flag: qsnctf{7443543dee3542858ee1e763084a1437}

答案

qsnctf{7443543dee3542858ee1e763084a1437}