数学基础

本文介绍密码学中常用的一些符号和数学知识。

标准符号

$\#S$，集合$S$中的元素数目

$F_q$，q个元素的有限域

$desc(A)$，代数结构A的描述

$x\larr D$，根据分布$D$进行赋值

$x\larr _US$，按$S$为均匀分布进行赋值

$ord(x)$，群元素的阶

$<g>$，由g生成的循环群

概率论和信息论

概率论和信息论是现代密码技术发展必不可少的工具。

现代密码系统，特别是公钥密码系统，对概率行为的要求已经达到相当苛刻的程度：语义安全性。

概率论的基本概念

令$S$为一个任意确定的点的集合,称之为概率空间(或样本空间)。任意元素$x\in S$称为样点(也称为结果、简单事件或不可分事件;为了简单我们将只用点)。一个事件(也称为合成事件或可分事件)是$S$的一个子集,通常用一个大写字母表示(比如$E$)。一次实验或观察是一种从$S$中产生(取出)一个点的动作。一个事件$E$的发生就是一个试验产生某个点$x\in S$,并满足:$x\in E$。

概率的经典定义

假设一个实验可以从$n=\# S$个等可能的点中产生一个点，并且每次实验必须产生一个点。令$m$表示事件$E$包含的点的数目，那么$\frac{m}{n}$为事件$E$发生的概率，并记为$Prob[E]=\frac{m}{n}$

概率的统计定义

假设在相同条件下进行了$n$次实验，其中事件$E$发生了$\mu$次，如果对所有足够大的$n$，$\frac{\mu}{n}$保持不变，那么就是说事件$E$的概率为$\frac{\mu}{n}$，记为，$Prob[E]\approx \frac{\mu}{n}$

随机变量及其概率分布

在密码学中，我们主要考虑定义在离散空间上的函数。设离散空间$S$包含有限个或者可数个孤立的点$x_1,...,$

离散随机变量及其分布函数

一个离散随机变量是一个实验的数字化结果。它是定义在样本空间上的函数

设$S$为一个概率空间，$\xi$为一个随机变量。$\xi$的分布函数是$S\rarr R$的一个函数，以一个概率值$Prob[\xi=x_i]=p_i$

均匀分布

