读书频道 > 安全 > 深入浅出密码学——常用加密技术原理与应用
1.4.2 整数环
2012-09-26 13:28:58     我来说两句 
收藏    我要投稿   
本书拥有的诸多特征使得它成为密码学从业者和学生独一无二的资源—本书介绍了绝大多数实际应用中使用的加密算法,并重点突出了它们的实用性。对于每种加密模式,我们都给出了最新的安全评估和推荐使用的密钥长度...  立即去当当网订购

在学习完模约简的特性后,我们现在可以尝试定义基于模运算的一般结构。考虑这样一个整数集合:它由 0~m-1 的整数,以及这些整数之间的加法和乘法得到的数组成。该整
数集合对应的数学结构可以表示为: 

定义1.4.2  环

整数环Zm由以下两部分组成:

1. 集合Zm ={0, 1, 2,…,  m -1}

2. 两种操作“+ ”和“× ”, 使得对所有的a, b∈Zm有:

1) a  + b   ≡   c  mod  m, ( c∈ Zm )
2) a  × b   ≡   d  mod  m, ( d∈ Zm )

我们先来看一个简单的整数环例子。

示例1.9   假设m = 9 ,即环Z9 ={0, 1, 2, 3, 4, 5, 6, 7, 8}。

下面是一些简单的算术运算:
 

6+8 = 14  ≡  5 mod 9
6×8 = 48  ≡  3 mod 9

要详细了解环以及与环有关的有限域的内容,请阅读第4.2 节。此时,我们需要关注环的以下重点特性:

●   如果环内任何两个数相加或相乘得到的结果始终在环内,那么这个环就是封闭的。
●   加法和乘法是可结合的,例如对所有的a ,  b ,  c∈Zm ,都有a +( b + c )=(a +  b )+ c 和a ⋅ (b ⋅ c ) = ( a ⋅ b  ) ⋅ c 。
●   加法中存在中性元素0 ,使得对每个a∈ Zm 都有a  + 0  ≡   a  mod  m 。
●   环中的任何元素a 都存在一个负元素-a ,使得a  + ( -a  )  ≡  0 mod m ,即加法逆元始终存在。
●   乘法中存在中性元素1 ,即对每个a∈ Zm ,都有a ×1  ≡   a  mod  m 。
●   不是所有元素都存在乘法逆元。假设a ∈ Zm ,乘法逆元a-1可以定义为:

a ⋅ a-1  ≡  1 mod m。

如果元素a 的乘法逆元存在,则可以除以这个元素,因为b / a   ≡   b ⋅ a-1 mod  m。

●   找出某个元素的逆元比较困难(通常使用欧几里得算法,该算法将在第6.3 节中介绍) 。但可以通过一种简单方法来判断一个给定元素a 的逆元是否存在:

当且仅当gcd(a,m) = 1 ,一个元素a ∈ Zm存在乘法逆元a-1。其中gcd 表示最大公约数(Greatest Common divisor),即同时能除 a 和m 的最大整数。在数论中,两个数的最大公约数是1 有着非常重要的意义,并且拥有专门的称谓,即:如果 gcd(a,m)=1 ,那么 a 和m 就被称作是互素( 互为素数) 或互质。

示例1.10    下面来判断] 26中15的乘法逆元是否存在?

由于

gcd(15, 26)= 1

说明15的逆元肯定存在。而由于

gcd(14, 26)= 2 ≠  1

说明] 26中14的乘法逆元不存在。

另一个环特性就是,对所有的a ,b ,c∈ Zm ,都有 a ×(b  + c ) =( a ×b )+(a ×c ) ,即分配法则成立。简言之,环Zm 是整数{0 ,1 ,2 ,…,m -1}的集合,我们可在该集合内进行加法、减法和乘法运算,有时也可做除法运算。

如前所述,环Zm和带模运算的整数运算在公钥密码学中占有非常重要的位置。实际应用中涉及的整数长度通常都是150~ 4096 位,高效的模运算就显得尤其重要。

点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.4.1 模运算
下一篇:1.4.3 移位密码( 凯撒密码)
相关文章
图文推荐
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站