# Tag Info

4

The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3): The $S_j$ (which are witnesses to the quadratic residuosity character of the $I_j$) are effectively hidden by the difficulty of extracting square roots $\bmod n$, and thus A can establish his ...

3

The problem is one of notation for modular arithmetic, at the point of the question reading if y^2 equals (x * v^e) % n then.. Likely the textbook is about if $y^2\equiv x\cdot v^e\pmod n$ then.. By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 ...

2

A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B. Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number. See: Quadratic residue problem on composite integers

2

Without a sign the verifier learns that the number he received is a QR modulo n. Whether a number is a QR is a hard problem as he does not know the factors of n.

2

The first problem is, that you calculated $v_i$ wrong right at the start. $$v_i = s_i^2 \mod n$$ This means: $$v_1 = 5^2 = 25 \mod 77$$ $$v_2 = 12^2 = 67 \mod 77$$ $$v_3 = 37^2 = 60 \mod 77$$ Then at the end you have: $$(x \cdot \prod_i v_i^{a_i}) = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77$$

1

In order to convert a 3-move id-scheme to a digital signature you have to replace the request (or the challenge) by the value of a secure hash function applied to the message (this method is called Fiat-Shamir method). In Sterns's id-scheme you have to choose a random element from the set $\{0,1,2\}$ for your message. That is $H(m)\in \{0,1,2\}.$ For ...

1

No, it wouldn't. Very simply put: If you can compute square roots wrt. a composite modulus, then you can calculate other fixed roots, too. This is based on the fact, that being able to compute square roots allows you to factor the modulus: Choose random $x$. Compute $x^2$. apply your square root algorithm to $x^2$. The result $y$ will be a different ...

1

Your question is related to the well known RABIN Cryptosystem which is similar to RSA, except the public exponent is 2. As fgrieu mentioned, decipherment can be easily processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the solution of the equation gives 4 roots, which means that the solution ...

1

Because we are working modulo $n$. There's not much more to say. There's no reason why any honest user would ever want to use a larger value. You might want to review modular arithmetic and its use in cryptography.

Only top voted, non community-wiki answers of a minimum length are eligible