当前位置:首页 >> 能源/化工 >>

公钥密码理论与技术的研究现状及发展趋势


第 32 卷 Vol.32

第 17 期 № 17

计 算 机 工 程 Computer Engineering
文章编号:1000—3428(2006)17—0004—03 文献标识码:A

2006 年 9 月 September 2006
中图分类号: TP309

·发

展趋势/热点技术·

公钥密码理论与技术的研究现状及发展趋势
叶生勤
(福建移动通信有限责任公司业务支撑中心,福州 350001) 摘 要:密码技术是信息安全技术的核心。该文概括介绍了国内外公钥密码的研究现状,特别是近年来国际上相继进行的一系列大型的密 码标准化工作,阐述了公钥密码的主要理论基础,介绍了椭圆曲线公钥密码体制及其特点。指出了公钥密码的发展趋势及我国在制定密码 的标准化问题上的研究重点。 关键词:公钥密码;大数因子分解问题;有限域;椭圆曲线离散对数问题

Status and Trend of Public Key Cryptography
YE Shengqin
(Service Support Center of Fujian Mobile Communication Co. Ltd., Fuzhou 350001) 【Abstract】Cryptography is the core of information security technology. This paper outlines the status of public key cipher, and the primary theory foundation of public key cryptography is formulated, especialy, the ECC & its characteristics are introduced in detail. Finally, this paper indicates the development trend for public key cryptography. 【Key words】Public key cipher; IFP; Galois field; ECDLP

密码 (学 )技术是网络与信息安全技术的核心。 1976 年, 美国密码学专家 Whitfield Diffie 和 Martin Hellman 发表了题 为“ New Directions in Cryptography”的这篇划时代的文章, 奠定了公钥密码体制的基础,它的提出被认为是密码学上的 一个里程碑。自从公钥密码的概念被提出以来,特别是近年 来国际上相继进行了一系列大型的密码标准化工作,如欧洲 的 NESSIE 计划、 日本的 CRYPTREC 计划以及韩国的相关密 码工作等,国际上又掀起了一次研究公钥密码的新高潮。 1.1 国内外主要的公钥密码及分析 自从公钥密码的概念被提出以来,国际上相继提出了许 多公钥密码方案。 如基于大整数因子分解困难问题的 RSA 体 制 和 Rabin 体 制 ; 基 于 有 限 域 上 的 离 散 对 数 困 难 问 题 的 Diffie-Hellman 公钥体制和 ElGamal 体制; 基于椭圆曲线上的 离散对数困难问题的 Diffie-Hellman 公钥体制和 ElGamal 体 制 。 此 外 , 还 有 基 于 背 包 问 题 的 Merkle-Hellman 体 制 和 Chor-Rivest 体制; 基于代数编码理论的 MeEliece 体制以及基 于有限自动机理论的公钥体制等。目前主要有两大类型的公 钥密码系统是安全实用的: (1)基于大整数因子分解问题的, 其中最典型的代表是 RSA 体制; (2)基于离散对数问题的, 如 ElGamal 公钥密码体制和影响比较大的椭圆曲线公钥密码 体制。由于分解大整数的能力日益增强,因此为保证 RSA 体 制的安全性总是要增加模长。目前 768bits 模长的 RSA 体制 已不安全。一般建议使用 1 024bits 模长,预计要保证 20 年 的安全性就要选择 2 048bits 的模长,增大模长所导致的巨大 的计算复杂度带来了实现上的难度。而基于离散对数问题的 公钥密码在目前技术下 512bits 模长就能够保证其安全性, 特 别是椭圆曲线上的离散对数的计算要比有限域上的离散对数 的计算更困难, 目前技术下只需要 160bits 模长即可保证其安 全性,特别适合于智能卡的实现,因而受到国际上的广泛关 —4—

1 国内外公钥密码及其研究现状

注。国际上已制定了椭圆曲线公钥密码标准 IEEEP1363。 1.2 NESSIE NESSIE(New European Schemes for Signatures, Integrity, and Encryption)总共召开了 4 次国际会议,共收到了来自 10 多个国家的 42 种密码算法 (包括分组密码、流密码、 MAC、 Hash 函数、公钥密码、数字签名及非对称识别方案 ) , 2003 年 2 月 27 日公布了 17 个推荐算法, 其中有 10 个对称算法 (4 个分组密码, 4 个 MAC和 2 个 Hash函数 )、 3 个公钥密码算法、 3 个数字签名方案和 1 个非对称识别方案。 另外, 17 个 NESSIE 推荐算法中有 5 个是性能良好的正在使用中的标准 (包括 1 个 公钥密码算法 RSA-KEM)。下面分别概括了 NESSIE中涉及公 钥密码算法及数字签名方案的简要情况 [2~ 4]。 1.2.1 NESSIE 公钥密码算法 (1)PSEC-KEM : NESSIE 的 首 要 推 荐 。 PSEC(Provably Secure Elliptic Curve Encryption)是日本 NTT 实验室提出的一 个基于椭圆曲线的公钥加密方案,它的加密消息不需要预先 进行信息编码。在假定 EC-DDH 正确的情况下,Hash 函数 h 选用随机预言模型,则 PSEC 对于自适应选择密文攻击是可 证明安全的。 (2)RSA-KEM: NESSIE 的第 2 推荐。是由 RSA 算法与 最优非对称加密模式 (OAEP) 组合在一块的一个公钥加密算 法。 由 RSA 欧洲实验室的 J.Jonsson 和美国的 B.Kaliski 提交。 (3)ACE Encrypt: ACE 加密算法是 Advanced Cryptogra -phic Engine 的简称。由 IBM 苏黎士研究室的 Victor Shoup 提交。决策 Diffie-Hellman 问题 (DDH)、强 RSA 假设、安全 Hash 函数等假定下对适应选择密文攻击是安全的。具有可证 明的安全性。 (4)EPOC : EPOC 是 Efficient Probabilistic Public Key
作者简介:叶生勤(1965—),男,工程师,主研方向:通信技术管理 收稿日期:2005-11-10 E-mail:yeshengqin@fj.chinamobile.com

Encryption 的简称,本算法由日本 NTT 实验室的 Tatsuaki Okamoto 提交,有 3 个版本: EPOC-1、 EPOC-2、 EPOC-3。 在某些适当的假设和随机预言模型下对适应选择密文攻击是 可证明安全的。 是一个概率加密体制, 使用了单向陷门函数 (H ASH 函数 ),也可使用对称加密算法。 (5)ECIES : 全 称 是 椭 圆 曲 线 整 体 加 密 方 案 , 由 加 拿 大 Certicom 公司提交。 安全性是基于椭圆曲线上离散对数问题。 1.2.2 NESSIE 数字签名方案 (基于公钥密码 ) (1)RSA-PSS: NESSIE 的首选推荐方案。是由 RSA 欧洲 实验室的 Jakob Jonsson 提交,将概率签名方案 (PSS)与 RSA 算法结合起来,使用了 EMSA-PSS 编码方案,适用于一般的 可适当抗击物理攻击的应用。 (2)ECDSA : NESSIE 的 第 2 推 荐 方 案 。 是 由 加 拿 大 Certicom 公司提交的椭圆曲线数字签名算法,其安全性基于 椭圆曲线上的离散对数问题。 (3)SFLASH :由法国的 Jacques Patarin提交。是一个选择 了特殊参数的 C*算法和多变量的公钥方案,使用了 3 个有限 域,安全性基于解多变量的二次方程的困难性。没有多项式 攻击方法或者低于 280的攻击, 是适合于价格低廉的智能卡的 快速数字签字算法。 (4)ESIGN:由 NTT 的 Tatsuaki Okamoto 提交。在适当的 假设和随机预言模型下,对适应选择明文攻击是可证明安全 的。它适合于软硬件实现,而且由于它比其它一般的签名算 法更有效, 因此它特别适合于智能卡和价格低廉的其它设备。 (5)QUARTZ:由法国的 Jacques Patarin 提交。其数学基 础是有限域上隐藏多项式方程 (HFE)和多变量代数等问题。 是 一个选择了特殊参数的 HFEV 算法和多变量的公钥方案,安 全性基于解多变量的二次方程的困难性,这个签名方案的一 个显著特点是签名长度短只有 128bits。 (6)FLASH :由法国的 Jacques Patarin提交。是一个选择了 特殊参数的 C* 算法和多变量的公钥方案,使用了两个有限 域,安全性基于解多变量的二次方程的困难性。没有多项式 攻击方法或者低于 280的攻击, 是适合于价格低廉的智能卡的 快速数字签字算法。 (7)ACE Sign:是与 ACE Encrypt 加密算法对应的数字签 名算法,由 IBM 苏黎士研究室的 Victor Shoup 提交。在决策 Diffie-Hellman 问题 (DDH)、强 RSA 假设、安全 Hash 函数等 假定下,对适应选择密文攻击是安全的。对能动选择明文攻 击是安全的。具有可证明的安全性。 1.3 CRYPTREC CRYPTREC(Cryptography Research and Evaluation Committees)[ 日本 ] 是专为日本构筑电子政府推荐密码技术而 成立的机构。评估活动也历时 3 年 (2001-2003),活动主要参 考了 AES 的做法,并与欧洲的 NESSIE 和 ISO/IEC 国际标准 化组织进行了协作。 该机构委员由日本著名的密码专家组成, 代表着日本密码技术的最高水平。经过 3 年的反复征集、评 估与筛选,2003 年 3 月日本总务省和经济产业省联合公布了 29 个电子政府推荐密码名单 (其中公钥密码 9 个 ),并出台了 电子政府推荐密码技术采购手册,为各省市构筑信息系统顺 利采购推荐密码技术提供技术指南。29 个推荐密码的公布标 志着该机构成立以来的首要任务已经完成。 表 1 概括了 CRYPTREC中涉及的 9 个公钥密码算法的简 要情况。从表 1[5]可以看出其中有部分算法同时也是 NESSIE 推荐算法。

表 1 CRYPTREC 推荐的公钥密码算法
算法 分类 名称 简介及设计特点 DSA 是 NIST 提出的标准化数字签名算法, 该算法的安全性基于有限域上的离散对数问题。 理论上没有可证明安全性证明,但经验上是安全 的。从安全的角度出发,CRYPTREC 力荐取 | p |=1 024 CRYPTREC 对 ECDSA(ANSI X9.62) 和 ECDSA(SEC1) 进行了评估。ECDSA(ANSI X9.62) 是数字签名法指南中记载的数字签名方式。 ECDSA(SEC1) 中的曲线是 SEC1 中规定的椭圆曲 线,目前还没有对其安全性提出问题 CRYPTREC 分别对签名 (RSASSA-PKCSl-vl _5 与 RSA-PSS) 和加密 (RSAES-PKCS1-v1_5 与 R SA-OAEP) 作了评估。这 4 种 RSA 方式从其长期 广泛使用的实绩和接受过深入评估研究的角度 看,经验上是安全的。RSASSA-PKCSl-vl_5 没有 可证明安全性证明; RSA-PSS 是新提出的方案, 理论上提供了可证明的安全性; RSA-OAEP 是 新提出的密码算法,提供了可证明安全性证明 DH 存在几种样式, CRYPTREC 仅对 ANSI X9.42-2001 进行了评估。该算法的安全性基于有 限域上计算离散对数困难。针对主动攻击没有提 供可证明安全性证明,但经验上是安全的。从安 全角度出发, CRYPTREC 力荐 |p|>1 024 算法的安全性基于椭圆曲线上的离散对数 问题的困难性。针对主动攻击没有可证明安全性 证明,但经验上是安全的。ECDH(SECl) 中的椭圆 曲线是 SEC1 中规定的椭圆曲线,目前还没有对 其安全性提出问题。从安全角度出发, CRYPTREC 力 荐群 的阶要选择含有 素因 子位数 在 160bits 以上的参数 该算法的安全性基于椭圆曲线上的离散对 数难题。提案中提供了关于 KEM 的可证明安全 性证明,在 KEM-DEM 中使用 PSEC-KEM 是安 全的

DSA

数字 签名 ECDSA

RSASSA-PKCS1-v1_5 RSA-PSS RSAES-PKCS1-v1_5

加密

RSA-OAEP

DH

密钥 交换

ECDH

PSEC-KEM

