python希爾加密代碼

⑴ 希爾密碼原理

希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。

中文名
希爾密碼
外文名
Hill Cipher
原理
基本矩陣論
類別
替換密碼
提出者
Lester S. Hill
快速
導航
產生原因

原理

安全性分析

例子
簡介
希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。
每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。
注意用作加密的矩陣（即密匙）在必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。
產生原因
隨著科技的日新月異和人們對信用卡、計算機的依賴性的加強，密碼學顯得愈來愈重要。密碼學是一門關於加密和解密、密文和明文的學科。若將原本的符號代換成另一種符號，即可稱之為廣義的密碼。狹義的密碼主要是為了保密，是一種防止竊文者得知內容而設的另一種符號文字，也是一般人所熟知的密碼。
使用信用卡、網路賬號及密碼、電子信箱、電子簽名等都需要密碼。為了方便記憶，許多人用生日、電話號碼、門牌號碼記做密碼，但是這樣安全性較差。
為了使密碼更加復雜，更難解密，產生了許多不同形式的密碼。密碼的函數特性是明文對密碼為一對一或一對多的關系，即明文是密碼的函數。傳統密碼中有一種叫移位法，移位法基本型態是加法加密系統C=P+s(mod m)。一般來說，我們以1表示A，2表示B，……，25表示Y，26表示Z，以此類推。由於s=0時相當於未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整個系統只有m-1種變化。換言之，只要試過m-1次，機密的信息就會泄漏出去。
由此看來，日常生活中的密碼和傳統的密碼的可靠性較差，我們有必要尋求一種容易將字母的自然頻度隱蔽或均勻化，從而有利於統計分析的安全可靠的加密方法。希爾密碼能基本滿足這一要求。
原理
希爾加密演算法的基本思想是，將d個明文字母通過線性變換將它們轉換為d個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。[1]
希爾密碼是多字母代換密碼的一種。多字母代換密碼可以利用矩陣變換方便地描述，有時又稱為矩陣變換密碼。令明文字母表為Z，若採用L個字母為單位進行代換，則多碼代換是映射f：Z→Z。若映射是線性的，則f是線性變換，可以用Z上的L×L矩陣K表示。若是滿秩的，則變換為一一映射，且存在有逆變換K。將L個字母的數字表示為Z上的L維矢量m，相應的密文矢量c，且mK=c，以K作為解密矩陣，可由c恢復出相應的明文c·K=m。
在軍事通訊中，常將字元（信息）與數字對應（為方便起見，我們將字元和數字按原有的順序對應，事實上這種對應規則是極易被破解的）：
abcde…x y z
12345…242526
如信息「NOSLEEPPING」對應著一組編碼14,15,19,12,5,5,16,16,9,14,7。但如果按這種方式直接傳輸出去，則很容易被敵方破譯。於是必須採取加密措施，即用一個約定的加密矩陣K乘以原信號B，傳輸信號為C=KB（加密），收到信號的一方再將信號還原（破譯）為B=KC。

⑵ 大佬們看下我這希爾排序的Python代碼有啥錯誤，找了好久找不著，顯示：list index out of range

for循環那裡少寫了一個range

⑶ 世界上有多少種密碼

世界上有很多種密碼，主要分類有以下幾種：

1、摩斯密碼，最早是一些表示數字的點和劃，數字對應單詞，需要查找一本代碼表才能知道每個詞對應的數；

2、四方密碼，是一種對稱式加密法，由法國人發明，這種方法將字母兩個一組，採用多字母替換密碼達到加密的目的；

3、希爾密碼，是運用基本矩陣論原理的替換密碼，由法國人希爾在1929年發明；

4、波雷費密碼，是一種對稱式密碼，是首種雙字母取代的加密法，最早出現在一份1854年3月26日由查爾斯·惠斯登簽署的文件中，他的朋友波雷費勛爵普及了這個加密法；

5、三分密碼，三分密碼由Felix Delastelle發明。三分密碼是三維的，用3×3×3的公式進行加密，它是第一個應用的三字母替換密碼。

⑷ 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

演算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重復步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。