资源描述：
《基于多处理器构造安全椭圆曲线的并行化设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于多处理器构造安全椭圆曲线的并行化设计与实现安全椭圆曲线是椭圆曲线密码体制理论研究与实际应用的前提和根本，本文通过分析GF(p)上构造安全椭圆曲线的算法与一种奇素数域构造给定长度的素数阶的椭圆曲线算法，将两种算法适合并行化的部分进行并行化处理，并设计了基于多处理器的构造安全椭圆曲线的并行化模型，进而实现加快构造安全椭圆曲线的速度。关键词：构造椭圆曲线；多处理器模型；并行算法；设计与实现中图分类号：TP302文献标识码：A：1.前言 安全椭圆曲线是ECC理论研究与实际应用的前提和基础，如果椭圆曲线不安全，那么ECC中的各种快速算法的研究、密码体制的研究
2、与在实践中的应用都是空想。ECC的安全性取决于有限域上椭圆曲线离散对数的难解性。所谓构造安全椭圆曲线，就是通过选择并确定椭圆曲线的参数和密钥，使椭圆曲线能抵御目前的所有攻击。 构造有限域上安全椭圆曲线的方法一般有两种：随机曲线法(SchoofElkiesAtkin,SEA)和复乘法（plexMultiplication,CM）。SEA法是通用的方法，它可以构造出许多安全椭圆曲线，但实现起来复杂。CM法相对比较简单，实现速度也比较快，但这种方法找出的椭圆曲线含有复乘，可能存在安全隐患。本文通过分析文献[3]中GF(p)上构造安全椭圆曲线的算法与文献[4]
3、中一种奇素数域构造给定长度的素数阶的椭圆曲线算法，分别将适合并行化的部分进行并行化处理以加快构造安全椭圆曲线的速度。2.GF(p)上构造安全椭圆曲线的算法分析与并行模型架构设计 文献[32]中提出GF(p)上构造安全椭圆曲线的算法描述如下： 输入：有限域的大小p>3 输出：椭圆曲线E(a,b)、#E(a,b)=kh,k是大的素因子、且 算法步骤： Step1：随机产生GF(p)上的一条椭圆曲线E(a,b)：； Step2：利用SEA算法计算出#E(a,b)；Step3：利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解中有
4、无大于的素因子k，如果没有，返回Step1； Step4：检测，否则返回Step1； Step5：检测。否则返回Step1； Step6：输出a、b、#E(a,b)、k、h＝#E(a,b)/k。 上面算法利用SEA算法计算出#E(a,b)后，执行Step3、Step4与Step5的主要目的是得到有效的a、b、#E(a,b)、k、h＝#E(a,b)/k，由于此算法是串行执行的，每一步不成功都要返回Step1，这必导致速度缓慢。为了加快构造安全椭圆曲线的速度，将原来串行化算法中适合并行化的部分进行并行计算。由于Step3、Step4与Step5之间相
5、互没有依赖关系，所以可以并行执行Step3、Step4与Step5，然后输出a、b、#E(a,b)、k、h＝#E(a,b)/k。 基于多处理器构造GF(p)上安全椭圆曲线模型架构（如图1）的设计思想是三个处理器共享一个循环缓存区和一个公共列表，处理器Ⅰ负责利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解，找出的素因子写到循环缓存区中；处理器Ⅱ从循环缓存区中读取并验证，然后将存储到公共列表中；处理器Ⅲ负责验证；最后输出a、b、#E(a,b)、k、h＝#E(a,b)/k.2.1基于多处理器GF(p)上构造安全椭圆曲线的并行算法设计 输入：
6、有限域的大小p>3 输出：椭圆曲线E(a,b)、#E(a,b)=kh,k是大的素因子、且 算法步骤： Step1：随机产生GF(p)上的一条椭圆曲线E(a,b)：； Step2：利用SEA算法计算出#E(a,b)；Step3：(1)处理器Ⅰ利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解中有无大于的素因子k，如果没有，返回Step1；(2)处理器Ⅱ检测，否则返回Step1；(3)处理器Ⅲ检测。否则返回Step1； Step4：输出a、b、#E(a,b)、k、h＝#E(a,b)/k。3.构造给定长度的素数阶椭圆曲线算法分析
7、 文献[33]提出构造给定长度的素数阶的椭圆曲线算法描述如下： 输入：大素数q的长度 输出：素数p、q、上阶为q的椭圆曲线E' 算法步骤： Step1：取定负奇基本判别式，使适当小； Step2：确定m，n的取值范围，使具有长度；Step3：在Step2确定的范围中随机选取奇数m，n，令，检查p的素性，直到p为素数为止；Step4：令，检查q的素性，若q不是素数，转Step3，若q是素数，转Step5；Step5：计算（函数），并求出的一个根；Step6：构造以为不变量的椭圆曲线：其中； Step7：随机选取，构造椭圆曲线：； Step8：
8、选取点，若，输出p,q,E'，否则，转Step7。 上述构造给定长度的素数阶的
