| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 网络协议 -> 密码编码学与网络安全--原理与实现--(第八版)第5章 ------有限域 -> 正文阅读 |
|
[网络协议]密码编码学与网络安全--原理与实现--(第八版)第5章 ------有限域 |
目录 学习目标
有限域在密码学中的地位越来越重要。许多密码算法都依赖于有限域的性质,特别是高级加密标准(AES)和椭圆曲线加密算法。其他例子包括消息认证码(CMAC)和认证加密方案(GCM)。 本章介绍有关有限域概念的背景知识,以便读者理解AES及其他使用有限域知识的密码算法的设计。 5.1群群、环和域都是数学理论中的分支——抽象代数或近世代数的基本元素。在抽象代数中,我们关心的是其元素能够进行代数运算的集合,也就是说,可以通过多种方法使得集合上的两个元素运算后得到集合中的第三个元素。这些运算方法都遵守特殊的规则,而这些规则又能确定集合的性质。根据约定,集合上元素的两种主要运算符号与普通数字的加法和乘法所用的符号相同。但要指出的是,在抽象代数中并不只限于普通的算术运算,详见后面的介绍。 5.1.1 群的性质群G,有时记为 ---------------------------------------------------------------------------------------------------------------------------------书本这里举了一个置换群的例子,详细请看书 --------------------------------------------------------------------------------------------------------------------------------- 若一个群的元素是有限的,则该群称为有限群,并且群的阶等于群中元素的个数。否则,称该群为无限群。 5.1.2 交换群一个群若满足以下的条件,则称为交换群。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A5). 交换律? 对于G中的任意元素a,b,都有 5.1.3 循环群我们在群中将求幂运算定义为重复运用群中的运算,如 e.g. 整数的加群是一个无限循环群,它由1生成。在这种情况下,幂被解释为是用加法合成的,因此n是1的第n次幂。 5.2 环环R,有时记为 环本质上是一个集合,可在其上进行加法、减法[a-b=a+(-b)]和乘法而不脱离该集合。 环若还满足以下条件,则被称为交换环。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M4)? 乘法交换律? 对于R中的任意元素a,b,有ab=ba。 下面定义整环,它是满足以下公理的交换环。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M5)? 乘法单位元? 在R中存在元素1,使得对R中的任意元素a,有a1=1a=a。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M6)? 无零因子? 若有R中的元素a,b,且ab=0,则必有a=0或b=0. ---------------------------------------------------------------------------------------------------------------------------------后面我会专门出一篇文章来学习环,多项式环,分圆多项式环,等。对于一些密码学方案来说是一种基本的结构 --------------------------------------------------------------------------------------------------------------------------------- 5.3 域域F,有时记为 域本质上是一个集合,可以在其上进行加法、减法、乘法和除法而不脱离该集合。除法又按规则 深入理解这些内容后,下面这些可以替代的描述可能是有用的。域
5.4 有限域GF(p)有限域的阶(元素的个数)必须是一个素数的幂 5.4.1 阶为p的有限域给定一个素数p,元素个数为p的有限域GF(p)被定义为整数 整数 因为w与p互素,若用w乘以 5.4.2 在有限域GF(p)中求乘法逆元当p值较小时,求有限域GF(p)中元素得乘法逆元很容易:只需构造一个乘法表,所要结果直接从表中读出。但是,当p值较大时,这种方法时不切实际的。 若a和b互素,则b有模a的乘法逆元。也就是说,若gcd(a,b)=1,则b有模a的乘法逆元。即对于正整数b<a,存在 再次重复(2.7),我们证明过该式可以用扩展欧几里得算法求解: 现在,若 然而,若 更一般地,对任意n,扩展欧几里得算法可用于求 5.4.3 小结本节介绍了如何构建阶为p的有限域,其中p为素数。特别地,我们用以下性质定义有限域GF(p)。
我们已经证明了有限域GF(p)中的元素是集合{0,1,...,p-1}中的元素,其算术运算是模p的加法和乘法。 5.5 多项式运算?在继续讨论有限域之前,需要介绍一个有趣的问题——多项式算术。这里只讨论单变元多项式,并且将多项式运算分为三种。
本节讨论前两种多项式运算,下一节讨论最后一种多项式运算。 5.5.1 普通多项式运算一个n次多项式( 式中, 在抽象代数中,一般不给多项式中的x赋一个特定值。为了强调这一点,变元x有时被称为不定元。 多项式运算包含加法、减法和乘法,这些运算是把变量x当成集合S中一个元素来定义的。除法也以类似的方式定义,但这时要求S是域。域包括实数域、有理数域、和素数域 加法、减法的运算规则是把相应的系数相加减。因此,若 则加法运算定义为 乘法运算定义为 式中, 5.5.2 系数在Zp中的多项式运算现在考虑系数是域F中的元素的多项式,这种多项式被称为域F上的多项式。在这种情况下,容易看出这样的多项式结合是一个环,称为多项式环。也就是说,如果把每个不同的多项式视为集合中的元素,那么这个结合就是一个环。 对有限域中的多项式进行多项式运算时,除法运算是可能的。注意,这并不是说能进行整除。下面说明两者的区别。在一个域中,给定两个元素a和b,a除以b的商也是这个域中的一个元素。然而,在非域的环R中,普通除法将得到一个商式和一个余式,这并不是整除。 现在,如果试图在非域系数集上进行多项式除法,那么除法运算并不总是有定义的。 然而,如所见的那样,即使系数集是一个域,多项式除法也不一定是整除。一般来说,除法会产生一个商式和一个余式。对于有限域中的多项式,式(2.1)的除法可以重述如下:给定n次多项式f(x)和m次多项式g(x)( 各个多项式的次数为
若允许有余数,则我们说有限域中的多项式除法是可能的。与整数的长除法相同,长除法也适用于多项式除法。后面会给出一些例子。 与整数运算相似,我们可以把余式r(x)写成f(x) mod g(x),即 有限域GF(2)中的多项式对我们而言式有意义的。在有限域GF(2)中加法等价于异或(XOR)运算,乘法等价于逻辑与(AND)运算。 域F中的多项式f(x)被称为不可约的(即约的),当且仅当f(x)不能表示为两个多项式的积(两个多项式都在F上,次数都低于f(x)的次数)。与整数相似,一个不可约多项式也被称为素多项式。 5.5.3 求最大公因式通过定义最大公因式,可以扩展有限域中多项式运算和整数运算之间的相似性。如果:
那么多项式c(x)为a(x)和b(x)的最大公因式。下面是一个等价的定义:gcd[a(x),b(x)]是能同时整除a(x)和b(x)的多项式中次数最高的一个。
上式假设a(x)的次数大于b(x)的次数,可以重复使用(5.3)来求最大公因式。将下列方案和用于整数的欧几里得算法的定义进行比较。 每个循环中都有 5.5.4 小结本节首先讨论了一般多项式的算术运算。在一般多项式算术运算中,变量不被计算,即不给多项式的变量赋值。相反,运用代数的一般规则对多项式进行算术运算(加、减、乘、除)。除非系数是域的元素,否则多项式的除法是不允许的。 接着讨论了有限域GF(p)中的多项式算术运算:加、减、乘、除。然而,除法不是整除,即除法的结果通常是商和余数。 最后,本节说明了使用欧几里得算法可以求有限域中的两个多项式的最大公因式。 本节论述的知识为下一节的学习奠定了基础。下一节中将用多项式来构建阶为 5.6 有限域GF(2^n)前几节中提到过有限域的元素个数必须为 5.6.1 动机实际上所有的加密算法(包括对称密钥和公开密钥算法)都涉及整数集上的算术运算。如果某种算法使用的运算之一是除法,那么就使用定义在有限域中的运算。为了方便使用和提高效率,我们希望这个整数集中的数与给定的二进制位数所能表达的信息一一对应而不应出现浪费。也就是说,我们希望这个整数集的范围是从0到
?5.6.2 多项式模运算设集合S由域 ?式中, 如果定义了合适的运算,那么每个这样的集合S就是一个有限域。定义由如下几条组成。
?5.6.3 求乘法逆元如欧几里得算法可以用来求两个多项式的最大公因式那样,扩展欧几里得算法可以用来求一个多项式的乘法逆元。若多项式b(x)的次数小于a(x)的次数且 如果d(x)=1,那么w(x)是b(x)模a(x)的乘法逆元。计算过程如下: ?5.6.4 计算上的考虑有限域GF( 可以由它的n个二进制系数 加法? ? ?我们发现这里的多项式加法是对应系数分别相加,而对于 乘法? ? ?简单的异或运算不能完成有限域?GF( 这个技巧基于下面的等式:
稍作思考就不难证明式(5.4)是正确的。如果不确定,可以除一下。一般来说,在有限域?GF( ?5.6.5 使用生成元定义有限域GF( 回顾第2章的讨论可知,若a是n的一个本原根,则其幂 首一多项式f(x)是有限域GF(p)上的n次本原多项式,当且仅当其根是有限域GF( 此外,上述方程为真时的最小正整数是 所有本原多项式都是不可约的,反之则不成立。对于不是本原多项式的不可约多项式i,我们可以找到一个正整数 最后,可以证明一个不可约多项式的根g是这个不可约多项式定义的有限域的生成元。 ?通常,对于由不可约多项式f(x)生成的有限域GF( 5.6.6 小结本节说明了如何构建阶为
有限域?GF( |
|
网络协议 最新文章 |
使用Easyswoole 搭建简单的Websoket服务 |
常见的数据通信方式有哪些? |
Openssl 1024bit RSA算法---公私钥获取和处 |
HTTPS协议的密钥交换流程 |
《小白WEB安全入门》03. 漏洞篇 |
HttpRunner4.x 安装与使用 |
2021-07-04 |
手写RPC学习笔记 |
K8S高可用版本部署 |
mySQL计算IP地址范围 |
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年4日历 | -2025/4/2 17:13:43- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |