格理论与密码学

内容简介

    《格理论与密码学》主要介绍格理论中的基础理论、关键技术及其在密码学中的典型应用。主要包括三方面内容:格理论与密码学的基础知识,包括数论基础、抽象代数基础、向量空间、对称密码体制、公钥密码体制、哈希函数等;格理论的基础理论和关键技术,包括格的基本定义、格中的计算性难题、向量问题、向量问题、二维格中的高斯格基约减算法、LLL格基约减算法及其衍生和变形、LLL与apprCVP问题以及格基约减算法的MATLAB实现;格理论在密码学中的典型应用,包括基于格的密码系统分析方法以及基于格理论的哈希函数。
    《格理论与密码学》可供从事信息安全、密码学、数学、计算机、通信等专业的科技人员参考,也可供高等院校相关专业的师生参考。

目录

前言
第1章 数学基础
1.1 数论基础
1.1.1 整除性和公因子
1.1.2 模运算
1.1.3 中国剩余定理
1.1.4 利用中国剩余定理求解二次同余式
1.1.5 分解性和有限域
1.1.6 有限域中的乘方和原根
1.2 抽象代数基础
1.2.1 群
1.2.2 环
1.2.3 可约性和商环
1.2.4 多项式环与欧几里得算法
1.2.5 多项式环的商和素数阶有限域
1.2.6 卷积多项式环
1.3 向量空间
1.3.1 基本概念
1.3.2 范数与正交基
习题
第2章 密码学
2.1 对称密码体制
2.1.1 对称密码体制原理
2.1.2 DES算法
2.1.3 AES算法
2.2 公钥密码体制
2.2.1 公钥密码体制的产生
2.2.2 公钥密码体制原理
2.2.3 Diffie-Hellman密钥交换协议
2.2.4 RSA密码系统
2.2.5 ElGamal密码系统
2.2.6 椭圆曲线密码系统
2.3 哈希函数
习题
第3章 格的定义与相关性质
3.1 格的基本定义
3.2 格中的计算性难题
3.3 向量问题
3.3.1 Hermite定理和Minkowski定理
3.3.2 高斯启发式
3.4 向量问题
习题
第4章 格基约减算法与实现
4.1 二维格中的高斯格基约减算法
4.2 LLL格基约减算法及其衍生和变形
4.2.1 LLL格基约减算法
4.2.2 LLL算法的衍生和变形
4.3 LLL与apprCVP问题
4.4 格基约减算法的MATLAB实现
4.4.1 基本函数
4.4.2 计算Hadamard比率函数
4.4.3 生成优质基函数
4.4.4 计算矩阵的行范数函数
4.4.5 向量正交化函数
4.4.6 LLL算法的实现
习题
第5章 格理论在密码学中的应用
5.1 基于格难题的密码系统
5.1.1 概述
5.1.2 GGH公钥密码系统
5.1.3 基于格的GGH密码学分析
5.2 同余密码系统及分析
5.2.1 同余密码系统
5.2.2 基于格的同余密码学分析
5.3 背包密码系统及分析
5.3.1 背包问题
5.3.2 超递增序列背包
5.3.3 MH背包公钥密码系统
5.3.4 基于格的背包密码学分析
5.4 NTRU密码系统及分析
5.4.1 NTRU密码系统
5.4.2 NTRU的安全性
5.4.3 基于格的NTRU密码学分析
习题
第6章 基于格理论的哈希函数及应用
6.1 预备知识
6.1.1 抗碰撞哈希函数
6.1.2 Merkle树
6.1.3 认证数据结构概述
6.2 基于格理论的哈希函数
6.2.1 LBH的数学基础
6.2.2 LBH的基本结构
6.2.3 LBH的安全性
6.2.4 LBH的代价分析
6.3 基于LBH的更新优化认证数据结构
6.3.1 LBH-UOADS基本思想
6.3.2 LBH-UOADS构建方案
6.3.3 LBH-UOADS的关键算法
6.3.4 LBH-UOADS的正确性和安全性证明
6.3.5 LBH-UOADS的代价分析
6.4 基于LBH-UOADS的数据查询认证方案
6.4.1 数据查询认证框架
6.4.2 查询认证过程
6.4.3 安全性分析
6.4.4 代价分析和比较
习题
参考文献

摘要与插图

