2 密码学的数学基础

2.1 信息论

2.1.1 熵与疑义度

假设所有的消息都有相等的可能性

那么一条消息种的信息量就表示：消息中所有可能的含义编码所需的最小的比特位数

例如：数据库中表示“星期”的字段包含不超过3bit的信息，000~110表示星期一到星期日，111不用

熵：用来形式化地衡量一条消息M中的信息量，记作H(M)。当用比特来衡量时，为 ${log_2{n}}$ ，其中n为消息的状态个数，假设所有状态有相等的可能出现概率

私以为：就是说比如星期一到星期天，假设这七种状态出现的概率相等，所以用比特衡量时，为 $log_2n$

信息量熵

定义：设随机变量 $X =$ { $x_i |i = 1,2,......n$ }， $X_i$ 出现的概率为p（ $x_i$ )>=0，且 $\sum_{i=1}^n p(x_i)=1$ 。则X的不确定性或熵定义为：

$H(X) = - \sum_{i=1}^n p(x_i) \log_2 p(x_i)$

从编码的角度，可理解为用最优的二进制编码形式表示所需的比特数
采用以2为低的对数时，相应的信息单位成为比特（Bit）
如果X均匀分布时候， $H(X)=log_2 n$
$H(X) \geq 0 $，当X为确定性的事件时，即 X 概率分布为 $p(X=a)=1$ ，则 $H(X)=0$

疑义度 ：消息的熵同时也可以衡量不确定性（疑义度），即如果将消息藏在密文中，需要破译它需要的明文比特数

例题1：

2 密码学的数学基础

解：令乙猜想作为事件V，V可能有十种结果，假定这十种结果是等概率的，则V的熵为：

$H(V)=-\frac{1}{10}log_2\frac{1}{10} \times 10 = log_2 10 = 3.32$

令事件 $A_k=U_1U_1U_3 \cdots U_k$ 为提k个问题，但是 $U_i$ 的熵不超过 $log_2 2 =1$ ，故 $A_k$ 的熵为不超过k比特，则：

$log_2 10 \leq k \cdot log_2 2 =k\qquad k\geq3.32$

所以K=4

**思考：**问题修改为甲任取不超过100相异的两个数，则k=？

$k\geq log_2 C_{100}^2 =12.27$

例题2：

有25个外表完全相同的硬币，其中24个重量完全一样，有一个较轻的伪币，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币？

借：事件V为找到伪币，共有25中可能，它们是等概率，所以：

$H(V)=log_2 25$

事件U为天平称的结果，可能有3种情况：1.左右平衡 2.右边重 3.左边重，所以：

$H(U)=log_2 3$

令 $A_k=U_1U_2U_3\cdots U_k$ 为连续用k次天平的事件，

$k\cdot log_23\geq log_2 25$

所以k最小为3

**思考：**如果有一枚假币（不知道轻重），用无砝码的天平试问要做多少次的比较，可以找到这枚假币，且是轻还是重？

事件V为找到假币硬币总共有以下几种情况

假币比较轻 25种情况
假币比较重 25种情况

所以共有50种可能，它们是等概率的，所以：

$H(V)=log_250$

事件U为天平称重的结果，可能有三种情况：1.左右平衡 2.右边重 3.左边重，所以：

$H(U)=log_2 3$

令 $A_k=U_1U_2U_3\cdots U_k$ 为连续用k次天平的事件，

$k\cdot log_23\geq log_2 50 \approx 3.572$

所以：最少4次

在密码学的应用:

2 密码学的数学基础

2.1.2 自然语言率

自然语言率：对于给定的一种语言，其自然语言率为：

$r=H(M)/N$

其中N为消息长度。

附：英语的自然语言率一般为 1bit/字母 ~1.5bit/字母

绝对语言率：每个字符编码的最大比特数，这里假设每个字符序列出现的机会相等。

若语言中有L个字母，则绝对语言率为：

$R = log_2L$

它是单个字母的最大熵。

英语的绝对语言率为：$log_226 \approx 4.7 $bit/字母

冗余度：语言的冗余度记为D，定义为：

$D=R-r$

其中R为绝对语言率，r为自然语言率。

英语：r=1.3bit/字母 R=4.7bit/字母 D=3.4bit/字母

2.1.3 密码系统的安全性

绝对安全的密码系统：一次一密（**与消息本身一样长，且**不重复使用）
密码系统的熵：衡量**空间K的大小的一个标准，通常是**数以2为底的对数。

$H(K)=log_2 k$

2.1.4 确定性距离

对于长度为n的消息，能够将一段密文消息解密成与原始明文同种语言的可懂文本的**个数为： $2^{H(K)-nD}-1$

其中 $H(K)$ 为密码系统的熵，n为消息长度，D为语言的冗余度。

确定性距离：能够唯一地确定**的最短的密文长度的近似值。

对称密码系统的确定性距离：定义为密码系统的熵除以语言的冗余度：
$U=H(K)/D$

理想安全的密码系统：确定性距离无限大的密码系统

2.1.5 混乱与扩散

混乱：在加密变换中，让**与密文的关系尽可能复杂的做法。
实现混乱的方法：代替
扩散：在加密过程中，尽可能将明文的统计特性在密文中消除。
实现扩散的方法：换位

2.2 复杂性理论

2.2.1 算法复杂性

算法的复杂性常常用两个变量来衡量：T（时间复杂性）和S（空间复杂性，或存储需求）

T和S都用n的函数来表示，n为输入的大小

数量级法：当n增大时，复杂性函数中增加的最快的一项

2 密码学的数学基础

2.2.2 问题复杂性

图灵机：一个有限状态机，具有无限的读写存储磁带，是一个理想化的计算模型。

问题：

易解的问题：可以在多项式时间内求解
难解的问题：只能在指数时间内求解
不确定的问题：找不出解决的算法，不考虑算法的时间复杂性

2 密码学的数学基础

对于问题复杂性的划分：

P问题：可以在多项式时间内求解的问题
NP问题：只能在一个非确定性的图灵机（能够进行猜测的一种图灵机）上在多项式时间内求解的问题。
- NP完全问题：一些特定的NP问题，与其他NP问题同等困难。
P空间问题：可以在多项式空间内求解，不能再多项式时间内求解的问题
- P空间完全问题：与其他P空间问题同等空难
指数时间问题

2 密码学的数学基础

2 密码学的数学基础

2.1 信息论

2.1.1 熵与疑义度

熵：用来形式化地衡量一条消息M中的信息量，记作H(M)。当用比特来衡量时，为log2n{log_2{n}}log2​n，其中n为消息的状态个数，假设所有状态有相等的可能出现概率

信息量熵

在密码学的应用:

2.1.2 自然语言率

2.1.3 密码系统的安全性

2.1.4 确定性距离

2.1.5 混乱与扩散

2.2 复杂性理论

2.2.1 算法复杂性

2.2.2 问题复杂性

对于问题复杂性的划分：

相关推荐

熵：用来形式化地衡量一条消息M中的信息量，记作H(M)。当用比特来衡量时，为 ${log_2{n}}$ ，其中n为消息的状态个数，假设所有状态有相等的可能出现概率