不正パケットの高速な検出を実現する簡易認証方式の提案と評価

不正パケットの高速な検出を実現する簡易認証方式の提案と評価

鴨下 友馬^†1 鈴木 秀和^†1 内藤 克浩^†2 渡邊 晃^†1

†1名城大学理工学部 ^†2愛知工業大学情報科学部

1 ^はじめに

モバイルネットワークの普及に伴い，ネットワークセ キュリティを脅かすDoS攻撃(Denial of Service Attack) が問題となっている．DoS攻撃は，大量のデータを処理 するサーバ類では特に脅威となる攻撃である．DoS攻 撃対策の一例として，共通鍵を事前に共有している場合 はHMAC (Hash-based Message Authentication Code)を 用いたパケット認証を利用することができる．しかし，

この認証方式ではパケット長が長いと不正パケットの検 出にかかる処理時間が長くなる．

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

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

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

IPsec (IP security)のESP (Encapsulating Security Pay-

load) [2]トランスポートモードを用いて，パケット受

信時のDoS攻撃対策処理を説明する．図1にパケット フォーマットを示す．ESP headerには32bitのシーケン ス番号が含まれている．認証コードは，パケットの認証 範囲と共通鍵を用いてHMAC-MD5により生成し，その 結果をICV (Integrity Check Value)に付与する．

パケット検証はリプレイ攻撃チェック，ICV(MAC)認 証の順に行い，不正パケットであると判定した場合には その時点で破棄を決定し，以降の処理は行わない．ここ で，リプレイ攻撃とは攻撃者が正規のパケットを盗聴し，

それを再送する攻撃である[3]．リプレイ攻撃チェック はこれを阻止するための処理であり，リプレイ防御ウィ ンドウと呼ばれるビットマスクを用いて受信を許可する シーケンス番号の範囲を決定することで，リプレイ攻撃 パケットを検出する．リプレイ攻撃では正規のパケット を攻撃に利用するためICV(MAC)認証では検出できず，

Proposal and Evaluation of Simple Authentication Method that Detects Invalid Packets Fast

Yuma Kamoshita^†1, Hidekazu Suzuki^†1, Katsuhiro Naito^†2and Akira Watanabe^†1

†1Faculty of Science and Technology, Meijo University

†2Faculty of Information Science, Aichi Institute of Technology Uni- versity

authenticated encrypted

ICV headerIP Data

headerESP headerTCP

TrailerESP

図1 ESPのパケットフォーマット

encrypted authenticated headerIP TCP/UDPheader

TCP/UDPdata IP

header UDP header

UDP data NTM

header

Original Packet

MAC

図2 NTMobileのパケットフォーマット

リプレイ攻撃チェックは必須である．

ICV(MAC)認証まで成功した場合は正規のパケット

とみなし，リプレイ防御ウィンドウの更新を行う．最後 に，パケットを復号して受信処理に入る．

3 NTMobile

NTMobileでは，IPsecと同様にエンドツーエンドの セキュリティを実現することができる．NTMobile端末 は，通信開始時にDC (Direction Coordinator)からの経 路生成指示によってトンネル経路を生成し，以後のす べての通信は仮想アドレスのパケットを実アドレスで カプセル化するという特徴がある．NTMobileにはRS (Relay Server)という大量のパケットを中継する装置が あり，不正パケットを可能な限り短時間で検出する機能 が求められる．

図2にNTMobileのパケットフォーマットを示す．こ

こで，NTM headerにはNTMobileの通信に関わるデー タが含まれており，32bitのシーケンス番号もここに含

まれる．MACには，HMAC-MD5により生成した認証

コードが付与される．パケット検証の方法はESPと同 様で，リプレイ攻撃チェック，MAC認証の順に行う．

4 ^提案方式

提案方式はパケット検証の最初に行い，不正パケット を短時間で検出することを目的とする．したがって，パ ケット検証は簡易認証，リプレイ攻撃チェック，MAC 認証の順に行い，正規のパケットであればリプレイ防御 ウィンドウの更新を行う．この方式はESP，NTMobile 双方に適用できるが，パケット内に，簡易認証に係る フィールド（8bit）を追加する必要がある．

NTMobileの場合，送信側は，通信に用いる共通鍵と

シーケンス番号を用いて8bitのハッシュ値（以下，簡 易ハッシュ値）を生成し，NTM header内に格納する．

