nettle: Public-key algorithms
1
1 6.7 Public-key algorithms
1 =========================
1
1 Nettle uses GMP, the GNU bignum library, for all calculations with large
1 numbers. In order to use the public-key features of Nettle, you must
1 install GMP, at least version 3.0, before compiling Nettle, and you need
1 to link your programs with ‘-lhogweed -lnettle -lgmp’.
1
1 The concept of “Public-key” encryption and digital signatures was
1 discovered by Whitfield Diffie and Martin E. Hellman and described in a
1 paper 1976. In traditional, “symmetric”, cryptography, sender and
1 receiver share the same keys, and these keys must be distributed in a
1 secure way. And if there are many users or entities that need to
1 communicate, each _pair_ needs a shared secret key known by nobody else.
1
1 Public-key cryptography uses trapdoor one-way functions. A “one-way
1 function” is a function ‘F’ such that it is easy to compute the value
1 ‘F(x)’ for any ‘x’, but given a value ‘y’, it is hard to compute a
1 corresponding ‘x’ such that ‘y = F(x)’. Two examples are cryptographic
1 hash functions, and exponentiation in certain groups.
1
1 A “trapdoor one-way function” is a function ‘F’ that is one-way,
1 unless one knows some secret information about ‘F’. If one knows the
1 secret, it is easy to compute both ‘F’ and it’s inverse. If this sounds
1 strange, look at the RSA example below.
1
1 Two important uses for one-way functions with trapdoors are
1 public-key encryption, and digital signatures. The public-key
1 encryption functions in Nettle are not yet documented; the rest of this
1 chapter is about digital signatures.
1
1 To use a digital signature algorithm, one must first create a
1 “key-pair”: A public key and a corresponding private key. The private
1 key is used to sign messages, while the public key is used for verifying
1 that that signatures and messages match. Some care must be taken when
1 distributing the public key; it need not be kept secret, but if a bad
1 guy is able to replace it (in transit, or in some user’s list of known
1 public keys), bad things may happen.
1
1 There are two operations one can do with the keys. The signature
1 operation takes a message and a private key, and creates a signature for
1 the message. A signature is some string of bits, usually at most a few
1 thousand bits or a few hundred octets. Unlike paper-and-ink signatures,
1 the digital signature depends on the message, so one can’t cut it out of
1 context and glue it to a different message.
1
1 The verification operation takes a public key, a message, and a
1 string that is claimed to be a signature on the message, and returns
1 true or false. If it returns true, that means that the three input
1 values matched, and the verifier can be sure that someone went through
1 with the signature operation on that very message, and that the
1 “someone” also knows the private key corresponding to the public key.
1
1 The desired properties of a digital signature algorithm are as
1 follows: Given the public key and pairs of messages and valid signatures
1 on them, it should be hard to compute the private key, and it should
1 also be hard to create a new message and signature that is accepted by
1 the verification operation.
1
1 Besides signing meaningful messages, digital signatures can be used
1 for authorization. A server can be configured with a public key, such
1 that any client that connects to the service is given a random nonce
1 message. If the server gets a reply with a correct signature matching
1 the nonce message and the configured public key, the client is granted
1 access. So the configuration of the server can be understood as “grant
1 access to whoever knows the private key corresponding to this particular
1 public key, and to no others”.
1
Menu