应用密码学第8讲

1、1本次课的安排：q公钥密码体制的概念qRSA密码算法q椭圆曲线密码算法2一、公钥密码体制的基本概念一、公钥密码体制的基本概念先考虑两个问题：1、密钥分配问题。2、数字签字问题。 数字签字是考虑如何为数字化的信息提供一种类似于书面文件签字或盖章的方法。这两个问题，导致了公钥密码体制的产生。公钥密码体制的产生是密码史上一次真正的革命。公钥密码算法的基本工具不再是代换和置换，而是数学函数。公钥密码算法的理论基础是数论。31、公钥密码体制的原理、公钥密码体制的原理加密密钥和解密密钥：加密密钥和解密密钥：公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开。 其中一个密钥是公开的，称为公开密钥公

2、开密钥（或称为公钥）。用于加密； 另一个密钥是为用户专用，因而是保密的，称为秘密密秘密密钥钥（或称为私钥），用于解密。PK：公开密钥：公开密钥SK: 秘密密钥秘密密钥在下面的讲解中：4图图4.1 公钥体制加密的框图公钥体制加密的框图EPKBmm=DSKBc加密原理：加密原理：5认证原理：认证原理：图图4.2 公钥密码体制认证框图公钥密码体制认证框图c=ESKAmm=DPKAc注意：注意：实际应用时先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质： 如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的

3、数字签字。6认证保密认证保密实际应用模型实际应用模型图图4.3 公钥密码体制的认证、保密框图公钥密码体制的认证、保密框图c=EPKB ESKAm加密过程：加密过程：解密过程：解密过程：m=DPKA DSKBc72、公钥密码算法应满足的要求、公钥密码算法应满足的要求 接收方接收方B产生密钥对（公开钥产生密钥对（公开钥PKB和秘密钥和秘密钥SKB）在计算上）在计算上是容易的。是容易的。 发方发方A用收方的公开钥对消息用收方的公开钥对消息m加密以产生密文加密以产生密文c，即，即c=EPKBm在计算上是容易的。在计算上是容易的。 收方收方B用自己的秘密钥对用自己的秘密钥对c解密，即解密，即m=DSKB

4、c在计算上是容在计算上是容易的。易的。8 敌手由敌手由B的公开钥的公开钥PKB求秘密钥求秘密钥SKB在计算上是不在计算上是不可行的。可行的。 敌手由密文敌手由密文c和和B的公开钥的公开钥PKB恢复明文恢复明文m在计算在计算上是不可行的。上是不可行的。 加、解密次序可换，即加、解密次序可换，即EPKBDSKB(m)=DSKBEPKB(m)其中最后一条虽然非常有用，但不是对所有的算法都其中最后一条虽然非常有用，但不是对所有的算法都作要求。作要求。93、对公钥密码体制的攻击、对公钥密码体制的攻击q穷搜索攻击：穷搜索攻击：攻击对象是短密钥。 然而，密钥长度太大又会使得加解密运算太慢而不实用，因此公钥密

5、码体制目前主要用于密钥管理和数字签字。q利用公钥计算私钥：利用公钥计算私钥：常用的公钥算法还都未能够证明这种 攻击是不可行的。q可能可能字攻击：字攻击：例如对56比特的DES密钥用公钥密码算法加 密后发送，敌手用算法的公开钥对所有可能的密钥加密后 与截获的密文相比较。如果一样，则相应的明文即DES密 钥就被找出。这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。10二、二、RSA算法算法RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到

6、广泛的应用。111. 密钥的产生密钥的产生 选两个保密的大素数选两个保密的大素数p和和q。 计算计算n=pq，(n)=(p-1)(q-1),其中其中(n)是是n的欧拉函数值。的欧拉函数值。 选一整数选一整数e，满足，满足1e(n)，且，且gcd(n),e)=1。 计算计算d，满足，满足de1 mod (n),即即d是是e在模在模(n)下的乘法下的乘法逆元，因逆元，因e与与(n)互素，由模运算可知，它的乘法逆元一定互素，由模运算可知，它的乘法逆元一定存在。存在。 以以e,n为公开密钥为公开密钥,p , q , (n) ,d为秘密密钥。为秘密密钥。122. 加密加密加密时首先将明文比特串分组，使得

