Add user id parsing to PGPPacket

From RFC 4880 [1]:

  A User ID packet consists of UTF-8 text that is intended to
  represent the name and email address of the key holder.  By
  convention, it includes an RFC 2822 [RFC2822] mail name-addr, but
  there are no restrictions on its content.  The packet length in the
  header specifies the length of the User ID.

[1]: http://tools.ietf.org/search/rfc4880#section-5.11

Add version-4-signature parsing to PGPPacket

From RFC 4880 [1]:

  The body of a version 4 Signature packet contains:

  - One-octet version number (4).
  - One-octet signature type.
  - One-octet public-key algorithm.
  - One-octet hash algorithm.
  - Two-octet scalar octet count for following hashed subpacket data.
    Note that this is the length in octets of all of the hashed
    subpackets; a pointer incremented by this number will skip over
    the hashed subpackets.
  - Hashed subpacket data set (zero or more subpackets).
  - Two-octet scalar octet count for the following unhashed subpacket
    data.  Note that this is the length in octets of all of the
    unhashed subpackets; a pointer incremented by this number will
    skip over the unhashed subpackets.
  - Unhashed subpacket data set (zero or more subpackets).
  - Two-octet field holding the left 16 bits of the signed hash value.
  - One or more multiprecision integers comprising the signature.
    This portion is algorithm specific, as described above.

I've stashed all of the algorithm-specific MPI values in the
'signature' field, because I don't care about verifying signatures at
the moment.

[1]: http://tools.ietf.org/search/rfc4880#section-5.2.3

Add PGPPacket._signature_types

From RFC 4880 [1]:

  There are a number of possible meanings for a signature, which are
  indicated in a signature type octet in any given signature.  Please
  note that the vagueness of these meanings is not a flaw, but a
  feature of the system.  Because OpenPGP places final authority for
  validity upon the receiver of a signature, it may be that one
  signer's casual act might be more rigorous than some other
  authority's positive act.  See Section 5.2.4, "Computing
  Signatures", for detailed information on how to compute and verify
  signatures of each type.

  These meanings are as follows:

  0x00: Signature of a binary document.
    This means the signer owns it, created it, or certifies that it
    has not been modified.

  0x01: Signature of a canonical text document.
    This means the signer owns it, created it, or certifies that it
    has not been modified.  The signature is calculated over the text
    data with its line endings converted to <CR><LF>.

  0x02: Standalone signature.
    This signature is a signature of only its own subpacket contents.
    It is calculated identically to a signature over a zero-length
    binary document.  Note that it doesn't make sense to have a V3
    standalone signature.

  0x10: Generic certification of a User ID and Public-Key packet.
    The issuer of this certification does not make any particular
    assertion as to how well the certifier has checked that the owner
    of the key is in fact the person described by the User ID.

  0x11: Persona certification of a User ID and Public-Key packet.
    The issuer of this certification has not done any verification of
    the claim that the owner of this key is the User ID specified.

  0x12: Casual certification of a User ID and Public-Key packet.
    The issuer of this certification has done some casual verification
    of the claim of identity.

  0x13: Positive certification of a User ID and Public-Key packet.
    The issuer of this certification has done substantial verification
    of the claim of identity.

    Most OpenPGP implementations make their "key signatures" as 0x10
    certifications.  Some implementations can issue 0x11-0x13
    certifications, but few differentiate between the types.

  0x18: Subkey Binding Signature
    This signature is a statement by the top-level signing key that
    indicates that it owns the subkey.  This signature is calculated
    directly on the primary key and subkey, and not on any User ID or
    other packets.  A signature that binds a signing subkey MUST have
    an Embedded Signature subpacket in this binding signature that
    contains a 0x19 signature made by the signing subkey on the
    primary key and subkey.

  0x19: Primary Key Binding Signature
    This signature is a statement by a signing subkey, indicating that
    it is owned by the primary key [2].  This signature is calculated
    the same way as a 0x18 signature: directly on the primary key and
    subkey, and not on any User ID or other packets.

  0x1F: Signature directly on a key
    This signature is calculated directly on a key.  It binds the
    information in the Signature subpackets to the key, and is
    appropriate to be used for subpackets that provide information
    about the key, such as the Revocation Key subpacket.  It is also
    appropriate for statements that non-self certifiers want to make
    about the key itself, rather than the binding between a key and a
    name.

  0x20: Key revocation signature
    The signature is calculated directly on the key being revoked.  A
    revoked key is not to be used.  Only revocation signatures by the
    key being revoked, or by an authorized revocation key, should be
    considered valid revocation signatures.

  0x28: Subkey revocation signature
    The signature is calculated directly on the subkey being revoked.
    A revoked subkey is not to be used.  Only revocation signatures by
    the top-level signature key that is bound to this subkey, or by an
    authorized revocation key, should be considered valid revocation
    signatures.

  0x30: Certification revocation signature
    This signature revokes an earlier User ID certification signature
    (signature class 0x10 through 0x13) or direct-key signature
    (0x1F).  It should be issued by the same key that issued the
    revoked signature or an authorized revocation key.  The signature
    is computed over the same data as the certificate that it revokes,
    and should have a later creation date than that certificate.

  0x40: Timestamp signature.
    This signature is only meaningful for the timestamp contained in
    it.

  0x50: Third-Party Confirmation signature.
    This signature is a signature over some other OpenPGP Signature
    packet(s).  It is analogous to a notary seal on the signed data.
    A third-party signature SHOULD include Signature Target
    subpacket(s) to give easy identification.  Note that we really do
    mean SHOULD.  There are plausible uses for this (such as a blind
    party that only sees the signature, not the key or source
    document) that cannot include a target subpacket.

