1
$\begingroup$

In general every public key cryptosystem ``has'' a probabilistic polynomial time algorithm $G$ such that $G(1^k)=(\textrm{public key}, \textrm{private key=trapdoor})$; $G$ is called the key generator. Now for the RSA cryptosystem the keys, can be found in the following way:

Bob decides the key length $k$, then $G(1^k)=((n,e), d)$ where $n=pq$ with $p$ and $q$ prime numbers, $n$ has length $k$ (as bit string), and $e\in\mathbb Z^\ast_{\phi(n)}$. The two primes $p$ and $q$ and are chosen in a random way, $\phi(n)$ is simply $(p-1)(q-1)$, $e\in\mathbb Z^\ast_{\phi(n)}$ is randomly chosen and finally $d$ is calculated in polynomial time with the extended Euclid algorithm. The couple $(n,e)$ is setted as the public key, whereas $d$ is the secret key.

I don't understand why this algorithm has probabilistic polynomial running time. Who ensures that I can find two random primes and $e$ in a reasonable time?

thanks in advance.

$\endgroup$
  • $\begingroup$ Basically, there are a lot of primes available to choose from. $\endgroup$ – Paŭlo Ebermann May 2 '14 at 20:12
  • $\begingroup$ Yes this is the intuition, but is there a formal proof aof this? $\endgroup$ – Dubious May 2 '14 at 20:23
  • $\begingroup$ jstor.org/stable/2371291 $\;$ $\endgroup$ – user991 May 2 '14 at 21:12
1
$\begingroup$

Short version: All the cool kids are using Randomized Algorithm !

Boring version:

  1. Any deterministic (part of a) crypto system can be broken ! [Goldwasser Micali]

  2. Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)

  3. Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)

$\endgroup$
  • 2
    $\begingroup$ "=" $\mapsto$ "$\approx$" $\;$ $\endgroup$ – user991 May 3 '14 at 5:15
  • $\begingroup$ yes, i could not find the latex code for that :P $\endgroup$ – Subhayan May 3 '14 at 8:35

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.