implementación de Diffie Hellman c #

5

Hola, todos,

Para un proyecto de prueba, he intentado implementar el (famoso) algoritmo Diffie Hellman para el intercambio seguro de claves.

Ahora he escrito esto en C #:

using System;
using System.Collections;
using System.Collections.Generic;

namespace DiffieHellman.Cryptology
{
    public static class CentralAuthority
    {
        private static readonly List<Int32> _primes = new List<Int32>();

        public static void CreatePrimeTable()
        {
            const Int32 topNumber = Int32.MaxValue / 2;
            BitArray numbers = new BitArray(topNumber, true);

            for (Int32 i = 2; i < topNumber; i++)
            {
                if (!numbers[i])
                    continue;

                for (Int32 j = i * 2; j < topNumber; j += i)
                    numbers[j] = false;
            }

            for (Int32 i = 1; i < topNumber; i++)
            {
                if (numbers[i])
                    _primes.Add(i);
            }
        }

        /// <summary>
        /// Generate a random Prime Number.
        /// </summary>
        public static Int32 GeneratePrime()
        {
            Int32 p = Randomizer.GetRandom(1, _primes.Count);
            return _primes[p];
        }

        /// <summary>
        /// Generate a random base integer (g) less than the prime
        /// </summary>
        public static Int32 GenerateBase(
            Int32 prime)
        {
            return Randomizer.GetRandom(1, prime - 1);
        }
    }
}




using System;

namespace DiffieHellman.Cryptology
{
    public class CaDiffieHellman
    {
        public Int64 Key { get; private set; }
        public Int32 Prime { get; private set; }
        public Int32 Generator { get; private set; }
        public Int64 ExponentiationY { get; private set; }
        private Int32 _privateX;

        public void GenerateParameters(
            Int32 prime = 0,
            Int32 generator = 0)
        {
            if (prime < 1 && generator < 1)
            {
                prime = CentralAuthority.GeneratePrime();
                generator = CentralAuthority.GenerateBase(prime);
            }

            if (prime <= generator - 1)
                return;

            Prime = prime;
            Generator = generator;
            _privateX = Randomizer.GetRandom(1, Prime - 1);

            Int64 xor = Generator ^ _privateX;
            while (xor > Prime - 1
                || xor == _privateX)
            {
                _privateX = Randomizer.GetRandom(1, Prime - 1);
                xor = Generator ^ _privateX;
            }

            ExponentiationY = (xor) % Prime;
        }

        public void GenerateKey(
            Int64 exponentiationYOther)
        {
            Key = (exponentiationYOther ^ _privateX) % Prime;
        }
    }
}



using System;
using System.Security.Cryptography;

namespace DiffieHellman.Cryptology
{
    public static class Randomizer
    {
        /// <summary>
        /// Real random generator
        /// Slower then Random().Next()!
        /// </summary>
        public static Int32 GetRandom(
            Int32 max)
        {
            return GetRandom(0, max);
        }

        /// <summary>
        /// Real random generator
        /// Slower than Random().Next()!
        /// </summary>
        public static Int32 GetRandom(
            Int32 min,
            Int32 max)
        {
            // Start a slower but more acurate randomizer service
            RNGCryptoServiceProvider rngCryptoServiceProvider = new RNGCryptoServiceProvider();
            Byte[] randomBytes = new Byte[4];
            rngCryptoServiceProvider.GetBytes(randomBytes);
            Int32 seed = BitConverter.ToInt32(randomBytes, 0);

            return new Random(seed).Next(min, max);
        }
    }
}


using System;
using System.Diagnostics;
using DiffieHellman.Cryptology;

namespace DiffieHellman
{
    public class Program
    {
        private static readonly CaDiffieHellman _caDiffieHellmanServer = new CaDiffieHellman();
        private static readonly CaDiffieHellman _caDiffieHellmanClient = new CaDiffieHellman();

        static void Main()
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            CentralAuthority.CreatePrimeTable();
            stopwatch.Stop();
            Console.WriteLine("Create Prime Table: {0}ms", stopwatch.ElapsedMilliseconds);

