一種采用泛進制計算法進行求解密鑰的方法

楊 虹

（遼寧警察學院 遼寧 116036）

0 引言

當前，世界計算機領域都在努力探索更加安全的數據保護方法，因此產生了很多加密解密算法。其中主要有兩大陣營，一是DES加密方法，稱為對稱加密方法；二是非線性加密解密方法，即以公式為主要計算方法。DES方法沒有可利用的公式，要想破解，需要采用窮舉法；非線性加密解密方法通過公式求解密鑰，最大特點是不可逆，其中以RSA算法和橢圓曲線算法為典型計算方法。

此外還有很多加密解密方法，雖然沒有公開（即被破解），但其中的原理基本相同。為了提高加密解密的難度，通常采用DES與非線性加密解密兩種方法的組合，以達到不被破解的目的。

1 RSA算法與橢圓曲線算法概述

1.1 RSA算法

RSA算法是一種非對稱密鑰算法。所謂非對稱就是指該算法需要一對密鑰，其中一個用于加密，另一個用于解密。

RSA算法涉及3個參數：n、e1、e2。其中，n是兩個大質數p、q的積。n是二進制表示所占用的位數，即密鑰的長度。e1和e2是一對相關的值，e1可以任意取值，但要求e1與（p-1）*（q-1）互質；再選擇e2，要求（e2*e1）mod（（p-1）*（q-1））=1。

（n 及e1），（n及e2）就是密鑰對。

RSA的加密算法和解密算法完全相同。設A為明文，B為密文，則：

e1和e2可以互換使用，即：

以上就是RSA算法。

1.2 橢圓曲線算法

橢圓曲線理論是代數幾何、數論等多個數學分支的一個交叉點，一直被認為是純理論學科。近年來，由于公鑰密碼學的產生與發展，該學科也找到了它的應用領域。在 RSA 密碼體制的基礎性問題——大整數分解和素性檢測——的研究方面，橢圓曲線是一個強有力的工具。特別以橢圓曲線上的（有理）點構成的 Abel 群為背景結構，實現各種密碼體制已是公鑰密

碼學領域的一個重要課題。由于橢圓曲線密碼體制本身的優點，自20世紀80年代中期被引入以來，橢圓曲線密碼體制逐步成為一個十分令人感興趣的密碼學分支，1997年以來形成了一個研究熱點，特別是移動通信安全方面的應用更是加快了這一趨勢。

橢圓曲線算法是在有限域Fp約束下，其中p為一個大質數，橢圓曲線可定義成所有滿足方程式E：y2=x3+ax+b（x，y，a，b∈F）的點（x，y）所構成的集合。若方程式x3+ax+b沒有重復因式或4 a3+27 b2≠0，則E：y2=x3+ax+b 能成為群。定義：

（1）橢圓曲線中存在一個無限遠的點O，但它并不在橢圓曲線上。

（2）若P 的負點稱為?P，則點P=（x，y）相對X坐標軸反射的點為?P=（x，?y）。

（3）若橢圓曲線上點P 的域為n，則n是最小的使得nP=0的正整數。

（4）橢圓曲線上的運算結果可以生成橢圓曲線上的所有點，但點O除外。

（5）E（Fp）為在Fp之下，由橢圓曲線E上全部點所構成的集合。

（6）若有兩個點P=（x1，y1）∈E（Fp）及Q=（x2，y2）∈E（Fp），且P≠±Q，則P+Q=R=（x3，y3）。其中，X3=（（y2-y1）/（x2-x1））2-x2-x1’，Y3=（（y2-y1）/（x2-x1））（x1-x3）-y1。

（7）若有兩個點 P=（x1，y1）∈E（Fp）且 P≠-P，則 P+P=2P=（x3，y3），其中，X3=（（3x12+a）/2y1）2-2x1，Y3=（（3x12+a）/2y1）（x1-x3）-y1。

（8）若對所有點（Fp）P∈E，則P+O=O+P=P、P+（?P）=O、O=?O。

（9）分配律成立，即若n∈F，則（m+n）P=mP+nP。

（10）交換律成立，即若pm，n∈F，則m（nP）=mn（P），其中kP=P+...+P。

以上就是橢圓曲線算法。

1.3 兩種算法總結

這兩種算法的特點如下：

（1）都需要求出兩個或兩個以上的未知數作為密鑰。

（2）公式可以重復使用。

（3）用素數做模進行計算。

（4）計算較復雜。

（5）不可逆運算。

由此得出結論，如果能找到一種算法具備以下特點，這個算法將會更加實用、有效：

（1）能夠求出兩個以上未知數。

（2）公式可以重復使用并簡單。

（3）用計算機里的數據（或任意整數）能求解出密鑰或多個密鑰。

（4）計算簡單，為不可逆運算。

（5）提高在計算機中的運算速度。

2 泛進制算法及三參數建立方法

2.1 泛進制算法

將任意進制數N轉換成十進制數的方法為：N=10s+m。式中，10表示十進制；s表示10的倍數；m是余數。

由此可見，將任意進制整數N轉換成所需要的某進制整數，可以寫成：

其中，N是范圍為 0，1，2，3，……的任意進制整數；p是范圍為2，3，……的任意整數；s是p的倍數，表示范圍為0，1，2，3，……的任意整數；m是余數，范圍為0，1，……p-1，該值與p有關。

例如，一個十進制數為254，選定p=14，根據公式（1），得到s=18，m=2。

如果選定p=15，根據公式（1），得到s=16，m=14。

通過改變p的值，可以得到不同的s、m的值。

如果上式中的p可以任意選定，那么公式（1）可以表示任意進制轉換的數。由于公式（1）中有3個未知數（3個變量），且這3個未知數可以變化，恰好符合計算機密鑰的變化規律，因此這3個未知數可以作為密鑰。

數字被p、s、m 三個因子所分解，每個因子所表達的含義與原數字（或代碼）所表達的含義完全不同，即改變了原數字。

知道p、s、m三個參數中的一個或兩個參數，都不能求出原數據，符合非對稱加密特點。由于公式簡單，所以計算速度較快。

例如，一個十進制數為200，令p=13，利用公式（1）經過計算得到N=13×15﹢5。

其中，p=13，s=15，m=5。由此可見，數字 200完全變形為三個因子13、15和5。

這種算法的特點是密鑰的計算方法簡單，且采用的進制數越大，被解密的可能就越小。

2.2 三參數建立方法

由公式（1）計算出三個參數p、s、m，將三個參數分別代入x、y、z坐標中，數字N可記做N（x、y、z），根據x、y、z坐標點，將數字隱藏到三維坐標表示的點內，形成三維加密方法。

因為計算公式簡單，容易被破解。在加密算法中，采用如此簡單的公式并不多見。一個數據用三維坐標表示，或多維坐標表示，其解密難度呈非線性增長。因此每增加一維參數，對解密工作者需要千百萬次窮舉法才能破解，所以增加破解難度。按照這個思路，還可以將數字N用更多維進行表述。利用多參數變化，也能達到加密目的。

3 泛進制算法特點

3.1 計算簡單

由公式（1）可以看出計算公式的參數非常簡單，比任何非線性加密解密計算方法都簡單。不僅如此，采用公式（1）進行迭代運算，也可以獲得多個參數。其他非線性加密方法采用迭代法，會影響計算機運行速度，而泛進制計算方法不會影響計算機中該算法的運行速度。

通過增加參數降低數學公式的運算難度，這是非線性加密解密最好的解決問題方法。不僅避免了許多深奧的數學計算和數學變化，還達到了不可逆計算的目的。

3.2 破解難度大

實際應用中，公式（1）中參數是可以選擇的。根據需要，一般把p選擇得大一些，這樣可以增加破解難度。由于公式（1）對三個參數表示范圍進行了界定，且這三個參數的取值范圍與其在計算機中所需存儲單元的位數有關，即若公式（1）中參數p的位數為xp，參數s的位數為xs，參數m的位數為xm，令xp=w，xs=y，xm=z，則理論上公式（1）中參數（即密鑰）有2w×2y×2z種可能，所以，采用窮舉法很難進行破解。

3.3 易于編程實現

每種加密解密方法都需要通過計算機編程得到密鑰，編程難度與程序是否容易實現相關。可以看出，公式（1）無論用什么語言編程都很容易實現，因為在計算機語言中，都有除法運算語句（指令），只要選定公式（1）中的p值，就很容易計算出s和m值。

3.4 p值選定具有隨機性

公式（1）中的p值選定非常關鍵。p值不能固定不變，如果p值固定不變，將會導致破解難度降低。計算機中的數字本身就是隨機的。利用計算機數字的特點，將一個數字分解成兩組數據，如果將某組數據作為p值，即指定計算機里某幾位數字作為p值，s和m的值就很容易求出。