[1]: http://tools.ietf.org/search/rfc4880#section-5.2.1
[2]: http://www.rfc-editor.org/errata_search.php?rfc=4880
     Errata ID: 2208
     Reported By: Constantin Hagemeier
     Date Reported: 2010-04-28
     Held for Document Update by: Sean Turner
     Date Held: 2010-07-20

     Section 5.2.1. says:

       This signature is a statement by a signing subkey, indicating
       that it is owned by the primary key and subkey.

     It should say:

       This signature is a statement by a signing subkey, indicating
       that it is owned by the primary key.

     Notes:

       The subkey does not own itself.

Stub out PGPPacket._parse_signature_packet

The first octet of each signature packet is it's version number.  That
means we can parse the first octet of the signature packet and use its
value to determine which version we're parsing.  From RFC 4880 [1]:

  The body of a version 3 Signature Packet contains:

  - One-octet version number (3).
  - ...

And in the next section [2]:

  The body of a version 4 Signature Packet contains:

  - One-octet version number (4).
  - ...

[1]: http://tools.ietf.org/search/rfc4880#section-5.2.2
[2]: http://tools.ietf.org/search/rfc4880#section-5.2.3

Add CAST5 block size to PGPPacket._cipher_block_size

From RFC 4880 [1]:

  CAST5 (128 bit key, as per [RFC2144])

From RFC 2144 [2]:

  CAST-128 is a 12- or 16-round Feistel cipher that has a blocksize of
  64 bits and a keysize of up to 128 bits...

[1]: http://tools.ietf.org/search/rfc4880#section-9.2
[2]: http://tools.ietf.org/search/rfc2144#section-2.7

Add AES block sizes to PGPPacket._cipher_block_size

From the AES spec [1]:

  This standard specifies the Rijndael algorithm (...), a symmetric
  block cipher that can process data blocks of 128 bits, using cipher
  keys with lengths of 128, 192, and 256 bits.

[1]: http://csrc.nist.gov/publications/fips/fips197/fips-197.{ps,pdf}

Add secret key parsing to PGPPacket

Use the same parser for public-key and public-subkey packets.  From
RFC 4880 [1]:

  A Secret-Subkey packet (tag 7) is the subkey analog of the Secret
  Key packet and has exactly the same format.

