わんくま同盟やまだ ひとり勉強会 #3

素人の、素人による、誰のための?
暗号入門
やまだ@わんくま同盟
わんくま同盟やまだ ひとり勉強会 #3
アジェンダ
1. 暗号とは
1. 暗号ってそもそも何?
2. 暗号ってどうやってできてるの?
•
換字式、転置式
3. 暗号の強度/複数の暗号方式がある理由
•
差分解読
2. 暗号方式(1) - 共通鍵暗号方式
– DES を題材にして概要説明
•
DES, 3DES, AES(Rijndael)……
3. ハッシュ
– SHA-1を題材にして概要説明
•
暗号とは何が違うのか
4. 暗号方式(2) - 公開鍵暗号方式
– RSA を題材にして概要説明
•
•
どうして共通鍵だけでは足りないのか?
電子署名とかハイブリッド暗号方式とか
わんくま同盟やまだ ひとり勉強会 #3
暗号とは
鍵
暗号化
暗号アルゴリズム
復号
平文
(ひらぶん)
Plain Text
暗号文
Cipher Text
鍵
暗号化
復号
…… 平文を暗号文に置き換えること
…… 暗号文を平文に戻すこと
わんくま同盟やまだ ひとり勉強会 #3
暗号の原理
• 換字
(いわゆるシーザー暗号)
abcdefghijklmnopqrstuvwxyz
例:3文字分だけ文字をずらす
文字を別の文字で
置き換える
defghijklmnopqrstuvwxyzabc
• 転置
abcdefghijklmnopqrstuvwxyz
例:逆順にならべかえる
順番を入れ替える
zyxwvutsrqponmlkjihgfedcba
わんくま同盟やまだ ひとり勉強会 #3
暗号の解読手法
• 【手法1】頻度分析
– 暗号文の例:duhbrxvdglwvwrredglpvrpdg
– 最も使用頻度が高い文字:d,r (4回)
• 暗号化されたのが英文であることがわかっているとすると、
これらは母音(a,e,i,o,u) の可能性が高い。
– いくつか文字が埋まれば、それが他の解読のヒントになる
• 【手法2】差分解読
– 複数の暗号文を入手 → 差分をとる
• duhbrxvdglwvwrredglpvrpdg
すべての文字が一定間隔でずれている → 「シーザー暗号」であることがわかる
• gxkeuaygjozyzuuhgjosyusgj
• 【結論】シーザー暗号レベルでは容易に解読可能
– 定型文を多く含むほど、大量の暗号文を入手されるほど脆弱に
わんくま同盟やまだ ひとり勉強会 #3
暗号の特徴
• 暗号の性格
– 複雑な計算が必要
• 単純な暗号化では簡単に解読されてしまう
– 大きなメモリ容量が必要
• 性格上、作業ファイルの利用が困難
• 暗号に対する制約
– CPUやメモリに大きな負荷がかかる
– 実時間で処理が終わらないと、実用にならない
最適な暗号方式は、使用できるHW等や利用局面によって変わる
わんくま同盟やまだ ひとり勉強会 #3
共通鍵(secret key)暗号方式
トルストイ
Alice
平文
暗号化
チェーホフ
Carol
暗号文
?
傍
受
ピョートル
一世
暗号文
鍵(secret key)
Bob
復号
平文
鍵(secret key)
同じでなければならない
わんくま同盟やまだ ひとり勉強会 #3
共通鍵(secret key)暗号方式の特徴
• 特長
– そこそこ高速
– 情報の漏洩防止
• 課題
– 鍵管理
• 鍵をどうやって相手と共有するか?
• 鍵の安全な配送と更新
– 成りすましを検出できない
わんくま同盟やまだ ひとり勉強会 #3
DES (Data Encryption Standard)
• DES の特徴
– 共通鍵暗号
• 暗号化の鍵と復号の鍵が同一
– ブロック暗号
• 64ビット単位で暗号化・復号
• S BOX と呼ばれる変換テーブルを利用
– 暗号化と復号のロジック自体も対称
– 暗号鍵も64ビット
• 実質56ビット、パリティ8ビット
わんくま同盟やまだ ひとり勉強会 #3
ECBモードとCBCモード
• ECB (Electric Codebook) モード
平文
8バイト
暗号器
暗号文
8バイト
8バイト
暗号器
8バイト
8バイト
暗号器
8バイト
8バイト
暗号文
暗号器
8バイト
8バイト
復号器
平文
8バイト
復号器
8バイト
8バイト
8バイト
復号器
8バイト
8バイト
復号器
8バイト
• CBC (Cipher Block Chaining) モード
平文
8バイト
8バイト
8バイト
8バイト
暗号文
8バイト
8バイト
8バイト
8バイト
初期
ベクトル
復号器
暗号器
暗号器
暗号器
復号器
復号器
復号器
暗号器
初期
ベクトル
暗号文
8バイト
8バイト
8バイト
8バイト
平文
8バイト
8バイト
8バイト
わんくま同盟やまだ ひとり勉強会 #3
8バイト
3DESと AES
• 3DES (Triple DES)
– 暗号鍵は128ビット
– 暗号化
• 鍵の前半64ビットで、DESによる暗号化
• 鍵の後半64ビットで、DESによる復号
• 鍵の前半64ビットで、DESによる暗号化
– 復号
• 鍵の前半64ビットで、DESによる復号
• 鍵の後半64ビットで、DESによる暗号化
• 鍵の前半64ビットで、DESによる復号
• AES (Advanced Encryption Standard)
– DES に続く米国暗号標準。Rijndael 暗号を採用
わんくま同盟やまだ ひとり勉強会 #3