Diffie-Hellman with non-prime modulusShortening Diffie Hellman key size through pbkdf?Authenticated Diffie Hellman Key ExchangeHow does SSH use both RSA and Diffie-Hellman?Diffie-Hellman and MIM attack, and server identityIn Ephemeral Diffie Hellman Key Exchange - what is actually ephemeral?DTLS and Ephemeral Diffie-HellmanAre public/private keys needed when using Diffie-Hellman with TLSDiffie Hellman Pre Master Secret too longHow to verify Diffie Hellman uses a “Safe” primeIs the server's private key needed in the Diffie Hellman key exchange?
In Endgame, why were these characters still around?
Is Cola "probably the best-known" Latin word in the world? If not, which might it be?
What happens to the Time Stone
Can Ghost kill White Walkers or Wights?
Casual versus formal jacket
Does this article imply that Turing-Computability is not the same as "effectively computable"?
What does this colon mean? It is not labeling, it is not ternary operator
Is it cheaper to drop cargo than to land it?
Father and Son and Grandsons
Unknowingly ran an infinite loop in terminal
Comment rendre "naysayers" ?
Can fracking help reduce CO2?
Enumerate Derangements
Which industry am I working in? Software development or financial services?
Was Unix ever a single-user OS?
Do I really need diodes to receive MIDI?
Why do money exchangers give different rates to different bills?
Besides the up and down quark, what other quarks are present in daily matter around us?
For a benzene shown in a skeletal structure, what does a substituent to the center of the ring mean?
How can I close a gap between my fence and my neighbor's that's on his side of the property line?
How do I tell my manager that his code review comment is wrong?
Quoting Yourself
What happens if I start too many background jobs?
Pressure inside an infinite ocean?
Diffie-Hellman with non-prime modulus
Shortening Diffie Hellman key size through pbkdf?Authenticated Diffie Hellman Key ExchangeHow does SSH use both RSA and Diffie-Hellman?Diffie-Hellman and MIM attack, and server identityIn Ephemeral Diffie Hellman Key Exchange - what is actually ephemeral?DTLS and Ephemeral Diffie-HellmanAre public/private keys needed when using Diffie-Hellman with TLSDiffie Hellman Pre Master Secret too longHow to verify Diffie Hellman uses a “Safe” primeIs the server's private key needed in the Diffie Hellman key exchange?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
When using the Diffie-Hellman key-exchange, it is said to be important to use a safe prime. However, if a non-prime modulus with sufficient bit-length is generated, is there an attack that can be used to recover the shared secret from the public communication (g, g^a, g^b, modulus) or to decrypt an encrypted message?
cryptography diffie-hellman
asked Apr 23 at 4:57
InfuzionInfuzion
1286
add a comment |
When using the Diffie-Hellman key-exchange, it is said to be important to use a safe prime. However, if a non-prime modulus with sufficient bit-length is generated, is there an attack that can be used to recover the shared secret from the public communication (g, g^a, g^b, modulus) or to decrypt an encrypted message?
cryptography diffie-hellman
asked Apr 23 at 4:57
InfuzionInfuzion
1286
add a comment |
When using the Diffie-Hellman key-exchange, it is said to be important to use a safe prime. However, if a non-prime modulus with sufficient bit-length is generated, is there an attack that can be used to recover the shared secret from the public communication (g, g^a, g^b, modulus) or to decrypt an encrypted message?
cryptography diffie-hellman
asked Apr 23 at 4:57
InfuzionInfuzion
1286
When using the Diffie-Hellman key-exchange, it is said to be important to use a safe prime. However, if a non-prime modulus with sufficient bit-length is generated, is there an attack that can be used to recover the shared secret from the public communication (g, g^a, g^b, modulus) or to decrypt an encrypted message?
cryptography diffie-hellman
cryptography diffie-hellman
asked Apr 23 at 4:57
InfuzionInfuzion
1286
asked Apr 23 at 4:57
InfuzionInfuzion
1286
asked Apr 23 at 4:57
InfuzionInfuzion
1286
asked Apr 23 at 4:57
InfuzionInfuzion
1286
asked Apr 23 at 4:57
InfuzionInfuzion
1286
1286
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
TL;DR: Yes, it possibly could be decrypted.
NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.
Why you should not use non-primes
Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.
One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.
For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.
Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.
Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.
There also may be other problems I am unaware of.
Thanks to AleksanderRas for the link to CryptoSE.
Why you should use safe primes
The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
add a comment |
Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.
Also see this question on CryptoSE for more information.
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "162"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fsecurity.stackexchange.com%2fquestions%2f207868%2fdiffie-hellman-with-non-prime-modulus%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
TL;DR: Yes, it possibly could be decrypted.
NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.
Why you should not use non-primes
Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.
One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.
For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.
Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.
Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.
There also may be other problems I am unaware of.
Thanks to AleksanderRas for the link to CryptoSE.
Why you should use safe primes
The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
add a comment |
TL;DR: Yes, it possibly could be decrypted.
NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.
Why you should not use non-primes
Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.
One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.
For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.
Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.
Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.
There also may be other problems I am unaware of.
Thanks to AleksanderRas for the link to CryptoSE.
Why you should use safe primes
The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
add a comment |
TL;DR: Yes, it possibly could be decrypted.
NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.
Why you should not use non-primes
Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.
One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.
For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.
Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.
Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.
There also may be other problems I am unaware of.
Thanks to AleksanderRas for the link to CryptoSE.
Why you should use safe primes
The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
TL;DR: Yes, it possibly could be decrypted.
NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.
Why you should not use non-primes
Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.
One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.
For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.
Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.
Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.
There also may be other problems I am unaware of.
Thanks to AleksanderRas for the link to CryptoSE.
Why you should use safe primes
The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
edited Apr 24 at 21:22
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
answered Apr 23 at 7:11
Peter HarmannPeter Harmann
6,19251527
6,19251527
add a comment |
add a comment |
Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.
Also see this question on CryptoSE for more information.
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
add a comment |
Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.
Also see this question on CryptoSE for more information.
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
add a comment |
Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.
Also see this question on CryptoSE for more information.
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.
Also see this question on CryptoSE for more information.
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
answered Apr 23 at 7:14
AleksanderRasAleksanderRas
314111
314111
add a comment |
add a comment |
Thanks for contributing an answer to Information Security Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fsecurity.stackexchange.com%2fquestions%2f207868%2fdiffie-hellman-with-non-prime-modulus%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
