Exploring Diffie-Hellman Encryption 20
damaru writes "Linux Journal is running a story on Diffie Hellman encryption, implemented using bc. The article says, 'The GNU bc threaded code compiler, included with most Linux distributions, provides arbitrary precision arithmetic that can handle the large numbers used in modern cryptography.'"
Re:What's next? (Score:1)
:)
Re:What's next? (Score:1)
Re:What's next? (Score:1)
Alice and Bob (Score:3, Funny)
Adam, Andy, Aaron, Alishia, Amy, etc.
Ben, Betty, Bronwin, etc.
WHY???
Re:Alice and Bob (Score:3, Informative)
It's also usually that Alice and Bob are trying to carry on a relationship, and jealous Eve is trying to mess things up...
Re:Alice and Bob (Score:4, Informative)
Alice: First participant in all the protocols
Bob: Second participant in all the protocols
Carol: Participant in the three- and four-way protocols
Dave: Participant in the four-way protocols
Eve: Eavesdropper
Mallory: Malicious active attacker
Trent: Trusted arbitrator
Walter: Warden; he'll be guarding Alice and Bob in some protocols
Peggy: Prover
Victor: Verifier
Re:Alice and Bob (Score:1)
Dave: Participant in the four-way protocols
You forgot:
Frank: Filmer of all participants in three- and four-way scenes
Re:Alice and Bob (Score:1)
A few problems... (Score:5, Informative)
The public number "n" they refer to should be a generator mod q. Primality does not guarantee that n is a generator mod q.
They mention needing to use larger numbers, but they don't scale it up enough. q should be at least 1024 bits, which is a little more than 16e306, which looks like a couple of lines of digits. The secret parameters xa and xb should be at least 64 bits, more safely 128 or 256 bits. Luckily, as long as xa and xb are large enough, the generator (n) can be pretty small. 2 often works as a generator. (I think the eassiest test for n bein a generator is for each prime factor p of (q-1), n ^((q-1)/p) % q != 1.) One of the main reasons you want (q-1)/2 to be prime is that it makes testing candidate generators easy.
Also, Diffie-Hellman is not an encryption algorithm. It is a key agreement algorithm. Those numers they "sneaked past" Mallory (ka and kb) connot be predicted or controlled without actually calculating them. The whole point is that it's computationally infeasable to calculate discrete logarithms in a large finite field generated by modular arithmatic. If Bob gets ya and can feasably compute xb such that ka= kb = m for some chosen value m, then the whole crypto system is broken. Diffie-Hellman is great for generating shared secrets (usually used as crypto keys for encryption algorithms), but cannot be used directly for encryption itself. The simplest way to use Diffie-Hellman as part of an encryption algorithm is to generate a shared one-time-pad that is xor'd with the plaintext. The ElGamal encryption algorithm does basically this, the only differece is that it uses modular multiplication instead of xor'ing to do the encryption once it has the shared one-time-pad.
Re:A few problems... (Score:1)
Re:A few problems... (Score:1, Informative)
You give a very elucidating description of some of the issues surrounding the Diffie-Hellman key agreement protocol, which makes me tend to think that you're pretty well studied on the matter. You even mention (indirectly) the benefits of using Sophie Germain (a.k.a. "safe") primes as moduli.
And then you go and say that 2 often works as a generator.
Unfortunately, this is not the case. Remember that, for the group Z_N (integers mod N, for some integer N), a generator is a number that is relatively prime to phi(N) == N - 1.
Since Diffie-Hellman usually uses Sophie Germain primes, phi(N) will take the form 2K for some prime integer K. And 2K is divisible by 2.
So, for any Sophie Germain prime, 2 is not a real generator (it will generate about 1/2 of the group, which is still very impressive and maybe still secure, but it will not generate all the elements of the group Z_N.).
Most implementations that I've seen basically have a "default generator"-- a small prime larger than 2. In the case of Sophie Germain primes, it's guaranteed to be relatively prime to phi(N). The most common value I see is 65537, but I've also seen 13, 17, and 127.
Also, the exponents used by Alice and Bob should be more than just 128 or 256 bits long; there are various attacks detailed in the literature against short exponents and some other similar mistakes.
Key Exchange for Session Management (Score:1)
Lets say that we are implementing a DH Key exchange program for a client server program. One could improve the basic key exchange by manipulating either "q" or "n" in the basic equation. Instead of having to communicate either one "in the clear" we could use some information which is readily available to both, say a timestamp at both ends. Naturally, this implies that both the client and the server are time aligned. Given that prolification of GPS and the veritable NTP this shouldn't be too hard. Plus, a server with multiple clients would have different keys.
Eve may have a 100 computers working in parallel but if the key exchange takes place periodically then it will be computationally improbable for Eve to reuse any old key. The periodicity can be set by the server for each client randomly on the secure channel. In addition, for eve to get to every single channel, recalculation will be required for each and every client.
I believe a similar mechanism is used in Cellular Networks to authenticate Mobile Phones.
bc? A compiler? Huh? (Score:2)
Huh? The bc I know is definitely an interpreter, not a compiler. Threaded code?
Is this something different? Or am I supposed to not take these technical articles literally?
Diffie-Hellman is NOT an encryption method! (Score:2, Interesting)
The Diffie-Hellman Key Transfer Algorithm (which I have printed on a T-shirt in nicely colored blocks) is NOT an encryption method, although it is used during protocol negotiations when preparing for encrypted communication across an untrusted network.