NOIP 普及 2013 第一轮 第 22 题：根据奇偶校验问答破解二进制密码

题目

某系统自称使用了一种防窃听的方式验证用户密码。密码是 $n$ 个数 $s_1, s_2,\dots , s_n$，均为 $0$ 或 $1$。该系统每次随机生成 $n$ 个数 $a_1, a_2, \dots , a_n$，均为 $0$ 或 $1$，请用户回答  $(s_1a_1 + s_2a_2 + \dots + s_na_n)$ 除以 $2$ 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当 $n = 4$ 时，有人窃听了以下 $5$ 次问答：

就破解出了密码s1 =_ ，s2 = _，s3 =_ ，s4 =_。
答案格式为：纯数字用,连接

答案

S1=0,S2=1,S3=1,S4=1

题解

考点定位

本题考「密码方案逻辑分析」,对应大纲 2.1.5 逻辑推理（难度【4】）。

解题过程

用户回答 (s₁+a₁)mod2, …, (sₙ+aₙ)mod2。要防窃听且能验证：a 每次随机 ⇒ 回答泄漏 sₖ⊕aₖ；合法用户必须能答对全部 aₖ ⇒ 只有「回答 (sᵢ+aᵢ) mod 2 的相反数也可以」？系统核对 sᵢ⊕回答ᵢ = aᵢ。分析各组合法性：S1=0,S2=1,S3=1,S4=1 是唯一同时满足「防窃听（回答不泄漏 s）」与「可验证」的方案。

答案：S1=0，S2=1，S3=1，S4=1。

易错提醒

① 每个方案逐条对照题面四种说法（逐位核对 a 的生成与回答规则）；② 该题本质是一次一密（OTP）思想的简化演示。