§9.2 信息安全与数据加密
要保证信息安全地传输，其核心是加密技术的安全问题。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。
军事领域的需要促使加密技术的发展！并扩展到商用、民用领域。
1、加密技术的历史
斯巴达密码棒（Scytale）
加密方式：把长带子状羊皮纸缠绕在圆木棍上，然后在上面写字；解下羊皮纸后，上面只有杂乱无章的字符，只有再次以同样的方式缠绕到同样粗细的棍子上，才能看出所写的内容。
成长史：现代密码电报就是在此基础上发展而来。
恺撒密码(Caesar)
加密方式：从A到Z的每个字母在加密时用字母表中位于后N位的那个字母代替，如3位则字母XYZ分别被替换成ABC。在三个移位的情况下，信息DOG（这种需要加密的信息统称“明文”）就变换成GRJ（这种经加密后产生的的信息统称“密文”）可以看到，加密、解密过程都是以字母移位的位数为参照的。这种在加密和解密的算法中依赖的参数则被称为——密钥。
当然，移位的选择并不仅仅限制在三位，从1到26任何数的移位都能产生类似效果。只要通信双方事先约定好，这个选择就很任意。很明显的是，移位方法最多也只有26种，这成为凯撒密码的致命弱点。
二战德国German Enigma机
加密方式：Enigma转轮组，正是多表替代——它通过不断改变明文和密文的字母映射关系，对明文字母们进行着连续不断的换表加密操作。
u三个转子不同的方向组成了262626=17576种不同可能性；
u三个转子间不同的相对位置为6种可能性；
u连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种；于是一共有175766100391791500，大约为10000000000000000，即一亿亿种可能性。
近代密码理论的奠基人—香农
1949年，香农发表了« 密码体制的通信理论»。
20世纪70年代中期
Ø Diffie和Hellman提出了“公钥密码”思想。公钥密码冲破了传统“单钥密码”体系的束缚，这种加密体系中不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。
Ø 美国国家标准局于1977年公布实施美国数据加密标准（DES），这是保密学史上第一次公开加密算法，并广泛应用于商用数据加密。
2、加密与加密系统
加密系统的组成
加密系统由明文(Plaintext)、密文(Cryptograph)、密钥(Key)、加密(Encipher)、解密(Decipher)组成。密钥：参与加密或解密变换的参数。
3、古典加密技术
移位密码：基于数论中的模运算。以英文字母符号集来说，因为共有26个字母，故可将移位密码形式地定义如下：
明文空间：P={A,B,C,…,Z} 密文空间：C={A,B,C,…,Z}
加密变换：C=Ek(P)=(p+k) mod 26 解密变换：P=Dk(C)=(c-k) mod 26
p表示明文字符在明文空间中字母的顺序，c表示加密字符在密文空间中字母的顺序，k表示密钥在密钥空间的取值。式中，mod表示取模运算（取余运算）。
例题1：若明文为“park”，假设k=4，试用移位加密方法将其加密为(tevo)。
例题2：若密文为"park"，假设k=4，用移位加密法求出的明文是(lwng)。
凯撒密码（移位密码）应用实例：是k=3的情况。通过向右移动源字母表3个字母，则形成如下代换字母表（密码本）：
例题3：在恺撒密码中，明文是“park”，k=3,则密文是(sdun)。
换位密码（又称置换密码）和替代密码技术相比，换位密码技术并没有替换明文中的字母,而是通过改变明文字母的排列次序来达到加密的目的。
1.换位就是将明文中的字母的位置重排。最简单的换位就是逆序法：
明文：computer system 密文：metsys retupmoc
2.列置换（纵行换位）：把明文中的字符按列重新排列。
明文：THIS IS A MESSAGE. 密文：TSSHAAIMGSEEISX
3.引入密钥k 如k=COMPUTER，
明文为：WHAT CANYOU LEARN FROM THIS BOOK
密文为：WORO NNSXALMK HUOO TETX YFBX ARIX CAHX
4、对称密钥密码系统
按使用密钥的不同，将现有的密码体制分为两种：对称密钥密码系统和公开密钥密码系统（非对称密钥密码系统）
对称密钥密码系统：加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接受者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码）。因此，通信双方都必须获得这把钥匙，并保持钥匙的秘密，加密算法和解密算法是公开的。
5、公开密钥密码系统
公开密钥密码系统：加密和解密使用的是不同的密钥（称为非对称密钥），这两个密钥之间存在着相互依存关系，即用其中任一个密钥加密的信息只能用另一个密钥进行解密。加密密钥和加密算法和解密算法是对外公开的，人人都可以通过这个密钥加密文件，然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文件后，可以使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并不需要分发，因此又称为私钥（不公开的秘钥），这就解决了密钥分发的问题。
如果A方利用公开密钥系统发一条信息给B方，则A方用B方公钥进行加密，B方用B方私钥进行解密。
公开密码密钥系统运作原理
例子：Jack欲传送一些机密信息给Allen，Jack只需向钥匙管理员索取Allen的公开密钥，并利用此公开密钥将信息加密。之后Jack便可将此加密的信息在互联网上传送出去。Allen收到此信息后，便可利用自己的私人密钥将信息解密。同样的， Allen的公开密钥可以让不同人士传送机密信息给Allen。
6、RSA：基于数论的公开密钥密码系统
1978年Rivest、Shamir和Adleman提出RSA公钥加密算法，获得了2002年的图灵奖。
RSA公开秘钥算法的发明人（从左到右Rivest、Shamir、Adleman,摄于1978年）
RSA公开密钥算法描述，密钥生成步骤(例子)
1、随机选择两个不相等的质数p和q
选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
2、计算p和q的乘积n
把61和53相乘，n = 61×53 =3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
3、计算n的欧拉函数φ(n)。根据公式：φ(n) = (p-1)(q-1)
算出φ(3233)等于60×52，即3120。
4、随机选择一整数e，条件是1< e < φ(n)，且e与φ(n) 互质
在1到3120之间，随机选择了17。（实际应用中，常常选择65537）
5、计算e对于φ(n)的模反元素d
模反元素：就是指有一个整数d，可以使得ed被φ(n)除的余数为1
ed ≡ 1 (mod φ(n)) 这个式子等价于 ed - 1 = kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1 已知 e=17, φ(n)=3120，即 17x + 3120y = 1
这个方程可以用”扩展欧几里得算法”求解
上图我们使用扩展欧几里得求得x=-367，所以d=x=-367，但通常我们习惯取正整数，这样方便计算，例如3和11互质，那么3的模反元素就是4，因为(3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素{…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
所以我们取d=d+kφ(n)=-367+1x3120=2753，到这里所有的计算已经全部完毕！
6、将n和e封装成公钥，n和d封装成私钥
在例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
RSA加密解密演示
小明（发送者）要给小红（接收者）发一个字母 m=“A”
小明先要得到小红的公钥 (n,e)即(3233,17)，用公钥加密明文
小红接收密文使用私钥(n,d)即(3233, 2753)对密文解密得到明文
1、小明先将“A”转ascii码为65，所以m=65，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n，使用加密公式算出密文c：
c＝me mod n 则 c=6517 mod 3233=2790
小明就把2790发给小红
2、小红拿到小明发过来的密文c=2790，就用解密公式进行解密得到明文m：
m＝cd mod n 则 m=27902753 mod 3233=65
然后小红对照着ascii码表得出65对应得字母为A。
至此，整个加解密过程就完了，注意m要小于n，如果消息大于n，则可以分段加密！
RSA算法基本原理视频
RSA算法如何计算公钥和私钥视频
信息安全与相关技术规范
