Latticesemi 莱迪思半导体

文章数:357 被阅读:87864

账号入驻

知识来了 | ECC椭圆曲线密码学简介

最新更新时间:2021-08-31 13:23
    阅读数:

点击上方蓝字关注“Latticesemi”

1什么是椭圆曲线?

我们在《几何》课本里学过二元一次方程表示直线,二元二次方程表示圆锥曲线(圆,椭圆,双曲线和抛物线),那么二元三次方程表示什么曲线呢?答案自然就是椭圆曲线。为了方便研究,大部分的二元三次方程可以简化成魏尔斯特拉斯方程的形式,见公式(4)。其中,系数a 和b 需要满足条件4a3 + 27b2 ≠ 0,该条件保证方程中不会出现非奇异点以获得平滑的椭圆曲线。 

ax + by + z = 0 (1)

ax2 + by2 + cxy + dx + ey + f = 0 (2)

ax3 + bx2y + cxy2 + dy3 + ex2 + fxy + gy2 + hx + iy + j = 0 (3)

y2 = x3 + ax + b (4)

一个违反直觉的事实是:椭圆曲线的形状跟椭圆毫无关系。当初数学家们在研究如何计算椭圆弧长的时候发现需要求解如下类型的积分, 由于和椭圆相关,积分中的分母项y =√(x3+ax+b) 便被称作椭圆曲线。

下图展示了一些合法的椭圆曲线,

下图展示了两种非法的椭圆曲线,分别存在一个尖点和叉点使曲线不平滑。

2密码学与有限循环群

现代密码学算法和协议中,消息是作为有限空间中的数字或元素来处理的。加密和解密的各种操作必须在消息之间进行变换,以使变换服从有限消息空间内部的封闭性。然而,数的一般运算诸如加减乘除并不满足有限空间内部的封闭性。所以密码算法通常运行于具有某些保持封闭性的代数结构的空间中,这种代数结构就是有限循环群。在数学中,群是一种代数结构,由一个集合以及一个二元运算组成。群必须满足以下四个条件:封闭性,结合律,存在单位元和存在逆元。

最常见的群之一是整数集Z以及加法操作。

有限循环群在群的基础上满足两个额外条件:群元素个数有限以及交换律。循环群由单个元素(产生元)的叠加操作生成,最常见的有限循环群为模拟时钟。

3椭圆曲线群定义

1985年,Neal KoblitzVictor S.Miller分别独立提出利用椭圆曲线产生椭圆曲线循环群用于密码学。在数学上,椭圆曲线群的元素为椭圆曲线上的点,群操作为”+”,”+”的定义为,给定曲线两点PQP+Q等于PQ两点的连线与曲线交点沿X轴的对称点,如果P=Q,则P+P等于P在曲线上的切线与曲线交点沿X轴的对称点。该群的单位元为无穷远零点记作O=(0,0),有P+O=P,点P的逆元为其沿X轴的对称点,记作-P

下图演示了如何计算P+Q=R(P≠Q)。

下图演示了如何计算P+Q=2P=R(P=Q)

下图演示了如何计算P的逆元-P

4椭圆曲线有限循环群

前面介绍的椭圆曲线都是基于有理数的,但是计算机运算浮点数(小数)的速度较慢,更重要的是四舍五入浮点数会产生误差,导致多次加密解密操作后原始消息不能被还原。故考虑到加密算法的可实现性,密码学上使用基于整数的模加运算产生椭圆曲线有限循环群。

本文不涉及具体的数学计算,将用具体的例子展示如何产生ECC有限循环群。例如考虑y2=x3-7x+10(mod 19)的集合,该集合中所有的元素如下图所示。模运算把发散的椭圆曲线映射到19*19的正方形空间中,并且保持了原有曲线的上下对称特性。 

下图展示了y2=x3-7x+10(mod 19)集合中的元素和椭圆曲线的关系。

Q’映射到点Q,点P的对称点也由点-P’映射到点-P

如果取一个更大的质数p进行模运算,集合中的元素点也会相应地增多。下图展示了利用同一个曲线方程进行不同模运算的结果。在实际的椭圆曲线加密算法中,使用长度为192-256位的质数p进行模运算。

现在我们基于y2=x3-7x+10(mod 19),利用产生元P=(2,2)来生成ECC有限循环群。如下图所示。具体的计算使用在线的ECC计算器(链接见参考资料)

G={nP|P=(2,2)}完整的集合为{p=(2,2),2P=(13,8),3P=(1,2),4P=(16,17),5P=(10,3),6P=(18,15),7P=(3,15),8P=(12,1),9P=(9,12),10P=(5,10),11P=(17,15),12P=(7,0),13P=(17,4),14P=(5,9),15P=(9,7),16P=(12,18),17P=(3,4),18P=(18,4),19P=(10,16),20P=(16,2),21P=(1,17),22P=(13,11),23P=(2,17),24P=O=(0,0)}。如下图所示,随着n的连续增加,元素点的分布没有任何特征,这正是密码学需要的特性。

5椭圆曲线离散对数问题ECDLP

