洛谷 B4500 / B4449 / B3843 凯撒密码、密码强度与密码合规——加密与安全的三道门 摘要B4500 破解凯撒密码从已知明密文对推断偏移量B4449 检测密码强度长度大写数字B3843 验证密码合规字符集长度组合规则。三道题覆盖了用户系统安全的基础三道门加密、强度策略和合规校验。本文从伪代码题解出发延伸到密码学 2000 年进化史凯撒→Enigma→RSA→AES、密码存储安全为什么不能存明文→哈希→加盐→Argon2、以及 NIST 2025 密码新规取消复杂度规则、推荐 15 字符密码、泄露密码筛查——从洛谷入门题到每家公司的用户注册系统。题目链接B4500 凯撒密码 | B4449 密码强度 | B3843 密码合规 目录 前言 三道题在考什么️ B4500凯撒密码 思路 伪代码 关键点 B4449密码强度 思路 伪代码 关键点✅ B3843密码合规 思路 伪代码 关键点⚖️ 三道门的对比⚠️ 注意事项 延伸从凯撒密码到现代密码学 密码学 2000 年进化史 密码存储为什么不能存明文 NIST 2025 密码新规 超越密码2FA 与 Passkey 三道门与三层安全 延伸阅读文献 前言这篇题解没有源代码只有伪代码。作为一名信奥教练我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了脑子没跑通。下次遇到变体题还是不会。伪代码剥掉了语言的壳只留算法的骨架。你看不到#include看不到cin、cout看不到那些让你以为我会了的语法细节。你能看到的只有这一步做什么、下一步做什么、为什么这么做。如果你是路过的友友已经在这道题上挣扎了很久——先去喝杯水回来重新看看自己卡在哪一步。是没读懂题意是思路方向偏了还是代码有 bug 但逻辑其实对大多数时候不是不会是走偏了。偏了不可怕可怕的是偏了之后直接放弃去抄一份能 AC 的代码。抄完你以为你懂了其实你只是搬了别人的结论。除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说能理解。但平时练习给自己一点耐心。先自己想、自己写、自己调跑不过了再来看伪代码你的思路和这里差在哪一步。那一步就是你真正学到的东西。 三道题在考什么三道题都是加密与安全主题但覆盖的环节不同B4500 凯撒密码B4449 密码强度B3843 密码合规考什么从已知明密文对推断偏移量解密新密文判断密码是否满足最低安全要求判断密码是否符合注册规则安全环节加密/解密强度策略合规校验核心操作模运算 字符偏移长度判断 字符类型检测逗号分割 多条件校验现实对应古典密码学密码策略NIST 指南用户注册系统的密码校验B4500 是加密——把信息变成看不懂的形式只有知道偏移量的人能还原。B4449 是强度策略——什么样的密码才算够安全太短的不行、太简单的不行。B3843 是合规校验——用户注册时密码必须满足一套规则才能通过。这是每个有用户系统的网站都在做的事。三道题恰好对应了用户系统安全的三道门加密传输、强度要求、合规验证。️ B4500凯撒密码 B4500 思路题目给三行已知明文、已知密文、待解密密文。从第一对明密文算出偏移量然后用这个偏移量逆向解密第三行。偏移量 密文首字符 - 明文首字符。解密时对每个密文字符减去偏移量用模 26 处理越界A 往前偏 3 变成 X。 B4500 伪代码读取 明文 code 读取 已知密文 decode 读取 待解密密文 new_code 偏移量 decode[0] - code[0] // 从首字符推断偏移量 对 new_code 中每个字符 c: 原始位置 c - A // 转成 0-25 解密位置 (原始位置 - 偏移量 26) % 26 // 减偏移26 防负数%26 处理回绕 输出字符 解密位置 A // 转回字母 B4500 关键点偏移量从首字符推断。shift decode[0] - code[0]。样例中D - A 3说明加密时每个字母向后移了 3 位。解密就反过来减 3。用样例追踪密文字符ASCII 位置减偏移 326 防负%26明文字符W22191919TK10777HH7444ET19161616QX23202020UL11888I输出THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG。26的作用。如果密文字符的位置小于偏移量比如 A0偏移 30-3-3结果是负数C 的%对负数保留符号。加 26 再取模确保结果在 0-25 范围内(-3 26) % 26 23 X。凯撒密码为什么非常容易被破解。题目背景自己说了。偏移量只有 25 种可能1-25暴力枚举全部、看哪个结果是有意义的英文几秒就破。凯撒密码的安全性等于零——它是密码学的起点但不是终点。 B4449密码强度 B4449 思路读入 T 组密码每组检查三个条件长度≥8、含大写字母、含数字。三个都满足输出 Y否则 N。代码用continue提前跳过短密码长度8 直接 N不继续检查字符这是一个合理的提前终止优化。 B4449 伪代码读取 T 对每组密码 s: 有大写 false 有数字 false 如果 s 长度 8: 输出 N 继续 // 提前终止不再检查字符 对 s 中每个字符 c: 如果 c 是大写字母: 有大写 true 如果 c 是数字: 有数字 true 如果 有大写 且 有数字: 输出 Y 否则: 输出 N B4449 关键点提前终止。长度8 直接 N不需要扫描字符。对于 T100、每组最多 100 字符最坏 10⁴ 次检查毫无压力。但提前终止是良好习惯——能跳过的计算就跳过。用样例追踪密码长度≥8有大写有数字结果PAs1s2an8 ✓P, A ✓1, 2 ✓Y1a2bCql38 ✓C ✓1, 2, 3 ✓YPa12bsna8 ✓P ✓1, 2 ✓Yab1da3cd8 ✓✗1, 3 ✓NPaabdbcd8 ✓P ✓✗NPa23 ✗——N两个布尔变量的接力。has_up和has_num像两个开关扫描时只要碰到对应类型的字符就把开关打开。扫描结束后两个开关都亮着才算安全。如果只亮一个或都不亮不安全。B4449 和 B3843 的区别。B4449 的规则更宽松——只要有大写和数字就行不限制小写和特殊字符。B3843 的规则更严格——必须满足字符集限制、长度范围、组合要求和特殊字符。前者像够不够安全的底线检查后者像符不符合规则的格式校验。✅ B3843密码合规 B3843 思路输入是逗号分隔的多个密码。对每个密码段检查四条规则字符集只能是小写、大写、数字、!#KaTeX parse error: Expected EOF, got # at position 45: …两种、至少一个特殊字符!#̲之一。全满足才输出。代码用k标记每个密码段的起始位置遇到逗号时处理k到i之间的字符段然后k i1跳到下一段。末尾手动加一个逗号确保最后一段被处理。 B3843 伪代码读取字符串 a a 末尾追加 , // 确保最后一段被逗号触发处理 段起点 k 0 对 i 0 到 a 长度-1: 如果 a[i] ,: 长度 0 有小写 false, 有大写 false, 有数字 false, 有特殊 false 对 j k 到 i-1: 长度 如果 a[j] 是小写字母: 有小写 true 否则如果 a[j] 是大写字母: 有大写 true 否则如果 a[j] 是数字字符: 有数字 true // 必须用 0 和 9不是 0 和 9 否则如果 a[j] 是 ! # $ 之一: 有特殊 true 否则: 有特殊 false // 非法字符 跳出内层循环 如果 长度 6-12 且 有特殊 且 (至少两种类型为 true): 输出 a[k] 到 a[i-1] // 输出合规密码 k i 1 // 跳到下一段起点 B3843 关键点逗号分割的标准操作。末尾加逗号 遇逗号触发处理 k i1跳段。这是处理分隔符切分字符串的经典模式在 CSV 解析、命令行参数解析中反复出现。字符类型检测的 if-else 链。用if-else if逐个判断字符属于哪类。一旦不属于任何合法类别立刻break并标记不合规——非法字符直接一票否决。用样例追踪密码段长度小写大写数字特殊非法字符合规seHJ12!8✓✓✓✓无✓ 输出sjdkffH$12311✓✓✓✓无✓ 输出sdf!12HDHa!14———— 是非法✗123^YUhg!12————^ 是非法✗至少两种类型的逻辑。原始代码的条件很长(smallbig || smallnumber || bignumber || smallbignumber) fu。这其实是小写、大写、数字中至少选两种的展开形式。更简洁的写法是(smallbignumber 2) fu——把布尔值当整数加和≥2 就是至少两种。⚖️ 三道门的对比B4500 凯撒密码B4449 密码强度B3843 密码合规安全环节加密/解密强度策略合规校验输入明文密文待解密密文T 组密码逗号分隔的多组密码核心操作模运算 字符偏移长度字符类型检测分割多条件校验判断逻辑算偏移→逆向偏移三个条件全满足四条规则全满足复杂度O(L)O(T × L)O(N)N 为总字符数现实对应古典密码学NIST 密码策略用户注册系统B4500 是把信息加密B4449 是检查密码够不够强B3843 是检查密码符不符合规则。一个管传输安全一个管密码质量一个管格式合规。三个合在一起就是大部分用户系统的密码安全基础流程。⚠️ 注意事项B4500 的26防负数C 中负数取模结果仍为负数如-3 % 26 -3必须先26再取模才能保证结果在 0-25 范围。B4500 的偏移量方向shift decode[0] - code[0]密文 - 明文解密时是减去偏移量。如果搞反了方向用明文 - 密文解密会变成加密。B4449 的提前终止continue跳过短密码后不再检查字符这是正确的——长度不够其他条件不用看。但注意has_up和has_num要在每组密码开始时重置。B3843 的数字判断0不是0a[j]0a[j]9检查的是字符 ‘0’ 到 ‘9’ASCII 48-57。如果写成a[j]0a[j]9检查的是 ASCII 值 0-9控制字符NULL、SOH、STX……没有任何可打印字符会匹配。这是学生最常见的混淆——数字 0 和字符 ‘0’ 是两个东西。数字 0 的 ASCII 值是 48不是 0。0是字符常量0是整数常量。少了两个引号逻辑完全不同。B3843 的逗号追加a ,是确保最后一段密码被处理的关键技巧。不追加的话最后一段没有逗号结尾不会被触发处理。B3843 的至少两种展开原始代码把条件完全展开成四项 OR更简洁的写法是(small big number 2)。 延伸从凯撒密码到现代密码学你说这三道题都是与加密相关而且大部分用户系统需求都会用到。没错——它们分别对应了用户系统安全的三个核心问题怎么加密、密码够不够强、密码符不符合规则。这三道门背后是密码学 2000 年的进化史和现代安全工程的完整体系。 密码学 2000 年进化史B4500 的凯撒密码是密码学有记载的起点Brief History of Encryption时期技术原理和 B4500 的关系公元前 50 年凯撒密码固定偏移替换就是 B4500 本身1553 年维吉尼亚密码Vigenère多表替换用关键词控制偏移凯撒的升级版——不同位置用不同偏移1918 年Enigma 转子机机械式多转子替换凯撒的终极版——每天换初始状态Cryptography History1977 年RSA 算法大数分解困难从替换到数学难题的范式转变信息安全基础2001 年AES 标准置换-替换网络全球加密标准至今未破CrypTool — Geschichte2024 年后量子密码格密码等数学结构抗量子计算机的下一代密码凯撒密码的偏移量只有 25 种可能暴力枚举几秒就破Quantum Cryptography。维吉尼亚用关键词控制偏移安全性提升了很多但 1863 年被 Kasiski 方法破。Enigma 每天换设置看起来不可破但 1939 年波兰密码局和图灵的 Bletchley Park 团队成功破译——二战因此缩短了至少两年Cryptography History。RSA 不再是替换而是利用数学难题——分解两个大质数的乘积极其困难。AES 是对称加密的全球标准密钥长度 128/192/256 位暴力破解需要 10⁶⁰ 年——宇宙年龄的 10⁵⁰ 倍。你今天在 B4500 里做的(char - A - shift 26) % 26和 AES 的置换-替换网络本质上做的是同一件事——把信息变成只有持有密钥的人才能还原的形式。区别只在于凯撒的密钥空间是 25AES-256 的密钥空间是 2²⁵⁶。 密码存储为什么不能存明文B4449 和 B3843 检查的是密码够不够强。但密码检查完之后呢用户的密码存在哪里绝对不能存明文。如果数据库被拖库SQL 注入、备份泄露所有用户的密码直接暴露Security of Credentials。攻击者还能用同一组邮箱密码去撞库其他平台——一次泄露引发连锁灾难Web 服务密码存储安全。正确做法是哈希 加盐OWASP Password Storage Cheat Sheet用户注册: 密码 → 加盐 → 哈希函数(慢速) → 存储哈希值 用户登录: 输入密码 → 加同样的盐 → 哈希 → 和存储的哈希值比对 相同 → 通过 不同 → 拒绝哈希Hash不是加密。加密可逆——有密钥就能解密还原。哈希不可逆——从哈希值反推密码只能靠暴力尝试Best practices for password hashing。盐Salt的作用。如果不加盐两个用户用同一密码哈希值相同——攻击者用预计算表彩虹表可以秒破。加盐后每个用户的盐不同同一密码的哈希也不同彩虹表失效What Is a Password Salt。算法特点推荐度MD5 / SHA-1太快暴力破解成本低❌ 不推荐bcrypt内置加盐可调成本因子✓ 推荐scrypt内存困难型抗 GPU 破解✓ 推荐Argon2id2015 年密码哈希竞赛冠军✓ 最推荐OWASP 2024 推荐使用 Argon2id其次是 bcrypt 或 PBKDF2OWASP Password Storage。 NIST 2025 密码新规B4449 要求大写数字B3843 要求小写大写数字特殊字符至少两种。这些规则在 2017 年之前是行业标配。但NIST 2025 年更新了 SP 800-63B推翻了很多旧规则NIST 2025 Password Recommendations旧规则NIST 2025 新规理由要求大小写数字特殊字符混合取消复杂度规则用户被迫加!1在末尾实际没提升安全性NIST SP 800-63B定期更换密码取消定期更换除非确认泄露NIST 2025用户会循环用旧密码最短 8 字符最短 8推荐 15最长 ≥64长度比复杂度重要——correct-horse-battery-staple比Tr0ub4dor3更安全NIST 2025 Refresh无泄露检查必须筛查已泄露密码用 Have I Been Pwned 等数据库检查NIST SP 800-63BNIST 的核心观点是复杂度规则让用户写出Password1!这种满足规则但不安全的密码。长度比复杂度重要得多NIST 2025。B4449 和 B3843 用的还是旧规则——这是 GESP 考试的简化版本不是工业标准。但它们教会学生的核心概念是对的密码需要满足一定要求才能使用。只是实际工业中要求的内容在变化——从够复杂转向够长没泄露过。 超越密码2FA 与 Passkey密码不是终点。现代系统正在超越密码技术原理和三道题的关系2FA / MFA密码 手机验证码/认证器B4449 的强度升级为多因素FIDO2 / Passkey设备生物识别 公钥签名彻底取代密码B4449/B3843 的规则不再需要OAuth / SSO第三方身份提供者不再自己存密码交给 Google/AppleHave I Been Pwned密码泄露数据库B4449 的强度检查升级为泄露检查NIST 2025 特别强调抗钓鱼的多因素认证phishing-resistant MFA——FIDO2/Passkey 是推荐方向NIST 2025 Refresh。未来的趋势是密码逐渐退场设备生物识别接管。 三道门与三层安全把三道题和延伸放在一起恰好覆盖了用户系统安全的完整链路层级洛谷题工业对应做什么加密传输B4500 凯撒密码AES-256 / TLS数据在传输中加密第三方看不到密码质量B4449 密码强度NIST SP 800-63B密码够长、没泄露过合规校验B3843 密码合规用户注册系统密码符合字符集和组合规则安全存储—Argon2id Salt密码哈希后存储拖库不泄露多因素—2FA / FIDO2超越密码防钓鱼B4500 管传输——信息在通道中加密。B4449 管质量——密码本身够不够强。B3843 管格式——密码符不符合注册规则。再加上存储安全哈希盐和多因素认证就是一套完整的用户系统安全方案。你今天在洛谷上写的三段代码对应的是用户注册系统的三个核心函数encrypt()、checkStrength()、validatePassword()。每家有用户系统的公司——从微信到银行——都在调用这三个函数的工业版。 延伸阅读文献标准NIST.SP 800-63B: Digital Identity Guidelines — Authentication and Authenticator Management(2025 Revision). NIST Official PDF —— 美国国家标准与技术研究院的密码认证指南2025 年取消复杂度规则。NIST.SP 800-63B (2017 Original). NIST Official —— 2017 年原版首次提出取消定期更换密码。IETF.Best Practices for Password Hashing and Storage(Draft). IETF —— 密码哈希存储的 IETF 最佳实践。论文K. Pandya et al.Brief History of Encryption. International Journal of Computer Applications, 2015. IJCA —— 从古代到现代的密码学历史综述。N. Gisin et al.Quantum Cryptography. Reviews of Modern Physics, 2002. arXiv —— 量子密码学综述含凯撒密码到量子密钥分发的历史脉络。在线资源洛谷.B4500 [GESP202603 三级] 凯撒密码. https://www.luogu.com.cn/problem/B4500洛谷.B4449 [GESP202512 三级] 密码强度. https://www.luogu.com.cn/problem/B4449洛谷.B3843 [GESP202306 三级] 密码合规. https://www.luogu.com.cn/problem/B3843OWASP Password Storage Cheat Sheet. https://github.com/OWASP/CheatSheetSeries/…/Password_Storage_Cheat_Sheet.md —— OWASP 密码存储最佳实践。NIST 2025 Password Recommendations: What’s Changed. https://www.captaindns.com/…/nist-2025-password-recommendations —— NIST 2025 密码新规解读。Your Password Policy Is Due for a 2025 Refresh. https://blogs.reliablepenguin.com/…/nist-2025 —— NIST 2025 更新详解。Cryptography History — From Ancient Secrets to Modern Security. https://www.bnitindia.com/blog/cryptography-history —— 密码学历史时间线。CrypTool — Geschichte der Kryptografie. https://www.cryptool.org/de/education/history/ —— 密码学教育工具含完整历史时间线。What Is a Password Salt and Why Does It Matter?https://www.panicvault.org/…/password-salt-explained —— 密码加盐原理详解。Security of Credentials: Algorithms and Techniques for Storing Passwords. IBIMA Publishing —— 密码存储算法综述。推荐教材B. Schneier.Applied Cryptography(2nd Edition). Wiley, 1996. —— 密码学经典教材从凯撒到 AES 全覆盖。W. Stallings.Cryptography and Network Security(7th Edition). Pearson, 2017. —— 网络安全与密码学标准教材。A. J. Menezes, P. C. van Oorschot, S. A. Vanstone.Handbook of Applied Cryptography. CRC Press, 1996. —— 应用密码学手册免费在线版。本文标签#算法 #密码学 #凯撒密码 #密码强度 #密码合规 #NIST #Argon2 #洛谷题解 #信奥 #C #入门本文首发于CSDN作者HugoStudio_SWAN