一種基于雙勾函數(shù)的數(shù)據(jù)加密算法研究

李宏偉，潘志遠(yuǎn)，黃繼杰

(1.國(guó)家電網(wǎng)有限公司技術(shù)學(xué)院分公司，山東 濟(jì)南 250002；2.北京科東電力控制系統(tǒng)有限責(zé)任公司，北京 100192)

0 引 言

根據(jù)香農(nóng)定理，每傳送一次密文就更換密鑰是絕對(duì)安全的，量子保密通信可實(shí)現(xiàn)這一要求[1],但量子信號(hào)的減衰除受線路運(yùn)行環(huán)境的影響，還受設(shè)備精度和組網(wǎng)模式的影響，使得經(jīng)典的對(duì)稱和非對(duì)稱加密方法還在繼續(xù)研究和應(yīng)用。文獻(xiàn)[2-4]在研究網(wǎng)絡(luò)安全時(shí)采用了基于主體身份鑒別和認(rèn)證、數(shù)據(jù)加密傳輸、傳輸鏈路節(jié)點(diǎn)身份鑒別和認(rèn)證等技術(shù)；文獻(xiàn)[5-7]在研究區(qū)塊鏈時(shí)采用了非對(duì)稱加密算法RSA、對(duì)稱加密AES算法和單向加密算法SHA256；文獻(xiàn)[8-9]在研究電力變電站遠(yuǎn)動(dòng)通信時(shí)采用了非對(duì)稱加密和對(duì)稱加密混用的算法；文獻(xiàn)[10-14]對(duì)非對(duì)稱加密中的橢圓曲線加密算法進(jìn)行了研究和應(yīng)用。

但隨著量子計(jì)算技術(shù)的發(fā)展及其超乎想象的計(jì)算能力，使得經(jīng)典的對(duì)稱和非對(duì)稱加密方法中的密鑰和密碼將有可能被輕易破解，促進(jìn)了后量子密碼時(shí)代的到來(lái)。其中格密碼學(xué)的研究成為一大熱點(diǎn)[15-16]，且成為了美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(national institute of standards and technology，NIST)后量子密碼時(shí)代的優(yōu)選技術(shù)。

該文從非線性的雙勾函數(shù)特性出發(fā)，依次研究其在對(duì)稱加密、非對(duì)稱加密及格加密中的算法實(shí)現(xiàn)及在電力云培訓(xùn)仿真中的應(yīng)用。

1 雙勾函數(shù)的特性

雙勾函數(shù)形如：

(1)

雙勾函數(shù)的圖像是分別以y軸和y=ax為漸近線的兩支曲線，且圖像上任意一點(diǎn)到兩條漸近線的距離之積恰為漸近線夾角(0°～180°)的正弦值與|b|的乘積。

變化趨勢(shì)：在y軸左邊先增后減，在y軸右邊先減后增。雙勾函數(shù)的兩條漸近線分別為y軸和y=ax。

雙勾函數(shù)的圖形是在笛卡爾坐標(biāo)系中第一和第四象限的曲線，現(xiàn)在基于橢圓曲線加密算法(ECC算法)被廣泛應(yīng)用于互聯(lián)網(wǎng)領(lǐng)域，如區(qū)塊鏈的加密中。ECC算法的數(shù)學(xué)原理是橢圓曲線和離散對(duì)數(shù)，使得ECC算法要比RSA算法復(fù)雜很多，這種復(fù)雜的計(jì)算雖帶來(lái)了性能提升的好處，但是也同時(shí)潛藏了一些問題。首先是一套ECC算法標(biāo)準(zhǔn)所對(duì)應(yīng)的這條曲線，可能暗藏?cái)?shù)學(xué)機(jī)關(guān)并可以通過后門來(lái)破解，比如目前使用面很廣的一套標(biāo)準(zhǔn)是美國(guó)國(guó)家安全局發(fā)布的，這套標(biāo)準(zhǔn)就被懷疑是有后門。

