密码学原理及案例解析

第1章 密码学 密码学（Cryptology）作为数学的一个分支，是密码编码学（Cryptography）和密码分析学（Cryptanalysis）的统称。密码学通过加密变换，将可读的信息变换为不可理解的乱码，从而起到保护信息和数据的作用，直接支持机密性、完整性和不可否认性。当前信息安全的主流技术和理论都是基于以算法复杂性理论为特征的现代密码学的。密码学的发展历程大致经历了三个阶段：古代加密方法（手工阶段）、古典密码（机械阶段）和近代密码（计算机阶段）。 密码学中的五元组为{明文、密文、密钥、加密算法、解密算法}，对应的加密方案称为密码体制。明文是作为加密输入的原始信息，通常用m来表示，明文空间通常用M表示；密文是明文加密变换后的结果，通常用c表示，密文空间通常用C表示；密钥是参与密码转换的参数，通常用k表示，密钥空间通常用K表示；加密算法是将明文变换为密文的变换函数，加密过程通常用E表示，即c=Ek（m）；解密算法是将密文恢复为明文的变换函数，解密过程通常用D表示，即m=Dk（c）。 密码体制是指完成加解密功能的密码方案。近代密码学中所出现的密码体制从原理上可分为两大类，即对称密码体制和非对称密码体制。对称密码体制也称为单密钥密码体制，基本特征是加密密钥与解密密钥相同，根据其对明文的处理方式可分为流密码和分组密码。非对称密码体制也称为公开密钥密码体制、双密码体制，其加密密钥和解密密钥不同，形成一个密码对，用其中一个密钥加密的结果可以用另一个密钥来解密。 古典密码学案例分析主要包括移位密码、乘法密码、仿射密码、Playfair密码、维吉尼亚密码等；流密码加密案例分析包括RC4和LFSR等算法的加解密案例分析。对称密码基本加密案例分析主要包括DES、3DES、IDEA、AES和SMS4等算法的加解密案例分析。对称密码工作模式案例分析主要是针对不同算法采用不同的分组方式和填充模式进行加密案例分析；散列函数案例分析包括MD5、SHA-1/256和HMAC等算法的加解密案例分析。非对称加密案例分析包括RSA、ELGAMAL、ECC等算法的加解密案例分析和密钥生成案例分析；数字签名案例分析包括RSA-PKCS签名算法、ELGAMAL签名算法、DSA签名算法和ECC签名算法等签名算法的案例分析；密码学数学基础案例分析主要针对密码学常用的数学知识进行相应的案例分析，包括大数运算、素性测试、模幂、原根、求逆和二次剩余等。文件加解密案例分析包括对文本、图片、音频、视频等多种格式的文件的加解密案例分析。数据库加解密应用案例分析包括单元级加密和数据库级加密案例分析。基于SSH协议的通信安全案例分析包括密码认证方式和密钥认证方式的SSH案例分析。基于GnuPG的加密及签名案例分析使用GnuPG实现文件及邮件的加解密和签名。PGP在文件系统、邮件系统中的应用则使用PGP实现文件及邮件的加解密和签名。 1.1 古典密码 古典密码学主要包括移位密码、乘法密码、仿射密码、Playfair密码、维吉尼亚密码等。 古典密码体制的一般定义为M=C=K=Z26，其中M为明文空间，C为密文空间，K为密钥空间，Z26为26个整数（对应26个英文字母）组成的空间；要求26个字母与模26的剩余类集合{0，1，2， ，25}建立一一对应的关系。 1.1.1 移位密码 移位密码在加密实现上就是将26个英文字母向后循环移动k位，其加解密可分别表示为c=Ek（m）=m=k（mod26），m=Dk（c）=c-k（mod26）其中，m、c、k是满足0≤m，c，k≤25的整数。 1.1.2 乘法密码 乘法密码通过对字母等间隔抽取以获得密文，其加解密可分别表示如下c=mk（mod26）m=ck-1（mod26）其中，m、c、k是满足0≤m，c，k≤25，且gcd（k，26）=1的整数。 1.1.3 仿射密码 仿射密码的加密是一个线性变换，将移位密码和乘法密码相结合，其加解密可分别表示为c=Ea，b（m）an=b（mod26）m=Da，b（m）=a-1（c-b）（mod26）其中，a、b是密钥，是满足0≤a，b≤25和gcd（a，26）=1的整数，即a和26互素；a=1表示a的逆元，即a-1 a≡1mod26。 1.1.4 Playfair密码 Playfair是一种人工对称加密技术，由Charles Wheatstone在1854年发明，得名于其推广者Lord Playfair。Playfair密码是一种著名的双字母单表替代密码。实际上Playfair密码属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合。Playfair密码基于一个5×5的字母矩阵，该矩阵通过使用一个英文短语或单词串即密钥来构造，去掉密钥中重复的字母得到一个无重复字母的字符串，然后将字母表中剩下的字母依次从左到右、从上往下填入矩阵中。 例如，若密钥为“playfair is a digram cipher”，去除重复字母后，得到有效密钥“playfirsdgmche”，可得字母矩阵如图1.1所示。 注意：字母i、j占同一个位置。 图1.1 字母矩阵 设明文字母对为（P1，P2），Playfair密码的加密算法如下。 （1）若P1、P2在同一行，密文C1、C2分别是紧靠P1、P2右端的字母，其中**列被看作*后一列的右方（解密时反向）。 （2）若P1、P2在同一列，密文C1、C2分别是紧靠P1、P2下方的字母，其中**行被看作*后一行的下方（解密时反向）。 （3）若P1、P2不在同一行，也不在同一列，则C1、C2是由P1、P2确定的矩形其他两角的字母，且C1和P1在同一行，C2和P2在同一行（解密时处理方法相同）。 （4）若P1=P2，则两个字母间插入一个预先约定的字母，如q，并用前述方法处理；如balloon，则以balqloon来加密。 （5）若明文字母数为奇数，则在明文尾填充约定字母。 1.1.5 维吉尼亚密码 维吉尼亚（Vigenenre）密码是*著名的多表代换密码，是16世纪法国著名密码学家Blaise de Vigenenre发明的。维吉尼亚密码使用一个词组作为密钥，密钥中每一个字母用来确定一个代换表，每一个密钥字母被用来加密一个明文字母，**个密钥字母加密**个明文字母，第二个密钥字母加密第二个明文字母，等所有密钥字母使用完后，密钥再次循环使用，于是加解密前需先将明/密文按照密钥长度进行分组。密码算法可表示如下： 设密钥K=（k1，k2， ，kd），明文M=（m1，m2， ，mn），密文C=（c1，c2， ，cn）； 加密变换为ci=Eki（mi）=mi+ki（mod26） 解密变换为mi=Dki（ci）=ci-ki（mod26） 通常通过查询维吉尼亚表进行加解密。 此处以移位密码为例说明，乘法密码、仿射密码、Playfair密码和维吉尼亚密码可参照完成。 1.加解密计算 （1）参照案例分析原理，在“明文”栏输入所要加密的明文，在“密钥”栏输入相应的密钥长度，如图1.2所示。 图1.2 输入明文和密钥长度 （2）单击“加密”按钮，在“明文”文本框内就会出现加密后的密文。 2.扩展案例分析 （1）单击扩展案例分析下的按钮，进入相应算法的扩展案例分析面板，此处以移位密码扩展案例分析面板，如图1.3所示。 图1.3 移位密码扩展案例分析面板 （2）在“密钥k”栏中输入一个0～25的整数，如19，单击“确定”按钮后，系统显示“明文-密文映射表”。 （3）在“明文”文本框中输入明文（如“Classical Cryptology.”），并单击“加密”按钮，在“密文”文本框内就会出现加密后的密文。 （4）解密过程是加密过程的逆过程，在“密文”文本框中输入密文（确保密钥已经正确输入），单击“解密”按钮即可得到相应的明文。 3.算法跟踪 1）加密跟踪 （1）选择要跟踪的算法即移位密码，在相应的算法计算区域填写明文和密钥。 （2）单击“跟踪加密”按钮，此时会弹出选择跟踪调试器对话框，对话框中所列出的可选调试器根据系统中所安装的调试器而不同。 （3）选择“新实例Microsoft CLR Debugger2005”或其他调试器并单击“是”按钮，打开调试器窗口，出现选择编码的对话框时选择“（自动检测）”，进入代码跟踪界面。 （4）选择对应C#源代码的xxx.cs标签页并按下快捷键F10开始跟踪，如图1.4所示。 （5）当算法跟踪完毕后，会自动切换回案例分析窗口并显示计算结果。 （6）查看案例分析面板中的计算结果，然后切换回调试器，单击工具栏中的“停止调试”按钮或按Shift+F5快捷键以停止调试。 （7）关闭调试器，弹出保存对话框，单击“否”按钮不保存。 图1.4 跟踪过程 2）解密跟踪 跟踪解密算法时，选择要跟踪的算法，在相应的算法计算区域填写密文和密钥，单击“跟踪解密”按钮会显示解密跟踪过程，具体步骤与加密跟踪步骤类似，在此不再赘述。 1.2 密码学数学基础 大多数运算器只支持小于64位的整数运算，无法进行加密算法的运算。为满足加密算法的需要，可通过建立大整数运算库来解决这一问题，通常通过以下两种方式进行处理。 （1）将大整数当作字符串处理，即将大整数用十进制字符数组表示。这种方式便于理解，但效率较低。 （2）将大整数当作二进制流进行处理，计算速度快。 大数运算包括素性测试、模幂、原根、求逆、二次剩余等。 1.2.1 素性测试 Monte Carlo算法和Las Vegas算法均为素性测试算法。 1.Monte Carlo算法 Monte Carlo算法又称为概率素性检测算法，算法描述如下。 输入：p为一个正整数。 输出：若p为素数，则输出YES，否则输出NO。 Prime_Test（p） flag=0； 重复log2p次： 在（1，p-1]区间均匀随机地选取x； 如果gcd（x，p）>1或x（p-1）/2≠±1modp，return（NO）； 如果flag=0且x（p-1）/2=-1modp，flag=1； 结束重复； 如果flag=0，即在重复中x（p-1）/2=-1modp没有出现过，return（NO）； return（YES） 2.Las Vegas算法 Las Vegas算法又称为素性证明，算法描述如下。 输入：p为一个正基数；q1，q2， ，qk为p-1的全体素因子，其中k≤log2p。 输出：若p为素数，则输出YES，否则输出NO。 Prim_Certify（p，q[k]） 在区间[2，p-1]均匀随机地选取g for（i=1，i++，k）do 如果g（p-1）/qi=1modp，输出NO_DECISION并终止程序； 如果g（p-1）=1modp，输出NO并终止程序； 输出YES并终止程序 1.2.2 模幂 对于b，c　　输入：整数b、c、m，其中b>0，c≥0，m>1。 输出：bc mod m。