7、每个分组对应的十进加密时首先将明文比特串分组，使得每个分组对应的十进制数小于制数小于n，即分组长度小于，即分组长度小于log2n。然后对每个明文分组然后对每个明文分组m，作加密运算：，作加密运算： cme mod n3. 解密解密对密文分组的解密运算为：对密文分组的解密运算为： mcd mod n 13例题：例题：4-8选选p=7，q=17。求。求n=pq=119，(n)=(p-1)(q-1)=96。取取e=5，满足，满足1e(n)，且，且gcd(n),e)=1。确定满足确定满足de=1 mod 96且小于且小于96的的d，因为因为775=385=496+1，所以，所以d为为77，因此公开钥为

8、因此公开钥为5，119，秘密钥为，秘密钥为77,7,96,17。设明文设明文m=19，则由加密过程得密文为，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为解密为 6677mod 1191914三、椭圆曲线密码体制三、椭圆曲线密码体制为保证为保证RSA算法的安全性，它的密钥长度需一再增大，使得算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得）可用短得多的密钥获得同样的安全性，因此具有广泛

9、的应用前景。同样的安全性，因此具有广泛的应用前景。ECC已被已被IEEE公钥密码标准公钥密码标准P1363采用。采用。151、椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4.1)其中其中a，b，c，d，e是满足某些简单条件的实数。是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为定义中包括一个称为无穷点的元素，记为

10、O。下面举两个椭圆曲线的例子。下面举两个椭圆曲线的例子。16图图4.4 椭圆曲线的两个例子椭圆曲线的两个例子17椭圆曲线上的加法运算定义如下：椭圆曲线上的加法运算定义如下：如果其上的如果其上的3个点位于同一直线上，那么它们的和为个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法。进一步可如下定义椭圆曲线上的加法律（加法法则）：则）： O为加法单位元，即对椭圆曲线上任一点为加法单位元，即对椭圆曲线上任一点P，有，有P+O=P。 设设P1=(x,y)是椭圆曲线上的一点（如图是椭圆曲线上的一点（如图4.4），它的），它的加法逆元定义为加法逆元定义为P2=-P1=(x,

11、-y)。这是因为这是因为P1、P2的连线延长到无穷远时，得到椭圆的连线延长到无穷远时，得到椭圆曲线上的另一点曲线上的另一点O，即椭圆曲线上的，即椭圆曲线上的3点点P1、P2，O共线，所以共线，所以P1+P2+O=O，P1+P2=O，即，即P2=-P1。由由O+O=O，还可得，还可得O=-O18 设设Q和和R是椭圆曲线上是椭圆曲线上x坐标不同的两点，坐标不同的两点，Q+R的定义如下：的定义如下： 画一条通过画一条通过Q、R的直线与椭圆曲线交于的直线与椭圆曲线交于P1，由由Q+R+P1=O得得Q+R= -P1。19 点点Q的倍数定义如下：的倍数定义如下： 在在Q点做椭圆曲线的一条切线，设点做椭圆曲

12、线的一条切线，设切线与椭圆曲线交于点切线与椭圆曲线交于点S，定义，定义2Q=Q+Q= -S。类似地可定义类似地可定义3Q=Q+Q+Q+，等。，等。s-s以上定义的加法具有加法运算的一般性质，如交换律、结合律等。202、有限有限域上的椭圆曲线域上的椭圆曲线密码中普遍采用的是有限域上的椭圆曲线，有限域密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式上的椭圆曲线是指曲线方程定义式(4.1)中，中，y2+axy+by=x3+cx2+dx+e所有系数都是某一有限域所有系数都是某一有限域GF(p)中的元素（其中中的元素（其中p为一为一大素数）。大素数）。其中最为常用的是由方程其中

