n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

(1)

1. はじめに

モバイルネットワークの普及に伴い，ネットワークセキュリティを脅かすDoS攻撃(Denial of Service Attack)が問題となっている．DoS攻撃対策の一例として，共通鍵を事前に共有している場合はHMAC (Hash-based Message Authentication Code)を用いたパケット認証（以下，MAC 認証）を利用することができる．しかし，この認証方式ではパケット長が長いと処理時間が長くなる．

そこで，共通鍵とシーケンス番号のみを用いた簡易認証方式を提案する．この方式では，共通鍵とシーケンス番号から生成した短いハッシュ値をパケット内に付加し，その値を最初に検証する．これにより，不正パケットのほとんどを高速に検出することが可能となる．

本稿では，実験による評価を行い，提案方式の有用性を示す．実験においては，移動透過性と通信接続性の両者を同時に実現するNTMobile (Network Traversal with Mobility) [1]^{を用いた．}

2. 既存のパケット検証処理

IPsec (IP security)のESP (Encapsulating Security Payload) における，パケット受信時のDoS攻撃防止処理を説明する．

パケット検証はリプレイ攻撃チェック，MAC認証の順に行い，不正パケットであると判定した場合にはその時点で破棄を決定し，以降の処理は行わない．ここで，リプレイ攻撃とは攻撃者が正規のパケットを盗聴し，それを再送する攻撃である[2]．リプレイ攻撃チェックはこれを阻止するための処理であり，リプレイ防御ウィンドウと呼ばれるビットマスクを用いて受信を許可するシーケンス番号の範囲を決定することで，リプレイ攻撃パケットを検出する．リプレイ攻撃では過去に送信された正規のパケットを攻撃に利用するため，MAC認証では検出できず，リプレイ攻撃チェックは必須である．MAC認証まで成功した場合は正規のパケットとみなし，リプレイ防御ウィンドウの更新を行う．

NTMobileは，移動透過性と通信接続性の両者を同時に

実現する技術であり，IPsecと同様にエンドツーエンドのセキュリティを実現することができる．NTMobileのパケット検証はESPと同様で，リプレイ攻撃チェック，MAC^認証の順に行い，正規のパケットであればリプレイ防御ウィンドウの更新を行う．

3. 提案方式

提案方式では，送信側は，通信に用いる共通鍵とシーケンス番号を用いて8bitのハッシュ値（以下，簡易ハッシュ値）を生成してパケットに付与する．ハッシュ関数は，演算時間の短いFNV-1(32bit)を用いることとする．受信側は，

最初に簡易ハッシュ値を計算し，受信パケットに格納された値と比較する．これらの値が不一致であれば不正パケットであると判定して破棄し，一致していればリプレイ攻撃チェックに進む．以後の処理は，既存のパケット検証処理と同様で，リプレイ攻撃チェック，MAC認証の順に行い，正規のパケットであればリプレイ防御ウィンドウの更新を行う．提案方式はESP，NTMobile双方に適用できるが，パケット内に，簡易認証に係るフィールド（8bit）を追加する必要がある．

4. 実験と評価

4. 1 検証時間の測定

MAC認証範囲を1,036Byteとしてパケット検証処理を

100,000回実行した際の，処理時間の平均値を表1に示す．

表1:検証時間の実測値 t_s[µs] t_r[µs] t_m[µs]

0.536 0.414 3.835

表2:不正パケット検出率簡易認証あり簡易認証なし

P_s 9.961×10⁻¹ 0

P_r 1.819×10⁻¹² 4.657×10⁻¹⁰ P_m 3.906×10⁻³ 9.999×10⁻¹

表3:正規のパケットの検証時間 t_u[µs] 簡易認証なし[µs] 簡易認証あり[µs]

0.561 4.810 5.346

ここで，t_sは簡易認証に要する時間，t_rはリプレイ攻撃チェックに要する時間，tmはMAC認証に要する時間である．

4. 2 不正パケットの検証時間

不正パケットが簡易認証で破棄される確率，リプレイ攻撃チェックで破棄される確率，MAC認証で破棄される確率をそれぞれP_s,P_r,P_mとすると，不正パケットの検証時間の平均値E^は式(1)^{のようになる．}

E=t_sP_s+(t_s+t_r)P_r+(t_s+t_r+t_m)P_m (1) これに表 1の実測値，および表 2の不正パケット検出率を適用すると，

E=0.553[µs] (2)

となった．一方，簡易認証を適用しない場合は，

E|_P_s_=0,_t_s₌₀=4.249[µs] (3) となる．この結果から，簡易認証により，不正パケットの検証時間を約1/8に短縮でき，不正パケットによるDoS攻撃耐性が大きく向上することが期待できる．

4. 3 正規のパケットの検証時間

攻撃がない状態においては，パケット検証に常に簡易認証処理が加わるため負荷が増えることになる．そこで，この増加した負荷が全体の処理時間に与える影響を調査した．

正規のパケットの検証処理を100,000回実行した際の，リプレイ防御ウィンドウ更新処理時間の平均値t_uと，全体の処理時間の理論値を表 3に示す．提案手法ではt_sが加わるため全体の検証処理時間は若干長くなるものの，この後の復号処理時間（MAC認証の約10倍），さらには正規の受信処理時間を考慮すると影響は極めて小さいと言える．

5. まとめ

本稿では，共通鍵とシーケンス番号のみを用いた簡易認証方式を提案し，実験によりその有用性を示した．今後，提

案方式をNTMobileに正式仕様として組み込む予定である．

参考文献

[1] 上醉尾一真ほか: IPv4/IPv6混在環境で移動透過性を実現するNTMobileの実装と評価,情報処理学会論文誌, Vol. 54, No.10, pp.2288–2299 (2013).

[2] Rescorla, E., et al: Guidelines for Writing RFC Text on Security Considerations, RFC 3552, IETF (2003).

(2)

(3)

ᵏᵍᵓᵑ

n ⛣ື㏻ಙ➃ᮎ䛾ᬑཬ

n 䜲䞁䝍䞊䝛䝑䝖฼⏝䛾㟂せቑຍ

n 䝛䝑䝖䝽䞊䜽䝉䜻䝳䝸䝔䜱䜈䛾⬣ጾ

n

ᬯྕ໬㏻ಙ䛻䛚䛔䛶䜒᭷ຠ䛺ᨷᧁ

n 䝸䝥䝺䜲ᨷᧁ 㻔㻾㼑㼜㼘㼍㼥㻌㻭㼠㼠㼍㼏㼗㻕