The generic (sub)key parsing is specified in section 5.5.3 [2]:

  The Secret-Key and Secret-Subkey packets contain all the data of the
  Public-Key and Public-Subkey packets, with additional algorithm-
  specific secret-key data appended, usually in encrypted form.

  The packet contains:

  - A Public-Key or Public-Subkey packet, as described above.
  - One octet indicating string-to-key usage conventions.  Zero
    indicates that the secret-key data is not encrypted.  255 or 254
    indicates that a string-to-key specifier is being given.  Any
    other value is a symmetric-key encryption algorithm identifier.
  - [Optional] If string-to-key usage octet was 255 or 254, a one-
    octet symmetric encryption algorithm.
  - [Optional] If string-to-key usage octet was 255 or 254, a
    string-to-key specifier.  The length of the string-to-key
    specifier is implied by its type, as described above.
  - [Optional] If secret data is encrypted (string-to-key usage octet
    not zero), an Initial Vector (IV) of the same length as the
    cipher's block size.
  - Plain or encrypted multiprecision integers comprising the secret
    key data.  These algorithm-specific fields are as described below.
  - If the string-to-key usage octet is zero or 255, then a two-octet
    checksum of the plaintext of the algorithm-specific portion (sum
    of all octets, mod 65536).  If the string-to-key usage octet was
    254, then a 20-octet SHA-1 hash of the plaintext of the
    algorithm-specific portion.  This checksum or hash is encrypted
    together with the algorithm-specific fields (if string-to-key
    usage octet is not zero).  Note that for all other values, a
    two-octet checksum is required.

RFC 4880 claims to list block sizes (needed for the IV length) [3]:

  OpenPGP specifies a number of symmetric-key algorithms.  This
  specification creates a registry of symmetric-key algorithm
  identifiers.  The registry includes the algorithm name, its key
  sizes and block size, and a reference to the defining specification.
  The initial values for this registry can be found in Section 9.

But in section 9.2 [4], they just list key size.  It looks like the
block size is usually equal to the key size, but not always.  From
section one of the AES spec [5]:

  This standard specifies the Rijndael algorithm (...), a symmetric
  block cipher that can process data blocks of 128 bits, using cipher
  keys with lengths of 128, 192, and 256 bits.

So it looks like the block size for each cipher needs research beyond
RFC 4880.

[1]: http://tools.ietf.org/search/rfc4880#section-5.5.1.4
[2]: http://tools.ietf.org/search/rfc4880#section-5.5.3
[3]: http://tools.ietf.org/search/rfc4880#section-10.3.2
[4]: http://tools.ietf.org/search/rfc4880#section-9.2
[5]: http://csrc.nist.gov/publications/fips/fips197/fips-197.{ps,pdf}

Add iterated and salted S2K parsing to _parse_string_to_key_specifier

From RFC 4880 [1]:

   Octet  0:        0x03
   Octet  1:        hash algorithm
   Octets 2-9:      8-octet salt value
   Octet  10:       count, a one-octet, coded value

[1]: http://tools.ietf.org/search/rfc4880#section-3.7.1.3

Add salted S2K parsing to PGPPacket._parse_string_to_key_specifier

From RFC 4880 [1]:

   Octet  0:        0x01
   Octet  1:        hash algorithm
   Octets 2-9:      8-octet salt value

[1]: http://tools.ietf.org/search/rfc4880#section-3.7.1.2

Add simple S2K parsing to PGPPacket._parse_string_to_key_specifier

From RFC 4880 [1]:

   Octet 0:        0x00
   Octet 1:        hash algorithm

[1]: http://tools.ietf.org/search/rfc4880#section-3.7.1.1

Stub out PGPPacket._parse_string_to_key_specifier

From RFC 4880 [1]:

       ID          S2K Type
       --          --------
       0           Simple S2K
       1           Salted S2K
       2           Reserved value
       3           Iterated and Salted S2K
       100 to 110  Private/Experimental S2K

In the following sections (3.7.1.1 - 3.7.1.3), the first octet of each
specifier is it's type (simple starts with 0x00, salted starts with
0x01, and iterated and salted starts with 0x03).  That means we can
parse the first octet of the S2K specifier and use its value to
determine which type of specifier we're parsing.

[1]: http://tools.ietf.org/search/rfc4880#section-3.7.1

Parse algorithm-specific data in _parse_generic_public_key_packet

