GPG Private Key Export Question

[Bob (Robert) Cavanaugh]

Peter,
I usually lurk on this group, but I have to give kudos for this. This is the best introductory explanation I have seen in a long time. Well done.

Thanks,
 
Bob Cavanaugh
Broadcom Corporation
16340 West Bernardo Drive
San Diego CA 92127
Work:    858-521-5562
Fax:     858-385-8810
Cell:    858-361-2068
 
-----Original Message-----
From: Gnupg-users [mailto:gnupg-users-bounces at gnupg.org] On Behalf Of Peter Lebbing
Sent: Saturday, September 28, 2013 2:27 AM
To: Paul Taukatch
Cc: gnupg-users at gnupg.org
Subject: Re: GPG Private Key Export Question

On 27/09/13 21:28, Paul Taukatch wrote:
> Was just hoping you could help clarify one more thing. Why exactly are the 
> numerical values for skey[0] and skey[1] equal to pkey[0] and pkey[1]?

RFC 4880 really is the place to look for this stuff. All your questions can be
answered by carefully reading the relevant sections of that RFC. Key packets are
described in section 5.5. You showed a --list-packets for an RSA key, so section
5.5.2 tells us a public key packet, or equivalently the start of a secret key
packet, contains, in order: a version number, a creation time, the algorithm,
and a series of multiprecision integers describing the key material. For RSA,
these are the modulus n and the exponent e. It is easily seen that these
probably correspond to skey[0] and skey[1] respectively (or pkey), because the
first one is 2048 bits, which is a reasonable size for the modulus, and the
second one is 17 bits, and I believe that GnuPG always uses the public exponent
65537.

Section 5.5.3 goes on to explain what follows in a secret key packet. If you
would remove the password from the exported key, you could see that contents as
well; right now it's in the encrypted part. Let's take a look at a 2048-bit RSA
key secret packet without encryption:

:secret key packet:
        version 4, algo 1, created 1374835387, expires 0
        skey[0]: [2048 bits]
        skey[1]: [17 bits]
        skey[2]: [2043 bits]
        skey[3]: [1024 bits]
        skey[4]: [1024 bits]
        skey[5]: [1023 bits]
        checksum: 4527
        keyid: A1DAD4EC3E7F0306

Section 5.5.3 starts off talking about the encryption with an S2K
(string-to-key, the method to create cryptokeys from a passphrase). Then follows
algorithm-specific stuff, then a checksum. Since we didn't do encryption, the
output above just indicates the algo-specific stuff and the checksum.
Algo-specific stuff for RSA is described as: multiprecision integer (MPI) of the
secret exponent d, prime p, prime q and u, the multiplicative inverse of p, mod
q. The secret exponent's size is on the order of the modulus, so that would be
skey[2]. The others are indeed on the order of half the size of the modulus, so
those sizes make sense as well. It would seem justified to think that, like it
did so far, GnuPG is reporting them in the order they appear in the packet,
making p skey[3], q skey[4] and u skey[5].

If you look at the Wikipedia article on RSA, they define q_inv = q^(-1) mod p. p
and q are exchangeable in the definition, so q_inv is equivalent to u. u is
expensive to compute, so it is included in the secret key material. The two
derived private exponents modulo p or q are cheap to compute. At least, that's
how I always interpreted the presence of u and absence of the other two.

> Is it because the numerical value listed is actually the key value of the 
> entire public/private key pair?

I don't know what you mean by "key value". It might be because...

> If so, is a specific portion of that key value used as the "secret key" and
> another portion used as the "public key"?

I get the sense you don't know how the basics of RSA work. If you're going to
look at RSA key material, you should know what makes an RSA key and how it
basically functions. There's no need to know the mathematical proof of the
correctness of its functioning, but you do need to understand a bit of the math.
I think the Wikipedia article on RSA is pretty readable, but I think they don't
state clearly enough for the uninitiated that by choosing d and e as they are
defined, you get (thanks to Euler's theorem) the property that:

m^e^d (mod n) = m^(e*d) (mod n) = m (mod n)
(equivalently:)
m^d^e (mod n) = m (mod n)

Since you can do the (mod n) at any time you darn well like:
c = m^e (mod n)     -- creates ciphertext
m = c^d (mod n) = m^e^d (mod n) = m (mod n) -- message recoverable

s = h^d (mod n)   -- signature is based on hash
h = s^e (mod n) = s^e^d (mod n) = h (mod n) -- compare hashes

By comparing hashes, you've proven that the person making the signature knows d,
because only d would reverse the effects of raising it to the power of e.

Interestingly, the Euler's theorem Wikipedia article does mention the property:

"
Euler's theorem also forms the basis of the RSA encryption system: encryption
and decryption in this system together amount to exponentiating the original
text by k*phi(n) + 1 for some positive integer k, so Euler's theorem shows that
the decrypted result is the same as the original.
"

This can be seen from point 5 of "Key generation" of the RSA article:

Solve d for d*e = 1 (mod phi(n)) = k*phi(n) + 1

> Also, is there any command I can use to view the entire contents of the 
> exported secret key packet?

As indicated above: remove the passphrase from the key.

HTH,

Peter.

PS: I took the liberty to write = where it should be a congruence relation
modulo n. Keeps it ASCII.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at <http://digitalbrains.com/2012/openpgp-key-peter>

_______________________________________________
Gnupg-users mailing list
Gnupg-users at gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-users