密码学复习

密码体系相关概念

• CIA：安全的三个关键目标
  保密性：信息没有出现非授权泄露
  完整性：信息没有出现非授权修改或破坏
  可用性：信息能够及时可靠地访问和使用
• OSI安全架构：
  安全攻击： 任何危及信息系统安全的行为
  安全机制：检测、阻止、恢复的过程
  安全服务：加强系统安全性的服务
• 安全攻击分为被动攻击和主动攻击，被动攻击是指通过监测或窃听获取加密信息的手段，而主动攻击有消息篡改，重放攻击，伪装，拒绝服务
• 密码学分为密码分析学和密码编码学
• 攻击类型：唯密文攻击，已知密文攻击，选择明文攻击（假设有一台加密机，放入特定的明文会产生对应的密文），选择密文攻击，攻击难度依次递增
• 分类标准：stream与block，对称密钥与非对称密钥，替换与置换等
  
• 约束关系其实只要满足（1）即可，即从明文到密文可以不唯一，但是不管是哪种密文一定要能还原成唯一的明文

传统密码

替换技术

• 凯撒密码的形式化五元组
  

单表替换密码

通过其中一个字母的对应关系就可以确定一张唯一的明密文对应表，但是密钥空间太小，无法保证密码的安全性，于是产生了单表替换密码，即一张没有任何规律的表，但是满足明密文之间一一对应的关系，从而使密钥空间提升到26！，但是因为人类自然语言的使用频率不一样，所以可以通过词频分析破解

• 转轮机：转$26\ast 26\ast 26$次(第一个转26次第二个转1次)回到原点，字母的顺序是固定不变的，每转一次字母对应新的内部物理连接，从而产生不一样的输出

双表替换密码playfair密码

5*5的矩阵，$i/j$同位，遵循三个规则进行加密（简单理解就是有对角线看对角线，没对角线整体向右下偏移），明文分组时用X填充，同样存在词频分析的问题，同时密钥不能过短，否则某一段相同的明文恰好遇上密钥，产生相同的密文，密钥就会被推断出来，这个问题在替换密码中都存在

多表替换密码维基密亚密码

每一个密钥字母都对应了一张表，因此在破解密文时，每一个字母都要猜测26种可能，并不存在固定的明密文间一一对应的关系

置换技术

栅栏密码

• 如图，两栏的栅栏密码按下图写出，再按行读出重新排列，也可以理解为隔一位选一个字母
  

列移位密码

按照所给密钥重新排列列的顺序

对称密码（block cipher）

DES

• 密钥中每八位有一位校验位，所以密钥的有效长度只有56位，密钥的产生过程：

  1. 从64位中选出56位

  2. 置换选择1

  3. 循环左移（每一轮的密钥左移的位数不同）

  4. 置换选择2（从56位密钥选出48位进行异或）
     

• DES在进入轮前做ip置换，出轮做ip逆置换，每一轮做的事情：采取feistel结构，进行扩展，异或，s盒选择，置换操作
  
• 这里介绍两种分析，差分密码分析和线性密码分析，尽管对于DES都是无效的，差分密码分析是指每次改变明文的一点点（可能是1bit），然后去观察密文，进而发现明密文之间的关系，线性密码分析是指设出明文和密文之间的方程，找到足够多的方程进而求解

工作模式

AES

• AES的基本结构：128bit明文，128/192/256bit密钥，从10轮开始，每增加64bit密钥轮数就增加两轮
• 加密流程：明文进来先进行轮密钥加，接着进行字节替换，行移位，列混合，轮密钥加（此时的密钥已经经过特殊的扩展规则生成了40组用来应对10轮加密）
• 解密流程：与加密相似，不过区别在于解密时所做的都是加密操作的逆操作
  
• 密钥的扩展机制：对W[0,4]数组扩充40个新列，构成总共44列的扩展密钥数组。新列以如下的递归方式产生：

1. 如果i不是4的倍数，那么第i列由如下等式确定：
   $W[i]=W[i-4]⨁W[i-1]$
