Batch RSA for stego data

[Anonymous <nobody@REPLAY.COM>]

Problem: Suppose there is a source of data which looks like random noise
but which contains embedded messages.  This may be a subliminal channel
in a crypto protocol, steganographically embedded data, or even a simple
message pool where you want to disguise what key each message is for.
How do you scan and identify messages for you?

Solution: Extract bits as appropraite, apply whatever selection rules
are necessary to pull them out of the stego'd data or other source.
Some fraction of what results is messages for you, the remainder is
noise or messages for someone else, which will be indistinguishable.

Method 1: For finding messages sent by someone you have communicated
with previously.  Use shared secret data to flag the message.

Method 1A: each time you send a message, include (in the encrypted
portion) a 64-bit random value which will be used to flag the next
message to them.  Prepend the encrypted message with the 64 bit random
value from the previous message.  Each person keeps a list of the next
random value to be expected from each communicant.  The extracted data
can be easily scanned to see if it matches anything on the list.

Method 1B: use shared secret data and a sequence number to calculate a
hash which will be used to flag the next message sent.  This can be
used to calculate the flag value to be expected for the next message
from each sender, which can be compared against each potential
message.

For both methods 1A and 1B, once the message is recognized a shared
secret key is used to decrypt the remainder of the data past the flag
portion.  The shared secret key can be changed after each message
using similar techniques to changing the flags.  (Safety tip: don't
make the shared secret key the same as the flag value.)


Method 2: For finding messages sent by someone you have never communicated
with previously.

Method 2A: Sender encrypts a low-entropy flag message with receiver's
public key, pads it so it looks like random noise, and puts that at
the start of each message.  Receiver decrypts the beginning of each
message using his private key, looking to see if the results are low
entropy.  When such a message is detected the secret key for
decrypting the remainder of the message can be embedded in the
low-entropy portion.

Method 2B: Like 2A, but use Fiat's "Batch RSA" to decrypt multiple
messages in one batch.  Recipient publishes his public key with
multiple legal exponents (say, the first 16 primes).  Sender encrypts
his low-entropy message choosing one of the encryption exponents at
random.  He checks to see if the low bits of the encryption output
match the index of the encryption exponent (e.g. if the 7th encryption
exponent was chosen then the low order 4 bits should hold the value
7).  He repeatedly encrypts with different random padding until he
finds an encrypted form which properly encodes the exponent.  Receiver
batches messages together such that the low order 4 bits of each
message in the batch are different, and applies the Batch RSA
decryption to try decrypting each message.  As before the receiver
looks to see if the result is low entropy.

For both 2A and 2B it may be possible to do the decryption using only
one of the two RSA primes, if the encrypted data was smaller than that
prime value.  (This idea comes from Shamir.)  Even if not, the Batch
RSA algorithm can be applied separately for the two primes and then
the results combined at the end for each message via the CRT, as is
often done for RSA decryption.