Implementación del Algoritmo Diffie-Hellman

Fondo

La criptografía de curva elíptica (ECC) es un enfoque de la criptografía de clave pública, basada en la estructura algebraica de curvas elípticas sobre campos finitos. ECC requiere una clave más pequeña en comparación con la criptografía que no es ECC para proporcionar una seguridad equivalente (una seguridad ECC de 256 bits tiene una seguridad equivalente a la de la criptografía RSA de 3072 bits).

Para una mejor comprensión de la criptografía de curva elíptica, es muy importante comprender los conceptos básicos de la curva elíptica. Una curva elíptica es una curva algebraica plana definida por una ecuación de la forma

y^2 = x^3 + ax + b         

Donde ‘a’ es el coeficiente de x y ‘b’ es la constante de la ecuación  

La curva no es singular; es decir, su gráfico no tiene vértices ni autointersecciones (cuando la característica del campo Coeficiente es igual a 2 o 3). 

En general, una curva elíptica se ve como se muestra a continuación. Las curvas elípticas pueden intersecarse en casi 3 puntos cuando se dibuja una línea recta que intersecta la curva. Como podemos ver, la curva elíptica es simétrica con respecto al eje x. Esta propiedad juega un papel clave en el algoritmo.

Elliptic Curve

Algoritmo de Diffie-Hellman

El algoritmo Diffie-Hellman se usa para establecer un secreto compartido que se puede usar para comunicaciones secretas mientras se intercambian datos a través de una red pública usando la curva elíptica para generar puntos y obtener la clave secreta usando los parámetros.  

  • En aras de la simplicidad y la implementación práctica del algoritmo, consideraremos solo 4 variables, una prima P y G (una raíz primitiva de P) y dos valores privados a y b.
  • P y G son números disponibles públicamente. Los usuarios (por ejemplo, Alice y Bob) eligen valores privados a y b y generan una clave y la intercambian públicamente. La otra persona recibe la clave y eso genera una clave secreta, después de lo cual tienen la misma clave secreta para cifrar.

Explicación paso a paso 

Alicia Beto
Claves públicas disponibles = P, G Claves públicas disponibles = P, G
Clave privada seleccionada = a Clave privada seleccionada = b

Clave generada = 

x = G^a mod P

Clave generada = 

y = G^b mod P

Se produce el intercambio de claves generadas.
Clave recibida = y clave recibida = x

Clave secreta generada = 

k_a = y^a mod P

Clave secreta generada = 

k_b = x^b mod P

Algebraicamente, se puede demostrar que 

k_a = k_b

Los usuarios ahora tienen una clave secreta simétrica para cifrar

Ejemplo: 

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.

Implementación:  

C

/* This program calculates the Key for two persons
using the Diffie-Hellman Key exchange algorithm */
#include<stdio.h>
#include<math.h>
 
// 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
    printf("The value of P : %lld\n", P);
 
    G = 9; // A primitive root for P, G is taken
    printf("The value of G : %lld\n\n", G);
 
    // Alice will choose the private key a
    a = 4; // a is the chosen private key
    printf("The private key a for Alice : %lld\n", a);
    x = power(G, a, P); // gets the generated key
     
    // Bob will choose the private key b
    b = 3; // b is the chosen private key
    printf("The private key b for Bob : %lld\n\n", b);
    y = power(G, b, P); // gets the generated key
 
    // Generating the secret key after the exchange
        // of keys
    ka = power(y, a, P); // Secret key for Alice
    kb = power(x, b, P); // Secret key for Bob
     
    printf("Secret key for the Alice is : %lld\n", ka);
    printf("Secret Key for the Bob is : %lld\n", kb);
     
    return 0;
}

Java

// This program calculates the Key for two persons
// using the Diffie-Hellman Key exchange algorithm
class GFG{
     
// Power function to return value of a ^ b mod P
private static long power(long a, long b, long p)
{
    if (b == 1)
        return a;
    else
        return (((long)Math.pow(a, b)) % p);
}
 
// Driver code
public static void main(String[] args)
{
    long P, G, x, a, y, b, ka, kb;
     
    // Both the persons will be agreed upon the
    // public keys G and P
     
    // A prime number P is taken
    P = 23;
    System.out.println("The value of P:" + P);
     
    // A primitive root for P, G is taken
    G = 9;
    System.out.println("The value of G:" + G);
     
    // Alice will choose the private key a
    // a is the chosen private key
    a = 4;
    System.out.println("The private key a for Alice:" + a);
     
    // Gets the generated key
    x = power(G, a, P);
     
    // Bob will choose the private key b
    // b is the chosen private key   
    b = 3;
    System.out.println("The private key b for Bob:" + b);
     
    // Gets the generated key
    y = power(G, b, P);
     
    // Generating the secret key after the exchange
    // of keys
    ka = power(y, a, P); // Secret key for Alice
    kb = power(x, b, P); // Secret key for Bob
     
    System.out.println("Secret key for the Alice is:" + ka);
    System.out.println("Secret key for the Bob is:" + kb);
}
}
 