2.1 公钥密码的抽象描述 用抽象的观点来看,公钥密码体制就是一种陷门单向函 数。我们说一个函数 f是单向函数,即对它的定义域中的任意 x 都易于计算 f(x) ,而对 f 的值域中的几乎所有的 y ,即使当 f 为 已知时要计算 f-1(y)在计算上也是不可行的。若当给定某些辅 助信息 (陷门信息 ) 时易于计算 f-1(y) ,就称单向函数 f 是一个陷 门单向函数。公钥密码体制就是基于这一原理而设计的,将 辅助信息 ( 陷门信息 ) 作为秘密密钥。它的安全性取决于它所 依据的数学问题的计算复杂性。 2.2 公钥密码的设计原理 2.2.1 基于大整数因子分解问题 (IFP)的公钥密码体制 这类密码体制以 RSA 为代表。表 1 中 RSA-KEM 、 RSA-PSS、 CRYPTREC 的 RSA 相关算法都是以 RSA 算法为 基础的。在理论上,RSA 的安全性取决于大数因子分解的困 难性, 但在数学上至今还未证明分解模 n 就是攻击 RSA 的最 佳方法,也未证明分解大整数就是 NP 问题,可能有尚未发 现的多项式时间分解算法。 2.2.2 基于有限域的离散对数问题 (DLP)的公钥密码体制 这一类中最著名的算法是 NIST 于 1994 年通过的数字签 名标准 (DSS)中使用的数字签名算法 DSA 及 ElGamal 密码体 制。DSA 算法的详细描述见文献 [1]。若能找到有效的算法从 g 和 y 求出 x, DSA 算法便被攻破。因此 DSA 的安全性依赖 于有限域上的离散对数问题的困难性。有限域上的离散对数 问题的难度和大整数因子分解问题的难度相当, DSA 的安 —5—

2 公钥密码的理论和技术

全性与 RSA 相比差不多。出于安全性的考虑,一般建议 p 的 长度至少为 1 024bits,而要保证长期的安全性则要求其长度 至少为 2 048bits。 2.2.3 椭圆曲线离散对数问题 (ECDLP)的公钥密码体制 (ECC) (1)椭圆曲线的定义 ECC是目前公钥密码领域的研究热点。如上表 1 所示, NESSIE 及 CRYPTREC中都有多种公钥密码算法属于 ECC。 有 限域 Fq上的椭圆曲线是仿射、非奇异的 Weistrass方程:
2 3 2 E / Fq : y + a1xy + a3 y = x + a2 x + a4 x + a6 , ai ∈ Fq

椭圆曲线 E(Fq) 上点 P 的阶是指一个最小的正整数 n ,使 nP=O 。而椭圆曲线离散对数问题 (ECDLP) 是指:给定曲线 E(Fq) 上阶为 n 的点 P ,若 Q 是 E 上另一个点,找一个整数 l , 0 ≤ l<n ,使得 Q=lP( 如果这样的 l 存在 ) 。对该系统的攻击依赖 于在 Fq上求解方程: lP ≡ Q mod q 或 l = log P Q mod q 。 DLP求解 是非常困难的, ECDLP 比 DLP 更难求解。在 Fq 上选择一条椭 圆曲线 E(Fq)及一个具有较高阶的基点 P,计算该点的倍乘 lP, 相对来说较容易,但已知 P 和 lP 要求 l 则是很困难。基于椭圆 曲线密码的安全性最终归结为解 ECDLP问题。当计算量足够 大,以致此 ECDLP问题无法解决时,认为该密码体制是安全 的。 ECC最重要的研究是它的安全性,而它的安全性依赖于 ECDLP的安全性。对于 ECDLP的攻击类似于对 DLP的攻击。 一般离散对数存在有效的亚指数时间算法攻击:指数计算法 (Index Calculus),但这种方法不能应用到 ECDLP上。这是因 为在 Index Calculus法中,找一组因子基 (factor base)是很基本 的,但这个概念不能推广到椭圆曲线点群上去,目前还没有 发现 ECDLP有什么特别大的弱点。 (4)安全曲线的选取 在 ECC 实现中,首先要选取安全的椭圆曲线,所谓安全 是指建立在所选曲线上的密码体制能够抗击目前已有的攻 击。为了抗击上面提到的各种攻击,根据式 (2)找的椭圆曲线 应满足下列要求: 1) 为了抗击 Pollard ρ 攻击,所选取 EC 的阶 #E(Fq) 的分解 式中应该包含一个大的素数因子,日前应不小于 160bits; 2)为了抗击 Weil对和 Tate对的攻击,对于 1≤ k≤ 30, n不 能除 qk-1(不宜选取超奇异椭圆曲线 ); 3) 为了抗击 Semaev-Smart-Satoh-Araki 的攻击所选曲线的 阶不能完全等于该曲线所定义于的有限域的阶,即 #E(Fq) ≠ q(不宜选取异常椭圆曲线 ); 4) 对于二进制域 F2 的度 m 不宜为合数。 Gaudry、 Hess 和 Smart 提出,若 m 有小约数 l(l=4),存在比 Pollard ρ 算法 更快求解 ECDLP 的方法。
m

