# Tag Info

### Why are finite groups used in cryptography?

Can someone explain why is that the case? Cryptosystems based on finite sets have two very nice properties: There is an upper bound to the size of all involved mathematical objects. This also allows ...
• 46k
Accepted

### Why must an elliptic curve group for ECC have prime order?

Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime ...
• 3,489
Accepted

### Is every point on an elliptic curve of a prime order group a generator?

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$. Since ...
• 721

### Why are finite groups used in cryptography?

Mostly, I would say that finite groups get used in crypto because they're a good way to describe things that naturally appear in many crypto schemes. For example, going way back to the early days of ...
• 46.1k
Accepted

### Why is the discrete logarithm problem hard?

Now, I wonder if there are any better arguments. Ultimately, no, not really. We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem ...
• 147k
Accepted

### Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (...
• 147k
Accepted

• 46k
Accepted

### How to decide if a point on a elliptic curve belongs to a group generated by a generator $g$?

The answer really depends on the Cryptographic Elliptic Curves that we know! Prime order Cryptographic EC: Since the order of the subgroup generated by an element must divide the order, then there is ...
• 48.5k
Accepted

• 4,445
Accepted

### What is a cyclic group of prime order $q$ such that the DLP is hard?

Cyclic group of prime order q such that the DLP is hard A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) ...
• 141k

### why are non singular curves used in elliptic curve cryptography?

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography. Why not use singular curves? It turns ...
• 3,489
Accepted

### How to find the order of a generator on an elliptic curve?

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of ...
• 12.1k
Accepted

### Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since ...
• 1,421
Accepted

### Is AES a group?

See the paper DES is not a group by Campbell and Wiener. TL;DR There are computational proofs that DES is not a group. The point is to carry out the types of computations that established DES is not a ...
• 22.5k

### Why must an elliptic curve group for ECC have prime order?

It's due a general performance/security tradeoff for discrete logarithm based cryptography. It doesn't apply to ECC only, but it's a generic rule. If the order is composite then it is possible (see ...
• 7,094