另外一個(gè)問題就是基于ECC的專利太多，而且這些專利很多都被一個(gè)公司所持有，這個(gè)公司就是黑莓，這就使得開發(fā)一套新的ECC方案有可能被認(rèn)為觸犯了某個(gè)專利。故雖然ECC目前發(fā)展良好，但是也面臨著各種挑戰(zhàn)，這就為基于雙勾函數(shù)曲線加密的應(yīng)用提供了機(jī)會(huì)。

2 基于雙勾函數(shù)的加密算法

2.1 基于雙勾函數(shù)的對(duì)稱加密

圖1 雙勾函數(shù)做垂線和平行線

以由雙勾函數(shù)曲線上的點(diǎn)(X0,Y0)為一個(gè)開始的(原文，密文)對(duì)，從點(diǎn)(X0,Y0)做漸近線的法線，交雙勾函數(shù)曲線上的點(diǎn) (X1,Y1)，再由點(diǎn)(X1,Y1)做平行線，交于勾函數(shù)曲線上的點(diǎn)(X2,Y2)，由下列方程：

(2)

(3)

再由點(diǎn)(X1,Y1)做平行線，交于雙勾函數(shù)曲線上的點(diǎn)(X2,Y2)：

(4)

再?gòu)狞c(diǎn)(X2,Y2)開始按上述方法做漸近線的法線，并與交點(diǎn)處做X軸的平行線，交于雙勾曲線上，這個(gè)過程稱為第二次操作。依此可進(jìn)行第三次、第四次，直至第N次，此時(shí)N為偶數(shù)?？梢钥闯龅贜次交于雙勾曲線上的點(diǎn)由三個(gè)參數(shù)決定：重復(fù)次數(shù)N，雙勾函數(shù)參量a和b(這兩個(gè)參量也可以換成漸近線與X軸的夾角β，用弧度表示；和最低點(diǎn)(X0,Y0)的X0值，即三元組(β，X0，N)。

圖2 雙勾函數(shù)的解密過程

以圖中點(diǎn)(X0,Y0)為例，先做平行線交于點(diǎn)(X0,Y0)，此為第一次操作，再按上面的步驟，從點(diǎn)(X0,Y0)作法線，交于點(diǎn)(X1,Y1)，此為第二次操作，再由點(diǎn)(X1,Y1)做平行線，交于雙勾函數(shù)曲線上的點(diǎn)(X2,Y2)，這個(gè)過程稱為第三次操作。依此可進(jìn)行第四次、第五次，直至第N次，此時(shí)N為奇數(shù)。

2.2 基于雙勾函數(shù)的非對(duì)稱加密

上述由法線和平行線操作次數(shù)構(gòu)成的集是一個(gè)阿貝爾群(P，+)，因?yàn)椋?/p>

封閉性：s和t是整數(shù)操作次數(shù)，屬于P，那么s+t也是整數(shù)操作次數(shù)，也屬于P。

結(jié)合性：(s+t)+c=s+(t+c)，為雙勾曲線上同一點(diǎn)。

單位元：0即為單位元(在基點(diǎn)G沒操作)，因?yàn)閷?duì)于所有操作次數(shù)s，s+0=0+s=s，為雙勾曲線上同一點(diǎn)。

逆元：s的逆元為-s(由操作s次后的雙勾曲線上的點(diǎn)，反向操作，即當(dāng)s為奇數(shù)時(shí)，做漸近線的法線；s為偶數(shù)時(shí)，作平行線，交于雙勾函數(shù)曲線上的另一點(diǎn))，因?yàn)閟+(-s)=0,即單位元(回到基點(diǎn)G)。

所以由法線和平行線操作次數(shù)構(gòu)成的集P是阿貝爾群(P,+)。

雙勾函數(shù)曲線上求解的問題描述為：已知(1)雙勾函數(shù)曲線E；(2)雙勾函數(shù)曲線E上一點(diǎn)G(基點(diǎn))；(3)雙勾函數(shù)曲線E上的一點(diǎn)xG(x為由G作法線和平行線的總次數(shù))。據(jù)此求解x，這個(gè)問題的難度保證了基于雙勾函數(shù)曲線加碼的安全性。

