利用帕斯卡三角和謝爾賓斯基三角的加密演算法

摘要： 文字資訊總是在新建，傳播，每天每個人至少會發出十條資訊，由於頻繁使用致使它們並未被加密。因此人們並不能通過簡訊交換機密資訊。本文中，我們開發出了一款新的加密演算法，它利用了帕斯卡三角和謝爾賓斯基三角相關的概念。要論述的做法是利用帕斯卡三角做替換和利用謝爾賓斯基三角做置換。這個方法 在現實生活...

文字資訊總是在新建，傳播，每天每個人至少會發出十條資訊，由於頻繁使用致使它們並未被加密。因此人們並不能通過簡訊交換機密資訊。本文中，我們開發出了一款新的加密演算法，它利用了帕斯卡三角和謝爾賓斯基三角相關的概念。要論述的做法是利用帕斯卡三角做替換和利用謝爾賓斯基三角做置換。這個方法 在現實生活中 簡單、易行。而且攻擊者很難從密文中破譯。但此方法在暴力破解和詞頻攻擊中依然很脆弱。

關鍵詞

加密，替換，置換，帕斯卡三角，謝爾賓斯基三角

一、簡介

由於其實用性及科技的普及，通訊使用者之間傳遞短訊息的方法在社交媒體、聊天應用、電子郵件等領域越來越廣泛。在這些領域中傳播的資訊難免有些是機密並且對使用者很敏感的。因此，非常有必要加密這些訊息。加密等機制就可以提供機密服務。替換法和置換法就經常用來加解密文字資訊[15]。本文中，我們將使用一種基於替換法和置換法的用於加解密的演算法，這種演算法基於要論述的帕斯卡三角和謝爾賓斯基三角的概念。帕斯卡三角的概念用於在一種特殊的模式下對純文字中字元進行異或運算，運算結束後得到我們想要的密文。

二、參考文獻

這一節裡，我們會提到一些經典和現代加密資料技術的概述。加密文字使用了前輩們介紹過的一些不同的簡單方法 [5, 7-9, 12, 13]

2.1 古典加密

凱撒密碼是已知的最簡單的加密方式之一。此方法由Julius Caesar命名，他使用這種方法與他的部下們通訊。這是一種利用按照字母表的順序將純文字內容移動一定字母實現加密的演算法。然而這種演算法並不能保證通訊的安全性並且很容易就可能被人們手動破解出來。該方法應用了下列等式(1)(2)[15]來實現加解密：

加密：C = (P+K) mod 26解密：P = (C-K) mod 26

PlayFair加密是一種多字元加密，每次加密兩個字元。它使用一個5×5的矩陣來進行加解密。該方法加密的是字母對而不是單純地將單個字母進行替換操作。PlayFair演算法很難破譯，因為用來對付簡單替換字母加密的頻率分析方法對它無效。頻率分析雖然有可能破譯出密文，但是要經過25×25=625鍾字母組合而不是25鍾可能出現的文字[15]Vigenere加密是一種多字元替換加密演算法。也就是說該加密演算法可以將一段純文字中的單字母替換為多字母密文。這種替換取決於字母在文中的位置。

Vigenere加密使用的是26×26的Vigenere字母表[15]柵欄加密技術是將明文按照對角線序列書寫並將行序列組合成密文的加密方法。在柵欄密碼中，我們將原文中的空格刪除並將字母寫到Z字形圖案中。破解柵欄密碼的關鍵就是柵欄數。[15]Hill密碼中，利用矩陣乘法的知識進行加密。它根據金鑰的大小將明文分解成子文字，並把每一個子文字與金鑰矩陣相乘得到密文文字矩陣。[15]加解密的等式如下(3)(4)：加密：C=PK mod 26解密：P=CK^-1 mod 26PS：這裡的C代表明文，P代表密文，K代表金鑰矩陣

2.2 文字資訊加密方法

Acharya等[1]提出了一種利用矩陣變換的影象加密方法。Cooper等[2]提出了一種利用帕斯卡三角的公鑰加密系統。Dinesh P. Baviskar等[3]開發了一種基於Android(安卓)系統的利用矩陣的資訊加解密演算法。加密演算法在保護機密資訊免遭黑手方面起著至關重要的作用。執行演算法需要消耗大量的計算機資源，如CPU壽命、記憶體和加密時間[6]。矩陣重排序的概念用於加密數字影象的例子也可以在本文中見到[10]。在[11]中，作者利用從SHA-512和MD5雜湊函式的隨機引數派生的金鑰開發了一種新的對稱密碼系統。在[14]中，利用了帕斯卡三角的新加密技術來加解密數字影象

