worldexplorer

       在開始介紹McEliece的算法之前，我們要先簡單說明一點背景知識。Alice想要傳送一段訊息給Bob但是又不想被Eve知道訊息的內容，Alice就必須把她想傳送的訊息加密，Bob則把收到的訊息解密，如此一來就算Eve攔截到傳送中的訊息也只能看到加密後的版本 (加密跟解密方式晚點會介紹)。這裡Alice想傳送的訊息叫做明文(Plaintext)，而加密過後的訊息則叫做密文(Ciphertext)。

       McEliece的加密方法總共會有五個參數，其中三個參數 (代號S,G,P) 組成私鑰 (Private Key)，另外兩個參數 (代號G',t) 則會組成公鑰 (Public Key)。首先Bob (欲接收訊息者) 會設計出公鑰以及私鑰，顧名思義Bob會將公鑰公開而將私鑰自己藏起來，這麼一來大家都知道Bob的公鑰了。Alice就可以把自己想要傳送的訊息和Bob的公鑰相乘 (在電腦的世界裡我們的資料都會被量化成0跟1，所以你可以把Alice想傳送的訊息以及公鑰想像成一串0跟1組成的數字，這兩串數字乘起來就是加密的第一步)，接著Alice還會再加上一段誤差向量 (Error Vector)，代號寫作 e。

       具題來說Alice想傳送的訊息是一大串0跟1組成的數字我們叫做m，首先Alice把m切成m=[m1 m2 m3 ... ml]，其中每一段的長度都是k。G'則是一個大小是k乘n的矩陣，因此把[m1 m2 m3 ... ml]乘以G'後Alice會得到m' = [m1' m2' m3' ... ml']，現在每一段的長度從k變成n了。所以Alice把m'加上長度n的誤差向量e，其中誤差向量e的1是t個。為什麼要在意誤差向量的0跟1分別有幾個? 因為我們把m'加上誤差向量，如果誤差向量都是0那加完m'+0 = m'根本沒變，所以誤差向量的1越多就代表離m'改變越多。假設把密文代號成v，那麼Bob就會收到 v = mG'+e。接著Bob的任務就是把 v 還原成 m 好得知Alice原本的訊息。

       那麼Bob要怎麼解密呢? 這就是McEliece算法的天才之處了。Bob的公鑰 G' 算法就是把SGP相乘。也就是說Bob收到的訊息其實是 v = mSGP+e。所以Bob把 v 乘上 P^(-1)得到 mSG + e' (把eP^(-1)簡單寫乘e')。接著Bob把其帶入Goppa codes的解密法，對入門而言這邊如何運算沒那麼重要，重要的是Bob會得到miS，接著只要再乘以S^(-1)就可以得到原本的m了。

       這個做法的高明之處就在於私鑰其實被藏在公鑰裡面了，但是這個巧妙的設計方法讓攔截者即使得到公鑰也很難進一步推敲出私鑰的組成，因為分開三個相乘的矩陣實在太複雜了~