Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
MSNBC: "how code rebels saved your privacy"

By Signal 11 in MLP
Sun Jan 07, 2001 at 11:18:26 PM EST
Tags: Freedom (all tags)
Freedom

In a decidedly uncharacteristic shift by MSNBC and most US media outlets, they are running a story originally printed in Newsweek about cryptography and what it means to privacy. I'm... stunned. The article trumpets up Whitfield Diffie, who, if I remember my crypto correctly, was one of the people who created the key exchange protocols for PKI.


Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o story
o Also by Signal 11


Display: Sort:
MSNBC: "how code rebels saved your privacy" | 13 comments (8 topical, 5 editorial, 0 hidden)
Whitfield Diffie (4.00 / 3) (#6)
by Miniluv on Sun Jan 07, 2001 at 07:30:44 PM EST

Whitfield Diffie, along with Martin Hellman, rediscovered the potential for the use of one way algorithms to allow public key cryptography. This was initially discovered by a team of British mathematicians but was kept classified by the British government until after Diffie-Hellman presented their findings.

Public Key crypto didn't become a public reality until RSA was invented however, as it was the first public asymetric encryption scheme.

Just thought I'd clarify on who Diffie was, and what he accomplished. It's a pretty damn cool achievment, and he ought to be heralded along with a group of others who all helped move cryptography forward in a big way.

"Its like someone opened my mouth and stuck a fistful of herbs in it." - Tamio Kageyama, Iron Chef 'Battle Eggplant'

Diffie-Hellman was the real breakthrough (4.00 / 2) (#8)
by Paul Crowley on Mon Jan 08, 2001 at 05:06:35 AM EST

I've never quite understood why RSA is given the prominence it is in the history of crypto. The first asymmetric algorithm was Diffie-Hellman, which allows two parties to agree a shared secret without an eavesdropper being able to pick it up. Once you have that, it's easy to encrypt content for the remote end using the shared secret.

Now, there's no denying that each of R, S, and A are outstandingly brilliant people, and RSA was the first scheme that could be used for digital signatures and thus a massive breakthrough in itself (Taher ElGamal later extended D-H to digital signatures) but ultimately it was D-H's paper that was the nuclear strike against conventional thinking about cryptology.

RSA also introduced a new hard problem basis for PK: D-H is based on the difficulty of the discrete log problem, RSA on integer factoring, and these days pretty much all PK schemes that anyone still trusts are fundamentally based on one of these two problems.

(Hairsplit for those in the know: By DL I don't just mean DL over Z*p here)
--
Paul Crowley aka ciphergoth. Crypto and sex politics. Diary.
[ Parent ]
DH versus RSA (4.00 / 1) (#9)
by Miniluv on Mon Jan 08, 2001 at 06:04:24 AM EST

I'm not a serious cryptogeek, more of an amateur fan, but I always thought the Diffie-Hellman breakthrough was more in the nature of their thought experiment in discovering that you could use one way functions to encrypt and give out a public key to decrypt. They didn't themselves write an algorithm doing this, but instead RSA fit that bill.

As I said, I may in fact be mistaken, but that was always my understanding of the evolution of PK crypto.

"Its like someone opened my mouth and stuck a fistful of herbs in it." - Tamio Kageyama, Iron Chef 'Battle Eggplant'
[ Parent ]

Diffie-Hellman key agreement (5.00 / 1) (#10)
by Paul Crowley on Mon Jan 08, 2001 at 12:23:39 PM EST

That's certainly the way it's often presented ("The Code Book" gives the history you describe), but there's an important omission. And I am a *serious* cryptogeek, so just take what I say as gospel, OK?

Diffie and Hellman's seminal 1976 paper, "New Directions in Cryptography", didn't just talk in the abstract about the possibility that we may someday be able to arrange secret communication over insecure channels: it presented the first protocol, Diffie-Hellman. Here's how it works.

First, we choose a big prime p. This prime needs to have some nice properties, but it's not a secret; if an RFC specifies a protocol is to use D-H, it might just specify what value of p to use directly, and everyone participating uses the same p. All arithmetic takes place mod p, so where you see "g^x" think "g^x mod p". At the same time, we choose a number g, which is usually small, like 2 or 3. (technical note: g must be a generator of the group Z*p.)

Now, you and I want to communicate, so we generate random secrets; I generate x and you generate y. We then calculate and send each other g^x and g^y. Now, I calculate (g^y)^x, and you calculate (g^x)^y, and we end up with the same number, g^xy. We can then use this as a cryptographic key for a conventional cryptosystem like Triple-DES (or Rijndael, these days). The easiest way known for the attacker to find g^xy given only g^x and g^y is to find the "discrete log" of g^x, where x = log_g(k) iff g^x =k And today, discrete logs are a hard problem if p is big enough.

So it was this protocol that turned established thinking on its head. With this protocol, two parties start with no shared secret, communicate over a channel where the eavesdropper can hear everything, and end up with a secret they can use to build a secure channel and cut the eavesdropper out. The publication of RSA brought PK technology a huge bound forward: it gave us public/private keypairs you could encrypt and decrypt with directly (ie real trapdoor functions), digital signatures, and a new fundamental problem (integer factorisation) that can sit at the heart of a PK protocol. But the popular perception is that Diffie and Hellman plucked the idea that such a thing might be possible out of thin air, and it ain't so: they had already shown that such seemingly insoluble challenges could be solved.
--
Paul Crowley aka ciphergoth. Crypto and sex politics. Diary.
[ Parent ]
Quick replies (4.00 / 1) (#11)
by Miniluv on Mon Jan 08, 2001 at 03:57:38 PM EST

And I am a *serious* cryptogeek, so just take what I say as gospel, OK?
Of course not, I never take anything anyone says on K5 as Gospel without research. No disrespect intended but that would just be asinine, and if I did so I'd have all sorts of incredibly wrong facts parading through my skull.

I firmly intend to read Diffie and Hellman's paper, and I don't really doubt your presentation of the facts. I'm curious what you meant by:

But the popular perception is that Diffie and Hellman plucked the idea that such a thing might be possible out of thin air, and it ain't so: they had already shown that such seemingly insoluble challenges could be solved.
That seems to run in a circle, as the big deal was that Diffie and Hellman did in fact pluck the idea of PK out of thin air. RSA built on DH work by finding a new trapdoor type problem, but DH laid the public foundation. Or am I missing something else?

"Its like someone opened my mouth and stuck a fistful of herbs in it." - Tamio Kageyama, Iron Chef 'Battle Eggplant'
[ Parent ]
Re: Quick replies (4.50 / 2) (#12)
by Paul Crowley on Mon Jan 08, 2001 at 07:11:58 PM EST

Oops, the "gospel" remark was meant as a weak joke. Sorry.

I mean that D&H didn't just write "Wouldn't it be neat if we could get secure communication without shared secrets? All we need is encryption keys that come in pairs such that you can't work out the decryption key given the encryption key". They demonstrated that it was possible to get secure communication without shared secrets by describing the protocol that's now known as Diffie-Hellman.

I'd love to read the paper myself - if you find a copy online, do let me know. I don't have access to an academic library, so I have read very few papers that aren't available online. However, the RSA paper is available: http://theory.lcs.mit.edu/~rivest/rsapaper.ps
--
Paul Crowley aka ciphergoth. Crypto and sex politics. Diary.
[ Parent ]
RSA is simple (3.00 / 1) (#13)
by burris on Tue Jan 09, 2001 at 01:11:14 AM EST

The reason RSA is dominant over discrete log and elliptic based systems is the math is relatively simple and easy to understand/implement compared to other systems (of course, there are many gotchas associated with using the deceptively simple RSA algorithms). The maths for ElGamal, for instance, are more complicated. There are two seperate sets of algorithms for encryption/decryption and signing/verifying and both require generation of nonces that are relatively prime to p-1.

Burris
c = m^e mod n

[ Parent ]

Newsweek (4.00 / 1) (#7)
by DigDug on Mon Jan 08, 2001 at 03:18:48 AM EST

Just an FYI -- this is a Newsweek, not an MSNBC article. MSNBC just publishes all of the Newsweek articles.

--
Yavista - if you haven't found a nice homepage yet.

MSNBC: "how code rebels saved your privacy" | 13 comments (8 topical, 5 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!