2. 如果i是4的倍数，那么第i列由如下等式确定：
   $W[i]=W[i-4]⨁T(W[i-1])$
   其中，T是一个有点复杂的函数。
   函数T由3部分组成：字循环、字节代换和轮常量异或，这3部分的作用分别如下。
   a. 字循环：将1个字中的4个字节循环左移1个字节。即将输入字[b0, b1, b2, b3]变换成[b1,b2,b3,b0]。
   b. 字节代换：对字循环的结果使用S盒进行字节代换。
   c. 轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。

近现代的一些对称密钥

Trible-DES

• 出于历史遗留数据的问题，采用k1加密，k2解密，k1再加密的模型会更好
• 两次加密或多次加密得到的明密文对应关系不可能由一次加密得到

IDEA

blowfish

• 特点：在算法运行时，根据输入密钥的不同，每一轮用输出结果更新s盒和p盒的两个参数，所以算法在跑起来之前需要先跑五百多次来更新参数，这就使加密的参数与密钥高度相关，每个人的blowfish都是不一样的，从而极大地提高了算法地安全性，同时，blowfish采取模加运算和异或运算，因此效率特别高

对称密码（stream cipher）

RC4

• 面向字节流处理数据，S数组有256个数据，因而每个数据出现的概率都是相等的
• S数组初始化为0-255
• T数组初始化为密钥的重复填入
• 第二步进行密钥的初始化$j=j+S[i]+T[i]$每次选一个数组值出来，和当前值做一个交换，做一个数组下标和数组值的共同运算，造成逻辑上的混乱，依然实现了一个字节0-255的完美覆盖，但是换了一种排列方式
• 第三步进行加密操作

应用层部署（端到端加密）和链路层部署

• 端到端加密：就是在应用层就将数据加密，传输数据永远处于密文状态，而ip地址，mac地址等信息对于攻击者来说都是可见的，也就是说攻击者可以看到信息发送的结点
• 链路层加密：信息一直打包到链路层才进行加密操作，对于攻击者监听到的任何信息都是以密文的形式存在，每一个结点具有解密还原，加密发送的能力。

流量分析

• 除了流量的分析，流量本身的特征，大小本身也是一种信息
• 采用流量填充的技术解决

公钥密码

RSA

DH密码

• 诞生之初解决了如何安全分发密钥的问题，基于离散对数问题逆向求解的困难性
• 如果p 是一个素数，g 和x 是整数，计算 $y=g^{x}modp$ 非常快。但是相反的过程：先知道 p, g 和y，要求某个x(离散对数)，满足等式$y=g^{x}modp$，通常十分困难。此相反求离散对数的过程称为“离散对数问题”
• A,B分别将公钥给到对方，再用自己的私钥和对方的公钥，就可以创建一个安全的传输通道

ECC

• ECC是定义在阿贝尔群上的，即满足交换律的群
• ECC上的DH问题，a计算$k_a\ast p$发给b，b计算$k_b\ast p$发给a，二者再利用已有的公私钥计算出公共通信密钥$k_a\ast k_b\ast p$
• 加解密过程：A生成一个随机树K，每一次会话都可以改变，用B的公钥和K加密信息，并将KG和密文发给B，B用自己的私钥和KG即可解密
  

MAC&HASH

• 消息在传输过程中关注的一些特点：能不能验证消息的来源，消息可不可以被伪造

MAC消息认证码

• 作用，验证消息的完整性，但解决不了争议
• 特点：采用一个密钥，生成定长的数据，通常使用DES-CBC模式的最后一块加密数据（如果数据不够64位就用0填充），在第三个模型中，要验证明文的完整性，就必须计算与之对应的密文的MAC码，因此必须保证密文的唯一性

HASH哈希函数

• 类似于MAC码，输入消息产生定长的摘要，第三个模型更普遍用于数字签名，既能验证消息的完整性，又能验证消息来源

生日攻击

• 实际上要达到0.5的概率去发生碰撞，所需要的数据量远小于数据的一半，甚至能达到开二次根号的级别