Ein Automat für Name-Stamp Protokolle

Definition 22 (Nichtdeterministischer Automat (NFA))
Der Fünf-Tupel

$$M = (Z,\Sigma,\delta,S,E)$$

ist ein nichtdeterministischer Automat (NFA) mit $Z$ Zustandsmenge, $\Sigma$ Eingabealphabet

$$\delta:\;Z \times \Sigma\;\rightarrow\;{\cal P}(Z)$$

Zustandsübergangsfunktion, $S \subseteq Z$ die Menge der Anfangszustände und $E \subseteq Z$ die Menge der Endzustände.

Definition 23 (Akzeptierte Wortmenge eines NFA)
Sei $M = (Z,\Sigma,\delta,S,E)$ ein NFA, $W(\Sigma) \ni x = x_1...x_n$, $Z' \subseteq Z$ und

$$\hat{\delta}:\;Z \times W(\Sigma)\;\rightarrow\;{\cal P}(Z)$$

mit $\hat{\delta}(Z',x) \ni z'$ gdw wenn eine Folge von Zuständen $z_0,...,z_{n-1},z' \in Z$ existiert mit $z_0 \in Z_0$, $z_i \in \hat{\delta}(z_{i-1},x_i)$ für $i=1,...,n$ und $z' \in \hat{\delta}(z_{n-1},x_n)$. Die akzeptierte Wortmenge $W_M$ des NFA $M$ ist dann

$$W_M = \{x \in W(\Sigma)\;\vert\;\hat{\delta}(S,x) \cap E \neq \emptyset\}$$

Beide Definition nach [4].

Definition 24 (NFA für Name-Stamp Protokoll)
Sei $T=\{\alpha_i,\beta_j\}$ ein Name-Stamp Protokoll und $A = (Z,\Sigma,\delta,S,E)$ ein NFA. $A$ ist ein NFA für das Name-Stamp Protokoll $T$, wenn $S = \{0\}$, $E = \{1\}$ und

$$\Sigma = E \cup D \cup \{i_b,d_b\;\vert\;B\in\{X,Y,Z\}\}$$

Weiterhin bildet die Zustandsübergangsfunktion Kanten von Zustand $0$ nach $1$ entsprechend den Buchstaben aus $\alpha_1$, Kanten von Zustand $0$ nach $0$ für alle

$$x \in \Sigma_z = E \cup \{D_z\} \cup \{i_b,d_b\;\vert\;B\in\{X,Y,Z\}$$

und entsprechend den Buchstaben aller $\alpha_i$ sowie $\beta_j$ für die Teilnehmer $X$,$Y$ und $Z$.

Beispiel 6
Sei $T = \{\alpha_1,\beta_1\}$ mit

$$\alpha_1 = E_y$$

und

$$\beta_1 = E_xD_y$$

das als Beispiel 1 oben eingeführte Name-Stamp Protokoll. Der zugehörige NFA $A = (Z,\Sigma,\delta,S,E)$ ist dann bestimmt durch:

$$\begin{eqnarray*} Z & = & \{0,1,2,4,5,6,7\} \\ \Sigma & = & E \cup D \cup \{i_b... ...\;\vert\;B\in\{X,Y,Z\}\} \\ S & = & \{0\} \\ E & = & \{1\} \\ \end{eqnarray*}$$

sowie der durch folgende Tabelle gegebenen Zustandsübergangsfunktion $\delta$

$\delta$	0	1	2	3	4	5	6	7
$E_x$	{0,2,3}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$E_y$	{0,1,4,5}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$E_z$	{0,6,7}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$D_x$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\{0\}$	$\emptyset$	$\{0\}$	$\emptyset$
$D_y$	{0}	$\emptyset$	$\{0\}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\{0\}$
$D_z$	{0}	$\emptyset$	$\emptyset$	$\{0\}$	$\emptyset$	$\{0\}$	$\emptyset$	$\emptyset$
$i_x$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$i_y$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$i_z$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$d_x$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$d_y$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$d_z$	{0}	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$

<>

Bemerkung: Offensichtlich gilt für die vom oben eingeführten NFA $A = (Z,\Sigma,\delta,S,E)$ für eine Name-Stamp Protokoll $T=\{\alpha_i,\beta_j\}$ mit den Teilnehmern $X$ und $Y$ sowie dem Angreifer $Z$ akzeptierte Sprache:

$$W_A = (V_Z \cup N_i(X,Y))^\star$$

wobei $V_Z$ die in der ersten Definition zu sicheren Name-Stamp Protokollen eingeführte Wortmenge ist. D.h. wir können nun vollkommen analog zu dieser Definition eine weitere auf Basis des eingeführten NFA finden.

Definition 25 (Sicheres Name-Stamp Protokoll (2))
Sei $T=\{\alpha_i,\beta_j\}$ ein Name-Stamp Protokoll und $A = (Z,\Sigma,\delta,S,E)$ der zugehörige NFA. $T$ ist sicher gdw

$$\neg \exists_{\gamma \in W_A}:\;\overline{\gamma}=\lambda$$