密码学基础

2019/11/10 Encryption

这篇文章主要总结了常见的密码学协议。

简要

密码学主要有三个分支,对称密码、非对称密码、密码协议。对称密码学主要有序列密码和分组密码。序列密码是单独加密每个位,而分组密码是每次使用相同的密钥加密整个块;序列密码的安全性取决于密钥序列,常见的模2加法是很好的序列加密。强加密算法都是基于两个本原操作,混淆和扩散。混淆是是密钥与密文之间尽可能模糊,而扩散是隐藏文本的统计属性。

基本数学概念

  1. 如果一个群的元素是有限的,那么称为有限群,群的阶就是群的元素的数量。否则称为无限群。

  2. 如果一个群满足交换律,则称为交换群。

  3. 如果一个群的所有元素都能由某个元素的幂生成,则称为循环群。其中这个元素叫做生成元,并且循环群总是交换群。

  4. 每个素数域的乘法群都是循环群。

有限循环群

假设是一个有限群,那么有

  1. , 有

  2. 生成的群的秩可以整除

假设是一个有限循环群,那么有

  1. 中的生成元个数是

  2. 如果是素数,那么所有满足的元素都是生成元。

  3. 循环群的每个元素都是其子群的生成元,并且子群也是一个循环群。

  1. 域中所有元素组成一个加法群,单位元为0。

  2. 域中除了0元素以外所有元素组成了乘法群,单位元为1。

  3. 域中分配率是成立的。

模素数p有限域

有限域的阶是一个素数的幂,一般记为是定义在整数集合{0,1…,p-1}上的域,满足几个性质:(1)有模加法与模乘法运算,并且在这个集合上封闭。(2)两个运算满足交换律与结合律。(3)有单位元。(4)有逆元。

是最小的有限域。的加法就是模2加法,对应硬件上的异或XOR操作;的乘法对应硬件上的逻辑与AND操作。AES使用的有限域是,这是一个扩展域,元素用多项式表示。

单向函数

函数是一个单向函数,仅当满足

  1. 在计算上是容易的。

  2. 在计算上是困难的。

大部分的公钥密码方案都使用了两种主流的单向函数,第一种是基于大整数分解难题,第二种是离散对数难题。

数论

最大公约数与最小公倍数

int gcd(int a, int b){
  return b ? gcd(b, a%b) : a;
}

int lcm(int a, int b){
  return a * b / gcd(a, b);
}

拓展欧几里得定理

已知整数,存在一组整数使得,该定理可以用于求解有限域的乘法逆元。

欧拉函数

内与互素的整数的个数表示为。例如中,欧拉函数的值为2,即。如果使用这种方式计算欧拉函数,效率太低。

假设可以因式分解为,那么有

因此想要快速计算出欧拉函数值,就需要知道的因式分解。这是RSA方案的核心,因为大整数分解的难题,所以无法求出欧拉函数值,因此也就无法解密。

费马小定理

假设是一个整数,是一个素数,那么有 mod

欧拉定理

假设假设是两个整数,并且,那么有 mod 。费马小定理是欧拉定理的一个特例。

Hash Functions 哈希函数

Hash函数是将任意长度的输入变换为固定长度的输出的不可逆的单向密码体制,在数字签名和消息完整性检测等方面有着广泛的应用。Hash函数同时是一种具有压缩特性的单向函数,其通常称为数字指纹,消息摘要或散列值。

Hash函数满足三个安全性质:

  1. 单向性:对任意给定的散列值,找到满足的在计算上是不可行的。
  2. 抗弱碰撞性:对任意给定的消息,找到并且的消息在计算上是不可行的。
  3. 抗强碰撞性:找到任何满足的偶对在计算上是不可行的。

Message Authentication Codes 消息认证码

The aim of a message authentication code is to prevent an adversary from modifying a messagee sent by one party to another, without the parties detecting that a modification has been made.

消息认证码的目标是确保消息完整性与消息来源。消息完整性通过Hash函数来实现,消息来源可以通过对称密码来实现。

常见的HMAC是密钥相关的哈希运算消息认证码(Hash-based Message Authentication Code)的缩写,由H.Krawezyk,M.Bellare,R.Canetti于1996年提出的一种基于Hash函数和密钥进行消息认证的方法,并于1997年作为RFC2104被公布,并在IPSec和其他网络协议(如SSL)中得以广泛应用,现在已经成为事实上的Internet安全标准。

Advanced Encryption Standard AES加密算法

AES为分组密码,分组密码也就是把明文分成长度相等的块,每次加密一组数据,直到加密完整个明文。在AES标准规范中,分组长度只能是128位,也就是说每个分组为16个字节。密钥的长度可以使用128位、192位或256位。

AES每轮的操作主要有4个,分别是字节替换(SubBytes)、行移位(ShiftRows)、列混淆(MixColumns)、轮密钥加(AddRoundKey)。

