1
$\begingroup$

I have a hidden function $f(x) = x \pmod{n}$ and would like to solve for $n$ based on a set of input and output pairs which can be chosen freely.

I would like to do this without brute force (i.e. start at $x_0=1$ and iterate $x_{i+1}=x_i+1$ until $f(x_i)=0$).

So far I have observed that if I expand $x=an+b$, then by subtracting $f(x)=b$ from the input, I am left with $x-f(x)=an$.

I can repeat this operation for various inputs and obtain a list of different multiples of $n$, but I cannot work out how to use them to solve for $n$ itself.

If I use the above procedure to obtain distinct $a_0n$ and $a_1n$, I could compute $gcd(a_0n,\,a_1n) = kn$, but there is no guarantee that $k=1$, and the situation remains the same no matter how many $a_in$ are processed in this way.

Is this even a solvable problem or do I need to include extra constraints on the function, like being explicit about the domain, perhaps $f := \mathbb{F_2}[x] \to \mathbb{F_2}[x]$ (polynomials with binary coefficients)?

$\endgroup$
0
1
$\begingroup$

You've done the hard work by finding that you can obtain $m_i=a_i\,n$ for various (unknown but essentially random) values of $a_i$.

Now define $n_0=m_0$, and compute $n_i=\gcd(n_{i-1},m_i)$ for increasing $i>0$. Sooner rather than later, the $n_i$ will converge to $n$.

This can be proved rigorously (though we often skip rigorous proofs in a crypto context). Sketch: prove by induction that $n_i=k_i\,n$ for $k_i$ dividing all $a_j$ with $0\le j\le i$. Then consider any prime factor $p$ of $k_i$, and the probability that it survives up to $i$ under the assumption that the $a_i$ are random.

Note: This works in a wider context than integers, e.g. polynomials, by changing "prime" to "irreducible".

$\endgroup$
1
  • $\begingroup$ Thanks, the proof sketch is useful $\endgroup$ – conchild Dec 29 '19 at 12:12
1
$\begingroup$

This smells like a HW question, so the OP should try it with more hints.

By querying this function at $x$, it is easy to tell whether $x\geq n$ or $x<n$. Let $k$ be a natural number such that $2^k<n\leq 2^{k+1}$, how many queries do you need to find this $k$? Knowing this $k$, how can you figure out $n$?


If the modulo operation is part of polynomial division with remainder, you could find the degree of $n$ using binary search. Once you know the degree, you can query another polynomial to find $n$.

$\endgroup$
3
  • $\begingroup$ I cannot depend on these inequalities because $f$ could be defined on a finite-field with no ordering. $\endgroup$ – conchild Dec 27 '19 at 8:57
  • $\begingroup$ @conchild does that mean the $\text{mod }n$ is remainder of polynomial division (the divisor is $n$)? $\endgroup$ – Gee Law Dec 28 '19 at 1:45
  • $\begingroup$ Yes, that could be the case $\endgroup$ – conchild Dec 29 '19 at 12:11

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.