前面已經定義公式（1）三個參數的取值范圍，根據需要還可以采用超范圍定義方法定義泛進制參數，將數字N中某參數取負值，同樣也可以得到數字N。具體計算方法如下：

令數字N為正整數，N=ps+m，取p為負數，則p寫成-p，即N=-ps+m，得m=（N+ps），所以，出現m大于N值顯現；同理可以得出很多結果，如果把三維坐標分成8個象限，一個數字N，就會有8個三維坐標象限表示的數組，因此解密難度遠遠大于兩維坐標表示的4象限數組。

3.5 計算方法具有可迭代性

公式（1）代入p，則有：

公式（1）代入s，則有：

公式（1）代入m，則有：

公式（1）分別代入p，s和m，則有：

公式（1）還可以繼續代入 pp，sp，mp……，即可得到更多參數（或密鑰）。

3.6 解決非線性密鑰生成困難的問題

由RSA算法與橢圓曲線算法可以看出，雖然橢圓曲線算法比RSA算法簡單，但非線性密鑰生成卻是很復雜的。計算機信息安全技術人員一直在尋找簡單且行之有效的密鑰生成方法。那么，密鑰變化主要與哪些因素有關呢？一是未知數變量有多少，即密鑰有多少。未知變量的增加實際就是密鑰的增加。在加密過程中，采用哪幾個密鑰進行加密，哪些密鑰不參與加密，只有加密人員根據迭代計算基本公式（1）選取參數的合理性而定，所以破解起來非常繁瑣，不易成功；二是隨機性，即在加密過程中參數需要隨機選定，這樣有利于加密，起到增加破解難度的目的；三是對稱加密與非對稱加密方法的結合。若p值固定，即是對稱加密方法；四是整數求解公式的表達完整性。該迭代計算公式只適用于整數計算，因此加密計算簡單、方便。只要滿足上述條件，加密會變得相對簡單，而解密則變得相對復雜。

3.7 泛進制與RSA及橢圓曲線加密算法比較

泛進制計算方法與RSA和橢圓曲線加密算法比較，泛進制計算簡單，有三個以上參數；而RSA和橢圓曲線加密算法計算公式比泛進制算法復雜，只有兩個參數。

泛進制計算方法可以迭代，而RSA和橢圓曲線加密計算不適合多次迭代，其原因是RSA和橢圓曲線加密計算復雜，如果再次迭代，速度會更慢，顯然不適合反復迭代。

泛進制加密方法可以實現三維空間數據加密，這種運算方法決定加密數據是存放在三維坐標之中的，因此三維數據隱藏方式要比二維隱藏方法要有難度，而泛進制很好的避開三位加密運算復雜的問題，很容易得到三維坐標點，所以采用泛進制加密方法為今后加密指出另一條加密思路。

4 結束語

泛進制加密方法是一種非線性的多密鑰計算方法，解決了非線性計算復雜的問題，同時可以大大地提高其在計算機中的處理速度，能實現三維空間加密，利用公式（1），還能進行迭代擴展。在RSA加密和橢圓曲線加密中的密鑰，計算公式很復雜，只能獲得兩個密鑰。相比較而言，采用泛進制加密方法的多密鑰計算公式求解方法方便、簡單、實用，是一個較理想加密解密算法。

[1]李寧.基于正規基的橢圓曲線密碼算法的研究和IP核實現[D].西安電子科技大學.2010.

[2]陸志彬.淺析橢圓曲線密碼系統的應用原理[J].計算機光盤軟件與應用.2010.

[3]程華.一種基于構造法的橢圓曲線改進算法[J].網絡安全技術與應用.2009.

[4]張京京，閆曉蔚，蔡建順，郭曙光.基于 Android系統的手機隱私安全的研究與實現[J].信息網絡安全.2012.

[5]龐遼軍，李慧€賢，裴慶祺，柳毅，王育民.一個單方加密-多方解密的公鑰加密方案[J].計算機學報.2012.

[6]黃東偉.移動可編程數據加密系統的設計與實現[D].青島科技大學.2010.

[7]符浩，陳靈科，郭鑫.基于Web網絡安全和統一身份認證中的數據加密技術[J].軟件導刊.2011.

[8]楊義先，鈕心忻.應用密碼學[M].北京郵電大學出版社.2005

[9]章照止.現代密碼學基礎[M].北京郵電大學出版社.2004.

[10]許春香，李發根，聶旭云，禹勇.現代密碼學[M].電子科技大學出版社.