ハッシュ関数は，演算時間の短いFNV-1(32bit)を用い ることとする．受信側は，最初に簡易ハッシュ値を計算 し，受信パケットに格納された値と比較する．これらの

表1 実験環境 OS Ubuntu 14.04 32bit

CPU ^{仮想マシン（}1Core 3.40GHz^） Memory 1GB

表2 ^{検証時間の実測値} t_s[µs] t_r[µs] t_m[µs]

0.536 0.414 3.835

値が不一致であれば不正パケットであると判定して破棄 し，一致していればリプレイ攻撃チェックに進む．以後 の処理は，既存のパケット検証処理と同様である．

5 ^{実験と評価}

5.1 検証時間の測定

パケット検証プログラムを試作し，表1の実験環境で 処理時間の測定を行った．図2のauthenticatedの長さ を1,036Byteとしてパケット検証処理を100,000回実行 した際の，処理時間の平均値を表2に示す．ここで，t_s は簡易認証に要する時間，t_r はリプレイ攻撃チェックに 要する時間，t_mはMAC認証に要する時間である．

5.2 不正パケットの検証時間

不正パケットの検証時間を，実測値とシミュレーショ ンから評価する．前提として，不正パケットの簡易ハッ シュ値の分布は一様であると仮定する．このとき，簡易 ハッシュ値の長さをl_h[bit]とすると，不正パケットにお いて簡易認証に成功する確率P_sは，

P_s= 1

2^lh (1)

となる．次に，シーケンス番号の長さを l_n[bit]，検証 処理開始時点での最新の受信済みシーケンス番号を n_l，リプレイ防御ウィンドウのサイズをs_w，リプレイ 防御ウィンドウ内の受信済みシーケンス番号の個数を r(1 ≤r ≤s_w)とすると，不正パケットにおいてリプレ イ攻撃チェックに成功する確率P_r は，

P_r = {(

2^ln −1)

−n_l}

+(s_w−r)

2^ln (2)

となる．したがって，不正パケットが簡易認証で破棄さ れる確率P_s，リプレイ攻撃チェックで破棄される確率 P_r，MAC認証で破棄される確率P_mは，

P_s=1−P_s (3)

P_r =P_s(1−P_r) (4)

P_m=P_sP_r (5)

となる．以上より，不正パケットの検証時間の平均値E は式(6)のようになる．

E=t_sP_s+(t_s+t_r)P_r+(t_s+t_r+t_m)P_m (6) 以下，処理時間のシミュレーション結果を示す．P_sは 定数であり，P_r,P_mは式(4)，式(5)からP_rに依存し，P_r が小さいほどP_mは大きくなる．実験時の各種パラメー タは簡易ハッシュ長l_h =8，シーケンス番号長l_n=32， リプレイ防御ウィンドウサイズ s_w = min(32,n_l) で ある．n_l, r は受信状況により変化するが，以下では n_l =1,r=1とする．式(6)で表2の実測値を用いると，

E=0.553[µs] (7)

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

0.561 4.810 5.346

表4 簡易ハッシュ値の長さを変化させた場合の比較

l_h[bit] 8 16 32

P_s 0.99609 0.99998 0.99999

P_r 1.819×10⁻¹² 7.105×10⁻¹⁵ 1.084×10⁻¹⁹ P_m 3.906×10⁻³ 1.526×10⁻⁵ 2.328×10⁻¹⁰

t_s[µs] 0.536 0.675 0.823

E[µs] 0.553 0.675 0.823

となった．一方，式(6)においてl_h =0,t_s =0とすれ ば，既存の不正パケット検証時間の平均値が求められ る．よって，表2の実測値t_r,t_mを用いると，

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

5.3 正規のパケットの検証時間

攻撃がない状態においては，パケット検証に常に簡易 認証処理が加わるため負荷が増えることになる．そこ で，この増加した負荷が全体の検証処理時間に与える 影響を調査した．正規のパケットの検証処理を100,000 回実行した際の，リプレイ防御ウィンドウ更新処理時 間の平均値t_u と，全体の検証処理時間の理論値を表3 に示す．提案手法ではt_s が加わるため全体の検証処理 時間は約11%長くなるものの，この後の復号処理時間

（MAC認証の約10倍），さらには正規の受信処理時間を 考慮すると影響は極めて小さいと言える．

