Information Security Asked by Roger Far on January 2, 2022

For a test project I have tried to implement the (famous) Diffie Hellman algorithm for safe key exchange.

Now I have written this 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();
}
}
}
```

Now my main concern is that I did not use the standard formula: g pow(a) mod p = A, but g XOR a mod p. The pow(a) does not work if it goes outside the int64 value.

Is this a safety concern?

This implementation has only 1 bug: when both parties generate the same privateX, it will fail, but with the large amount of base numbers generated this only happens once in about 50 million times.

I would like to discuss the strength of this method and potential pitfalls!

Thanks!

What you implemented is *not* Diffie-Hellman, and has no strength at all. You are being confused with the use of the '`^`

' character.

In C-like programming languages, '`^`

' is the operator for a bitwise exclusive-or (a "XOR").

When writing mathematics in ASCII, it is customary to denotes exponentiation with the '`^`

' character -- and it is not a XOR at all ! This notation comes from LaTeX, a typesetting system which is the de facto standard among mathematicians. In this message, I can use HTML tags and write '*g ^{a}*' to say "

Moreover, Diffie-Hellman uses *modular* exponentation on big integers -- typical size being 1024 bits or more. 32-bit or 64-bit integers will not be enough to achieve any kind of security, and, in any case, modular exponentiation is *not* what `pow()`

implements (in algebraic terms, you want to work over a finite field, not plain integers or real numbers). In C# (.NET 4.0), you would want to use the System.Numerics.BigInteger class, and in particular its `ModPow()`

method. But first, if you ever want to do that, you first have to understand the underlying mathematics. You can begin by reading the first three chapters of the Handbook of Applied Cryptography (no relation whatsoever with Schneier's "Applied Cryptography", and, in my view, the "Handbook" is a far more useful book). It may seem a bit harsh, but you cannot hope to implement Diffie-Hellman properly unless you master the mathematics described in those first three chapters.

(And, of course, implementing cryptographic algorithms has other pitfalls, related to side-channel leaks, so even if you *do* understand what happens mathematically, making your own implementation is not necessarily a good idea.)

Answered by Thomas Pornin on January 2, 2022

Diffie-Hellman is based on modular exponentiation, so by using a different function in this code you haven't implemented Diffie-Hellman at all but something else.

Also the 63/64-bit numbers you're using are too small in any case.

You should read a basic text on cryptography, e.g. Schneier's Applied Cryptography.

Answered by frankodwyer on January 2, 2022

Get help from others!

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP