橢圓曲線加密在Nvidia GT200圖形顯卡上的快速實(shí)現(xiàn).pdf

1、橢圓曲線加密(EllipticCurveCryptography，ECC)是一種被廣泛應(yīng)用的公鑰加密技術(shù)，相對于其他的公鑰加密體制不僅具有更高的安全性，還可以在保證安全性的基礎(chǔ)上使用較短的密鑰。在日益增長的高性能需求下，ECC的快速實(shí)現(xiàn)在學(xué)術(shù)領(lǐng)域和實(shí)際工業(yè)應(yīng)用中受到了廣泛關(guān)注。圖形顯卡處理器(GraphicProcessingUnits，GPU)，憑借強(qiáng)大的并行能力，在當(dāng)今社會(huì)被廣泛應(yīng)用于通用計(jì)算，也成為密碼學(xué)領(lǐng)域的新寵兒。
　　

2、本文主要描述了ECC加密庫在英偉達(dá)GT200系列GPU上的快速實(shí)現(xiàn)與設(shè)計(jì)。該庫能夠執(zhí)行在TwistedEdwards曲線以及蒙哥馬利曲線(MontgomeryCurves)上基于優(yōu)化素?cái)?shù)域(OptimalPrimeFields，OPF)的標(biāo)量乘(ScalarMultiplication，ECSM)操作k*P。本課題的目的是在GT200系列GPU上單位時(shí)間內(nèi)最大數(shù)量的并行執(zhí)行ECSM。課題中我們采用線程級(jí)并行或者數(shù)據(jù)級(jí)，即一個(gè)線程執(zhí)行一個(gè)

3、完整的k*P操作，線程間處理不同的數(shù)據(jù)執(zhí)行相同的指令集。關(guān)于k*P的實(shí)現(xiàn)分為隨機(jī)基點(diǎn)和確定基點(diǎn)兩種情況。對于隨機(jī)取點(diǎn)模式，采用了MontgomeryLadder算法在蒙哥馬利曲線上的實(shí)現(xiàn);對于確定點(diǎn)模式，采用了comb算法在twistedEdwards曲線上的實(shí)現(xiàn)，預(yù)存256個(gè)點(diǎn)。結(jié)合GPU的結(jié)構(gòu)特點(diǎn)，對這兩種算法我們做了不同程度的修改，采用特殊的技巧替換其中的條件語句，不僅避免了線程分歧提高了實(shí)現(xiàn)效率，還可以有效的減少測信道信息泄漏。

4、在TwistedEdwardscurves上的點(diǎn)以擴(kuò)展的映射坐標(biāo)(extendedprojectivecoordinates)表示，在該情況下pointaddition操作只需要七個(gè)底層域乘法。
　　OPF的定義形式為p=u·2k+1，其中u的長度只有16比特，可以很大程度上簡化模減運(yùn)算。在本課題中底層在OPF域上的算術(shù)運(yùn)算采用224為基數(shù)來表示域中的元素（一般基數(shù)為232）。采用這種表達(dá)方式可以很好的利用GPUGT200的指令集

5、，GT200支持24×24-bit的乘法，提供原操作。另外，224的基數(shù)表示有助于不完全模減技術(shù)的執(zhí)行，即在域上的加法和乘法完成后我們不需要執(zhí)行模減操作。
　　綜合以上實(shí)現(xiàn)技術(shù)和配置，我們可以在GT200的三十個(gè)多處理器上同時(shí)發(fā)放2880個(gè)在蒙哥馬利曲線上的224-bit域內(nèi)ECSM操作，4320個(gè)在TwistedEdwards曲線上的224-bit域內(nèi)點(diǎn)乘操作。在224-bit域上，蒙哥馬利曲線最大吞吐量為115200個(gè)k*P/