From RFC 4880 [1]:

  This algorithm-specific portion is:

  Algorithm-Specific Fields for RSA public keys:

    - multiprecision integer (MPI) of RSA public modulus n;
    - MPI of RSA public encryption exponent e.

  Algorithm-Specific Fields for DSA public keys:

    - MPI of DSA prime p;
    - MPI of DSA group order q (q is a prime divisor of p-1);
    - MPI of DSA group generator g;
    - MPI of DSA public-key value y (= g**x mod p where x is secret).

  Algorithm-Specific Fields for Elgamal public keys:

    - MPI of Elgamal prime p;
    - MPI of Elgamal group generator g;
    - MPI of Elgamal public key value y (= g**x mod p where x is
      secret).

We need to parse these fields explicitly, because the secret key
packets start with public key packets.  In order to tell where the
rest of the secret key data starts, we need to know the length of the
public key packet; simply treating the rest of the packet as an opaque
public key doesn't work.

[1]: http://tools.ietf.org/search/rfc4880#section-5.5.2

Add PGPPacket._parse_multiprecision_integer

From RFC 4880 [1]:

  An MPI consists of two pieces: a two-octet scalar that is the length
  of the MPI in bits followed by a string of octets that contain the
  actual integer.

  These octets form a big-endian number; a big-endian number can be
  made into an MPI by prefixing it with the appropriate length.

  Examples:

  (all numbers are in hexadecimal)

  The string of octets [00 01 01] forms an MPI with the value 1.  The
  string [00 09 01 FF] forms an MPI with the value of 511.

  Additional rules:

  The size of an MPI is ((MPI.length + 7) / 8) + 2 octets.

  The length field of an MPI describes the length starting from its
  most significant non-zero bit.  Thus, the MPI [00 02 01] is not
  formed correctly.  It should be [00 01 01].

  Unused bits of an MPI MUST be zero.

  Also note that when an MPI is encrypted, the length refers to the
  plaintext MPI.  It may be ill-formed in its ciphertext.

[1]: http://tools.ietf.org/search/rfc4880#section-3.2

Decode public key algorithm in _parse_generic_public_key_packet

It's easier for humans to parse the text representation ;).

Add PGPPacket._hash_algorithms

From RFC 4880 [1]:

      ID           Algorithm                             Text Name
      --           ---------                             ---------
      1          - MD5 [HAC]                             "MD5"
      2          - SHA-1 [FIPS180]                       "SHA1"
      3          - RIPE-MD/160 [HAC]                     "RIPEMD160"
      4          - Reserved
      5          - Reserved
      6          - Reserved
      7          - Reserved
      8          - SHA256 [FIPS180]                      "SHA256"
      9          - SHA384 [FIPS180]                      "SHA384"
      10         - SHA512 [FIPS180]                      "SHA512"
      11         - SHA224 [FIPS180]                      "SHA224"
      100 to 110 - Private/Experimental algorithm

[1]: http://tools.ietf.org/search/rfc4880#section-9.4

Add PGPPacket._compression_algorithms

From RFC 4880 [1]:

       ID           Algorithm
       --           ---------
       0          - Uncompressed
       1          - ZIP [RFC1951]
       2          - ZLIB [RFC1950]
       3          - BZip2 [BZ2]
       100 to 110 - Private/Experimental algorithm

[1]: http://tools.ietf.org/search/rfc4880#section-9.3

Add PGPPacket._symmetric_key_algorithms

From RFC 4880 [1]:

       ID           Algorithm
       --           ---------
       0          - Plaintext or unencrypted data
       1          - IDEA [IDEA]
       2          - TripleDES (DES-EDE, [SCHNEIER] [HAC] -
                    168 bit key derived from 192)
       3          - CAST5 (128 bit key, as per [RFC2144])
       4          - Blowfish (128 bit key, 16 rounds) [BLOWFISH]
       5          - Reserved
       6          - Reserved
       7          - AES with 128-bit key [AES]
       8          - AES with 192-bit key
       9          - AES with 256-bit key
       10         - Twofish with 256-bit key [TWOFISH]
       100 to 110 - Private/Experimental algorithm

