mp-modsqrt: Always return the smaller possible square root.

[u/mdw/catacomb] / key.1

.\" -*-nroff-*-
.ie t \{\
.  if \n(.g \{\
.    fam P
.  \}
.  ds ss \s8\u
.  ds se \d\s0
.  ds us \s8\d
.  ds ue \u\s0
.  ds *b \(*b
.\}
.el \{\
.  ds ss ^
.  ds se
.  ds us _
.  ds ue
.  ds *b \fIbeta\fP
.\}
.de VS
.sp 1
.RS
.nf
.ft B
..
.de VE
.ft R
.fi
.RE
.sp 1
..
.TH key 1 "5 June 1999" "Straylight/Edgeware" "Catacomb cryptographic library"
.SH NAME
key \- simple key management system
.SH SYNOPSIS
.B key
.RB [ \-k
.IR keyring ]
.I command
.PP
where
.I command
is one of:
.PP
.B help
.RI [ command ...]
.br
.B show
.RI [ item ...]
.br
.B add
.RB [ \-lqrLS ]
.RB [ \-a
.IR alg ]
.RB [ \-b | \-B
.IR bits ]
.RB [ \-p
.IR param ]
.RB [ \-R
.IR tag ]
.br
\h'8n'
.RB [ \-A
.IR seed-alg ]
.RB [ \-s
.IR seed ]
.RB [ \-n
.IR bits ]
.br
\h'8n'
.RB [ \-e
.IR expire ]
.RB [ \-t
.IR tag ]
.RB [ \-c
.IR comment ]
.RB [ \-C
.IR curve ]
.br
\h'8n'
.I type
.IR attr ...
.br
.B expire
.IR tag ...
.br
.B delete
.IR tag ...
.br
.B tag
.I tag
.RI [ new-tag ]
.br
.B comment
.I tag
.RI [ comment ]
.br
.B setattr
.I tag
.IR attr ...
.br
.B getattr
.I tag
.I attr
.br
.B lock
.I qtag
.br
.B unlock
.I qtag
.br
.B list
.RB [ \-uqv ]
.RB [ \-f
.IR filter ]
.RI [ tag ...]
.br
.B fingerprint
.RB [ \-f
.IR filter ]
.RB [ \-a
.IR hash ]
.RI [ tag ...]
.br
.B verify
.RB [ \-f
.IR filter ]
.RB [ \-a
.IR hash ]
.I tag
.I fingerprint
.br
.B tidy
.br
.B extract
.RB [ \-f
.IR filter ]
.I file
.RI [ tag ...]
.br
.B merge
.I file
.SH DESCRIPTION
The
.B key
command performs useful operations on Catacomb keyring files.  It
provides a number of subcommands, by which the various operations may be
carried out.
.SS "Global options"
Before the command name,
.I "global options"
may be given.  The following global options are supported:
.TP
.BR "\-h, \-\-help " [ \fIcommand ...]
Writes a brief summary of
.BR key 's
various options to standard output, and
returns a successful exit status.  With command names, gives help on
those commands.
.TP
.B "\-v, \-\-version"
Writes the program's version number to standard output, and returns a
successful exit status.
.TP
.B "\-u, \-\-usage"
Writes a very terse command line summary to standard output, and returns
a successful exit status.
.TP
.BI "\-k, \-\-keyring " file
Names the keyring file which
.B key
is to process.  The default keyring, used if this option doesn't specify
one, is the file named
.B keyring
in the current directory.  The keyring must be stored in a regular file:
pipes, sockets, devices etc. are not allowed.
The
.B key
program attempts to lock the keyring before accessing it, using
.BR fcntl (2)
locking.  It will however time out after a short while (10 seconds) and
report a failure.
.SS Concepts
In addition to the actual key data itself, a Catacomb key has a number
of other pieces of information attached to it:
.TP
.B "keyid"
Every key has a 32-bit identifying number, written in hexadecimal.
Keyids are not actually related to the key contents: they're generated
randomly.  Applications use keyids to refer to specific keys; users are
probably better off with tags and types.  A
.I deleted
key cannot be looked up by keyid.
.TP
.B "tag"
A key's tag is a unique string which can be used by users and
applications to identify the key.  Tag strings may not contain spaces,
colons or dots.  A
.I deleted
key cannot be looked up by tag.  Whenever a tag name is wanted, a hex
keyid or key type string can be given instead.
.TP
.B "type"
A key's type string describes what the key may be used for.  The type
string is arbitrary, except that it may not contain whitespace
characters, dots or colons.  Applications use key types to obtain an
arbitrary but suitable key for some purpose.  An
.I expired
key cannot be looked up by type, but may be looked up by keyid or tag.
.TP
.B "key encoding"
There are a number of different ways in which keys can be represented,
according to the uses to which the key will be put.  Most symmetric
algorithms use
.I binary
keys.  Keys used with number-theoretic systems (like most common
public-key systems) use
.I "multiprecision integer"
keys.  Elliptic curve systems use
.I "curve point"
keys, which are either a pair of integers representing field elements,
or a `point at infinity'.  Algorithms which require several key
constituents (again, like most public-key systems) use
.I structured
keys, which consist of a collection of named parts.  It's possible to
store an
.I "ASCII string"
as a key, though this is usually done as a component of a structured
key.  Finally, keys (including structured keys) can be encrypted.
.TP
.B "filter"
Keys and key components may be selected by a filter expression, a
sequence of flag names separated by commas.  Flags are:
.BR binary ,
.BR integer ,
.BR struct ,
.BR ec ,
.BR string ,
or
.B encrypt
(describing the key encoding);
.BR symmetric ,
.BR private ,
.BR public ,
or
.B shared
(describing the category of key);
.B burn
and its negation
.B \-burn
(whether the key should be erased from memory after use); and
.B secret
and its negation
.B \-secret
(whether the key is safe to divulge).
.TP
.B "qualified tag"
A key component may be identified by the key's tag (or keyid, or type).
Subcomponents of structured keys are identified by following the tag by
a dot and the name of the subcomponent.
.TP
.B "expiry time"
Most keys expire after a certain amount of time.  Once a key has
expired, it will no longer be chosen as a result of a lookup by key
type.  However, it is not deleted until its deletion time is also
reached.
.TP
.B "deletion time"
A key's deletion time is the latest expiry time of any of the objects
which require that key.  For example, a key used for authenticating
cryptographic cookies should have its deletion time set to the longest
expiry time of any of the cookies it can authenticate.  Once a key's
deletion time is passed, it can no longer be referred to by
applications, and will be removed from the keyring next time it's
written to disk.
.TP
.B "comment"
A key may be given a comment when it's created.  The comment is for the
benefit of users, and isn't interpreted by applications at all.
(Hopefully.)
.TP
.B "attributes"
A key as zero or more name/value pairs.  The names and values are
arbitrary strings, except they may not contain null bytes.  Some
attributes may have meaning for particular applications or key types;
others may be assigned global meanings in future.
.SH "COMMAND REFERENCE"
.SS help
The
.B help
command behaves exactly as the
.B \-\-help
option.  With no arguments, it shows an overview of
.BR key 's
options; with arguments, it describes the named subcommands.
.SS show
The
.B show
command prints various lists of tokens understood by
.BR key .
With no arguments, it prints all of the lists; with arguments, it prints
just the named lists, in order.  The recognized lists can be enumerated
using the
.VS
key show list
.VE
command.  The lists are as follows.
.TP
.B list
The lists which can be enumerated by the
.B show
command.
.TP
.B hash
The hash functions which can be used with the
.B fingerprint
and
.B verify
commands.
.TP
.B ec
The built-in elliptic curves which can be used with the
.B add \-a ec
command.
.TP
.B dh
The built-in Diffie-Hellman groups which can be used with the
.B add \-a dh
command.
.TP
.B keygen
The key-generation algorithms which are acceptable to the
.B \-a
option of the
.B add
command.
.TP
.B seed
The pseudorandom generators which are acceptable to the
.B \-s
option of the
.B add
command.
.SS add
The
.B add
command creates a new key and adds it to the keyring.  The command
accepts the following options:
.TP
.BI "\-a, \-\-algorithm " alg
Selects a key generation algorithm.  The default algorithm is
.BR binary ;
the different algorithms are described below.  The command
.B key show keygen
lists the recognized key-generation algorithms.
.TP
.BI "\-b, \-\-bits " bits
The length of the key to generate, in bits.  The default, if this option
is not supplied, depends on the key-generation algorithm.
.TP
.BI "\-B, \-\-qbits " bits
The length of the subsidiary key or parameter, in bits.  Not all
key-generation algorithms have a subsidiary key size.
.TP
.BI "\-p, \-\-parameters " tag
Selects a key containing parameter values to copy.  Not all
key-generation algorithms allow the use of shared parameters.  A new key
also inherits attributes from its parameter key.
.TP
.BI "\-A, \-\-seedalg " seed-alg
Use the deterministic random number generator algorithm
.I seed-alg
to generate the key.  Use
.I before
the
.B \-s
or
.B \-n
options; without one of these,
.B \-A
has no effect.  The default algorithm is
.BR rmd160-mgf .
The command
.B key show seed
shows a list of recognized seeding algorithms.  The seeding algorithm
used to generate a key is recorded as the key's
.B seedalg
attribute.
.TP
.BI "\-s, \-\-seed " seed
Generate the key deterministically using the given
.IR seed ,
which should be a Base64-encoded binary string.  This is mainly useful
for parameters keys (types
.BR dsa-param
and
.BR dh-param ),
to demonstrate that a set of parameters has been generated in an honest
fashion.  The
.B dsarand
generation algorithm can be used to generate
.B dsa-param
keys as required by FIPS186.  The requested seed is recorded,
Base64-encoded, as the new key's
.B seed
attribute.
.TP
.BI "\-n, \-\-newseed " bits
Generate a new seed, with the given length in
.IR bits .
The generated seed is recorded, Base64-encoded, as the new key's
.B seed
attribute.
.TP
.BI "\-e, \-\-expire " expire
The expiry date for the generated key.  This may be the string
.RB ` forever '
if the key should never expire automatically, or any date acceptable to
the
.BR getdate (3)
library function.  Briefly,
.B getdate
understands absolute dates such as
.RB ` 1999-08-02 '
or
.RB ` "August 2nd, 1999" ',
and (perhaps more usefully) relative dates such as
.RB ` "+2 weeks" '.
The default is to allow a 2 week expiry, which isn't useful.
.TP
.BI "\-c, \-\-comment " comment
Sets a comment for the key.  The default is not to attach a comment.
.TP
.BI "\-C, \-\-curve " curve-spec
Use the elliptic curve described by
.I curve-spec
when generating elliptic curve parameters.
.TP
.BI "\-t, \-\-tag " tag
Selects a tag string for the key.  The default is not to set a tag.  It
is an error to select a tag which already exists.
.TP
.BI "\-r, \-\-retag"
If a
.B \-t
option is given, remove this tag from any key which already has it.
.TP
.BI "\-R, \-\-rand-id " tag
Selects the key to use for the random number generator.  Catacomb's
random number generator can be
.IR keyed ,
so that, even if the inputs to the generator are compromised, knowledge
of the key is also necessary to be able to predict the output.  By
default, the latest-expiring key with type
.B catacomb-rand
is used, if present; if not, no key is used.
.TP
.BI "\-l, \-\-lock"
Requests that the secret parts of the newly-generated key be encrypted
using a passphrase.
.TP
.BI "\-q, \-\-quiet"
Suppresses the progress indication which is usually generated while
time-consuming key generation tasks are being performed.
.TP
.BI "\-L, --lim-lee"
When generating Diffie-Hellman parameters, generate a Lim-Lee prime
rather than a random (or safe) prime.  See the details on Diffie-Hellman
key generation below.
.TP
.BI "\-S, --subgroup"
When generating Diffie-Hellman parameters with a Lim-Lee prime, choose a
generator of a prime-order subgroup rather than a subgroup of order
.RI ( p "- 1)/2."
.PP
The key's type is given by the required
.I type
argument.  Following the type are zero or more attributes, which are
attached to the key in the same way as for the
.B setattr
command.
.PP
The key-generation algorithms supported are as follows:
.TP
.B "binary"
Generates a plain binary key of the requested length.  If the requested
key length is not a multiple of eight, the high-order bits of the first
octet of the key are zeroed.  The default key length is 128 bits.
.TP
.B "des"
Generates a DES key, with parity bits.  The key length must be 56, 112
or 168; the default is 56.  The low-order bit of each octet is ignored by
the DES algorithm; it is used to give each octet odd parity.
.TP
.B "rsa"
Generates a public/private key pair for use with the RSA algorithm.
.IP
The key components are
.I p
and
.IR q ,
a pair of prime numbers;
.IR n ,
the product of
.I p
and
.IR q ;
.IR e ,
the public exponent;
.IR d ,
the private exponent, chosen such that
.IR ed \ \(==\ 1
(mod
.RI ( p \ \-\ 1)( q \ \-\ 1));
and some other values useful for optimizing private-key operations:
.IR q \*(ss\-1\*(se\ mod\  p ,
.IR d \ mod\  p \ \-\ 1,
and
.IR d \ mod\  q \ \-\ 1.
The values
.I n
and
.I e
constitute the public key; the rest must be kept secret.  The key size
requested by the
.B \-b
option determines the size of the modulus
.IR n ;
the default is 1024 bits.
.IP
The key generation algorithm chooses
.I p
and
.I q
to be
.I strong
primes: both
.IR p \ \-\ 1
and
.IR p \ +\ 1
have large prime factors \- call them
.I r
and
.I s
respectively \- and
.IR r \ \-\ 1
also has a large prime factor;
.I q
has similar properties.
.IP
The modulus
.I n
cannot be sensibly used as a shared parameter, since knowledge of
corrssponding public and private exponents is sufficient to be able to
factor the modulus and recover other users' private keys.
.TP
.B "dh-param"
Generates parameters for use with the Diffie-Hellman key exchange
protocol, and many related systems, such as ElGamal encryption and
signatures, and even DSA.  (The separate DSA algorithm uses the
generator described in FIPS186-1.)
.IP
The Diffie-Hellman parameters are a prime modulus
.I p
and a generator
.I g
of a subgroup of
.BR Z / \c
.IB p Z
of order
.IR q .
The
.B \-b
option controls the size of the modulus
.IR p ;
the default size is 1024 bits.
.IP
If no 
.I q
size is selected using the
.B \-B
option and the Lim-Lee prime option is disabled, then 
.I p
is chosen to be a `safe' prime (i.e.,
.IR p \ =\ 2 q \ +\ 1,
with
.I q
prime).  Finding safe primes takes a very long time.  In this case, the
value of
.I g
is fixed as 4.
.IP
If a size is chosen for
.I q
and Lim-Lee primes are not selected then the prime
.I q
is generated and
.I p
is chosen so that
.IR p \ \-\ 1
is a multiple of
.IR q .
.IP
If the
.B \-L
option was given Lim-Lee primes are selected: the parameters are chosen
such that
.IR p \ =\ 2\  q \*(us0\*(ue\ q \*(us1\*(ue\ q \*(us2\*(ue\ ...\ +\ 1,
where the
.IR q \*(us i\*(ue
are primes at least as large as the setting given by the
.B \-B
option (or 256 bits, if no setting was given).
.IP
If the
.B \-S
option was given, the generator
.I g
is chosen to generate the subgroup of order
.IR q \*(us0\*(ue;
otherwise,
.I g
will generate the group of order
.RI ( p \ \-\ 1)/2\ =\  q \*(us0\*(ue\ q \*(us1\*(ue\ q \*(us2\*(ue\ ...
.IP
Finally, the
.B \-C
option can be given, in which case the parameters are taken directly
from the provided group specification, which may either be the the name
of one of the built-in groups (say
.B "key show dh"
for a list) or a triple
.RI ( p ,\  q ,\  g ).
separated by commas.  No random generation is done in this case: the
given parameters are simply stored.
.TP
.B "dh"
Generates a public/private key pair for use with offline Diffie-Hellman,
ElGamal, DSA or similar discrete-logarithm-based systems.  It selects a
private key
.IR x \ <\  q ,
and computes the public key
.IR y \ =\  g\*(ssx\*(se \ mod\  p .
.TP
.B "dsa-param"
Generates parameters for the DSA algorithm.  DSA parameters are also
suitable for use with Diffie-Hellman and ElGamal system.
.IP
The main difference between DSA and Diffie-Hellman parameter generation
is thatthe DSA parameter generation
algorithm creates a
.I seed
from which the parameters are derived, and, assuming that the SHA-1 hash
function is strong, it's not feasible to construct a seed from which
deliberately weak parameters are derived.  The algorithm used is the one
described in the DSA standard, FIPS\ 186, extended only to allow
sequential search for a prime
.I q
and to allow arbitrary parameter sizes.  The seed is stored,
Base64-encoded, as the value of the attribute
.BR seed .
.IP
The default lengths for
.I p
and
.I q
are 768 and 160 bits respectively, since the DSA standard specifies that
.I q
be 160 bits, and the choice of 768 bits for
.I p
gives commensurate security.
.TP
.B "dsa"
Generates a public/private key pair for DSA.  As for Diffie-Hellman
keys, it selects a
private key
.IR x \ <\  q ,
and computes the public key
.IR y \ =\  g\*(ssx\*(se \ mod\  p .
.TP
.B "bbs"
Generates a public/private key pair for the Blum-Blum-Shub random-number
generator, and the Blum-Goldwasser semantically-secure public-key
encryption system.
.IP
The key components are prime numbers
.I p
and
.IR q ,
both congruent to 3 (mod\ 4), and their product
.IR n .
The public key is simply the modulus
.IR n ;
the factors
.I p
and
.I q
are the private key.
.IP
The key-generation algorithm ensures that the two primes
.I p
and
.I q
are
.I strong
(see the discussion of strong primes above, in the section on RSA keys),
and that
.RI ( p \ \-\ 1)/2
and
.RI ( q \ \-\ 1)/2
are relatively prime, giving a maximum possible period length.
.IP
The key size requested by the
.B \-b
option determines the length of the modulus
.IR n ;
the default length is 1024 bits.
.TP
.B "ec-param"
Store an elliptic curve specification.  If no explicit
.I curve-spec
is given (the
.RB ` \-C '
option) then a curve is chosen whose order is about the size given by the
.RB ` \-b '
option (default is 256 bits).
.IP
A
.I curve-spec
can be given explicitly (in which case
.RB ` \-b '
is ignored).  It can either be the name of a built-in curve (say
.B "key show ec"
for a list of curve names) or a full specification.  The curve is
checked for correctness and security according to the SEC1
specification: failed checks cause a warning to be issued to standard
error (though the program continues anyway).  The check can be
suppressed using the
.RB ` \-q '
option.
.IP
A curve specification consists of the following elements optionally
separated by whitespace: a
.IR "field type" ,
which is one of
.BR "prime" ,
.BR "niceprime" ,
.BR "binpoly" ,
.or
.BR "binnorm" ;
an optional
.RB ` : ';
the field modulus
.IR p ;
if the field type is
.B binnorm
then an optional
.RB ` , '
and the representation of the normal element \*(*b; an optional
.RB ` / ';
a
.IR "curve type" ,
which is one of
.BR "prime" ,
.BR "primeproj" ,
.BR "bin" ,
and
.BR "binproj"
(the `proj' types currently have much better performance);
an optional
.RB ` : ';
the two field-element parameters
.I a
and
.IR b 
which define the elliptic curve
.IR E ,
separated by an optional
.RB ` , ';
an optional
.RB ` / ';
the 
.IR x -
and
.IR y -coordinates
of the generator point
.IR G ,
separated by an optional
.RB ` , ';
an optional
.RB ` : ';
the order
.I r
of the group generated by 
.IR G ;
an optional
.RB ` * ';
and the 
.I cofactor
.I h
=
.RI # E / r .
.TP
.B "ec"
Generate a private scalar and a corresponding public point on an
elliptic curve.  See
.B ec-param
above for how to specify elliptic curve parameter sets.  The scalar
.I x
is chosen unformly between 0 and the curve order
.IR r ;
the public point is then
.I x
\(mu
.IR G .
.SS "expire"
Forces keys to immediately expire.  An expired key is not chosen when a
program requests a key by its type.  The keys to expire are listed by
their
.IR tag s.
.SS "delete"
Deletes keys immediately.  The keys to delete are listed by their
.IR tag s.
Be careful when deleting keys.  It might be a better idea
to expire keys rather than deleting them.
.SS "tag"
Sets, deletes or changes the tag attached to a key.  The first tag or
keyid names the key to be modified; the second, if present specifies the
new tag to be set.  If no second argument is given, the existing tag, if
any, is removed and no new tag is set.  It is an error to set a tag
which already exists on another key, unless you give the
.B \-r
option, which removes the tag first.
.SS "setattr"
Attaches attributes to a key.  The key to which the attributes should be
attached is given by its
.IR tag .
Each attribute has the form
.IB name = value\fR.
An attribute can be deleted by assigning it an empty value.  Although
the keyring file format is capable of representing an attribute with an
empty value as distinct from a nonexistant attribute, this interface
does not allow empty attributes to be set.
.SS "getattr"
Fetches a single attribute of a key.  The key whose attribute is to be
read is given by its
.IR tag .
The attribute's value is written to standard output followed by a
newline.  If the key or attribute is absent, a message is written to
standard error and the program exits nonzero.
.SS "comment"
Sets, deletes or changes the comment attached to a key.  The first
argument is a key tag or keyid which names the key to be modified; the
second, if present, is the new comment.  If no second argument is given,
the existing comment, if any, is removed, and no new comment is set.
.SS "lock"
Locks a key or key component using a passphrase.  If the key is already
locked, the existing passphrase is requested, and a new passphrase is
set.
.SS "unlock"
Unlocks a passphrase-locked key or key component.  If the key is not
locked, an error is reported.
.SS "list"
Lists the keys in the keyring.  A couple of options are supported:
.TP
.B "\-v, \-\-verbose"
Increases the amount of information displayed for each key.  Repeat for
a greater effect.
.TP
.B "\-q, \-\-quiet"
Decreases the amount of information displayed for each key.  Each use
cancels a
.RB ` \-v '
option.
.TP
.B "\-u, \-\-utc"
Display key expiry times as UTC rather than using the local time zone.
.TP
.BI "\-f, \-\-filter " filter
Specifies a filter.  Only keys and key components which match the filter
are listed.
.PP
By default, a single line of output is generated for each, showing
keyids, types, expiry and deletion dates, and comments.  Additional
.RB ` \-v '
options show more information, such as the exact time of day for expiry
and deletion, key attributes, and a dump of the actual key data.  If the
verbosity level is sufficiently high, passphrases are requested to
decrypt locked keys.  Make sure nobody is looking over your shoulder
when you do this!
.SS "fingerprint"
Reports a fingerprint (secure hash) on components of requested keys.
The following options are supported:
.TP
.BI "\-f, \-\-filter " filter
Specifies a filter.  Only keys and key components which match the filter
are fingerprinted.  The default is to only fingerprint nonsecret
components.
.TP
.BI "\-a, \-\-algorithm " hash
Names the hashing algorithm.  Run
.B key show hash
for a list of hashing algorithms.  The default is
.BR rmd160 .
.PP
The keys to be fingerprinted are named by their tags or keyids given as
command line arguments.  If no key tags are given, all keys which match
the filter are fingerprinted.  See
.BR keyring (5)
for a description of how key fingerprints are computed.
.SS "verify"
Check a key's fingerprint against a reference copy.  The following
options are supported:
.TP
.BI "\-f, \-\-filter " filter
Specifies a filter.  Only key components which match the filter are
hashed.  The default is to only fingerprint nonsecret components.  An
error is reported if no part of the key matches.
.TP
.BI "\-a, \-\-algorithm " hash
Names the hashing algorithm.  Run
.B key show hash
for a list of hashing algorithms.  The default is
.BR rmd160 .
.PP
The reference fingerprint is given as hex, in upper or lower case.  The
hash may contain hyphens, colons and whitespace.  Other characters are
not permitted.
.SS "tidy"
Simply reads the keyring from file and writes it back again.  This has
the effect of removing any deleted keys from the file.
.SS "extract"
Writes a selection of keys to a file.  An option is supported:
.TP
.BI "\-f, \-\-filter " filter
Specifies a filter.  Only keys and key components which match the filter
are written.
.PP
Keys extracted are written to the file named by the first argument,
which may be
.RB ` \- '
to designate standard output.  The keys to extract are listed by their
tags; if no tags are given, all keys which match the filter are
extracted.  The output is a valid keyring file.
.SS "merge"
Merges the keys from the named
.IR file ,
which may be
.RB ` \- '
to designate standard input, with the keyring.  Keys already in the
keyring are not overwritten: you must explicitly remove them first if
you want them to be replaced during the merge.
.SH "SEE ALSO"
.BR keyring (5).
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>