格理论与密码学pdf/txt下载_在线阅读全文

内容简介

《格理论与密码学》主要介绍格理论中的基础理论、关键技术及其在密码学中的典型应用。主要包括三方面内容：格理论与密码学的基础知识，包括数论基础、抽象代数基础、向量空间、对称密码体制、公钥密码体制、哈希函数等；格理论的基础理论和关键技术，包括格的基本定义、格中的计算性难题、最短向量问题、最近向量问题、二维格中的高斯格基约减算法、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章 数学基础 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.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 时算法结束。这就证明了算法能够在有限步内结束。
 此外，在迭代过程中有
 ri - 1 ＝ ri ? qi + ri + 1 ，　0 ≤ ri + 1 ＜ ri
 这表明
 gcd（ ri - 1 ，ri ） ＝ gcd（ ri ，ri + 1 ） ，　i ＝ 1 ，2 ，3 ，…
 当rt + 1 ＝ 0 时，有rt - 1 ＝ rt ? qt ，故
 gcd（ rt - 1 ，rt ） ＝ gcd（ rt ? qt ，rt ） ＝ rt
 再由迭代等式可知
 gcd（ a ，b） ＝ rt
 也就是说最后一个不为零的余数就是a 和b 的最大公因子。
 证毕
 下面分析算法的效率。因为ri 的值严格递减，且r1 ＝ b ，故算法最多执行b 步
 就能够终止。然而，这样求出的只是一个上界。注意，随着步骤（3）的每两次迭
 代，ri 的值至少能够减半：ri + 2 ＜ 1
 2 ri ，i ＝ 0 ，1 ，2 ，… 。下面分两种情况证明此不
 等式。
 情况1 ：ri + 1 ≤ 1
 2 ri 。
 由于ri 严格递减，故
 ri + 2 ＜ ri + 1 ≤ 1
 2 ri
 情况2 ：ri + 1 ＞ 1
 2 ri 。
 考虑ri + 1 除ri ，即
 ri ＝ ri + 1 ? 1 + ri + 2
 则有
 ri + 2 ＝ ri - ri + 1 ＜ ri - 1
 2 ri ＝ 1
 2 ri
 综合两种情况，能够证明
 ri + 2 ＜ 1
 2 ri ，　i ＝ 0 ，1 ，2 ，…
 反复利用这个等式将得
 r2 k + 1 ＜ 1
 2 r2 k - 1 ＜ 1
 4 r2 k - 3 ＜ 1
 8 r2 k - 5 ＜ 1
 16 r2 k - 7 ＜ … ＜ 1
 2k r1 ＝ 1
 2k b
 因此，若有2k ≥ b ，则
 r2 k + 1 ＜ 1 痴r2 k + 1 ＝ 0
 算法结束。
 在定理证明过程中，rt + 1 ＝ 0 ，则t + 1 ≤ 2 k + 1 痴t ≤ 2 k ，且在上述算法中共执行
 了t 次除法，故欧几里得算法至多在2 k 次迭代后结束。选取满足2k ≥ b ＞ 2k - 1 的
 最小的k ，则迭代次数≤ 2 k ＝ 2（ k - 1） + 2 ＜ 2log2 b + 2 。
 上述定理证明了欧几里得算法至多执行2log2 b + 1 次迭代。然而，这个估计
 值可以被改进。已有文献证明，迭代次数不超过1.45log2 b + 1.68 ，且对于随机选
 取的a 和b ，平均迭代次数约为0.85log2 b + 0.14 。
 定理1.2（扩展的欧几里得算法） 　设a ，b 是正整数，存在u ，v 满足
 au + bv ＝ gcd（ a ，b）
 证明　从欧几里得算法得知
 a ＝ b ? q1 + r2
 将其代入
 b ＝ r2 ? q2 + r3
 可得
 b ＝ （ a - b ? q1 ） ? q2 + r3
 故
 r3 ＝ - a ? q2 + b ? （1 + q1 q2 ）
 再将结果代入
 r2 ＝ r3 ? q3 + r4
 最终得
 a - b ? q1 ＝ ［ - a ? q2 + b ? （1 + q1 q2 ）］ q3 + r4
 整理可得
 r4 ＝ a ? （1 + q2 q3 ） - b ? （ q1 + q3 + q1 q2 q3 ）
 即为r4 ＝ a ? u + b ? v 的形式。
 重复此过程将得
 rt ＝ a ? u + b ? v ＝ gcd（ a ，b）
 证毕
 定义1.4 　设a ，b 是整数，当gcd（ a ，b） ＝ 1 时，称a 和b 互素。
 一般地，可以在等式A u + B v ＝ gcd（ A ，B）两端同除gcd（ A ，B） ，得
 A
 gcd（ A ，B） u + B
 gcd （ A ，B） v ＝ 1
 则A
 gcd（ A ，B）和B
 gcd（ A ，B）互素。
 1.1.2 　模运算
 本小节介绍模运算的概念和相关性质。
 定义1.5 　设m 为自然数，a 和b 是任意整数，如存在关系a ＝ b + km ，其中k
 为整数，则定义a ≡ b（modm） ，其含义为：b 是a 除以m 的余数（ b 为a 模m 的余
 数，或a 与b 模m 同余） 。
 定义1.6 　amodm 表示a 模m 运算，表示a 除以m 的余数，其值能够取遍0
 到m - 1 之间的整数。
 例如，（7 + 8）mod12 ＝ 15mod12 ＝ 3 ，也可表示成：15 ≡ 3（mod12） 。
 模运算（ + ，- ，× ）满足交换律、结合律和分配律。按模运算原理：对中间结
 果做模运算，与做完全部运算后再做模运算的所得结果相同。
 命题1.2 　设整数m ≥ 1 ，则有
 （1） 若a1 ≡ a2 （modm） ，b1 ≡ b2 （modm） ，则a1 ± b1 ≡ a2 ± b2 （modm） ，且a1 ? b1 ≡
 a2 ? b2 （modm） 。
 （2） 设a 为整数，当且仅当gcd（ a ，m） ＝ 1 时，存在整数b 满足a ? b ≡ 1
 （modm） 。若这样的b 存在，称其为a 模m 的乘法逆元，也可以是a- 1 表示a 的逆元。
 证明
 （1） 设
 a1 ＝ a2 + k1 m ，　b1 ＝ b2 + k2 m
 则
 a1 ± b1 ＝ a2 ± b2 + （ k1 ± k2 ） m
 即
 a1 ± b1 ≡ a2 ± b2 （modm）
 对于a1 ? b1 ≡ a2 ? b2 （modm） ，有
 a1 ? b1 ＝ （ a2 + k1 m） ? （ b2 + k2 m） ＝ a2 ? b2 + （ k1 b2 + k2 a2 + k1 k2 m） ? m
 即
 a1 ? b1 ≡ a2 ? b2 （modm）
 （2） 必要性：设gcd（ a ，m） ＝ 1 ，由定理1.2 知，存在整数b ，v 满足ab + mv ＝ 1 ，
 即ab - 1 ＝ - mv ，能够被m 整除，由同余定义知ab ＝ 1（modm） 。
 充分性：设a 存在模m 逆元，即a ? b ≡ 1（modm） ，则存在整数c 使得ab - cm ＝ 1 。
 又因为gcd（ a ，m）能够整除ab - cm ＝ 1 ，故gcd（ a ，m） ＝ 1 。
 证毕
 当除数与模m 互素时，可以进行模除法运算。例如，已知7 - 1 ≡ 8（mod11） ，计
 算
 5
 7 ＝ 5 ? 7 - 1 ≡ 5 ? 8 ≡ 40 ≡ 7（mod11） 。
 继续讨论模运算的性质。若对a 做带余除法a ＝ m ? q + r ，0 ≤ r ＜ m 。这表明
 满足a ≡ r（modm）的r 能够取0 到m - 1 之间的所有整数。所以，若要研究模m
 的整数，只需要取0 ≤ r ＜ m 即可。这就引出了同余类的概念。
 定义1.7 　记整数模m 同余类环为
 ￠ / m ￠ ＝ ｛0 ，1 ，2 ，… ，m - 1｝
 注意到在同余类环中所进行的运算，所得结果均需模m 以保持运算的封
 闭性。
 定义1.8 　命题1.2 中的命题（2）证明了若gcd（ a ，m） ＝ 1 ，则a 存在模m 的乘
 法逆元。这种具有逆元的元素称为单位，用如下记号来表示所有单位构成的
 集合：
 （￠ / m ￠ ） 倡＝ ｛ a ∈ ￠ / m ￠ ：gcd（ a ，m） ＝ 1｝
 集合（￠ / m ￠ ） 倡称为整数模m 单位群。
 例1.1 　整数模24 单位群为（￠ /24 ￠ ） 倡＝ ｛1 ，5 ，7 ，11 ，13 ，17 ，19 ，23｝ ；整数模
 7 单位群为（￠ /7 ￠ ） 倡＝ ｛1 ，2 ，3 ，4 ，5 ，6｝ 。
 密码学领域中很重要的一个问题就是如何表示（￠ / m ￠ ） 倡中的元素个数。定
 义这个量为欧拉函数。
 定义1.9 　欧拉函数表示（￠ / m ￠ ） 倡中元素的个数，记为
 ?（ m） ＝ # （￠ / m ￠ ） 倡＝ # ｛0 ≤ a ＜ m ：gcd（ a ，m） ＝ 1｝
 从例1.1 中可得，?（24） ＝ 8 ，?（7） ＝ 6 。
 1.1.3 　中国剩余定理
 在一千多年前的?孙子算经?中，有这样一道算术题：今有物不知其数，三三数
 之剩二，五五数之剩三，七七数之剩二，问物几何？ 按照今天的话来说就是：一个
 数除以3 余2 ，除以5 余3 ，除以7 余2 ，求这个数。
 这样的问题，也有人称为“韩信点兵” 。它形成了一类问题：初等数论中如何
 解线性同余式。这类问题的有解条件和解的方法被称为“中国剩余定理”或“孙子
 定理” 。
 最简单的情形是只有两个同余式
 x ≡ a（modm）和x ≡ b（modn） gcd（ m ，n） ＝ 1
 则由中国剩余定理可得上述方程组有唯一解。下面来看一个简单的例子。
 例1.2 　求下面同余方程组的解：
 x ≡ 1（mod5）
 x ≡ 9（mod11）
 （1.1）
 　　解　由模运算的定义可知第一个等式的解具有以下形式：
 x ＝ 1 + 5 y ，　y ∈ ￠ （1.2）
 　　将式（1.2）代入式（1.1）的第2 个等式可得
 1 + 5 y ≡ 9（mod11）
 因此
 5 y ≡ 8（mod11） （1.3）
 　　为了解出y ，将式（1.3）两端乘以5（mod11）的乘法逆元9 ，即
 y ≡ 9 ? 8 ≡ 72 ≡ 6（mod11）
 将y 的值代入到式（1.2）中，最终算出

显示全部信息

格理论与密码学下载

格理论与密码学

发布书评

相关图书推荐