5.4 簡易ハッシュ値の長さによる処理時間の比較 簡易ハッシュ長l_hを変化させた場合のP_s,P_r,P_m，お よび簡易認証を100,000回実行した際の処理時間の平均 値t_s，さらに不正パケットの検証時間の平均値E を表 4に示す．l_h が大きくなるほど，P_sは1に近付き，P_r, P_mはほぼ0となる．このため，Eはt_sの値に限りなく 近付く．一方，l_hが長くなるとt_sが増加し，その結果 Eも増加する．このとき，t_sの増加量に対して，P_sの変 化，すなわち簡易認証の効果は大差ない．したがって，

簡易ハッシュ値の長さは8bitで十分である．

6 まとめ

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

参考文献

[1] 上醉尾一真ほか：IPv4/IPv6混在環境で移動透過性を 実現するNTMobileの実装と評価，情処学論，Vol.

54，No.10，pp.2288–2299 (2013).

[2] Kent, S.: IP Encapsulating Security Payload (ESP), RFC 4303, IETF (2005).

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

鴨下 友馬

，鈴木 秀和

，内藤 克浩

，渡邊 晃

†

名城大学 理工学部 情報工学科

‡

愛知工業大学 情報科学部 情報科学科

ᵏᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

n ⛣ື㏻ಙ➃ᮎ䛾ᬑཬ

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

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

n ᬯྕ໬䛿ᚲ㡲䛾ᢏ⾡

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

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

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

ᵐᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

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

㻭㼠㼠㼍㼏㼗㼑㼞

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

ᵑᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

㻭㼠㼠㼍㼏㼗㼑㼞

㻼㼍㼏㼗㼑㼠

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

ᵒᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

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

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

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

ᵓᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

n 䝅䞊䜿䞁䝇␒ྕ䛾౑⏝

㻭㼠㼠㼍㼏㼗㼑㼞 1 2 3 4 5 6

㻜 㻜 㻜 㻜 㻜 㻜 䈈 㻏㻝

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

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

ཷಙ≧ἣ

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

ᵔᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

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

㻭㼠㼠㼍㼏㼗㼑㼞 1 2 3 4 5 6

㻝 㻜 㻜 㻜 㻜 㻜 䈈 㻏㻝

㻼㼍㼏㼗㼑㼠

㻏㻝 㻼㼍㼏㼗㼑㼠

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

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

ཷಙ≧ἣ

ᵕᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

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

㻭㼠㼠㼍㼏㼗㼑㼞 1 2 3 4 5 6

㻝 㻜 㻜 㻜 㻜 㻜 䈈 㻏㻝

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

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

ཷಙ≧ἣ

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

ᵖᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

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

㻭㼠㼠㼍㼏㼗㼑㼞 1 2 3 4 5 6

㻝 㻝 㻜 㻜 㻜 㻜 䈈 㻏㻞

㻼㼍㼏㼗㼑㼠

㻏㻝 㻼㼍㼏㼗㼑㼠

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

ཷಙ≧ἣ

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

ᵗᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

n 䝸䝥䝺䜲ᨷᧁᐇ᪋

㻭㼠㼠㼍㼏㼗㼑㼞

㻏㻝 㻼㼍㼏㼗㼑㼠

1 2 3 4 5 6

㻝 㻝 㻜 㻜 㻜 㻜 䈈

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

ཷಙ≧ἣ

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

ᵏᵎᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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

㻭㼠㼠㼍㼏㼗㼑㼞 1 2 3 4 5 6

㻝 㻝 㻜 㻜 㻜 㻜 䈈 㻏㻝

㻼㼍㼏㼗㼑㼠

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

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

ᵏᵏᵍᵔᵑ

㻝㻚㻌◊✲⫼ᬒ䛸᪤Ꮡᢏ⾡

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 ⏕ᡂ䛧䛯⡆᫆䝝䝑䝅䝳್䜢䝟䜿䝑䝖䛻௜ຍ䛧䛶㏦ಙ

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

㻿㼑㼚㼐㼑㼞

㻏㻝 㻴㼍㼟㼔

㻰㼍㼠㼍 㻹㻭㻯

㻾㼑㼏㼑㼕㼢㼑㼞

ᵏᵗᵍᵔᵑ