13、最为常用的是由方程 y2x3+ax+b(mod p) (4.2) (a,bGF(p),4a3+27b2(mod p)0)定义的曲线。定义的曲线。21设设Ep(a,b)表示方程表示方程(4.2)所定义的椭圆曲线上的点集所定义的椭圆曲线上的点集(x,y)|0 xp,0yp,且且x,y均为整数均为整数,x,y满足满足4.2式式 并上无穷远点并上无穷远点O。3 、椭圆曲线上的密码椭圆曲线上的密码为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。困难问题。 考虑方程考虑方程Q=kP，其中，其中P，QEp(a,b)，kp，则由，则由k和和P易

14、求易求Q，但由但由P、Q求求k则是困难的，这就是椭圆曲线上的离散对数问则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。题，可应用于公钥密码体制。22q用椭圆曲线实现Diffie-Hellman密钥交换密钥交换第第1步：取一素数步：取一素数p2180和两个参数和两个参数a、b，则得方，则得方程程(4.2)表达的椭圆曲线及其上面的点构成的表达的椭圆曲线及其上面的点构成的Abel群群Ep(a,b)。第第2步，取步，取Ep(a,b)的一个生成元的一个生成元G(x1,y1)，要求，要求G的阶的阶是一个非常大的素数，是一个非常大的素数，G的阶是满足的阶是满足nG=O的最小正的最小正整数整

15、数n。Ep(a,b)和和G作为公开参数。作为公开参数。下面看一下下面看一下两用户两用户A和和B之间的密钥交换过程：之间的密钥交换过程：23 A选一小于选一小于n的整数的整数nA，作为秘密钥，并由，作为秘密钥，并由PA=nAG产生产生Ep(a,b)上的一点作为公开密钥。上的一点作为公开密钥。 B类似地选取自己的秘密钥类似地选取自己的秘密钥nB和公开钥和公开钥PB A、B分别由分别由K=nAPB和和K=nBPA产生出双方共享的产生出双方共享的秘密密钥。秘密密钥。这是因为这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。攻击者若想获取攻击者若想获取K，则必须由，则必须由PA和和G求出求

16、出nA，或由，或由PB和和G求出求出nB，即需要求椭圆曲线上的离散对数，即需要求椭圆曲线上的离散对数，因此是不可行的。因此是不可行的。24q用椭圆曲线实现用椭圆曲线实现ElGamal密码体制密码体制假设用户B要把信息加密传送给用户A：用户A选择一条椭圆曲线Ep(a,b)，取椭圆曲线上的一个生成 元G；用户A选择一个正整数nA作为秘密密钥，并生成公开密钥 PA=nAG；用户A把Ep(a,b)、 PA和G传给用户B；用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M, 并生成一个随机数k，并计算C1=M+k PA，C2=kG；用户B把C1,C2传给用户A；用户A计算C1 nAC2，结果就

17、是M。因为：C1 nAC2= M+k PA nA kG =M+k PA k (nA G)= M+k PA k PA = M25例例4.15 取取p=751，Ep(-1,188)，即椭圆曲线为，即椭圆曲线为y2x3-x+188,Ep(-1,188)的一个生成元是的一个生成元是G=(0,376)A的公开钥为的公开钥为PA=(201,5)假定假定B已将欲发往已将欲发往A的消息编码到椭圆曲线上的点的消息编码到椭圆曲线上的点Pm=(562,201)B选取随机数选取随机数k=386，由，由kG=386(0,376)=(676,558)Pm+kPA=(562，201)+386(201,5)=(385,328)，得密文为得密文为(676,558),(385,328)26q椭圆曲线密码体制的优点椭圆曲线密码体制的优点（1） 安全性高目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为 ，其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子。因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全。max(exp(log)Op27(2)