安全归约困惑之随机问题
密码学：
数学基础： 各种用于从A到B里，与A相关的数学知识，包括概率论
计算机基础： 包括了计算复杂性理论
密码学基础： 包括了各种术语、算法定义和安全定义
学什么不好，学密码学？上辈子肯定杀人放火了 :(
今天，要解释的知识是： 概率论里的随机性
问题： p是一个大素数。 已知x从Z_p里随机选, 然后计算 y=2x+1 mod p。 此时的y也是随机的吗？（y的随机性和 从Z_p里随机选一样的吗？）
答案1：当然也是随机的。
答案2：不是随机的，因为通过x可以计算y，所以y不是随机的。
随机，粗暴地理解，就是“不可预测+每个潜在的值出现的概率相同”
为了更清楚的表达，此时应该添加个主语：小强！
小强已知w, 计划知道z的值。
如果小强不能预测z的值，且z以等概率选到每一个潜在的值， 那么z对小强而言就是随机的。
回到前面的问题：
问题： p是一个大素数。 已知x从Z_p里随机选, 然后计算 y=2x+1 mod p。 此时的y也是随机的吗？（y的随机性和 从Z_p里随机选一样的吗？）
答案1：如果小强不知道x选到的值，那y是随机的。
答案2：如果小强知道了x的值，那y就不再是随机的。
所以，很多问题不清楚，那是因为定义不清。 我发现，当问题不清不楚的时候，把问题转化为已知.....求.....就可以清楚很多了。
不知道这样解释是否清楚？那，清楚后，这能有啥屁用？这是接下来要讨论的知识点。
安全归约里，我们作者经常用一个词汇表达内容“random and independent”。 除了随机，还要独立。为什么还要独立呢，这是因为有了“独立”，就可以把“已知”撇开了。 也就是说， 当x和y具有随机且独立时， 我们完全可以不用管小强知道不知道x，他一定不能预测到y。
大家都爱例子，我给个例子吧。
背景： 有一个数字签名方案，每一个消息的签名带一个随机数r。在安全归约里，这个随机数是通过r=f(m)模拟，where f(x) 是一个Z_p下的线性函数。
方法一： f(x)=ax+b 是个一次函数 ，且（a，b）为随机选。 在证明里，当敌人询问得到n个消息的签名时，对应的随机数为
r_1=f(m_1), r_2=f(m_2), ..., r_n=f(m_n)
从敌人证明者的角度，在敌人不知道其它随机数r_j时，每一个r_i都可以看成随机的。当敌人知道所有的随机数时， 每一个r_i就不是随机的，而是“非独立”有关系的。 因此，也就出现了“可区分性”的证明错误问题。
方法二： f(x)=a_n x^n +...+a_2 x^2 +a_1 x +a_0是一个n次的多项式线性函数。
在证明里，当敌人询问得到n个消息的签名时，对应的随机数为
r_1=f(m_1), r_2=f(m_2), ..., r_n=f(m_n)
从敌人证明者的角度，即使敌人知道了所有的r_i， 它们每一个数也是随机的， 因为知道r_1, r_2, .., r_{n-1}, 也不能预测到r_n, 因为它们是随机+独立的。
所以，BB签名为什么要用到q-SDH? 不是作者无聊，而是无奈！
问题： p是一个大素数。 已知x从Z_p里随机选, 然后计算 y=2x+1 mod p。 此时的y也是随机的吗？（y的随机性和 从Z_p里随机选一样的吗？）
答案： x和y都是随机的，但它们不是独立的。
