nettle.info: Public-key algorithms

Reference

Randomness

Key derivation functions

Back to Software Index

7.7 Public-key algorithms
=========================

Nettle uses GMP, the GNU bignum library, for all calculations with large
numbers.  In order to use the public-key features of Nettle, you must
install GMP, at least version 3.0, before compiling Nettle, and you need
to link your programs with ‘-lhogweed -lnettle -lgmp’.

   The concept of “Public-key” encryption and digital signatures was
discovered by Whitfield Diffie and Martin E. Hellman and described in a
paper 1976.  In traditional, “symmetric”, cryptography, sender and
receiver share the same keys, and these keys must be distributed in a
secure way.  And if there are many users or entities that need to
communicate, each _pair_ needs a shared secret key known by nobody else.

   Public-key cryptography uses trapdoor one-way functions.  A “one-way
function” is a function ‘F’ such that it is easy to compute the value
‘F(x)’ for any ‘x’, but given a value ‘y’, it is hard to compute a
corresponding ‘x’ such that ‘y = F(x)’.  Two examples are cryptographic
hash functions, and exponentiation in certain groups.

   A “trapdoor one-way function” is a function ‘F’ that is one-way,
unless one knows some secret information about ‘F’.  If one knows the
secret, it is easy to compute both ‘F’ and it’s inverse.  If this sounds
strange, look at the RSA example below.

   Two important uses for one-way functions with trapdoors are
public-key encryption, and digital signatures.  The public-key
encryption functions in Nettle are not yet documented; the rest of this
chapter is about digital signatures.

   To use a digital signature algorithm, one must first create a
“key-pair”: A public key and a corresponding private key.  The private
key is used to sign messages, while the public key is used for verifying
that that signatures and messages match.  Some care must be taken when
distributing the public key; it need not be kept secret, but if a bad
guy is able to replace it (in transit, or in some user’s list of known
public keys), bad things may happen.

   There are two operations one can do with the keys.  The signature
operation takes a message and a private key, and creates a signature for
the message.  A signature is some string of bits, usually at most a few
thousand bits or a few hundred octets.  Unlike paper-and-ink signatures,
the digital signature depends on the message, so one can’t cut it out of
context and glue it to a different message.

   The verification operation takes a public key, a message, and a
string that is claimed to be a signature on the message, and returns
true or false.  If it returns true, that means that the three input
values matched, and the verifier can be sure that someone went through
with the signature operation on that very message, and that the
“someone” also knows the private key corresponding to the public key.

   The desired properties of a digital signature algorithm are as
follows: Given the public key and pairs of messages and valid signatures
on them, it should be hard to compute the private key, and it should
also be hard to create a new message and signature that is accepted by
the verification operation.

   Besides signing meaningful messages, digital signatures can be used
for authorization.  A server can be configured with a public key, such
that any client that connects to the service is given a random nonce
message.  If the server gets a reply with a correct signature matching
the nonce message and the configured public key, the client is granted
access.  So the configuration of the server can be understood as “grant
access to whoever knows the private key corresponding to this particular
public key, and to no others”.

RSA

The RSA public key algorithm.

DSA

The DSA digital signature algorithm.

Elliptic curves

Elliptic curves and ECDSA