基于FPGA的椭圆曲线加密设计

2019-01-17 10:30:54 来源:网络
标签:

摘 要: 椭圆曲线加密是一种目前已知的所有公钥密码体制中能够提供最高比特强度的一种公钥体制。在FPGA实现椭圆曲线加密系统时,基于GF(2)的多项式有限域中的乘法、求逆运算是其中的两大难点。本文提供了一种椭圆曲线加密的FPGA实现的结构,着重讨论了基于GF(2)的多项式有限域中的乘法、求逆运算的实现,并与软件实现的性能进行了比较。

 

加密的安全性
从数论的角度来说,任何公钥密码系统都建立在一个NP(无法处理的问题)的基础上,即对于特定的问题,没有办法找到一个多项式时间算法求解该问题。一般求解此类问题的算法都是指数时间或者亚指数时间,例如现在常用的RSA算法就是基于大整数因式分解问题的难解性。经过近三十多年的研究,RSA算法虽然并不存在多项式时间的算法,但是可以找到亚指数时间的算法,目前其密钥长度必须大于1024位才能保证信息传递的安全,而椭圆曲线加密系统 (EllipTIc Curve Cryptosystem—ECC) 是目前已知的所有公钥密码体制中能够提供最高比特强度 (Strength-Per-Bit) 的一种公钥体制,只需要160的密钥就可以达到1024位RSA算法提供的安全等级。其根据是有限域上的椭圆曲线上的点群中的离散对数问题(ECDLP),许多密码专家认为它是指数级的难度。因此对于椭圆曲线加密系统来说,这一点从计算量、处理速度、存储空间和通信带宽等角度分析,椭圆曲线加密系统都有很大的优势。IEEE已经制定的公钥加密算法标准P1363就是基于ECC算法的。现在密码学界普遍认为它将替代RSA成为通用的公钥密码算法,目前已成为研究的热点,是很有前途的研究方向。

 

图1 点算法实现

 


图2 密钥、数据交换

 


图3 椭圆曲线加密系统结构图

 


图4 椭圆曲线加密系统FPGA电路模块框图

 


图5 验证系统结构

 

椭圆曲线加密体制
椭圆曲线

引进Non-supersingular椭圆曲线Weierstrass方程E:Y2+XY=X3+aX2+c其中a,c∈GF(2k),c≠0。为简化以后的运算,引进z使X=x/z;Y=y/z,则椭圆曲线方程化为E:y2z+xyz=x3+ax2z+cz3,定义(x, y, z)=λ(x, y, z)。可以看出当z≠0,(X, Y)和(x, y, z)相对应,当z=0可以理解为沿y轴趋向无穷远,定义为无穷远点O。则椭圆曲线上所有的点外加无穷远点构成的集合构成一个Abel群,O是单位元(零元)。在椭圆曲线E上定义了两种点运算:点运算和点运算。


1) 椭圆曲线上点运算定义为:设P=( x1, y1, 1)∈E,Q=( x2, y2, 1) ∈E,-P=( x1, y1+ x1, 1), 当Q≠-P时 PQ=(x3, y3, z3) 则
当P≠Q时:
其中A=(x2z1+x1),B=(y2z1+y1), C=A+B,D=A2(A+a2z1)z1BC
当P=Q时:
其中


2) 椭圆曲线上的点运算定义为:设P=(x1, y1, 1)∈E,(ltlt-1...l0)2是整数l的二进制表示形式,lP=PPAP=Q且Q∈E。


利用上面的点运算,得点算法实现如图1所示。定义l=logpQ,若P的周期很大,则利用l、P求Q是比较容易的,但利用P、Q求l是很难处理的,这就是ECDLP,椭圆曲线加密就是建立在这个难题之上。


加密体制
在Diffe-Hellman公钥系统体制中,具体的椭圆曲线、曲线上点P及P的周期大素数N都是公开信息。
A和B要进行通讯,首先得到椭圆曲线E、点P及素数N。然后用户A将[1,N-1]中随机选取的整数a作为私钥,A将KpubA=aP作为自己的公钥传送给用户B,与此同时B将 [1,N-1]中随机选取的整数b作为私钥,并将KpubB=bP作为自己的公钥传送给A。A、B各自将自己的私钥点乘于对方传过来的公钥得到KAB,这样就完成了密钥的交换过程。当用户A需要将待传数据m传送给用户B时,A利用m和KAB生成Em,当用户B得到Em后,利用密钥交换过程自己生成的KAB和从用户A处得到的加密数据Em生成数据m。见图2。

 

椭圆加密体制实现
迄今所投入使用的椭圆加密系统中,绝大部分的密钥长度都比较短,一般集中在30~60位,这是因为在软件实现时,由于软件执行速率所限,密钥长度比较大(≥160)的椭圆加密系统的速率将达不到使用要求。与此同时,在硬件实现时,密钥长度比较大的椭圆加密系统将耗费大量的硬件资源。随着椭圆加密算法研究的深入和可编程逻辑器件的快速发展,利用可编程逻辑器件实现椭圆加密系统已经是一个可能的选择,下面将介绍一种实现方案,并且用软、硬件分别实现。


根据以上椭圆加密体制的要求,设计出图3的加密系统结构图,其中椭圆加密系统参数接口获取与加密有关的椭圆的基本参数,如私钥、椭圆曲线、椭圆曲线上的给定点等。椭圆曲线乘法控制部分主要负责如何计算乘法结果,会大量调用PP和PQ来实现乘法功能;而PP和PQ通过有限域加法、乘法和求逆的调用得到结果。


软件模型验证
软件实现的主要目的是为硬件实现建立验证模型,整个软件的结构如图3所示。在软件验证系统实现的过程中,有限域上的加法是异或操作。有限域上的乘法和求逆是关键点,必须预先考虑到硬件实现时的资源消耗,需要高效的算法。在此系统中使用了复合域GF((2n)m)带来的特殊性,可以高效、快速的实现乘法和求逆运算。