(1)

上的所有 Fq上有理点加上一个无穷远点 O构成的集合:
E ( Fq ) ={( x, y) ∈ Fq × Fq | y 2 + a1 xy + a3 y = x3 + a2 x 2 + a4 x + a6 }∪{O}

在实际密码应用中, 有限域 Fq一般取 q=p(素数 )和 q=2m两 种情形,此时式 (1)在同构意义下 Weistrass方程有更简单的形 式:
E / F p : y 2 = x3 + ax + b, 4a3 + 27b2 ≠ 0
E / F m : y 2 + xy = x3 + a2 x 2 + a6 , a6 ≠ 0 2
E / F m : y 2 + a3 y = x 3 + a 4 x + a6 2

(2) (3) (4)

由式 (3)所决定的椭圆曲线称作异常的 (ordinary), 由式 (4) 所决定的椭圆曲线称作超奇异的 (supersingular)。基于超奇异 椭 圆 曲 线 上 的 公 钥 体 制 的 安 全 性 和 基 于 F2 的 一 个 小 次 数
n

k (≤ 6) 扩张的乘法群

F

*

(2n )k

上离散对数问题的公钥体制的安

全性相当。因而只考虑式 (2)和式 (3)决定的椭圆曲线。 (2)建立椭圆曲线公钥密码体制 (ECC) 1)椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中,首 先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363 标 准 中 , 定 义 其 参 数 为 一 个 七 元 组 : T = (q,FR,a,b,G,n,h),其中 q代表有限域 Fq, q为 p(素数 )或 2m; FR 为域表示法,如 f(x) 为 F2 域元素的不可约多项式的表示法;
m

当 q为素数 p时,方程为式 (2),当 q为 2m时,方程为式 (3),a,b 是方程中的系数;G为基点;n为大素数并且等于点 G的阶,h 是小整数称为余因子且 h=#E(Fq)/n。主要的安全性参数是 n , 因此 ECC密钥的长度就定义为 n的长度。 2) ECC 的密钥 选取了基域 Fq 和椭圆曲线后,得到了在有限域 Fq 上的曲 线 E(Fq)确定的具体的形式,即上述的椭圆曲线域参数的一个 七元组。每个用户选取一个整数 d(1≤ d<n)作为其私钥,而以 点 Q=dG( 为倍乘, G 为基点 ) 作其公钥,这样形成一个椭圆曲 线公钥密码系统。在这个密码体制中,具体的曲线 E(Fq),基 域 Fq,基点 G及其阶 n,以及每个用户的公钥都是该系统的公 开参数,每个用户的私钥是保密的。 3)基于 ECC 的加解密 假设用户 A欲将明文 M加密后发送给 B,A执行以下操作: ①查找 B的公钥 (E(Fq),G, n, QB);②将 M表示成一个域元素, 即 M ∈ Fq ;③在区间 [1, n] 内选取一个随机数 k ;④计算点 kG=(x1, y1);⑤依据 B的公钥计算点 kQB=(x2, y2),若 x2=0,则 返回到第③步;⑥计算 C=M × x2 ;⑦传送加密数据 (x1, y1,C) 给 B。 B收到 A的密文 (x1, y1,C)后,执行以下操作:①使用私钥 dB ,计算点 dB(xl, yl)=(x2, y2) ,再计算 Fq 中的 (x2)-1 ;②计算 M=C(x2)-1,得到明文 M。 (3)椭圈曲线离散对数问题 (ECDLP) —6—

