Rabin Cryptosystem es un criptosistema de clave pública inventado por Michael Rabin. Utiliza cifrado de clave asimétrica para comunicarse entre dos partes y cifrar el mensaje.
La seguridad del criptosistema Rabin está relacionada con la dificultad de factorización. Tiene la ventaja sobre los demás de que el problema en el que se basa ha resultado ser tan difícil como la factorización de enteros . También tiene la desventaja de que cada salida de la función de Rabin puede ser generada por cualquiera de las cuatro entradas posibles. si cada salida es un texto cifrado, se requiere una complejidad adicional en el descifrado para identificar cuál de las cuatro entradas posibles era el verdadero texto sin formato.
Pasos en el criptosistema Rabin
Generación de claves
- Genere dos números primos muy grandes, p y q, que satisfagan la condición
p ≠ q → p ≡ q ≡ 3 (mod 4)
Por ejemplo:
p=139 y q=191 - Calcular el valor de n
n = pq - Publicar n como clave pública y guardar p y q como clave privada
Cifrado
- Obtener la clave pública n.
- Convierte el mensaje a valor ASCII. Luego conviértalo a binario y amplíe el valor binario consigo mismo, y cambie el valor binario nuevamente a m decimal.
- Cifrar con la fórmula:
C = m 2 mod n - Enviar C al destinatario.
Descifrado
- Aceptar C del remitente.
- Especifique a y b con GCD Euclidiano Extendido tal que, ap + bq = 1
- Calcule r y s usando la siguiente fórmula:
r = C (p+1)/4 mod p
s = C (q+1)/4 mod q - Ahora, calcule X e Y usando la siguiente fórmula:
X = ( apr + bqs ) mod p
Y = ( apr – bqs ) mod q - Las cuatro raíces son, m1=X, m2=-X, m3=Y, m4=-Y
Ahora, conviértalas a binarias y divídalas por la mitad. - Determine en qué mitad izquierda y derecha son iguales. Mantenga la mitad de ese binario y conviértalo a m decimal. Obtenga el carácter ASCII para el valor decimal m. El carácter resultante da el mensaje correcto enviado por el remitente.
A continuación se muestra la implementación del criptosistema Rabin en Java
// Java program to illustrate
// Process of Rabin Cryptosystem
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.security.SecureRandom;
import java.util.Random;
class Cryptography {
private static Random r = new SecureRandom();
private static BigInteger TWO = BigInteger.valueOf(2);
private static BigInteger THREE = BigInteger.valueOf(3);
private static BigInteger FOUR = BigInteger.valueOf(4);
public static BigInteger[] generateKey(int bitLength)
{
BigInteger p = blumPrime(bitLength / 2);
BigInteger q = blumPrime(bitLength / 2);
BigInteger N = p.multiply(q);
return new BigInteger[] { N, p, q };
}
public static BigInteger encrypt(BigInteger m,
BigInteger N)
{
return m.modPow(TWO, N);
}
public static BigInteger[] decrypt(BigInteger c,
BigInteger p,
BigInteger q)
{
BigInteger N = p.multiply(q);
BigInteger p1 = c.modPow(p
.add(BigInteger.ONE)
.divide(FOUR),
p);
BigInteger p2 = p.subtract(p1);
BigInteger q1 = c.modPow(q
.add(BigInteger.ONE)
.divide(FOUR),
q);
BigInteger q2 = q.subtract(q1);
BigInteger[] ext = Gcd(p, q);
BigInteger y_p = ext[1];
BigInteger y_q = ext[2];
BigInteger d1 = y_p.multiply(p)
.multiply(q1)
.add(y_q.multiply(q)
.multiply(p1))
.mod(N);
BigInteger d2 = y_p.multiply(p)
.multiply(q2)
.add(y_q.multiply(q)
.multiply(p1))
.mod(N);
BigInteger d3 = y_p.multiply(p)
.multiply(q1)
.add(y_q.multiply(q)
.multiply(p2))
.mod(N);
BigInteger d4 = y_p.multiply(p)
.multiply(q2)
.add(y_q.multiply(q)
.multiply(p2))
.mod(N);
return new BigInteger[] { d1, d2, d3, d4 };
}
public static BigInteger[] Gcd(BigInteger a, BigInteger b)
{
BigInteger s = BigInteger.ZERO;
BigInteger old_s = BigInteger.ONE;
BigInteger t = BigInteger.ONE;
BigInteger old_t = BigInteger.ZERO;
BigInteger r = b;
BigInteger old_r = a;
while (!r.equals(BigInteger.ZERO)) {
BigInteger q = old_r.divide(r);
BigInteger tr = r;
r = old_r.subtract(q.multiply(r));
old_r = tr;
BigInteger ts = s;
s = old_s.subtract(q.multiply(s));
old_s = ts;
BigInteger tt = t;
t = old_t.subtract(q.multiply(t));
old_t = tt;
}
return new BigInteger[] { old_r, old_s, old_t };
}
public static BigInteger blumPrime(int bitLength)
{
BigInteger p;
do {
p = BigInteger.probablePrime(bitLength, r);
} while (!p.mod(FOUR).equals(THREE));
return p;
}
}
public class RabinCryptosystem {
public static void main(String[] args)
{
BigInteger[] key = Cryptography.generateKey(512);
BigInteger n = key[0];
BigInteger p = key[1];
BigInteger q = key[2];
String finalMessage = null;
int i = 1;
String s = "Hello";
System.out.println("Message sent by sender : " + s);
BigInteger m
= new BigInteger(
s.getBytes(
Charset.forName("ascii")));
BigInteger c = Cryptography.encrypt(m, n);
System.out.println("Encrypted Message : " + c);
BigInteger[] m2 = Cryptography.decrypt(c, p, q);
for (BigInteger b : m2) {
String dec = new String(
b.toByteArray(),
Charset.forName("ascii"));
if (dec.equals(s)) {
finalMessage = dec;
}
i++;
}
System.out.println(
"Message received by Receiver : "
+ finalMessage);
}
}
Producción:
Message sent by sender : Hello Encrypted Message : 96683217050639837550625 Message received by Receiver : Hello
Publicación traducida automáticamente
Artículo escrito por harsh_thoriya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA