加密技术基础知识

加密技术概述

加密技术指的是数据在传输的过程中会利用数学方法将传输的数据进行组织，以密文的方式进行信息传输，即使在传输过程中被非法分子窃取密文，但是由于没有详细的算法和密钥，因此难以进行解密获得原始的数据， 从而保障了信息的安全性。 加密技术（Cryptography）主要包括明文、密文、算法和密钥 4 项内容。

1. 明文（plaintext）指的是需要传输的信息数据
2. 密文（ciphertext）指的是加密处理之后的明文
3. 算法(algorithm)指的是加密处理中采用的处理组织方法
4. 密钥（encryption key）指的是算法的不同运算参数

加密算法分类

基于密钥的算法，按照密钥的特点分类

对称加密算法(DES) 

在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先须知道加密密钥

对称加密算法从加密模式上可分为两类:序列密码、分组密码。

分组密码

分组密码只能加密固定长度的分组，需要加密的明文长度可能超过分组密码的分组长度，此时就需要对分组密码算法进行迭代，以便将长明文进行加密，迭代的方法就称为分组密码的模式 当需要加密的分组短于分组密码的长度时，需要在明文中添加相应长度的特定数据进行填充。

 ECB（电子密码本模式）

• 将明文分组加密后结果直接成为密文分组 。
• 明文分组与密文分组是一一对应的关系；且每个明文分组各自独立地进行加密和解密。

 CBC（密码分组链接模式）

• 先将明文与前一个密文分组进行异或（XOR）运算，再进行加解密 。
• 初始化向量（IV）：在加密第一个明文分组时，需要事先准备一个长度为一个分组的比特序列代替；每次加密时，都会随机产生一个不同的比特序列作为初始化向量 。
• 无法对单独一个中间的明文分组加密；对初始化向量没有加密 。

 CBC字节反转攻击：攻击者改变前一组密文的一个字节，然后与下一组的密文异或， 我们就可以得到一个不同的明文了，从而就能达到攻击的效果

 CBC模式中密文分组存在缺失的比特时，之后所有的明文分组都护收到影响

CFB（密文反馈模式） 

• 前一个密文分组会被送回到密码算法的输入端
• 密文分组与明文分组之间只有XOR（而CBC中，明文分组与密文分组之间有XOR和密码算法两个步骤）
• CFB模式中有密码算法产生的比特序列成为密钥流（在CFB中密码算法相当于伪随机数生成器）
• 在CFB中分组密码算法在解密时仍执行加密操作（因为密钥流通过加密生成）

 CFB重放攻击

1. 有一天，Alice向Bob发送了一条消息，这两条消息是由4个密文分组组成的。
2. 主动攻击者Mallory将该消息中后3个密文分组保存了下来。
3. 转天，Alice又向Bob发送了内容不同的4个密文分组（我们假设使用了相同的密钥）。
4. Mallory用昨天保存下来的3个密文分组将今天发送的后3个密文分组进行了替换。

流密码 

流密码(也称序列密码)： 使用流密码对某一消息 m执行加密操作时一般是先将m分成连续的符号(一般为比特串)，m=m1m2m3……； 然后使用密钥流 k=k1k2k3……中的第 i 个元素ki 对明文消息的第 i 个元素 mi 执行加密变换，i=1,2,3,……；所有的加密输出连接在一起就构成了对 m执行加密后的密文。

•  一次一密：如果这里的密钥流是完全随机的(random)、与明文相同长度的比特串，对应的密码被称为体制(one-time pad)。Shannon曾证明了“一次一密的密码体制是不可破解的(unbreakable)”。
• 在通常使用的流密码中，加、解密所需要的这种序列是由一个确定性(deterministic)的密钥流生成器(key generator)产生的， 该生        成器的输入是一个容易记住的密钥，称之为密钥流生成器的初始密  钥或种子(seed)密钥。因此，严格来说，密钥流序列都是伪随机序列。

