Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In his book "Applied Cryptography" Bruce Schneier, when talking about public key cryptography, says that:
If the same algorithm is used for both encryption and digital-signature verification there is a possible attack. In these cases, the digital signature operation is the inverse of the encryption operation: Vx = Ex and Sx = DX.
I'm not sure how that is possible, could you further explain what Bruce is proposing here?
$\newcommand{\Z}{\mathbb{Z}}$Pick primes $p$ and $q$ with $2^{1023} < p < q < 2^{1024}$ and $n = p q > 2^{2047}$, drawing $p$ and $q$ uniformly at random. $n$ is the public key, and $p$ and $q$ are the private key, with which you can quickly compute cube roots modulo $n$. (You can also use $65537^\text{th}$ roots, but $e = 3$ makes the public-key computations faster and makes no difference for security in sensible RSA-based signature and encryption schemes.)
Suppose a ‘signature’ on a message $m \in \Z/n\Z$ is a cube root $s$ of $m$ modulo $n$ so that $s^3 \equiv m \pmod n$, and suppose you ‘encrypt’ a message $m \in \Z/n\Z$ by cubing it giving a ciphertext $c \equiv m^3 \pmod n$ so that ‘decrypting’ $c$ requires computing cube roots modulo $n$. This is what is endearingly called ‘textbook RSA’, though it should more properly be called ‘do you even RSA, bro‽’.
How does using the same key for signature and encryption make it worse, you ask? Suppose you intercepted a ciphertext $c \equiv m^3 \pmod n$ that someone sent to me, and you want to find the message $m$. If you persuade me to sign $c$ as a message, giving the signature $s$ with $s^3 \equiv c \pmod n$, then the signature I reveal to you is $s \equiv m \pmod n$. Oops.
This is not how modern RSA-based signature or encryption schemes work, fortunately.
In modern RSA-based signature schemes (RSASSA-PSS, RSA-FDH), a signature on an octet string $m$ is a pair $(r, s)$ where $r$ is a (possibly empty) uniform random bit string and $s$ is a cube root of $H_0(r, m)$ modulo $n$, for some standard hash function $H_0$ mapping messages to elements of $\Z/n\Z$ over which the attacker has little control.
In modern RSA-based encryption schemes, we either
(a) RSAES-OAEP: pick a short secret session key $k$ uniformly at random, pick a bit string $r$ uniformly at random, and send $c \equiv H_1(r, k)^3 \pmod n$, where $H_1$ is a hash function mapping short strings to elements of $\Z/n\Z$; or
(b) RSA-KEM: pick $x \in \Z/n\Z$ uniformly at random, send $c \equiv x^3 \pmod n$, and derive the short secret session key $k = H_2(x)$, where $H_2$ is a hash function mapping elements of $\Z/n\Z$ to short octet strings.
Then we use $k$ as the secret key for a symmetric-key AEAD to enclose the message.
Since the attacker can't control more than $b$ bits of the output of $H_0$, $H_1$, or $H_2$ without spending at least $2^b$ effort, varying either the message $m$ to be signed or the ciphertext $c$ to be decrypted doesn't help them either to decrypt messages of their choice or to sign any messages they can figure out.
All that said, the lesson here is that the security of a cryptosystem that uses one key for two different purposes—e.g., signing and encrypting, or even two different encryption schemes such as RSAES-PKCS1-v1_5 and RSAES-OAEP—is not determined by independently analyzing each purpose; combining them may have catastrophic consequences, and the composite cryptosystem must be studied in its own right. If you also want to use, say, a verifiable random function with the same key, you have to study it again.
Say you ask the holder of the private key to decrypt something that you've encrypted for him. You've however lost the original data. So the holder of the private key decrypts the seemingly random data and returns the result.
Now imagine that instead of a ciphertext you send a message to be signed or a hash over the message to be signed. The holder of the private key will try to decrypt it. However, because $D(x) = S(x)$ what is returned is a valid signature over the message. This could be the case for, for instance, raw RSA.
However, for most encryption algorithms this won't be possible in real life. For instance, raw RSA is insecure, so PKCS#1 padding is used. Not only is PKCS#1 padding different for encryption and signature generation, but remember that we have to unpad for decryption and pad for signature generation.
So it depends on the algorithm used, but for often-used encryption primitives the problem is usually not applicable. Still, it is always preferable to use a different key pair for authentication, signing (or rather, non-repudiation) and encryption.
If you have to create your own protocol for, for instance, homomorphic encryption, where raw primitives are more common then sure, remember Bruce's advice.
