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 &lt; a &lt; p$ and $0 &lt; b &lt; 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 ?
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 &lt; 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.