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:
$\begingroup$
$\endgroup$
2
asked Nov 11, 2013 at 5:07
-
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$– DrLecterNov 11, 2013 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$– TheRookierLearnerNov 11, 2013 at 18:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
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 Bodewes ♦Nov 11, 2013 at 19:29
-
$\begingroup$ @owlstead Yes, thats clearly true. I assumed that the problem instance is of appropriate size and made an edit. $\endgroup$– DrLecterNov 11, 2013 at 19:38
$\begingroup$
$\endgroup$
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.
