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$


$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 ?

  • $\begingroup$ 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. $\endgroup$
    – fkraiem
    May 22 '15 at 16:34
  • $\begingroup$ "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. $\endgroup$
    – Thomas
    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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.