* GF(2n)上的乘法:A(y)&TImes;B(y)=C(Y)modQ(y),Q(y)为既约多项式。常用的有: Paar-Rosner乘法器、Mastrovito乘法器、Massey-Omura乘法器、Hasan-Bhargava乘法器等,此处介绍两种选择:
1) 当n比较小时可用查表法实现,设ω为Q(y)=0的本原根,则F2n={0,ω,Aω2n-1},利用查表法取得A、B的级次数a、b,C的级次c=a+b,再次利用查表法由c得C。在本系统中就使用了此法实现GF(2n)上的乘法。
2) 当n比较大时,利用查表法资源消耗太大,难以承受,可利用C=Z&TImes;B(n比较大时),Z是由A(y),Q(y)确定的矩阵,其中:

 

* 复合有限域的乘法:以GF((24)2)为例,利用GF(24)上的乘法和加法可以构造出GF(28)的乘法。子域GF(24)的本原多项式为Q(y)=y4+y+1,第二个子域的本原多项式为R(z)=z3+z+ω14,其中ω是GF(24)的基底元素,满足Q(ω)=0。域中两个元素的乘法[a0+a1z]&TImes;[b0+b1z]可以表示为:

 

这样GF((24)2)在复合域上的乘法就可以通过GF(24)上的有限域的数学运算而得到。
* 复合有限域的逆运算:复合有限域GF((2n)m)中的元素A的逆为:

 
关注与非网微信 ( ee-focus )
限量版产业观察、行业动态、技术大餐每日推荐
享受快时代的精品慢阅读
 

 

继续阅读
【技术分享】英特尔10纳米Agilex FPGA核心技术全解读

英特尔的10纳米FPGA终于来了。在四月刚刚结束的英特尔“以数据为中心创新日”中,曾经代号为Falcon Mesa的英特尔最新一代10纳米FPGA正式亮相,并正式命名为Agilex™。

【技术分享】针对FPGA的GTP信号,PCB设计时应考虑的信号完整性问题

千兆位级串行I/O技术有着极其出色的优越性能,但这些优越的性能是需要条件来保证的,即优秀的信号完整性。例如,有个供应商报告说,他们第一次试图将高速、千兆位级串行设计用于某种特定应用时,失败率为90%。

FPGA业务仅占营收的3%却成为10nm工艺第一批受益者,英特尔是怎么想的?
FPGA业务仅占营收的3%却成为10nm工艺第一批受益者,英特尔是怎么想的?

和过去几代产品相比,AMD近期推出的产品给了英特尔更为激烈的竞争压力,这将帮助AMD逐步超越英特尔;近几年来,英特尔一直深陷制造工艺升级泥潭,它最近发布的10纳米 FPGA表明它的10纳米工艺还有一些尚未得到解决的问题;AMD很有可能重现二十年前的辉煌,再次夺得CPU性能的铁王座。

【技术分享】使用EPROM或EEPROM配置FPGA大家都会,使用NOR闪存呢?

NOR闪存已作为FPGA(现场可编程门列阵)的配置器件被广泛部署。其为FPGA带来的低延迟和高数据吞吐量特性使得FPGA在工业、通信和汽车ADAS(高级驾驶辅助系统)等应用中得到广泛采用。汽车场景中摄像头系统的快速启动时间要求就是很好的一个例子——车辆启动后后视图像在仪表板显示屏上的显示速度是最为突出的设计挑战。

【技术分享】详解FPGA中的DDS技术

我知道,我对与电子有关的所有事情都很着迷,但不论从哪个角度看,今天的现场可编程门阵列(FPGA),都显得“鹤立鸡群”,真是非常棒的器件。如果在这个智能时代,在这个领域,想拥有一技之长的你还没有关注FPGA,那么世界将抛弃你,时代将抛弃你。

更多资讯
高云半导体研讨会圆满召开,累计出货已达1500万片

2019年4月12日,中国武汉,高云半导体FPGA技术研讨会系列活动于武汉凯悦酒店成功召开,现场气氛热烈,座无虚席。

高云半导体研讨会圆满召开,累计出货已达1500万

2019年4月12日,中国武汉,高云半导体FPGA技术研讨会系列活动于武汉凯悦酒店成功召开,现场气氛热烈,座无虚席。

【技术分享】FPGA越来越精密,对DC-DC电源的精度也越来越高

FPGA厂商不断采用更先进的工艺来降低器件功耗,提高性能,同时FPGA对供电电源的精度要求也越加苛刻,电压必须维持在非常严格的容限内,如果供电电压范围超出了规范的要求,就有会影响到FPGA的可靠性,甚至导致FPGA失效。

【技术分享】详解迭代开发FPGA的思想,FPGA增量编译使用教程

FPGA设计的特点是需要不断不断的迭代各个设计流程来达到最终的设计,同时迭代的成本大,它比单片机开发更注重迭代的开发思想。所以,设计的前期一定要从系统的角度考虑好系统的方案,然后在系统这个方案中不断的迭代,不然后期发现由于系统方案的问题就得不偿失了,好的系统架构就是成功一大半了。其中,在FPGA设计中可以通过增量编译来加快我们的开发。

【技术分享】CRT/OLED/LCD等视频显示系统控制原理分析

作为消费者,我们对于各种形式的视频系统都已经非常熟悉了。但是从嵌入式开发人员的角度来看,视频就好像是一张纷繁复杂的网络,里面充满了各种不同的分辨率、格式、标准与显示等。

Moore8直播课堂
开发板测评
技术讨论
电路方案

1970-01-01 08:00:00