三、要論述的加密方法

接下來要進行論述的方法引用帕斯卡三角概念進行替換和引用謝爾賓斯基三角概念進行置換從而加密資料。起初，明文字元以三角形排列。然後我們利用帕斯卡三角把每一個字母進行按位異或操作得到新的密文字母。謝爾賓斯基三角加密則是利用謝爾賓斯基三角來去的加密訊息的。

3.1 帕斯卡三角

帕斯卡三角是由二項式係數構成的三角形陣列。每行中的條目從左邊開始編號為k = 0，並且通常相對於鄰行中的數字交錯排列。行和列這兩個引數使得我們可以在帕斯卡三角形的第n行第k列找到相應的二項式係數(nk)，這種結構來源於如[4]中所說的帕斯卡三角原則中的二項式係數。那麼就有如下兩個等式(5)(6)： 其中 一個帕斯卡三角示例如圖1所示：

3.2 謝爾賓斯基三角

謝爾賓斯基三角是由一個等邊三角形按照如下方法連續去除一些三角形構成的：

a.從一個等邊三角形開始 
b.將其均分為四個全等的等邊三角形並去除中心的三角形 
c.對每個小三角形重複b的步驟

謝爾賓斯基三角的形成過程示例如圖2所示： 基於以上我們提出的概念，我們把加密過程分為兩個階段，例如階段Ⅰ(利用帕斯卡三角進行替換)和階段Ⅱ(利用謝爾賓斯基三角進行置換)

3.3 階段Ⅰ：(利用帕斯卡三角替換)

在傳送端，明文中的字元按照圖中的三角形(三角形-1)按行排列。基於上述公式(5)和(6)，藉助明文中的起始字元對其他字元進行異或操作(如三角形-2)。把這兩步加在一起得到加密後的密文。階段Ⅰ的字元替換過程如下：我們假設明文為“meet me at party”。將其按照上述方法排列而成的三角形-1如圖3所示。接下來填充字元，像這種情況下以字母“x”填充到三角形的末尾 利用帕斯卡三角原理替換後的三角形-2如圖4所示： 通過三角形-1和三角形-2獲取到的替換後的文字如圖5所示： 因此，在應用以上方法後我們的明文替換成了“MQQ9MUJYEU09REI”

3.4 階段Ⅱ：(利用謝爾賓斯基三角置換)

在謝爾賓斯基三角中，我們把奇數位的字元寫在前面，偶數位的字元寫在後面，謝爾賓斯基三角的示例如圖7所示 把階段Ⅰ的結果輸入到階段Ⅱ來獲得最終的密文。首先把階段Ⅰ的結果按圖8所示按位排列，並根據謝爾賓斯基三角的規則讀取密文 因此，我們得到了由“meet me at party”加密成的密文“MQQ9UJYEU0IM9RE”

3.5 加密演算法

輸入：明文 輸出：密文

步驟一：把明文放入一個[m,m]的矩陣中加密形成三角形-1

步驟二：新建一個基於帕斯卡三角規則的三角形，三角形-2，即，將處於邊緣的字元和0進行異或，處於裡面的字元和相鄰的字元進行異或

步驟三：把三角形-1中的字元和三角形-2中的字元相加的結果替換原字元

步驟四：重複步驟三的操作直至矩陣被遍歷 步驟五：按照謝爾賓斯基三角的規則讀取字元 步驟六：儲存密文

四、實驗結果及分析

我們提出的辦法是使用Java語言進行實驗。系統配置是處理器為Intel i5-5200U，主頻2.2GHz，RAM 4GB，Windows作業系統。使用多條不同長度的不同明文測試加密演算法。基於帕斯卡三角對明文進行替換，如表1所示。按照我們提出的方法密文中重複的字元會被替換成不同的字元。計算明文與密文之間的Hamming Distance(漢明距離)以量化位元差 表2給出了按照上面論述的替換和置換方法變換後的密文。明文中的字元被隨機地打亂散落於密文的各個位置。計算了明文與密文之間的Hamming Distance(漢明距離)後又觀察到位元差增大了 在應用替換和置換變換後，我們之前所論述方法的效果得到增強。從結果來看，明文中重複的字元對映到密文中的不同字元。因此，密文不易受密碼分析和字母頻率攻擊

五、總結

