5
$\begingroup$

Basically the title says it all. It would be great if someone could tell give an example using provable security. More information about groups can be found at:

https://en.wikipedia.org/wiki/Group_(mathematics)

https://en.wikipedia.org/wiki/Group-based_cryptography

$\endgroup$
  • 5
    $\begingroup$ This is quite a broad question. Basically, every time you choose a group where the required hard problem is not hard, then you will run into problem. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a generator. Then given $g$, $y$ and you have to find the discrete logarithm $y\equiv xg \pmod(n)$, you can efficiently solve this linear congruence using Euclid (so the discrete log problem is easy and thus every discrete log based cryptosystem will be insecure here). $\endgroup$ – DrLecter Nov 11 '13 at 9:32
  • 1
    $\begingroup$ Thanks. This was something I was searching for. If you could just post it as answer I would gladly accept it. $\endgroup$ – TheRookierLearner Nov 11 '13 at 18:18
8
$\begingroup$

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 generator. Then the discrete logarithm problem in this group is given $g$, $y$ you have to find the discrete logarithm $x=\log_g(y)$, i.e., compute $x$ such that $y\equiv xg \pmod n$. However, you can efficiently solve this linear congruence by using Euclid.

Consequently, the discrete logarithm problem in the group $(Z_n,+)$ is easy and thus every discrete logarithm based cryptosystem will be insecure in this setting.

$\endgroup$
  • 2
    $\begingroup$ I guess if the problem is hard, but the group is too small you would run into problems as well. Using any asymmetric primitive with a strength of 10 bits is probably not a good idea... $\endgroup$ – Maarten - reinstate Monica Nov 11 '13 at 19:29
  • $\begingroup$ @owlstead Yes, thats clearly true. I assumed that the problem instance is of appropriate size and made an edit. $\endgroup$ – DrLecter Nov 11 '13 at 19:38
7
$\begingroup$

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 adversary can use Pohlig-Hellman to recover a secret key and compute the shared secret.

This can be remediated by using a Sophie Germain prime as the modulus - i.e. finding a prime $p$ such that $q = 2p+1$ is also prime. Using $q$ as the modulus ensures that the order of the group is not smooth, thus precluding the use of Pohlig-Hellman.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.