n 㻰㼛㻿ᨷᧁ 㻔㻰㼑㼚㼕㼍㼘㻌㼛㼒㻌㻿㼑㼞㼢㼕㼏㼑㻌㻭㼠㼠㼍㼏㼗㻕

(4)

ᵐᵍᵓᵑ

n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻭㼠㼠㼍㼏㼗㼑㼞

㻼㼍㼏㼗㼑㼠㻼㼍㼏㼗㼑㼠

(5)

ᵑᵍᵓᵑ

n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

㻭㼠㼠㼍㼏㼗㼑㼞

㻼㼍㼏㼗㼑㼠

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

(6)

ᵒᵍᵓᵑ

n 㻾㻲㻯㻞㻠㻜㻝㻌㻔㻵㻼㼟㼑㼏㻌㼂㼑㼞㻚㻞㻕䛷ᶆ‽໬

n 䝅䞊䜿䞁䝇␒ྕ䛾౑⏝

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻜㻜㻜㻜㻜㻜䈈㻏㻝

㻼㼍㼏㼗㼑㼠㻏㻝㻼㼍㼏㼗㼑㼠

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

ཷಙ≧ἣ

㻜䠖ᮍཷಙ䠈㻝䠖ཷಙ῭䜏

(7)

ᵓᵍᵓᵑ

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

n

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻝㻜㻜㻜㻜㻜䈈㻏㻝

㻼㼍㼏㼗㼑㼠

㻏㻝㻼㼍㼏㼗㼑㼠

㻜䠖ᮍཷಙ䠈㻝䠖ཷಙ῭䜏 ኴᯟ䠖䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

ཷಙ≧ἣ

(8)

ᵔᵍᵓᵑ

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

n

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻝㻜㻜㻜㻜㻜䈈㻏㻝

㻼㼍㼏㼗㼑㼠㻏㻞㻼㼍㼏㼗㼑㼠

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

ཷಙ≧ἣ

(9)

ᵕᵍᵓᵑ

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

n

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻝㻝㻜㻜㻜㻜䈈㻏㻞

㻼㼍㼏㼗㼑㼠

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

ཷಙ≧ἣ

(10)

ᵖᵍᵓᵑ

n 䝸䝥䝺䜲ᨷᧁᐇ᪋

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻝㻝㻜㻜㻜㻜䈈

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

ཷಙ≧ἣ

(11)

ᵗᵍᵓᵑ

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ῭䜏䛸ุᐃ 䝸䝥䝺䜲ᨷᧁ䛸䜏䛺䛧䛶◚Რ

㻭㼠㼠㼍㼏㼗㼑㼞

1 2 3 4 5 6

㻝㻝㻜㻜㻜㻜䈈㻏㻝

㻼㼍㼏㼗㼑㼠

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

(12)

ᵏᵎᵍᵓᵑ

㻼㼍㼏㼗㼑㼠㻼㼍㼏㼗㼑㼠

n ཷಙഃ䛻㐣๫䛺㈇Ⲵ䜢୚䛘䜛䛣䛸䛷䝃䞊䝡䝇䜢୙⬟䛻䛥䛫䜛ᨷᧁ

㻭㼠㼠㼍㼏㼗㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻼㼍㼏㼗㼑㼠㻼㼍㼏㼗㼑㼠㻼㼍㼏㼗㼑㼠

(13)

ᵏᵏᵍᵓᵑ

n 㻹㻭㻯ㄆド

n

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

n

䝟䜿䝑䝖䛾䝕䞊䝍㒊䛸ඹ㏻㘽䜢⏝䛔䛶㻹㻭㻯䜢⏕ᡂ

㻿㼑㼚㼐㼑㼞

㻰㼍㼠㼍

㻹㻭㻯

㻾㼑㼏㼑㼕㼢㼑㼞

(14)

ᵏᵐᵍᵓᵑ

n 㻹㻭㻯ㄆド

n

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

n

䝟䜿䝑䝖䛾䝕䞊䝍㒊䛸ඹ㏻㘽䜢⏝䛔䛶㻹㻭㻯䜢⏕ᡂ

㻰㼍㼠㼍㻹㻭㻯

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

(15)

ᵏᵑᵍᵓᵑ

n 㻹㻭㻯ㄆド

n

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

n

ཷಙഃ䛿㻹㻭㻯䜢⏕ᡂ䛧䛶䝟䜿䝑䝖䛾㻹㻭㻯䛸ẚ㍑

㻰㼍㼠㼍㻰㼍㼠㼍

㻹㻭㻯

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

(16)

ᵏᵒᵍᵓᵑ

n 㻱㻿㻼㻌㻔㻱㼚㼏㼍㼜㼟㼡㼘㼍㼠㼕㼚㼓㻌㻿㼑㼏㼡㼞㼕㼠㼥㻌㻼㼍㼥㼘㼛㼍㼐㻕

n

㻻㻿㻵ཧ↷䝰䝕䝹䛾䝛䝑䝖䝽䞊䜽ᒙ䠄➨㻟ᒙ䠅䛻䛚䛡䜛

୍⯡ⓗ䛺䝉䜻䝳䝸䝔䜱䝥䝻䝖䝁䝹䠄㻾㻲㻯㻠㻟㻜㻟䠅

n

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽䠈㻹㻭㻯ㄆド䛾㡰䛻⾜䛖

n 䝸䝥䝺䜲ᨷᧁ䝟䜿䝑䝖䛿㻹㻭㻯ㄆド䛷䛿᳨ฟ䛷䛝䛺䛔

n 䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽䛾᪉䛜ฎ⌮᫬㛫䛜㏿䛔

(17)

ᵏᵓᵍᵓᵑ

n 㻺㼀㻹㼛㼎㼕㼘㼑㻔㻺㼑㼠㼣㼛㼞㼗㻌㼀㼞㼍㼢㼑㼞㼟㼍㼘㻌㼣㼕㼠㼔㻌㻹㼛㼎㼕㼘㼕㼠㼥㻕

^{㻖㻝㻌㻖㻞}

n

⛣ື㏱㐣ᛶ䛸㏻ಙ᥋⥆ᛶ䛾୧⪅䜢ྠ᫬䛻 ᐇ⌧䛩䜛ᢏ⾡

n ⛣ື㏱㐣ᛶ䠖㏻ಙ୰䛻䝛䝑䝖䝽䞊䜽䛜ษ䜚᭰䜟䛳䛶䜒