同步序列密码

 同步序列密码的原理：        

        种子密钥k经过由安全信道传送给收、发双方后，由密钥流产生器生成加密和解密所需要的密钥流，而加、解密本身就是简单的模2加法运算。

同步序列密码的特点：

1. 密钥流仅仅依赖于种子密钥和密钥流产生器的结构，而与明文流（或密文流）无关。
2. 如果密钥流完全随机产生且长度至少和明文流一样长，则可实现绝对安全的“一次一密”。但实际上，这很难做到。
3. 无差错传播。因为密钥流独立于密文流，所以一个密文的传输错误不会影响下一个密文的解密。
4. 为了保障接收端能够正确解密，要求收、发双方必须严格同步。

自同步序列密码 

 自同步序列密码的简介：

        与同步序列密码需要收、发双方严格同步不同，自同步序列密码能够依靠自身的能力“自动地”实现收、发双方的同步，因而是一种不需要外部同步的序列密码系统。

自同步序列密码的特点：

1. 密钥流不仅依赖于种子密钥和密钥流产生器的结构，还与密文流（或明文流）有关。初始向量IV在这里相当于初始密文的作用，要求收、发双方必须相同。
2. 自同步。密钥序列的产生取决于种子密钥k和固定个数的先前若干位的密文字符，因此，即使出现删除、插入等非法攻击，只要接受端连续收到一定位数的正确密文，最终都能够自动重建同步解密，因而收、发双方不再需要外部同步。
3. 有差错传播。因为密钥流与密文流有关，所以一个密文的传输错误会影响下面有限个密文的解密

密钥流产生器

 密钥流产生器是决定序列密码安全性能的主要因素，因而线性反馈寄存器（LFSR）是密钥流产生器最基本也是最重要的部件

• 当一个时钟脉冲到来时，第i级寄存器的内容传送给第i－1级寄存器，i ＝ 2，3，…，n。
• 第一级寄存器的内容为反馈移位寄存器的输出。
• 反馈函数f（x1，x2，…，xn－1，xn）的值传送给第n级寄存器。

如果一个n阶反馈移位寄存器的反馈函数形如 f (x1，x2，…，xn)＝cnx1＋cn－1x2＋…＋c1xn， 其中ci∈GF(2)，1≤i≤n，则称其为线性反馈移位寄存器，否则，称其为非线性反馈移位寄存器。

基于LFSR的密钥流产生器 

 如果n级线性反馈移位寄存器产生的输出序列的周期为2^n-1，则称为m序列产生器。m序列不仅周期长，而且伪随机特性好，这正是序列密码的密钥流所需要的特性。

非对称加密算法 

• 非对称加密算法使用一对钥匙 -- 公钥和私钥。
• 加密明文时采用 公钥加密，解密密文时使用私钥才能完成。
• 发信方（加密者）知道收信方的公钥，只有收信方（解密者）才是唯一知道自己私钥的人。 

 非对称加密算法的数学模型 

 情景：Alice要发送信息m给Bob

1. Alice用Bob的公钥PU（b）加密m并发送
2. Bob接受加密后的信息，用只有自己知道的私钥PR（b）进行解密，得到m
3. 由于算法的严谨性，任何不知道Bob的私钥的人，都无法对加密的信息进行解密，也无法从公钥PU（b）推导出私钥PR（b）。

主要用途（局限性）

        由于速度比对称密码算法要慢几个数量级，因此公钥密码算法至今主要用于数据安全，或用于短数据和密钥的加密。

实用的公钥密码体制应该满足以下的要求：