// This code is contributed by raghav14

Python3

from random import randint
 
if __name__ == '__main__':
 
    # Both the persons will be agreed upon the
    # public keys G and P
    # A prime number P is taken
    P = 23
     
    # A primitive root for P, G is taken
    G = 9
     
      
    print('The Value of P is :%d'%(P))
    print('The Value of G is :%d'%(G))
     
    # Alice will choose the private key a
    a = 4
    print('The Private Key a for Alice is :%d'%(a))
     
    # gets the generated key
    x = int(pow(G,a,P)) 
     
    # Bob will choose the private key b
    b = 3
    print('The Private Key b for Bob is :%d'%(b))
    
    # gets the generated key
    y = int(pow(G,b,P)) 
     
     
    # Secret key for Alice
    ka = int(pow(y,a,P))
     
    # Secret key for Bob
    kb = int(pow(x,b,P))
     
    print('Secret key for the Alice is : %d'%(ka))
    print('Secret Key for the Bob is : %d'%(kb))

Javascript

<script>
 
// This program calculates the Key for two persons
// using the Diffie-Hellman Key exchange algorithm
 
// Power function to return value of a ^ b mod P
function power(a, b, p)
{
    if (b == 1)
        return a;
    else
        return((Math.pow(a, b)) % p);
}
 
// Driver code
var P, G, x, a, y, b, ka, kb;
 
// Both the persons will be agreed upon the
// public keys G and P
 
// A prime number P is taken
P = 23;
document.write("The value of P:" + P + "<br>");
 
// A primitive root for P, G is taken
G = 9;
document.write("The value of G:" + G + "<br>");
 
// Alice will choose the private key a
// a is the chosen private key
a = 4;
document.write("The private key a for Alice:" +
               a + "<br>");
 
// Gets the generated key
x = power(G, a, P);
 
// Bob will choose the private key b
// b is the chosen private key   
b = 3;
document.write("The private key b for Bob:" +
               b + "<br>");
 
// Gets the generated key
y = power(G, b, P);
 
// Generating the secret key after the exchange
// of keys
ka = power(y, a, P); // Secret key for Alice
kb = power(x, b, P); // Secret key for Bob
 
document.write("Secret key for the Alice is:" +
               ka + "<br>");
document.write("Secret key for the Bob is:" +
               kb + "<br>");
 
// This code is contributed by Ankita saini
 
</script>

C++

/* This program calculates the Key for two persons
using the Diffie-Hellman Key exchange algorithm using C++ */
#include <cmath>
#include <iostream>
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 << "The value of P : " << P << endl;
 
    G = 9; // A primitive root for P, G is taken
    cout << "The value of G : " << G << endl;
 
    // Alice will choose the private key a
    a = 4; // a is the chosen private key
    cout << "The private key a for Alice : " << a << endl;
 
    x = power(G, a, P); // gets the generated key
 
    // Bob will choose the private key b
    b = 3; // b is the chosen private key
    cout << "The private key b for Bob : " << b << endl;
 
    y = power(G, b, P); // gets the generated key
 
    // Generating the secret key after the exchange
    // of keys
    ka = power(y, a, P); // Secret key for Alice
    kb = power(x, b, P); // Secret key for Bob
    cout << "Secret key for the Alice is : " << ka << endl;
 
    cout << "Secret key for the Alice is : " << kb << endl;
 
    return 0;
}
// This code is contributed by Pranay Arora

Producción:

The value of P : 23
The value of G : 9

The private key a for Alice : 4
The private key b for Bob : 3

Secret key for the Alice is : 9
Secret Key for the Bob is : 9

Este artículo es una contribución de Souvik Nandi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.GeeksforGeeks.org o envíe su artículo por correo a contribuya@GeeksforGeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *