椭圆曲线加密在Nvidia GT200图形显卡上的快速实现

摘要

椭圆曲线加密(EllipticCurveCryptography，ECC)是一种被广泛应用的公钥加密技术，相对于其他的公钥加密体制不仅具有更高的安全性，还可以在保证安全性的基础上使用较短的密钥。在日益增长的高性能需求下，ECC的快速实现在学术领域和实际工业应用中受到了广泛关注。图形显卡处理器(GraphicProcessingUnits，GPU)，凭借强大的并行能力，在当今社会被广泛应用于通用计算，也成为密码学领域的新宠儿。
　　本文主要描述了ECC加密库在英伟达GT200系列GPU上的快速实现与设计。该库能够执行在TwistedEdwards曲线以及蒙哥马利曲线(MontgomeryCurves)上基于优化素数域(OptimalPrimeFields，OPF)的标量乘(ScalarMultiplication，ECSM)操作k*P。本课题的目的是在GT200系列GPU上单位时间内最大数量的并行执行ECSM。课题中我们采用线程级并行或者数据级，即一个线程执行一个完整的k*P操作，线程间处理不同的数据执行相同的指令集。关于k*P的实现分为随机基点和确定基点两种情况。对于随机取点模式，采用了MontgomeryLadder算法在蒙哥马利曲线上的实现;对于确定点模式，采用了comb算法在twistedEdwards曲线上的实现，预存256个点。结合GPU的结构特点，对这两种算法我们做了不同程度的修改，采用特殊的技巧替换其中的条件语句，不仅避免了线程分歧提高了实现效率，还可以有效的减少测信道信息泄漏。在TwistedEdwardscurves上的点以扩展的映射坐标(extendedprojectivecoordinates)表示，在该情况下pointaddition操作只需要七个底层域乘法。
　　OPF的定义形式为p=u·2k+1，其中u的长度只有16比特，可以很大程度上简化模减运算。在本课题中底层在OPF域上的算术运算采用224为基数来表示域中的元素（一般基数为232）。采用这种表达方式可以很好的利用GPUGT200的指令集，GT200支持24×24-bit的乘法，提供原操作。另外，224的基数表示有助于不完全模减技术的执行，即在域上的加法和乘法完成后我们不需要执行模减操作。
　　综合以上实现技术和配置，我们可以在GT200的三十个多处理器上同时发放2880个在蒙哥马利曲线上的224-bit域内ECSM操作，4320个在TwistedEdwards曲线上的224-bit域内点乘操作。在224-bit域上，蒙哥马利曲线最大吞吐量为115200个k*P/s，最小延迟为19.2ms;TwistedEdwards曲线最大吞吐量为345417k*P/s，最小延迟为4.52ms。其中吞吐量是目前取得最好的研究成果的2.45倍。