你好,密码学(3):离散概率(速成课)(续)

导览

课程地址请见Coursera

对于离散概率的更详细解释,请见:WikiBooks (English)

注意:文章中对专业名词进行解释的链接均来自维基百科,中国大陆读者若想访问请自备… …

若未阅读上篇文章密码学I:离散概率的,强烈建议前去阅读。

独立性

定义

独立性:若存在两事件$A$、$B$,$A$事件的发生无法向你提供关于$B$事件的任何信息,则称$A$、$B$两事件是互相独立的。即:
$$
Pr[A\;\:\mathtt{and}\;\:B]=Pr[A]\cdot Pr[B]
$$

通常来讲,独立性衡量的是两事件间互不相关的程度。

随机变量中的独立性

若有两个在集合$V$中取值的随机变量$X,Y$,那么如果这两个随机变量满足:
$$
\forall a,b\in V\\
Pr[X=a\;\:\mathtt{and}\;\:X=b]\;\;=\;\;Pr[X]\cdot Pr[Y=b]
$$

这意味着即使你知道$X=a$你也不知道关于$y$的取值的任何信息。

异或运算(XOR)

这是一种在密码学中相当重要的运算。

关于其重要的原因我们将稍后讲到。

定义

一种对数值$A$和$B$进行的运算,记为:
$$
A\oplus B
$$
其运算基本规则为:两两数值相同时为假,而数值不同时为真。

这也就是说,$15\oplus 17=true$,$15\oplus 15=false$。

通常来讲,我们所写的形如$100101\oplus 110110$不是对整个数值进行运算,而是对数值的每一位进行运算。即(一般我们用$1$表示“真”,用$0$表示“假”):$$100101\oplus 110110=010011$$

请见:维基百科 - 逻辑异或(中文 - 大陆简体)

异或运算(XOR)的重要性质

阐述:若存在一个随机变量$y$,和一个独立均匀随机变量$x$,此时$x$和$y$的异或(无论$y$以什么方式分布)$z$总是一个均匀的随机变量

换句话说如果我取一个随机的分布,然后用独立均匀随机变量和它进行异或运算,最终得到的一定是一个均匀随机变量,即:
$$
Y\mathtt{\quad is\;\:a\;\:\mathbf{rand.}\;\:var.\;\:over\quad}{0,1}^2,\\
X\mathtt{\quad is\;\:an\;\:\mathbf{indep.\;\:uniform}\;\:var.\;\:on\quad}{0,1}^2\\
\mathtt{Than\;\;}Z:Y\oplus X\mathtt{\quad is\;\:\mathbf{uniform}\;\:var.\;\:over\quad}{0,1}^2
$$
证明现不列出。可能会在作者博客上给出。

生日悖论(The birthday paradox)

##定义
定义:假设在全集$U$中选择几个独立、以相同方式分布的随机变量$n$ ,则如若选择$\sqrt{|U|}$次,则基本上有很大的几率(超过$\frac{1}{2}$)会有两个相同的元素。换句话说,若抽样$\sqrt{|U|}$次,那么很有可能(超过$\frac{1}{2}$)你的两个抽样会是 一样的,即:
$$
r_1,…,r_n\in U\mathtt{\quad are\;\:indep.\;\:and\;\:has\;\:same\;\:way\;\:of\;\:distribution}\\
\mathtt{when}\quad n=1.2 \times \sqrt{|U|} \quad \mathtt{than}\quad Pr[\exists i\neq j: \;r_i=r_j ]\ge \frac{1}{2}\\
\text(\exists \quad \text{means “exist”)}
$$

该定理被叫做“悖论”是因为经常使用该定理来描述人们的生日。因为根据该定理,最少仅仅需要$1.2\times\sqrt{365}$个人聚集在一起就能够使得有两个人有同样的生日的概率大于$\frac{1}{2}$,即24个人。这就是为什么叫做悖论,因为24应该是一个比大多数人的预计都要小的数。

##应用
Slide-1
假设我们有一个100万样本的全集,那么当我们抽样大概1200次时, 我们抽样到相通数字元素的概率大约是$0.5$;但是你可以看到如果我们抽样2200次,有两个元素相同的概率就已经是$0.9$了;你也看到了抽样3000次时基本就是$1$了。所以只要取样个数超过全集大小的平方根,抽到相同元素的概率将会很快趋近于1

以后我们会再返回并更具体地学习生日悖论,但目前就到此为止。

结语

本节和上一节主要介绍了概率分布基础、事件、随机变量基本知识以及一种在密码学中非常常用也非常重要的算法XOR(异或运算,$\oplus$)及其基本性质,最后简要介绍了密码学中一个非常中心的理论:生日悖论。
本节和上一节的知识相当基础和重要。

下一节/下一章我们会开始学习我们的加密系统的第一个例子。

本节完

=。=
0%