Skip to main content
19 votes

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 ...
SEJPM's user avatar
  • 46k
16 votes
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 ...
CurveEnthusiast's user avatar
16 votes
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 ...
diagprov's user avatar
  • 721
15 votes

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 ...
Ilmari Karonen's user avatar
15 votes
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 ...
poncho's user avatar
  • 147k
11 votes
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 (...
poncho's user avatar
  • 147k
10 votes
Accepted

Why are elliptic curves constructed using prime fields and not composite fields?

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{...
CurveEnthusiast's user avatar
10 votes
Accepted

Elliptic Curve Cryptography - When to use p and when to use n

A possible analogy is two layers in a communication protocol, with $p$ and $n$ the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically ...
fgrieu's user avatar
  • 141k
10 votes
Accepted

Elliptic Curve - Divide by 2

There are two strategies to do what you want. The first one being to find the group order $q$ and then compute $i=2^{-1}\bmod q$. When you then multiply your point $P$ by $i$ you get $Q=[i]P$ with $[...
SEJPM's user avatar
  • 46k
10 votes
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 ...
kelalaka's user avatar
  • 48.5k
9 votes
Accepted

Find the generators of multiplicative group of units efficiently?

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $...
fgrieu's user avatar
  • 141k
9 votes

Non-commutitive and nonassociative algebraic structures in cryptography

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these ...
Joseph Van Name's user avatar
9 votes
Accepted

Discrete logarithm problem is easy in a cyclic group of order a power of two

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$. Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $...
J.D.'s user avatar
  • 4,445
8 votes
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) ...
fgrieu's user avatar
  • 141k
8 votes

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 ...
CurveEnthusiast's user avatar
8 votes
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 ...
yyyyyyy's user avatar
  • 12.1k
8 votes
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 ...
Aman Grewal's user avatar
  • 1,421
8 votes
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 ...
kodlu's user avatar
  • 22.5k
7 votes

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 ...
Ruggero's user avatar
  • 7,094
7 votes
Accepted

How to construct a hash function into a cyclic group such that its discrete log is intractable?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(...
poncho's user avatar
  • 147k
7 votes
Accepted

How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

Notation is basically a free choice of the author, as they describe functionally the same. And there is no fixed definition for this. However, common practice in mathematical publications is: ...
tylo's user avatar
  • 12.7k
7 votes
Accepted

Factoring large $N$ given oracle to find square roots modulo $N$

What I have come up with till now is, first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a\equiv\pm b\pmod N$. Repeat this ...
yyyyyyy's user avatar
  • 12.1k
7 votes

Why are elliptic curves constructed using prime fields and not composite fields?

To complete the other answer, one can note that elliptic curves over the $\mathbb{Z}/n\mathbb{Z}$ ring for non-prime $n$ are at the heart of Lenstra elliptic curve factorization, so such elliptic ...
Frédéric Grosshans's user avatar
7 votes
Accepted

Groups for which DDH is easy but CDH is hard

Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?) Yes, if $g$ is an element with ...
poncho's user avatar
  • 147k
7 votes

Why do elliptic curves require fewer bits for the same security level?

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, ...
Squeamish Ossifrage's user avatar
7 votes
Accepted

Discrete logarithm weak group

Is there any better algorithm ? Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You ...
poncho's user avatar
  • 147k
7 votes
Accepted

Why do algebraic proofs apply to cryptography?

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results. Given the terminology in your question, ...
Gilles 'SO- stop being evil''s user avatar
7 votes

Why Abstract Algebra in Cryptography?

Abstract algebra basically comprises Groups, Rings, Fields, Vector Spaces, Modules, and many other algebraic structures. It is not only useful in Cryptography but in Channel Coding, in the branch of ...
SSA's user avatar
  • 640
7 votes

VDF / RSA groups

The RSA group for modulus $N$ of secret factorization simply is the multiplicative group of integers modulo $N$, often noted $\mathbb Z_N^*$. That can be viewed or defined as the subset of integers $m$...
fgrieu's user avatar
  • 141k

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