練習問題 n = 7, k = 4, p = 7 – 4 = 3 とし，巡回符号を構成する． G(x) = x3 + x2 + 1 が生成多項式に使えることを確かめよ 0110 を符号化せよ 0001100 は正しい符号語か，判定せよ 回答例は http://narayama.naist.jp/~kaji/lecture/ に掲載 1 今日の講義 第四部：情報を不正者から隠す 対称鍵暗号系（今回） 鍵共有法，公開鍵暗号への導入（次回） 公開鍵暗号（次々回） 2 秘密の情報通信 情報を，他人に知られることなく伝えたい...古代からある要求 もっとも原始的なアプローチ： 信頼できる人物にメッセージを託す 他人には見つからないように，情報を送受信する 他のメッセージの中に，秘密のメッセージを埋め込む 3 ステガノグラフィ 他のメッセージの中に，秘密のメッセージを埋め込む 一見すると通常の手紙だが，見る人が見ると，秘密の メッセージが読み取れる ⇒ 暗号用語ではステガノグラフィと呼ぶ（秘匿通信） ステガノグラフィの例： あぶり出し 手紙の文字にマーキング（小さな穴をあける） 画像ファイルを微細に変更する ⇒ 電子透かし 4 ステガノグラフィの問題点と現状 「秘密情報が埋め込まれている」ことがバレてしまうと... 秘密情報の解明が，比較的容易 「秘密ナシ」バージョンと，簡単にすり替え可能 工学的な意味で，十分成熟した技術とはなっていないが， 暗号技術と組み合わせて使われることもある 5 暗号とは 暗号とは．．． 「通信の内容が、当事者以外には解読出来ないように、普通 の文字・記号を一定の約束で他の記号に置き換えたもの。」 （新明解国語辞典，第５版） 主な用途： 通信路の保護 （盗聴者に情報を漏らさない） 記録情報の保護 （覗き見から秘密を守る） 6 操作と用語 平文（ひらぶん，へいぶん） plaintext： 盗聴や覗き見から守りたい情報 通話内容，日記，メイルの文章，プログラムetc. 「通信の内容が、当事者以外には解読出来ないように、普通 の文字・記号を一定の約束で他の記号に置き換えたもの。」 暗号化 encrypt 暗号文 ciphertext 復号 decrypt 一定の約束で置き換えられた記号を， 元の文字・記号に復元する操作 7 単純な暗号：シーザー暗号 非常に単純な暗号化方式： 文字を何文字分か「ずらす」ことで，暗号化を行う方法 A ↓ 暗号文の文字 D 平文の文字 B ↓ E C ↓ F ．．． ．．． Y ↓ B Z ↓ C J. Caesar 平文：THISISASAMPLETEXT 暗号文：WKLVLVDVDPSOHWHAW 暗号の鍵：何文字分ずらしたか．．．上の例では３文字 鍵の種類＝文字数 （上の例では 26 通り） 平文が意味のある文章ならば，鍵の総当りによる解読が可能 8 少しマシな暗号：換字暗号 （単純な）換字暗号 平文の文字と暗号文の文字の対応表を鍵とする 暗号化・復号は，単純な文字の置き換え A ↓ 暗号文の文字 E 平文の文字 B ↓ K C ↓ A ．．． ．．． Y ↓ Z Z ↓ G シーザー暗号は，換字暗号の特殊なケース 鍵の種類＝文字数の階乗（上の例では 26!=4x1026通り） 総当りで調べるには，鍵の種類が多すぎる 9 換字暗号の解読 換字暗号の弱点： 同じ文字はいつも同じ文字に置き換えられる 平文によっては，文字の出現頻度に偏りがある 暗号文の文字出現頻度から，鍵が推測可能な場合も 英語の文章： E, T, A, S ,O, N などが頻繁に出現する 暗号文において頻繁に出現する文字 ．．．上の文字のどれかである可能性が高い A.C. Doyle, The Adventure of the Dancing Men コナン・ドイル：踊る人形 (1903) 10 頻度攻撃 information as a concept has many meanings the concept of information is a b c d 典型的な英文 8.6% 1.4% 2.8% 3.8% zpunim gt oncuit 未知の utqvgwp gw h 暗号文 antaubz spgap nigqgthvvm cuigluw eino h 8.4% → a x a c theory in modern english is a concept which originally derives from classical greek 機密情報 1.5% → b 2.7% → c 3.8% → d 11 換字暗号の改良 一対多の換字暗号 平文の一文字を，複数種類の文字に置換 複数文字，単語単位での換字暗号 king→mountain, castle →piano, … 文字の対応関係を，徐々に変化させる Vigenère暗号，エニグマ暗号など 平文に関する統計的な情報が，少ないながらも観測可能 ⇒現在の計算機パワーの前では，ほとんど無力 12 絶対に安全な暗号 使い捨て暗号 (one-time pad)： 鍵は，平文と同じ長さのランダムな文字列 暗号化：平文と鍵系列を加算 復号：暗号文から鍵系列を減算 平文 鍵系列 暗号文 0110 1101 0111 0100 1011 0101 1010 1011 1101 1000 1101 1111 暗号文 鍵系列 復号結果 1101 1000 1101 1111 1011 0101 1010 1011 0110 1101 0111 0100 受信者 共有 送信者 13 使い捨て暗号の特徴 鍵が真正乱数ならば，情報理論的に安全 （無限の計算能力があっても，解読できない） 一度使った鍵は，再利用できない 非常に長い鍵が必要となり，効率が悪い コストを度外視し，とにかく安全性を確保したい場合には有効 軍事暗号としては，有力な選択肢の一つ 商用暗号としては「使えない」 14 軍事暗号と商用暗号：条件の違い 軍事暗号： 自分で開発して自分で使う 抜群の技術力と資金力 商用暗号： 開発者と使用者が異なる コスト的要因が無視できない ⇒ 異なる目標，異なる条件，異なるアプローチ... 15 商用暗号：セキュリティに関する３つの要件 中身が公開されたものだけを信用する 多くの研究者に「叩かれても生き残っている」品質 秘密方式には，トラップが存在する可能性も排除できない 実績のあるものを重視する 安全性の検証には，それなりに時間がかかる 斬新であることは，そのことだけでもリスクが高い 安全性とコストとのトレードオフを意識する 「守りたい情報の価値 < 攻撃にかかるコスト」で十分 システム運用のコストも，十分意識して 16 DES (Data Encryption Standard)の歴史 1973 NIST（米国標準規格局）が暗号アルゴリズムを公募 1974 IBMが，同社のLucifer暗号の改良版を応募 （この間，安全性に関する評価が原則公開で行われる） 1977 「データ暗号化のための標準方式」として採用 (Data Encryption Standard, DESの名前の由来） 1990 Biham, Shamirによる「差分攻撃」 1993 松井による「線形攻撃」（国際的な発表は94年） 1997 DESの次世代方式(AES)を公募 現在...AES選定済み しかし，DESも広く利用されている 17 １段目 ２段目 L16 １６段目 暗号文 64 IP-1 f R16 R15 L15 R1 R2 f f R1 32 L2 L1 L1 32 IP 64 平文 48 48 48 RK16 RK1 56 RK1 56 鍵 DESの基本構造 青字：ビット数 18 DESの構成要素１ IP：初期置換 ［６４ビット→６４ビット］ ビット位置の置換を行う IP-1：最終置換 ［６４ビット→６４ビット］ IPの逆置換 RKi：ラウンド鍵生成部 ［５６ビット→５６×４８ビット］ ５６ビットの出力：入力ビットの置換 ４８ビットの出力：入力ビットの部分集合（ラウンド鍵） 64 IP 64 56 64 IP IP-1 64 48 RK IP i 56 19 DESの構成要素２ f ：f 関数 ［４８×３２ビット→３２ビット］ 32 48 拡大置換 拡大置換 48 S-box置換 S-box置換 S1 32 P-box置換 f 関数 S2 S3 P-box置換：ビット位置の置換 32 20 DESのラウンド操作 以下の一連の操作．．．ラウンド操作 ラウンド鍵と右32ビットブロックから f 関数を計算 f 関数値を左32ビットブロックに足す 左ブロックと右ブロックを交換する DES全体は，１６ラウンドからなる ただし，最後のラウンドだけブロック交換は行わない Li Ki+1 f Li+1 Li 1 Ri Ri Ri+1 Ri 1 Li f ( Ri , Ki 1 ) このような構造を「Feistel 構造」と呼ぶ 21 ラウンド操作の可逆性 Li+1, Ri+1 がわかったとき Ri はわかる Ki+1 が不明なら，Li も不明 Ri Ki+1 拡大置換 48 Li Ri Ki+1 f S-box置換 Li+1 Ri+1 Li 1 Ri Ri 1 Li f ( Ri , K i 1 ) 32 P-box置換 f 関数 f (Ri, Ki+1) ラウンド鍵がわからないと，ラウンド操作を逆にたどれない 22 L16 平文 IP-1 f R16 R15 L15 R1 R2 f f R1 L2 L1 L1 IP 暗号文 鍵 RK1 RK15 RK16 DESの復号 （青枠内は）暗号化のときと完全に同じ操作 23 復号の原理（１） 暗 号 化 の 16 段 目 L15 R15 K16 f L16 L15 R16 R15 K16 f L16 R16 L16 R16 IP-1 IP 復 号 の 1 段 目 f K16 f K16 24 復号の原理（２） L15 R15 K16 f L16 L15 R15 K16 f R16 同じ値 L16 R16 f K16 K16 f R15 L15 25 復号の原理（３） L15 R15 K16 f 暗 号 化 の 15 段 目 L14 R14 K15 f L15 R15 R15 L15 同じ値 K16 f R15 L15 復 号 の 2 段 目 K15 f R14 L14 26 復号の原理：まとめ ラウンド鍵の与え方を逆転すると，暗号化装置を使って復号 ができる （involution構造） 原理： 暗号化のIP-1と復号のIPが，互いをキャンセルする 暗号化の16段目と復号の1段目が，互いをキャンセル 暗号化の15段目と復号の2段目が，互いをキャンセル : 暗号化の1段目と復号の16段目が，互いをキャンセル 暗号化のIPと復号のIP-1が，互いをキャンセルする 復号の結果得られる値は，暗号化装置への入力と同じ 27 DESの安全性（１） 鍵を知らない攻撃者が，解析的に解読すること ．．．ほぼ不可能（正確には，誰も方法を発見していない） DES解読器 制作費 25万ドル 鍵の総当り攻撃 暗号文攻撃または既知平文攻撃を想定 ハードウェアによる専用解読器の設計 インターネット上の多数の計算機による，分散計算 1999年の段階．．．10万台，22時間で解読に成功 ムーアの法則：計算機性能は18ヶ月で2倍になる 現在は，さらに危険な状況 28 DESの安全性（２） もう少し理論的な方向からのアプローチ 差分攻撃法：Biham, Shamirにより1990年に提唱 差が特定の値になっている平文の組を多数使用 DES開発時に，想定済み？ 線形解読法：三菱電機の松井氏により1993年に提唱 暗号文・平文の特定数ビットからなる線形式が，偏った 値となることを利用した攻撃法 望ましい暗号の構造を示唆するという意味で，重要 29 DESの安全性：まとめ DESは，もはや絶対安全とはいえない 計算機能力の向上 インターネットを使った大規模な分散計算 ⇒ 鍵の総当り攻撃が可能に 差分攻撃，線形攻撃など，攻撃技術の発達 ただし，誰でも簡単に解読できる，というほどではない 「解読のコスト＜守りたい情報の価値」となる場合が問題 「解読のコスト」が急速に小さくなっている 30 DESに関する「疑惑」 DESには，設計者しか知らない弱点が仕込まれているのでは？ なぜなら，そこにNSAが関与しているから．．． NSA: 米国国家安全保障局 CIA, FBI, 軍の情報機関を統括する組織 政府は，長らくその存在を認めなかった 最近では，「エシュロン」への関与が噂に 鍵の長さが，IBM提案の半分に短縮された S-box置換の中身が，NSAの選定したものに入れ替えられた NSAは，線形解読法が可能であることを知っていたらしい ⇒噂の真相は明らかになっていない 31 新しい暗号標準 DESに変わる新しい暗号方式が必要．．． Advanced Encryption Standard, AES NIST （米国技術標準局）が公募 １２カ国から１５種類のアルゴリズムが提案される 1999 候補を５種類に絞り込む 2000 ベルギーからの提案 “Rijndael” が選定される AES Conference をベースに，徹底した公開討論 2001 FIPSとして認定 1997 今後，徐々にDESに取って代わっていく，はず 32 本日のまとめ 暗号の基礎 DESについて 33 練習問題 以下に示す換字暗号の暗号文を解読せよ （ただし，アルファベット以外の記号は換字していない） usawlu rcunsac bsaelrsn fhs blyan emt fylthx fl wlmfh cqyvec lu fhmywncx, uscyax wvg xscyw cqfsy fhs qlyrsy qyssnlr qvdhfsy cun ucfvluca ascnsy eyvsn fscyw lq ilx bhsu fhs flmyucrsuf bcw cbcynsn fl fhs elufvusuf qly fhs qvywf fvrs. bvfh fhvyfx qvks ncxw zsqlys fhs wleesy whlbtvses oveow lqq vu ilhcuuswzmyd, fhs fylthx fhcf fhvyfx fbl fscrw cys hltvud fl avqf elrs imax sasksufh vw czlmf fl srzcyo lu fhs qvuca asd lq vfw blyan flmy. 参考： http://narayama.naist.jp/~kaji/crypto/index.html 34
© Copyright 2024 ExpyDoc
![BELL DESIGN - 図面 #47 [1D-04917(WJ0019)] A1横 - ジェーイーエル](http://s3.expydoc.com/store/data/000541186_1-71436bd2356cd8f6cbade1f1f164b781-250x500.png)
