大数据

当前位置:首页 > 大数据

《算法导论》第三十一章 续4

31.6 元素的幂

正如我们经常考虑一个对模n的已知元素a的倍数一样,现在考虑对模n的a的幂组成的序列,其中a∈Zn*

QQ截图20220627112848.jpg

模n。从0开始编号,序列中的第0个值为a0 mod n=1,第i个值为ai modn。例如,对模7, 3的幂为

QQ截图20220627113002.jpg

而对模7,2的幂为

QQ截图20220627113038.jpg

在本节中,令<a>表示由a反复相乘生成的zn*的子群,令ordn(a)(对模n, a的阶)表示a在Zn*中的阶。例如,在Z7*中,<2>={1, 2,4},ord7(2)=3。用欧拉phi函数Φ(n)的定义作为Zn*的规模(参见31.3节),就可以将推论31. 19转化为用Zn*表示,从而得到欧拉定理,再具体用ZP*表示(其中p是素数),就得到费马定理。

定理31.30(欧拉定理)  对于任意整数n>1, aΦ(n)=1(mod n)对所有a∈Zn*都成立。

定理31.31(费马定理)  如果 p是素数,则ap-1=1(mod p)对所有a∈Zp*都成立。

证明  根据等式(31.21),如果p是素数,则Φ(p)=p-1。

由于0∉Zp*,故费马定理对Zp中除了0以外的每一个元素都适用。然而,对所有a∈Zp,如果p是素数,则有ap=a(mod p)。

如果ordn(g)=|zn*|,则对模n, Zn*中的每个元素都是g的一个幂,且g是Zn*的一个原根或生成元。例如,对模7,3是一个原根,但2不是。如果Zn*包含一个原根,就称群Zn*是循环的。下列定理是由Niven和Zuckerman[ 265]首先证明的,在此略去其证明过程。

定理31.32  对所有的素数 p>2和所有正整数e,使得Zn*是循环群的n>1的值为2,4,pe和2pe

如果g是Zn*的一个原根且a是Zn*中的任意元素,则存在一个z,使得gz=a(mod n)。这个z称为对模n到基g上的a的一个离散对数或指数,将这个值表示为indn,g (a)。

定理31. 33(离散对数定理)  如果g是 Zn*的一个原根,则当且仅当等式x=y(mod Φ(n))成立时,有等式gx=gy(mod n)成立。

证明  首先假设x=y(mod Φ(n)),则对某个整数k有x=y+kΦ(n)。因此,

QQ截图20220627140440.jpg

反之,假设gx=gy(modn)。因为g的幂的序列生成<g>中的每一个元素,且|<g>| =Φ(n),推论31. 18意味着g的幂的序列是一个周期为Φ(n)的周期序列。所以,如果g2=gy(mod n),则必有x=y(mod Φ(n))。

现在关注以一个素数的幂为模的1的平方根。下面的定理将用在31.8节中讨论的素数测试算法中。

定理31.34  如果p是一个奇素数且e≥1,则方程 

QQ截图20220627140808.jpg

仅有两个解,即x=1和x=-1。

证明  方程(31.34)等价于

QQ截图20220627140910.jpg

由于p>2,有p|(x-1)或p|(x+1),但它们不同时成立。(否则,由性质(31. 3),p也能整除它们的差(x+1)-(x- 1)=2。)如果pQQ截图20220627141104.jpg(x-1),则gcd(pe,x-1)=1,而且由推论31.5,有pe|(x+1)。也就是说,x= - 1(mod pe)。 对称地,如果pQQ截图20220627141104.jpg(x+1),则gcd(pe,x+1)=1,而且推论31.5意味着pe|(x-1),所以x=1(mod pe)。因此,x=-1(mod pe), 或者x=1(mod pe)。

如果一个数x满足方程x2=1(mod n),但x不等于以n为模的1的两个“平凡”平方根:1或-1,则x是一个以n为模的1的非平凡平方根。例如,6是以35为模的1的非平凡平方根。下面给出定理31.34的一个推论,它将用于31.8节中讨论的Miller- Rabin素数测试过程的正确性证明。