㏻ಙ䜢⥅⥆䛷䛝䜛ᛶ㉁

n ㏻ಙ᥋⥆ᛶ䠖䝛䝑䝖䝽䞊䜽⎔ቃ䛻㛵䜟䜙䛪㏻ಙ䜢㛤ጞ䛩䜛䛣䛸䛜䛷䛝䜛ᛶ㉁

n

㻵㻼㼟㼑㼏䛸ྠᵝ䛾䝉䜻䝳䝸䝔䜱䜢ഛ䛘䜛

n 䝟䜿䝑䝖᳨ド䛿䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽䠈㻹㻭㻯ㄆド䛾㡰䛻⾜䛖

㻖㻝㻌ୖ㓩ᑿ୍┿䠈㕥ᮌ⚽࿴䠈ෆ⸨ඞᾈ䠈Ώ㑔 ᫭䠖㻵㻼㼢㻠㻛㻵㻼㼢㻢㻌ΰᅾ⎔ቃ䛷⛣ື㏱㐣ᛶ䜢ᐇ⌧䛩䜛㻺㼀㻹㼛㼎㼕㼘㼑䛾ᐇ⿦䛸ホ౯䠈

᝟ሗฎ⌮Ꮫ఍ㄽᩥㄅ䠈㼂㼛㼘㻚㻌㻡㻠㻘㻌㻺㼛㻚㻌㻝㻜㻘㻌㼜㼜㻚㻌㻞㻞㻤㻤䇵㻞㻞㻥㻥㻌㻔㻞㻜㻝㻟㻕㻚

㻖㻞㻌⣡ᇽ༤ྐ䠈ඵ㔛ᰤ㍜䠈㕥ᮌ⚽࿴䠈ෆ⸨ඞᾈ䠈Ώ㑔 ᫭䠖ᐇ⏝໬䛻ྥ䛡䛯㻺㼀㻹㼛㼎㼕㼘㼑䝣䝺䞊䝮䝽䞊䜽䛾ᐇ⿦䛸ホ౯䠈

➨㻤㻞㻌ᅇ㻹㻮㻸䞉➨㻡㻟㻌ᅇ㼁㻮㻵㻌ྜྠ◊✲Ⓨ⾲఍䠈㻺㼛㻚㻌㻠㻢㻘㻌㼜㼜㻚㻌㻝䇵㻤㻌㻔㻞㻜㻝㻣㻕㻚

(18)

ᵏᵔᵍᵓᵑ

n ᪤Ꮡ䛾䝟䜿䝑䝖᳨ド䛾ㄢ㢟

n

䝟䜿䝑䝖㛗䛜㛗䛔䜋䛹㻹㻭㻯ㄆド䛾ฎ⌮᫬㛫䛜㛗䛟䛺䜛

n 䝟䜿䝑䝖᳨ドฎ⌮䛾኱༙䛜㻹㻭㻯ㄆド

኱㔞䛾䝟䜿䝑䝖䜢ฎ⌮䛩䜛䝃䞊䝞➼䛷䛿㻰㼛㻿ᨷᧁ䜢㜵ᚚ䛩䜛䛯䜑䛻

ᑡ䛧䛷䜒㏿䛟୙ṇ䝟䜿䝑䝖䜢᳨ฟ䛧䛯䛔

(19)

ᵏᵕᵍᵓᵑ

n ⡆᫆ㄆド

n

䝅䞊䜿䞁䝇␒ྕ䛸ඹ㏻㘽䛛䜙⡆᫆䝝䝑䝅䝳್䠄㻤㼎㼕㼠䠅䜢

⏕ᡂ

㻏㻝

㻿㼑㼚㼐㼑㼞

㻴㼍㼟㼔

㻾㼑㼏㼑㼕㼢㼑㼞

(20)

ᵏᵖᵍᵓᵑ

n ⡆᫆ㄆド

n

⏕ᡂ䛧䛯⡆᫆䝝䝑䝅䝳್䜢䝟䜿䝑䝖䛻௜ຍ䛧䛶㏦ಙ

n ⡆᫆䝝䝑䝅䝳್䜢᱁⣡䛩䜛䝣䜱䞊䝹䝗䠄㻤㼎㼕㼠䠅䛜ᚲせ

㻿㼑㼚㼐㼑㼞

㻏㻝㻴㼍㼟㼔

㻾㼑㼏㼑㼕㼢㼑㼞

(21)

ᵏᵗᵍᵓᵑ

n ⡆᫆ㄆド

n

䝟䜿䝑䝖᳨ドฎ⌮䛾᭱ึ䛻ᐇ᪋

n

⡆᫆䝝䝑䝅䝳್䜢⏕ᡂ䛧䛶

ཷಙ䝟䜿䝑䝖䛾⡆᫆䝝䝑䝅䝳್䛸ẚ㍑

㻿㼑㼚㼐㼑㼞

㻏㻝㻴㼍㼟㼔

㻏㻝㻏㻝

㻾㼑㼏㼑㼕㼢㼑㼞

(22)

ᵐᵎᵍᵓᵑ

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴᭦᪂ฎ⌮

ᡂຌ

ኻᩋ

◚Რ

ཷ⌮

᪤ Ꮡ ᪉ ᘧ

㛤ጞ

(23)

ᵐᵏᵍᵓᵑ

⡆᫆ㄆド

㻹㻭㻯ㄆド

䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴᭦᪂ฎ⌮

ᡂຌ

ኻᩋ

◚Რ

ཷ⌮

᪤ Ꮡ ᪉ ᘧ ᥦ

᱌ ᪉ ᘧ

㛤ጞ

(24)

ᵐᵐᵍᵓᵑ

n 䝝䝑䝅䝳㛵ᩘ䛿㻲㻺㼂㻙㻝㻌㻟㻞㼎㼕㼠∧䜢౑⏝

n

ධຊ M 䛿㻤㼎㼕㼠ᩚᩘ䛾㓄ิ

n

ฟຊhash䛿㻟㻞㼎㼕㼠ᩚᩘ

n 䛣䛾䛖䛱䠈ୗ఩㻤㼎㼕㼠䜢⡆᫆䝝䝑䝅䝳್䛸䛩䜛 n

ᐃᩘOffset㻘㻌Prime䛿㻟㻞㼎㼕㼠ᩚᩘ

Offset = 2166136261;

Prime = 16777619;

hash = Offset;

for i := 0 to i < |M| do begin

