基于ECC算法的密码技术体系 与密码产品发展研究报告 李述胜 2011年9月 Confidential 北京数字证书认证中心 2007年10月 1 前 言 通过交流：  认识ECC算法的大概原理  认识国家关于商用密码产品应用体系的规 划和关键内容 2 目 录 基于ECC算法的密码技术体系 密码产品发展情况研究 总结不建议 3 ECC算法概述  公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对 数问题类、椭囿曲线类。有时也把椭囿曲线类归为离散对数类。  椭圆曲线密码学（Elliptic curve cryptography，缩写为ECC）是基于椭 圆曲线数学的一种公钥密码的方法。椭圆曲线在密码学中的使用是在1985年 由Neal Koblitz和Victor Miller分别独立提出的。  那椭圆曲线算法的难题是什么呢？ - 椭囿曲线依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上。 4 椭圆曲线的理解：射影平面  ▲直线L上的无穷远点只能有一个。 ▲平面上一组相互平行的直线有公共的无穷远点。 ▲ 平面上任何相交的两直线L1,L2有不同的无穷远点。 ▲平面上全体无穷远点构成一条无穷远直线。 ▲平面上全体无穷远点与全体平常点构成射影平面。 5 椭圆曲线的形状：  6 椭圆曲线的加法    运算法则：任意取椭囿曲线上两点P、Q （若P、Q两点重合，则做P点的切线 ）做直线交于椭囿曲线的另一点R’，过R’做y轴的平行线交于R。我们规定 P+Q=R。（如图） ▲根据这个法则，可以得到如下结论 ：如果椭囿曲线上的三个点A、B、C， 处于同一条直线上，那么他们的和等于零元，即A+B+C= O∞ ▲椭囿曲线无穷远点O∞不椭囿曲线上一点P的连线交于P’，过P’作y轴的平行 线交于P，所以有 无穷远点 O∞+ P = P 。这样，无穷远点 O∞的作用不普 通加法中零的作用相当（0+2=2），我们把无穷远点 O∞ 称为 零元。同时 我们把P’称为P的负元（简称，负P；记作，-P）。（参见下图） ▲k个相同的点P相加，我们记作kP。如下图：P+P+P = 2P+P = 3P。 7 密码学中的椭圆曲线  前面的椭圆曲线是连续的，幵不适合用于加密；必须把椭圆曲线变成离散的点。 因此，要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成 的域）。 选择两个满足下列条件的小于p(p为素数)的非负整数a、b 4a3+27b2≠0 (mod p) 则满足下列方程的所有点(x,y)，再加上 无穷远点O∞ ，构成一条椭囿曲线。 y2=x3+ax+b (mod p) 其中 x,y属于0到p-1间的整数，幵将这条椭囿曲线记为Ep(a,b)。 我们看一下y2=x3+x+1 (mod 23)的图像 E23(1,1)   10+17 = 27？ 10+17 = 27（mod23)= 4    8 椭圆曲线的加密原理：  采用椭囿曲线加密算法的难题开展密钥运算： K=kG [其中 K,G为 Ep(a,b)上的点，k为小于n（n是点G的阶）的整数] 给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对 困难了。  我们把点G称为基点（base point），k（k<n，n为基点G的阶）称 为私有密钥（privte key），K称为公开密钥（public key)。  密码学中，描述一条Fp上的椭囿曲线，常用到六个参量： T=(p,a,b,G,n,h)。 （p 、a 、b 用来确定一条椭囿曲线， G为基点， n为点G的阶， h 是椭囿曲线上所有点的个数m不n相 除的整数部分） p 当然越大越安全，但越大，计算速度会变慢。 9 ECC加密解密过程  举例：一个利用椭圆曲线进行加密通信的过程： 1、用户A选定一条椭圆曲线Ep(a,b)，  并取椭圆曲线上一点，作为基点G。 2、用户A选择一个私有密钥k，并生成公开密钥K=kG。 3、用户A将Ep(a,b)和点K，G传给用户B。 4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M，并产 生一个随机整数r（r<n）。 5、用户B计算点C1=M+rK；C2=rG。 6、用户B将C1、C2传给用户A。 7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。 在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K 、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都是相对困难的。 因此，H无法得到A、B间传送的明文信息。 10 签名过程比RSA复杂  ECC的签名过程和密钥协商都比RSA复杂些，需要在计算摘 要时需要做2次预处理，且需要公钥作为输入参数。  预处理1是指使用签名方的用户标识和签名方公钥，通过运 算得到Z值的过程。Z值用于预处理2，也用于SM2密钥协商 协议。 计算公式为：Z= SM3(ENTL‖ID‖a‖b‖xG‖yG‖xA‖yA)  预处理2是指使用Z值和待签名消息，通过SM3运算得到杂凑 值H的过程。杂凑值H用于SM2数字签名。 - 计算公式为：H = SM3(Z‖M) 11 Hash函数定义（增加了pucPublicKey和pucID） 原型： int SAF_Hash( unsigned int uiAlgoType, unsigned char *pucInData, unsigned int uiInDataLen, unsigned char *pucPublicKey, unsigned char *pucID, unsigned int ulIDLen, unsigned char *pucOutData, unsigned int *puiOutDataLen); 描述： HASH运算，对给定长度数据的HASH运算 参数： uiAlgoType[in] SGD_SM3 SGD_SHA1 SGD_SHA256 HASH算法 pucInData[in] 输入数据 uiInDataLen[in] 输入数据长度 pucPublicKey[in] 签名者公钥。当alAlgID为SGD_SM3时有效。 pucID[in] 签名者的ID值，当alAlgID为SGD_SM3时有效。 ulIDLen[in] 签名者ID的长度，当alAlgID为SGD_SM3时有效。 pucOutData[out] HASH puiOutDataLen[out] HASH长度 0 成功 非0 失败，返回错误代码 返回值： 备注： 当ulAlgID为SGD_SM3且ulIDLen不为0的情况下pPubKey、pucID有效，执行SM2算法签名预处理1操作 。计算过程遵循《SM2密码使用规范》。 12 椭圆曲线算法ECC与RSA算法的比较  ECC与RSA方法相比，有以下的优点： - 安全性能更高，如160位ECC与1024位RSA、DSA有相同的安全强度。 - 计算量小，处理速度快 在私钥的处理速度上（解密和签名），ECC 远 比RSA、DSA快得多。 - 存储空间占用小 ECC的密钥尺寸和系统参数与RSA、DSA相比要小得 多， 所以占用的存储空间小得多。 - 带宽要求低使得ECC具有广泛得应用前景。  ECC将成为通用的公钥加密算法。SET协议的制定者已把它作为下一代 SET协议中缺省的公钥密码算法。 国家密码局也已出台政策文件推广 应用ECC算法。 13 SM2密钥定义：  《SM2椭圆曲线公钥密码算法推荐曲线 参数》是我国推荐使用的ECC曲线。  SM2私钥是一个大于等于1并且小于n-1 （n为SM2算法的阶，其值参见《SM2椭 圆曲线公钥密码算法推荐曲线参数》的 n值）的整数，简记为k，长度为256位 。（32字节）  SM2公钥是SM2曲线上的一个点，由横坐 标和纵坐标两个分量来表示，记为（x ，y），简记为Q，长度为512位。（64 字节） 14 商用密码标准规范体系：    基础类： - 《SM2椭囿曲线公钥密码算法推荐曲线参数》：确定曲线 - 《SM2椭囿曲线公钥密码算法》 ： 确定底层算法 - 《SM2密码使用规范》：确定密钥长度、密钥格式、签名格式和密文格式 ，预处理（摘要过程）； - 《SM2加密签名消息语法规范》，对比P7定义数字信封数据格式 - 《标识规范》：统一定义所有的OID标识； - 《框架规范》：定义总体基础设施的框架。 CA类： - 《证书认证系统密码及其相关安全技术规范》 - 《数字证书认证系统密码协议规范》 - 《密钥管理规范》 - 《数字证书格式》 设备类： - 《密码设备应用接口规范》 - 《智能IC卡及智能密码钥匙密码应用接口规范》 15 标准规范体系：  服务类： - 《通用密码服务接口规范》 - 《证书应用综合服务接口》 - 《时间戳服务接口规范》 - 《身份鉴别接口规范》 - 《基于角色的访问控制技术规范》 - 《单点登彔接口规范》  应用类： - 《密文数据格式规范》 - 《安全电子签章密码应用技术规范》 - 《安全电子文件密码应用规范》 - 《基于服务器的数字证书验证协议》 16 商用密码基础设施框架 应用1 —— 应用N 责任认定 身份鉴别 单点登录 访问控制 时间戳 电子签章 典型密码服务层 通用密码服务 密码设备管理 通用密码服务层 属性证 书系统 电子证据 管理系统 证书认 证系统 密码设备 密码设备服务层 公钥密码基础设施应用技术体系框架 时间戳 系统 基础设施 安全支撑 平台 17 目 录 基于ECC算法的密码技术体系 密码产品发展情况研究 总结不建议 18 ECC算法升级将产生新的市场机遇  CA系统升级（全国第三方CA32多家，行业+企业）  KMC升级（1省1个）  密码设备升级（加密机、USBKey、IC卡）  证书应用类产品升级（认证网关、API、DSVS、电 子签章等） 19 密码设备和软件产品  基于SM2算法的密码设备升级是大势所趋。  支持SM2算法的密码机厂商包括：卫士通、得安、56所、三 未信安等  支持SM2算法的USBkey厂商包括：华大信安、握齐、海泰、 中孚等。  支持SM2算法的DSVS：安信天行、吉大、信安世纪等。  支持SM2算法的CA系统产品：安信天行、吉大、格尔、56所 等 20