Adam Back <[EMAIL PROTECTED]>:
> On how to stego pgp messages. First you have to ensure that the data
> you are stegoing has a rectangular distribution [...]
[...]
> It might be nice to update stealth-2 for openPGP / pgp5. There you
> have the additional task of coping with Elgamal key exchange. With
> Elgamal you have g^k mod p, and m.y^k mod p which could be normalised
> using Hal's algorithm relative to p. [...]
This normalization works for the m*y^k mod p part (assuming that the
padding that leads to m is good so that that product is reasonably
random), but not for g^k mod p. The problem is that usually g will
not be a generator of the group (Z/pZ)*, but merely of a proper
subgroup thereof; and this shows in the ElGamal output.
To use steganography with ElGamal anyway, an additional step is
required. If you know the order of g mod p, then you can multiply
in a random element of the "orthogonal" subgroup of (Z/pZ)*, which
the receiver can cancel out by one exponentiation, provided that the
order q of g is co-prime to (p-1)/q, i.e. that no factor of q
occurs in p-1 more often than in q:
Let g' be some generator of (Z/pZ)*. Then g'^((p-1)/q) generates
the same order-q subgroup as g, and g'^q generates a subgroup of
order r := (p-1)/q) such that the natural product of those subgroups
is (Z/pZ)*. To prepare g^k mod p for stegoing, pick a random
number R in 1 .. r and compute F := (g'^q)^R mod p. Then
multiply g^k mod p by F to get a number that is uniformly
distributed in 1 .. p-1, and use this product as input to the
normalization process; use the normalizations of F*g^k mod p
and m*y^k mod p as input for your stego-embedding.
The receiver, after having undone the normalization step, has to
compute g^k mod p from F*g^k mod p. Observe that
(*) F^r == g'^(q*r) == 1 (mod p)
since q*r = p-1, while the generator g'^r of the order-q
subgroup stays a generator of that subgroup when taken to the r.
Find q' such that r*q' == 1 mod q (this is possible because
we assumed r to be co-prime to q); then
(**) (g'^r)^(r*q') == g'^r (mod p),
and thus *every* element of the subgroup generated by g'^r is
preserved by the map a |-> a^(r*q'). Now of course congruence (*)
also means that
F^(r*q') == 1 (mod p),
and because elements of the order-q subgroup (of which g is another
generator) are preserved it follows that
(F*g^k)^(r*q') == g^k (mod p),
which means that, as intended, we've got rid of factor F.
The next step in ElGamal decryption is exponentiation
with secret exponent x, so we can just as well compute
(F*g^k)^(r*q'*x) (mod p)
in a single step unless we have to re-generate the ElGamal message for
separate software -- note that r*q'*x (which naturally is mod p-1
in this exponent) is a key-dependent constant, so this is just like
standard ElGamal decryption except that the exponent is different
(longer).
Unfortunately, the OpenPGP format for ElGamal keys does not include q,
not even as an option. What one could do to hack around this
limitation is use the same DH-parameters for ElGamal encryption as for
the associated DSA key (which does include q).
