• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 9
    • 下载费用:30 金币  

    重庆时时彩杀通杀码: 椭圆域曲线运算方法和椭圆域曲线运算器.pdf

    关 键 词:
    椭圆 曲线 运算 方法 运算器
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410171041.7

    申请日:

    2014.04.28

    公开号:

    CN103942031A

    公开日:

    2014.07.23

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 7/72申请日:20140428|||公开
    IPC分类号: G06F7/72; H04L9/30 主分类号: G06F7/72
    申请人: 山东华芯半导体有限公司
    发明人: 刘奇浩; 刘大铕; 高美洲
    地址: 250101 山东省济南市高新区新泺大街1768号齐鲁软件园大厦B座二层
    优先权:
    专利代理机构: 济南泉城专利商标事务所 37218 代理人: 丁修亭
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410171041.7

    授权公告号:

    103942031B||||||

    法律状态公告日:

    2017.07.04|||2014.08.20|||2014.07.23

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明公开了一种椭圆域曲线运算方法和椭圆域曲线运算器,涉及到的运算比较全面,采用点乘次数k的新的NAF表示方法,似的k的二进制表示中的非零元素的个数减少,从而减少了点加运算的次数,进而减少了点乘的整体运算时间,而具有比较高的运算效率。

    权利要求书

    权利要求书
    1.  一种椭圆域曲线运算方法,用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法,其特征在于,该方法基于模的运算,并同时基于点的运算;
    其中基于点的运算为对初始点P的运算,并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式:NAF(kp)=(kpm-1……kp1kp0),其中m为NAF表达式的位宽;
    并对初始点P进行倍点,生成的倍点:1P、2P、……np;n为大于等于8小于等于17的自然数;
    对NAF(kp)与生成的倍点进行点乘,直到运算完成,输出运算结果。

    2.  根据权利要求1所述的椭圆域曲线运算方法,其特征在于,对生成的倍点采用给定的数列通式选择出初始倍点,用于初始的点乘运算,并在后续的点乘运算中,给出点乘运算逻辑;
    若按照点乘运算逻辑的路径若逻辑出初始倍点,则直接调用该逻辑出的初始倍点进行运算,若逻辑出其余的倍点,则生成逻辑出的相应倍点后进行点乘运算,直到的运算完成。

    3.  根据权利要求2所述的椭圆域曲线运算方法,其特征在于,所述数列通式采用等差数列通式。

    4.  根据权利要求2或3所述的椭圆域曲线运算方法,其特征在于,点乘运算逻辑采用倍点运算次数和点加运算次数,给出不同倍点运算次数和点加运算次数的组合,以适配于各倍点,并在相应的倍点运算或者点加运算完成后,相应的次数加一。

    5.  根据权利要求1至3任一所述的椭圆域曲线运算方法,其特征在于,所述倍点的个数为13。

    6.  根据权利要求2所述的椭圆域曲线运算方法,其特征在于,将初始倍点存放到存储单元,其余的倍点在点乘运算逻辑中生成。

    7.  一种椭圆域曲线运算器,用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法,其特征在于,包括模的运算器和基于点的运算器;
    其中点的运算器为对初始点P的运算器,并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式:NAF(kp)=(kpm-1……kp1kp0),其中m为NAF表达式的位宽;
    该点的运算器还包括倍点运算器,对初始点P进行倍点,生成的倍点:1P、2P、……np;n为大于等于8小于等于17的自然数;
    以及点乘运算器,对NAF(kp)与生成的倍点进行点乘,直到运算完成,输出运算结果。

    说明书

    说明书椭圆域曲线运算方法和椭圆域曲线运算器
    技术领域
    本发明涉及一种椭圆域曲线运算方法和椭圆域运算器。
    背景技术
    对数据进行加密是一种常用且行之有效的信息安全策略。目前基于有限域上椭圆曲线离散对数问题的非对称密码算法ECC(Emmiptic Curve Cryptography,椭圆曲线密码)被公认为是最高比特强度的公钥密码体制,广泛应用于快速加密、密钥交换、身份验证、数字签名、保密通信等领域,是1985年分别由Mimmer和Kobmitz独立提出的。相对于其他的公钥密码系统(如RSA和EmGamam),椭圆曲线密码系统具有计算速度快、存储空间小、带宽要求低等优点。
    椭圆曲线公钥密码算法作为ECC算法中的一种,加密强度为256位,安全性高、存储空间小、可以快速完成签名、密钥交换以及加密应用。
    椭圆曲线公钥密码算法相关的运算逻辑可以做为独立的单元进行设计,并且采用层次化的划分方式可以分为有限域运算层以及椭圆曲线运算层。
    有限域运算层的主要功能是提供椭圆加密算法所需要的数论运算支持,包括256位大整数模加、模减、模乘、模逆、模幂、比较运算。
    椭圆曲线运算层由有限域运算层的各种基础运算按照一定的规则进行排序后构成,包括点加、倍点、点乘、坐标转换等运算。点乘运算是在点加、倍点的基础上实现的,同时需要有限域运算的支持,因此点乘运算速度决定了加密机制运算速度。
    当前,提升系统整体运算可以通过两种方法来实现:一、提升有限域运算层的基础运算速度,如中国第CN101782845A号发明申请公开针对点加和倍点算法,重新排列了修改的Jacobian坐标点的点加和倍点运算序列,提出了一种实现点加运算和倍点运算的新方法。
    再如中国第CN101221491A号发明专利申请公开利用Jacobian坐标系下椭圆曲线点加的计算公式,提取出相互独立的操作,构造三级流水线电路结构。
    二、优化点乘运算电路的基础运算调用方式,如中国第CN1822539A发明申请公开采用32个子寄存器构成寄存器堆作为数据暂存单元,缓解大数模运算过程中寄存器堆的复用问题。
    但是上述发明专利申请公开的方案均受运算所限制,只能支持模(Mod)运算,对上层运算产生的中间变量则无能为力。
    发明内容
    本发明的目的在于提供一种椭圆域曲线运算方法,提高运算速度,本发明还提供了一种椭圆域曲线运算器。
    依据本发明的一个方面的一种椭圆域曲线运算方法,用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法,该方法基于模的运算,并同时基于点的运算;
    其中基于点的运算为对初始点P的运算,并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式:NAF(kp)=(kpm-1……kp1kp0),其中m为NAF表达式的位宽;
    并对初始点P进行倍点,生成的倍点:1P、2P、……np;n为大于等于8小于等于17的自然数;
    对NAF(kp)与生成的倍点进行点乘,直到运算完成,输出运算结果。
    根据权利要求1所述的椭圆域曲线运算方法,其特征在于,对生成的倍点采用给定的数列通式选择出初始倍点,用于初始的点乘运算,并在后续的点乘运算中,给出点乘运算逻辑;
    若按照点乘运算逻辑的路径若逻辑出初始倍点,则直接调用该逻辑出的初始倍点进行运算,若逻辑出其余的倍点,则生成逻辑出的相应倍点后进行点乘运算,直到的运算完成。
    依据本发明的另一个方面的一种椭圆域曲线运算器,用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法,包括模的运算器和基于点的运算器;
    其中点的运算器为对初始点P的运算器,并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式:NAF(kp)=(kpm-1……kp1kp0),其中m为NAF表达式的位宽;
    该点的运算器还包括倍点运算器,对初始点P进行倍点,生成的倍点:1P、2P、……np;n为大于等于8小于等于17的自然数;
    以及点乘运算器,对NAF(kp)与生成的倍点进行点乘,直到运算完成,输出运算结果。
    依据本发明,涉及到的运算比较全面,采用点乘次数k的新的NAF表示方法,似的k的二进制表示中的非零元素的个数减少,从而减少了点加运算的次数,进而减少了点乘的整体运算时间,而具有比较高的运算效率。
    附图说明
    图1为依据本发明的一种椭圆域运算装置的结构框图。
    图2为基于椭圆加密算法的点乘运算状态转移图。
    图3为非临接表达式NAF(k)运算状态转移图。
    图4为预计算状态转移图。
    具体实施方式
    如图1所示,为椭圆域运算装置的基本配置,它由五个部分构成,分别是系统总线数据接口???、配置接口???、配置寄存器???、运算单元???、数据存储单元???。
    基于所述系统总线数据接口???,图1所示的椭圆域运算装置在系统中以系统总线从设备的形式出现,挂在应用系统的总线上,构成系统总线的从设备。
    通过配置接口??槎愿ㄖ僮魇?、运算类型进行配置,运算完成后读出中断信息。
    通过系统总线数据接口??榕渲貌僮魇?。
    运算单元??楦涸鹜瓿筛髦衷怂?,包括基于模的加法、减法、乘法、取逆、取幂运算,基于点的加法、乘法运算,并在运算完成后产生中断标志位,构成所述中断信息,以使配置接口??槟芄欢寥≡怂愕ピ?榈脑诵凶刺?。
    数据存储单元??橛?块单口RAM构成,负责存储初始操作数及运算结果,配合运算单元调度完成数据的正确转移。
    其中的操作数可以构成为如下所述的倍点。
    在这样的一个实施例中,椭圆域曲线运算器,用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法,包括模的运算器和基于点的运算器;
    其中点的运算器为对初始点P的运算器,并对给定的标量k采用有符号编码中的非相邻有符号二进制编码生成k的NAF表达式:NAF(kp)=(kpm-1……kp1kp0),其中m为NAF表达式的位宽;
    该点的运算器还包括倍点运算器,对初始点P进行倍点,生成的倍点:1P、2P、……np;n为大于等于8小于等于17的自然数;
    以及点乘运算器,对NAF(kp)与生成的倍点进行点乘,直到运算完成,输出运算结果。
    如图2所示,整个点乘运算阶段分为三部分,分别为标量k的NAF表达式计算,初始预计算,类迭代乘法计算。
    通过对标量k进行重新编码,采用有符号二进制编码来减少二进制编码中的非零元个数,能够有效减少点乘运算中的点加运算次数,达到提升点乘算法效率的目的。
    本发明所提出的k的NAF表达式计算电路,采用有符号编码中的非相邻有符号二进制表示编码NAF,使得k的二进制表示中的非零元素的个数减少,减少点加次数,减少点乘运算步骤,电路运算状态转移图如图3所示。
    具体如下:
    NAF_IDME:k的NAF表达式计算初始化阶段,等待NAF计算启动信号,由所述配置接口??楦?,启动后,进入下一步骤,即NAF_RK;
    NAF_RK:将标量k从存储单元3中从低位开始读出,进入循环加法器进行计算,读操作结束后,进入NAF_K;
    NAF_K:生成NAF(k) = (km-1…k1k0),进入NAF_K2KP;
    NAF_K2KP:进行NAF(k)向NAF(kp)的转换,转换完成后进入NAF_DONE;
    NAF_DONE:k的NAF计算完成,产生运算完成中断,中断被清0后,进入NAF_IDME,等待下一次运算,以响应新的请求。
    计算标量k的 NAF(非邻接形式)表达式的算法1如下:
    输入:k
    输出:NAF(kp)。 
    1. 临时变量c ← k, k的NAF表达式位宽m← 0;向左的箭头表示赋值,即设定一个临时变量c,其初始值是k,而k的NAF表达式的初始位宽为0,m表示k的NAF表示式的位宽。
    2. 当c > 0时,重复执行:
    2.1 如果c % 2 = = 1,则km← 2 ? (c mod 4), c ← c ? km;否则km← 0;“%”表示数学运算“除法运算后取余数”,“==”表示数学运算符“等于”。 
    2.2 c ← c/2, m←m + 1。 “/”表示数学运算“除法运算后取整数”
    3. 生成NAF(k) = (km-1…k1k0)。
    4.  i从m-1到0,重复执行 
    如果 ki == 1 && ki-1 == 0 && ki-2 == -1则kpi= 0, kpi-1=kpi-2= 1,i ← i - 3; 
    否则如果ki == -1 && ki-1 == 0 && ki-2 == 1则kpi= 0, kpi-1=kpi-2= -1,i ← i - 3; 
    否则kpi= ki, i ← i - 1。 
    5. 生成NAF(kp)=( kpm-1…kp1kp0)
    预计算过程如图3所示,对初始点P进行倍点、点加运算,可得到1P、2P … 13P中任意一点,由于可用RAM容量有限,暂存1P、5P、9P、13P点,剩余点则在后续运算过程中动态生成,运算过程状态转移图如图4所示。
    PRE_IDME:预计算过程初始化阶段,等待预计算启动信号,进入PRE_RM。
    PRE_RM:将点P(xp,yp,zp)从存储单元3中读入到存储单元1和存储单元2中,将蒙哥马利乘法辅助算子R,从存储单元4读入到存储单元2中,读操作结束后,进入PRE_DP。
    PRE_DP:对存储单元1中的数据进行倍点运算,运算完成后,判断倍点运算次数信号pre_dp_cnt,若为初次运算,则产生2P点后进入PRE_DPM;若为2次运算,则产生4P点后进入PRE_DPM;若为3次运算,则产生8P点后,进入PRE_MZ2B;若为4次运算,则产生12P点后,进入PRE_MZ2B。pre_dp_cnt进行步长为1的累加。
    PRE_MZ2B:判断倍点运算次数信号pre_dp_cnt与点加运算次数信号pre_ap_cnt。pre_dp_cnt为2次运算同时pre_ap_cnt为初次运算,进入PRE_AP,其它情况则进入PRE_M1P。
    PRE_AP:对存储单元2中的数据进行点加运算,运算完成后,判断点加运算次数信号pre_ap_cnt,若为初次运算,则产生5P点后进入PRE_DPM;若为2次运算,则产生6P点后进入PRE_M6P;若为3次运算,则产生8P点后,进入PRE_CPA;若为4次运算,则产生12P点后,进入PRE_CPA。
    PRE_M1P:将P点从存储单元3中读入到存储单元1,与存储单元2中的xP点进行加法运算,生成P+xP点,运算完成后进入PRE_MZ2B。
    PRE_M6P:将存储单元2中的6P点读入到存储单元1中,准备进行12P点计算,读入完成后,进入PRE_DP。
    PRE_CPA:判断读次数信号pre_rd_cnt,若pre_rd_cnt为0,进入PRE_DPM;若pre_rd_cnt为1,进入PRE_M4P;若pre_rd_cnt为2,则进入PRE_DPM。判断完成后,pre_rd_cnt进行步长为1的累加。
    PRE_DPM:将存储单元2中的结果读入到存储单元3中,读出完成后,判断倍点运算次数信号pre_dp_cnt与点加运算次数信号pre_ap_cnt。pre_dp_cnt为2次运算,同时pre_ap_cnt为初次运算,进入PRE_DP;pre_dp_cnt为3次运算,同时pre_ap_cnt为初次运算,进入PRE_M1P;pre_dp_cnt为3次运算,同时pre_ap_cnt为2次运算,进入PRE_MZ2B;pre_dp_cnt为4次运算,同时pre_ap_cn为4次运算,且pre_rd_cnt为1,进入PRE_CPA;pre_dp_cnt为4次运算,同时pre_ap_cnt为4次运算,且pre_rd_cnt为2进入PRE_DONE。
    PRE_DONE:预计算完成,产生运算完成中断,中断被清0后,进入PRE_IDME,等待下一次运算。
    系统整体算法2如下:
    输入:标量k,每个字所占位宽w,点 P。 
    输出:Q = kP。 
    1. 预计算:
    对 i从 1到 2w-3,计算Pi ← iP。
    2.  Q ← 0。 
    3.  i 从m-1 到0,重复执行 
    3.1 若kpi= 0,则t←1, u←0; 
    否则,寻找一个最大的t≤w使得u←kpi,…, kpi-t+1是奇数。 
    3.2 Q ← 2tQ 
    3.3 若u > 0,则Q ← Q + Pu; 
    否则,若u< 0,则Q ← Q + P-u。
    4.4  i ← i - t。 
    5.  返回Q。
    从上述方案可以看出:
    本方法适用于基数在素域中Jacobian加重射影坐标系下的椭圆曲线公钥密码算法。 为了满足椭圆加密算法性能的要求,采用软硬件协同工作的方式实现椭圆加密算法,将耗时的关键运算用本方法直接实现,其余部分用外部控制器的软件实现。采用本方法,有以下有益效果:
    1、涉及运算全面,可以实现基于模的加法、减法、乘法、取逆、取模、取幂运算;可以实现基于点的加法、乘法运算;同时可以进行RSA相关的基于模的2048位的加法、减法、比较、乘法运算,所有运算接口向外开放,可以通过总线寄存器接口进行配置,灵活性大;
    2、本方法利用了点乘次数k的新的NAF表示方法,使得k的二进制表示中的非零元素的个数减少,所以进行点加运算的次数就会减少,减少了点乘的整体运算时间;
    3、本方法在预计算阶段,采用4点计算法,可保证后续运算点在最短时间内完成,同时又不占用过多的数据存储空间。
    关于倍点的个数,在前述的预计算中有所体现,其数量的多寡跟硬件配置和加密的复杂程度相关,本领域的技术人员据此可进行选择,推荐8~17个,在硬件有更好的配置时,可以选择更多的个数。

    关于本文
    本文标题:椭圆域曲线运算方法和椭圆域曲线运算器.pdf
    链接地址://www.4mum.com.cn/p-6143327.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 360七乐彩基本走势图 欢乐生肖平台哪个好 重庆时时露珠网址 红马计划软件安卓 广东时时快乐十分 快3赚钱投注方法 北京pk10牛逼计划软件 时时彩组六杀三码技巧 河北时时2017 时时彩组三组六一起买怎么稳赚不赔 蛋蛋有大小 双色球最新500期走 体彩足彩投注截止时间 双色球有什么规律和技巧 6码中特2015 七乐彩