hash = (Prime * hash) ^ M[i]

end;

(25)

ᵐᵑᵍᵓᵑ

n 䝅䞊䜿䞁䝇␒ྕ䜢㻤㼎㼕㼠ẖ䛻ศ๭

n

䝅䞊䜿䞁䝇␒ྕ䛜㻟㻞㼎㼕㼠䛾ሙྜ

n ඹ㏻㘽䜢㻤㼎㼕㼠ẖ䛻ศ๭

n

ඹ㏻㘽䛜㻝㻞㻤㼎㼕㼠䛾ሙྜ

n 䝝䝑䝅䝳㛵ᩘ䜈䛾ධຊ M 䜢⏕ᡂ K = { k

1 ^, ^k 2 ^, ^⋯ ^, ^k 16 ^} N = { n

1, n

2, n

3, n 4}

M = N , K

(26)

ᵐᵒᵍᵓᵑ

n 䝔䝇䝖䝥䝻䜾䝷䝮䛾௙ᵝ

n

౑⏝ゝㄒ䠖㻯

n

㏻ಙ䛿⾜䜟䛪䠈䝟䜿䝑䝖᳨ドฎ⌮䛾䜏䜢ᐇ⾜

n ⿦⨨䛾௙ᵝ

n ௨ୖ䛾᮲௳䛻䛶ṇᖖ䛻ືస䛩䜛䛣䛸䜢☜ㄆ

䝩䝇䝖䝬䝅䞁 ௬᝿䝬䝅䞁

㻻㻿㼃㼕㼚㼐㼛㼣㼟㻌㻣㻌㻢㻠㼎㼕㼠㼁㼎㼡㼚㼠㼡㻌㻝㻠㻚㻜㻠㻌㻟㻞㼎㼕㼠㻸㼕㼚㼡㼤

䜹䞊䝛䝹㻙㻟㻚㻝㻟㻚㻜㻙㻝㻝㻢㻙㼓㼑㼚㼑㼞㼕㼏

㻯㻼㼁㻵㼚㼠㼑㼘㻌㻯㼛㼞㼑㻌㼕㻣㻙㻞㻢㻜㻜㻟㻚㻠㻜㻳㻴㼦㻝㻯㼛㼞㼑๭䜚ᙜ䛶

㻹㼑㼙㼛㼞㼥㻤㻚㻜㻜㻳㻮㻝㻚㻜㻜㻳㻮๭䜚ᙜ䛶

(27)

ᵐᵓᵍᵓᵑ

n ฎ⌮᫬㛫 ts 㻘㻌 tr 㻘㻌 tm 㻘㻌 tu 䜢ᐃ⩏䛧 ᐃ

n

㻝㻜㻜㻘㻜㻜㻜ᅇᐇ⾜᫬䛾ᖹᆒ್

n

㻹㻭㻯⏕ᡂ䛻䛿㻴㻹㻭㻯㻙㻹㻰㻡䜢

౑⏝

n

㻹㻭㻯⏕ᡂ䠄䝟䜿䝑䝖ㄆド䠅䛾

⠊ᅖ䛿㻝㻜㻟㻢㻮㼥㼠㼑

䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴

᭦᪂ฎ⌮

ts tr

tm tu

⡆᫆ㄆド

㻹㻭㻯ㄆド

㛤ጞ

ts [μs] tr [μs] tm [μs] tu [μs]

0.536 0.414 3.835 0.561

(28)

ᵐᵔᵍᵓᵑ

n 䛔䛪䜜䛛䛾ฎ⌮䛷

◚Რ䛥䜜䜛䜒䛾䜢

୙ṇ䝟䜿䝑䝖䛸䜏䛺䛩

n ☜⋡ Ps 㻘㻌 Pr 㻘㻌 Pm 䜢ᐃ⩏

䛩䜛䛸䠈

Ps + Pr + Pm = 1

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ 䝏䜵䝑䜽

㻹㻭㻯ㄆド ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ 䠄☜⋡䠖Ps䠅

䠄☜⋡䠖Pr䠅

䠄☜⋡䠖Pm䠅

ts

tr

tm

◚ Რ

(29)

ᵐᵕᵍᵓᵑ

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮䛻せ䛩䜛᫬㛫䛾ᖹᆒ್䛿

E = ts Ps

+ (ts + tr ) Pr

+ (ts + tr + tm ) Pm

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ 䝏䜵䝑䜽

㻹㻭㻯ㄆド ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ 䠄☜⋡䠖Ps䠅

䠄☜⋡䠖Pr䠅

䠄☜⋡䠖Pm䠅

ts

tr

tm

◚ Რ

㛤ጞ

(30)

ᵐᵖᵍᵓᵑ

n ௨ୗ䛾⌮ㄽ್䠈ᐇ ್䜢⏝䛔䜛

n

Ps 㻘㻌 Pr 㻘㻌 Pm 䛿㻹㻭㻯ㄆド䛻฿㐩䛩䜛☜⋡䛜᭱኱䛸䛺䜛䛸䛝䛾⌮ㄽ್䠈 ts 㻘㻌 tr 㻘㻌 tm 䛿ᐇ ್

n 䛣䛾䛸䛝䠈

Ps = 9.961 × 10−1 Pr = 1.819 × 10−12 Pm = 3.906 × 10−3

= ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

ts [μs] tr [μs] tm [μs]

0.536 0.414 3.835

E = 0.553[μs]

(31)

ᵐᵗᵍᵓᵑ

n ᪤Ꮡ᪉ᘧ䛷䛿䠈⡆᫆ㄆド䜢౑⏝䛧䛶䛔䛺䛔䛯䜑 ௨ୗ䛾䜘䛖䛻䛺䜛

n

Pr 㻘㻌 Pm 䛿㻹㻭㻯ㄆド䛻฿㐩䛩䜛☜⋡䛜᭱኱䛸䛺䜛䛸䛝䛾⌮ㄽ್䠈 tr 㻘㻌 tm 䛿ᐇ ್

n 䛧䛯䛜䛳䛶䠈

E = ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

E !

Ps = 0, ts = 0 = 4.249[μs]

Ps = 0

Pr = 4.657 × 10−10 Pm = 9.999 × 10−1

ts [μs] tr [μs] tm [μs]

0 0.414 3.835

(32)

ᵑᵎᵍᵓᵑ

n ௨ୖ䛾⤖ᯝ䜘䜚䠈ᥦ᱌᪉ᘧ䛻䜘䜚

୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫䜢᭱኱㻝㻛㻤⛬ᗘ䛻

▷⦰䛩䜛䛣䛸䛜䛷䛝䜛

୙ṇ䝟䜿䝑䝖䛻䜘䜛㻰㼛㻿ᨷᧁ⪏ᛶ䛜

኱䛝䛟ྥୖ䛩䜛䛣䛸䛜ᮇᚅ䛷䛝䜛 E = 0.553[μs]

E !

Ps = 0, ts = 0 = 4.249[μs]

ᥦ᱌᪉ᘧ䠖

᪤Ꮡ᪉ᘧ䠖

(33)

ᵑᵏᵍᵓᵑ

n ṇつ䛾䝟䜿䝑䝖䛾ሙྜ䛿䠈

⡆᫆ㄆド䛾㏣ຍศ䛰䛡

㈇Ⲵ䛜ቑຍ䛩䜛

ts [ μs ] tr [ μs ] tm [ μs ] tu [ μs ] 0.536 0.414 3.835 0.561

᪤Ꮡ᪉ᘧ䠖 4.810[μs]

ᥦ᱌᪉ᘧ䠖 5.346[μs]

᭦᪂ฎ⌮

ts tr tm

tu

⡆᫆ㄆド

㻹㻭㻯ㄆド

㛤ጞ

(34)

ᵑᵐᵍᵓᵑ

n 䛣䛾ᚋ䛾᚟ྕฎ⌮䛿䠈㻹㻭㻯ㄆド䛾⣙㻝㻜ಸ䛾

᫬㛫䜢せ䛩䜛

᭦᪂ฎ⌮

ts tr tm

tu

⡆᫆ㄆド

㻹㻭㻯ㄆド

10tm

᚟ྕฎ⌮

⡆᫆ㄆド䛾㈇Ⲵ䛿

ᴟ䜑䛶ᑠ䛥䛔

(35)

ᵑᵑᵍᵓᵑ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥 l _h 䜢ኚ໬䛥䛫䛯ሙྜ

n

䝥䝻䜾䝷䝮䛾ไ⣙ୖ䠈᭱ᑠ䛿㻤㼎㼕㼠

n

lh 䛜኱䛝䛟䛺䜛䜋䛹 Ps ≈ 1 䠈䛩䛺䜟䛱 Pr ≈ 0 㻘㻌 Pm ≈ 0 䛸䛺䜛䛾䛷௨ୗ䛜ᡂ❧

E = ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm ≈ ts

lh [bit] Ps ts [μs] E [μs]

8 9.9609 × 10−1 0.536 0.553

16 9.9998 × 10−1 0.675 0.675

32 9.9999 × 10−1 0.823 0.823

(36)

ᵑᵒᵍᵓᵑ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥 l _h 䜢ኚ໬䛥䛫䛯ሙྜ

n

䝥䝻䜾䝷䝮䛾ไ⣙ୖ䠈᭱ᑠ䛿㻤㼎㼕㼠

n

ts 㻘㻌 E 䛾ቑຍ㔞䛻ᑐ䛧䛶 Ps 䛿኱ᕪ䛺䛔

⡆᫆ㄆド䛾ຠᯝ䛜኱䛝䛟ୖ᪼䛩䜛䜟䛡䛷䛿䛺䛔

⡆᫆䝝䝑䝅䝳್䛿㻤㼎㼕㼠䛜᭱㐺

lh [bit] Ps ts [μs] E [μs]

8 9.9609 × 10−1 0.536 0.553

16 9.9998 × 10−1 0.675 0.675

32 9.9999 × 10−1 0.823 0.823

(37)

ᵑᵓᵍᵓᵑ

n

᪤Ꮡ᪉ᘧ䛸ẚ㍑䛧䛶୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫䜢

᭱኱㻝㻛㻤⛬ᗘ䛻▷⦰䛩䜛䛣䛸䛜ྍ⬟

n

⡆᫆䝝䝑䝅䝳್䛿㻤㼎㼕㼠䛜᭱㐺

n ௒ᚋ䛾ணᐃ

n

㻺㼀㻹㼛㼎㼕㼘㼑䛻ṇᘧ௙ᵝ䛸䛧䛶㐺⏝

(38)

ᵑᵔᵍᵓᵑ

n ㏦ಙඖ䛾Ꮡᅾ䜢☜ㄆ

n

㍍䛔ฎ⌮䜢ᐇ᪋ᚋ䠈㔜䛔ฎ⌮䜢ᐇ᪋

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻼㼡㼎㼘㼕㼏㻌㻷㼑㼥㻼㼞㼕㼢㼍㼠㼑㻌㻷㼑㼥㻯㼛㼙㼙㼛㼚㻌㻷㼑㼥

㻼㼍㼏㼗㼑㼠

(39)

ᵑᵕᵍᵓᵑ

n ㏦ಙඖ䛾Ꮡᅾ䜢☜ㄆ

n

㍍䛔ฎ⌮䜢ᐇ᪋ᚋ䠈㔜䛔ฎ⌮䜢ᐇ᪋

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻼㼡㼎㼘㼕㼏㻌㻷㼑㼥㻼㼞㼕㼢㼍㼠㼑㻌㻷㼑㼥

(40)

ᵑᵖᵍᵓᵑ

n ㏦ಙඖ䛾Ꮡᅾ䜢☜ㄆ

n

㍍䛔ฎ⌮䜢ᐇ᪋ᚋ䠈㔜䛔ฎ⌮䜢ᐇ᪋

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻼㼡㼎㼘㼕㼏㻌㻷㼑㼥㻼㼞㼕㼢㼍㼠㼑㻌㻷㼑㼥

(41)

ᵑᵗᵍᵓᵑ

n 㻱㻿㻼㻌㻔㻱㼚㼏㼍㼜㼟㼡㼘㼍㼠㼕㼚㼓㻌㻿㼑㼏㼡㼞㼕㼠㼥㻌㻼㼍㼥㼘㼛㼍㼐㻕㻌

n

䝟䜿䝑䝖䛾ᶵᐦᛶ䛚䜘䜃᏶඲ᛶ䜢☜ಖ䛧

㏦ಙඖ䛾ㄆド䜢⾜䛖䝉䜻䝳䝸䝔䜱䝥䝻䝖䝁䝹

n ᶵᐦᛶ䠖䜰䜽䝉䝇䜢ㄆྍ䛥䜜䛯⪅䛰䛡䛜

