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