密碼學(xué)：

• 數(shù)學(xué)基礎(chǔ)：? 各種用于從A到B里，與A相關(guān)的數(shù)學(xué)知識，包括概率論

• 計算機基礎(chǔ)： 包括了計算復(fù)雜性理論

• 密碼學(xué)基礎(chǔ)： 包括了各種術(shù)語、算法定義和安全定義

學(xué)什么不好，學(xué)密碼學(xué)？上輩子肯定殺人放火了 :(

今天，要解釋的知識是： 概率論里的隨機性

問題： p是一個大素數(shù)。 已知x從Z_p里隨機選, 然后計算 y=2x+1 mod p。 此時的y也是隨機的嗎？（y的隨機性和 從Z_p里隨機選一樣的嗎？）

答案1：當然也是隨機的。

答案2：不是隨機的，因為通過x可以計算y，所以y不是隨機的。

隨機，粗暴地理解，就是“不可預(yù)測+每個潛在的值出現(xiàn)的概率相同”

為了更清楚的表達，此時應(yīng)該添加個主語：小強！

小強已知w, 計劃知道z的值。

如果小強不能預(yù)測z的值，且z以等概率選到每一個潛在的值， 那么z對小強而言就是隨機的。

回到前面的問題：

問題： p是一個大素數(shù)。 已知x從Z_p里隨機選, 然后計算 y=2x+1 mod p。 此時的y也是隨機的嗎？（y的隨機性和 從Z_p里隨機選一樣的嗎？）

答案1：如果小強不知道x選到的值，那y是隨機的。

答案2：如果小強知道了x的值，那y就不再是隨機的。

所以，很多問題不清楚，那是因為定義不清。 我發(fā)現(xiàn)，當問題不清不楚的時候，把問題轉(zhuǎn)化為已知.....求.....就可以清楚很多了。

不知道這樣解釋是否清楚？那，清楚后，這能有啥屁用？這是接下來要討論的知識點。

安全歸約里，我們作者經(jīng)常用一個詞匯表達內(nèi)容“random and independent”。 除了隨機，還要獨立。為什么還要獨立呢，這是因為有了“獨立”，就可以把“已知”撇開了。 也就是說， 當x和y具有隨機且獨立時， 我們完全可以不用管小強知道不知道x，他一定不能預(yù)測到y(tǒng)。

大家都愛例子，我給個例子吧。

背景： 有一個數(shù)字簽名方案，每一個消息的簽名帶一個隨機數(shù)r。在安全歸約里，這個隨機數(shù)是通過r=f(m)模擬，where f(x) 是一個Z_p下的線性函數(shù)。

方法一： f(x)=ax+b 是個一次函數(shù)?，且（a，b）為隨機選。 在證明里，當敵人詢問得到n個消息的簽名時，對應(yīng)的隨機數(shù)為

r_1=f(m_1),? r_2=f(m_2), ...,?r_n=f(m_n)

從敵人證明者的角度，在敵人不知道其它隨機數(shù)r_j時，每一個r_i都可以看成隨機的。當敵人知道所有的隨機數(shù)時， 每一個r_i就不是隨機的，而是“非獨立”有關(guān)系的。 因此，也就出現(xiàn)了“可區(qū)分性”的證明錯誤問題。

方法二： f(x)=a_n x^n +...+a_2 x^2 +a_1 x +a_0是一個n次的多項式線性函數(shù)。

在證明里，當敵人詢問得到n個消息的簽名時，對應(yīng)的隨機數(shù)為

r_1=f(m_1),? r_2=f(m_2), ...,?r_n=f(m_n)

從敵人證明者的角度，即使敵人知道了所有的r_i， 它們每一個數(shù)也是隨機的， 因為知道r_1, r_2, .., r_{n-1}, 也不能預(yù)測到r_n, 因為它們是隨機+獨立的。

所以，BB簽名為什么要用到q-SDH? 不是作者無聊，而是無奈！

問題： p是一個大素數(shù)。 已知x從Z_p里隨機選, 然后計算 y=2x+1 mod p。 此時的y也是隨機的嗎？（y的隨機性和 從Z_p里隨機選一樣的嗎？）

答案： x和y都是隨機的，但它們不是獨立的。