Cryptohack 密码学挑战 Write-Up：Jack‘s Birthday Confusion-北京尧图网络

1. 题目信息挑战名称Jacks Birthday Confusion所属分类Hash Functions哈希函数难度入门级链接CryptoHack – Challenges2. 题目描述Jack 设计了一个名为JACK11的哈希算法它产生11 位的固定长度输出即 11 个比特。题目问给定没有其他关于JACK11算法的信息平均需要尝试多少个不同的秘密值才能有75% 的概率发生一次碰撞即两个不同的秘密产生相同的哈希值我们需要利用生日悖论Birthday Paradox来计算这个值。3. 前置知识3.1 生日悖论Birthday Paradox生日悖论指出在一个房间里只需要23 个人就能有超过 50% 的概率找到两个生日相同的人。这看似反直觉但数学上完全成立。核心思想碰撞概率增长的速度比线性快得多因为我们需要考虑所有可能的配对。3.2 通用公式对于输出空间大小为 NN 的哈希函数当我们尝试 kk 个不同的输入时至少发生一次碰撞的概率为P(碰撞)≈1−e−k(k−1)/(2N)P(碰撞)≈1−e−k(k−1)/(2N)当 k≪Nk≪N 时这个近似非常精确。更精确的公式是P(碰撞)1−∏i0k−1(1−iN)P(碰撞)1−i0∏k−1(1−Ni)3.3 输出空间大小JACK11产生 11 位输出因此输出空间大小为N2112048N2112048这意味着哈希值可以是 0 到 2047 之间的任意整数。4. 解题过程4.1 已知条件哈希输出长度11 位输出空间大小N2112048N2112048目标概率75%即 0.75我们需要找到最小的 kk使得P(至少一次碰撞)≥0.75P(至少一次碰撞)≥0.754.2 使用近似公式1−e−k(k−1)/(2N)0.751−e−k(k−1)/(2N)0.75e−k(k−1)/(2N)0.25e−k(k−1)/(2N)0.25两边取自然对数−k(k−1)2Nln⁡(0.25)−2Nk(k−1)ln(0.25)k(k−1)2N−ln⁡(0.25)ln⁡(4)≈1.3862942Nk(k−1)−ln(0.25)ln(4)≈1.386294k(k−1)2N⋅ln⁡(4)2×2048×1.386294≈5677.54k(k−1)2N⋅ln(4)2×2048×1.386294≈5677.54k2−k−5677.540k2−k−5677.540用求根公式k114×5677.542122711.162k2114×5677.542122711.161150.7022≈75.8521150.702≈75.85因为 kk 必须是整数所以 k76k76。也就是说尝试 76 个不同的秘密值恰好有 75% 的概率发生碰撞。4.3 精确计算验证用 Python 精确计算pythonimport math N 2 ** 11 # 2048 def collision_probability(k, N): # 精确计算没有碰撞的概率 no_collision 1.0 for i in range(k): no_collision * (N - i) / N return 1 - no_collision def find_k(target_prob, N): k 1 while True: prob collision_probability(k, N) if prob target_prob: return k, prob k 1 target 0.75 k, prob find_k(target, N) print(f需要 {k} 个值才能达到 {target*100:.0f}% 的碰撞概率) print(f实际概率: {prob:.6f}) # 输出: # 需要 76 个值才能达到 75% 的碰撞概率 # 实际概率: 0.7503344.4 关于平均的说明题目问的是平均需要多少个秘密值。在概率统计中我们可以通过上述公式计算出达到特定概率所需的尝试次数。对于 75% 的概率答案是76。但要注意平均在这里可以理解为如果我们重复进行多次实验每次随机选择秘密值大约 75% 的实验会在尝试到第 76 个值时发生碰撞。4.5 可视化pythonimport matplotlib.pyplot as plt import numpy as np N 2048 k_values range(1, 200) probs [collision_probability(k, N) for k in k_values] plt.figure(figsize(10, 6)) plt.plot(k_values, probs, linewidth2) plt.axhline(y0.75, colorr, linestyle--, label75% 目标) plt.axvline(x76, colorg, linestyle--, labelk 76) plt.xlabel(尝试次数 k) plt.ylabel(碰撞概率) plt.title(JACK11 碰撞概率 vs 尝试次数 (N2048)) plt.grid(True, alpha0.3) plt.legend() plt.show()5. 两种常见的误解5.1 误解一50% 概率需要 NN 个值许多人会记住50% 碰撞概率需要约 NN 个值即 2048≈45.252048≈45.25。这是因为当 k≈Nk≈N 时碰撞概率约为 50%。这个近似来自P≈1−e−k2/(2N)P≈1−e−k2/(2N)当 kNkN 时P≈1−e−1/2≈0.3935P≈1−e−1/2≈0.3935实际上只有 39%。更准确的近似是 k≈2Nln⁡2≈2×2048×0.693≈2837≈53k≈2Nln2≈2×2048×0.693≈2837≈53。5.2 误解二75% 概率是 50% 概率的 1.5 倍这是错误的概率增长不是线性的。要达到 75% 的概率需要比 50% 多很多尝试。具体来说50% 概率约 54 个值75% 概率约 76 个值90% 概率约 97 个值99% 概率约 137 个值6. 答案推导总结步骤计算结果1输出位数112输出空间大小211204821120483碰撞概率公式P1−e−k(k−1)/(2N)P1−e−k(k−1)/(2N)4代入目标概率1−e−k(k−1)/40960.751−e−k(k−1)/40960.755解方程k≈75.85k≈75.856向上取整k76k767. 扩展思考7.1 通用公式对于任意输出空间大小 NN要达到碰撞概率 PP 所需的尝试次数 kk 为k≈⌈2N⋅ln⁡(11−P)⌉k≈⌈2N⋅ln(1−P1)⌉对于本题k⌈2×2048×ln⁡(10.25)⌉⌈4096×ln⁡(4)⌉⌈5677.54⌉⌈75.35⌉76k⌈2×2048×ln(0.251)⌉⌈4096×ln(4)⌉⌈5677.54⌉⌈75.35⌉767.2 生日悖论在密码学中的意义生日悖论直接影响哈希函数的安全性碰撞攻击对于 nn 位的哈希函数攻击者只需要尝试 2n/22n/2 次就能以 50% 概率找到碰撞而不是 2n2n 次。安全标准这就是为什么现代哈希函数如 SHA-256需要至少 256 位输出使得攻击者需要尝试 21282128 次这在计算上不可行。密码存储在密码哈希中也需要考虑生日攻击因此通常使用加盐salt来增加攻击难度。7.3 不同概率对应的尝试次数N2048概率尝试次数 k近似公式10%212N⋅0.1052N⋅0.10525%342N⋅0.2882N⋅0.28850%542N⋅0.6932N⋅0.69375%762N⋅1.3862N⋅1.38690%972N⋅2.3032N⋅2.30395%1112N⋅2.9962N⋅2.99699%1382N⋅4.6052N⋅4.6058. 相关代码速查python# 计算 75% 碰撞概率所需尝试次数 import math N 2 ** 11 P 0.75 k math.ceil(math.sqrt(2 * N * math.log(1 / (1 - P)))) print(k) # 输出: 76 # 验证概率 def prob_collision(k, N): return 1 - math.exp(-k * (k - 1) / (2 * N)) print(prob_collision(k, N)) # 输出: 0.7503349. 答案text7610. 参考资源Cryptohack - Hash Functions 系列Birthday Attack - WikipediaBirthday Problem - WikipediaNIST SP 800-107: Recommendation for Applications Using Approved Hash Algorithms

Cryptohack 密码学挑战 Write-Up：Jack‘s Birthday Confusion

相关推荐

修复指南：解决打开软件提示丢失 `api-ms-win-devices-query-l1-1-0.dll` 报错

全域透视，智守高墙——黎阳之光“透明监狱”重构智慧监管新范式

OWTB 3PL 智慧仓储管理系统 - 全设备清单本清单

更多资讯

嘉立创EDA专业版原理图绘制实战：从网络标签到模块化设计

卡丁车语音控制实战：硅麦选型、I²S配置与指令优化

Java毕设实战：宠物商务智慧管理系统全解析

TCP/UDP网络调试助手源码解析：C++与C#双语言实现与调试避坑

Blender建模模式+动态网格编辑+Geometry Script联动工作流详解

游戏引擎架构的本质：团队分工如何决定底层架构

今日更新

济南做网站多少钱：3个案例拆解，防黑源码下载全攻略

婚恋网站实战案例：避开3个高价坑，省钱50%还能跑赢流量

制作网页比较方便的软件怎么选?一文搞懂避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？