28/11/2023
Lidt almenviden om privat kryptering på offentlige netværk
Implementering af Diffie-Hellman algoritme
Elliptic Curve Cryptography (ECC) er en tilgang til offentlig nøglekryptografi, baseret på den algebraiske struktur af elliptiske kurver over endelige felter. ECC kræver en mindre nøgle sammenlignet med ikke-ECC-kryptografi for at give tilsvarende sikkerhed (en 256-bit ECC-sikkerhed har tilsvarende sikkerhed opnået med 3072-bit RSA-kryptografi).
For en bedre forståelse af elliptisk kurvekryptografi er det meget vigtigt at forstå det grundlæggende i den elliptiske kurve. En elliptisk kurve er en plan algebraisk kurve defineret af en ligning af formen
y^2 = x^3 + akse + b
Hvor 'a' er koefficienten for x, og 'b' er konstanten for ligningen
Kurven er ikke-ental; det vil sige, at dens graf ikke har cusps eller selvskæringer (når karakteristikken for koefficientfeltet er lig med 2 eller 3).
Generelt ser en elliptisk kurve ud som vist nedenfor. Elliptiske kurver kan krydse næsten 3 punkter, når der trækkes en lige linje, der skærer kurven. Som vi kan se, er den elliptiske kurve symmetrisk om x-aksen. Denne egenskab spiller en nøglerolle i algoritmen.
Elliptisk kurve
Diffie-Hellman algorithm:
The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters.
For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables, one prime P and G (a primitive root of P) and two private values a and b.
P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly. The opposite person receives the key and that generates a secret key, after which they have the same secret key to encrypt.
Step-by-Step explanation is as follows:
Alice Bob
Public Keys available = P, G Public Keys available = P, G
Private Key Selected = a Private Key Selected = b
Key generated =
x = G^a mod P
Key generated =
y = G^b mod P
Exchange of generated keys takes place
Key received = y key received = x
Generated Secret Key =
k_a = y^a mod P
Generated Secret Key =
k_b = x^b mod P
Algebraically, it can be shown that
k_a = k_b
Users now have a symmetric secret key to encrypt
Vis flere
Example:
Step 1: Alice and Bob get public numbers P = 23, G = 9
Step 2: Alice selected a private key a = 4 and
Bob selected a private key b = 3
Step 3: Alice and Bob compute public values
Alice: x =(9^4 mod 23) = (6561 mod 23) = 6
Bob: y = (9^3 mod 23) = (729 mod 23) = 16
Step 4: Alice and Bob exchange public numbers
Step 5: Alice receives public key y =16 and
Bob receives public key x = 6
Step 6: Alice and Bob compute symmetric keys
Alice: ka = y^a mod p = 65536 mod 23 = 9
Bob: kb = x^b mod p = 216 mod 23 = 9
Step 7: 9 is the shared secret.
Implementation:
C++
Java
Python3
C
C #
Javascript
C++
/* This program calculates the Key for two persons
using the Diffie-Hellman Key exchange algorithm using C++ */
using namespace std;
// Power function to return value of a ^ b mod P
long long int power(long long int a, long long int b,
long long int P)
{
if (b == 1)
return a;
else
return (((long long int)pow(a, b)) % P);
}
// Driver program
int main()
{
long long int P, G, x, a, y, b, ka, kb;
// Both the persons will be agreed upon the
// public keys G and P
P = 23; // A prime number P is taken
cout
