【密码学复习】第三讲密码学基础
Shannon通信保密系统
一个密码体制是一个五元组：（P, C, K, E, D )
其中，
P --明文空间
C --密文空间
K--密钥空间
E --加密变换
D --解密变换
一个加密变换是一个下列形式的映射：
E: P× K → C
一般对于给定的k∈ K,把E(*,k)记为Ek ;
Ø一个解密变换是一个与加密E变换相对应的映射：
D: C×K → P
对于给定的k∈K,也把D(*,k)记为Dk
熵和无条件保密
熵和无条件保密
若将X视为一个系统的输入空间，Y视为系统的输出空间，在通信中，X和Y之间的平均互信息定义为：
I(X,Y)=H(X)-H(X|Y)
它表示X熵减少量
定义：密码系统（
P,C,K,E,D）是完善保密（无条件保密）的充分必要条件是
H (P | C) =H(P) 或I (P , C)= 0
• 时间（计算）复杂性：考虑算法的主要操作步骤，计算执行中所需的总操作次数.
• 空间复杂性：执行过程中所需存储器的单元数目.
• 数据复杂性：信息资源
定义假设一个算法的计算复杂度为O(nt )，其中t为常数，n为输入问题的长度（log2明文），则称这算法的复杂度是多项式的。具有多项式时间复杂度的算法为多项式时间算法
非多项式时间算法：算法的计算复杂性写不成O(P(n))形式，其中P(n)表示n的多项式函数.
P问题和NP问题
• 定义(P问题)如果一个判定问题存在解它的多项式时间的算法，则称该问题属于P类.
• 定义(NP问题) 如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答可以在多项式时间验证其是否正确，则称该问题属于NP类
计算安全性
当问题输入长度足够大，分析密码体制的算法的复杂度较大，可能的计算能力下，在保密的期间内可以保证算法不被攻破，这就是密码体制的计算安全性思想。
实际安全是指密码系统满足以下准则之一：
Ø 破解该密码系统的成本超过被加密信息本身的价值；
Ø 破译该密码系统的时间超过被加密信息的有效生命周期