第1 章　数学基础
本章将介绍本书用到的一些基本的数学概念和符号。1.1 节和1.2 节分别简
要介绍数论和抽象代数的基础知识，对这些内容不熟悉的读者可以参考更详细的
参考书籍；1.3 节主要介绍定义在?m 上的向量空间的概念和性质。充分理解本
章内容对于其余各章的学习是必要的。
1.1 　数论基础
数论和代数学是现代密码学的基础。本节将介绍数论中的一些重要定理和
结论。数论是研究整数性质的一个数学分支，其研究对象是整数（自然数） 。整数
在计算机科学、密码学与信息安全、数字信号处理等领域起到了重要的作用。本
节将介绍整除性和整数的分解，带余除法以及求解公因子的相关算法；并介
绍模运算的运算法则与性质，以及求解线性同余方程组的方法；此外还介绍了素
数、有限域、模除法运算的概念；介绍了有限域中的乘方和原根的性质。
1.1.1 整除性和公因子
若a ，b 是整数，则可以分别计算a + b ，a - b ，a ? b ，且所得结果均是整数。这
种性质称为对元素运算的封闭性。
但是对除法运算并不能总是满足这种运算封闭性。例如，不能用2 去除3 ，因
为3/2 并不是整数，由此引出了整除性的基本概念。
定义1.1 　设a ，b 是整数，b ≠ 0 。若存在整数c ，满足a ＝ bc ，则称b 整除a 或a
被b 整除，记为b｜ a 。
命题1.1 　设a ，b ，c ∈ ￠ ，则有
（1） 若a｜ b ，b｜ c ，则a｜ c ；
（2） 若a｜ b ，b｜ a ，则a ＝ ± b ；
（3） 若a｜ b ，a｜ c ，则a｜（ b + c）且a｜（ b - c） 。
定义1.2 　a 和b 的公因子是能够同时整除二者的正整数。顾名思义，公
因子就是满足d｜ a ，d｜ b 的的正整数d ，用gcd（ a ，b）来表示。在不存在歧义的
情况下也可以表示成（ a ，b） 。
公因子的概念虽然简单，但有很多应用。下面介绍几种计算公因子
的方法。
定义1.3（带余除法） 　设a ，b 是正整数，则存在的q 和r 满足
a ＝ b ? q + r ，　0 ≤ r ＜ b
若求a 和b 的公因子，先对a 作带余除法，即
a ＝ b ? q + r ，　0 ≤ r ＜ b
若d 是a 和b 的公因子，则d 也能够整除r ；若e 是b 和r 的公因子，e 也能够
整除a 。换言之，有
gcd（ a ，b） ＝ gcd（ b ，r）
重复此过程，对b 作带余除法，即
b ＝ r ? q′ + r′ ，　0 ≤ r′ ＜ r
则有
gcd（ b ，r） ＝ gcd（ r ，r′）
此过程将使余数越来越小，为0 ，此时有
gcd（ s ，0） ＝ s ＝ gcd（ a ，b）
这种方法常称为辗转相除法，或欧几里得算法。
定理1.1（欧几里得算法） 　设a ，b 是正整数（ a ≥ b） ，下述算法能够在有限步
内计算出gcd（ a ，b） ：
（1） 设r0 ＝ a ，r1 ＝ b ；
（2） 令i ＝ 1 ；
（3） 对ri - 1 作带余除法，ri - 1 ＝ ri ? qi + ri + 1 ，0 ≤ ri + 1 ＜ ri ；
（4） 若ri + 1 ＝ 0 ，则ri ＝ gcd（ a ，b） ，算法结束；
（5） 若ri + 1 ＞ 0 ，令i ＝ i + 1 ，转到第（3）步。
其中，第（3）步执行2log2 b + 1 次。
证明　定理1.1 所进行的带余除法过程可以用下列步骤来表示：
a ＝ b ? q1 + r2 ，　0 ≤ r2 ＜ b
b ＝ r2 ? q2 + r3 ，　0 ≤ r3 ＜ r2
r2 ＝ r3 ? q3 + r4 ，　0 ≤ r4 ＜ r3
r3 ＝ r4 ? q4 + r5 ，　0 ≤ r5 ＜ r4
　　　　? 　　　　
rt - 2 ＝ rt - 1 ? qt - 1 + rt ，　0 ≤ rt ＜ rt - 1
rt - 1 ＝ rt ? qt
rt ＝ gcd（ a ，b）
ri 的值严格递减，当ri + 1 ＝ 0 时算法结束。这就证明了算法能够在有限步内结束。
此外，在