[1]: http://tools.ietf.org/search/rfc4880#section-9.2

Add PGPPacket._public_key_algorithms

From RFC 4880 [1]:

      ID           Algorithm
      --           ---------
      1          - RSA (Encrypt or Sign) [HAC]
      2          - RSA Encrypt-Only [HAC]
      3          - RSA Sign-Only [HAC]
      16         - Elgamal (Encrypt-Only) [ELGAMAL] [HAC]
      17         - DSA (Digital Signature Algorithm) [FIPS186] [HAC]
      18         - Reserved for Elliptic Curve
      19         - Reserved for ECDSA
      20         - Reserved (formerly Elgamal Encrypt or Sign)
      21         - Reserved for Diffie-Hellman (X9.42,
                   as defined for IETF-S/MIME)
      100 to 110 - Private/Experimental algorithm

[1]: http://tools.ietf.org/search/rfc4880#section-9.1

Add public key parsing to PGPPacket

Use the same parser for public-key and public-subkey packets.  From
RFC 4880 [1]:

  A Public-Subkey packet (tag 14) has exactly the same format as a
  Public-Key packet, but denotes a subkey.  One or more subkeys may be
  associated with a top-level key.

The generic (sub)key parsing is specified in section 5.5.2 [2]:

  OpenPGP implementations MUST create keys with version 4 format.  V3
  keys are deprecated; an implementation MUST NOT generate a V3 key,
  but MAY accept it.

  ...

  A version 4 packet contains:

  - A one-octet version number (4).
  - A four-octet number denoting the time that the key was created.
  - A one-octet number denoting the public-key algorithm of this key.
  - A series of multiprecision integers comprising the key material.

Also check that the --export packets begin with a public-key packet.
From RFC 4880 [3]:

  A Public-Key packet starts a series of packets that forms an OpenPGP
  key (sometimes called an OpenPGP certificate).

[1]: http://tools.ietf.org/search/rfc4880#section-5.5.1.2
[2]: http://tools.ietf.org/search/rfc4880#section-5.5.2
[3]: http://tools.ietf.org/search/rfc4880#section-5.5.1.1

Add a flexible packet-parsing framework

Shunting packet-type processing out to type-specific methods.  For
example, 'public-key packet' packets will be parsed by
PGPPacket._parse_public_key_packet.

From the re docs [1]:

  '+'
    Causes the resulting RE to match 1 or more repetitions of the
    preceding RE. ab+ will match 'a' followed by any non-zero number
    of 'b's; it will not match just 'a'.

  ...

  \W
    For Unicode (str) patterns:
      Matches Unicode word characters; this includes most characters
      that can be part of a word in any language, as well as numbers
      and the underscore. If the ASCII flag is used, only [a-zA-Z0-9_]
      is matched (but the flag affects the entire regular expression,
      so in such cases using an explicit [a-zA-Z0-9_] may be a better
      choice).

    For 8-bit (bytes) patterns:
      Matches characters considered alphanumeric in the ASCII
      character set; this is equivalent to [a-zA-Z0-9_].

[1]: http://docs.python.org/3/library/re.html#regular-expression-syntax

gpg-migrate.py: Convert PGPPacket 'packet-tag' key to 'type'

And convert the integer to a string using the table from RFC 4880 [1]:

  The packet tag denotes what type of packet the body holds.  Note
  that old format headers can only have tags less than 16, whereas new
  format headers can have tags as great as 63.  The defined tags (in
  decimal) are as follows:

       0        -- Reserved - a packet tag MUST NOT have this value
       1        -- Public-Key Encrypted Session Key Packet
       2        -- Signature Packet
       3        -- Symmetric-Key Encrypted Session Key Packet
       4        -- One-Pass Signature Packet
       5        -- Secret-Key Packet
       6        -- Public-Key Packet
       7        -- Secret-Subkey Packet
       8        -- Compressed Data Packet
       9        -- Symmetrically Encrypted Data Packet
       10       -- Marker Packet
       11       -- Literal Data Packet
       12       -- Trust Packet
       13       -- User ID Packet
       14       -- Public-Subkey Packet
       17       -- User Attribute Packet
       18       -- Sym. Encrypted and Integrity Protected Data Packet
       19       -- Modification Detection Code Packet
       60 to 63 -- Private or Experimental Values

