cryptography faq public key cryptography archive name cryptography faq part last modified faq for sci crypt part public key cryptography this is the sixth of ten parts of the sci crypt faq the parts are mostly independent but you should read the first part before the rest we don t have the time to send out missing parts by mail so don t ask notes such as kah refer to the reference list in the last part the sections of this faq are available via anonymous ftp to rtfm mit edu as pub usenet news answers cryptography faq part xx the cryptography faq is posted to the newsgroups sci crypt sci answers and news answers every days contents what is public key cryptography what s rsa is rsa secure how fast can people factor numbers what about other public key cryptosystems what is public key cryptography in a classic cryptosystem we have encryption functions e k and decryption functions d k such that d k e k p p for any plaintext p in a public key cryptosystem e k can be easily computed from some public key x which in turn is computed from k x is published so that anyone can encrypt messages if d k cannot be easily computed from x then only the person who generated k can decrypt messages that s the essence of public key cryptography published by diffie and hellman in in a classic cryptosystem if you want your friends to be able to send secret messages to you you have to make sure nobody other than them sees the key k in a public key cryptosystem you just publish x and you don t have to worry about spies this is only the beginning of public key cryptography there is an extensive literature on security models for public key cryptography applications of public key cryptography other applications of the mathematical technology behind public key cryptography and so on what s rsa rsa is a public key cryptosystem defined by rivest shamir and adleman for full details there is a faq available by ftp at rsa com here s a small example plaintexts are positive integers up to keys are quadruples p q e d with p a bit prime number q a bit prime number and d and e large numbers with de divisible by p q we define e k p p e mod pq d k c c d mod pq now e k is easily computed from the pair pq e but as far as anyone knows there is no easy way to compute d k from the pair pq e so whoever generates k can publish pq e anyone can send a secret message to him he is the only one who can read the messages is rsa secure nobody knows an obvious attack on rsa is to factor pq into p and q see below for comments on how fast state of the art factorization algorithms run unfortunately nobody has the slightest idea how to prove that factorization or any realistic problem at all for that matter is inherently slow it is easy to formalize what we mean by rsa is isn t strong but as hendrik w lenstra jr says exact definitions appear to be necessary only when one wishes to prove that algorithms with certain properties do not exist and theoretical computer science is notoriously lacking in such negative results how fast can people factor numbers it depends on the size of the numbers in october arjen lenstra and dan bernstein factored into primes using about three weeks of maspar time the maspar is a processor simd machine each processor can add about integers per second the algorithm there is called the number field sieve it is quite a bit faster for special numbers like than for general numbers n but it takes time only about exp o log n log log n in any case an older and more popular method for smaller numbers is the multiple polynomial quadratic sieve which takes time exp o log n log log n faster than the number field sieve for small n but slower for large n the breakeven point is somewhere between and digits depending on the implementations factorization is a fast moving field the state of the art just a few years ago was nowhere near as good as it is now if no new methods are developed then bit rsa keys will always be safe from factorization but one can t predict the future before the number field sieve was found many people conjectured that the quadratic sieve was asymptotically as fast as any factoring method could be what about other public key cryptosystems we ve talked about rsa because it s well known and easy to describe but there are lots of other public key systems around many of which are faster than rsa or depend on problems more widely believed to be difficult this has been just a brief introduction if you really want to learn about the many facets of public key cryptography consult the books and journal articles listed in part
