El algoritmo RSA es un algoritmo de criptografía asimétrica. Asimétrico en realidad significa que funciona en dos claves diferentes, es decir, clave pública y clave privada. Como el nombre describe, la clave pública se otorga a todos y la clave privada se mantiene privada.
Un ejemplo de criptografía asimétrica:
- Un cliente (por ejemplo, un navegador) envía su clave pública al servidor y solicita algunos datos.
- El servidor cifra los datos utilizando la clave pública del cliente y envía los datos cifrados.
- El cliente recibe estos datos y los descifra.
Dado que esto es asimétrico, nadie más, excepto el navegador, puede descifrar los datos, incluso si un tercero tiene la clave pública del navegador.
Las firmas digitales se utilizan para verificar la autenticidad del mensaje enviado electrónicamente. Un algoritmo de firma digital utiliza un sistema de clave pública. El transmisor previsto firma su mensaje con su clave privada y el receptor previsto lo verifica con la clave pública del transmisor. Una firma digital puede proporcionar servicios de autenticación de mensajes, integridad de mensajes y no repudio.
Algoritmo
Generación de claves RSA:
- Elija dos números primos grandes p y q
- Calcular n=p*q
- Seleccione la clave pública e tal que no sea un factor de (p-1)*(q-1)
- Seleccione la clave privada d tal que la siguiente ecuación sea verdadera (d*e)mod(p-1)(q-1)=1 o d sea inversa de E en módulo (p-1)*(q-1)
Esquema de firma digital RSA: en RSA, d es privado; e y n son públicos.
- Alice crea su firma digital usando S=M^d mod n donde M es el mensaje
- Alice envía el Mensaje M y la Firma S a Bob
- Bob calcula M1=S^e mod n
- Si M1=M entonces Bob acepta los datos enviados por Alice.
A continuación se muestra la implementación.
Python3
# Function to find gcd
# of two numbers
def euclid(m, n):
if n == 0:
return m
else:
r = m % n
return euclid(n, r)
# Program to find
# Multiplicative inverse
def exteuclid(a, b):
r1 = a
r2 = b
s1 = int(1)
s2 = int(0)
t1 = int(0)
t2 = int(1)
while r2 > 0:
q = r1//r2
r = r1-q * r2
r1 = r2
r2 = r
s = s1-q * s2
s1 = s2
s2 = s
t = t1-q * t2
t1 = t2
t2 = t
if t1 < 0:
t1 = t1 % a
return (r1, t1)
# Enter two large prime
# numbers p and q
p = 823
q = 953
n = p * q
Pn = (p-1)*(q-1)
# Generate encryption key
# in range 1<e<Pn
key = []
for i in range(2, Pn):
gcd = euclid(Pn, i)
if gcd == 1:
key.append(i)
# Select an encryption key
# from the above list
e = int(313)
# Obtain inverse of
# encryption key in Z_Pn
r, d = exteuclid(Pn, e)
if r == 1:
d = int(d)
print("decryption key is: ", d)
else:
print("Multiplicative inverse for\
the given encryption key does not \
exist. Choose a different encryption key ")
# Enter the message to be sent
M = 19070
# Signature is created by Alice
S = (M**d) % n
# Alice sends M and S both to Bob
# Bob generates message M1 using the
# signature S, Alice's public key e
# and product n.
M1 = (S**e) % n
# If M = M1 only then Bob accepts
# the message sent by Alice.
if M == M1:
print("As M = M1, Accept the\
message sent by Alice")
else:
print("As M not equal to M1,\
Do not accept the message\
sent by Alice ")
Producción:
decryption key is: 160009 As M = M1, Accept the message sent by Alice