Diffie Hellman c # implementazione

5

Ciao a tutti,

Per un progetto di prova ho cercato di implementare l'algoritmo Diffie Hellman (famoso) per lo scambio sicuro di chiavi.

Ora ho scritto questo in 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();
        }
    }
}

Ora la mia preoccupazione principale è che non ho usato la formula standard: g pow (a) mod p = A, ma g XOR a mod p. Il pow (a) non funziona se esce dal valore int64.

Si tratta di un problema di sicurezza?

Questa implementazione ha solo 1 bug: quando entrambe le parti generano lo stesso privateX, fallirà, ma con la grande quantità di numeri di base generati ciò accade solo una volta in circa 50 milioni di volte.

Vorrei discutere la forza di questo metodo e le potenziali insidie!

Grazie!

    
posta Farlock85 02.05.2011 - 10:54
fonte

2 risposte

10

Ciò che hai implementato è non Diffie-Hellman, e non ha alcuna forza. Ti stai confondendo con l'uso del carattere ' ^ '.

Nei linguaggi di programmazione C-like, ' ^ ' è l'operatore per un esclusivo bit per bit o un "XOR".

Quando si scrive la matematica in ASCII, è consuetudine denotare esponenziazione con il carattere ' ^ ' - e non è affatto un XOR! Questa notazione deriva da LaTeX, un sistema di composizione tipografica che è lo standard di fatto tra i matematici. In questo messaggio, posso usare i tag HTML e scrivere " g a " per dire " g al potere a ", ma se dovessi scrivere in ASCII normale (ad esempio su Usenet), dovrei scrivere: ' g ^ a '.

Inoltre, Diffie-Hellman usa l'esponentazione modulare sui grandi numeri interi - la dimensione tipica è 1024 bit o più. Gli interi a 32 bit o 64 bit non saranno sufficienti per raggiungere qualsiasi tipo di sicurezza e, in ogni caso, l'esponenziazione modulare è non quale pow() implementa (in termini algebrici, si vuole lavorare su un campo finito, numeri interi non interi o numeri reali). In C # (.NET 4.0), si consiglia di utilizzare System.Numerics.BigInteger class, e in particolare il suo metodo ModPow() . Ma prima, se mai vuoi farlo, devi prima capire la matematica sottostante. Puoi iniziare leggendo i primi tre capitoli del Manuale di crittografia applicata (nessun rapporto con Schneier "applicato Crittografia "e, a mio avviso, il" Manuale "è un libro molto più utile). Può sembrare un po 'duro, ma non puoi sperare di implementare Diffie-Hellman correttamente a meno che tu non abbia padronanza della matematica descritta in quei primi tre capitoli.

(E, naturalmente, implementare algoritmi crittografici presenta altre insidie, legate a perdite di canale laterale, quindi anche se fai capisci cosa succede matematicamente, fare la tua implementazione non è necessariamente una buona idea .)

    
risposta data 02.05.2011 - 15:08
fonte
4

Diffie-Hellman è basato su esponenziazione modulare, quindi usando una funzione diversa in questo codice non hai implementato Diffie-Hellman affatto ma qualcos'altro.

Anche i numeri di 63/64-bit che stai utilizzando sono troppo piccoli in ogni caso.

Dovresti leggere un testo di base sulla crittografia, ad es. Schneier's Applied Cryptography.

    
risposta data 02.05.2011 - 11:47
fonte

Leggi altre domande sui tag