cryptography faq basic cryptology archive name cryptography faq part last modified faq for sci crypt part basic cryptology this is the third 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 cryptology cryptography plaintext ciphertext encryption key what references can i start with to learn cryptology how does one go about cryptanalysis what is a brute force search and what is its cryptographic relevance what are some properties satisfied by every strong cryptosystem if a cryptosystem is theoretically unbreakable then is it guaranteed analysis proof in practice why are many people still using cryptosystems that are relatively easy to break what is cryptology cryptography plaintext ciphertext encryption key the story begins when julius caesar sent messages to his trusted acquaintances he didn t trust the messengers so he replaced every a by a c every b by a d and so on through the alphabet only someone who knew the shift by rule could decipher his messages a cryptosystem or cipher system is a method of disguising messages so that only certain people can see through the disguise cryptography is the art of creating and using cryptosystems cryptanalysis is the art of breaking cryptosystems seeing through the disguise even when you re not supposed to be able to cryptology is the study of both cryptography and cryptanalysis the original message is called a plaintext the disguised message is called a ciphertext encryption means any procedure to convert plaintext into ciphertext decryption means any procedure to convert ciphertext into plaintext a cryptosystem is usually a whole collection of algorithms the algorithms are labelled the labels are called keys for instance caesar probably used shift by n encryption for several different values of n it s natural to say that n is the key here the people who are supposed to be able to see through the disguise are called recipients other people are enemies opponents interlopers eavesdroppers or third parties what references can i start with to learn cryptology for an introduction to technical matter the survey articles given in part are the best place to begin as they are in general concise authored by competent people and well written however these articles are mostly concerned with cryptology as it has developed in the last years or so and are more abstract and mathematical than historical the codebreakers by kahn kah is encyclopedic in its history and technical detail of cryptology up to the mid s introductory cryptanalysis can be learned from gaines gai or sinkov sin this is recommended especially for people who want to devise their own encryption algorithms since it is a common mistake to try to make a system before knowing how to break one the selection of an algorithm for the des drew the attention of many public researchers to problems in cryptology consequently several textbooks and books to serve as texts have appeared the book of denning den gives a good introduction to a broad range of security including encryption algorithms database security access control and formal models of security similar comments apply to the books of price davies pri and pfleeger pfl the books of konheim kon and meyer matyas mey are quite technical books both konheim and meyer were directly involved in the development of des and both books give a thorough analysis of des konheim s book is quite mathematical with detailed analyses of many classical cryptosystems meyer and matyas concentrate on modern cryptographic methods especially pertaining to key management and the integration of security facilities into computer systems and networks the books of rueppel rue and koblitz kob concentrate on the application of number theory and algebra to cryptography how does one go about cryptanalysis classical cryptanalysis involves an interesting combination of analytical reasoning application of mathematical tools pattern finding patience determination and luck the best available textbooks on the subject are the military cryptanalytics series frie it is clear that proficiency in cryptanalysis is for the most part gained through the attempted solution of given systems such experience is considered so valuable that some of the cryptanalyses performed during wwii by the allies are still classified modern public key cryptanalysis may consist of factoring an integer or taking a discrete logarithm these are not the traditional fare of the cryptanalyst computational number theorists are some of the most successful cryptanalysts against public key systems what is a brute force search and what is its cryptographic relevance in a nutshell if f x y and you know y and can compute f you can find x by trying every possible x that s brute force search example say a cryptanalyst has found a plaintext and a corresponding ciphertext but doesn t know the key he can simply try encrypting the plaintext using each possible key until the ciphertext matches or decrypting the ciphertext to match the plaintext whichever is faster every well designed cryptosystem has such a large key space that this brute force search is impractical advances in technology sometimes change what is considered practical for example des which has been in use for over years now has or about possible keys a computation with this many operations was certainly unlikely for most users in the mid s the situation is very different today given the dramatic decrease in cost per processor operation massively parallel machines threaten the security of des against brute force search some scenarios are described by garron and outerbridge gar one phase of a more sophisticated cryptanalysis may involve a brute force search of some manageably small space of possibilities what are some properties satisfied by every strong cryptosystem the security of a strong system resides with the secrecy of the key rather than with an attempt to keep the algorithm itself secret a strong cryptosystem has a large keyspace as mentioned above the unicity distance is a measure which gives the minimum amount of ciphertext that must be intercepted to uniquely identify the key and if for some key the unicity distance is much longer than the amount of ciphertext you intend to encrypt under that key the system is probably strong a strong cryptosystem will certainly produce ciphertext which appears random to all standard statistical tests see for example cae a strong cryptosystem will resist all known previous attacks a system which has never been subjected to scrutiny is suspect if a system passes all the tests mentioned above is it necessarily strong certainly not many weak cryptosystems looked good at first however sometimes it is possible to show that a cryptosystem is strong by mathematical proof if joe can break this system then he can also solve the well known difficult problem of factoring integers see part failing that it s a crap shoot if a cryptosystem is theoretically unbreakable then is it guaranteed analysis proof in practice cryptanalytic methods include what is known as practical cryptanalysis the enemy doesn t have to just stare at your ciphertext until he figures out the plaintext for instance he might assume cribs stretches of probable plaintext if the crib is correct then he might be able to deduce the key and then decipher the rest of the message or he might exploit isologs the same plaintext enciphered in several cryptosystems or several keys thus he might obtain solutions even when cryptanalytic theory says he doesn t have a chance sometimes cryptosystems malfunction or are misused the one time pad for example loses all security if it is used more than once even chosen plaintext attacks where the enemy somehow feeds plaintext into the encryptor until he can deduce the key have been employed see kah why are many people still using cryptosystems that are relatively easy to break some don t know any better often amateurs think they can design secure systems and are not aware of what an expert cryptanalyst could do and sometimes there is insufficient motivation for anybody to invest the work needed to crack a system