欧洲 NESSIE 计划及日本 CRYPTREC 计划的相继进行, 以及韩国等一些发达国家也不甘落后地启动了相关标准的征 集和制定工作,使得国际上又掀起了一次研究公钥密码的新 高潮。同时美国为适应技术发展的需求也加快了其它密码标 准的更新 (如 SHA-1 和 FIPS140-1)。我国在国家“ 863”计划 中也将制定密码的标准化问题列入了议程。今后,公钥密码 的重点研究方向为: (1) 用于设计公钥密码的新的数学模型和陷门单向函数 的研究; (2)针对实际应用环境的公钥密码的设计; (3) 公钥密码的快速实现研究,包括算法优化和程序优 化、软件实现和硬件实现; (4)公钥密码的安全性评估问题,特别是椭圆曲线公钥密 码的安全性评估问题; (5)欧洲 NESSIE 推荐公钥密码算法的分析及其相关的应 用研究; (6)日本 CRYPTREC 推荐公钥密码算法的分析及其相关 的应用研究; (7)公钥密码在 3G 移动通信系统中的应用研究。 (下转第 9 页)

3 公钥密码的重点研究方向


相关文章:
国内外分组密码理论与技术的研究现状及发展趋势
国内外分组密码理论与技术的研究现状及发展趋势 1 引言 密码( 学 )技术是信息安全技术的核心 ,主要由密码编码技术和 密码分析技术两个分支组成。 码编码技术的...
国内外信息安全研究现状及发展趋势
1.国内外密码理论与技术研究现状及发展趋势 密码理论与技术主要包括两部分,即基于数学的密码理论与技术(包括公钥密码、分组 密码、序列密码、认证码、数字签名、Hash...
密码学的研究方向与发展前景综述
完整性、可用性和抗抵赖性,都需要采用 密码技术来...断增长的情况下,迫切需要发展密码理论 和创新密码...二、研究方向 1.在线/离线密码学 ?? 公钥密码学...
公钥密码技术应用初探本科生毕业论文
概括介绍了国内外公钥密码的研究现状,指出了公钥密码的发展及今 后的研究方向。...1 公钥密码理论和技术 1.1 公钥密码的抽象描述 用抽象的观点来看, 公钥密码...
公钥密码体制研究综述
公钥密码体制研究综述 摘要: 公钥密码体制对于保证网络信息安全起到了非常重要的作用,本文结 合笔者学习密码学基础的一些体会,对公钥密码体制的基本概念,发展现状、及...
公钥密码体制总结及展望
的几种常见的算法以及公钥密码体制的未来发展趋势。...电子商务等技术相结合,保证网上数据传输的机密性、完整...因式分解理论的研究现状表明:所使用的 RSA 密钥至少...
17 国内外信息安全研究现状及发展趋势
1.国内外密码理论与技术研究现状及发展趋势 .国内外密码理论与技术研究现状及发展趋势密码理论与技术主要包括两部分,即基于数学的密码理论与技术(包括公钥密码、分组...
国内外密码学发展现状
(一)最新理论与技术研究进展 我国学者在密码学方面...分布式发展趋势, 并诱发新技术和应用模式的出现。 具体...(3)后量子时代的密码或量子免疫的密码是公钥密码...
网络安全现状及发展趋势毕业论文设计
2.密码理论与技术研究现状及发展趋势密码理论与技术主要包括两部分,即基于数学的密码理论与技术(包括 公钥密码、分组密码、序列密码、认证码、数字签名、Hash 函数、...
公钥密码技术讲义
四川大学计算机网络与安全研究公钥密码技术讲义 1...的情况下,网络中的用户约定一个共同的公开密钥密码...4.1 数字签名原理在文件上手写签名长期以来被用作...
更多相关标签:
国内外研究现状和趋势 | 研究现状和发展趋势 | 本课题研究现状及趋势 | 国内外研究现状及趋势 | 研究现状及发展趋势 | 研究现状与发展趋势 | 研究现状与趋势 | 功能对等理论研究现状 |