基于雙勾函數(shù)數(shù)字簽名法的加密算法(DHC)具體如下：

基于雙勾函數(shù)的數(shù)據(jù)加密算法屬于非對(duì)稱密鑰加密系統(tǒng)體系，又稱公鑰密鑰加密體系。它需要使用不同的密鑰來(lái)分別完成加密和解密操作，一個(gè)公開發(fā)布，即公開密鑰，另一個(gè)由用戶自己秘密保存，即私用密鑰。信息發(fā)送者用公開密鑰去加密，而信息接收者則用私用密鑰去解密。

針對(duì)上面確定的雙勾函數(shù)加密三元組(β，X0，Xg)，都采用上面基于素?cái)?shù)的公共密鑰機(jī)制來(lái)生成。這三個(gè)數(shù)中都是帶小數(shù)的實(shí)數(shù)，為確保法線能盡可能不平行于Y軸，β取值應(yīng)在30至60之內(nèi)為宜。同時(shí)，為了使第一次操作就是做法線，Xg應(yīng)取最低點(diǎn)X0的右邊值，即Xg大于X0。

在雙勾函數(shù)曲線加密中，給定雙勾函數(shù)曲線E，基點(diǎn)G和點(diǎn)kG(該點(diǎn)為從G點(diǎn)開始，做了k次上述操作后與雙勾函數(shù)曲線E的交點(diǎn))，稱(β，X0，kG)為公鑰，(β，X0，G)值為私鑰，更簡(jiǎn)單地k就是真正的私鑰。

計(jì)算公鑰和私鑰利用了上述“運(yùn)算”中兩種操作：奇數(shù)為做漸近線的法線，記錄交點(diǎn)的y值；偶數(shù)為做平行于X的平行線，記錄交點(diǎn)的x值的負(fù)數(shù)，即記錄雙勾函數(shù)曲線下半部對(duì)稱的點(diǎn)的x值。

采用DHC算法對(duì)數(shù)據(jù)進(jìn)行加密和解密，首先要確定分組的大小。由于DHC算法計(jì)算出的取值(奇數(shù)為做漸近線的法線，取交點(diǎn)的y值；偶數(shù)為做平行于X的平行線，取交點(diǎn)的x值的負(fù)數(shù)，即記錄雙勾函數(shù)曲線下半部對(duì)稱的點(diǎn)的x值)是用4字節(jié)表示的浮點(diǎn)數(shù)表示，而從緩沖區(qū)明文M中取出的數(shù)是整數(shù)(次數(shù))，為保證加密后的報(bào)文長(zhǎng)度不變，每次從M中取4字節(jié)的整數(shù)i出來(lái)，從雙勾函數(shù)曲線的點(diǎn)kG處做i次運(yùn)算，從而得到4字節(jié)明文對(duì)應(yīng)的密文。

使用DHC算法解密時(shí)，從雙勾函數(shù)曲線的點(diǎn)G處循環(huán)做運(yùn)算(奇數(shù)為做漸近線的法線，取交點(diǎn)的y值；偶數(shù)為做平行于X的平行線，取交點(diǎn)的x值的負(fù)數(shù)，即記錄雙勾函數(shù)曲線下半部對(duì)稱的點(diǎn)的x值)，直至與4字節(jié)密文所對(duì)應(yīng)的浮點(diǎn)數(shù)差小于0.000 01為止(按照IEEE754的標(biāo)準(zhǔn)，單精度浮點(diǎn)數(shù)有效位最多小數(shù)點(diǎn)后7位)，并將這次的循環(huán)次數(shù)n減去私鑰k所得的整數(shù)，其4字節(jié)所對(duì)應(yīng)的二進(jìn)制就是明文中對(duì)應(yīng)的4字節(jié)信息。

