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!