请问上图中与点Q相对应的n值为多少?查找集合G={nP|P=(2,2)}中的元素可知答案是Q=(5,10)=10P,但是实际应用中没有现成的集合可供查表。若已知某个点Q,只能用比较原始的方法演算可能的n值,目前可实现的效率最高的算法为Baby-step giant-step算法,计算复杂度为O(√n)。反过来,如果已知n计算n*P则简单的多,因为有限循环群满足结合律,可以使用square and multiply算法,计算复杂度为O(<2log2n)。例如,比特币使用名为secp256k1的标准ECC曲线,n的长度为256位. Baby-step giant-step算法的计算复杂度为O(2128),而square and multiply算法的计算复杂度仅为O(<512)。

用密码学术语描述为:ECC有限循环群构成了一个单向函数Q=nP,已知n,P可以很容易计算Q;反过来已知P,Q则难以计算n.于是(n,Q=n*P )构成了一对私钥和公钥。

举个具体的例子,利用square and multiply 算法计算Q=137P,仅需9步便得到计算结果。

6ECDH基于椭圆曲线的Diffie-Hellman密钥交换

ECC可以用于加密解密,但是由于其算法复杂计算速度慢,故莱迪思iCE40 UltraPlus系列芯片综合使用ECDH算法进行密钥交换,再通过AES进行消息的快速加密/解密助力于IoT通信。故本文以iCE40 UltraPlus芯片的Security IP为例介绍ECDH密钥交换。下图为ECDH密钥交换算法的示意图,iCE40PlusHost分别产生自己的私钥和公钥,然后通过公共网络把公钥分享给对方,再各自使用私钥在本地计算出相同的密钥进行AES加密通信。

由于有限循环群满足交换律,我们可以验证KEYHost=m*n*P=n*m*P=KEYFPGA. 

7总结

相比于RSA和经典DL加密,ECC使用更短的密钥实现更安全的非对称加密。莱迪思首先在低功耗低成本FPGA中实现了ECC密钥交换算法助力于IoT通信。本文简要介绍了ECC的相关知识,希望能对大家在具体实施加密方案的时候提供一定的帮助与指导。

8参考资料

  1. Blog: Andrea Corbellini. Elliptic Curve Cryptography: a gentle introduction. Link: andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

  2. Book: Wenbo Mao. Modern Cryptography: Theory and Practice.

  3. Blog: Certicom. ECC tutorial. Link: www.certicom.com/content/certicom/en/ecc-tutorial.html

  4. Online Tool: Online tool: ECC calculator. Link: christelbach.com/ECCalculator.aspx

  5. Paper: 陆俊,浅说椭圆曲线。

  6. Paper: Mahesh Agarwal. Elliptic Curves do arise from ellipses.

  7. Online Course: Christof Paar. Understanding Cryptography. Link: www.crpto-textbook.com


关注我们还可留言哦~



推荐帖子

关于WDM和Directshow的结合开发,100分重谢!
小弟目前已经开发完saa7130在windows下的驱动,现在准备将其写成硕士论文,前不久交了初稿,被导师痛批,道:没有丝豪创新点!郁闷之至,遂前往eeworld来寻求慰藉。请问各位大侠,能不能将directshow的部分小功能整合到WDM驱动中实现呢,这样是否能在性能方面有所提高? 恳请各位前辈,关于WDM驱动开发如何才能写出有新意的高质量论文,小弟不才,在各大主流的学术论文搜索引擎上,均未发现任何关于WDM驱动开发方面的文章,是不是可以结合微软的最新驱动模型WDF来写呢? 还
asinc 嵌入式系统
适用于 C6748 处理器且支持 TI-RTOS 的处理器 SDK
描述 处理器SDK(软件开发套件)是统一的软件平台,适用于TI嵌入式处理器,设置简单,提供开箱即用的基准测试和演示。处理器SDK的所有版本在TI的广泛产品系列中保持一致,让开发人员可以无缝地在多种器件之间重用和迁移软件。处理器SDK和TI的嵌入式处理器解决方案让可扩展平台解决方案的开发变得前所未有地简单。适用于C6748、C6746和C6742的处理器SDK包括TI-RTOS操作系统的各种支持。RTOS亮点:TI-RTOS内核,一种用于TI器
灞波儿奔 DSP 与 ARM 处理器
基于zigbee多点大气温湿度采集系统
大神们啊小弟要毕业了,但是要做毕业设计啊!!选的是zigbee,但是我都没有接触过啊这两天看了一下毫无头绪啊哎求大神们做过基于zigbee多点大气温湿度采集系统相关的设计可以给我发一些资料吗??小弟在此跪谢了!!!!我用的是cc2530芯片和dht11温湿度采集传感器。。。。。。。谢谢大神们了!好人一生平安!!!基于zigbee多点大气温湿度采集系统
夜星 RF/无线
最新资讯分享,MOTO XT883使用的TI的芯片
2011年9月2日摩托罗拉在北京中关村贝塔咖啡举办了——新里程碑摩托罗拉XT883体验会,作为里程碑系列的最新成员摩托罗拉XT883装备了德州仪器OMAP44301GHz双核处理器芯片。这颗芯片不仅拥有强劲的通用数据处理能力,同时它的浮点运算性能(图形、多媒体处理能力)也非常出色,这主要都归功于该芯片内的PowerVRSGX540图形核心。 可以了解一下此芯片的相关技术呵呵~~最新资讯分享,MOTOXT883使用的TI的芯片
Laura_luck DSP 与 ARM 处理器

最新有关Latticesemi 莱迪思半导体的文章

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: TI培训

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2021 EEWORLD.com.cn, Inc. All rights reserved