Remove the redundant file headers.
[mdwtools] / crypto.dtx
1 % \begin{meta-comment} <general public licence>
2 %%
3 %% crypto package -- useful macros for typesetting crypto papers
4 %% Copyright (c) 2001 Mark Wooding
5 %%
6 %% This program is free software; you can redistribute it and/or modify
7 %% it under the terms of the GNU General Public License as published by
8 %% the Free Software Foundation; either version 2 of the License, or
9 %% (at your option) any later version.
10 %%
11 %% This program is distributed in the hope that it will be useful,
12 %% but WITHOUT ANY WARRANTY; without even the implied warranty of
13 %% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 %% GNU General Public License for more details.
15 %%
16 %% You should have received a copy of the GNU General Public License
17 %% along with this program; if not, write to the Free Software Foundation,
18 %% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 % \end{meta-comment}
20 %
21 % \begin{meta-comment} <Package preambles>
22 %<+package>\NeedsTeXFormat{LaTeX2e}
23 %<+package>\ProvidesPackage{crypto}
24 %<+package> [2001/09/16 1.0 Crypto typesetting]
25 % \end{meta-comment}
26 %
27 % \CheckSum{258}
28 %% \CharacterTable
29 %% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
30 %% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
31 %% Digits \0\1\2\3\4\5\6\7\8\9
32 %% Exclamation \! Double quote \" Hash (number) \#
33 %% Dollar \$ Percent \% Ampersand \&
34 %% Acute accent \' Left paren \( Right paren \)
35 %% Asterisk \* Plus \+ Comma \,
36 %% Minus \- Point \. Solidus \/
37 %% Colon \: Semicolon \; Less than \<
38 %% Equals \= Greater than \> Question mark \?
39 %% Commercial at \@ Left bracket \[ Backslash \\
40 %% Right bracket \] Circumflex \^ Underscore \_
41 %% Grave accent \` Left brace \{ Vertical bar \|
42 %% Right brace \} Tilde \~}
43 %%
44 %
45 % \begin{meta-comment}
46 %
47 %<*driver>
48 \input{mdwtools}
49 \describespackage{crypto}
50 \mdwdoc
51 %</driver>
52 %
53 % \end{meta-comment}
54 %
55 %^^A-------------------------------------------------------------------------
56 % \section{User guide}
57 %
58 % \subsection{Algorithm typesetting}
59 %
60 % A lot of provable-security papers need to be able to typeset algorithms
61 % describing adversaries, schemes, oracle behaviour, etc. There is a
62 % (relatively) standard format for doing this which we support.
63 %
64 % \DescribeEnv{program}
65 % The \env{program} environment provides handy notation for describing
66 % algorithms formally. It gives a \env{tabbing} environment, so that things
67 % can be laid out nicely, and allows fragments of algorithms to be laid out
68 % in columns or rows, with separating rules.
69 %
70 % \DescribeMacro\next
71 % Within the \env{program} environment, the |\next| command stops typesetting
72 % the current column, typesets a vertical separator rule, and starts a new
73 % column. Adjacent columns are spaced out evenly across the page, with equal
74 % space around the rules rules and at the current margins. This means that
75 % the rules don't line up, but it still seems to provide a pleasing effect.
76 %
77 % \DescribeMacro\newline
78 % The |\newline| macro begins a new row of algorithm typesetting. A page
79 % break is possible at a |\newline|.
80 %
81 % \DescribeMacro\kw
82 % A number of standard keywords are available, as shown in
83 % table~\ref{tab:kw}. The typsetting of these is done by the |\kw| command,
84 % which usually sets its argument in text bold face, but can be redefined.
85 % The standard definition uses |\xspace| so that you don't need to remember
86 % to say \verb*+\ + after a keyword command.
87 % \begin{table}
88 % \centering
89 % \def\row#1{\texttt{\string#1} & #1 \\}
90 % \begin{tabular}{ll}
91 % \textbf{Command} & \textbf{Keyword} \\
92 % \row\RETURN
93 % \row\IF
94 % \row\THEN
95 % \row\ELSE
96 % \row\REPEAT
97 % \row\WHILE
98 % \row\UNTIL
99 % \row\FOREVER
100 % \row\DO
101 % \row\FOR
102 % \row\FOREACH
103 % \row\FROM
104 % \row\IN
105 % \row\TO
106 % \row\ABORT
107 % \row\PARSE
108 % \row\NEW
109 % \row\AS
110 % \end{tabular}
111 % \caption{Keywords available for algorithm typesetting}
112 % \label{tab:kw}
113 % \end{table}
114 %
115 % \DescribeMacro\ind
116 % Within a \env{program} environment, the |\ind| command shunts the indent
117 % level 1\,em to the right.
118 %
119 % \DescribeMacro\gets
120 % \DescribeMacro\getsr
121 % \DescribeMacro\inr
122 % Assignment can be represented using the standard command |\gets|, which
123 % typesets a left-pointing arrow `$\gets$'. Random sampling -- the selection
124 % of a random element from a set or probability distribution -- can be
125 % represented using the new command |\getsr|, which typesets an arrow with a
126 % little `R' above it `$\getsr$'. Random membership -- showing that
127 % something is a random variable with some distribution -- can be represented
128 % using the |\inr| command, which just typesets an $\in$ sign with a
129 % subscript `R': `$\inr$'.
130 %
131 % Should one wish, one can use a different character than `R' to denote
132 % randomness. Some authors use `\$', for example. I know of one
133 % (cheapskate?) author who has used `\rlap/c'. Redefining the |\random|
134 % command lets you do this. For example, you can say
135 % |\newcommand{\random}{\$}| should you so wish.
136 %
137 % \DescribeMacro\id
138 % Long identifiers can be typeset using the |\id| command. giving the
139 % identifier name as an argument. The |\id| command is only valid in maths
140 % mode. As currently set up, |\id| sets its argument in \emph{text} italics;
141 % this seems to look better in documents which use a PostScript body face and
142 % Computer Modern for maths.
143 %
144 % \DescribeMacro\Xid
145 % It's handy to be able to glue a bit of (possibly fancy) maths typesetting
146 % to an identifier, e.g., to construct $\Xid{H'}{list}$, or
147 % $\Xid{\mathcal{E}}{CTR$\$$}^F$. This is done using
148 % \syntax{"\\Xid{"<maths>"}{"<text>"}"}. The two bits are joined by a text
149 % hyphen `-'.
150 %
151 % \DescribeMacro\cookie
152 % Sometimes textual names are used for special `symbols', which have meaning
153 % to algorithms, e.g., the symbols $\cookie{find}$ and $\cookie{guess}$ in
154 % the standard indistinguishability game. These can be typeset using the
155 % |\cookie| command.
156 %
157 % \subsection{Other stuff}
158 %
159 % \DescribeMacro\Thing
160 % In the quantifiable-security world, there are standard symbols for
161 % advantage, success probability, insecurity, etc. The generic `style hook'
162 % for these is \syntax{"\\Thing{"<name>"}{"<notion>"}{"scheme"}"}, which
163 % typesets $\Thing{name}{notion}{scheme}$. It helps a lot if you have the
164 % \package{amstext} package loaded.
165 %
166 % \DescribeMacro\Succ
167 % \DescribeMacro\Adv
168 % \DescribeMacro\InSec
169 % \DescribeMacro\Expt
170 % \DescribeMacro\Game
171 % \begin{synshorts}
172 % Some standard `things' are provided: "\\Succ{"<notion>"}{"<scheme>"}",
173 % "\\Adv{"<notion>"}{"<scheme>"}", "\\InSec{"<notion>"}",
174 % "\\Expt{"<notion>"}{"<scheme>"}", and "\\Game{"<notion>"}{"<scheme>"}".
175 % \end{synshorts}
176 %
177 % \DescribeMacro\G
178 % In proofs which proceed by varying the rules of the game played by the
179 % adversary and bounding the probability of it noticing at each step, game
180 % names are usually typeset as $\G n$ for small numbers $n$. The command
181 % \syntax{"\\G{"<n>"}"} command does this typesetting. There's an optional
182 % argument, which is a symbol to write instead of `G'.
183 %
184 % \DescribeMacro\Func
185 % \DescribeMacro\Perm
186 % When dealing with finite PRFs and PRPs, we need to talk about the set of
187 % \emph{all} functions (or permutations) over particular sets, usually
188 % $n$-vectors of bits. The macros \syntax{"\\Func{"<l>"}{"<L>"}"} and
189 % \syntax{"\\Perm{"<L>"}"} typeset $\Func{l}{L}$ and $\Perm{L}$ respectively,
190 % and are intended to denote the sets of all functions $F\colon \{0, 1\}^l
191 % \to \{0, 1\}^L$ and all permutations $\Pi\colon \{0, 1\}^L \to \{0, 1\}^L$
192 % respectively.
193 %
194 % \DescribeMacro\PKCS
195 % Finally, the |\PKCS| macro typesets `\PKCS{$n$}', allowing you to name RSA
196 % Security Inc.'s Public Key Cryptography Standards in a relatively nice way.
197 %
198 % \implementation
199 %
200 %
201 %^^A-------------------------------------------------------------------------
202 % \section{Implementation}
203 %
204 % We need David Carlisle's handy \package{xspace} package and the AMS |\text|
205 % command.
206 %
207 % \begin{macrocode}
208 %<*package>
209 \RequirePackage{amstext}
210 \RequirePackage{xspace}
211 % \end{macrocode}
212 %
213 % \subsection{Algorithm typsetting}
214 %
215 % \begin{macro}{\cookie}
216 % \begin{macro}{\kw}
217 % \begin{macro}{\id}
218 %
219 % First, some style issues. Note the |\xspace| at the end of |\kw|.
220 %
221 % \begin{macrocode}
222 \def\cookie#1{\text{\normalfont\sffamily\/#1\/}}
223 \def\kw#1{\text{\normalfont\bfseries\/#1\/}\xspace}
224 \def\id#1{\text{\normalfont\itshape\/#1\/}}
225 % \end{macrocode}
226 %
227 % \end{macro}
228 % \end{macro}
229 % \end{macro}
230 %
231 % \begin{macro}{\getsr}
232 % \begin{macro}{\inr}
233 %
234 % The symbols for random selection and membership are fairly easy. The `R'
235 % over $\getsr$ is actually in scriptscript style, because that seems to look
236 % nicer.
237 %
238 % \begin{macrocode}
239 \providecommand\random{R}
240 \def\inr{\mathrel{\in_{\random}}}
241 \def\getsr{\mathrel{\mathop{\gets}\limits^{\scriptscriptstyle\random}}}
242 % \end{macrocode}
243 %
244 % \end{macro}
245 % \end{macro}
246 %
247 % \begin{macro}{\Xid}
248 %
249 % The compound identifiers set by |\Xid| are easy.
250 %
251 % \begin{macrocode}
252 \def\Xid#1#2{\id{$#1$-#2}}
253 % \end{macrocode}
254 %
255 % \end{macro}
256 %
257 % Now for the various keywords. These are trivial, but useful.
258 %
259 % \begin{macrocode}
260 \def\RETURN{\kw{return}}
261 \def\IF{\kw{if}}
262 \def\THEN{\kw{then}}
263 \def\ELSE{\kw{else}}
264 \def\REPEAT{\kw{repeat}}
265 \def\WHILE{\kw{while}}
266 \def\UNTIL{\kw{until}}
267 \def\FOREVER{\kw{forever}}
268 \def\DO{\kw{do}}
269 \def\FOR{\kw{for}}
270 \def\FOREACH{\kw{for\,each}}
271 \def\FROM{\kw{from}}
272 \def\IN{\kw{in}}
273 \def\TO{\kw{to}}
274 \def\ABORT{\kw{abort}}
275 \def\PARSE{\kw{parse}}
276 \def\AS{\kw{as}}
277 \def\NEW{\ifmmode\mathop{\kw{new}}\else\kw{new}\fi}
278 \def\SEND{\kw{send}}
279 \def\OUTPUT{\kw{output}}
280 \def\STOP{\kw{stop}}
281 % \end{macrocode}
282 %
283 % \begin{environment}{program}
284 % \begin{macro}{\next}
285 % \begin{macro}{\newline}
286 % \begin{macro}{\ind}
287 %
288 % Now for the \env{program} environment and its associated twiddling. This
289 % is actually a little fiddly.
290 %
291 % At the beginning, if we're in vertical mode -- i.e., there was a paragraph
292 % break before the start of the environment -- then remember this, because it
293 % affects the typesetting at the end. Set up |\next| and |\newline| in terms
294 % of the underlying machinery, and start a row of algorithm.
295 %
296 % \begin{macrocode}
297 \def\program{%
298 \normalfont%
299 \@tempswatrue\ifvmode\@tempswafalse\fi%
300 \def\next{\program@end\vrule\program@begin}%
301 \def\newline{\program@endline\medskip\program@startline}%
302 \def\ind{\quad\=\+\kill}%
303 \ifdim\topsep<\parskip\topsep\parskip\fi%
304 \ifdim\@topsepadd<\z@\@topsepadd\z@\fi%
305 \begingroup\trivlist%
306 \advance\@topsep-\parskip\advance\@topsepadd-\parskip\item%
307 \program@startline%
308 }
309 % \end{macrocode}
310 %
311 % Ending the environment is easy-ish. We stop the current row and leave a
312 % gap, matching the one that |\poem@startline| adds automatically. If we
313 % were initially in horizontal mode, then don't indent the next paragraph,
314 % and ignore spaces after the |\end{program}| command.
315 %
316 % \begin{macrocode}
317 \def\endprogram{%
318 \program@endline\endtrivlist\endgroup%
319 \if@tempswa\@endparenv\fi\@ignoretrue%
320 }
321 % \end{macrocode}
322 %
323 % Now for the guts of all of this. First of all, we turn to the typesetting
324 % of a column, which is just hfil glue, a \env{minipage} with zero width and
325 % a \env{tabbing} environment. The first tab is already set 1\,em in from
326 % the margin. We use \env{minipage} to set up the list parameters correctly
327 % and manage the initial and final spacing. The zero width is OK because
328 % \env{tabbing} sets a list of hboxes rather than using outer horizontal
329 % mode, so the |\hsize| is irrelevant.
330 %
331 % \begin{macrocode}
332 \def\program@begin{%
333 \begingroup%
334 \hfil%
335 \minipage[t]\z@%
336 \topsep\z@%
337 \itemsep\z@%
338 \parskip\z@\parsep\z@%
339 \partopsep\z@%
340 \tabbing%
341 % \end{macrocode}
342 %
343 % This is rather messy. The |\item| from the \env{trivlist} messes up the
344 % spacing. We remove the box, and fix |\prevdepth| to ensure that there's no
345 % glue at the top.
346 %
347 % \begin{macrocode}
348 \quad\=dummy\\%
349 \@stopfield%
350 \begingroup%
351 \setbox\z@\lastbox\unskip\unskip\unskip\setbox\z@\lastbox\unskip%
352 \endgroup%
353 \prevdepth-\@m\p@%
354 \@startfield\strut\ignorespaces%
355 }
356 % \end{macrocode}
357 %
358 % Ending a program has no discernable subtlety.
359 %
360 % \begin{macrocode}
361 \def\program@end{%
362 \endtabbing%
363 \endminipage%
364 \hfil%
365 \endgroup%
366 }
367 % \end{macrocode}
368 %
369 % Finally, the row setting is fairly easy. We have to ensure that we obey
370 % the prevailing list parameters.
371 %
372 % \begin{macrocode}
373 \def\program@startline{%
374 \moveright\@totalleftmargin%
375 \hb@xt@\linewidth\bgroup%
376 \program@begin%
377 }
378 \def\program@endline{%
379 \program@end%
380 \egroup%
381 }
382 % \end{macrocode}
383 %
384 % \end{macro}
385 % \end{macro}
386 % \end{macro}
387 % \end{environment}
388 %
389 % \subsection{Other stuff}
390 %
391 % \begin{macro}{\Thing}
392 % \begin{macro}{\Succ}
393 % \begin{macro}{\Adv}
394 % \begin{macro}{\InSec}
395 % \begin{macro}{\Expt}
396 % \begin{macro}{\Game}
397 %
398 % Typesetting |\Thing| is easy. This acts as a style hook for the rest of
399 % these things.
400 %
401 % \begin{macrocode}
402 \def\Thing#1#2#3{\text{\normalfont\bfseries#1}^{\text{\normalfont#2}}_{#3}}
403 % \end{macrocode}
404 %
405 % And now here they are.
406 %
407 % \begin{macrocode}
408 \def\Succ{\Thing{Succ}}
409 \def\Adv{\Thing{Adv}}
410 \def\InSec#1{\Thing{InSec}{#1}{}}
411 \def\Expt{\Thing{Expt}}
412 \def\Game{\Thing{Game}}
413 % \end{macrocode}
414 %
415 % \end{macro}
416 % \end{macro}
417 % \end{macro}
418 % \end{macro}
419 % \end{macro}
420 % \end{macro}
421 %
422 % \begin{macro}{\G}
423 %
424 % The name of a game is typeset simply as
425 %
426 % \begin{macrocode}
427 \newcommand\G[2][G]{\mathbf{#1}_{#2}}
428 % \end{macrocode}
429 %
430 % \end{macro}
431 %
432 % \begin{macro}{\Func}
433 % \begin{macro}{\Perm}
434 %
435 % The finite sets of functions and permutations are just a style choice. We
436 % choose to buck the standard trends and use caligraphic letters.
437 %
438 % \begin{macrocode}
439 \def\Func#1#2{\mathcal{F}^{#1,#2}}
440 \def\Perm#1{\mathcal{P}^{#1}}
441 % \end{macrocode}
442 %
443 % \end{macro}
444 % \end{macro}
445 %
446 % \begin{macro}{\PKCS}
447 %
448 % Finally, I find that \PKCS{$n$} looks best typeset like this:
449 %
450 % \begin{macrocode}
451 \def\PKCS#1{PKCS\,\##1}
452 % \end{macrocode}
453 %
454 % \end{macro}
455 %
456 % \vskip\parskip\vbox{ ^^A The best way I could find of keeping this lot
457 % ^^A together, I'm afraid.
458 % That's all there is. Byebye.
459 %
460 % \begin{macrocode}
461 %</package>
462 % \end{macrocode}
463 % \nopagebreak
464 %
465 % \hfill Mark Wooding, \today
466 % }
467 % \Finale
468 %
469 \endinput