Mixing
Why can we not use the group $Z_p^*$ for cryptography?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.
rsa dsa
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
2
down vote
favorite
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.
rsa dsa
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.
rsa dsa
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.
rsa dsa
rsa dsa
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 50 mins ago
asked 3 hours ago
Erik
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Erik
113
asked 3 hours ago
Erik
113
113
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Erik is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago
add a comment |Â
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
edited 11 mins ago
Ella Rose
13.5k33372
answered 2 hours ago
jadb
3507
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
edited 11 mins ago
Ella Rose
13.5k33372
answered 2 hours ago
jadb
3507
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
add a comment |Â
up vote
5
down vote
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
edited 11 mins ago
Ella Rose
13.5k33372
answered 2 hours ago
jadb
3507
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
add a comment |Â
up vote
5
down vote
up vote
5
down vote
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
edited 11 mins ago
Ella Rose
13.5k33372
answered 2 hours ago
jadb
3507
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
edited 11 mins ago
Ella Rose
13.5k33372
answered 2 hours ago
jadb
3507
edited 11 mins ago
Ella Rose
13.5k33372
edited 11 mins ago
Ella Rose
13.5k33372
edited 11 mins ago
Ella Rose
13.5k33372
13.5k33372
answered 2 hours ago
jadb
3507
answered 2 hours ago
jadb
3507
answered 2 hours ago
jadb
3507
3507
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
add a comment |Â
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
@fgrieu, thanks... I assumed the multiplicative group but good to be explicit.
– jadb
1 hour ago
add a comment |Â
Erik is a new contributor. Be nice, and check out our Code of Conduct.
Erik is a new contributor. Be nice, and check out our Code of Conduct.
Erik is a new contributor. Be nice, and check out our Code of Conduct.
Erik is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62436%2fwhy-can-we-not-use-the-group-z-p-for-cryptography%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Are you specifically asking about DSA vs ECDSA?
– mikeazo
3 hours ago
Rather about ElGamal v.s. ECDSA, I think
– Erik
2 hours ago
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
– Ilmari Karonen
2 hours ago
...although we do also have this general question with some pretty nice answers.
– Ilmari Karonen
2 hours ago