Cyphernomicon Top
Cyphernomicon 2.5

MFAQ--Most Frequently Asked Questions:

    2.5.1. "Why is crypto so important?"
           + The three elements that are central to our modern view of
              liberty and privacy (a la Diffie)
             - protecting things against theft
             - proving who we say we are
             - expecting privacy in our conversations and writings
           - Although there is no explicit "right of privacy" enumerated
              in the U.S. Constitution, the assumption that an individual
              is to be secure in his papers, home, etc., absent a valid
              warrant, is central. (There has never been a ruling or law
              that persons have to speak in a language that is
              understandable by eavesdroppers, wiretappers, etc., nor has
              there ever been a rule banning private use of encrption. I
              mention this to remind readers of the long history of
              crypto freedom.)
           -  "Information, technology and control of both _is_ power.
              *Anonymous* telecommunications has the potential to be the
              greatest equalizer in history.  Bringing this power to as
              many as possible will forever change the discourse of power
              in this country (and the world)." [Matthew J Miszewski, ACT
              NOW!, 1993-03-06]
    2.5.2. "Who uses cryptography?"
           - Everybody, in one form or another. We see crypto all around
              us...the keys in our pockets, the signatures on our
              driver's licenses and other cards, the photo IDs, the
              credit cards. Lock combinations, door keys, PIN numbers,
              etc. All are part of crypto (although most might call this
              "security" and not a very mathematical thing, as
              cryptography is usually thought to be).
           - Whitticism: "those who regularly
              conspire to participate in the political process are
              already encrypting." [Whit Diffie]
    2.5.3. "Who needs crypto? What have they got to hide?"
           + honest people need crypto because there are dishonest
             - and there may be other needs for privacy
           - There are many reasons why people need privacy, the ability
              to keep some things secret. Financial, personal,
              psychological, social, and many other reasons.
           - Privacy in their papers, in their diaries, in their pesonal
              lives. In their financial choices, their investments, etc.
              (The IRS and tax authorities in other countries claim to
              have a right to see private records, and so far the courts
              have backed them up. I disagree.)
           - people encrypt for the same reason they close and lock
              their doors
           - Privacy in its most basic forms
    2.5.4. "I'm new to crypto--where should I start?"
           - books...Schneier
           - soda
           - sci.crypt
           - talk.politics.crypto
           - FAQs other than this one
    2.5.5. "Do I need to study cryptography and number theory to make a
           - Absolutely not! Most cryptographers and mathematicians are
              so busy doing their thing that they little time or interest
              for political and entrepreneurial activities.
              Specialization is for insects and researchers, as someone's
              .sig says.
           - Many areas are ripe for contribution. Modularization of
              functions means  people can concentrate in other areas,
              just as writers don't have to learn how to set type, or cut
              quill pens, or mix inks.
           - Nonspecialists should treat most established ciphers as
              "black boxes" that work as advertised. (I'm not saying they
              do, just that analysis of them is best left to experts...a
              little skepticism may not hurt, though).
    2.5.6. "How does public key cryptography work, simply put?"
           - Plenty of articles and textbooks describe this, in ever-
              increasing detail (they start out with the basics, then get
              to the juicy stuff).
           + I did find a simple explanation, with "toy numbers," from
              Matthew Ghio:
             - "You pick two prime numbers; for example 5 and 7.
                Multiply them together, equals 35.  Now you calculate the
                product of one less than each number, plus one.  (5-1)(7-
                1)+1=21.  There is a mathematical relationship that says
                that x = x^21 mod 35 for any x from 0 to 34.  Now you
                factor 21, yeilds 3 and 7.
                "You pick one of those numbers to be your private key and
                the other one is your public key.  So you have:
                Public key: 3
                Private key: 7
                "Someone encrypts a message for you by taking plaintext
                message m to make ciphertext message c:  c=m^3 mod 35
                "You decrypt c and find m using your private key: m=c^7
                mod 35
                "If the numbers are several hundred digits long (as in
                PGP), it is nearly impossible to guess the secret key."
                [Matthew Ghio, alt.anonymous, 1994-09-03]
             - (There's a math error here...exercise left for the
    2.5.7. "I'm a newcomer to this should I get started?"
           - Start by reading some of the material cited. Don't worry
              too much about understanding it all.
           - Follow the list.
           - Find an area that interests you and concentrate on that.
              There is no reason why privacy advocates need to understand
              Diffie-Hellman key exchange in detail!
           + More Information
             + Books
               - Schneier
               - Brassard
             + Journals, etc
               - Proceedings
               - Journal of Cryptology
               - Cryptologia
             - Newsgroups
             - ftp sites
    2.5.8. "Who are Alice and Bob?"
    2.5.9. "What is security through obscurity"?
           - adding layers of confusion, indirection
           - rarely is strong in a an infromation-theoretic or
              cryptographic sense
           - and may have "shortcuts" (like a knot that looks complex
              but which falls open if approached the right way)
           - encryption algorithms often hidden, sites hidden
           - Make no mistake about it, these approaches are often used.
              And they can add a little to the overall security (using
              file encyption programs like FolderBolt on top of PGP is an
   2.5.10. "Has DES been broken? And what about RSA?"
           - DES: Brute-force search of the keyspace in chosen-plaintext
              attacks is feeasible in around 2^47 keys, according to
              Biham and Shamir. This is about 2^9 times easier than the
              "raw" keyspace. Michael Wiener has estimated that a macine
              of special chips could crack DES this way for a few
              thousand dollars per key. The NSA may have such machines.
           - In any case, DES was not expected to last this long by many
              (and, in fact, the NSA and NIST proposed a phaseout some
              years back, the "CCEP" (Commercial COMSEC Endorsement
              Program), but it never caught on and seems forgotten today.
              Clipper and EES seem to have grabbed the spotlight.
           - IDEA, from Europe, is supposed to be much better.
           - As for RSA, this is unlikely. Factoring is not yet proven
              to be NP-co
   2.5.11. "Can the NSA Break Foo?"
           - DES, RSA, IDEA, etc.
           - Can the government break our ciphers?
   2.5.12. "Can brute-force methods break crypto systems?"
           - depends on the system, the keyspace, the ancillary
              information avialable, etc.
           - processing power generally has been doubling every 12-18
              months (Moore's Law), so....
           - Skipjack is 80 bits, which is probably safe from brute
              force attack for 2^24 = 1.68e7 times as long as DES is.
              With Wiener's estimate of 3.5 hours to break DES, this
              implies 6700 years using today's hardware. Assuming an
              optimistic doubling of hardware power per year (for the
              same cost), it will take 24 years before the hardware costs
              of a brute force attack on Skipjack come down to what it
              now costs to attack DES. Assuming no other weaknesses in
           - And note that intelligence agencies are able to spend much
              more than what Wiener calculated (recall Norm Hardy's
              description of Harvest)
   2.5.13. "Did the NSA know about public key ideas before Diffie and
           + much debate, and some sly and possibly misleading innuendo
             - Simmons claimed he learned of PK in Gardner's column, and
                he certainly should've been in a position to know
                (weapons, Sandia)
           + Inman has claimed that NSA had a P-K concept in 1966
             - fits with Dominik's point about sealed cryptosystem boxes
                with no way to load new keys
             - and consistent with NSA having essentially sole access to
                nation's top mathematicians (until Diffies and Hellmans
                foreswore government funding, as a result of the anti-
                Pentagon feelings of the 70s)
   2.5.14. "Did the NSA know about public-key approaches before Diffie
            and Hellman?"
           - comes up a lot, with some in the NSA trying to slyly
              suggest that _of course_ they knew about it...
           - Simmons, etc.
           - Bellovin comments (are good)
   2.5.15. "Can NSA crack RSA?"
           - Probably not.
           - Certainly not by "searching the keyspace," an idea that
              pops up every few months . It can't be done. 1024-bit keys
              implies roughly 512-bit primes, or 153-decimal digit
              primes. There are more than 10^150 of them! And only about
              10^73 particles in the entire universe.
           - Has the factoring problem been solved? Probably not. And it
              probably won't be, in the sense that factoring is probably
              in NP (though this has not been proved) and P is probably
              not NP (also unproved, but very strongly suspected). While
              there will be advances in factoring, it is extremely
              unlikely (in the religious sense) that factoring a 300-
              digit number will suddenly become "easy."
           - Does the RSA leak information so as to make it easier to
              crack than it is to factor the modulus? Suspected by some,
              but basically unknown. I would bet against it. But more
              iffy than the point above.
           + "How strong is strong crypto?"
             - Basically, stronger than any of the hokey "codes" so
                beloved of thriller writers and movie producers. Modern
                ciphers are not crackable by "telling the computer to run
                through all the combinations" (more precisely, the number
                of combinations greatly exceeds the number of atoms in
                the universe).
   2.5.16. "Won't more powerful computers make ciphers breakable?"
           + The effects of increasing computer power confer even
              *greater* advantage to the cipher user than to the cipher
              breaker. (Longer key lengths in RSA, for example, require
              polynomially more time to use, but exponentially more time
              to break, roughly speaking.) Stunningly, it is likely that
              we are close to being able to use key lengths which cannot
              be broken with all the computer power that will ever exist
              in the universe.
             + Analogous to impenetrable force fields protecting the
                data, with more energy required to "punch through" than
                exists in the universe
               - Vernor Vinge's "bobbles," in "The Peace War."
             - Here I am assuming that no short cuts to factoring
                exist...this is unproven, but suspected. (No major
                shortcuts, i.e., factoring is not "easy.")
             + A modulus of thousands of decimal digits may require more
                total "energy" to factor, using foreseeable approaches,
                than is available
               - reversible computation may help, but I suspect not much
               - Shor's quantum-mechanical approach is completely
                  untested...and may not scale well (e.g., it may be
                  marginally possible to get the measurement precision to
                  use this method for, say, 100-digit numbers, but
                  utterly impossible to get it for 120-digit numbers, let
                  alone 1000-digit numbers)
   2.5.17. "Will strong crypto help racists?"
           - Yes, this is a consequence of having secure virtual
              communities.  Free speech tends to work that way!
           - The Aryan Nation can use crypto to collect and disseminate
              information, even into "controlled" nations like Germany
              that ban groups like Aryan Nation.
           - Of course, "on the Internet no one knows you're a dog," so
              overt racism based on superficial external characteristics
              is correspondingly harder to pull off.
           - But strong crypto will enable and empower groups who have
              different beliefs than the local majority, and will allow
              them to bypass regional laws.
   2.5.18. Working on new ciphers--why it's not a Cypherpunks  priority
            (as I see it)
           - It's an issue of allocation of resources. ("All crypto is
              economics." E. Hughes) Much work has gone into cipher
              design, and the world seems to have several stable, robust
              ciphers to choose from. Any additional work by crypto
              amateurs--which most of us are, relative to professional
              mathematicians and cipher designers--is unlikely to move
              things forward significantly. Yes, it could happen...but
              it's not likely.
           + Whereas there are areas where professional cryptologists
              have done very little:
             - PGP (note that PRZ did *not* take time out to try to
                invent his own ciphers, at least not for Version
                2.0)...he concentrated on where his efforts would have
                the best payoff
             - implementation of remailers
             - issues involving shells and other tools for crypto use
             - digital cash
             - related issues, such as reputations, language design,
                game theory, etc.
           - These are the areas of "low-hanging fruit," the areas where
              the greatest bang for the buck lies, to mix some metaphors
   2.5.19. "Are there any unbreakable ciphers?"
           - One time pads are of course information-theoretically
              secure, i.e., unbreakable by computer power.
           + For conventional ciphers, including public key ciphers,
              some ciphers may not be breakable in _our_ universe, in any
              amount of time. The logic goes as follows:
             - Our universe presumably has some finite number of
                particles (currently estimated to be 10^73 particles).
                This leads to the "even if every particle were a Cray Y-
                MP it would take..." sorts of thought experiments.
                But I am considering _energy_ here. Ignoring reversible
                computation for the moment, computations dissipate energy
                (some disagree with this point). There is some uppper
                limit on how many basic computations could ever be done
                with the amount of free energy in the universe. (A rough
                calculation could be done by calculating the energy
                output of stars, stuff falling into black holes, etc.,
                and then assuming about kT per logical operation. This
                should be accurate to within a few orders of magnitude.)
                I haven't done this calculation, and won't here, but the
                result would likely be something along the lines of X
                joules of energy that could be harnessed for computation,
                resulting in Y basic primitive computational steps.
                I can then find a modulus of 3000 digits or 5000 digits,
                or whatever, that takes *more* than this number of steps
                to factor. Therefore, unbreakable in our universe.
           - Caveats:
              1. Maybe there are really shortcuts to factoring. Certainly
              improvements in factoring methods will continue. (But of
              course these improvements are not things that convert
              factoring into a less than exponential-in-length
              problem...that is, factoring appears to remain "hard.")
              2. Maybe reversible computations (a la Landauer, Bennett,
              et. al.) actually work. Maybe this means a "factoring
              machine" can be built which takes a fixed, or very slowly
              growing, amount of energy. In this case, "forever" means
              Lefty is probably right.
              3. Maybe the quantum-mechanical idea of Peter Shor is
              possible. (I doubt it, for various reasons.)
   2.5.20. "How safe is RSA?" "How safe is PGP?" "I heard that PGP has
           - This cloud of questions is surely the most common sort that
              appears in sci.crypt. It sometimes gets no answers,
              sometimes gets a rude answer, and only occasionally does it
              lead to a fruiful discussion.
           - The simple anwer: These ciphers appear to be safe, to have
              no obvious flaws.
           - More details can be found in various question elsewhere in
              this FAQ and in the various FAQs and references others have
   2.5.21. "How long does encryption have to be good for?"
           - This obviously depends on what you're encrypting. Some
              things need only be safe for short periods of time, e.g., a
              few years or even less. Other things may come back to haunt
              you--or get you thrown in prison--many years later. I can
              imagine secrets that have to be kept for many decades, even
              centuries (for example, one may fear one's descendents will
              pay the price for a secret revealed).
           - It is useful to think _now_ about the computer power likely
              to be available in the year 2050, when many of you reading
              this will still be around. (I'm _not_ arguing that
              parallelism, etc., will cause RSA to fall, only that some
              key lengths (e.g., 512-bit) may fall by then. Better be
              safe and use 1024 bits or even more. Increased computer
              power makes longer keys feasible, too.).

Next Page: 2.6 PGP
Previous Page: 2.4 Organizational

By Tim May, see README

HTML by Jonathan Rochkind