世界第一簡單密碼學（修訂版）

專欄 擴張版輾轉相除法

輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。

　 設 除以 ，餘數為 。

　若 ，則最大公因數即為 ，計算即完成。

　若 ，則 的組合置換為 和 ，然後再回到最初的步驟。

只要重覆　到　的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。

舉個實例，請以輾轉相除法求出1365和77的最大公因數。

　　1365＝17×77＋56 （← 依1365÷77＝17餘56的計算可知）

　　77＝1×56＋21　　 （← 依77÷56＝1餘21的計算可知）

　　56＝2×21＋14　　 （← 依56÷21＝2餘14的計算可知）

　　21＝1×14＋　　　 （← 依21÷14＝1餘7的計算可知）

　　14＝2×　＋0　　　（← 依14÷7＝2餘0的計算可知）

因此，最大公因數為7。只要依步驟計算便可確實得到結果，因此可讓人感到輾轉相除法的實用性。

一次不定方程式*的解之計算

接下來，對互質的20和17，請以輾轉相除法求最大公因數。

　　20＝1×17＋3（1）

　　17＝5×3＋2（2）

　　3＝1×2＋1（3）

　　2＝2×1＋0

由於直接可看出最大公因數為1，似乎並不需要使用輾轉相除法。

然而，為求出結果的算式卻具有相當大的利用價值喔！

*不定方程式：Diophantine equation。

首先，將式（1）、（2）、（3）移項，得到下列的3個式子。

　　（4）

　　 ＝　（5）

　　 　 ＝1（6）

接下來，將式（5）代入式（6）的　中，請注意3和17。

× 　 ＝ 3 （7）

接著，將式（4）代入式（7）的 3 中，請注意20和17。

6× 3

然後，將此一連串的步驟所得的結果改寫如下。

　　

將上式改寫為 ，而符合 的數皆為整數。這種形式的方程式就稱為一次不定方程式，可求出整數解的 和 。

也就是說，利用輾轉相除法的計算過程，、 時，可得一次不定方程式的整數解。此方法即為擴張版輾轉相除法，是非常具有利用價值的運算法。

一般而言，若設 和 為非0的整數，且 和 的最大公因數為 ，則一次不定方程式

　　

有整數解，而且可利用擴張版輾轉相除法求出一組解。然而，一次不定方程式的解並不僅有1組。方程式的所有的整數解皆可利用任意的整數 表示如下。

（8）

以模數運算計算倒數

若利用式（8）中所表示的解的公式，則一次不定方程式 的所有整數解可表示如右。

　　（6＋17（9）

時，解為。

將此代入一次不定方程式 。

　　

移項並整理式子。

　　（10）

若仔細看式（10），就可得知實際上它和下式意義相同。

　　17×13＝1mod 20（11）

在第168頁中，mod 的情況下，說明了「模數 中，解密金鑰 為加密金鑰 的乘法逆運算數」。意即，關於式（11）的模數20中，13為17的乘法逆運算數。

也就是說，若使用擴張版輾轉相除法，則可高效率地導出模數運算中的倒數。由於在公開金鑰密碼中，為了產生祕密金鑰（解密金鑰），算出倒數是必須的，因此密碼的世界中，也會讓擴張版輾轉相除法大大發揮。

雖可求出17mod 20的倒數 ，然而又該如何求出16mod 20的倒數為 呢？由於16和20的最大公因數為4，因此可用前述方法求出 。但是，為了求出倒數的一次不定方程式 時，則由於左式勢必為4的倍數，因此不存在整數解。換句話說，若在2個數非為互質的情況下，則無法求出倒數。藉由擴張版輾轉相除法導出倒數的方法，只能在2數為互質的情況下才成立。

最後，以輾轉相除法列出實際求出模數1001中，73的倒數 的計算過程。首先，以輾轉相除法，求出73和1001的最大公因數。

　　1001＝13×73＋52

　　73＝1×52＋21

　　52＝2×21＋10

　　21＝2×10＋1

　　10＝10×1＋0

因此可知，73和1001的最大公因數為1，也就表示73和1001互質。接下來，將這些式子改寫為求餘數的式子。

　　（12）

　　（13）

　　（14）

　　（15）

將式（14）代入式（15）取代10。

　　

　　（16）

將式（16）改寫為52和21的組合。

　　（17）

將式（13）代入式（17）取代21。

　　

　　（18）

將式（18）改寫為73和52的組合。

　　（19）

將式（12）代入式（19）取代52。

　　

　　（20）

將式（20）改寫為1001和73的組合。

　　（21）

將式（21）移項。

　　

由於此和96×73＝1mod 1001意義相同，因此模數1001中的73的倒數 為96。

專欄 擴張版輾轉相除法

輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。

　 設 除以 ，餘數為 。

　若 ，則最大公因數即為 ，計算即完成。

　若 ，則 的組合置換為 和 ，然後再回到最初的步驟。

只要重覆　到　的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。

舉個實例，請以輾轉相除法求出1365和77的最大公因數。

　　1365＝17×77＋56 （← 依1365÷7...

目前以網際網路為中心且被網絡化的資訊社會中，除了活用網路上的公開資訊及電子郵件的往來外，也多虧網路商店及網路銀行的普及，使我們的生活變得更便利。

然而，在享受網路時代的恩惠之外，

「安心安全、資訊安全、保護個人資料……，以及密碼」

這類令人感到些許不安的詞彙，每天都在生活中不斷出現。這到底是怎麼一回事呢？為什麼呢？