᝟ሗ䛻䜰䜽䝉䝇䛷䛝䜛䛣䛸䜢☜ᐇ䛻䛩䜛ᛶ㉁

n ᏶඲ᛶ䠖᝟ሗ䛚䜘䜃ฎ⌮᪉ἲ䛜ṇ☜䛷䛒䜛䛣䛸䠈䛚䜘䜃᏶඲䛷䛒䜛䛣䛸䜢ಖㆤ䛩䜛ᛶ㉁

n

ᶵᐦᛶ䛾☜ಖ䠖䝟䜿䝑䝖䛾ᬯྕ໬

n

᏶඲ᛶ䛾☜ಖ䞉㏦ಙඖ䛾ㄆド䠖㻹㻭㻯ㄆド

n 㻱㻿㻼䛷䛿䠈㻹㻭㻯䜢㻵㻯㼂㻌㻔㻵㼚㼠㼑㼓㼞㼕㼠㼥㻌㻯㼔㼑㼏㼗㻌㼂㼍㼘㼡㼑㻕䛸࿧䜆䛣䛸䛜ከ䛔

(42)

ᵒᵎᵍᵓᵑ

n

㻱㻿㻼㻌㼔㼑㼍㼐㼑㼞䠖㻿㻼㻵䠄㻟㻞㼎㼕㼠䠅䛸䝅䞊䜿䞁䝇␒ྕ䠄㻟㻞㼎㼕㼠䠅

n 㻿㻼㻵㻌㻔㻿㼑㼏㼡㼞㼕㼠㼥㻌㻼㼍㼞㼍㼙㼑㼠㼑㼞㻌㻵㼚㼐㼑㼤㻕䠖䝉䝑䝅䝵䞁㆑ูᏊ

n

㻱㻿㻼㻌㼀㼞㼍㼕㼘㼑㼞

n 㻼㼍㼐㼐㼕㼚㼓䠖䝟䝕䜱䞁䜾䠄㻜䡚㻞㻡㻡㻮㼥㼠㼑䠅

n 㻼㼍㼐㻌㻸㼑㼚㼓㼠㼔䠄㻤㼎㼕㼠䠅䠖㻼㼍㼐㼐㼕㼚㼓䛾㛗䛥䠄㻮㼥㼠㼑༢఩䠅

n 㻺㼑㼤㼠㻌㻴㼑㼍㼐㼑㼞䠄㻤㼎㼕㼠䠅䠖㻰㼍㼠㼍䛾ඛ㢌䝦䝑䝎䛾㻵㻼䝥䝻䝖䝁䝹␒ྕ

n

㻵㻯㼂䠖ㄆド䝁䞊䝗

header header header Data

Trailer ICV encrypted

authenticated

(43)

ᵒᵏᵍᵓᵑ

n ⌧≧䛾㻱㻿㻼㻌㼔㼑㼍㼐㼑㼞

n ᥦ᱌᪉ᘧ㐺⏝᫬䛾㻱㻿㻼㻌㼔㼑㼍㼐㼑㼞䠄୍౛䠅

n

ㄢ㢟䠖䝣䜷䞊䝬䝑䝖ኚ᭦䛻䜘䜚஫᥮ᛶ䛜䛺䛟䛺䜛

0 7 15 23 31

0

SPI

1

Sequence Number

0 7 15 23 31

0

SPI

1

Sequence Number

2

Simple Hash Reserved

(44)

ᵒᵐᵍᵓᵑ

n 㻺㼀㻹㻌㼔㼑㼍㼐㼑㼞㻌㻔㻟㻢㻮㼥㼠㼑㻕

n

㻺㼀㻹㼛㼎㼕㼘㼑䛾㏻ಙ䛻㛵䜟䜛䝕䞊䝍䜢ྵ䜐

n 䝅䞊䜿䞁䝇␒ྕ䠄㻟㻞㼎㼕㼠䠅䠈⡆᫆䝝䝑䝅䝳್䛺䛹

n 䛯䛰䛧䠈⌧≧䛾䝅䞊䜿䞁䝇␒ྕ䛿㻝㻢㼎㼕㼠

n 㻻㼞㼕㼓㼕㼚㼍㼘㻌㻼㼍㼏㼗㼑㼠䜢䜹䝥䝉䝹໬

IP header

UDP header

UDP data NTM

header

Original Packet IP MAC

Header

TCP/UDP Header

TCP/UDP data encrypted

authenticated

(45)

ᵒᵑᵍᵓᵑ

n ⌧≧䛾㻺㼀㻹㻌㼔㼑㼍㼐㼑㼞

0 7 15 23 31

0

NTM ID

1

Version Type Flag Count

2

Transaction ID

3

Sequence Number Message Length

4

Next Opt. Reserved

5

Node ID or Path ID (128bit)

6 7 8

(46)

ᵒᵒᵍᵓᵑ

n ᥦ᱌᪉ᘧ㐺⏝᫬䛾㻺㼀㻹㻌㼔㼑㼍㼐㼑㼞

0 7 15 23 31

0

NTM ID

1

Version Type Flag Count

2

Transaction ID

3

Sequence Number

4

Message Length Next Opt. Simple Hash

5

Node ID or Path ID (128bit)

6 7 8

(47)

ᵒᵓᵍᵓᵑ

n ௨ୗ䛾䝝䝑䝅䝳㛵ᩘ䜢ẚ㍑

n

㝖⟬ἲ

n

஌⟬ἲ

n

㻲㻺㼂㻙㻝㻌㻟㻞㼎㼕㼠∧

n ධຊ㻝㻢㻜㼎㼕㼠䛾䛸䛝䛾ฎ⌮᫬㛫䜢 ᐃ

n

₇⟬䛻せ䛩䜛᫬㛫䛜᭱䜒▷䛔㻲㻺㼂㻙㻝㻌㻟㻞㼎㼕㼠∧䜢᥇⏝

䜰䝹䝂䝸䝈䝮 ฎ⌮᫬㛫[μs]

㝖⟬ἲ 0.544

஌⟬ἲ 1.247

㻲㻺㼂㻙㻝㻌㻟㻞㼎㼕㼠∧ 0.410

(48)

ᵒᵔᵍᵓᵑ

n Ps 㻘㻌 Pr 㻘㻌 Pm 䛿௨ୗ䛾ᘧ䛷ィ⟬䛩䜛

n

ྛኚᩘ䞉ᐃᩘ䛾ព࿡䛿௨㝆䛻ヲ㏙