本文中，我們開發了一種使用帕斯卡和謝爾賓斯基三角形原理加解密文字資訊的新密碼系統。該方法非常簡單且易於實現因為它涉及用替換和置換技術加密文字。明文中的字元替換成隨機字元然後使用置換法將密文隨機改組。所論述的加密方法明顯滿足混淆和擴散的特性。使用所論述方法加密後的訊息不易受密碼分析和字母頻率攻擊

參考文獻

1.Acharya B, Patra S, and Panda G, “Image encryption by novel cryptosystem using matrix transformation”, Emerging Trends in Engineering and Technology出版社, 2008年. 
2.Cooper R.H, Fredericton NB, Hunter-Duvar R and Patterson W, “A more efficient public-key cryptosystem using the Pascal triangle”, World Prosperity Through Communications, IEEE International Conference(計算機與通訊國際會議), 1989年,第三卷,第1165頁 – 1169頁. 
3.Dinesh P. Baviskar, Sidhhant N. Patil and Onkar K. Pawar, “Android based message encryption/decryption using matrix”, International Journal of Research in Engineering and Technology(國際工程技術研究期刊), 第四卷, 第一期, 2015年1月. 
4.Edwards A.W.F, “Pascal‟s Arithmetical Triangle: The Story of a Mathematical Idea”. 
5.Hazem M. El bakry, Ali E. Taki El Deen and Ahmed Hussein Ali El Tengy, “A New Mobile Application for Encrypting SMS/Multimedia Messages on Android”, International Journal of Scientific & Engineering Research(國際科學與工程研究雜誌), 第四卷, 第十二期 2013年. 
6.Himani Agarwal and Monisha Sharma, “A Review of Text Encryption Techniques”, Asian Journal of Computer Science and Information Technology(亞洲電腦科學與資訊科技雜誌), 第四卷, 第五期, 第47頁-54頁, 2014年.
7.Punam V. Maitri, Rekha V. Sarawade, Mayuri P. Patil and Sarika T. Deokate, “MSC: Mobile Secure Communication Using SMS in Network Security: A Survey”, International Journal of Engineering Research & Technology(國際工程研究與技術雜誌), 第二卷, 第十一期, 2013年. 
8.Rohan Rayarikar, Sanket Upadhyay and Priyanka Pimpale , “SMS Encryption using AES Algorithm on Android”, International Journal of Computer Applications(國際計算機應用雜誌) (0975–8887) , 第五十卷, 第十九期, 2012年7月. 
9. Shobha Jha P U. Dutta P and Priyankgupta P , “SMS Encryption using NTRU Algorithms on Android Application”, International Journal of Scientific Engineering and Applied Science(國際科學工程與應用科學), 第二卷, 第一期, 2016年1月. 
10.Sivakumar T and Venkatesan R, “A Novel Image Encryption Approach using Matrix Reordering”, WSEAS Transactions on Computers雜誌, 第十二卷, 第十一期, 2013年. 
11.Sivakumar T and Anusha T, “A New Symmetric Cryptosystem using Randomized Parameters of SHA-512 and MD5 Hash Functions”, International Journal of Innovations in Engineering and Technology(國際工程與技術創新雜誌), 第六卷, 第四期, 2016年5月. 
12.Smile Markovski, Aleksandra Kuzmanovska, and Milivoj Simeonovsk, “A Protocol for Secure SMS Communication for Android OS”, ICT Innovations雜誌 2011年版, 第一百五十卷, Advances in Intelligent and Soft Computing, 第171頁-178頁, 2011年 
13.Sri Rangarajan, Sai Ram N and Vamshi Krishna N, “Securing SMS using Cryptography”, International Journal of Computer Science and Information Technologies(國際電腦科學與資訊科技期刊), 第四卷, 第二期, 第285頁–288頁, 2013年. 
14.Sugapriya K, Kishorekumar K and Anitha Kumari K, “A Novel Encryption Technique using Pascal Triangle for Image Cryptosystem”, National Conference on Research and Challenges in IT(全國IT研討會議), 2016年4月22日 – 23日, PSG College of Technology, Coimbatore 
15.William Stallings, “Cryptography and Network Security-Principles and Practice”, Pearson Education出版社, 新德里, 2013年

*參考來源： ION_METHOD_USING_PASCAL_S_TRIANGLE_BASED_SUBSTITUTION_AND_SIERPINSKI_TRIANGLE_BASED_PERMUTATION" target="_blank" ref="nofollow" rel="nofollow,noindex">academia.edu ，NaTsUk0 編譯整理，轉載請註明來自 FreeBuf.COM。