# Tag Info

0

Your Question is related to the well know RABIN Cryptosystem which is similary like RSA, except the public exponenent is 2. As fgrieu mentionned it, decipherment can be easilly processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the resolution the equation gives 4 roots, which mean that the ...

2

Fkraiem's answer is correct: this is not necessary. From your comment on his answer it seems however you don't understand why Alice and Bob retrieve the same key. This, again, doesn't rely on $g$ being a generator. Recall from your high school math classes that $(g^a)^b = g^{ab} = g^{ba} = (g^b)^a$. This is basically the trick that is being used here. Since ...

5

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.

0

In this case, take a look to the GQ identication scheme, from Guillou and Quisquater.

0

Let u = a mod n, i.e., the least residue modulo n. Then: a = u + k.n for some k in Z. The binomial expansion of the exponential is: $$(u + kn)^{b} = \sum_{i = 0}^{b}\binom{b}{i}u^{b - i}(kn)^{i}$$ Every term, except for i = 0, is a multiple of (n), which is congruent to 0 mod n. The i = 0 term: (u^b), yields: (a mod n)^b.

1

Since you only ask for help, help is what I will give. I will not solve it for you, however. That said, since you didn't give an indication of where you are stuck, it is hard to help. Hopefully this helps. If you can show that $(a\bmod{n}\cdot c\bmod{n})\bmod{n} \equiv (a\cdot c)\bmod{n}$, for all $a,c\in\mathbb{Z}_n^*$, then you can show the property you ...

1

$$\pi\colon\;\mathbb Z\to \mathbb Z/n\mathbb Z,\;a\mapsto a+n\mathbb Z$$ is a ring homomorphism.

3

After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and ...

2

Claim. $a^{(p-1)/2} = 1$ if and only if $x$ is even. Proof. If $x$ is even, let $x = 2y$. Then $$a^{(p-1)/2} = (g^x)^{(p-1)/2} = g^{2y(p-1)/2} = (g^{p-1})^y = 1^y = 1.$$ If $x$ is odd, let $x = 2y+1$. Then $$a^{(p-1)/2} = g^{(2y+1)(p-1)/2} = \dots$$ (remember here that $g$ is a generator of $\mathbf{F}_p^*$).

Top 50 recent answers are included