㻞㻚㻌ᥦ᱌᪉ᘧ

n ⡆᫆ㄆド

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

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

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

㻿㼑㼚㼐㼑㼞

㻏㻝 㻴㼍㼟㼔

㻰㼍㼠㼍 㻹㻭㻯

㻏㻝 㻴㼍㼟㼔

㻏㻝 㻏㻝

㻾㼑㼏㼑㼕㼢㼑㼞

ᵐᵎᵍᵔᵑ

㻞㻚㻌ᥦ᱌᪉ᘧ

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

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

ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ

◚Რ

ཷ⌮

᪤ Ꮡ ᪉ ᘧ

㛤ጞ

ᵐᵏᵍᵔᵑ

㻞㻚㻌ᥦ᱌᪉ᘧ

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

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

ᡂຌ

ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ

ኻᩋ

◚Რ

ཷ⌮

᪤ Ꮡ ᪉ ᘧ ᥦ

᱌ ᪉ ᘧ

㛤ጞ

ᵐᵐᵍᵔᵑ

㻞㻚㻌ᥦ᱌᪉ᘧ

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

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

ᡂຌ

ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ

ኻᩋ

◚Რ

ཷ⌮

᪤ Ꮡ ᪉ ᘧ ᥦ

᱌ ᪉ ᘧ

㛤ጞ

n ỖểỮỄỉɧദἣἃἕἚử ẮẮỂᄊూẴỦẮểầỂẨỦ

n

ቇତἡἕἉἷ͌ỊᵖᶀᶇᶒễỉỂ

ᄊూỂẨễẟẮểờẝỦầύ

ଏ܍ỉᢿЎỂỽἢὊӧᏡ

n ϼྸỉ᝟ᒵỊݱẰẟ

ᵐᵑᵍᵔᵑ

㻟㻚㻌ᐇ⿦

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 ;

ᵐᵒᵍᵔᵑ

㻟㻚㻌ᐇ⿦

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

ᵐᵓᵍᵔᵑ

㻠㻚㻌ホ౯

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

n ౑⏝ゝㄒ䠖㻯

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

n ⿦⨨䛾௙ᵝ

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

䝩䝇䝖䝬䝅䞁 ௬᝿䝬䝅䞁

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

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

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

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

ᵐᵔᵍᵔᵑ

㻠㻚㻌ホ౯

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

ᵐᵕᵍᵔᵑ

㻠㻚㻌ホ౯

n ᥦ᱌᪉ᘧ䜢௨ୗ䛾ほⅬ䛛䜙ホ౯

n ᥦ᱌᪉ᘧ䛾᭷⏝ᛶ

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ṇつ䛾䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛾ጇᙜᛶ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛻䜘䜛ẚ㍑

ᵐᵖᵍᵔᵑ

㻠㻚㻌ホ౯

n ᥦ᱌᪉ᘧ䜢௨ୗ䛾ほⅬ䛛䜙ホ౯

n ᥦ᱌᪉ᘧ䛾᭷⏝ᛶ

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ṇつ䛾䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛾ጇᙜᛶ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛻䜘䜛ẚ㍑

ᵐᵗᵍᵔᵑ

㻠㻚㻌ホ౯

n ୙ṇ䝟䜿䝑䝖䛿

䛔䛪䜜䛛䛾ฎ⌮䛷

◚Რ䛥䜜䜛

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

䛩䜛䛸䠈

Ps + Pr + Pm = 1

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ 䝏䜵䝑䜽

㻹㻭㻯ㄆド ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ

ኻᩋ 䠄☜⋡䠖Ps䠅

䠄☜⋡䠖Pr䠅

䠄☜⋡䠖Pm䠅

ts

tr

tm

◚ Რ

㛤ጞ

ᵑᵎᵍᵔᵑ

㻠㻚㻌ホ౯

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

E = ts Ps

+ (ts + tr ) Pr

+ (ts + tr + tm ) Pm

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ 䝏䜵䝑䜽

㻹㻭㻯ㄆド ᡂຌ

ᡂຌ

ኻᩋ

ኻᩋ

ኻᩋ 䠄☜⋡䠖Ps䠅

䠄☜⋡䠖Pr䠅

䠄☜⋡䠖Pm䠅

ts

tr

tm

◚ Რ

㛤ጞ

ᵑᵏᵍᵔᵑ

㻠㻚㻌ホ౯

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

