Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

New answers tagged

2

Given $$\alpha ^{k}\equiv \prod p_{i}^{a^{i}} \mod p$$ take $\log$ of both sides to base $\alpha$ \begin{align} \log_\alpha(\alpha ^{k}) &\equiv \log_\alpha(\prod p_{i}^{a^{i}}) \mod p\\ k &\equiv \sum \log_\alpha(p_{i}^{a^{i}}) \mod p-1 \quad\text{;by Little Fermat}\\ k &\equiv \sum a_i \log_\alpha(p_{i}) \mod p-1\\ \end{align} Here $\...


1

Probably what your professor meant is that you start with any group element $\alpha$, and then use $g := \alpha^t$ as the generator for a cryptosystem such as Schnorr signatures, as long as $g$ is not itself the identity. Why? If $g \ne 1$, then $g$ is guaranteed to have prime order $q$, because $g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$, ...


2

The point is that even though $p - 1 = tq$ may be large, the discrete log security of $(\mathbb Z/p\mathbb Z)^\times$ against Pohlig–Hellman depends on the size of $q$, not on the (possibly much larger) size of $p$ or $tq$. If $q$ is the largest prime factor, then the cost of computing discrete logs modulo $p$ is essentially at most the cost of computing ...


1

I think that Antoine Joux said modulo 4 just because he is explicitly working with two bits (the least significant for the xor and the most significant for the and), although that equation really holds over $\mathbb{Z}$ even if you reduce mod 3, as you noticed. Indeed, in some point of the paper he even defines a function to extract a bit homomorphically. ...


0

Let $p = 2^{255} - 19$. Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$. (Here $k = 1$.) So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\...


1

"Integers modulo 4" is usually the finite ring $(\Bbb Z_4,+,*)$ which internal laws are + | 0 1 2 3 * | 0 1 2 3 --+-------- --+-------- 0 | 0 1 2 3 0 | 0 0 0 0 1 | 1 2 3 0 1 | 0 1 2 3 2 | 2 3 0 1 2 | 0 2 0 2 3 | 3 0 1 2 3 | 0 3 2 1 but here, the question's citation only deals with the finite group $(\Bbb Z_4,+)$. difference ...


6

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; def fast_power(base, power): result = 1 while power > 0: # If power is odd if power % 2 == 1: result = (result * base) % MOD # Divide the power by 2 power = ...


1

Yes. You don't need to wait until the end of the computation to compute the remainder, you can do that in each step of the exponentiation; this way, the largest numbers you'll need to handle are twice the size of n. There are many algorithms to compute the exponentiation itself, the simplest is square-and-multiply.


Top 50 recent answers are included