An Introduction to Cryptography
May 30, 2012 9:40 PM Subscribe
Journey into Cryptography is a multipart video introduction to the subject for beginners, created by Brit Cruise and hosted by Khan Academy. There are several interactive tools to help explain some key concepts. Also, a recent lecture entitled "Principles of Security" was given by noted Javascript curmudgeon Douglas Crockford, focusing on security and the web, with a detour into Volapük.
NYY PBZZRAGF VA GUVF GUERNQ FUBHYQ OR RAPBQRQ VA EBG 13, ORPNHFR ABG RIRA GUR AFN XABJF UBJ GB PENPX GUNG PBQR.
posted by twoleftfeet at 10:56 PM on May 30, 2012
posted by twoleftfeet at 10:56 PM on May 30, 2012
Bxnl, ohg jr'yy nccyl vg gjvpr, whfg gb or fnsr.
posted by benito.strauss at 11:18 PM on May 30, 2012
posted by benito.strauss at 11:18 PM on May 30, 2012
GUNG WHFG TVIRF LBH EBG 0, JUVPU VF ABG N ERYVNOYR PVCURE
posted by twoleftfeet at 11:20 PM on May 30, 2012
posted by twoleftfeet at 11:20 PM on May 30, 2012
Fvzba Fvatu’f Gur Pbqr Obbx vf nabgure jbegujuvyr bireivrj, sbe gubfr jub cersre gb ernq.
sgsl, zvthefxv :)
posted by hot_monster at 12:05 AM on May 31, 2012
sgsl, zvthefxv :)
posted by hot_monster at 12:05 AM on May 31, 2012
V QBA'G XABJ NOBHG LBH, OHG ZL FCRYY PURPXRE VF TBVAT PENML
posted by twoleftfeet at 12:23 AM on May 31, 2012 [1 favorite]
posted by twoleftfeet at 12:23 AM on May 31, 2012 [1 favorite]
It's a shame that they stop with DH key exchange. A similar but much more commonly used algorithm is RSA. It forms the basis for things like code signing that allows Apple to enforce what applications may run on an iPhone, as well as TLS which is used to implement "https:" URLs that secure web traffic from eavesdropping, such as when you do online banking. And it's not that hard to grasp, at least in principle.
For example, here's a 309 digit number, split into three lines so as not to cause your browser to horizontally scroll:
This 309 digit number (let's call it "n") is the result of multiplying two 155 digit prime factors which we'll call "p" and "q". And it's not just any number, it's the modulus of one of the Verisign root certificates. It was issued on 1996-01-28, and will expire on 2028-08-01. From this extremely long lifetime we can infer that this is a very important certificate, because generally the lifetime corresponds with how much pain will result when it expires or needs to be replaced. This is a root certificate because it's at the top of the chain: it is used to sign or vouch for other certificates, but nothing vouches for this one; its authenticity must be taken on faith. It therefore must be bundled or included with all software that speaks TLS (nee SSL), which explains why changing it would generally be painful.
If you could find either p or q (the 155 digit factors of that number), you would have vast power. You could generate and sign certificates for any website, which means you could interpose yourself between a user and that site and read their traffic or censor their content, and there would be no way for them to tell. I'm sure repressive regimes would kill for such power -- it's like a master key, and it's deceptively simple: here's a number, now just figure out the two numbers that were multiplied together to produce it. Actually doing this is quite another matter. By the prime number theorem, we have about 2512 / log(2512) ≈ 3.8 × 10151 prime divisors to test. Suppose we had a computer that can perform such a test division in a single clock cycle, and say that it runs at 100 GHz. Say that we have 100 billion such computers on the planet, and heck, say we have 100 billion such planets. You're still looking at ≈ 6 × 10110 years on average to find the answer; not even close to realistic. Of course, there are probably much more sophisticated ways of factoring that number, but it's still going to be computationally futile, and that's the point. Some root certificates use 2048 bit keys (such as Apple), or even 4096 bit keys. The time required to brute-force one of those is so large it's not even worth calculating.
As a side note, if you were lucky enough to factor the number and you decided to become evil, eventually someone would probably spot the forgery, and the appropriate certificate authorities would be contacted. There is a protocol for revoking certificates which would be followed. In theory, software that speaks TLS is supposed to regularly consult these revocation lists before trusting a certificate to ensure that it has not been revoked. But this requires an online lookup, which means it will fail if access to the revocation servers is blocked by that same repressive regime that is intercepting its users' traffic. Browsers have a bad track record of simply ignoring revocation check failures, since even normal network gremlins can cause a failure that makes it seem like the destination site is unreachable when really it's the revocation servers that are unreachable. (Here's Chrome developers announcing that they're removing online revocation checks entirely and instead using a cached list of revoked certs regularly updated from the mothership.) In general, since certificate revocations happen so infrequently, a real revocation is not often tested, and software has been historically poor in dealing with this circumstance.
The Wikipedia article on RSA gives a reasonable summary of how the algorithm actually works. I've intentionally used the same names for n, p, and q. The exponent e is 65537 by definition. If we know p and q we can easily calculate d, the private key, which is probably stored in some vault deep in the bowels of Verisign. (They likely use these root certificates only on special occasions to sign sub-certificates that are actually used for everyday signing.) Note that in the case of code signing and TLS, RSA is not actually used for encryption but rather signing. To create a digital signature, take the hash of the certificate or executable (call it "s") and compute sd mod n. To verify the signature, calculate se mod n. If equal, the signature is valid, and this check for authenticity only needed the signature s, the exponent e, and the public modulus n.
posted by Rhomboid at 2:02 AM on May 31, 2012 [39 favorites]
For example, here's a 309 digit number, split into three lines so as not to cause your browser to horizontally scroll:
1414003220445505168651733717730245848798996096446189276423753426333490573009604000372323349247010467812I like to write it in decimal (base 10) just so that it feels tangible since that's what we're intuitively used to dealing with, but normally it's written in base 16 (hexadecimal) where it has 256 digits. One hexadecimal digit represents four binary digits, so if written in base 2 (binary) this number would have 1024 digits.
9876507706177038315164623421917999077204720004583781782158248353254979130458806462408304053853419030157
1832597441704620988055765289140138246856927863523873759538652326729606982847841094220861282830980236711
This 309 digit number (let's call it "n") is the result of multiplying two 155 digit prime factors which we'll call "p" and "q". And it's not just any number, it's the modulus of one of the Verisign root certificates. It was issued on 1996-01-28, and will expire on 2028-08-01. From this extremely long lifetime we can infer that this is a very important certificate, because generally the lifetime corresponds with how much pain will result when it expires or needs to be replaced. This is a root certificate because it's at the top of the chain: it is used to sign or vouch for other certificates, but nothing vouches for this one; its authenticity must be taken on faith. It therefore must be bundled or included with all software that speaks TLS (nee SSL), which explains why changing it would generally be painful.
If you could find either p or q (the 155 digit factors of that number), you would have vast power. You could generate and sign certificates for any website, which means you could interpose yourself between a user and that site and read their traffic or censor their content, and there would be no way for them to tell. I'm sure repressive regimes would kill for such power -- it's like a master key, and it's deceptively simple: here's a number, now just figure out the two numbers that were multiplied together to produce it. Actually doing this is quite another matter. By the prime number theorem, we have about 2512 / log(2512) ≈ 3.8 × 10151 prime divisors to test. Suppose we had a computer that can perform such a test division in a single clock cycle, and say that it runs at 100 GHz. Say that we have 100 billion such computers on the planet, and heck, say we have 100 billion such planets. You're still looking at ≈ 6 × 10110 years on average to find the answer; not even close to realistic. Of course, there are probably much more sophisticated ways of factoring that number, but it's still going to be computationally futile, and that's the point. Some root certificates use 2048 bit keys (such as Apple), or even 4096 bit keys. The time required to brute-force one of those is so large it's not even worth calculating.
As a side note, if you were lucky enough to factor the number and you decided to become evil, eventually someone would probably spot the forgery, and the appropriate certificate authorities would be contacted. There is a protocol for revoking certificates which would be followed. In theory, software that speaks TLS is supposed to regularly consult these revocation lists before trusting a certificate to ensure that it has not been revoked. But this requires an online lookup, which means it will fail if access to the revocation servers is blocked by that same repressive regime that is intercepting its users' traffic. Browsers have a bad track record of simply ignoring revocation check failures, since even normal network gremlins can cause a failure that makes it seem like the destination site is unreachable when really it's the revocation servers that are unreachable. (Here's Chrome developers announcing that they're removing online revocation checks entirely and instead using a cached list of revoked certs regularly updated from the mothership.) In general, since certificate revocations happen so infrequently, a real revocation is not often tested, and software has been historically poor in dealing with this circumstance.
The Wikipedia article on RSA gives a reasonable summary of how the algorithm actually works. I've intentionally used the same names for n, p, and q. The exponent e is 65537 by definition. If we know p and q we can easily calculate d, the private key, which is probably stored in some vault deep in the bowels of Verisign. (They likely use these root certificates only on special occasions to sign sub-certificates that are actually used for everyday signing.) Note that in the case of code signing and TLS, RSA is not actually used for encryption but rather signing. To create a digital signature, take the hash of the certificate or executable (call it "s") and compute sd mod n. To verify the signature, calculate se mod n. If equal, the signature is valid, and this check for authenticity only needed the signature s, the exponent e, and the public modulus n.
posted by Rhomboid at 2:02 AM on May 31, 2012 [39 favorites]
That's a great comment, Rhomboid, and I'm very glad you didn't encode it in Rot 13!
posted by twoleftfeet at 2:24 AM on May 31, 2012 [1 favorite]
posted by twoleftfeet at 2:24 AM on May 31, 2012 [1 favorite]
Ah, I should have noted in the post that it appears the series is ongoing, so hopefully there will be additional topics added in the near future.
posted by gwint at 6:36 AM on May 31, 2012
posted by gwint at 6:36 AM on May 31, 2012
The company I work for, Galois, has developed a domain-specific language for cryptography called Cryptol. It's been used in education (you can use it to solve Sudoku puzzles), as well as for verifying implementations of cryptographic algorithms.
posted by dylanjames at 8:28 AM on June 1, 2012 [1 favorite]
posted by dylanjames at 8:28 AM on June 1, 2012 [1 favorite]
Move Over, Quantum Cryptography: Classical Physics Can Be Unbreakable Too
I must read this one more carefully to believe it since random number generation is often the biggest security hole anyways.
posted by jeffburdges at 9:49 AM on June 16, 2012
I must read this one more carefully to believe it since random number generation is often the biggest security hole anyways.
posted by jeffburdges at 9:49 AM on June 16, 2012
« Older The Great Taliban Jailbreak | "I will lead the attack!" Newer »
This thread has been archived and is closed to new comments
posted by migurski at 10:10 PM on May 30, 2012 [2 favorites]