上述加解密保證了明文和密文等長(zhǎng)，但以4字節(jié)作為整數(shù)的過程計(jì)算量大。為此取明文中的2字節(jié)作為整數(shù)(操作次數(shù))，每次從M中取2字節(jié)的整數(shù)i出來(lái)，從雙勾函數(shù)曲線的點(diǎn)kG處做i次運(yùn)算，從而得到2字節(jié)明文對(duì)應(yīng)的4字節(jié)密文，因而密文長(zhǎng)度是明文的2倍。為了更快的應(yīng)用場(chǎng)合，也可以每次從M中取1字節(jié)的整數(shù)i出來(lái)，從雙勾函數(shù)曲線的點(diǎn)kG處做i次運(yùn)算，從而得到1字節(jié)明文對(duì)應(yīng)的4字節(jié)密文，因而密文長(zhǎng)度是明文的4倍。

使用DHC算法進(jìn)行數(shù)字簽名時(shí)，設(shè)私鑰、公鑰分別為k、K，即K=kG，其中G為位于雙勾函數(shù)(y=ax+b/x,ab>0)曲線上的基點(diǎn)。設(shè)定哈希值用h表示，私鑰用k表示，隨機(jī)數(shù)用r表示，根據(jù)如下原理：

hG/s+xK/s=hG/s+x(kG)/s=(h+xk)G/s=r(h+xk)G/(h+kx)=rG。

(1)私鑰簽名的過程。

(a)選擇隨機(jī)數(shù)r，計(jì)算點(diǎn)rG。

(b)根據(jù)隨機(jī)數(shù)r，消息M的哈希值h，私鑰k，計(jì)算s=(h+kx)/r。

(c)將消息M和簽名{rG,s}發(fā)給接收方。

此處的消息M為采用DHC算法對(duì)數(shù)據(jù)進(jìn)行加密后的信息。

上述計(jì)算中，x表示雙勾函數(shù)曲線的基點(diǎn)G的X軸值，kx是指在雙勾曲線上從基點(diǎn)做了k次上文所提的操作(垂直線和平行線)的次數(shù)。

(2)公鑰驗(yàn)證簽名的過程。

(a)接收方收到消息M以及簽名{rG,s}。

(b)根據(jù)消息M采用與發(fā)送方相同的哈希算法求解哈希值h。

(c)使用發(fā)送方公鑰K計(jì)算：hG/s+xK/s，將計(jì)算結(jié)果與rG比較，如相等即驗(yàn)簽成功。

上述計(jì)算中，xK指在雙勾曲線上從點(diǎn)K做了x次上文所提的操作(垂直線和平行線)的次數(shù)。

2.3 基于雙勾函數(shù)的格加密研究

利用量子干涉效應(yīng)使得“量子并行計(jì)算”的若干個(gè)計(jì)算結(jié)果中，一部分的計(jì)算結(jié)果被量子干涉所強(qiáng)化，而另外一部分被量子干涉所抵消。這將導(dǎo)致觀測(cè)到特定結(jié)果的概率增加，從而使得量子計(jì)算機(jī)以更高的概率輸出想要得到的計(jì)算結(jié)果?；诖肆孔痈缮嫘?yīng)，Peter Shor于1994年提出了Shor算法。Shor算法可以用量子計(jì)算機(jī)以多項(xiàng)式時(shí)間求解周期函數(shù)的周期，而RSA、橢圓曲線等密碼體制所基于的困難問題：大整數(shù)分解和離散對(duì)數(shù)求解，都可以轉(zhuǎn)化為周期函數(shù)求解周期的問題，因而可以通過Shor算法求解。這使得現(xiàn)有的公鑰密碼體制很容易被量子計(jì)算機(jī)所擊破。