            stopwatch = Stopwatch.StartNew();
            for (Int32 i = 0; i < Int32.MaxValue; i++)
            {
                // Generate random prime and generator at server
                _caDiffieHellmanServer.GenerateParameters();

                // Send prime and generator to client
                _caDiffieHellmanClient.GenerateParameters(_caDiffieHellmanServer.Prime, _caDiffieHellmanServer.Generator);

                // Calculate the key
                _caDiffieHellmanServer.GenerateKey(_caDiffieHellmanClient.ExponentiationY);

                // Calculate the key
                _caDiffieHellmanClient.GenerateKey(_caDiffieHellmanServer.ExponentiationY);

                if (_caDiffieHellmanServer.Key != _caDiffieHellmanClient.Key)
                    Console.WriteLine("Error ({0}): wrong key", i);

                if (_caDiffieHellmanServer.Key == 0 || _caDiffieHellmanClient.Key == 0)
                    Console.WriteLine("Error ({0}): key 0", i);

                if (i % 10000 == 0)
                    Console.WriteLine("Progress: {0}, {1}ms, {2}", i, stopwatch.ElapsedMilliseconds, _caDiffieHellmanServer.Key);
            }
            stopwatch.Stop();
            Console.WriteLine("Loop: {0}ms", stopwatch.ElapsedMilliseconds);

            Console.ReadKey();
        }
    }
}

Ahora mi principal preocupación es que no usé la fórmula estándar: g pow (a) mod p = A, pero g XOR a mod p. El comando (a) no funciona si se sale del valor int64.

¿Se trata de un problema de seguridad?

Esta implementación tiene solo 1 error: cuando ambas partes generan el mismo privateX, fallará, pero con la gran cantidad de números base generados, esto solo ocurre una vez en aproximadamente 50 millones de veces.

¡Me gustaría hablar sobre la fuerza de este método y los posibles escollos!

¡Gracias!

    
pregunta YesMan85 02.05.2011 - 10:54
fuente

2 respuestas

10

Lo que implementaste es no Diffie-Hellman, y no tiene ninguna fuerza. Se te confunde con el uso del carácter ' ^ '.

En los lenguajes de programación tipo C, ' ^ ' es el operador para una exclusiva a nivel de bits -o (un "XOR").

Al escribir matemáticas en ASCII, se acostumbra a denotar exponenciación con el carácter ' ^ ', ¡y no es un XOR en absoluto! Esta notación proviene de LaTeX, un sistema de composición tipográfica que es el estándar de facto entre los matemáticos. En este mensaje, puedo usar etiquetas HTML y escribir ' g a ' para decir " g al poder a ", pero si tuviera que escribir en ASCII simple (por ejemplo, en Usenet), tendría que escribir: ' g ^ a '.

Además, Diffie-Hellman usa la exponenciación modular en enteros grandes, el tamaño típico es de 1024 bits o más. Los enteros de 32 bits o de 64 bits no serán suficientes para lograr ningún tipo de seguridad, y, en cualquier caso, la exponenciación modular es no lo que implementa pow() (en términos algebraicos, quiere trabajar sobre un campo finito, no enteros simples o números reales). En C # (.NET 4.0), desearía utilizar System.Numerics.BigInteger class, y en particular su método ModPow() . Pero primero, si alguna vez quieres hacer eso, primero tienes que entender las matemáticas subyacentes. Puede comenzar por leer los primeros tres capítulos del Manual de criptografía aplicada (no tiene relación alguna con Schneier's "Applied Criptografía ", y, en mi opinión, el" Manual "es un libro mucho más útil. Puede parecer un poco duro, pero no puede esperar implementar Diffie-Hellman correctamente a menos que domine las matemáticas descritas en esos primeros tres capítulos.

(Y, por supuesto, la implementación de algoritmos criptográficos tiene otros inconvenientes, relacionados con las fugas en los canales laterales, por lo que incluso si comprende lo que sucede matemáticamente, hacer su propia implementación no es necesariamente una buena idea .)

    
respondido por el Thomas Pornin 02.05.2011 - 15:08
fuente
4

Diffie-Hellman se basa en la exponenciación modular, por lo que al usar una función diferente en este código, no se ha implementado Diffie-Hellman en absoluto, sino algo más.

Además, los números de 63/64 bits que está utilizando son demasiado pequeños en cualquier caso.

Debería leer un texto básico sobre criptografía, por ejemplo, Criptografía aplicada de Schneier.

    
respondido por el frankodwyer 02.05.2011 - 11:47
fuente

Lea otras preguntas en las etiquetas