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
people
- 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
contribution?"
- 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
student.)
2.5.7. "I'm a newcomer to this stuff...how 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
example)...
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
Skipjack.
- 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
Hellman?"
+ 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
(grapeshot?).
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
bugs?"
- 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
published.
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.).
By Tim May, see README
HTML by Jonathan Rochkind