椭圆曲线密码算法（ECC）安全实现项目简.doc

1 椭圆曲线密码算法 椭圆曲线密码算法 ECC 安全实现 安全实现 项目简介项目简介 1 信息安全的核心 密码技术信息安全的核心 密码技术 当今社会已进入信息化时代 计算机网络已逐渐应用于社会各个领域 伴随着国民经 济信息化进程的推进和电子商务等网络新业务的兴起 社会对计算机网络的依赖程度越来 越高 计算机网络和信息系统的应用给人们带来了前所未有的方便 大大地提高了劳动生产 率 给社会带来了无限的商机与财富 然而 社会对计算机网络的高度依赖同时也蕴藏着巨大的风险 网络攻击 网络欺诈 网络犯罪将会给社会带来巨大的经济损失和秩序动荡 甚致会使整个人类社会陷入危机 因此 网络和信息系统的安全保密这一个必须解决的问题 已引起了全球社会的极大关注 信息时代呼唤信息安全 而数据加密技术正是保证信息安全的最重要的手段 密码学上通常将数据加密技术分为两大类 对称密码体制和公钥密码体制 对称密码体制是一种传统密码体制 代表性的有 DES AES IDEA RC5 等 它们 的安全性是基于密码体制设计者的水平 偏爱以及复杂的数学运算 在对称加密系统中 加密和解密采用相同的密钥 因为加解密密钥相同 需要通信的 双方必须选择和保存他们共同的密钥 各方必须信任对方不会将密钥泄密出去 对于具有 n 个用户的网络 需要 n n 1 2 个密钥 在用户群不是很大的情况下 对称加密系统是有 效的 但是对于大型网络 当用户群很大 分布很广时 密钥的分配和保存就成了问题 另外 对称加密系统仅能用于对数据进行加解密处理 提供数据的机密性 不能用于数字 签名 因而人们迫切需要寻找新的密码体制 1976 年 Whitfield Diffie 和 Martin Hellman 提出了公钥密码体制的概念 公钥加密 系统中 加密和解密是相对独立的 加密过程使用公钥 E 而解密使用一个不同的 但数 学上相关的 的私钥 D 知道公钥可以对明文进行加密 但不能对密文进行解密 如果接 收者选择并公布了他的公钥 另外任何人都可以用这一公钥来加密传送给接收者的消息 私钥是秘密保存的 只有私钥的所有者才能利用私钥对密文进行解密 公钥加密系统不存在对称加密系统中密钥的分配和保存问题 对于具有n个用户的网 络 仅需要2n个密钥 公钥加密系统除了用于数据加密外 还可用于数字签名 公钥加密系统可提供以下功 能 机密性 Confidentiality 保证非授权人员不能非法获取信息 通过数据加 密来实现 确认 Authentication 保证对方属于所声称的实体 通过数字签名来实现 数据完整性 Data integrity 保证信息内容不被篡改 入侵者不可能用假 消息代替合法消息 通过数字签名来实现 2 不可抵赖性 Nonrepudiation 发送者不可能事后否认他发送过消息 消 息的接受者可以向中立的第三方证实所指的发送者确实发出了消息 通过数 字签名来实现 可见公钥加密系统满足信息安全的所有主要目标 自公钥加密问世以来 学者们提出了许多种公钥加密方法 它们的安全性都是基于复 杂的数学难题 对某种数学难题 如果利用通用的算法计算出秘钥的时间越长 那么基于 这一数学难题的公钥加密系统就被认为越安全 根据所基于的数学难题来分类 有以下三类系统目前被国际公认为是安全和有效的 整数因子分解系统 代表性的有 RSA 离散对数系统 代表性的有 DSA 椭园曲线离散对数系统 ECC 2 2 椭圆曲线密码算法椭圆曲线密码算法 在 ECC 中 我们关心的是某种特殊形式的椭圆曲线 即定义在有限域上的椭圆曲线 其方程如下 y2 x3 ax b mod p 1 这里 p 是素数 a 和 b 为两个小于 p 的非负整数 它们满足 4a3 27b2 mod p 0 满足方程 1 的椭圆曲线如图 1 我们用 Ep a b 表示模 p 椭圆群 其元素是满足上面方程的小于 p 的非负整数对 x y 以及无穷远点 O 在 E 上定义 运算 P Q R R 是过 P Q 点的直线与曲线的另一点关于 X 轴的对 称点 如图 1 当 P Q 时 R 是 P 点的切线与曲线的另一交点的对称点 如图 2 图 1 椭圆曲线上的加法 P Q R 3 图 2 椭圆曲线上的加法 P P 2P R 可以证明 椭圆曲线上的点关于 运算构成 Abel 群 椭圆曲线离散对数问题 ECDLP 定义如下 给定素数 p 和椭圆曲线 E 对 Q kP 在已 知 P Q 的情况下求出小于 p 的正整数 k 可以证明由 k 和 P 计算 Q 比较容易 而由 Q 和 P 计算 k 则比较困难 ECDLP 是比整数因 子分解问题 IFP 和离散对数问题 DLP 难得多的数学难题 基于该难题 Neal Koblitz 和 Victor Miller 在 1985 年分别提出了椭圆曲线密码系统 ECC ECC 即可以用于数据加密 也可以用于数字签名 将椭圆曲线中的加法运算与离散对数中的模乘运算相对应 将椭圆曲线中的乘法运算 与离散对数中的模幂运算相对应 我们就可以建立基于椭圆曲线的对应的密码体制 例如 对应 Diffie Hellman 公钥系统 我们可以通过如下方式在椭圆曲线上予以实现 在 E 上选取生成元 P 要求由 P 产生的群元素足够多 通信双方 A 和 B 分别选取 a 和 b a 和 b 予以保密 但将 aP 和 bP 公开 A 和 B 间通信用的密钥为 abP 这是第三者无法得知的 对应 EIGamal 密码系统可以采用如下的方式在椭圆曲线上予以实现 将明文 m 嵌入到 E 上 Pm点 选一点 B E 每一用户都选一整数 a 0 a N N 为阶数 已知 a 保密 aB 公开 欲向 A 送 m 可送去下面一对数偶 kB Pm k aAB k 是随机产生的整数 A 可以从 kB 求得 k aAB 通过 Pm k aAB k aAB Pm 恢复 Pm 同样对应 DSA 我们可以在椭圆曲线上构造 ECDSA 3 ECC 的技术优势 抗攻击性强 几种公钥系统抗攻击性如图 3 所示 4 图 3 几种公钥系统抗攻击性比较 ECC 和其它几种公钥系统相比 其抗攻击性具有绝对的优势 具有单位比特最高强度 的安全性 如 160bit ECC 与 1024bit RSA DSA 有相同的安全强度 而 210bit ECC 则与 2048bit RSA DSA 具有相同的安全强度 计算量小 处理速度快 虽然在 RSA 中可以通过选取较小的公钥 可以小到 3 的方法提高公钥处理速度 即 提高加密和签名验证的速度 使其在加密和签名验证速度上与 ECC 有可比性 但在私钥的 处理速度上 解密和签名 ECC 远比 RSA DSA 快得多 因此 ECC 总的速度比 RSA DSA 要快得多 在相同的安全强度下 我们用 160bit ECC 进行加解密或数字签名要比用 1024bit RSA DSA 要快大约 10 倍 密钥尺寸和系统参数小 ECC 的密钥尺寸和系统参数与 RSA DSA 相比要小得多 意味着它所占的存贮空间要小 得多 带宽要求低 当对长消息进行加解密时 三类密码系统有相同的带宽要求 但应用于短消息时 ECC 带宽要求却低得多 而公钥加密系统多用于短消息 例如用于数字签名和用于对对称系统 的会话密钥传递 4 公司研发优势公司研发优势 目前 国内只有少数单位投入力量开发 ECC 但均未能成功 其原因是加密算法实质 上是数学问题 而对于 ECC 国内只有很少的专家能完全弄懂椭圆曲线离散对数理论 我公 司首席科学家陈建华博士和研发小组主要成员来自于武汉大学数学与计算机科学学院信息 安全研究室 该研究室是国内最知名的信息安全研究机构之一 陈建华博士近 10 年先后在 武汉大学数学系攻读数学博士 在中国科技大学博士后流动站作博士后研究工作以及在武 汉大学信息安全研究室从事加密算法理论研究工作 他的主要研究领域是超越数论 椭圆 5 曲线的各种计算方法 其研究成果被冯克勤 陆洪文等国内著名同行专家高度评价 达到 国际一流 国内领先水平 对于加密系统 我们有如下技术优势 ECC 1 关于求阶问题 我们研究出了一种新的算阶方法 比目前国际上通行的几种算阶 方法快近千倍 2 关于素数 的选择 国外的 一般选择为 既在域上 一般ppp 2GF n 2n 来说不超过 我们的取为任意的素数 字长可取为多比特 155p160 3 关于椭圆曲线的选择 椭圆曲线应选择为 好的 椭圆曲线 即要求所选择的 曲线即满足安全性要求又满足可用性要求 通过精心的大量计算 我们选出一类满足此条 件的曲线 4 我们的方法可以做到域位长和阶位长相同 5 在 ECC 实施方案上 我们找到了一种不用明文嵌入的方法 6 我们研制的系统 试验后得出的结论是 密钥为 160 的系统其加解密的速ECC 度比快约十倍 RSA1024 武汉大学作为本公司主要股东 全力支持本项目的研发 武汉大学计算中心和信息 安全研究实验室为本项目提供了国内一流的研发环境 我公司将从三个方向推进本项目产品的研发 三个方向是 理论基础研究 系统软件 开发 应用研发 三个方向分别采用不同的国际先进研究手段和研发工具 以保证公司在 理论研究和应用实践两个方面始终处于国际国内领先水平 5 5 行业及市场情况 行业及市场情况 1 国内外信息安全政策 信息安全问题涉及计算机安全和密码使用 有关的政策法规也因此而分为计算机安全 管理政策法规和关于密码使用的政策法规 在信息安全问题出现的早期阶段 各国立法和 管理的重点集中在计算机犯罪方面 近几年 立法和管理的热点转移到对于密码的应用管 理方面 美欧等国对于密码使用的管理政策集中在使用密码进行信息加密和使用数字签名实 施证书授权两个重要方面 主要内容为 政府组织制定技术标准与管理条例 政府鼓励使 用标准商用密码算法 政府不参与商用密码算法安全产品的商业经营活动 商用密码信息 安全产品可以经过中性技术权威的评测认证机构进行评测认证 经过中性机构评测认证的 产品有利于进入市场 各开发公司使用标准密码算法所开发的安全产品的质量与系统安 全性 由开发者负责 毋须向政府申报批准或由政府组织专家审定 产品完全由市场来检 验 选择 优胜劣汰 标准商用密码算法不一定需要硬件保护 保密的关键在于保护密钥 解密的关键则在如何得到密钥 政府限制对不同国家出口不同密钥长度的安全产品 出口 控制标准需执行美国联邦条例法典和国际武器贸易条例 ITAR 关于安全产品出口的规定 目前已有放松 美国限制对中国和俄罗斯出口密钥长于 40 位的安全产品 目前尚未见 有政府限制商用密码安全产品进口条例的规定 我国信息安全管理的基本方针是 兴利除弊 集中监控 分级管理 保障国家安全 对于密码的管理政策实行 统一领导 集中管理 定点研制 专控经营 满足使用 的发 展和管理方针 我国的密码管理基本政策是 全国的商用密码由国家密码管理委员会统一 6 领导 国家密码管理委员会办公室具体管理 研制 生产和经营商用密码必须经国家主管 部门批准 未经国家密码主管部门批准 任何单位和个人不得研制 生产和经销密码产品 需要使用密码技术手段保护信息安全的单位和部门 必须按照国家密码管理规定 使用国 家密码管理委员会指定单位研制和生产的密码 不得使用自行研制的密码 也不得使用从 国外引进的密码 2 信息安全市场分析与预测 整个信息安全产品市场 从应用类型上 可分为防火墙类产品 防攻击类产品 密码 类产品 类产品和访问控制类等产品市场 但以上的产品在技术上均涉及到密码学领 域 密码技术是信息安全产品的核心技术 信息安全类产品的市场前景非常广阔 可广泛用于政府 金融 证券 计算机网络 电信 民航 交通 铁路 海关 税务 公检法 交通 农业 电力 工商 军事 水利 钢铁 石油等行业 另外在各大企业 互联网服务商 ICP 及 ISP 以及个人也有大量顾客 3 国外市场状况 2000 年 3 月份 美国某媒体在网上对各大公司负责采购 IT 产品的专业人士进行了采 访调查 这次调查涉及美国市场上近 4000 个大型用户 调查结果表明 信息安全产品成为 IT 市场上最受关注的焦点 有 50 以上的企业购买信息安全产品年预算超过 500 万元美元 30 的企业表示愿意化费 300 万元美元购买信息安全产品 根据世界性的权威机构 IDC Internationnal Data Company 的调查 1998 年世界 信息安全市场为 1 400 亿元美元 较上年增长一成半 全球 1999 年在信息安全产品的市 场约为 2 200 亿元美元 其中密码加密类产品占有市场份额为 31 约 682 亿元美元 预计未来两年 全球信息安全产品市场会迅速增长至 3 300 亿元美元 在发达国家信息安 全方面的投资占整个信息产业投资的 20 以上 各类信息安全产品市场份额比例如下图所 示 1999年全球信息安全产品市场分额 其它类产品13 密码加密类 产品31 防火墙类 产品37 访问控制 类产品7 认证中心类 产品7 防攻击类 产品5 7 4 国内市场分析 今年 1 月 中国人民银行总行召开了全国金融业电子信息安全会议 指出人民银行将 拨出预算经费的 15 用于信息安全方面的建设 同时要求各金融机构在每年的金融电子化 建设资金中 原则上以不低于 15 的专项资金用于计算机安全项目建设 据初步统计 金 融系统用于信息安全建设的资金将高达 40 50 亿元 而我国金融电子化只占全国信息产业 的 20 1999 年统计数据表明 去年中国的 IT 行业市场达 5000 亿元人民币 信息安全 类产品约占 2 比例 具有 100 亿元人民币的巨大市场 而且这个市场每年均以很高的速 度在增长 其中国内密码类产品占安全产品市场份额约为 30 约 30 亿元 有专家预计 2000 年国内密码类的产品市场将达到 40 亿元 并且到 2001 年密码类产品的市场将达到 65 亿元人民币 2002 年内 国内密码类安全市场将会发展到 100 亿以上 目前 我国国内密码类占有市场的绝大多数产品均采用基于国外有关的技术进行二次 开发 而我公司自主开发的具有自主知识产权的基于 ECC 加密算法为核心技术的系列信息 安全产品 在技术上达到国际一流 国内首创的领先水平 是现有国内所有公钥密码系统 产品的替代产品 预计 2001 年我公司开发的系列产品在国内力争达到 0 3 的市场份额 约 2000 万元 2002 年我公司产品在国内市场份额将力争达到 1 约 1 亿元 2003 年我公司的产品力争 在国内市场达到 2 的市场份额 约 3 亿人民币 今后几年产值和市场占有率将不断增长 市场前景十分看好 5 行业竞争对手 在国际上 虽然已有 ECC 信息加密技术的产品面世 但我司拥有的 ECC 信息加密技术 也处于领先水平 具体介绍见第五章 具有较强的国际竞争力 而在国内市场上 由于国 家商用密码管理上实行专控 不准使用进口技术和产品 因此 国际市场的技术和产品 对我司的影响是很小的 目前 国内还没有厂商或单位成功开发出基于 ECC 算法的加密产品 现有的产品大 多是基于 RSA 或 DES 的算法 所以从这个角度来说 我公司没有具体的竞争对手 RSA 是 目前使用最普遍的公开密钥加密系统 它的密钥长度一般是 512 位 但已被攻破 为了保 证安全 推荐使用的密钥长度是 1024 位 而 ECC 较之于 RSA 的优点是 在同等安全的条件 下 ECC 算法所需的密钥长度远比 RSA 算法短 这就有效地解决了为增强安全强度提高密 钥长度而带来的成本增高 效率降低的问题 ECC 必将取代 RSA 因为它更适合信息产业发 展的需要 信息安全产品主要有四大类 从技术角度分类 第一类是链路层网络加密产品 如保密电话 传真 加密调制解调器及 X 25 DDN 加 密机以及链路传输加密设备等 该类设备解决了信息在传输中端对端的保密问题 但不能 解决信息的有效性和身份的有效性问题 8 第二类是网络层 TCP IP 加密产品 如 IP 加密机 VPN 加密设备 SSL 加密产品等 该类产品适合于虚拟专用网和 WWW 服务器型的数据传输加密 第三类是应用层网络安全产品 该类产品解决数据加密和数据的有效性等安全问题 是电子商务和金融等专用内部网安全的主要产品 第四类网络安全产品是针对操作系统网络协议和数据库中安全功能的不足和疏漏而采 取的监控或补救手段 如网络监控软件 防火墙软件及数据库访问控制软件等产品 我公司的产品主要属于第二类和第三类产品 目前生产第一类产品的主要厂家有原电子部三十所 原邮电部数据所 总参 56 所和 清华紫光顺风公司等 第四类产品的主要厂家有北京天融公司 电子部三十所 原邮电部 数据所 总参 56 所 中科院信息安全工程中心 总参计算中心等 第二 三类产品国内主要厂商有山东德安公司 北京诺方公司 成都卫士通公司 北京信安世纪公司 上海格尔软件公司等 上述公司的核心技术大多是基于 RSA 或 DES 等 算法 例如山东德安公司的主导产品 SJYO SJYO3 SJYO5 已通过国家密码管理委员会办 公室组织的鉴定 为例 该产品支持的密码算法为 RSA 算法 模长为 512 768 1024 2048 位 和 DSA 数字签名算法 模长为 512 1024 位 该公司宣称该 产品达到国内领先 国际先进的水平 但根据权威的第三方说法 该公司的产品只是基于 普通的 RSA 算法 在安全强度 工作效率上都无法和 ECC 产品相抗衡 6 预期研发成果与计划 本项目的研发分阶段进行 第一阶段 基础理论探索和基本算法实现 研究椭圆曲线密码理论 用软件实现椭圆 曲线的基本加 解密功能 本阶段已经完成 第二阶段 继续深层次研究椭圆曲线密码理论及其实现技巧 深入分析椭圆曲线安全 性能 优化实现算法 提高实现效率 本阶段预计需要 6 9 个月 第三阶段 在继续研发的同时 组织有关部门对科研成果进行技术鉴定 获取研发许 可和生产许可 申请专利 获取研发许可和生产许可在时间上具有不确定性 公司争取在 2001 年 6 月底完成 在公司获取研发许可和生产许可后将逐步进行应用产品开发 公司拟开为以下产品 ECC 加密