推论31.35  如果对模n存在1的非平凡平方根,则n是合数。

证明  根据定理 31. 34的逆否命题,如果对模n存在1的非平凡平方根,则n不可能是奇素数或者奇素数的幂。如果x2=1(mod 2),则x=1(mod 2),故1的所有对模2的平方根都是平凡的。因此,n不能是素数。最后,为了使1的非平凡平方根存在,必有n>1。因此,n必定是合数。

用反复平方法求数的幂

数论计算中经常出现一种运算,就是求一个数的幂对另一个数的模运算,也称为模取幂。更明确地说,希望有一种高效的方法来计算ab mod n的值,其中a, b为非负整数,n是一个正整数。在许多素数测试程序和RSA公钥加密系统中,模取幂运算是一种很基本的运算。采用b的二进制表示,反复平方法可以高效地解决这个问题。

设<bk,bk-1,...,b1,b0)是b的二进制表示(即二进制表示有k+1位长,bk 为最高有效位,b0为最低有效位)。随着c的值从0到b成倍增长,下列过程最终计算出ae mod n。

QQ截图20220627142308.jpg

在每次迭代中,第6行平方操作的使用解释了“反复平方”这个名称的由来。举一个例子, 对a=7,b=560,以及n=561,这个算法计算图31-4中给出的对模561的序列的值,所用到的指数序列出现在表格以c标示的行中。

QQ截图20220627142438.jpg

图31-4  当a=7,b=560=<1000110000>,n=561时,MODULAR-EXPONENTIATION计算ab (mod n)的结果。数值在每次for 循环执行后显示。最终结果为1

这个算法并不真的需要变量c,只是用它使得下面两部分的循环不变:

仅在第4~9行的for循环的每次迭代之前,

1.c的值与b的二进制表示的前缀<bk,bk-1,...,bi+1>相同,且

2.d=ae mod n。

下面使用这个循环不变式:

初始化:最初,i=k,使得前缀<bk,bk-1,...,bi+1>是空的,这对应于c=0。此外,d=1=a0 mod n。

保持:令c'和d'表示在for循环的一次迭代的结束处c和d的值,因此,它们是下一次迭代前的值。每次迭代更新c'=2c(如果bi=0)或者c'=2c+1(如果bi=1),使得c在下一次迭代之前是正确的。如果bi=0,则d'=d2 mod n=(ac)2 mod n=a2c mod n=ac' modn。如果bi=1,则d'=d2a mod n=(ac)2 mod n=a2c+1 mod n=ac' mod n。无论哪种情况,在下一次迭代之前,都有d=ac mod n。

终止:在终止时,i=-1。因此,c=b,因为c具有b的二进制表示的前缀<bk,bk-1,...,b0>的值。因此,d=ac mod n=ab mod n。

如果输入a,b与n都是β位的数,则需要的算术运算的总次数是O(β),并且需要的位操作的总次数是O(β)。


练习

31.6-1  画出一张表, 展示Z11*中每个元素的阶。找出最小的原根g,并画出一张表,对所有x∈Z11*,给出相应的ind11.g (x)的值。

31.6-2  写出一个模取幂算法,要求该算法检查b的各位的顺序为从右向左,而非从左向右。

31.6-3  假设已知 Φ(n),说明如何运用过程MODULAR-EXPONENTIATION,对任意a∈Zn*计算出a -1 mod n的值。


31.7 RSA 公钥加密系统

通过公钥加密系统,可以对传输于两个通信单位之间的消息进行加密,即使窃听者窃听到被加密的消息,也不能对其进行破译。公钥加密系统还能让通信的一方,在电子消息的末尾附加一个无法伪造的“数字签名”。这种签名是纸质文件上的手写签名的电子版本。任何人都可以轻松地核对签名,但却不能伪造它,如果这一消息中的任何位有所变化,整个签名就失去了效力。因此,数字签名可以为签名者身份和其签署的信息内容提供证明。对于电子签署的商业性合同、电子支票、电子购货单和其他一些各方希望进行认证的电子信息来说,这是一种理想的工具。

