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

6 of 20 comments (clear)

  1. Alice and Bob by droyad · · Score: 3, Funny

    Who are Alice and Bob and why on earth are they in every example of cryptography between two people? Are they some kind of cryptography god? I know they stand for A and B but you can have:
    Adam, Andy, Aaron, Alishia, Amy, etc.
    Ben, Betty, Bronwin, etc.

    WHY???

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

  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.
  3. bc? A compiler? Huh? by shoppa · · Score: 2
    The GNU bc threaded code compiler

    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?

  4. Diffie-Hellman is NOT an encryption method! by Ashurbanipal · · Score: 2, Interesting

    DH is the secure key transfer mechanism used by SSL and TLS (although TLS can theoretically use other methods, nobody does in practice).

    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.