基于MSP430 微控制器的在感应器网络上.doc

基于MSP430 微控制器的在感应器网络上通过软件执行以成对为基础的的密码系统摘要: 由于平台的有限的能力，密码计划的软件实施为无线传感器网络形成了一个挑战。然而，它的可行性已被证明在最近的论文上。在这项工作中，我们描述了用于MSP430微控制器的成对基础的加密技术和椭圆曲线加密软件实现。这种软件执行在Tmote Sky和TelosB一些无线传感器中有所使用。随着ECDSA的计划，我们在新的领域里实现了对MNT和BN曲线的配对计算。这个工作的主要成果是对乘法和减法程序特定平台的优化，使得在乘法领域与已经公布的被人熟知的计时器相比，速度有了28%的提升。这种优化从而提高了双配对和点乘计算的速度。关键词：配对密码，无线感应器网络，软件实现。1. 引言由于无线传感器网络（WSN）应用于大量问题，使其最近成为被研究的对象。他们带来的挑战之一就是如何保护自己防止窃听或恶意操纵的沟通。这些可以通过多种加密方案解决；但由于这些节点是极为有限的环境，这些方案必须有效地实现。在无线传感器网络非对称加密对称的优势很好的建立在文献基础上。出于这个原因，我们选择了实现两种非对称密码系统类型：配对的和椭圆曲线密码。正在考虑的安全水平是64/70-bit，是最可行的，并且至存在大部分的工作重点，以及128位，这可能很昂贵，但这是未来数年的发展趋势，而且同时还未探讨无线传感器网络。这项工作的主要贡献是特定于平台的优化，以改善这两个不同的安全级别的密码系统的计算和计时两种速度。这项工作的其余部分组织如下。在第二节，我们介绍一下MSP430微控制器，描述它的特点和局限性。随后，在第3节，对乘法和减法的基本操作进行描述，以及我们提出的优化。配对密码的执行和结果会在第4节有所描述。在第5节会详细介绍椭圆曲线加密的执行和结果。最后，这个文件的结论在第6节。2. MSP430微控制器来自德州仪器公司的MSP430是一种主要用于低功耗已知的16位微控制器系列，并且应用在无线感应器上，例如Moteiv 的Tmote Sky和Crossbow的TelosB。它具有12个通用寄存器和指令集，包括一个27位的唯一一个变化和字节交换。内存（字节，字），同时可以通过四种地址处理方式：寄存器直接访问，寄存器（带有偏移字），寄存器间接访问和寄存器后增间接访问。目的操作数可以是只处理寄存器直接和索引模式。每个指令可以由多达三个字节表示（一个用于指令和两个偏移字）。除了少数例外，它是相对简单的计算每个指令周期数：一种是每个指令字，加上一个每次读内存和两个每次写内存。短立即数（-1，0，1，2，4和8）可以被编码不使用两个字（例如将一个寄存器赋值零到“NAVIE WAY”将0存入只需一个周期）。不过，有一个与指令集的关键问题：它缺乏同时乘法和除法。在一些MSP430型号上已经部分解决了硬件乘法器问题。这是一个内存映射的外围设备支持四种操作：乘法，有符号数乘法，乘法和累加以及有符号数乘法和累加。为了使用他们，有必要将第一个操作数写入四个具体地址中的一个里。（MPY，MPYS，MAC，MACS；各自的）根据将进行的操作。然后，第二个操作数可以被写入到另一个具体地址（OP2）和双精度的结果将在延迟两个周期后在两个地址里（RESLO，RESHI）得到。乘法和累加操作将加法标志位置1后存入到另一个地址（SUMEXT）。硬件乘法器的一个重要后果是，它意味着一个不同寻常的开销，因为操作数必须从内存中写入和读取。此外，也没有除法指令，因此必须在软件执行，这是相当昂贵了。当给算法计时，我们测量了由程序执行所需要的周期数。假定8,000,000 Hz的时钟，以秒或毫秒计时计算；确切的最大时钟在不同的MSP430系列设备上是不同的。出于这个原因，建议通过周期数比较其运行时间。我们使用O2优化的3.2.3 版MSPGCC编译，除非另有说明。3. 乘法和减法对IFp进行乘法大约是点乘和配对计算运行时间总和的75%。因此，关键是要实现它使用汇编语言。根据我们的实验这可以将速度提升两倍。在IFp进行乘法包括两个操作：操作数的普通乘法到双精度数和一个素数模随后减少。1233.1 乘法相乘标准算法是Comba方法1，这是一个从标准教科书版本的行优先变化过来的列优先方法，可以减少内存访问。最近，它已提出了变体的Comba方法，混合方法2，即行优先和列优先混合的技术。它可以被看作是普通的Comba方法，与每个“数字”现在是整数存储在多个机器有着差异，和数字位数进行乘法与逐行教科书技术了。这两种方法如图1所示。图1相乘的计算方法的比较：Comba法左，混合法右混合方法的优点是，在一个数与数相乘时，对所有整数的第一个数字都可以存储在寄存器中，以减少内存读取。因此，这一方法适合于有较大的寄存器数量的平台。在3中，作者提出了一种混合的方法，更加优化的版本，使用顺序结转捕手寄存器来简化其进行处理。他们还研究了它在许多平台上，包括MSP430的，相比之下，他们在那里能够获得15.4的速度提升，Comba方法的应用。看来，当提供足够的寄存器时，混合方法总是优于普通的Comba方法，但是这没有考虑到该平台的特点。分析Comba方法的运行时间，可以肯定的是，大部分时间都花费在重复步骤一：乘法和累加。对于每个结果列，有必要计算它们的许多结果和累加和，以获得该列的结果和未来两列进行。该乘法和累加的步骤（我们将称之为“MulAcc”）的重要性，指出以前在2.4。然而，到目前为止，已被忽视的事实是， MulAcc正是由MAC（乘法和累加）的MSP430的硬件乘法器操作提供。该MulAcc步骤如图2所示。图2该MulAcc步骤，例如使用的单词作为A1和B2的一步。 R14和R15的寄存器指针举行的两个4字操作数它包括两个整数的读取，每一个来自各自的操作数，他们的乘积随后存为一个双精度整数，最后是这两个整数的和放入三重精度累加器（第三个只增加那些进行的累加和）。对于不使用MAC是在算法1中列出和使用算法2的MAC MulAcc一步伪汇编代码。相对于算法1，算法2有两个指令少，共节省四个周期又少了一个存储器的少了一个延伸字地址。这就带来了一个很大的加速，因为MulAcc一步是反复大小为n的机器操作数大小n2倍。 算法1：普通MulAcc步骤 算法2： MulAcc步骤使用MAC与混合方法相比，使用MAC的普通Comba的主要优点是，后者使用了所有12个可用的寄存器，而前者的叶子8个免费寄存器。这些可以作为一个简单的操作数缓存。此外，一个寄存器可以用来保存了SUMEXT地址以添加使用寄存器间接访问模式，而不是对寄存器的索引，保存在每个MulAcc多步循环（这需要，因为否则SUMEXT被取出一个指令重新排序前的硬件乘法器）两个周期的延时。表1比较了我们的执行指令以及3里的内容。可以很容易地看到，最大节省的加指令数量较少来，由于硬件乘法器是通过本身的增加最多。同样的，一个周期可以被保存在每个步骤由于第一个操作数，寻址方式，可以用用后递增的寄存器间接读访问（MOV reg+，label）的线性关系。表1。 160位乘法指令计数的比较乘法计时表2，其中明确指出，Comba乘法器是使用MAC优化乘数详细确实是有效的，和3所示的混合乘数器相比快9.2。我们发现，使用了128位Comba乘数器的Karatsuba乘法是比使用256位的Comba快一点，同时也需要更少的代码空间。 表2。时序乘法和平方3.2 减法传统的模块化减法是昂贵的操作，因为它需要昂贵的分歧。由于MSP430没有完整的除法指令，他们将需要在软件计算，这将是更加高昂。我们在文献中选择了不再需要两个分支的算法：Montgomery减法6和Barrett减法7。Montgomery减法需要将操作数被转变为一个特殊的Montgomery形式。这通常不是一个问题，因为我们可以用“官方”的所有数字的表示的Montgomery形式在加密协议中的使用，他们将只需要改回，比如：要打印在屏幕上供人阅读。Montgomery减法还需要预先计算的常量，它是机器的整数大小所依赖的。Montgomery减法算法具有几乎与Comba乘法相同的结构，将第一个操作数作为双精度数下部相减，第二个操作数作为首要模量。因此，可以采用相同的MAC优化，加快减法过程。Barrett减法是稍微复杂，它涉及到一半的精度Comba乘法。这些也都可以利用乘法的MAC优化。它还需要预先计算的常数模量是首要的依赖。当首要模量具有一种特殊形式，也有一些减法的具体算法。对于素数的形式2K- C的，如从SECG标准的160位素数8，该算法是在9中描述。对于“NIST的质数”10，该算法的描述11。减法计时列于表3。从5减法计时，估计减去从5中提及的乘法时间而在3中记录的乘法时间。虽然确切的比较可能会很难做出估计，由于这种不精确，我们注意到，MAC再次优化是非常有效的。Barrett减法慢于Montgomery减法，但由于我们侧重优化Montgomery，我们认为，它的速度可以得到进一步改善。正如所料，减法模是一种特殊形式快得多。表3。减法计时最后，乘法-乘法后跟减法的算法的运行时间-列于表4。相比于5，使用MAC乘法领域快了约28。表4。乘法领域的计时（使用Montgomery减法）4. 基于加密使用配对的身份最近，它已被证明是基于身份的加密使用双线性配对在无线传感器网络方案12中是非常适合的。有许多基于身份的加密方案，但在这方面可能是最有用的非交互式密钥协商方案13,14,15，允许双方的计算，以一个无相互作用的相互键启动一个安全通道使用对称加密，并将如接下来所描述的。设e : G1 G2 GT 是一个双线性配对和G1和G2添加组和一个乘法组GT，他们全都是素数命令r。让H1：0，1 *G1和H2：0，1 *G2是两个哈希函数。主密钥的生成是由密钥生成中心，选择一个随机数s1，.，的r - 1。私人密钥分配前完成部署的传感器通过分配一个传感器A的身份IDA和私钥S1A=SH1（IDA）和S2A = SH2（IDA）。现在，假设A和B传感器希望计算一个共享密钥。如果G1和G2是同一组和配对是对称的，那么这两个散列函数将是相同的，每个节点的两个私人密码匙将是相等的。因此，A可以计算e（S1A，H1（IDB）和B可以计算e（H1（IDA），S1B）。由于双线性和对称性，我们有：然后，双方可以生成相同的值，它可以被用来推导出一个共享密钥。在我们的例子，虽然配对是不对称的，因为使用的是普通的椭圆曲线。因此，我们需要为每个传感器两个私有密钥，散列函数是不同的，而在方程式的最后一步是无效的。尽管如此，我们有两个有用的方程，可以很容易地验证：e（S1A，H2（IDB）= e（H1（IDA），S2B）和e（H1（IDB），S2A）= e（S1B，H2（IDA）。在14中建议每一缔约方应乘这两个方程的两侧，以计算共享密钥，但是这需要两个配对计算。在 5建议传感器可以商定的公式，他们应使用少量的通信。相反，还有一个更简单修复，它维护了协议非交互方面。它可以定义在与使用较小的ID的传感器字典顺序应该第一次在第一私钥配对参数和其他其第二参数在第二个配对的私钥，因此选择无任何交互的方程之一。44.1 160-Bit领域的MNT曲线对于160位的领域，我们已经实现了两个安全级别。为了让比较，第一个同5中描述的一样使用嵌入4度MNT曲线。在上述地点选择在以提供最低限度可接受的安全参数; 640位扩展领域中使用的安全性提供了大约64位16。笔者选择了Tate配对，而不是较快的Ate，因为在G2散列一个身份到一个点是比Tate配对简单。Miller循环的实现使用与W = 3的滑动窗口技术。所选定的安全第二级遵循类似的实现，但使用与嵌入度为6的MNT曲线。在960位扩展领域，提供了大约70个安全位17这样的结果。各自领域的操作和配对有限时序详细计算表5，这表明MAC优化导致了在64位水平有20.2的速度提升。这是很重要的说法，在5中，作者选择了关闭编译优化其代码;理由是，在速度上的差异采用不同的编译器取得十分显着优化，使用时，将作出任何比较困难。尽管如此，我们觉得提供的优化版本计时，会导致更多有趣的对比。表5。Field操作时间和在MNT曲线中的配对计算12344.14.2 256位字段上的BN曲线对于128位的安全级别，我们选择 Barreto-Naehrig族曲线18。他们有一个内嵌12度，并提供一个允许增加一倍嵌入六次扭曲并在IFp2之上的曲线上增加了米勒的算法，而不是昂贵的IFp12。曲线选择的是由x值产生的，0x4080000000000001 在19提出。至于BN的公式，可以发现在文献上有不同的值p（x）：原始文件18使用p（x）= 36x4 +36 x3 +24 x2+6x +1中，但其他一些文献19,20中使用p（x）= 36x4 - 36x3 +24 x2 6x+1，当使用倒想的x时，可以得到相同的值。我们使用的原始版本。我们选的搭配是Optimal Ate21， R-ate 22和Xate 19；所有这些最佳配对，在定义在21中。他们提供截断了四分之一米勒循环的最佳速度。我们按照20详细的方法，但使用23最后幂优化。由于米勒循环通过6x+2位（或x在Xate），它具有低Hamming重量运行时，滑动窗口技术是不恰当的病并且没有使用过。我们目前得出有限段操作时间，并在表6配对计算。配对计算在MNT曲线中是要昂贵（expensive）得多，并可能无法接受无线传感器scenario。正如在24指出的那样，重要的是要记住，配对计算尺度或多或少像RSA，而不像椭圆曲线加密。这也是值得注意的是这三种配对几乎是相同的速度，而Xate配对要快一点。我们在算法3中描述了BN曲线的Xate配对。配对的计算程序ROM和RAM的要求列于表7。要正确地看待他们，我们注意到，流行传感器，如Tmote Sky和TelosB都具有48KB的ROM和10K 的RAM。该代码规模仍然较大，虽然它是唯一可能的分析来确定特定应用的可行性。已分配的内存量可能是容忍的，因为其中大部分是从堆栈中分配和释放后计算。算法3。 对BN曲线的Xate配对表6。为段操作计时和有关在BN曲线上的配对计算表7。 ROM和为配对方案分配的最大RAM 5 椭圆曲线密码虽然与配对计划建基于身份的无线传感器似乎理想的情况下，他们仍然是昂贵的，主要表现在高128位的安全级别。出于这个原因，我们还实施了更便宜的椭圆曲线密码，以便与配对的密码体制的比较。为了说明具体的使用，