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

2 of 20 comments (clear)

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