internals.tex

含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种CheckSum校验、多种MAC校验等几十种加密算法的程序

\documentclass{article}

\setlength{\textwidth}{6.75in} % 1 inch side margins
\setlength{\textheight}{9in} % ~1 inch top and bottom margins

\setlength{\headheight}{0in}
\setlength{\topmargin}{0in}
\setlength{\headsep}{0in}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\title{Botan Internals}
\author{Jack Lloyd ([e-mail])}
\date{July 30, 2002}

\newcommand{\filename}[1]{\texttt{#1}}
\newcommand{\manpage}[2]{\texttt{#1}(#2)}

\newcommand{\function}[1]{\textbf{#1}}
\newcommand{\type}[1]{\texttt{#1}}
\renewcommand{\arg}[1]{\textsl{#1}}

\begin{document}

\maketitle

\tableofcontents

\parskip=5pt

\section{Introduction}

This document is intended to document some of the trickier and/or more
complicated parts of Botan. This is not going to be terribly useful if you
just want to use the library, but for people wishing to understand how it
works, or contribute new code to it, it will hopefully prove helpful.

I've realized that a lot of things Botan does internally are pretty hard to
understand, and that a lot of things are only inside my head, which is a bad
place for them to be (things tend to get lost in there, not to mention the
possibility that I'll get hit by a truck next week).

This document is currently very incomplete. I'll be working on it as I have
time.

\pagebreak

\section{Filter}

Need something here.

\section{Pipe}

Pipe is, conceptually, a tree structure of Filter objects. There is a single
unique top, and an arbitrary number of leaves (which are SecureQueue objects).
SecureQueue is a simple Filter that buffers it's input.

Writing into the pipe writes into the top of the tree. The filter at the top
of the tree writes it's output into the next Filter, and so on until eventually
data trickles down into the bottommost Filters, where the data is stored for
later retrieval.

When a new message is started, Pipe searches through the tree of Filters and
finds places where the \arg{next} field of the Filter is NULL. This implies
that it was the lowest layer of the Filter tree that the user added. It then
adds SecureQueue objects onto these Filters. These queues are also stored in a
\type{std::vector} called \arg{messages}. This is how the Pipe knows how to
read from them later without doing a tree traversal every time.

Pipe will, if asked, destroy the existing tree structure, in order to create a
new one. However, the queue objects are not deleted, because Pipe might need to
read from them later.

An optimization in future versions will involve deleting empty queues that we
``know'' can't be written to, and then replace their field in \arg{messages}
with NULL. On reading, Pipe will know that this means that the queue is empty,
and act as if such a queue was really there. This is relatively minor, because
in recent versions an empty queue only takes up a few dozen bytes (previous to
0.8.4 or so, an empty queue still took up 4 kilobytes of memory).

\section{Library Initialization}

A lot of messy corner cases.

\section{Lookup Mechanism}

Most objects know their name, and they know how to create a new copy of
themselves. We build mapping tables that map from an algorithm name into a
single instance of that algorithm. The tables themselves can be found in
\filename{src/lookup.cpp}.

There are a set of functions named \function{add\_algorithm} that can be used
to populate the tables. We get something out of the table with
\function{retrieve\_x}, where x is the name of a type (\texttt{block\_cipher},
\texttt{hash}, etc). This returns a const pointer to the single unique instance
of the algorithm that the lookup tables know about. If it doesn't know about
it, it falls back on calling a function called
\function{try\_to\_get\_x}. These functions live in
\filename{src/algolist.cpp}. They are mostly used to handle algorithms which
need (or at least can have) arguments passed to them, like \type{HMAC} and
\type{SAFER\_SK}. It will return NULL if it can't find the algorithm at all.

When it's asked for an algorithm it doesn't know about (ie, isn't in the
mapping tables), the retrieval functions will ask the try-to-get functions if
\emph{they} know about it. If they do, then the object returned will be stored
into the table for later retrieval.

The functions \function{get\_x} call the retrieval functions. If we get back
NULL, an exception is thrown. Otherwise it will call the \function{clone}
method to get a new copy of the algorithm, which it returns.

The various functions like \function{output\_length\_of} call the retrieval
function for each type of object that the parameter in question (in this case,
\texttt{OUTPUT\_LENGTH}) might be meaningful for. If it manages to get back an
object, it will return (in this case) the \texttt{OUTPUT\_LENGTH} field of the
object. No allocations are required to call this function: all of it's
operations work directly on the copies living in the lookup tables.

\section{Allocators}

A big (slow) mess.

\section{BigInt}

Read ``Handbook of Applied Cryptography''.

\end{document}