home *** CD-ROM | disk | FTP | other *** search
/ The Hacker's Encyclopedia 1998 / hackers_encyclopedia.iso / pc / crypto / crypfq06.txt < prev    next >
Encoding:
Text File  |  2003-06-11  |  4.7 KB  |  102 lines
  1.  
  2. Archive-name: cryptography-faq/part06
  3.  
  4.  
  5. This is the sixth of ten parts of the sci.crypt FAQ. The parts are
  6. mostly independent, but you should read the first part before the rest.
  7. We don't have the time to send out missing parts by mail, so don't ask.
  8. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  9.  
  10.  
  11.  
  12. Contents:
  13.  
  14. 6.1. What is public-key cryptography?
  15. 6.2. What's RSA?
  16. 6.3. Is RSA secure?
  17. 6.4. How fast can people factor numbers?
  18. 6.5. What about other public-key cryptosystems?
  19.  
  20.  
  21. 6.1. What is public-key cryptography?
  22.  
  23.   In a classic cryptosystem, we have encryption functions E_K and
  24.   decryption functions D_K such that D_K(E_K(P)) = P for any plaintext
  25.   P. In a public-key cryptosystem, E_K can be easily computed from some
  26.   ``public key'' X which in turn is computed from K. X is published, so
  27.   that anyone can encrypt messages. If D_K cannot be easily computed
  28.   from X, then only the person who generated K can decrypt messages.
  29.   That's the essence of public-key cryptography, published by Diffie
  30.   and Hellman in 1976.
  31.  
  32.   In a classic cryptosystem, if you want your friends to be able to
  33.   send secret messages to you, you have to make sure nobody other than
  34.   them sees the key K. In a public-key cryptosystem, you just publish X,
  35.   and you don't have to worry about spies.
  36.  
  37.   This is only the beginning of public-key cryptography. There is an
  38.   extensive literature on security models for public-key cryptography,
  39.   applications of public-key cryptography, other applications of the
  40.   mathematical technology behind public-key cryptography, and so on.
  41.  
  42. 6.2. What's RSA?
  43.  
  44.   RSA is a public-key cryptosystem defined by Rivest, Shamir, and
  45.   Adleman. Here's a small example. See also [FTPDQ].
  46.  
  47.   Plaintexts are positive integers up to 2^{512}. Keys are quadruples
  48.   (p,q,e,d), with p a 256-bit prime number, q a 258-bit prime number,
  49.   and d and e large numbers with (de - 1) divisible by (p-1)(q-1). We
  50.   define E_K(P) = P^e mod pq, D_K(C) = C^d mod pq.
  51.  
  52.   Now E_K is easily computed from the pair (pq,e)---but, as far as
  53.   anyone knows, there is no easy way to compute D_K from the pair
  54.   (pq,e). So whoever generates K can publish (pq,e). Anyone can send a
  55.   secret message to him; he is the only one who can read the messages.
  56.  
  57. 6.3. Is RSA secure?
  58.  
  59.   Nobody knows. An obvious attack on RSA is to factor pq into p and q.
  60.   See below for comments on how fast state-of-the-art factorization
  61.   algorithms run. Unfortunately nobody has the slightest idea how to
  62.   prove that factorization---or any realistic problem at all, for that
  63.   matter---is inherently slow. It is easy to formalize what we mean by
  64.   ``RSA is/isn't strong''; but, as Hendrik W. Lenstra, Jr., says,
  65.   ``Exact definitions appear to be necessary only when one wishes to
  66.   prove that algorithms with certain properties do _not_ exist, and
  67.   theoretical computer science is notoriously lacking in such negative
  68.   results.''
  69.  
  70. 6.4. How fast can people factor numbers?
  71.  
  72.   It depends on the size of the numbers. In October 1992 Arjen Lenstra
  73.   and Dan Bernstein factored 2^523 - 1 into primes, using about three
  74.   weeks of MasPar time. (The MasPar is a 16384-processor SIMD machine;
  75.   each processor can add about 200000 integers per second.) The
  76.   algorithm there is called the ``number field sieve''; it is quite a
  77.   bit faster for special numbers like 2^523 - 1 than for general numbers
  78.   n, but it takes time only exp(O(log^{1/3} n log^{2/3} log n)) in any
  79.   case.
  80.  
  81.   An older and more popular method for smaller numbers is the ``multiple
  82.   polynomial quadratic sieve'', which takes time exp(O(log^{1/2} n
  83.   log^{1/2} log n))---faster than the number field sieve for small n,
  84.   but slower for large n. The breakeven point is somewhere between 100
  85.   and 150 digits, depending on the implementations.
  86.  
  87.   Factorization is a fast-moving field---the state of the art just a few
  88.   years ago was nowhere near as good as it is now. If no new methods are
  89.   developed, then 2048-bit RSA keys will always be safe from
  90.   factorization, but one can't predict the future. (Before the number
  91.   field sieve was found, many people conjectured that the quadratic
  92.   sieve was asymptotically as fast as any factoring method could be.)
  93.  
  94. 6.5. What about other public-key cryptosystems?
  95.  
  96.   We've talked about RSA because it's well known and easy to describe.
  97.   But there are lots of other public-key systems around, many of which
  98.   are faster than RSA or depend on problems more widely believed to be
  99.   difficult. This has been just a brief introduction; if you really want
  100.   to learn about the many facets of public-key cryptography, consult the
  101.   books and journal articles listed in part 10.
  102.