I read that Silver–Pohlig–Hellman algorithm solves the discrete logarithm with prime module $p$ in $O(\log^2(p))$ if $p-1$ is a smooth number. This seems pretty fatal for cryptography, since it is a polynomial over the key length, right?
So my questions are:
Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently.
However, the solution is pretty simple: Choose a safe prime as modulus: $p=2q+1$ (with $q$ prime), or a prime $p$ where $p-1$ contains at least one large factor, so that the BS-GS algorithm for this factor is too large (It has $\mathcal{O}(\sqrt{q})$ memory and time complexity for prime $q$).
For example this is done in DSA: Choose prime $q$ first, then calculate a prime $p$, where $p-1$ is a multiple of $q$. Examples for suggested key lengths $(|q|,|p|)$: (160,1024), (224,2048), (256,2048),...
edit:
To answer your first question: If you choose $p$ randomly, chances are high that your security is MUCH lower than you would expect:
For random $p$ , the chance of $p-1$ being divisible by a low prime $a$ is $\frac{1}{a-1}$. A random $p$ means that $(p-1)$ mod $a$ is uniform distributed in $[0,a-2]$.
Now, if $a$ is small, we can ignore the costs of the BS-GS algorithm for $a$, and you "loose" $\log_2{a}$ bits of security: The remaining problem doesn't have to be solved for group order $(p-1)$ but for $(p-1)/a$.
Since there are quite a lot of small prime numbers, you have a problem. Best to avoid this problem by choosing $p$ not totally random, but with $q$ large enough. (Choose q, calculate some $p$ and test them for primality).
