[Cryptography] Questions about crypto that lay people want to understand

[Arnold Reinhold]

On Sat, 19 Dec 2015 11:22 Henry Baker asked:

> In gathering material for a crypto talk to
> laypersons, I've been trying to collect a
> number of questions that such laypersons
> would like to know the answers to.
> 
> This talk is about the fundamental ideas
> of crypto, and not addressing details of
> HTTPS, so it's not a grown-up version of
> a "crypto party".
> 
> I have my own ideas for answers to some
> of these questions, but I'd be curious as
> to what others on this list think.
> 
> BTW, some of these questions will stump
> the best experts, but people will ask
> anyway!

Here are my attempts to answer your questions. But I would strongly recommend reading A History of U.S. Communications Security; the David G. Boak Lectures, National Security Agency (NSA), Volumes I, 1973, Volumes II 1981, partially released 2008, with additional portions declassified October 14, 2015 (http://www.governmentattic.org/18docs/Hist_US_COMSEC_Boak_NSA_1973u.pdf). It was recently mentioned on this list. It is from the horse’s mouth, informative and very well written. 

> 
> [These questions are in no particular
> order.]
> 
> * Ordinary citizens lived thousands of
> years in sophisticated societies and
> never needed clever crypto.  I don't
> recall any crypto in the Bible, and the
> only discussion of crypto in novels
> seems to occur in the context of war
> or high politics -- e.g., Queen Mary
> of Scots.
> 

There is crypto in the Bible: Several words in Jeremiah are coded in the AtBash cipher, the Hebrew version of the A->Z, B->Y, … substitution cipher. See https://en.wikipedia.org/wiki/History_of_cryptography for more on ancient uses. Crypto was a secret art reserved for the powerful in most places.

> Why now?  What is it about modern
> society that seems to require crypto
> for us ordinary citizens?

There was really very little crypto technology available to the public before the introduction of DES in 1977. The Boak lectures discuss this at length, see Volume II  p. 27 ff. Telephones were the only electronic communication system in common use until the last two decades. Now much of our lives are carried out electronically and our cell phones are filled with private information.  

> 
> * We just had a crypto war in the
> 1990's, and everyone thought the
> problem was solved.  Why are we
> having another crypto war 20 years
> later?  Is this a generational
> phenomenon?  Or is this a periodic
> cicada phenomenon?  Will there be
> a quantum crypto war in 2035 ?

I believe the forces on the restrictive side of the crypto wars were never reconciled to their loss back then. Any terrorist crisis becomes an excuse to reopen the question. In addition, improved security by Apple and to a lesser extent Google, has made strong encryption a default behavior. 

I’m skeptical about quantum cryptography and I certainly don’t see it filtering down to the general public by 2035 or ever. And I would not trust it in any case because it is too hard to audit.

> 
> * Why the intimate connection
> between crypto and randomness?
> This connection seems very odd,
> since encrypted text must be
> capable of being *decrypted* back
> into plaintext, and therefore
> even seemingly random ciphertext
> must have significant structure.

Ciphers do not create secrets, instead they allow a small secret (a key) to protect a much larger amount of information. That key does not have to be random, a good passphrase can be an effective key, for example, but random quantities are the most efficient secrets, since they lack any structure. There are also situations in public key cryptography where it is important that a number used in an algorithm, while not secret, never be used twice. By using long, truly random numbers, the likelihood of a repetition is very small.

> 
> * SW/HW engineers and crypto
> folks both use the word "code" to
> indicate that some additional
> structure has been added to
> ordinary ASCII text in order to
> achieve certain goals -- e.g.,
> error detection, error correction,
> confidentiality, integrity.  Are
> these uses of "code" indicative
> of any deeper relationship between
> the different fields?

The word “code" in English has many loosely related meanings, most of which do not involve any secrecy. One meaning is just a reversible correspondence between two sets of symbols, e.g. ASCII converting letters and numbers into binary patterns or a legal code that matches citation strings like 18USC703 with paragraphs of text. 

> 
> * What is the relationship
> between the "key" in my pocket
> and a crypto "key” ?

Typical keys to mechanical locks have a series of bumps and depressions on them. When inserted into the lock, these push up tiny pins to different heights. Those pins are split into two parts. When all the splits line up at the right level, the lock cylinder can turn. The heights for each pin can be (and are) assigned a number and the sequence of those numbers works just like a cryptographic key.

> 
> * Crypto techniques seem to
> involve *cycles* -- e.g. modular
> arithmetic, etc.  Why do cyclic
> and circular things keep showing
> up in crypto ?

Encryption must be reversible to be useful. An operation that transforms a set of symbols in a reversible way is an example of a mathematical group, and cryptography makes use of different groups to create very complicated transformations. Cyclic operations are simple examples of groups, but they are not the only types of groups used. 

> 
> * (For the physicist/EE.) What
> is the relationship between
> "information" in "information
> theory" and "quantum theory" ?
> Why the complete disconnect
> between the quantum world and
> information theory/crypto ?

Information theory and crypto are closely tied to a different branch of physics, thermodynamics.  The notion of entropy, first discovered in the theoretical analysis of 19th century steam engines, is directly applicable. The formula on the headstone of the great thermodynamicist Ludwig Boltzmann is in everyday use in understanding cryptographic security.

> 
> * Why are some things hard to
> compute?  Can't we just get
> the cleverest people from MIT,
> Stanford, (insert your favorite
> here) to work on this?  If we
> can build an H-bomb, make it
> to the Moon and back, and
> translate languages (thank
> you, Google!), what's the
> matter with you guys?

It’s a good question. The difficulty of certain problems is accepted in cryptography based on long failure to make progress against those problems, not any mathematical proof. There is a nice section on NSA’s 1981 opinion of then relatively new public key cryptography in Volume II of the Boak Lectures, p. 33: "We did not leap to its adoption for a variety of a reason. Foremost, we were uncertain of its security potential. The fact that mathematicians bad not yet found a way to factor large numbers did not mean that there was no way.  It was an interesting mathematical puzzle, first put forward centuries ago. but with no great incentives for its solution beyond the satisfaction of intellectual curiosity, no perceived commercial applications, and so on. So there was no evidence of a great many brains having worked· the problem over the years;…” 

Since then commercial applications abound and many more great brains have worked on the problem and NSA now uses public key crypto but not RSA, but there are still no proofs. Unfortunately (in my opinion) too many mathematicians direct their efforts to a theory of complexity that uses the language of cryptography, has little or nothing to do with practical cryptography (e.g. the P vs NP problem).

> 
> * If HTTPS is good enough for
> my bank account, how come I
> can't use it to vote?  Why
> do I have to vote in person?

Some here would question your premise that HTTPS is good enough for banking. There are additional protections for your bank account, including the ability to trace and reverse fraudulent transactions and legal limits (in the U.S. at least) to your losses in case of provable theft. The security track record of electronic voting has not been good and the desire to have a system that is both audit-able and preserves the secret ballot is a big technological challenge. Finally not every one in the political world wants voting to be easy. 

> 
> * Speaking of banking, will
> digital currency replace
> paper money?

I’ll leave this one to others.

> 
> * What is "strong" crypto?
> Some products say that they
> use "government quality"
> crypto.  Will I be twice as
> safe with 2048-bit keys as
> with 1024-bit keys?
> 

I would define strong crypto as systems that encrypt using algorithms for which there is no know way to to decrypt without knowing the key or at least a large portion of it. For systems that use completely random strings of bits as keys, such as symmetric ciphers, adding one bit doubles the systems security against ordinary decryption means. Two bits are thought to be needed to double strength against theoretical quantum computers. 

When 1024-bit keys 2048-bit keys are mentioned they are usually for public key cryptography and thus are not random quantities, but have considerable structure, e.g. a 1024 bit RSA key is typically the product of two 512-bit prime numbers. Doubling the length of such keys does much more that double their strength. In 2003 RSA Security claimed that 1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, and 2048-bit RSA keys to 112-bit symmetric keys. If that analysis still holds true, then 2048-bit RSA keys are 2^32 time stronger that 1024-bit RSA keys, or about 4 billion times harder to crack.

Hope this helps,

Arnold Reinhold