RSA公钥加密系统主要基于以下事实:寻求大素数是很容易的,但要把一个数分解为两个大素数的积却相当困难。31.8节描述了一个能有效地找出大素数的过程,而31.9节将讨论大整数的分解问题。

公钥加密系统

在一个公钥加密系统中,每个参与者都拥有一把公钥和一把密钥。每把密钥都是一段信息。例如,在RSA加密系统中,每个密钥均由一对整数组成。在密码学中常以参与者“Alice”和“Bob”作为例子:用PA和SA分别表示Alice 的公钥和密钥,用PB和SB分别表示Bob的公钥和密钥。

每个参与者均自己创建公钥和密钥。密钥需要保密,但公钥则可以对任何人透露,甚至可以公之于众。事实上,假设每个参与者的公钥都能在一个公开目录中看到,这样通常是很方便的,这使得任何参与者都可以容易地获得任何其他参与者的公钥。

公钥和密钥指定了可用于任何信息的函数。设D表示允许的信息集合。例如,D可能是所有有限长度的位序列的集合。在最简单、最原始的公钥加密设想中,要求公钥与密钥指定一种从D到其自身的一对应的函数。对应Alice的公钥PA的函数用PA( )表示,对应她的密钥SA的函数表示成SA( ),因此PA( )与SA( )函数都是D的排列。假定已知密钥PA或SA,可以有效地计算出函数PA( )和SA( )。

系统中任何参与者的公钥和密钥都是一个“匹配对”,它们指定的函数互为反函数。也就是说,对任何消息MED,有

QQ截图20220627154547.jpg

无论用哪种次序,运用两把密钥PA和SA对M相继进行变换后,最后仍然得到消息M。


在公钥加密系统中,要求除了Alice 外,没人能在较实用的时间内计算出函数SA( )。对于送给Alice加密邮件的保密性与Alice的数字签名的有效性,以下假设十分关键:Alice 必须对SA保密;如果她不能做到这一点,就会失去她的唯一性,并且加密系统也不能把唯一性赋予她。 假设即使每个人都知道PA,井且能够有效地计算出SA( )的反函数PA( ),依然要保证只有Alice能够计算出SA( )。为了设计一个可行的公钥加密系统,必须解决以下问题:如何创建一个系统,在该系统中可以公开其变换PA( ),而不至于因此而公开其相应的逆变换SA( )的计算方法。这项任务看起来很可怕,然而我们将看到如何去完成它。

在一个公钥加密系统中,加密的工作方式如图31-5 所示。假定Bob要给Alice 发送一条加密的消息M,使得该消息对于窃密者像一串无意义的乱码。发送消息的方案如下:

  • Bob取得Alice的公钥PA(根据一个公开的目录或直接向Alice索取)。

  • Bob计算出相应于M的密文C=PA(M), 并把C发送给Alice。

  • 当Alice收到密文C后,她运用自己的密钥SA恢复原始信息:SA(C)= SA(PA (M))=M。

由于SA( )和PA( )互为反函数,所以Alice能够根据C计算出M。因为只有Alice能够计算出SA( ),所以也只有Alice能根据C计算出M。因为Bob运用PA( )对M进行加密,所以只有Alice可以理解接收的消息。

QQ截图20220627155216.jpg

图31-6  公钥系统的数字签名过程。Alice 将她的数字签名σ= SA (M' )附加到消息M'上,来对消息M'签名。她将消息/签名对(M', σ)发送给Bob, Bob 通过检查等式M' = PA(σ)来验证它。

