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

几乎所有的加密算法( 即对称算法和非对称算法) 都基于有限个元素的运算。而我们习
惯的绝大多数数集都是无穷的,比如自然数集或实数集。而下面将介绍的模运算则是在有限整数集中执行算术运算的简单方法。

首先来看一个来自于日常生活中的有限整数集的例子:

示例1.4   看一下时钟上的时针,如果时间不停增加,将得到以下结果:

1 点,2 点,3 点,…,11 点,12点,1 点,2 点,3 点,…,11 点,12点,1 点,2点,3 点,…

不管时间怎么增加,它的值都不会离开这个集合。

下面将介绍在这样一个有限集内进行运算的一般方法。

示例1.5   考虑拥有9 个数字的集合:

{0, 1, 2, 3, 4, 5, 6, 7, 8}

只要结果小于9 ,就可以正常地执行算术运算,比如:

2 × 3 = 6
4 + 4 = 8

但是8+4 怎么办呢?下面将尝试以下规则:正常地执行整数算术运算,并将得到的结果除以9 。我们感兴趣的只有余数,而不是原来的结果。由于 8+4=12,12除以9 的余数是
3 ,可以写作:

8 + 4 ≡  3 mod 9

以下是模运算的精确定义:

定义1.4.1   模运算

假设,, arm∈ Z (其中 ] 是所有整数的集合),并且m>0。如果m 除 a -r ,可记作:
 

a  ≡   r mod  m

其中m 称为模数,r 称为余数。

这个定义超越了非正式的规则,即“除以模数,考虑余数”。下面将讨论其推理过程。
 
1. 余数的计算

总可以找到一个a ∈Z ,使得

a=q·m+r,其中0  ≤  r < m                          (1.1)

由于 a-r=q`m(m 除a-r),上述表达式可写作:  a≡rmodm( r ∈ {0 ,1,2,…,m-1}) 。
 
示例1.6   假设a=42,  m=9 ,则

42=4⋅ 9+6

 
因此42≡6mod9 。

2. 余数不唯一

考虑一个奇怪的问题:对每个给定的模数m 和整数a ,可能同时存在无限多个有效的余数。下面来看另一个例子。

示例1.7   考虑a=12,m=9 的情形。根据前面的定义,以下几个结果都是正确的:
 

●   12 ≡  3 mod 9 ,3 是一个有效的余数,因为9 |(12 – 3)

  ●   12 ≡  21 mod 9,21是一个有效的余数,因为9 |(21 – 3)
  ●   12 ≡  -6 mod 9 ,-6 是一个有效的余数,因为9 |(-6 – 3)

这里的x  |  y 代表x 除y 。这个操作背后是一个系统。整数集

{…, -24, -15, -6, 3, 12, 21, 30,…}

构成了一个所谓的等价类。模数9 还存在另外8 个等价类:

{…, -27, -18, -9, 0, 9, 18, 27,…}
 {…, -26, -17, -8, 1, 10, 19, 28,…}
       {…, -19,-10 ,-1, 8, 17, 26, 35, …}

3. 等价类中所有成员的行为等价

对于一个给定模数m ,选择等价类中任何一个元素用于计算的结果都是一样的。等价类的这个特性具有重大的实际意义。在固定模数的计算中—这也是密码学中最常见的情况—我们可以选择等价类中最易于计算的一个元素。首先来看一个示例。

示例1.8   许多实际公钥方案的核心操作就是xe mod m 形式的指数运算,其中 x 、e 和m 都是非常大的整数,比如长度为2 048 位。下面将用一个非常简单的例子说明计算模指数运算的两种方法。我们想计算38 mod 7。第一种方法非常简单,而第二种方法将在等价类之间切换。

●   3 = 6561≡2mod7  ,因为6 561= 937⋅ 7 +2 


注意:尽管我们已经知道最后的结果不会大于6 ,但还是会得到相当大的中间结果6561。

●   下面这个方法更加巧妙:首先执行两个部分指数运算:

38 = 34⋅ 34 = 81⋅ 81

然后将中间结果 81 替换为同一等价类中的其他元素。在模数7 的等价类中,最小的正元素是 4( 由于 81 = 11 ` 7 + 4),因此:

38 = 81⋅81 ≡  4⋅ 4 = 16 mod 7

使用这种方法,我们可以轻松地计算出最后结果为16 ≡  2 mod 7 。

注意:第二种方法的计算可以不使用计算器,因为它所涉及的所有数字都不会大于81。而第一种方法中计算6 561 除以7 就已经具有一定的挑战性。我们必须牢记的通用规则就是:应该尽早使用模约简,使计算的数值尽可能小,这样做总是极具计算优势。
 

当然,不管在等价类中怎么切换,任何模数计算的最终结果都是相同的。

4. 余数的选择问题

一般选择等式(1.1) 中满足以下条件的r :

0  ≤   r  ≤ m -1 。

但从数学角度看,选择等价类中的任何一个元素对最后的结果都没有任何影响。

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

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