n Ps 䛿ᐃᩘ䠈 Pr 㻘㻌 Pm 䛿㻹㻭㻯ㄆド䛻฿㐩䛩䜛☜⋡䛜

᭱኱䛸䛺䜛䛸䛝䛾⌮ㄽ್䠈 ts 㻘㻌 tr 㻘㻌 tm 䛿ᐇ ್

n 䛣䛾䛸䛝䠈

Ps =1 − 1

28 = 9.961 × 10−1 Pr = 1.819 × 10−12

Pm = 3.906 × 10−3

E = 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]

ᵑᵐᵍᵔᵑ

㻠㻚㻌ホ౯

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

ᵑᵑᵍᵔᵑ

㻠㻚㻌ホ౯

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

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

▷⦰䛩䜛䛣䛸䛜䛷䛝䜛

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

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

E !

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

ᥦ᱌᪉ᘧ䠖

᪤Ꮡ᪉ᘧ䠖

ᵑᵒᵍᵔᵑ

㻠㻚㻌ホ౯

n ᥦ᱌᪉ᘧ䜢௨ୗ䛾ほⅬ䛛䜙ホ౯

n ᥦ᱌᪉ᘧ䛾᭷⏝ᛶ

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ṇつ䛾䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛾ጇᙜᛶ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛻䜘䜛ẚ㍑

ᵑᵓᵍᵔᵑ

㻠㻚㻌ホ౯

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

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

㛤ጞ

ᵑᵔᵍᵔᵑ

㻠㻚㻌ホ౯

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

᫬㛫䜢せ䛩䜛

䝸䝥䝺䜲㜵ᚚ䜴䜱䞁䝗䜴

᭦᪂ฎ⌮

ts tr tm

tu

⡆᫆ㄆド

䝸䝥䝺䜲ᨷᧁ䝏䜵䝑䜽

㻹㻭㻯ㄆド

10tm

⡆᫆ㄆド䛾㈇Ⲵ

䠄ཷಙฎ⌮᫬㛫䜈䛾ᙳ㡪䠅䛿 ᴟ䜑䛶ᑠ䛥䛔

㛤ጞ

ᵑᵕᵍᵔᵑ

㻠㻚㻌ホ౯

n ᥦ᱌᪉ᘧ䜢௨ୗ䛾ほⅬ䛛䜙ホ౯

n ᥦ᱌᪉ᘧ䛾᭷⏝ᛶ

n ୙ṇ䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ṇつ䛾䝟䜿䝑䝖䛾᳨ドฎ⌮᫬㛫

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛾ጇᙜᛶ

n ⡆᫆䝝䝑䝅䝳್䛾㛗䛥䛻䜘䜛ẚ㍑

ᵑᵖᵍᵔᵑ

㻠㻚㻌ホ౯

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

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

32 9.9999 × 10−1 0.823

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

ᵑᵗᵍᵔᵑ

㻠㻚㻌ホ౯

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

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

ᵒᵎᵍᵔᵑ

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 㻵㻯㼂䠖ㄆド䝁䞊䝗

IP header

ESP header

TCP

header Data ESP

Trailer ICV encrypted

authenticated

ᵒᵔᵍᵔᵑ

௜㘓

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

ᵒᵕᵍᵔᵑ

௜㘓

n 㻺㼀㻹➃ᮎ

n 㻺㼀㻹㼛㼎㼕㼘㼑ᶵ⬟䜢ᐇ⿦䛧䛯

➃ᮎ

n 㻰㻯㻌㻔㻰㼕㼞㼑㼏㼠㼕㼛㼚㻌㻯㼛㼛㼞㼐㼕㼚㼍㼠㼛㼞㻕

n ௬᝿㻵㻼䜰䝗䝺䝇䛾⟶⌮䞉㓄ᕸ

n ௬᝿㻵㻼䜰䝗䝺䝇䈈㏻ಙ㆑ูᏊ

n ᐇ㻵㻼䜰䝗䝺䝇䈈఩⨨㆑ูᏊ

n ㏻ಙ⤒㊰⏕ᡂ䛾ᣦ♧

ᵧᶌᶒᶃᶐᶌᶃᶒ

ᵬᵲᵫᇢ஛ ᵢᵡ ᵫᵬ

ᵬᵲᵫᇢ஛

ᵡᵬ

