# Chosen-Message-Attack RSA-Signature

I know that because of the multplicative property of RSA

$s =(s_1s_2) \bmod n = (m_1m_2)^d \bmod n$

If Oscar wants to sign now an own message $m$ he chooses another message $m_1$ with $\gcd(m_1,n)=1$ and he calculates $m_2 = m\cdot m_1^{-1} \bmod n$

After this part I don't understand the attack...

How is he able to sign now his own message $m$ ?

## The Procedure

Step 1: Factor the original signature $s$ into $s=\prod_{i=1}^n s_i$ and then exponentiate each signature with $e$ as in: $m=\prod_{i=1}^n s_i^e=\prod_{i=1}^n m_i$. Different methods to obtain multiple $s_i,m_i$ pairs work just as well, such as asking the signing oracle.

Step 2: Build a new message with a valid signature as the product of any subset of the $m_i$, e.g. $m'=\prod_{k\in M'\subseteq \{m_1,...,m_n\}}m_k$ now build the same product for the signatures and you've successfully forged your message: $s'=\prod_{k\in S'\subseteq \{s_1,...,s_n\}}s_k$ where $S'$ is the corresponding set of signatures to $M'$.

## The Theory

The theory behind step 2 is exactly as you'd have imagined, e.g. you have some $(m_i,s_i=m_i^d \bmod n)$ pairs and multiply them the signatures to get the new signature $s'=s_1\cdot s_2 \cdot ... \cdot s_n=m_1^d\cdot m_2^d \cdot ... \cdot m_n^d=(m_1\cdot m_2 \cdot ... \cdot m_n)^d=(m')^d$ which by definition of the RSA signature scheme is a valid signature for $m'$.

## The (simple) Example

Let's take the example from the comments: $p=3,q=11,n=33,\varphi(n)=20,e=3,d=7$ and we are provided with two message / signature pairs: $(m_1,s_1)=(4,16),(m_2,s_2)=(6,30)$.

Now let's skip step 1 for now and directly proceed with step 2 (as we already have more than one message-signature-pair). Step 2 says: "select any message-signature-pairs and multiply them together". So we have $m'=m_1\cdot m_2\bmod n=(4\cdot 6) \bmod 33 = 24$ and we have $s'=s_1\cdot s_2 \bmod n=16\cdot 30 \bmod 33=18$. Thus we have constructed the message-signature-pair $(24,18)$.

Let's also quickly apply the theory part here: $m^d\bmod n$ is a valid signature for any message $m$. $s'=16\cdot 30 \bmod 33=(4^7\bmod 33)\cdot (6^7 \bmod 33) =(4\cdot 6 )^7 \bmod 33=(24)^7\bmod 33 = 18$

• I have for example n =33, phi(n)=20, e =3 Alice did send Bob two messages --> (m,s) = (4,16) and (6,30) Then we calculated m' = (4*6 mod 33 = 24) and s'=(16*30 mod 33 = 18) – userkir May 28 '16 at 15:08
• Yet, I still do not get the second part, where we have to build our own new message – userkir May 28 '16 at 15:14
• @userkir I have tried to clarify my answer, tell me if there's still something unclear. – SEJPM May 28 '16 at 17:30
• I'm really thankful for the answers. Nearly everthing is clear except for m' . So in this case Oscar can't choose the message m' freely , can he ? – userkir May 28 '16 at 18:25
• @userkir, no he can't. $m'$ must be constructed from what you can extract from the given set of signatures / messages. – SEJPM May 28 '16 at 18:27

Suppose you want to obtain the signature $s = m^d \bmod n$ on a chosen message $m$. Here is that attack.

1. You ask the signer to sign a random message $m_1$ and obtain the corresponding signature $s_1 = m_1^d \bmod n$;
2. You compute message $m_2 := m\cdot m_1^{-1} \bmod n$ and ask the signer to sign message $m_2$; you obtain the signature $s_2 = m_2^d \bmod n$.

From the pairs $(m_1,s_1)$ and $(m_2,s_2)$, the signature $s$ on chosen message $m$ can be recovered as $s = s_1 \cdot s_2 \bmod n$.

To see it, observe that $s \equiv s_1 \cdot s_2 \equiv m_1^d \cdot m_2^d \equiv m_1^d \cdot (m\cdot m_1^{-1})^d \equiv m_1^d \cdot m^d \cdot m_1^{-d} \equiv m^d \pmod n$.

Note that you could obtain the signature on message $m$ by only asking one signature to the signer. Indeed, you can construct the pair $(m_1,s_1)$ in Step 1 above by yourself as follows: choose a random $s_1$ modulo $n$ and define $m_1 = s_1^e \bmod n$ (where $e$ is the public verification exponent). We then have $m_1^d \equiv s_1 \pmod n$ as required.

• But why should Alice sign a single message for me ? – userkir May 29 '16 at 8:44
• The messages Alice is asked to sign are "random looking"---and so appear as innocent messages. Bob (the attacker) can for example tells Alice that the message represents a key and asks Alice to sign it to authenticate the key. From the received signature, Bob can then obtain the signature on chosen message $m$ (for example, $m=$"Alice owes Bob $1,000,000"). – user94293 May 29 '16 at 13:50 • Okay, cool thats interesting. But this wouldn´t work if Alice and her Partner would use a Hash function, right ? – userkir May 29 '16 at 14:08 • Correct in general (this depends on the hash function) ---see Desmedt and Odlyzko (Crypto'85) though. But for example, if the hash function is a full-domain hash function (i.e., whose output range is$\{0, \dots, n-1\}\$), the resulting signatures are secure. This is the well-known RSA-FDH signature scheme. – user94293 May 29 '16 at 14:36