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