0
$\begingroup$

Suppose to have a function for numbers expressed in 8-bit $\in [0,2^8-1]$ defined as: $$f(x)=x||x||x||x$$ where $|f(x)|$ is exactly 32 bits.

e.g., suppose x=2 (00000010) so $f(x)=2+2^9+2^{17}+2^{25}=33686018$ (00000010000000100000001000000010)

Given N and x I'd like to find y,z,w s.t.

$$f(x)*f(y) \space mod \space N= f(z)*f(w) \space mod \space N$$

What is a good way to proceed?

Improve this question
$\endgroup$
1
$\begingroup$

OBVIOUS, if you write $f(x)=(1+2^8+2^{16}+2^{24})\times x=K\times x$. Then $f(x)\times f(y)=K^2\times x \times y$. Then $\forall y$, choosing $z \in (\mathbb{Z}/n.\mathbb{Z})^{*}$ allows to dermine the unique $w \in \mathbb{Z}/n.\mathbb{Z}$ satisfying this relation in the multiplicative group.

Improve this answer
$\endgroup$
  • $\begingroup$ Use the table of the multiplicative group. From $K^2\times x \times y\;=\; K^2\times z \times w $ what could you do in a set endowed with a group structure? $\endgroup$ – Robert NACIRI Mar 25 '15 at 14:34
  • $\begingroup$ sorry I misclick and delete the original question on the comment that was "how to choose z and w?". So I have just to bring any w and z s.t. $wz=xy$ or is there some other criteria that I am missing? $\endgroup$ – abc Mar 25 '15 at 14:39
  • $\begingroup$ Take a look over the to the definition of group structure and understand how to do arithmetric. here if you fix three parameters x, y, and z you can calculate w, exactly as you have to do in elementary school. This is only arithmetic. $\endgroup$ – Robert NACIRI Mar 25 '15 at 14:59
  • $\begingroup$ Thanks, but when you write $\mathbb{Z}/n.\mathbb{Z}$ who is $n$ there? $\endgroup$ – abc Mar 25 '15 at 15:05
  • $\begingroup$ This is your N. Sorry for the typo. $\endgroup$ – Robert NACIRI Mar 25 '15 at 15:10

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.