Ps = 1 − 1 2 l

h Pr = 1

2 l h

1 − {(2 ln

− 1) − nl } + {min(sw , nl ) − r } 2 ln

Pm = 1 2 l

h

{(2 ln

− 1) − nl } + {min(sw , nl ) − r } 2 ln

= ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

(49)

ᵒᵕᵍᵓᵑ

n lh 䛿䛂⡆᫆䝝䝑䝅䝳್䛾㛗䛥 [bit] 䛃

n

ඛ㏙䛧䛯㏻䜚 lh = 8

E = ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

Ps = 1 − 1 2 8

Pr = 1

2 8 1 − {(2 ln

− 1) − nl } + {min(sw , nl ) − r } 2 ln

Pm = 1 2 8

{(2 ln

− 1) − nl } + {min(sw , nl ) − r }

2 ln

(50)

ᵒᵖᵍᵓᵑ

n ln 䛿䛂䝅䞊䜿䞁䝇␒ྕ䛾㛗䛥 [bit] 䛃

n

ඛ㏙䛧䛯㏻䜚 ln = 32

= ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

Ps = 1 − 1 28

Pr = 1 28

1 − {(2 32 − 1) − nl } + {min(sw , nl ) − r } 2 32

Pm = 1 28

{(2 32 − 1) − nl } + {min(sw , nl ) − r }

2 32

(51)

ᵒᵗᵍᵓᵑ

n sw 䛿䛂䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛾䝃䜲䝈䛃

n

㻱㻿㻼䛸ྠᵝ䛸䛩䜜䜀 sw = 32

E = ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

Ps = 1 − 1 28

Pr = 1 28

1 − {(232 − 1) − nl } + {min(32, nl ) − r } 232

Pm = 1 28

{(232 − 1) − nl } + {min(32, nl ) − r }

232

(52)

ᵓᵎᵍᵓᵑ

n nl 䛿䛂᳨ドฎ⌮㛤ጞ᫬䛾᭱᪂䝅䞊䜿䞁䝇␒ྕ䛃

n r 䛿䛂䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴ෆ䛾ཷಙ῭䜏ಶᩘ䛃

n

௨ୗ䛾ሙྜ䠈 nl = 116 䠈 r = 31

= ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

85 116

㻝㻝㻝㻜㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻝㻜

㻜䠖ᮍཷಙ䠈㻝䠖ཷಙ῭䜏 ኴᯟ䠖䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䠄sw = 32䠅

(53)

ᵓᵏᵍᵓᵑ

n nl 䛿䛂᳨ドฎ⌮㛤ጞ᫬䛾᭱᪂䝅䞊䜿䞁䝇␒ྕ䛃

n r 䛿䛂䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴ෆ䛾ཷಙ῭䜏ಶᩘ䛃

n

௒ᅇ䛾䝅䝭䝳䝺䞊䝅䝵䞁䛷䛿䠈 nl = 1 䠈 r = 1 䛸䛩䜛

䝅䞊䜿䞁䝇␒ྕ 1 䛾䝟䜿䝑䝖䛾䜏䜢ཷಙ䛧䛯≧ែ

E = ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

1 2 16 2ln

−1

㻝㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜䈈㻜

㻜䠖ᮍཷಙ䠈㻝䠖ཷಙ῭䜏 ኴᯟ䠖䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䝅䞊䜿䞁䝇␒ྕ䛾㛗䛥䠖ln = 32

(54)

ᵓᵐᵍᵓᵑ

n nl = 1 䠈 " = 1 䜢௦ධ䛩䜛䛸䠈

= ts Ps + (ts + tr ) Pr + (ts + tr + tm ) Pm

Ps = 1 − 1 2⁸

= 9.961×10−1

Pr = 1 28

1 − {(232 − 1) − 1} + {min(32, 1) − 1}

232

= 1.819×10−12

Pm = 1 28

{(232 − 1) − 1} + {min(32, 1) − 1}

232

= 3.906×10−3

(55)

ᵓᵑᵍᵓᵑ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥 l _h 䜢ኚ໬䛥䛫䛯ሙྜ

n

䝥䝻䜾䝷䝮䛾ไ⣙ୖ䠈᭱ᑠ䛿㻤㼎㼕㼠

n

ྛ☜⋡䛾ኚ໬䛿௨ୗ䛾䜘䛖䛻䛺䜛

n

n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

n ⛣ື㏻ಙ➃ᮎ䛾ᬑཬ

n 䜲䞁䝍䞊䝛䝑䝖฼⏝䛾㟂せቑຍ

n 䝛䝑䝖䝽䞊䜽䝉䜻䝳䝸䝔䜱䜈䛾⬣ጾ

ᬯྕ໬㏻ಙ䛻䛚䛔䛶䜒᭷ຠ䛺ᨷᧁ

n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

㻭㼠㼠㼍㼏㼗㼑㼞

n 㐣ཤ䛻㏦ಙ䛥䜜䛯ṇつ䛾䝟䜿䝑䝖䜢෌㏦䛩䜛ᨷᧁ

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 㻾㻲㻯㻞㻠㻜㻝㻌㻔㻵㻼㼟㼑㼏㻌㼂㼑㼞㻚㻞㻕䛷ᶆ‽໬

n 䝅䞊䜿䞁䝇␒ྕ䛾౑⏝

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ⠊ᅖ䜢Ỵᐃ

䜴䜱䞁䝗䜴ෆ䛛᭱᪂䛷䠈ᮍཷಙ䛾䝅䞊䜿䞁䝇␒ྕ䜢ཷ⌮

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 䝸䝥䝺䜲ᨷᧁᐇ᪋

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴䛻䜘䜚ཷಙ῭䜏䛸ุᐃ 䝸䝥䝺䜲ᨷᧁ䛸䜏䛺䛧䛶◚Რ

㻭㼠㼠㼍㼏㼗㼑㼞

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n ཷಙഃ䛻㐣๫䛺㈇Ⲵ䜢୚䛘䜛䛣䛸䛷 䝃䞊䝡䝇䜢୙⬟䛻䛥䛫䜛ᨷᧁ

㻭㼠㼠㼍㼏㼗㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 㻹㻭㻯ㄆド

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯 䝟䜿䝑䝖᳨ド

䝟䜿䝑䝖䛾䝕䞊䝍㒊䛸ඹ㏻㘽䜢⏝䛔䛶㻹㻭㻯䜢⏕ᡂ

