NOIP 提高 2013 第一轮 第 21 题：就破解出了密码s1 =_ ，s2 = _，s3 =_ ，s4 =_

题目

某系统自称使用了一种防窃听的方式验证用户密码。密码是 $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ᵢ) mod 2。同时满足防窃听与可验证的方案：

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

易错提醒

① 一次一密思想：随机掩码 a 使回答不泄漏 s；② 逐方案对照题面四条说法。