信息保密技术

第2讲信息保密技术密码学发展简史密码学基本概念古典密码对称加密体制非对称加密体制2.1密码学的发展简史密码学有着悠久而迷人的历史，从古至今已有4000多年的历史了，密码学的发展大致经历了三个阶段：手工加密阶段、机械加密阶段和计算机加密阶段。1.手工加密阶段早在公元前1900年左右，一位佚名的埃及书吏在碑文中使用了非标准的象形文字,这或许是目前已知最早的密码术实例。古典密码的加密方法一般是采用文字置换，主要使用手工方式实现，因此我们称这时期为密码学发展的手工阶段。2.机械阶段到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无级电需求的出现，引起了密码设备的一场革命－发明了转轮密码机，转轮机的出现是密码学的重要标志之一。3.计算机阶段计算机科学的发展刺激和推动了密码学进入计算机阶段。1949年，C.Shannon发表了“保密系统的通信理论”，为密码学的发展奠定了理论基础，使密码学成为一门真正的科学。2.2密码学基本概念密码学（Cryptology）研究进行保密通信和如何实现信息保密的问题，具体指通信保密传输和信息存储加密等。密码学包括两个分支：密码编码学（Cryptography）和密码分析学（Cryptanalyst）。密码编码学研究怎样编码、如何对消息进行加密，密码分析学研究如何对密文进行破译。明文（Message）：待加密的信息，用M或P（Plaintext）表示。明文的集合构成明文空间，记为SM={M}。密文（Ciphertext）：经过加密处理后的形式，用Ｃ表示。密文的集体构成密文空间，记为SC={C}。密钥（Key）：用于加密或解密的参数，用K表示。密钥的集合构成密钥空间，记为SK={Ｋ}。加密（Encryption）：用某种方法伪装消息以隐藏它的内容的过程。加密算法（EncryptionAlgorithm）：将明文变换为密文的变换函数，通常用E表示，即E：SM→SC，表示为C=Ek(M)。2.2密码学基本概念解密（Decryption）：把密文转换成明文的过程。解密算法（DecryptionAlgorithm）：将密文变换为明文的变换函数，通常用D表示，即D：SC→SM，表示为M=Dk(C)。密码分析（Cryptanalysis）：截获密文者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员（Cryptanalyst）：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。这种攻击对密文没有进行任何破坏。主动攻击(Activeattack)：攻击者非法侵入一个密码系统，采用伪造、修改、删除、等手段向系统注入假消息进行欺骗。这种攻击对密文具有破坏作用。密码体制：由明文空间SM、密文空间SC、密钥空间SK、加密算法E和解密算法D构成的五元组{SM、SC、SK、E、D}，称为密码体制。2.2密码学基本概念密码系统（Cryptosystem）：用于加密和解密的系统。加密时，系统输入明文和加密密钥，加密变换后，输出密文；解密时，系统输入密文和解密密钥，解密变换后，输出明文。一个密码系统由信源、加密变换、解密变换、信宿和攻击者组成。KKMC加密变换Ｃ＝Ｅk(M)解密变换M＝Dk(C)信源信宿主动攻击者被动攻击者密钥器密钥器2.2密码学基本概念柯克霍夫（Kerckhoffs）原则：密码系统的安全性取决于密钥，而不是密码算法，即密码算法要公开。这是荷兰密码学家Kerckhoff于1883年在名著《军事密码学》中提出的基本假设。遵循这个假设的好处是：①它是评估算法安全性的惟一可用的方式。因为如果密码算法保密的话，密码算法的安全强度无法进行评估。②防止算法设计者在算法中隐藏后门。因为算法公开后，密码学家可以研究分析是否存在漏洞，同时也接受攻击者的检验。③有助于推广使用。当前网络应用十分普及，密码算法的应用不再局限于传统的军事领域，只有算法公开，才可能被大多数人接受并使用，同时，对用户而言，只需掌握密钥就可以使用了，勿须应用非常方便。2.3古典密码从古代到19世纪末提出和使用的密码称为古典密码古典密码大多比较简单，一般可用手工或机械方式实现其加密和解密过程，破译也比较容易。1.移位密码移位密码的加密方法是将明文字母按某种方式进行移位，如著名的恺撒密码。在移位密码中，将26个英文字母依次与0,1,2,…,25对应，密文字母c可以用明文字母m和密钥k按如下算法得到：c=m+k(mod26)给定一个密文字母c,对应的明文字母m可由c和密钥k按如下算法得到：m=c-k(mod26)按照密码体制的数学形式化定义，移位密码体制描述为五元组(P，C，K，E，D)，其中：P=C=K=Z26={0，1，2，…，25}E={ek:Z26Z26|ek(m)=m+k(mod26)}，D={dk:Z26Z26|dk(c)=ck(mod26)}。2.3古典密码2.仿射密码移位密码的加密方法是将明文字母按某种方式进行移位，如著名的恺撒密码。在移位密码中，将26个英文字母依次与0,1,2,…,25对应，密文字母c可以用明文字母m和密钥k按如下算法得到：c=m+k(mod26)给定一个密文字母c,对应的明文字母m可由c和密钥k按如下算法得到：m=c-k(mod26)按照密码体制的数学形式化定义，移位密码体制描述为五元组(P，C，K，E，D)，其中：P=C=K=Z26={0，1，2，…，25}E={ek:Z26Z26|ek(m)=m+k(mod26)}，D={dk:Z26Z26|dk(c)=ck(mod26)}。2.3古典密码例假设k1=9和k2=2，明文字母为q,则对其用仿射密码加密如下：先把文字母为q转化为数字13。由加密算法得c=913+2=119(mod26)=15再把c=15转化为字母得到密文P。解密时，先计算k11。因为93≡1(mod26)，因此k11=3。再由解密算法得m=k11(ck2)(mod26)=3(c-2)=3c-6(mod26)≡45+20(mod26)=13(mod26)。对应的明文字母为q。2.3古典密码3.维吉利亚(Vigenere)密码Vigenere是法国的密码学专家，Vigenere密码是以他的名字命名的。该密码体制有一个参数n。在加解密时同样把英文字母用数字代替进行运算，并按n个字母一组进行变换。明、密文空间及密钥空间都是n长的英文字母串的集合，因此可表示P=C=K=(Z26)n。加密变换如下：设密钥k=(k1,k2,…,kn)，明文P=(m1,m2,…,mn)，加密函数ek(P)=(c1,c2,…,cn)，其中ci=(mi+ki)(mod26),i=1,2,…,n。对密文c=(c1,c2,…,cn)，密钥k=(k1,k2,…,kn)，解密变换为dk(c)=(m1,m2,…,mn)，其中mi=(ciki)(mod26),i=1,2,…,n。2.3古典密码例设n=6，密钥是cipher，这相应于密钥k=(2,8,15,7,4,17)，明文是thiscryptosystemisnotsecure。试用Vigenere密码对其加密。解首先将明文按每6个分为一组，然后与密钥进行模26“加”得：19781821724151914182428157417281574172115232568023821221518194128181314191842201742815741728157417281520119191291522825819222519相应的密文是：VPXZGIAXIVWPUBTTMJPWIZITWZT2.3古典密码4.置换密码置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。实现的方法多种多样。在这里，我们介绍一类较常见的置换密码。其加解密方法如下：把明文字符以固定的宽度m(分组长度)水平地(按行)写在一张纸上（如果最后一行不足m，需要补充固定字符），按1，2，…，m的一个置换交换列的位置次序，再按垂直方向(即按列)读出即得密文。解密就是将密文按相同的宽度m垂直在写在纸上，按置换的逆置换交换列的位置次序，然后水平地读出得到明文。置换就是密钥。2.3古典密码例设明文Jokerisamurderer，密钥=(41)(32)(即(4)=1，(1)=4，(3)=2，(2)=3)),即按4，3，2，1列的次序读出得到密文，试写出加解密的过程与结果。解加密时，把明文字母按长度为4进行分组，每组写成一行，这样明文字母Jokerisamurderer被写成4行4列，然后把这4行4列按4，3，2，1列的次序写出得到密文。过程与结果如图2-3-1所示。解密时，把密文字母按4个一列写出，再按的逆置换重排列的次序，最后按行写出，即得到明文。明文：Jokerisamurderer按4字母一行写出jokerisamurderer按列写出的顺序4321按列写出密文：eadrksreoiurjrme密文：eadrksreoiurjrme按4字母一列写出ekojasirdrumrere交换列的顺序4321按行写出明文：jokerisamurderer2.3古典密码在现代密码学中，假定密码方案遵从Kerckhoffs原则，因此，对密文的破解取决于加密密钥。就古典密码而言，由于算法相对简单，算法复杂度也不高，一种可能的攻击方法是对所有可能的密钥进行尝试的强力攻击，称为穷举搜索攻击。移位密码：密钥空间K=Z26={0，1，2，…，25}，因此，最多尝试26次即可恢复明文。仿射密码：密钥空间为K={(k1，k2)|k1，k2Z26,其中gcd(k1,26)=1}，k1可能的取值有1，3，5，7，9，11，15，17，19，21，23，25，因此，最多尝试12×26次即可恢复明文。对于古典密码方案而言，由于密钥空间非常有限，因此，很难抵抗穷举搜索攻击。另一方面，就英文而言，一些古典密码方案不能很好地隐藏明文消息的统计特征，攻击者也可以利用这一弱点进行破译。结论：古典密码方案并不适合Kerckhoffs原则，算法的保密性基于算法的保密。2.4对称加密体制2.4.1序列密码2.4.2分组密码2.4.3数据加密标准－DES2.4对称加密体制在这种密码体制中，对于大多数算法而言，解密算法是加密算法的逆运算，加密密钥和解密密钥相同，满足关系：M=Dk(C)=Dk(Ek(M))。对称密码体制的开放性差，要求通信双方在通信之前，商定一个共享密钥，彼此必须妥善保管。对称密码体制分为两类。一类是对明文的单个位（或字节）运算的算法，称为序列密码算法，也称为流密码算法(StreamCipher)。另一类算法是把明文信息划分成不同的块（或小组）结构，分别对每个块进行加密和解密，称为分组加密算法(BlockCipher)。2.4.1序列密码序列密码将明文划分成单个位(如数字0或1)作为加密单位产生明文序列，然后将其与密钥流序列逐位进行模2加运算，用符号表示为，其结果作为密文。加密过程如图所示。加密算法是：解密算法是：2mod)(iiikmc2mod)(iiikcm2.4.1序列密码序列密码分为同步序列密码和自同步序列密码两种。同步序列密码要求发送方和接收方必须是同步的，在同样的位置用同样的密钥才能保证正确地解密。如果在传输过程中密文序列有篡改、删除、插入等错误导致同步失效，则不可能成功解密，只能通过重新同步来实现恢复。在传输期间，一个密文位的改变只影响该位的恢复，不会对后继位产生影响。自同步序列密码的密钥的产生与密钥和已产生的固定数量的密文位有关，因此，密文中产生的一个错误会影响到后面有限位的正确解密。因此，自同步密码的密码分析比同步密码更加困难。序列密码具有实现简单、便于硬件计算、加解密处理速度快、低错误（没有或只有有限位的错误）传播等优点，但同时也暴露出对错误产生不敏感的缺点。2.4.1