ElGamal

Simmons’s second subliminal channel [1459], described in [1407,1473], is based on the ElGamal signature scheme (see Section 19.6).

Key generation is the same as the basic ElGamal signature scheme. First choose a prime, p, and two random numbers, g and r, such that both g and r are less than p. Then calculate

K = g^r mod p

The public key is K, g, and p. The private key is r. Besides Alice, Bob also knows r; it is the key that is used to send and read the subliminal message in addition to being the key used to sign the innocuous message.

To send a subliminal message M using the innocuous message M', M and p must be all relatively prime to each other, and M and p -1 must be relatively prime. Alice calculates

X = g^M mod p

and solves the following equation for Y (using the extended Euclidean algorithm):

M' = rX + MY mod (p - 1)

As in the basic ElGamal scheme, the signature is the pair: X and Y.

Walter can verify the ElGamal signature. He confirms that

K^XX^Y ≡ g^M' (mod p)

Bob can recover the subliminal message. First he confirms that

(g^r)^X X^Y ≡ g^M' (mod p)

If it does, he accepts the message as genuine (not from Walter).

Then, to recover M, he computes

M = (Y^–1 (M' - rX)) mod (p - 1)

For example, let p =11 and g =2. The private key, r, is chosen to be 8. This means the public key, which Walter can use to verify the signature, is g^r mod p =2⁸ mod 11 =3.

To send the subliminal message M =9, using innocuous message M'= 5, Alice confirms that 9 and 11 are relatively prime and that 5 and 11 are relatively prime. She also confirms that 9 and 11 -1 =10 are relatively prime. They are, so she calculates

X = g^M mod p = 2⁹ mod 11 = 6

Then, she solves the following equation for Y:

5 = 8 * 6 + 9 * Y mod 10

Y = 3, so the signature is the pair, X and Y: 6 and 3.

Bob confirms that

(g^r)^X X^Y ≡ g^M' (mod p)

(2⁸)⁶6³ ≡ 2⁵ (mod 11)

It does (do the math yourself if you don’t trust me), so he then recovers the subliminal message by calculating

M = (Y^–1 (M' - rX)) mod (p - 1) = 3^-1(5 - 8 * 6) mod 10 = 7(7) mod 10 = 49 mod 10 = 9

ESIGN

A subliminal channel can be added to ESIGN [1460] (see Section 20.6).

In ESIGN, the secret key is a pair of large prime numbers, p and q, and the public key is n =p²q . With a subliminal channel, the private key is three primes, p, q, and r, and the public key is n, such that

n = p²qr

The variable, r, is the extra piece of information that Bob needs to read the subliminal message.

To sign a normal message, Alice first picks a random number, x, such that x is less than pqr and computes:

w, the least integer that is larger than (H(m) - x^k mod n)/pqr)

s = x + ((w/kx^k-1) mod p)pqr

H(m) is the hash of the message; k is a security parameter. The value s is the signature.

To verify the signature, Bob computes s^k mod n. He also computes a, which is the least integer larger than the number of bits of n divided by 3. If H(m) is less than or equal to s^k mod n, and if s^k mod n is less than H(m) +2^a , then the signature is considered valid.

To send a subliminal message, M, using the innocuous message, M', Alice calculates s using M in place of H(m). This means that the message must be smaller than p²qr. She then chooses a random value, u, and calculates

x' = M' + ur

Then, use this x' value as the “random number” x to sign M'. This second s value is sent as a signature.

Walter can verify that s (the second s) is a valid signature of M'.

Bob can also authenticate the message in the same way. But, since he also knows r, he can calculate

s = x' + ypqr = M + ur + ypqr ≡ M (mod r)

This implementation of a subliminal channel is far better than the previous two. In the Ong-Schnorr-Shamir and ElGamal implementations, Bob has Alice’s private key. Besides being able to read subliminal messages from Alice, Bob can impersonate Alice and sign normal documents. Alice can do nothing about this; she must trust Bob to set up this subliminal channel.

The ESIGN scheme doesn’t suffer from this problem. Alice’s private key is the set of three primes: p, q, and r. Bob’s secret key is just r. He knows n =p²qr, but to recover p and q he has to factor that number. If the primes are large enough, Bob has just as much trouble impersonating Alice as would Walter or anyone else.

DSA

There is also a subliminal channel in DSA (see Section 20.1) [1468,1469,1473]. In fact, there are several. The simplest subliminal channel involves the choice of k. It is supposed to be a 160-bit random number. However, if Alice chooses a particular k, then Bob, who also knows Alice’s private key, can recover it. Alice can send Bob a 160-bit subliminal message in each DSA signature; everyone else simply verifies Alice’s signature. Another complication: Since k should be random, Alice and Bob need to share a one-time pad and encrypt the subliminal message with the one-time pad to generate a k.

DSA has subliminal channels that do not require Bob to know Alice’s private key. These also involve choosing particular values of k, but cannot be used to send 160 bits of information. This scheme, presented in [1468,1469], allows Alice and Bob to exchange one bit of subliminal information per signed message.

(1)  Alice and Bob agree on a random prime, P (different from the parameter p in the signature scheme). This is their secret key for the subliminal channel.

(2)  Alice signs an innocuous message, M. If she wants to send Bob the subliminal bit, 1, she makes sure the r parameter of the signature is a quadratic residue modulo P. If she wants to send him a 0, she makes sure the r parameter is a quadratic nonresidue modulo P. She does this by signing the message with random k values until she gets a signature with an r with the requisite property. Since quadratic residues and quadratic nonresidues are equally likely, this shouldn’t be too difficult.

(3)  Alice sends the signed message to Bob.

(4)  Bob verifies the signature to make sure the message is authentic. Then he checks whether r is a quadratic residue or a quadratic nonresidue modulo P and recovers the subliminal bit.