New answers tagged

2

We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$. This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}\mod p$ is, you can just plug that value in and do computations like you'd expect. Note that $3^{-1}\mod p$ means the element $u\in(\mathbb{Z}/p\mathbb{Z})^\...


2

For the function $F(x) = ax \bmod n$, where the inputs are limited to the range $[0, n)$, this function will be a bijection (that is, no collisions) if and only if $a$ and $n$ are relatively prime. Here is a proof in the direction you're asking about: Suppose there exists a collision, that is, we have a pair $x, y$ with $0 \le x < y < n$ where $F(x) =...


1

For this specific example, which doesn't make for a really useful hash function given that it isn't compressing, it's rather easy to prove the presence or absence of collisions. So, assume $$H_{a,n}(x)=a\cdot x\bmod n$$ is the hash function we are looking it. Then if $H_{a,n}(x)\cdot a^{-1}\bmod n$ has a unique value, then there is exactly one input for ...


4

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance. In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\...


1

The prototypical example of a group in cryptography is a cyclic group. You can write this in a variety of ways, so I'll go through a few quickly. Additively: Consider the group $\mathbb{Z}/n\mathbb{Z}$ under $+$. This forms a group, and it's a cyclic group generated by $\langle 1\rangle$ (subject to the relation that $n\cdot 1 = 0$). Note that the "...


Top 50 recent answers are included