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

20 comments

  1. What's next? by leviramsey · · Score: 0, Redundant

    RSA with your TI calculator?

    1. Re:What's next? by Louis_Wu · · Score: 0, Offtopic

      (Score:0, Redundant)
      Redundant? The second post?

      Maybe (Score:2, Funny), or even (Score:0, Silly). But (Score:0, Redundant)???

    2. Re:What's next? by Louis_Wu · · Score: 1
      And my post just got hit with "-1, Offtopic". I love /.

      :)

    3. Re:What's next? by danielsmc · · Score: 1

      I tried that with my TI-85, and almost got it working (although with very small key sizes.) It would have worked, except for the fact that the TI-85's mod() function is broken for large numbers. It might work with an 89, though. :P

    4. Re:What's next? by multiplexo · · Score: 1

      Goddamnit! This is brilliant and it just goes to show you how fucking cool UNIX/Linux is. I've been using bc for years for simple math problems and I never had any idea it could do stuff like this. Do you get tools such as bc with any version of Doze? Fuck no. Hell, I just ran these programs on my Mac with MacOS X, which has bc available from the command line. Damn! I love UNIX!

      --
      cheap labor conservatives - they want to keep you hungry enough to be thankful for minimum wage.
  2. Alright, by hexfortyfive · · Score: 0, Offtopic

    So, Internet Explorer and SSL into a bar...

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

    3. Re:Alice and Bob by the+way,+what're+you · · Score: 1
      Carol: Participant in the three- and four-way protocols
      Dave: Participant in the four-way protocols

      You forgot:

      Frank: Filmer of all participants in three- and four-way scenes

      --
      example.org - powered by Linux!
    4. Re:Alice and Bob by Beryllium+Sphere(tm) · · Score: 1

      It's a little known fact, but Dilbert's colleague Alice developed a desperate crush on Microsoft Bob, and they encrypted their correspondence to save both of them the embarrassment of being discovered.

  4. 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 Viol8 · · Score: 1

      Its just a wild guess but maybe theye didn't do any heavy crypto because that wasn't the point of the article and because only a small percentage of people could understand or would be interested in the maths behind it. I had enough trouble just following that "simple" stuff. "Blum-Blum-Shub" ?? You've gottta be kidding me!Sounds like something out of a Sesame Street nonsense rhyme.

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

  5. Good Read... by metacosm · · Score: 0, Offtopic

    I gotta say that I enjoyed this little post -- I thought it was a fun easy read -- and very interesting, fun to explore and tweak.

  6. Key Exchange for Session Management by hero_or_what · · 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.

    1. Re:Key Exchange for Session Management by Anonymous Coward · · Score: 0

      IIRC, When a cell phone moves into a cell operated by a new MSC (Mobile Switching Centre), the IMSI (International Mobile Station Identifier) is transmitted to the MSC in the clear.

      This then allows the MSC to lookup the mobile station information in the users HLR (Home Location Register).

      The MSC then stores this information, which includes the MSISDN (Mobile Station International Subscribe Dialling Number (or something like that)), and the Ki (which is 'hardcoded' into your SIM card), which can be used as part of a symmetric encryption algorithm (but usually actually isnt).

      Once the subscriber record has been loaded by the MSC into its VLR (Visitor Location Register), the MSC generates a TMSI (Temporary Mobile Station Identifier), which is used for subsequent communication between the MSC and the cell phone (or MS - Mobile Station)

      (this bit not too sure if i've got right)
      The MSC then encrypts a random string using the Ki, which it sends (in cleartext) to the cell phone, which also encrypts the string, using its copy of Ki, sending it back to the MSC.

      The MSC then compares the two (the one it computed, and the one it received), if they match, then the phone must be who it says it is, because the only two places that the key is stored is in the HLR, and the SIM card.

      Possibly the (Ki + random string) computation is done at the HLR, and not the VLR (so Ki is not sent across the network) but I can't remember..

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

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