ᵮᶐᶇᶔᵿᶒᶃ ᵬᶃᶒᶕᶍᶐᶉ

ᵬᵟᵲ

ᵫᵬ ᵘᴾᵫᶍᶀᶇᶊᶃᴾᵬᶍᶂᶃ

ᵡᵬ ᵘᴾᵡᶍᶐᶐᶃᶑᶎᶍᶌᶂᶃᶌᶒᴾᵬᶍᶂᶃ

ᵒᵖᵍᵔᵑ

௜㘓

n 㻾㻿㻌㻔㻾㼑㼘㼍㼥㻌㻿㼑㼞㼢㼑㼞㻕

n ┤᥋⤒㊰䜢⏕ᡂ䛷䛝䛺䛔㝿䛻 䝟䜿䝑䝖䜢୰⥅

n ┤᥋⤒㊰䜢⏕ᡂ䛷䛝䛺䛔౛

n 㻹㻺䞉㻯㻺䛾୍᪉䛜㻵㻼㼢㻠䠈

௚᪉䛜㻵㻼㼢㻢

n 㻹㻺䞉㻯㻺䛜␗䛺䜛㻺㻭㼀㓄ୗ

ᵧᶌᶒᶃᶐᶌᶃᶒ

ᵢᵡ

ᵬᵲᵫᇢ஛

ᵮᶐᶇᶔᵿᶒᶃ

ᵬᶃᶒᶕᶍᶐᶉ

ᵬᵟᵲ

ᵰᵱ ᵬᵲᵫᇢ஛

ᵫᵬ

ᵬᵟᵲ

ᵫᵬ ᵘᴾᵫᶍᶀᶇᶊᶃᴾᵬᶍᶂᶃ

ᵡᵬ ᵘᴾᵡᶍᶐᶐᶃᶑᶎᶍᶌᶂᶃᶌᶒᴾᵬᶍᶂᶃ

ᵮᶐᶇᶔᵿᶒᶃ

ᵬᶃᶒᶕᶍᶐᶉ

ᵒᵗᵍᵔᵑ

௜㘓

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

ᵓᵎᵍᵔᵑ

௜㘓

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

ᵓᵏᵍᵔᵑ

௜㘓

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

ᵓᵐᵍᵔᵑ

௜㘓

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

n 㝖⟬ἲ

n ஌⟬ἲ

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

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

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

䜰䝹䝂䝸䝈䝮 ฎ⌮᫬㛫

[μs]

㝖⟬ἲ

0.544

஌⟬ἲ

1.247

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

0.410

ᵓᵑᵍᵔᵑ

௜㘓

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

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

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

ᵓᵒᵍᵔᵑ

௜㘓

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

n ඛ㏙䛧䛯㏻䜚 lh = 8

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

ᵓᵓᵍᵔᵑ

௜㘓

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

n ඛ㏙䛧䛯㏻䜚 lh = 8

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

ᵓᵔᵍᵔᵑ

௜㘓

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

n ඛ㏙䛧䛯㏻䜚 ln = 32

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

ᵓᵕᵍᵔᵑ

௜㘓

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

n ඛ㏙䛧䛯㏻䜚 ln = 32

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

ᵓᵖᵍᵔᵑ

௜㘓

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

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

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

ᵓᵗᵍᵔᵑ

௜㘓

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

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

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

ᵔᵎᵍᵔᵑ

௜㘓

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

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

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

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

85 116

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

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

ᵔᵏᵍᵔᵑ

௜㘓

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

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

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

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

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

1 2 16 2 ln

−1

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

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

ᵔᵐᵍᵔᵑ

௜㘓

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

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

ᵔᵑᵍᵔᵑ

௜㘓

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

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

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

n lh 䛜኱䛝䛟䛺䜛䜋䛹䠈 Ps ≈ 1 㻘㻌 Pr ≈ 0 㻘㻌 Pm ≈ 0 䛸䛺䜛䛣䛸䛜 䜟䛛䜛

lh [bit] ts [ μs ] Ps Pr Pm

8 0.536 9.9609 × 10−1 1.8190 × 10−12 3.9063 × 10−3

16 0.675 9.9998 × 10−1 7.1054 × 10−15 1.5259 × 10−5

32 0.823 9.9999 × 10−1 1.0842 × 10−19 2.3283 × 10−10