1. 参与方B容易通过计算产生一对密钥 公开密钥PU（b）和私有密钥PR（b）。
2. 发送方A容易通过计算产生密文：c＝ePUb（m）
3. 接收方B容易通过计算解密密文：m＝dPRb（c）＝dPRb(ePUb(m))
4. 他人即使知道公开密钥PUb，要确定私有密钥PRb在计算上是不可行的。
5. 他人即使知道公开密钥PUb和密文c，要想恢复报文m在计算上也是不可行的。
6. 加密和解密函数可以以两个次序中的任何一个来使用: m＝dPRb(ePUb(m)) m=ePUb(dPRb(m))

非对称加密算法本质上是设计一种陷门单向函数。 陷门单向函数是密码学的核心。 陷门单向函数的定义：

•  正向计算容易。即如果知道x，计算y=f(x)相对容易。
•  反向计算极其困难。即如果知道y =f(x), 反向计算x=f^(−1) (y)非常困难，例如：f(x)=x%11 // 模数运算
•  存在陷门δ，已知δ 时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的
• 数学上比如两个大素数乘积容易计算，但是反过来很难分解。 

RSA算法 

         RSA是目前使用最广泛的公钥密码体制之一。它是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

        RSA算法的安全性基于RSA问题的困难性，也就是基于大整数因子分解的困难性上。

        RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥 。 

RSA算法加密过程 

1. Alice随机选两个不相等的质数61和53，并计算两数的积N=61*53=3233，N的长度就是密钥长度。3233的二进制是110010100001，一共12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，总要的场合是2048位。
2. 计算N的欧拉函数。 φ(N)=(p-1)(q-1)=60*52=3120.
3.  Alice 在1到3120上随机选择了一个随机数e=17。
4. 计算e对φ(N)的模反元素d，即时，ed-1=kφ(N)。 即是求解：17x+3120y=1.用扩展欧几里得算法求解。可以算出一组解(x,y)=(2753,-15)，即d=2753。至此完成计算。
5. 其中N=3233,e=17,d=2753。所以公钥就是(N,e)=(3233,17)，私钥(N,d)=(3233,2753)。实际应用中公钥和私钥都是采用ASN.1格式表达的 

加密要用到公钥(N,e)。

1. 假设Bob要向Alice发送加密信息m，他就要用Alice的公钥(N,e)对m进行加密。但m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
2. 所谓加密就是计算下式的c。
3. m^e ≡ c (mod n)假设m=65,Alice的公钥(3233,17),所以等式如下： 65^17≡2790（mod 3233）
4. 所以c等于2790，Bob就把2790发给Alice。 

RSA算法解密 

1. Alice收到Bob发来的2790后，就用自己的私钥(3233,2755)进行解密。
2. c^d ≡ m (mod n)也就是c的d次方除以n的余数就是m。
3. 2790^2753 ≡ 65 (mod 3233)因此得到原文65。 

RSA的可靠性 

• 在RSA私钥和公钥生成的过程中，共出现过p,q,N,φ(N),e,d，其中(N,e组成公钥)，其他的都不是公开的，一旦d泄露，就等于私钥泄露。那么能不能根据N,e推导出d呢？
• ed ≡ 1(mod φ(N))。只有知道e和φ(N)，才能算出d φ(N)=(p-1)(q-1)。只有知道p和q,才能算出φ(N） n=pq,只有将n分解才能算出p和q所以，只有将n质因数分解，才能算出d。也就意味着私钥破译。
• 但是，大整数的质因数分解是非常困难的。 

非对称加密算法的破解 

至少三种攻击方式进行破解

• 强力攻击(对密钥)

        密钥穷举法搜索可能的私钥。 解决方法：密钥长度要足够长（但同时也增加了解密加密的速度） 

• 公开密钥算法本身可能被攻破

        从数学上对陷门单向函数寻求突破，从公钥PU推导出私钥PR。 目前没有严格证明该方法无效 。

• 可能报文攻击(对报文本身的强力攻击)

        因为知道公钥PU，攻击者完全可以穷举所有可能的明文，用公钥来逐一加密这些明文，必有一个加密加过与截获的密文相同。 解决方法：明文也要足够长