深入浅出密码学-课程笔记

课程教师：马海英

2110310044 赵涛涛

[TOC]

密码学基本定义

密码学本身可以分为三个主要分支：

对称算法：通信双方共享一个密钥，并使用相同的加密方法和解密方法。

非对称算法：与对称密码学不同的是，用户拥有一个公私钥对。可以用于数字签名或者密钥交换。

密码协议：密码协议是针对密码学算法的应用，例如传输层安全方案（TLS）。

替换密码是一种简单的对称加密方法。可以使用蛮力攻击或者密钥穷尽搜索；可以使用字母频率法分析攻击。

移位密码是替换密码的一种特例。可以使用蛮力攻击或者密钥穷尽搜索；可以使用字母频率法分析攻击。

仿射密码拥有两个密钥，一个密钥（a）用于乘以明文，另一个密钥相当于移位密钥。

Kerckhoffs 原理

即使除密钥外的整个系统的一切都是公开的, 这个密码体制也必须是安全的。尤其是即使攻击者知道系统的加密算法和解密算法, 此系统也必须是安全的。

群、环、域

群是元素集合及集合内任意两个元素的联合操作的集合。群操作是封闭的、可结合的。存在单位元、每个元素都存在逆元。群上有一种操作，可以是加法操作或者乘法操作。若操作满足交换律也叫交换群。
环在交换群的基础上，添加了一种二元运算。环上有两种操作，环内元素存在单位元，但不一定存在乘法逆元；（乘法逆元的判断方法是欧几里得算法）
域在交换环的基础上，还增加了二元运算除法，要求元素(除零以外)可以作除法运算，即每个非零的元素都要有乘法逆元。域上有两种操作，域内元素一定存在乘法逆元；

域是一种可以进行加减乘除(除0以外)的代数结构，是数域与四则运算的推广。整数集合，不存在乘法逆元(1/3不是整数)，所以整数集合不是域，是环。有理数、实数、复数可以形成域，分别叫有理数域、实数域、复数域。其中，集合元素个数为有限个的域被称为有限域（伽罗瓦域）。

域包含的元素个数称为域的阶或者基

只有当\(m=p^{n}\)，其中\(n\)为正整数，\(p\)为素数，阶为\(m\)的有限域才存在.

正如欧几里得算法所得，当且仅当某元素\(a\)与域的阶\(p\)互素，\(gca(a, p) =1, a\)的逆元存在，因此在整数环GF（p）中，若p为素数，GF（p）内的所有非零元素都存在乘法逆元，则GF（p）也称为素数域或伽罗瓦域。

\(GF(2^{m})\)内的加法与乘法。加法使用按位异或。乘法满足分配率。模运算可以使用长除法。

序列密码：单独加密每个位。

分组密码：每次使用相同的密钥加密整个明文组。

一次一密：是无条件安全（在无限计算资源的情况下也不能被破解）的。满足（1）通过真随机数生成器生成密钥（2）每个密钥仅使用一次（3）仅合法通信方知晓密钥。

计算安全：如果为破解一个密码体制，最好的已知算法至少需要t个操作。则称为计算安全。

线性反馈移位寄存器（LFSR）

一个度为m的LFSR的最大生成序列为\(2^{m}-1\).

LFSR可以分为三种：

产生最大长度序列的 LFSR: 它是基于本原多项式 。
生成的序列长度不是最长, 但其序列长度却与寄存器的初始值无关的 LFSR: 这些 LFSR 基于非本原的不可约多项式。注意: 所有的本原多项式都是不可约多项式。
生成的序列长度不是最长但长度与寄存器的初始值相关的 LFSR: 这些 LFSR 基于不可约多项式。

对称加密算法

DES是一种使用56位密钥对64位长度的明文组进行加密的算法。

强加密算法都基于扩散和混淆：

混淆，模糊密钥与密文之间关系的操作。实现混淆的常用元素为替换。
扩散，是一个隐藏明文统计属性，将明文符号的影响扩散到多个密文符号的加密操作。最简单的实现方法是位置换，用于DES。

AES的密钥长度为128/192/256，分组大小为128位.

AES的替换算法为3DES.

AES密码与分组密码Rijndael基本一致。只有分组为128位的Rijndael算法才称为AES算法。

AES分为密钥加法层、s-盒、扩散层（行移位，列混淆）。

公钥加密算法

对称加密算法优缺点：非常安全快速，被广泛使用，但也存在一些问题。

（1）密钥分配的链路不安全。

（2）密钥管理难，\(n\)个用户的网络中需要\(\frac{n(n-1)}{2}\)个密钥。且每个用户都需要存储\(n-1\)个密钥。（3）没有提供消息的不可否认性。

公钥加密算法优缺点为每个用户生成一个公私钥对，公钥用于加密，私钥用于解密，可以保证消息的安全性。对于一个n个用户的网络，仅需要n对公私钥对即可。但公钥加密算法的密钥非常长，可加密的消息长度有限，加密非常缓慢，不适用于直接对消息进行加密。

结合使用：可以使用公钥加密算法建立安全信道，交换对称密钥，这样可以在保证密钥安全交换的基础上降低加解密开销。

公钥加密方案都来自于一个公共原理，即单向函数：

该函数在\(y=f(x)\)上的计算是容易的，
且在\(x=f^{-1}(y)\)上的计算是不可行的。

具有实用性的公钥算法家族

整数分解方案 有效公钥方案基于这样一个事实: 因式分解大整数是非常困难的。这类算法最突出的代表就是 RSA。 离散对数方案 有不少算法都基于有限域内的离散对数问题, 最典型的例子包括 Diffie-Hellman 密钥交换、Elgamal 加密或数字签名算法(DSA)。 椭圆曲线(EC)方案 离散对数算法的一个推广就是椭圆曲线公钥方案。典型例子包括椭圆曲线 Diffie-Hellman 密钥交换(ECDH)和椭圆曲线数字签名算法 (ECDSA)。