2019年《Nature》上發(fā)表了Google最新一代量子處理器Sycamore，它包含53個(gè)量子比特，對(duì)量子處理器的輸出進(jìn)行重復(fù)性采樣，并與經(jīng)典計(jì)算機(jī)模擬的結(jié)果進(jìn)行比較。Sycamore完成同樣的任務(wù)只需要200 秒，而Google估計(jì)使用目前世界上最強(qiáng)大的超級(jí)計(jì)算機(jī)Summit需要1萬(wàn)年,以此證明該量子處理器實(shí)現(xiàn)了量子優(yōu)越性(quantum supremacy)。IBM提出使用二級(jí)存儲(chǔ)可以模擬54-bit量子計(jì)算機(jī)，并且通過優(yōu)化將經(jīng)典計(jì)算機(jī)執(zhí)行任務(wù)的時(shí)間從1萬(wàn)年降低到2.55天。針對(duì)量子計(jì)算機(jī)的這種威脅，密碼學(xué)家們提出了“后量子密碼”這一概念。從廣義的角度上說(shuō)，后量子密碼學(xué)研究量子計(jì)算機(jī)出現(xiàn)后將對(duì)密碼學(xué)產(chǎn)生的影響；從狹義的角度上說(shuō)，后量子密碼主要關(guān)注于設(shè)計(jì)可抵抗量子計(jì)算威脅的密碼算法，尤其是公鑰加密和數(shù)字簽名算法。

格密碼就是這樣一類備受關(guān)注的抗量子計(jì)算攻擊的公鑰密碼體制。2020年7月22日，美國(guó)國(guó)家標(biāo)準(zhǔn)局NIST公布了其舉辦的后量子密碼標(biāo)準(zhǔn)競(jìng)賽的第三輪入選算法，這意味著從2016年開始的美國(guó)后量子密碼標(biāo)準(zhǔn)制定工作進(jìn)入了最后的沖刺階段，在7個(gè)正式入選第三輪的算法中，有5個(gè)都屬于格密碼的范疇。而與此同時(shí)，在中國(guó)密碼學(xué)會(huì)舉辦的后量子密碼算法競(jìng)賽中，格密碼也在其中占據(jù)了相當(dāng)大的比例。

格(lattice)是一種數(shù)學(xué)結(jié)構(gòu)，定義為一組線性無(wú)關(guān)的非0向量(稱作格基)的整系數(shù)線性組合。具體來(lái)說(shuō)，給定一組格基，x1,x2,…,xn對(duì)任意的整數(shù)c1,c2,…,cn，c1x1,c2x2,…,cnxn都是屬于這個(gè)格的向量，其中n稱為格的維數(shù)?；诟竦拿艽a學(xué)近年來(lái)發(fā)展迅速，利用格上困難問題作為極微本原來(lái)構(gòu)造的密碼學(xué)方案層出不窮[17-20]。

(5)

顯然c1y1,c2y2,…,cnyn也是雙勾函數(shù)且是非線性的，故構(gòu)成了格；同時(shí)c1y1+c2y2+…+cnyn也是雙勾函數(shù)考慮。雙勾函數(shù)在正一象限的曲線，由這個(gè)格構(gòu)成了一個(gè)雙勾曲線空間(正半部曲線)，包含了無(wú)窮多條這樣的曲線，其中每條曲線由a和b兩參數(shù)決定。

在用格進(jìn)行加密時(shí)，需要求解數(shù)學(xué)難題來(lái)加大破解的計(jì)算量。取明文中三字節(jié)(并增加1)構(gòu)成一個(gè)正整數(shù)ak，現(xiàn)取一未知的整數(shù)bk，構(gòu)成雙勾曲線空間中的一條雙勾曲線yk。

選取c1k,c2k,…,cnk，使得c1ka1+c2ka2+…+cnkan=ak且c1kb1+c2kb2+…+cnkbn=bk，即由y1,y2,…,yn構(gòu)成yk。當(dāng)允許c1,c2,…,cn為正有理數(shù)時(shí)，計(jì)算滿足上式中c1k,c2k,…,cnk的和為最小可以看成是一數(shù)學(xué)難題，存在進(jìn)行加密的條件了。

另外，在這個(gè)雙勾曲線空間中，求該曲線與任意兩條曲線的交點(diǎn)。比如上式中y1和y2兩條曲線的交點(diǎn)(Xc,Yc),其中：

(6)