㻿㼑㼚㼐㼑㼞

㻾㼑㼏㼑㼕㼢㼑㼞

n 㻹㻭㻯ㄆド

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯 䝟䜿䝑䝖᳨ド

䝟䜿䝑䝖䛾䝕䞊䝍㒊䛸ඹ㏻㘽䜢⏝䛔䛶㻹㻭㻯䜢⏕ᡂ

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 㻹㻭㻯ㄆド

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯 䝟䜿䝑䝖᳨ド

ཷಙഃ䛿㻹㻭㻯䜢⏕ᡂ䛧䛶䝟䜿䝑䝖䛾㻹㻭㻯䛸ẚ㍑

㻿㼑㼚㼐㼑㼞 㻾㼑㼏㼑㼕㼢㼑㼞

n 㻱㻿㻼㻌㻔㻱㼚㼏㼍㼜㼟㼡㼘㼍㼠㼕㼚㼓㻌㻿㼑㼏㼡㼞㼕㼠㼥㻌㻼㼍㼥㼘㼛㼍㼐㻕

㻻㻿㻵ཧ↷䝰䝕䝹䛾䝛䝑䝖䝽䞊䜽ᒙ䠄➨㻟ᒙ䠅䛻䛚䛡䜛

୍⯡ⓗ䛺䝉䜻䝳䝸䝔䜱䝥䝻䝖䝁䝹䠄㻾㻲㻯㻠㻟㻜㻟䠅

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽䠈㻹㻭㻯ㄆド䛾㡰䛻⾜䛖

n 㻺㼀㻹㼛㼎㼕㼘㼑 㻔㻺㼑㼠㼣㼛㼞㼗㻌㼀㼞㼍㼢㼑㼞㼟㼍㼘㻌㼣㼕㼠㼔㻌㻹㼛㼎㼕㼘㼕㼠㼥㻕

⛣ື㏱㐣ᛶ䛸㏻ಙ᥋⥆ᛶ䛾୧⪅䜢ྠ᫬䛻 ᐇ⌧䛩䜛ᢏ⾡

㻵㻼㼟㼑㼏䛸ྠᵝ䛾䝉䜻䝳䝸䝔䜱䜢ഛ䛘䜛

n ᪤Ꮡ䛾䝟䜿䝑䝖᳨ド䛾ㄢ㢟

䝟䜿䝑䝖㛗䛜㛗䛔䜋䛹㻹㻭㻯ㄆド䛾ฎ⌮᫬㛫䛜㛗䛟䛺䜛

኱㔞䛾䝟䜿䝑䝖䜢ฎ⌮䛩䜛䝃䞊䝞➼䛷䛿 㻰㼛㻿ᨷᧁ䜢㜵ᚚ䛩䜛䛯䜑䛻

ᑡ䛧䛷䜒㏿䛟୙ṇ䝟䜿䝑䝖䜢᳨ฟ䛧䛯䛔

n ⡆᫆ㄆド

䝅䞊䜿䞁䝇␒ྕ䛸ඹ㏻㘽䛛䜙⡆᫆䝝䝑䝅䝳್䠄㻤㼎㼕㼠䠅䜢

⏕ᡂ

㻿㼑㼚㼐㼑㼞

㻾㼑㼏㼑㼕㼢㼑㼞

n ⡆᫆ㄆド

⏕ᡂ䛧䛯⡆᫆䝝䝑䝅䝳್䜢䝟䜿䝑䝖䛻௜ຍ䛧䛶㏦ಙ

㻿㼑㼚㼐㼑㼞

㻾㼑㼏㼑㼕㼢㼑㼞

n ⡆᫆ㄆド

䝟䜿䝑䝖᳨ドฎ⌮䛾᭱ึ䛻ᐇ᪋

⡆᫆䝝䝑䝅䝳್䜢⏕ᡂ䛧䛶

ཷಙ䝟䜿䝑䝖䛾⡆᫆䝝䝑䝅䝳್䛸ẚ㍑

㻿㼑㼚㼐㼑㼞

㻾㼑㼏㼑㼕㼢㼑㼞

◚Რ

ཷ⌮

◚Რ

ཷ⌮

n 䝝䝑䝅䝳㛵ᩘ䛿㻲㻺㼂㻙㻝㻌㻟㻞㼎㼕㼠∧䜢౑⏝

ධຊ M 䛿㻤㼎㼕㼠ᩚᩘ䛾㓄ิ

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

n ཷಙഃ䛻㐣๫䛺㈇Ⲵ䜢୚䛘䜛䛣䛸䛷䝃䞊䝡䝇䜢୙⬟䛻䛥䛫䜛ᨷᧁ

㻭㼠㼠㼍㼏㼗㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

㻹㻭㻯㻌㻔㻹㼑㼟㼟㼍㼓㼑㻌㻭㼡㼠㼔㼑㼚㼠㼕㼏㼍㼠㼕㼛㼚㻌㻯㼛㼐㼑㻕䜢⏝䛔䛯䝟䜿䝑䝖᳨ド

㻿㼑㼚㼐㼑㼞㻾㼑㼏㼑㼕㼢㼑㼞

n 㻺㼀㻹㼛㼎㼕㼘㼑㻔㻺㼑㼠㼣㼛㼞㼗㻌㼀㼞㼍㼢㼑㼞㼟㼍㼘㻌㼣㼕㼠㼔㻌㻹㼛㼎㼕㼘㼕㼠㼥㻕

኱㔞䛾䝟䜿䝑䝖䜢ฎ⌮䛩䜛䝃䞊䝞➼䛷䛿㻰㼛㻿ᨷᧁ䜢㜵ᚚ䛩䜛䛯䜑䛻

1 ^, ^k 2 ^, ^⋯ ^, ^k 16 ^} N = { n

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮䛻せ䛩䜛᫬㛫䛾ᖹᆒ್䛿

Ps 㻘㻌 Pr 㻘㻌 Pm 䛿㻹㻭㻯ㄆド䛻฿㐩䛩䜛☜⋡䛜᭱኱䛸䛺䜛䛸䛝䛾⌮ㄽ್䠈 ts 㻘㻌 tr 㻘㻌 tm 䛿ᐇ ್

Pr 㻘㻌 Pm 䛿㻹㻭㻯ㄆド䛻฿㐩䛩䜛☜⋡䛜᭱኱䛸䛺䜛䛸䛝䛾⌮ㄽ್䠈 tr 㻘㻌 tm 䛿ᐇ ್