如果等式成立,则他接受(M',o)作为Alice 已经签名的一个消息

  • Alice运用她的密钥SA和等式σ= SA (M' )计算出信息M'的数字签名σ。

  • Alice把消息/签名对(M',σ)发送给Bob。

  • 当Bob收到(M',σ)时,他可以利用Alice的公钥,通过验证等式M' = PA(σ)来证实该消息的确是来自Alice。 (假设M'包含Alice 的名字,这样Bob就知道应该使用谁的公钥。)如果等式成立,则Bob可以得出消息M'确实是Alice签名的结论。如果等式不成立,那么Bob就得出结论,要么是信息M'或数字签名σ因传输错误而损坏,要么信息对(M', σ)是一个故意的伪造。

因为一个数字签名既证明了签署者身份,也证明了签署的信息内容,所以它是对文件末尾的手写签名的一种模拟。

数字签名必须可被任何能取得签署者的公钥的人所验证。一条签署过的信息可以被一方确认后再传送到其他可以验证签名的各方。例如,这条消息可能是Alice 发给Bob的一张电子支票。Bob确认了支票上Alice的签名后,就可以把这张支票送交银行,而银行也可以对签名进行验证,然后调拨相应的资金。

签署的信息未必是加密的,该信息可以是“公开的”,没有受到保护。如果把上述有关加密和签名的两种方案结合起来使用,就可以创建出同时被签署和加密的消息,签署者首先把其数字签名附加在消息的后面,然后再用他预定的接收者的公钥对最终的消息/签名对进行加密。接收者用其密钥对收到的消息进行解密,以同时获得原始消息和数字签名。然后,接收者可以用签署者的公钥对签名进行验证。相应的纸质文件系统的实现过程为:对文件签名后,将文件封入一个纸质信封内,该信封只能由预定的接收者打开。

RSA 加密系统

在RSA公钥加密系统中,一个参与者按下列过程创建他的公钥和密钥:

1.随机选取两个大素数p和q,使得p≠q,例如,素数p和q可能各有1024位。

2.计算n= pq。

3.选取一个与中(n)互质的小奇数e,其中由等式(31.20),Φ(n)等于(p-1)(q-1)。

4.对模Φ(n),计算出e的乘法逆元d的值。(推论31. 26保证d存在且唯一。给定e和Φ(n),可以利用31.4节中的方法计算d。)

5.将对P=(e, n)公开,并作为参与者的RSA公钥。

6.使对S=(d, n)保密,并作为参与者的RSA密钥。

对于这个方案,域D为集合Zn。为了变换与公钥P=(e, n)相关的消息M,计算

QQ截图20220627160117.jpg

为了变换与密钥S=(d, n)相关的密文C,计算

QQ截图20220627160206.jpg

这两个等式对加密与签名是通用的。为了创建一个签名,签署人把其密钥应用于待签署的消息,而不是密文中。为了确认签名,将签署人的公钥应用在签名中,而非加密的消息中。

我们可以运用31. 6节中描述的过程MODULAR-EXPONENTIATION,来实现上述公钥与密钥的有关操作。为了分析这些操作的运行时间,假定公钥(e, n)和密钥(d, n)满足lge=O(1),lgd≤β,且lgn≤β。然后,应用公钥需要执行O(1)次模乘法运算和O(β2)次位操作。应用密钥需要执行O(β)次模乘法运算和O(β3)次位操作。

定理31. 36(RSA的正确性) RSA 等式(31.37)和(31.38)定义了满足等(31.35)和(31.36)的Zn的逆变换。

证明  根据等(31. 37)和(31.38),对任意M∈Zn,有

QQ截图20220627160536.jpg

因为e和d是对模Φ(n)=(p-1)(q-1)的乘法逆元,所以对某个整数k,有

QQ截图20220627160654.jpg

但是,如果M≠0(mod p),则有

QQ截图20220627160734.jpg

并且,如果M=0(mod p),则有Med=M(mod p)。因此,对所有M,

QQ截图20220627160854.jpg

类似地,对所有M,有

QQ截图20220627160924.jpg

因此,根据中国余数定理的推论31.29,对所有M,有

QQ截图20220627161007.jpg

RSA加密系统的安全性主要来源于对大整数进行因式分解的困难性。如果对方能对公钥中的模n进行分解,就可以根据公钥推导出密钥,这是因为对方和公钥创建者以同样的方法使用因子p和q。因此,如果能够轻易地分解大整数,也就能够轻易地打破RSA加密系统。这一命题的逆命题是,如果分解大整数是困难的,则打破RSA也是困难的。经过20年的研究,人们还没有发现比分解模n更容易的方法来打破RSA加密系统。并且正如我们将在31.9节中所见,对大整数进行分解的困难程度令人惊异。通过随机地选取两个1024位的素数并求出它们的积,就可以创建出一把无法用现行技术在可行的时间内“破解”的公钥。在数论算法的设计方法还缺乏根本突破的情况下,细心地遵循所推荐标准来执行,RSA 加密系统可以为实际应用提供高度的安全性。

然而,为了通过RSA加密系统实现安全性,应该在很长(数百位乃至一千位)的整数.上操作,以防御因式分解技术可能的进步。2009 年,RSA模数通常是在768到2048位的范围内。要建立这样大小的模数,必须能够有效地找出大素数。31. 8节将讨论这个问题。

为了提高效率,通常运用一种“混合的”或“密钥管理”模式的RSA,来实现快速的无公钥加密系统。在这样一个系统中,加密密钥与解密密钥是相同的。如果Alice希望私下把一条长消息M发送给Bob,她从快速无公钥加密系统中选取一把随机密钥K,然后运用K对M进行加密,得到密文C。这里,C和M一样长,但K相当短。然后,她利用Bob的公开RSA密钥对K进行加密。因为K很短,所以计算PB(K)的速度也很快(比计算PB(M)的速度快很多)。然后,她把(C,PB(K))传送给Bob, Bob对PB(K)解密后得到K,然后再用K对C进行解密,得到M。

类似地,可以使用一种混合的方法来提高数字签名的执行效率。在这种方法中,使RSA与一个公开的抗冲突散列函数h相结合,这个函数是易于计算的,但是对这个函数来说,要找出两条消息M和M',使得h(M)=h(M'),在计算上是不可行的。h(M)的值是消息M的一个短(如256位)“指纹”。如果Alice 希望签署一条消息M,她首先把函数h作用于M得到指纹h(M),然后用她的密钥加密h(M)。她将(M, SA (h(M))作为她签署的M的版本发送给Bob。Bob可以通过计算h(M),并将PA应用于收到的SA(h(M)验证其是否等于h(M)来验证签名的真实性。因为没有人能够创建出两条具有相同指纹的消息,所以在计算上不可能既改变了签署的消息,又保持了签名的合法性。

最后,我们注意到利用证书可以更轻松地分配公钥。例如,假设存在一个“可信的权威”T,每个人都知道他的公钥。Alice 可以从T获取一条签署的消息(她的证书),声明“Alice的公钥是PA”。由于每个人都知道PT所以这个证书是“自我认证”。Alice 可以将她的证书包含在签名信息中,使得接收者可以立即得到Alice 的公钥,以验证她的签名。因为她的密钥是被T签署的,所以接收者知道Alice的密钥确实是Alice本人的密钥。


练习

31.7-1  考虑一个RSA密钥集合,其中p=11,q=29,n=319,e=3。在密钥中用到的d值应当是多少?对消息M=100加密后得到什么消息?

31.7-2  证明:如果Alice的公开指数e等于3,并且对方获得了Alice 的秘密指数d,其中0<d<q(n),则对方能够在关于n的位数的多项式时间内对Alice的模n进行分解。(尽管不用证明下列结论,但你也许会对下列事实感兴趣:即使条件e=3被去除,上述结论仍然成立。参见Miller[255]。)

*31.7-3 证明:在如下意义中,RSA是乘法的:

PA(M1)PA(M2)= PA(M1M2)   (mod n)

利用这个事实证明:如果对方有一个过程,对Zn中的用PA加密的消息,它能够有效地解密出其中的百分之一,则他可以运用一种概率性算法,以较大概率为每一条用PA加密的信息进行解密。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~