常见的AES加密模式有:

  1. AES-ECB(Electronic codebook): ECB是最简单的块密码加密模式,加密前根据加密块大小(如AES为128位)分成若干块,之后将每块使用相同的密钥单独加密,解密同理。ECB模式由于每块数据的加密是独立的,因此加密和解密都可以并行计算,ECB模式最大的缺点是相同的明文块会被加密成相同的密文块,这种方法在某些环境下不能提供严格的数据保密性。

  2. AES-CBC(Cipher-block chaining): CBC模式对于每个待加密的密码块在加密前会先与前一个密码块的密文异或然后再用加密器加密,第一个明文块与一个叫初始化向量的数据块异或。CBC模式相比ECB有更高的保密性,但由于对每个数据块的加密依赖与前一个数据块的加密所以加密无法并行。

  3. AES-CFB(Cipher feedback): CFB模式类似于CBC,可以将块密码变为自同步的流密码;工作过程亦非常相似,CFB的解密过程几乎就是颠倒的CBC的加密过程。

  4. AES-OFB(Output feedback): OFB是先用块加密器生成密钥流(Keystream),然后再将密钥流与明文流异或得到密文流,解密是先用块加密器生成密钥流,再将密钥流与密文流异或得到明文,由于异或操作的对称性所以加密和解密的流程是完全一样的。CFB与OFB具有相似性。

  5. AES-CTR(Counter mode): 与OFB相似,CTR将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流,其中,计数器可以是任意保证长时间不产生重复输出的函数,但使用一个普通的计数器是最简单和最常见的做法。CTR模式的特征类似于OFB,但它允许在解密时进行随机存取。由于加密和解密过程均可以进行并行处理,CTR适合运用于多处理器的硬件上。

RSA

RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA属于非对称密码算法(公钥密码体系),其安全性规约到大整数分解难题,广泛用于加密和数字签名。RSA的算法过程如下:

  1. 找到两个大素数

  2. 计算

  3. 找到小于,满足

  4. 计算 mod

  5. 加密过程: mod

  6. 解密过程: mod

公钥算法家族

  1. 大整数分解方案,例如RSA。

  2. 离散对数方案,例如DH密钥交换、Elgamal加密、数字签名算法DSA。

  3. 椭圆曲线方案,例如ECDH椭圆曲线DH交换、椭圆曲线数字签名算法ECDSA。

RSA算法

RSA的密钥生成:

  1. 选择两个大素数

  2. 计算出

  3. 计算出

  4. 随机选择一个小于的公开指数,满足

  5. 私钥满足 mod

RSA的加解密过程:

  1. mod

  2. mod

对RSA的攻击

  1. 整数分解。目前对于768bit的整数已经可以比较快速的分解成两个素因子的乘积。

  2. 公约数。如果两次加密使用的n值具有相同的素因子,那么可以使用欧几里得算法求解出其中一个素因子,然后就可以对这两个n进行因式分解。

  3. 开源项目yafu。当p与q相近或者是相差过大的时候,有现成的自动化工具可以快速分解n。

  4. 低指数加密。当e值比较小,例如e=3时,明文的三次方小于模数,那么就可以对其开三次方求出明文。

  5. 低指数解密。https://github.com/pablocelayes/rsa-wiener-attack。

  6. 共模攻击。使用相同的n对相同的明文m进行加密,那么可以不用解n的因式分解,也能求出明文。

Diffie-Hellman密钥交换

DH密钥交换的过程如下,A、B双方进行协商。

  1. 选择一个大素数以及一个小于的整数并公开。

  2. A选择一个随机数,计算 mod 并发送给B。

  3. B选择一个随机数,计算 mod 并发送给A。

  4. 双方得到相同的密钥 mod

Diffie-Hellman协议是广泛使用的密钥交换方法,它是基于循环群的。使用基本的DHKE的协议在主动攻击面前是不安全的(中间人攻击);如果仅考虑被动攻击,DH的安全性规约到DHP难题,与离散对数问题类似。

椭圆曲线密码体制

在多数情况下,ECC在性能上(更少的计算量)和带宽(更短的签名和密钥)上比RSA和离散对数(DL)方案更具有优势。

椭圆曲线的定义

上的椭圆曲线指满足 mod 的所有对的集合,以及一个无穷大的虚数点。其中,并且满足条件 mod

F&Q

  1. 对称密码与非对称密码的对比? 对称密码的优点:算法运算速度较快;密钥相对较短;密文明文长度相同;缺点是密钥分发需要安全的通道;密钥量大,密钥难于管理;难以解决不可否认问题;非对称密码的优点:密钥分发管理比较简单;解决不可否认问题;缺点是算法复杂,处理速度慢。

  2. 古典密码学中的替换与置换是指什么? 置换是指根据一定的规则重新排列明文,打破明文的结构特性,特点是保持明文的所有字符不变,打乱了明文字符的位置和次序。而替换是指将明文的一个字母由其他字母、数字或者符号替代的一种方法。

  3. 消息认证码与对称密码算法的区别? 对称加密函数的逆函数是解密函数,而消息验证码函数不存在逆函数。也就是说消息认真码具有单向性,而对称密码算法具有双向性。

  4. 不同安全等级所要求的公钥算法的位长度?

参考资料

密码学基础: AES加密算法

Bristol大学密码学博士生的五十二个知识点

SM4算法、AES算法、DES算法三种分组密码的基础分析

RSA

Search

    Table of Contents