第5章公钥密码 5.简介 前面介绍了传统密码体制中的对称加密体制,本章要讲述另一种重要的密钥体 制———公钥密码体制。公钥密码学的发展是整个密码学发展历史中最伟大的一次革命, 也许可以说是唯一的一次革命。在公钥密码体制产生和应用之前的整个密码学史中,所 有的密码算法基本上都是基于代换和置换这两种方法。几千年来,对算法的研究主要是 通过手工计算来完成的。随着转轮加密/解密机器的出现,传统密码学有了很大进展,利 用电子机械转轮可以开发出极其复杂的加密系统,利用计算机甚至可以设计出更加复杂 的系统,最著名的就是数据加密标准DES 。转轮机和DES是密码学发展的重要标志,但 它们都基于代换和置换这些初等方法之上。 而公钥密码学与以前的密码学完全不同。公钥密码的发展提供了新的理论和技术基 础,同时也是密码学发展的里程碑。算法的基本工具突破传统的代换和置换,公钥密码使 用的基本工具是数学函数;另一方面公钥密码是非对称的,使用两个独立的密钥,两个密 钥的使用对机密性、密钥分配、数字签名等都有划时代的意义。 公钥密码体制的概念是在解决对称密码体制中最难解决的两个问题时提出的,这两 个问题是密钥分配和数字签名。 对称密码体制在进行密钥分配时,要求通信双方或者已经有一个共享的密钥,或者可 以借助一个密钥分配中心来分配密钥。对前者的要求,常常可用人工方式传送双方最初 共享的密钥,但是这种方法成本很高,而且还要依赖于通信过程的可靠性,这同样是一个 安全隐患;对于第二个要求则完全依赖于密钥分配中心的可靠性,同时密钥中心往往需要 很大的存储容量来处理大量的密钥。 第二个问题数字签名考虑的是如何为数字化的消息或文件提供一种类似于为书面文 件手写签字的方法。这个对于对称密码体制是一个非常难以解决的问题。而随着社会的 发展,尤其电子商务的发展,数字签名问题必须得到好的解决。W.Difie和M.Helman 为解决上述两个问题,从而提出了公钥密码体制。 对称加密和公开加密的一个显著区别体现在密钥协商上:使用对称加密的双方需要 实时协商密钥;而使用公开加密时,用户的公私钥对是收发双方事先按照某种算法产生 的,所以完全避开了密钥协商的步骤,方便陌生人进行加密通信。 对称加密的优点是加解密速度快,尤其针对长报文时;但它的缺点也比较明显,系统 中的密钥数量多而且难以安全分发,同时不能对报文进行发送端鉴别。这些不足说明需 要产生新的加密算法。 与对称加密算法比较而言,公钥密码的优点是:系统中需要产生密钥个数少,而且可 以公开分发密钥,通信双方事先不需要通过保密信道交换密钥;同时可以实现数字签名进 行发送端鉴别。这使得公钥密码特别适用于互联网这种大规模通信的环境。但是它也有 显著的缺点:加解密速度慢,不适合直接加密明文。 公钥密码是密码学上的重大突破,但初学者会对公钥密码有一些误解,这里先提前说 明。一种误解是,从密码分析的角度看,公钥密码比传统密码更安全。事实上,任何加密 方法的安全性依赖于密钥的长度和破译密文所需要的计算量。从抗密码分析的角度看, 原则上不能说传统密码优于公钥密码,也不能说公钥密码优于传统密码。 第二种误解是,公钥密码是一种通用的方法,所以传统密码已经过时。其实正相反, 由于现有的公钥密码方法所需的计算量大,所以取代传统密码似乎不太可能。就像公钥 密码的发明者之一W.Difie所说的:公(“) 钥密码学仅限于用在密钥管理和签名这类应用 中,这几乎是已被广泛接受的事实。” 第三种误解是,对称密码中与密钥分配中心的握手是一件异常麻烦的事情,与之相 比,用公钥密码实现密钥分配则非常简单。事实上,使用公钥密码也需要某种形式的协 议,该协议通常包含一个中心代理,并且它所包含的处理过程既不比对称密码中的那些过 程更简单,也不比之更有效。 本章先介绍公钥密码设计的基本思想与概念,接着介绍Difie-Helman密钥分配协 议。密钥分配协议不是一个公钥密码的加解密算法,但很多人认为它是公钥密码思想的 起源,它是密码学中一个惊人的成就,该算法的作者也因此获得计算机理论研究的最高奖 项———图灵奖。然后讨论RSA算法,它是目前公钥密码中最重要的一种切实可行的加解 密算法,RSA的三位作者也获得了图灵奖。最后我们介绍椭圆曲线密码算法的一些知 识,该领域是公钥密码研究的一个热点。 5.1 公钥密码体制的设计原理 1. 公钥密码算法最重要的特点是采用两个相关的密钥将加密与解密能力分开,其中一 个密钥是公开的,称为公开密钥,用来加密;另一个密钥是用户专用,是保密的,称为私有 密钥,用于解密。加密和解密使用的密钥是不同的,因此公钥密码体制也称为双钥密码体 制。公钥密码算法的重要特性:已知密码算法和加密密钥,想得到解密密钥在计算上是 不可行的。 图5.加密过程主要有以下几步。 1是公钥密码体制加密的框图, (1)系统中要求接收消息的端系统, 如图5. 产生一对用来加密和解密的密钥,1中的 接收者B,需要产生一对密钥PKB 和SKB,其中PKB是公钥,SKB 是私钥。 (2)端系统B将公钥PKB 放在一个公开的寄存器或文件中,通常放入存放密钥的密 钥中心中。另一私钥SKB 则被用户保存。 (3)A如果要想向B发送消息m,则首先必须得到并使用B的公钥PKB 加密m,表 示为 c=EPKB[m] 89 图5.公钥密码体制加密的框图 1 其中, E 是加密算法。 c 是密文; (4)B收到A的加密密文 c 后,用自己的私钥SKB 解密得到明文信息,表示为 c] 其中, D 是解密算法。 m =DSKB[ 因为整个过程中只有B知道SKB,所以其他人都无法对 c 解密,从而信息得到机密性 保护。作为密码分析员可以观察到密文 c 并且可以得到公钥PKB,但是他不能访问私钥 SKB 或者明文m,所以密码分析者的目的是恢复私钥SKB 或者明文m。如果密码分析者 知道加密(E)和解密(D)算法,如果他只关心 m 这一个明文消息,那么他会集中精力试图 通过生成明文估计值来恢复m所以他会 试图破解私钥SKB。 ^。但是通常密码分析者也希望能获得其他消息, 公钥密码不仅能用于保密通信,还可以提供不可否认性,这一点是对称密码由于自身 特点而无法实现的。 首先解释一下不可否认,在使用对称密码保护的情况下,假设A从她的股票经纪人 B处订购了100 股股票,为了保护订单的机密性和完整性,A使用共享对称密钥KAB 加 密,假设A下了订单不久后并在向B付钱之前,股票暴跌90% 。这时A宣布她从没有下 过订单,也就是说A否认了这笔交易。 那么B能否证实A曾经下过订单呢,不,他不能。因为B也知道对称密钥KAB,他可 以假冒A在订单上放置伪造的消息。因此,尽管B知道A确实下了订单,但是却不能证 明这一点。如何防止A否认这笔交易呢? 可以使用数字签名,数字签名就是通过某种密 码运算生成一系列符号及代码组成电子密码进行签名,来代替书写签名或印章,对于这种 电子签名还可进行技术验证。 公钥密码可以实现数字签名,信息发送者可使用公钥密码产生别人无法伪造的一段 数据串。事实上,确保数据机密性只是公钥体系的用途之一,它还有一个非常重要的用途 就是对信息进行数字签名,防止信息发送者抵赖或第三方冒充发送者发送信息。对称加 密算法不能实现这个功能,那为什么公开加密机制可以实现此功能呢? 很简单,还是使用 了“公钥加密,只有私钥能解密;私钥加密,只有公钥能解密”的原理。 90 发送者用自己的私钥加密数据后传给接收者,接收者用发送者的公钥解开数据后,就 可以确定消息来自于谁,同时也是对发送者消息真实性的一个证明,发送者对所发消息不 可否认。如图5.2所示,用户A用自己的私钥SKA 对明文 m 进行加密,过程表示为 c=ESKA[m] 将密文 c 发送给B。B用A提供的公钥PKA 对 c 进行解密,该过程可以表示 为 m =DPKA[ c] 因为从 m 得到 c 是经过A的私钥SKA 加密,也只有A才能做到,因此 c 可以当作 A对 m 的数字签名。另一方面,任何人只要得不到A的私钥SKA 就不能篡改m,所以以 上过程实现了对消息来源和消息完整性的认证功能。 图5.公钥密码体制数字签名原理框图 2 在这个数字签名的过程中,发送者使用私钥加密实现签名的功能,接收者使用公钥解 密实现验证的功能,这与前面提到的加密过程相反。使用公钥密码加密时,发送者使用公 钥加密,接收者使用私钥解密。在许多公钥算法中,两个密钥中任何一个都可用来加密, 而另一个用来解密,可分别实现加解密和数字签名的功能。 在以上数字签名过程中,由于消息是由用户自己的私钥加密的,所以消息不可能被他 人篡改,但却能很容易被他人窃听,这是由于任何人都能使用用户的公钥对消息解密。因 此为了同时提供认证功能和保密性,可采用双重加、3所示。 解密。原理图如图5. 图5.公钥密码体制的认证、保密原理图 3 91 发送方首先用自己的私钥SKA 对消息 m 进行加密,用于提供数字签名功能。然后 用接收方的公钥PKB 进行第二次加密操作,表示为c=EPKB[ESKA[m]], 解密过程为m= DPKA[DSKB[即接收方用自己的私钥和发送方的公钥对收到的密文进行两次解密 c]], 操作。一 般来讲,公钥加密算法应满足以下几点基本要求。 (1)接收方B产生密钥对(公钥PKB 和私钥SKB)是很容易计算得到的。 (2)发送方A用收到的公钥对消息 m 加密以产生密文c,即c=EPKB[m], 很容易通 过计算得到。 (3)接收方B用自己的私钥对密文 c 解密,[ 即 m =DSKBc]在计算上是容易的。 (4)密码分析者或者攻击者由B的公钥PKB 求私钥SKB 在计算上是不可行的。 (5)密码分析者或者攻击者由密文 c 和B的公钥PKB 恢复明文 m 在计算上是不可 行的。 (6)加密、解密操作的次序可以互换,也就是EPKB[DSKB(m)]=DSKB[EPKB(m)]。 以上要求中最后一条虽然非常有用,但并不是对所有算法都有此要求。 以上要求的本质是要求一个陷门单向函数。所谓陷门单向函数是两个集合X、 Y 之 间的一个映射,使得 Y 中每一元素 y 都有唯一的一个原像 x ∈ X ,且由 x 易于计算它的 像y。但是由 y 计算它的原像 x 在计算上是不可行的。这里所说的易于计算是指函数值 能在其输入长度的多项式时间内求出,即如果输入长 n 比特,则求函数值的计算时间是 na 的某个倍数,其中 a 是一个固定常数。这时认为求函数值的算法属于可计算,否则就 是不可行的。注意这里的可计算和不可行两个概念与计算复杂性理论中复杂度的概念非 常相似,同时存在着本质的区别。在复杂性理论中,算法复杂度是用算法在最坏的情况下 或平均情况时的复杂度来度量的。而这里所说的两个概念是指算法在几乎所有情况下的 情景。称一个函数是陷门单向函数,是指该函数是易于计算的,但求它的逆过程是不可行 的,除非在已知某些附加信息的前提下。当附加信息给定后,求逆可在一定时间内完成。 所以总结为:陷门单向函数是一族可逆函数fk ,但是满足以下3个条件。 (1)Y=fk (X)易于计算(当 k 和 X 已知时)。 (f-1 Y)易于计算( 2)X= k (当 k 和 Y 已知时)。 (3) X =f-1 Y)在计算上是不可行的( k (当 Y 已知但 k 未知时)。 1.公钥密码分析 5.2 与对称密码一样,公钥密码也易受穷举攻击,其解决方法也是使用长密钥。但同时也 应考虑使用长密钥的利弊,公钥体制使用的是某种可逆的数学函数,计算函数值的复杂性 可能不是密钥长度的线性函数,而是比线性函数增长更快的函数。因此,为了抗穷举攻 击,密钥必须足够长;同时为了便于实现加密和解密,密钥必须足够短。在实际中,现在使 用的密钥长度确实可以抗穷举攻击,但是它也使加密/解密速度太慢,所以公钥密码目前 主要用于密钥管理和签名中。 92 对公钥密码的另一种攻击方法是,找出一种给定的公钥计算出私钥的方法。到目前 为止,还未在数学上证明对一特定公钥算法这种攻击是不可行的,所以包括已被广泛使用 的RSA在内的任何算法都是值得怀疑的。密码分析的历史表明,同一个问题从一个角度 看是不可解的,但从另一个不同的角度来看则可能是可解的。 最后,还有一种攻击形式是公钥体制中所特有的,这种攻击本质上就是对消息的穷举 攻击。例如,假定要发送的消息是56位的DES密钥,那么攻击者可以用公钥事先对所有 可能的密钥加密,并与截获的密文匹配,从而可破解任何消息。因此,无论公钥体制的密 钥有多长,这种攻击都可以转化为对56位密钥的穷举攻击。这是一种针对公开加密算法 的类似彩虹表的攻击。对抗这种攻击的方法是,在要发送的消息后附加上一个随机数。 5.2 Difie-Helman密钥交换 1976年,WhitfieldDifie和MartinHelman在《密码学的新方向》一文中提出了著 名的Difie-Helman密钥交换算法,标志着公钥密码体制的出现。Difie和Helman第 一次提出了不需要使用保密信道就可以安全分发对称密钥,这就是Difie-Helman算法 的重大意义所在。不仅如此,公钥加密本身就是一个重大创新,因为它从根本上改变了加 密和解密的过程。 密钥交换问题是对称加密的难题之一,Difie-Helman密钥交换算法可以有效地解 决这个问题。这个机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥。 然后可以用这个密钥进行加密和解密。 需要注意的是,Difie-Helman密钥交换算法不是一种加密算法,不能进行消息的加 密和解密。只是一种能使双方共享的对称密钥不需要在网络上传递的算法。双方确定要 用的密钥后,则使用该密钥用某种对称加密算法实现加密和解密消息。Difie-Helman 算法第一次尝试了不需要基于保密信道的密钥分发,它的目的是使两个用户在公共网络 平台上安全地交换一个对称密钥,以便用于随后的报文加密。Difie-Helman算法的吸 引力主要在于对称密钥只在需要的时候才会进行计算,之前密钥不需要保存,所以不会有 泄密的危险。其次,它也不需要PKI的支持,除对全局参数的约定外,密钥交换不需要事 先存在的任何条件。所以目前许多商业产品还在使用这种密钥交换技术,如SSL 、 IPSec等。 Difie-Helman算法的安全性建立在离散对数问题的计算困难性之上。假定给定 g 和x=gk ,那么为了求解 k 需要进行通常的对数运算logg (x)。现在给定g、 p 和 gkmodp ,求解 k 的问题与对数问题类似,不同的是进行的是离散值的计算,这个问题称 为离散对数。尽管同因子分解一样未被证明是NP完全问题,但求解离散对数问题也是 非常困难的。简而言之,可以如下定义离散对数:首先定义一个素数 p 的原根,为其各次 幂产生从1~p-1的所有整数根,也就是说,如果 a 是素数 p 的一个原根,那么数值 a modp,a2modp,…,ap-1modp 是各不相同的整数,并且以某种排列方式组成了1~p-1的所有整数。 93 对于一个整数 b 和素数 p 的一个原根a,可以找到唯一的指数i,使得 b=ai modp,0≤i≤p-1 b)。 指数 i 称为 b 的以 a 为基数的模 p 的离散对数。该值被记为inda ,( 基于此背景知识,可以定义Difie-Helman密钥交换算法。该(p) 算法的实现原理如 图5.描述如下。 4所示, 图5.n密钥交换算法的实现原理 4 Difie-Helma (1)有两个全局公开的参数, a 是 q 的一个原根。 一个素数 q 和一个整数a, (2)设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数 XA