在用格進(jìn)行加密時(shí)所構(gòu)成的雙勾曲線yk，其與上面n條曲線的交點(diǎn)為(Xk1,Xk2,…,Xkn)，現(xiàn)在就是找出整數(shù)bk使(Xk1,Xk2,…,Xkn)存在，因?yàn)闉樨?fù)值開根號(hào)不成立(也即沒交點(diǎn)，此時(shí)取值為0，表示沒交點(diǎn))。對(duì)于每個(gè)整數(shù)ak找出滿足這條件的最小bk，其計(jì)算量隨n的增大而加大，也可以看成是一數(shù)學(xué)難題，故而存在進(jìn)行加密的條件了。

3 仿真實(shí)驗(yàn)或案例分析

在聯(lián)想工作站(四顆Inter i5-6500 Cpu，48G內(nèi)存)上進(jìn)行仿真實(shí)驗(yàn)，同時(shí)在加解密的速度上與橢圓曲線加密算法(ECC)進(jìn)行對(duì)比。在實(shí)現(xiàn)ECC時(shí)調(diào)用了LibTommath庫(kù)(源碼網(wǎng)址：https://blog.csdn.net/cg129054036/article/details/83862918)。

在用雙勾函數(shù)加、解密(算法流程如圖3、4所示)時(shí)，先根據(jù)選定的參數(shù)a、b和基點(diǎn)的x，依次做漸近線的法線和交點(diǎn)的x軸平行線，從而初始生成加密碼值表?？紤]到碼值表的大小與取原文的字節(jié)數(shù)相關(guān)，這里取原文1個(gè)字節(jié)數(shù)來(lái)對(duì)應(yīng)碼值表前256個(gè)浮點(diǎn)數(shù)。這兩算法的加密速度對(duì)比見表1。

表1 與橢圓曲線加密算法的速度對(duì)比

圖3 基于雙勾函數(shù)的加密流程

圖4 基于雙勾函數(shù)的解密流程

在應(yīng)用案例上，將基于雙勾函數(shù)數(shù)字簽名法的加密算法(DHC)應(yīng)用到了電力云培訓(xùn)仿真中,確保了云培訓(xùn)考核的安全性。具體實(shí)施過程如下：

(1)教員根據(jù)每個(gè)學(xué)員的郵箱信息在密碼中心為其申請(qǐng)證書，如圖5所示，為學(xué)員Bob的郵箱“bob@b.com”申請(qǐng)證書。

圖5 雙勾函數(shù)的非對(duì)稱加密應(yīng)用

(2)教員收到密碼中心下發(fā)的學(xué)員Bob的私鑰。

(3)學(xué)員Bob從密碼中心獲得他的公鑰。

(4)學(xué)員Bob對(duì)獲得的公鑰進(jìn)行驗(yàn)證以確定是他的公鑰。

(5)學(xué)員Bob采用獲得的公鑰加密其考試答案，并利用自已的私鑰進(jìn)行數(shù)字簽名，一并發(fā)給教員。

(6)教員采用學(xué)員的公鑰對(duì)數(shù)字簽名進(jìn)行驗(yàn)證，驗(yàn)證通過后，采用學(xué)員Bob的私鑰解密報(bào)文，獲得學(xué)員Bob的考試答案。

4 結(jié)束語(yǔ)

雙勾曲線函數(shù)僅由兩個(gè)參數(shù)決定其曲線形狀，可以在其曲線上添加某種操作來(lái)進(jìn)行對(duì)稱和非對(duì)稱的加密。該文通過對(duì)其漸近線添加垂直線操作以及線上點(diǎn)的X軸平行線操作，將明文數(shù)值對(duì)應(yīng)為交替所做的垂直線和平行線的次數(shù)，用最后一次交點(diǎn)的X或Y值作為對(duì)應(yīng)的密文。這種對(duì)稱加密算法比橢圓曲線加密算法快了兩個(gè)數(shù)量級(jí)，在此基礎(chǔ)上可設(shè)計(jì)相應(yīng)的非對(duì)稱加密算法(DHC)來(lái)滿足快速加密場(chǎng)合的需求。同時(shí)可選擇任意條雙勾曲線函數(shù)作為格基，來(lái)構(gòu)成非線性的格空間，從而具有了進(jìn)行格加密的可能。