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!