Slashdot Mirror

← Back to Stories (view on slashdot.org)

Exploring Diffie-Hellman Encryption

Posted by michael on from the DIY dept.

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.'"

4 of 20 comments (clear)

  1. Re:Alice and Bob by emag · · Score: 3, Informative

    Alice, Bob, Eve, etc are all just the traditional names to use to make crypto examples more real. If I had the energy, I'd pull out Applied Cryptography or some other crypto texts, and give a more definitive list.

    It's also usually that Alice and Bob are trying to carry on a relationship, and jealous Eve is trying to mess things up...

    --
    "The urge to save humanity is almost always a false front for the urge to rule." --H.L. Mencken
  2. A few problems... by karlm · · Score: 5, Informative
    Diffie-Hellman is great. SSH2 uses Diffie-Hellman with digital signatures to prevent a "man-in-the-middle" attack. That being said, this article made some goofs. I understand that they were just trying to show off bc's MP arithmatic. However, it just gets a little old to see poorly implemented crypto as the standard way to show off MP arthmatic. Don't get me wrong, I have Applied Crypto on my night stand and all, but it would be nice to see an arbitrary binomial expansion program or a program to search for Merseme primes. Maybe just a nice Miller-Rabin primality tester or a Blum-Blum-Shub pseudorandom number generator.

    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.

    --
    Copyright Violation:"theft, piracy"::Anti-Trust Violation:"thermonuclear price terrorism"<-Overly dramatic language.
    1. Re:A few problems... by Anonymous Coward · · Score: 1, Informative

      This is very weird.

      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.

  3. Re:Alice and Bob by keesh · · Score: 4, Informative

    From Applied Cryptography:

    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