密码学中最常用的随机变量服从均匀分布：$Prob[\xi=x_i]=\frac{1}{ \# S}$

设$S$表示最长为$k$比特的非负数集合，依据均匀分布，从$S$中随机取出一个数，所取的数为k比特的概率是$\frac{1}{2}$

二项式分布

假定一个实验只有两个结果,记为“成功”和“失败”(例如,抛一枚硬币只有两个结果,“正面”和“反面")。独立地重复进行该实验,如果每一次实验结果仅有两种可能的点，且它们的概率在整个实验过程中保持不变,那么这样的实验就称为贝努利试验(bernoulli trials)。

假设在任何一次试验中：$Prob[Y]=p,Prob[N]=1-p$

那么$Prob[n\ test,k\ N]=C_n^kp^k(1-p)^{n-k}$

如果随机变量$\xi_n$取值为0，1，n，且对每一个p，$0< p<1$，有$Prob[\xi_n=k]=C_n^kp^k(1-p)^{n-k}$

那么我们说$\xi _n$服从贝努利分布

生日悖论

对任意函数$f:X\rarr Y$，其中$Y$为包含n个元素的集合，我们来解决下面的问题：

对于一个概率界限$\epsilon,0<\epsilon<1$，找一个整数$k$，使得对于$k$个两两互异的值$x_1,x_2,...,x_k\in_U X$，$k$个函数值$f(x_1),f(x_2),...,f(x_k)$对某些$i\ne j$有 $Prob[f(x_i)=f(x_j)]\ge \epsilon$

即在$k$个函数值中，以不小于$\epsilon$的概率发生碰撞

上述问题可以表示成：从装有$n$个不同颜色小球的袋子中去一个球，记下该球的颜色，然后放回。找到一个整数$k$，至少出现一次颜色匹配的概率为$\epsilon$。令$y_i$表示第$i$次取出的小球的颜色，第二次取出小球颜色不同的概率为$1-1/n$，以此类推，第$k$个球还未发生碰撞的概率为$(1-\frac{1}{n})(1-\frac{2}{n})...(1-\frac{k-1}{n})$

当n足够大且x相对较小时$1+\frac{x}{n}=e^{\frac{x}{n}}$

因此$(1-\frac{1}{n})(1-\frac{2}{n})...(1-\frac{k-1}{n})=e^{-\frac{k(k-1)}{2n}}$

这是不碰撞的概率，因此碰撞的概率为$1-e^{-\frac{k(k-1)}{2n}}=\epsilon$

我们有$k\approx \sqrt {2n\log \frac{1}{1-\epsilon}}$

考虑$\epsilon=1/2$，则$k=1.1774\sqrt{n}$，它表示对于一个输出空间大小为$n$的随机函数，我们只需计算大约$\sqrt n$个函数值，就能以一个不可忽略的概率发现一个碰撞。

如果说，我们将一组数据作为某个密码函数的原像隐藏，如果该数据的平方根不够大，那么就可以通过随即计算函数值来找出这组数据。这种攻击被称为生日攻击。它来源于：$n=365,k\approx22.49$，为了以大于50%的概率从房间中找到有两个人的生日相同，在该房间中只需有23人即可。

生日悖论的应用：指数计算的Pollard袋鼠算法

$p$为素数，$f(x)=g^x(mod\ p)$是一个随机函数，对于$x=1,2,..,p-1$，函数值$f(x)$在整数区间$[1,p-1]$范围内任意变化，这个函数具有单向性。求逆十分困难。

在某些情况下，我们知道a和b，可以计算$f(a),f(a+1),...$在穷尽b-a步之前找到x。如果b-a太大，那么这种穷搜索方法不现实。但如果$\sqrt{b-a}$是一个容易处理的值，那么生日悖论在$\sqrt{b-a}$步求$f(x)$中起到作用。

Pollard发现了这种方法，他称之为$\lambda$算法或袋鼠算法。

Pollard用两个袋鼠描述他的算法，一只是驯养的袋鼠$T$，另一只是野生的袋鼠$W$，已知$f(x)=g^x(mod\ p)$求解x的问题可以模型化为$T$追捕$W$。这一点是通过让袋鼠沿着跳跃的方式完成的。

$S=\{s(0),s(1),...,s(J-1)\}=\{2^0,2^1,...,2^{J-1}\}$

袋鼠每一次跳跃的距离为$S$中随机的一个数，每只袋鼠都随身携带一个里程表来计算它跳过的总距离。

$T$从已知点$t_0=g^b(mod\ p)$开始跳，$T$是驯服的袋鼠，它的路线为$t(i+1)=t(i)g^{s(t(i)mod\ J)}(mod\ p)$

在跳了n此后，$T$携带的里程表记录着它目前跳过的距离$d(n)=\Sigma_{i=0}^ns(t(i)mod\ J)$

我们将上面的表达式重新表达为$t(n)=g^{b+d(n-1)}mod\ p$

$W$是野生的，它从一个未知的点$w_0=g^xmod\ p$，它的路线为$w(i+1)=w(i)g^{s(w(i)mod\ J)}(mod\ p)$

$W$携带的里程表记录着它目前跳过的距离$D(j)=\Sigma_{k=0}^js(w_kmod\ J)$

我们将上面的表达式重新表达为$w(i)=g^{x+D(i-1)}mod\ p$

显然，它们的足迹$t(i)$和$w(j)$是两个随机函数，根据生日悖论，在$T$和$W$分别大约跳$n\approx\sqrt{b-a}$步内，发生碰撞，也就是跳在了同一个点。如果超过$n\approx\sqrt{b-a}$，那么碰撞发生的概率趋向于1.

信息论

香农关于消息源的熵(entropy)的定义用来衡量这个源所含信息量的多少。这个量度以源输出的所有可能的消息集上的概率分布函数形式给出。

设$L={a_1,a_2,...,a_n}$为由n个不同符号组成的语言，假设信源$S$以独立的概率$Prob[a_1],Prob[a_2],...,Prob[a_n]$分别输出这些符号，并且满足$\Sigma_{i=1}^nProb[a_i]=1$

S的熵为$H(S)=\Sigma_{i=1}^nProb[a_i]\log_2(\frac{1}{Prob[a_i]})$，我们称之为“每个信源输出的比特数”

如果$S$以概率1输出某个符号，例如$a_1$，则熵函数$H(S)$有最小值0，这是因为$H(S)=Prob[a_1]\log_2(\frac{1}{Prob[a_1]})=\log_21=0$，这种情况说明，当我们确信信源$S$确定地仅输出$a_1$，我们没必要浪费比特来记录它。