[1]: http://tools.ietf.org/search/rfc4880#section-4.3

Pull PGPPacket header parsing out into _parse_header

This parsing is distinct from the payload parsing, so stash it in a
separate method.

Add packets_from_bytes to help parse multi-packet streams

Check for short packets in PGPPacket.from_bytes

When the data is longer than expected, the packet may just be part of
a stream.

Track data offset in bytes, and extract the packet payload

Return the offset when we're done, because there may be multiple
packets in a stream.

Extract the packet length from the old-format length header

From RFC 4880 [1]:

  Scalar numbers are unsigned and are always stored in big-endian
  format.  Using n[k] to refer to the kth octet being interpreted, the
  value of a two-octet scalar is ((n[0] << 8) + n[1]).  The value of a
  four-octet scalar is ((n[0] << 24) + (n[1] << 16) + (n[2] << 8) +
  n[3]).

The struct big-endian byte-order character is '>' [2].

[1]: http://tools.ietf.org/search/rfc4880#section-3.1
[2]: http://docs.python.org/3/library/struct.html#byte-order-size-and-alignment

Add PGPPacket._old_format_packet_lengths

From RFC 4880 [1]:

   The meaning of the length-type in old format packets is:

   0 - The packet has a one-octet length.  The header is 2 octets long.

   1 - The packet has a two-octet length.  The header is 3 octets long.

   2 - The packet has a four-octet length.  The header is 5 octets long.

   3 - The packet is of indeterminate length.  The header is 1 octet
       long, and the implementation must determine how long the packet
       is.  If the packet is in a file, this means that the packet
       extends until the end of the file.  In general, an implementation
       SHOULD NOT use indeterminate-length packets except where the end
       of the data will be clear from the context, and even then it is
       better to use a definite length, or a new format header.  The new
       format headers described below have a mechanism for precisely
       encoding data of indeterminate length.

The struct format characters are [2]:

  Format   C Type           Python type   Standard size   Notes
  B        unsigned char    integer       1               (3)
  H        unsigned short   integer       2               (3)
  I        unsigned int     integer       4               (3)

  3. When attempting to pack a non-integer using any of the integer
     conversion codes, if the non-integer has a __index__() method
     then that method is called to convert the argument to an integer
     before packing.

     Changed in version 3.2: Use of the __index__() method for
     non-integers is new in 3.2.

[1]: http://tools.ietf.org/search/rfc4880#section-4.2.1
[2]: http://docs.python.org/3/library/struct.html#format-characters

Extract the packet tag

From RFC 4880 [1]:

  The first octet of the packet header is called the "Packet Tag".  It
  determines the format of the header and denotes the packet contents.
  The remainder of the packet header is the length of the packet.

  Note that the most significant bit is the leftmost bit, called bit
  7.  A mask for this bit is 0x80 in hexadecimal.

              +---------------+
         PTag |7 6 5 4 3 2 1 0|
              +---------------+
         Bit 7 -- Always one
         Bit 6 -- New packet format if set

  PGP 2.6.x only uses old format packets.  Thus, software that
  interoperates with those versions of PGP must only use old format
  packets.  If interoperability is not an issue, the new packet format
  is RECOMMENDED.  Note that old format packets have four bits of
  packet tags, and new format packets have six; some features cannot
  be used and still be backward-compatible.

  Also note that packets with a tag greater than or equal to 16 MUST
  use new format packets.  The old format packets can only express
  tags less than or equal to 15.

  Old format packets contain:

         Bits 5-2 -- packet tag
         Bits 1-0 -- length-type

  New format packets contain:

         Bits 5-0 -- packet tag

[1]: http://tools.ietf.org/search/rfc4880#section-4.2

Stub out gpg-migrate.py

Following the general approach outlined by Atom Smasher [1], but I'll
just parse the packets directly in Python.

[1]: http://atom.smasher.org/gpg/gpg-migrate.txt