(1)  Choose an arbitrary sequence of at least 160 bits and call it S. Let g be the length of S in bits.

(2)  Compute U = SHA(S) ⊕ SHA ((S + 1) mod 2^g), where SHA is the Secure Hash Algorithm (see Section 18.7).

(3)  Form q by setting the most significant bit and the least significant bit of U to 1.

(4)  Check whether q is prime.

(5)  If q is not prime, go back to step (1).

(6)  Let C = 0 and N = 2.

(7)  For k = 0, 1,..., n, let V_k = SHA ((S + N + k) mod 2^g)

(8)  Let W be the integer

W = V₀ + 2¹⁶⁰V₁ +...+ 2^{160(n - 1)}V_{n - 1} + 2¹⁶⁰ⁿ(V_n mod 2^b)

and let

X = W + 2^{L - 1}

Note that X is an L-bit number.

(9)  Let p = X – ((X mod 2_q) – 1). Note that p is congruent to 1 mod 2_q.

(10)  If p < 2^{L - 1}, then go to step (13).

(11)  Check whether p is prime.

(12)  If p is prime, go to step (15).

(13)  Let C = C + 1 and N = N + n + 1.

(14)  If C = 4096, then go to step (1). Otherwise, go to step (7).

(15)  Save the value of S and the value of C used to generate p and q.

In [1154], the variable S is called the “seed,” C is called the “counter,” and N the “offset.”

The point of this exercise is that there is a public means of generating p and q. For all practical purposes, this method prevents cooked values of p and q. If someone hands you a p and a q, you might wonder where that person got them. However, if someone hands you a value for S and C that generated the random p and q, you can go through this routine yourself. Using a one-way hash function, SHA in the standard, prevents someone from working backwards from a p and q to generate an S and C.

This security is better than what you get with RSA. In RSA, the prime numbers are kept secret. Someone could generate a fake prime or one of a special form that makes factoring easier. Unless you know the private key, you won’t know that. Here, even if you don’t know a person’s private key, you can confirm that p and q have been generated randomly.

ElGamal Encryption with DSA

There have been allegations that the government likes the DSA because it is only a digital signature algorithm and can’t be used for encryption. It is, however, possible to use the DSA function call to do ElGamal encryption.

Assume that the DSA algorithm is implemented with a single function call:

    DSAsign (p,q,g,k,x,h,r,s)

You supply the numbers p, q, g, k, x, and h, and the function returns the signature parameters: r and s.

To do ElGamal encryption of message m with public key y, choose a random number, k, and call

    DSAsign (p,p,g,k,0,0,r,s)

The value of r returned is a in the ElGamal scheme. Throw s away. Then, call

    DSAsign (p,p,y,k,0,0,r,s)

Rename the value of r to be u; throw s away. Call

    DSAsign (p,p,m,1,u,0,r,s)

Throw r away. The value of s returned is b in the ElGamal scheme. You now have the ciphertext, a and b.

Decryption is just as easy. Using secret key x, and ciphertext messages a and b, call

    DSAsign (p,p,a,x,0,0,r,s)

The value r is a^x mod p. Call that e. Then call

    DSAsign (p,p,1,e,b,0,r,s)

The value s is the plaintext message, m.

This method will not work with all implementations of DSA. Some may fix the values of p and q, or the lengths of some of the other parameters. Still, if the implementation is general enough, this is a way to encrypt using nothing more than digital signature function.

RSA Encryption with DSA

RSA encryption is even easier. With a modulus n, message m, and public key e, call

    DSAsign (n,n,m,e,0,0,r,s)

The value of r returned is the ciphertext.

RSA decryption is the same thing. If d is the private key, then

    DSAsign (n,n,m,d,0,0,r,s)

returns the plaintext as the value of r.

Security of DSA

At 512-bits, DSA wasn’t strong enough for long-term security. At 1024 bits, it is.