斐波那契数列在标量乘法中的应用

技术与应用

斐波那契数列在标量乘法中的应用

李磊

0引

诞生了。此时只要不改变椭圆曲线方程和基础点P,任意改变标

Kobilitz和Millier:建议将椭圆曲线用于公钥加密体系的乘法系数k的规模,这个系数k的确定,能够借助预先保存的斐波那契数列来完成

自中叶起，椭圆在众多领域得到日益广泛的应用，这得益于其能显著降低运算的繁复程度。

曲线具有高比特的安全性,所以在资源有限的环境中更能得到广

1.2算法实现步骤简介

泛的应用,例如应用在智能卡和嵌入式设备中。

(1)先确定椭圆曲线方程和基点P。因为斐波那契算法是使

椭圆曲线计算中的一个很重要的操作就是点的标量乘法运

用了一个被称为斐波那契数库的结构,它局限于在同一条椭圆曲

算,例如计算kP,其中k是标量,P是椭圆曲线上的任意一点

线上的制定点P下执行。改变椭圆曲线任意一个系数或者改变基

标量乘法包括两个层雨上的操作:一个是椭圆曲线上点的基本操

点P都会产生个新的斐波那契数库

作,如点的倍加,二倍加和三倍加等;二是域上的操作,开发快

(2)生成斐波那契数库。给定曲线方程和基点P后会有唯一

速模块化的乘法和求逆算法等。人们提出了各种各样的算法用以

个斐波那契数库与之对应,系统会根据指令自动生成该数库并

提高椭圆曲线加密系统的效率。

保存。

日前计算标量乘法的方法有许多,例如二进制展开法、带符

3)输入系数k。系数k的值是可以任意输入的,因为只要

号的二进制法、m进制法以及利用复乘的GLV法等等。

k为正整数,都可以分解为若干个斐波郝契数之和。

SPA攻击是种有效地攻击方式,它通过对不同操作的功耗

(4)分解系数k。原理见斐波那契数列性质2,为方便程序

研究以获取涉及核心的资讯,针对加密活动里的各类步骤,在执行层面,我们运用了这种划分方法:首要是选取不大于量值ん的最值

能量使用模式能呈现多种形态,恶意攻击者借助各类斐波那契数值k,计算k减去k,再从中选取不超过k的最大斐波那契数

通过分析能量消耗的差异来提取有效数据,为了有效抵御侧信道攻击,应该首先确定k2的值,接着令m2等于m减去k2,然后继续这个步骤,直到m变为零,这样就可以

的办法就是将标量乘法中的操作尽可能的转化成同类型的操作

得到k对应的斐波那契加法链k,k2,ky…k。

例如将乘法转化为一系列的加法运算,这样就会使得功耗变化不

(5)在斐波那契数库中査找系数k分解后对应的项。由丁斐

再明显

斐波那契数列是这样一个数列“1,1,2,3,5“它存在这样

波那契数是固定的一组数,因此步骤(4)中分解得到的一组斐

个性质,即任意一个正整数都可以表示为若干个斐波那契数之

波邶契数群,包括k2,ky等k值,肯定存储于数据库里,采用对照方式能够十分便捷地

和。利用这一性质,我们可叮以把斐波那契数列运用到椭圆曲线标

容易的提取出相应的项。

量乘法的计算中来,通过对系数k的有效变化使kP的运算转化

(6)计算kP。通过步骤(5)的比对和提取,在使用次简

为加法运算(斐波那契法),这样就可以有效预防SPA攻击了。

单的点加法就可以还原最初的标量乘法kP

液那契数列的引入

2功能块实现

新的标量乘法的核心部分就是斐波那契数列的引入,由于任

2.1斐波那契数列和斐波那契数库的实现

意一个大整数都可以表示成斐波那契数列中若干项之和,所以对

(1)斐波那契数列( Fibonacci. m)程序

于大系数的分解有着重要的意义。

斐波那契数列有着非常利于程序实现的推导公式:

例如对于任意大整数14235,我们可以表示成

Fn)=F(v-1+F(n-2),m23

14235=10946+2584+610+895+1

下面就是斐波那契数列的源程序的编写了。因为斐波那契数

假如有一个斐波那契数列清单开元棋官方正版下载开yunapp体育官网入口下载手机版开yun体育app入口登录，很容易识别出10946、2584、610这些数值

列是这样一个数列112358

,它满足第一位和第二位都是

89, 5, 1均属于斐波那契数列,该数列具备特定的规律,按照第n项等于前两项之和的规则生成,第n项的值等于第n-1项与第n-2项之和,这一特点在设计过程中需要被考虑进去

性质,因此能够将其纳入标量运算范畴内,将kP改写成多个步骤时,由于是以函数文件方式存储,所以开头必须先使用 function

项之和,即

创建一个名为a-fb的函数，这个函数接收一个参数n，它指定了要构建一个fb函数，这个fb函数的作用是

kP=k,P+k2P+k3P+…,k为斐波那契数

实现的斐波那契数列函数,其中a是一个变量,就表示fb函数,

在上述公式里,若已知等式右侧各项的具体数值,那么P仅是为了方便后续程序设计而设定的符号:n代表fhb序列的项数

也就不难算出了,那么问题来了,怎么能够事先知道k1P的值

情况一,当n等于1时,需要特别指出,情况二,当n等于2时,也必须分开来讲,就是说,如果n

elseif n==2,a-

:当n>2时,就要开始用递推

关系了,可以假设b=fhb,那么a就应该是数列b再加上最

1.1斐波那契数库的使用

为了便于探讨新的标量乘法方法，我们借助椭圆曲线公式来体现梅1加上b，其中b代表最终那个值，通过这种方式，整个函数的构成得以展现

圆曲线,即

棍序就编辑完成,如图1所示:

y2=x2+ax+b,其中,b∈K

(2)

实际上这是一种简化了的椭圆曲线表示形式,这既有助于新

求基液那契序列

function f=Fibonacci(n

算法的程序实现而又不失一般椭圆曲线的性师。后,椭圆曲线

从以上表达式中可以看出,当系数a,b确

f(1)=1:f(2

的一般形式也随之确定,如果再给出点P,则可以构造这样一组

数据;

f(i)=f(1-2)+f(i-1)

P,P,2P,3P,5P8P…kP…,其中ん为斐波那契数

确定了椭圆曲线方程和点P,我们很容易根据椭圆曲线上点

图1斐波那契数列源码

的加法运算来求出2P,再由斐波那契数列的递推公式

(2)斐波那契数库( Fibonacci-Eccm)的建立

通过运用公式F(n)等于F(n-1)加上F(n-2)，能够较为便捷地计算出后续各项的值

这里所说的斐波那契数库实际上就是系数为斐波那契数的

相应的数值。这样,针对特定方程中某一点P,其斐波那契数列的对应值就构成了一个标量乘法数值集合,例如P,P,2P,3P,5P,8P等等,之所以需要构建这样一套

万方数据