#610. NOIP2013TG-21

NOIP2013TG-21

  1. (填空题)

某系统自称使用了一种防窃听的方式验证用户密码。

密码是 nn 个数 s1,s2,...,sns_1,s_2,...,s_n,均为 0011。该系统每次随机生成 nn 个数 a1,a2,...,ana_1,a_2,...,a_n,均为 0011,请用户回答 (s1a1+s2a2+...+snan)(s_1a_1 + s_2a_2 + ... + s_na_n) 除以 22 的余数。

如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。

然而,事与愿违。例如,当 n=4n=4 时,有人窃听了以下 55 次问答:

就破解出了密码:

s1s_1:{{ input(1) }}

s2s_2:{{ input(2) }}

s3s_3:{{ input(3) }}

s4s_4:{{ input(4) }}