# Tag Info

## Hot answers tagged group-theory

10

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a ...

10

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$ $= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] ...

9

The cornerstone of the argument is the following: If the cycle attack works, then you can factor $n$ (see details below). The attacker can choose $e$. I.e., when trying to factor $n$, the attacker is not constrained to use the specific $e$ which you selected for your public key; he can invent his own $e$, since he will do all the computations himself. ...

8

As far as I understand, the HSP is a hard problem such that: some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built); many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key. In particular, integer ...

7

Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a ...

6

The question makes a number of statements that are incorrect. It is not correct that a fixed point is guaranteed to exist. It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist. Moreover, the existence of fixed points has only an extremely tenuous connection to security. Assume $E$ is a ...

6

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup. One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in ...

6

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...

5

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits. Let $n = pq$ be RSA modulus. Generate random number $a$ co-prime to $n$ and random number $x < n$ but very close to $n$. Compute $b = a^x \text{ mod } n$ but ...

5

With addition and $\mathbb{Z}_n$, each party chooses a secret $x$ and sends $xg \pmod n$ over the wire, for an agreed upon generator $g$. Division by $g$ modulo $n$ is easily computable, and reveals $x$. In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With $\mathbb{Z}_n$ and ...

5

This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain. For prime $p$, we know that $g^{p-1} \equiv 1 \pmod{p}$. Therefore, $y = g^{p-2} \equiv 1/g \pmod {p}$. Therefore, $(xg).y \equiv x \pmod{p}$, revealing the secret key. If modulus is not ...

4

Almost all cryptographic algorithms which use groups actually work in subgroups generated by a conventional element; even if the group as a whole is non-abelian, the subgroup is cyclic, thus abelian. The Anshel-Anshel-Goldfeld protocol tries to use non-commutativity itself, and relies on "how much non-abelian" the group is. All asymmetric cryptographic ...

4

If $\mathcal{G}$ is of order $N$ (who doesn't look like a prime number btw) and $g$ is a generator of $\mathcal{G}$ then $g$ has order N. Since $(g^{nq})^p=1$ and $\forall 1\le k <p, (g^{nq})^k\neq 1$ (g has order $N$ and $knq<N$) then $g^{nq}$ generates a subgroup of $\mathcal{G}$ of order $p$ and there's only one such subgroup : $\mathcal{G_p}$. The ...

4

As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus". Here's is a demonstration that the discrete log problem is not drastically easier than factoring the ...

4

The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory. That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e., $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of ...

4

Your first two paragraphs made a series of statements; these statements were less than perfectly accurate, and D.W. attempted to address those. You then went on and asked What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, ...

4

The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$. There is also the Computational Linear Assumption (CLIN), which states that it is hard to ...

4

Firstly, $|\mathbb Z_n|=n$, whereas $|\mathbb Z_n^*|=\varphi(n)<n$. So, by the pigeon-hole principal there cannot be a mathematically invertible function $f:\mathbb Z_n\to\mathbb Z_n^*$. So, lets relax our idea of what 'invertible' means a bit. How about ensuring every element of $\mathbb Z_n^*$ has a preimage? Yep, we can do that. To use a couple of ...

3

The multiplication operation is indeed not uniquely reversible given just the output. But we also have one of the inputs, namely, the subkey. We can use that to reverse the multiplication. Decryption for IDEA requires changing the subkeys in the key schedule. I didn't find a good description of IDEA online, so I went back to Applied Cryptography, 2nd ...

3

You also asked I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions. One nontrivial result is here; what this result states is that a composition of the DES round functions ...

3

U-Prove Recommended Parameters describes the groups used by U-Prove. For the subgroup variant it references Appendix A.1.1.3 of FIPS186-3 which is about groups for finite-field based DSA. AFAIK these groups are Schnorr groups, even though NIST never refers to them as such. The ECC variant uses standard NIST curves such as P-256, P-384 and P-521.

3

Every element $g$ in a group $G$ generates a subgroup of $G$ of order $r$, where $r$ is the smallest (non-zero) integer such that $g^r = 1$. Moreover, if $g^s = 1$ for some positive value $s$, then $s$ is a multiple of $r$. Finally, $r$ necessarily divides the order of $G$ (i.e. the number of elements in $G$). Therefore, if your group order is $N = ab$ for ...

3

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA ...

3

One of the biggest problems you'll have is to ascertain that $m^{e^k} = m$ for some $k$. You need to have a way of knowing that particular value is genuine. Given the typical use-case of RSA applies padding and is used for small data sizes for things such as keys to symmetric algorithms, it isn't always likely that this check will be easy to compute. The ...

3

Given the additive group $(G, +)$ with $|G| = p$ and generator $P$, what are the computations and exchanged messages for Diffie-Hellman? I use order $p$ and assuming $p$ to be prime and the generator as $P$ (as it is used in context of elliptic curve groups - since you need additive groups where the DLP and the CDHP are hard - which is not the case for ...

3

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in ...

2

In my experience, I never have found that cryptographers base their opinion of a cryptosystem on the properties of the underlying group. If its a braid group, abelian group, or finite field: that does not really matter. What matters is, as @Thomas notes, how hard do we think the problem is in a particular setting? Cryptography in braid groups usually has ...

2

You need to refine your definition of discrete logarithm to get a precise answer, as the discrete logarithm problem can be defined for any group, Being able to compute the discrete logarithm on the group of points of a degenerate elliptic curves defined over the ring $Z_n$ also yields the factorization of $n$ (see Silverman's xedni calculus).

2

According to this: To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes. So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite ...

2

In cryptography, you care not merely that some problem is hard but that hard instances are readily producible. Why don't people use NP-complete problems for cryptography, for example? An NP-complete problem would give you greater confidence asymptoticly speaking for two reasons : If any NP-complete problem were collapsed to P, then factoring becomes P ...

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