From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Sun, 6 Mar 94 10:48:27 PST
To: cypherpunks@toad.com
Subject: Re: Stealth PGP
Message-ID: <MhSWI=m00awH0EYEcH@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


There are actually several clever ways that you can get around the
problem with the RSA encrypted data being less than the modulus.  The
simplest is to encrypt it more than once.
Suppose you have a modulus m of legnth n.  You then create a block of
data to encrypt, b, of legnth n. If b is less than m, encrypt it with
RSA.  If not, don't encrypt it.  Then take 2^n-b-1 (which, btw, is the
same as xoring b with all one-bits).  If that result is less than m,
encrypt it with RSA.  Since m is greater than half of 2^n (it must be,
otherwise it would be less than legnth n), all possible plaintexts will
be encrypted at least once with RSA, some twice.  This does leave a
somewhat uneven distribution of values when comparing plaintext and
ciphertext (which can be minimized by more encryptions), but that only
shows up when and if the message is decrypted; as long as you use random
padding properly before encrypting, the encrypted data will look
completely random.

My ideal "Stealth-PGP" would work something like this: Take a file,
encrypt it with a random session key, prepend the session key to the
file, encrypt the first n bytes (which include the session key and part
of the encrypted data) with RSA if it's less than m, XOR it (reverse all
bits), and then encrypt with RSA if that's less than m.

Actually, putting the data inside the RSA might not be a good idea, it
would not work well for small files unless you added a legnth byte. 
Maybe the RSA part could just be filled with random padding...