# How is information disclosed by modular multiplication?

Consider the case that

$c = a \cdot b \mod p$

where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are known.

Q1: Can an attacker learn some bits of $a$ using this information?

The question is based on the following non-modular example:

$a = x_1 \cdot 2^z + x_0$

and

$b = x_2 \cdot 2^z + x_3$

gives the product:

$a \cdot b = x_1x_22^{2z} + (x_0x_2+x_1x_3)2^z + x_0x_3$

Then if anyone knows the $z$ least significant bits of $a \cdot b$ (the product $x_0x_3$), then some of the divisors of $x_0x_3$ is equal to $x_0$, allowing to bound the possible values of $x_0$ to the possible divisors of $x_0x_3$.

Q2: Can this non-modular analysis be applied to the modular one ?

• In some cases yes [Factorization of a number obtained by a modular multiplication operation can reveal factors of the used operands], for example if $n$ is even, then $ab\mod n$ is even if and only if $ab$ is even, which means that either $a$ or $b$ is even. May 22 '15 at 16:34
• "Works" for $n = 3$ as well, if the remainder of $ab$ is 2 mod 3 then one of $a$, $b$ must be 2 mod 3, and the other must be 1 mod 3. Similarly if $ab$ is 1 mod 3 then $a$ and $b$ must have the same remainder mod 3... (ignoring the trivial case where $ab$ is divisible by 3). Not sure how much useful information that leaks though. May 23 '15 at 3:00

Can an attacker learn some bits of a using this information?

No. In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$.

That is, even if we knew all the bits of $c$, no particular value of $a$ are any more likely than any other (assuming we have no information about $b$). And, in particular, we have no information on any of the bits of $a$ (other than what's implied by $1 \le a < p$, which we already knew).

Any observation in the non-modular case (where this observation does not apply) doesn't apply to the modular case.

Moderator note: This answers a different question that I incorrectly merged:

Consider a number $$r$$ obtained by:
$$\quad r=a⋅b\bmod n$$
Can knowing the factorization of $$r$$ reveal some information (bits) of $$a$$ and $$b$$ ?

The factoring of $$r$$ is not unique $$\pmod n$$.