利用網際網路處理許多資訊時，其中總包含讓別人知道就糟糕的事，不希望別人知道、想要保密的資訊。例如，信用卡號、銀行帳號、病歷、貸款金額、電子郵件地址等，為了不輕易洩露給他人知道，保護資訊是不可或缺的。若資訊被他人惡意運用，很可能會引發犯罪案件。因此，保護資訊無疑是網絡化的資訊社會中最重要的課題。由於存在著許多這類的不安要因，因此為了得以安心且安全地使用網路服務，而構築出的基本技術即為「密碼」。

近年來，密碼系統大幅進步。這不僅是資訊安全相關的專家之領域，對於將便利的網際網路視為理所當然，並使用頻繁的我們而言，密碼也是必備的知識。

那麼，密碼系統是以何種構造達成資訊安全維護及個人資料的保護呢？

本書以漫畫為基礎，解說密碼系統的結構和功能。至於為了理解密碼系統所不可或缺的複雜數學，則以能讓任何人都可以理解的方式解說。期望讀者在沈浸於故事情節的同時，也能輕易地學習。當然，故事中也隱藏了密碼，希望您在閱讀本書的同時也能解開它。相信您在讀完本書後，勢必能習得密碼系統及資訊安全的基礎知識！

最後，衷心感謝非常照顧我的OHM社開發局的各位，以及負責作畫的HINOKI IDEROU大師。

目前以網際網路為中心且被網絡化的資訊社會中，除了活用網路上的公開資訊及電子郵件的往來外，也多虧網路商店及網路銀行的普及，使我們的生活變得更便利。

然而，在享受網路時代的恩惠之外，

「安心安全、資訊安全、保護個人資料……，以及密碼」

這類令人感到些許不安的詞彙，每天都在生活中不斷出現。這到底是怎麼一回事呢？為什麼呢？

利用網際網路處理許多資訊時，其中總包含讓別人知道就糟糕的事，不希望別人知道、想要保密的資訊。例如，信用卡號、銀行帳號、病歷、貸款金額、電子郵件地址等，為了不輕易洩露給他人知道，保護資...

前言
序章1
第1章　密碼學的基礎15
1-1　密碼學相關用語16
密碼學的基本用語20
加密金鑰　　和解密金鑰　　的關係21
1-2　古典加密系統24
凱撒密碼24
替代密碼 25
多字母密碼26
置換密碼 27
1-3　密碼的安全性 28
替代密碼的金鑰數 31
多字母密碼的金鑰數 32
置換密碼的金鑰數 32
可解讀的條件 35
絕對安全的密碼 35
安全密碼 37
第2章　共通金鑰（對稱金鑰）加密系統45
2-1　二進位數和XOR運算46
2-2　共通金鑰密碼是什麼？57
共通金鑰密碼的特徵 62
2-3　串流密碼的構造 63
2-4　區塊密碼的構造 66
CBC模式 69
2-5　　　　DES密碼的構造 70
Feistel密碼的基本構造 71
對合72
DES的加密金鑰之生成 75
DES的非線性函數f的構造 76
使用DES加密及解密的基本構造 77
2-6　DES密碼和AES密碼 78
AES密碼的概要 83
簡易版DES加密及解密實例 87
轉換為二進位資料 87
DES密碼的生成 87
DES密碼的解密 95
DES加密金鑰的生成 100
DES解密金鑰的生成 104
第3章　公開金鑰加密系統107
3-1　公開金鑰密碼的基礎 108
公開金鑰加密方式的主要種類 117
單向函數 118
RSA密碼的誕生 121
3-2　質數和質因數分解 122
質數判定 131
3-3　模數（餘數）運算136
模數運算的加法和減法 139
模數運算的乘法和除法 148
3-4　費馬小定理和歐拉定理154
數論之父　　費馬 155
費馬檢驗和假質數157
歐拉定理 158
數學家歐拉 159
兩個質數的乘積之歐拉函數 160
3-5　RSA密碼的構造 163
RSA密碼的加密及解密 165
RSA密碼的金鑰生成法 167
公開金鑰和秘密金鑰的做法 169
RSA密碼的生成 171
RSA密碼的解密 173
3-6　公開金鑰和離散對數問題 175
離散對數問題 176
ElGamal密碼的加密及解密 178
專欄　擴張版輾轉相除法 183
第4章　實際的密碼應用 187
4-1　混合密碼 188
4-2　雜湊函數和訊息認證碼192
竄改 192
防止竄改的對策 194
雜湊函數 195
盜用個人資料 196
防止盜用的對策 197
訊息認證碼的構造 198
否認（repudiation）是什麼？ 199
訊息認證碼的兩個缺點 201
4-3　數位簽章202
否認的對策 202
數位簽章的構造 203
中間人攻擊205
防止中間人攻擊的對策 206
憑證和認證中心 206
4-4　公開金鑰密碼基礎建設208
專欄　零知識互動式證明219
補充說明 225
參考文獻 227
索引 228

前言
序章1
第1章　密碼學的基礎15
1-1　密碼學相關用語16
密碼學的基本用語20
加密金鑰　　和解密金鑰　　的關係21
1-2　古典加密系統24
凱撒密碼24
替代密碼 25
多字母密碼26
置換密碼 27
1-3　密碼的安全性 28
替代密碼的金鑰數 31
多字母密碼的金鑰數 32
置換密碼的金鑰數 32
可解讀的條件 35
絕對安全的密碼 35
安全密碼 37
第2章　共通金鑰（對稱金鑰）加密系統45
2-1　二進位數和XOR運算46
2-2　共通金鑰密碼是什麼？57
共通金鑰密碼的特徵 62
2-3　串流密碼的構造 63
2-4　區塊密碼的...