Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
5  
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). –  DrLecter Nov 11 '13 at 9:32
1  
Thanks. This was something I was searching for. If you could just post it as answer I would gladly accept it. –  TheRookierLearner Nov 11 '13 at 18:18

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
2  
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... –  owlstead Nov 11 '13 at 19:29
    
@owlstead Yes, thats clearly true. I assumed that the problem instance is of appropriate size and made an edit. –  DrLecter Nov 11 '13 at 19:38

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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