[Reto Programación] Cifrado RSA

overxfl0w13 · Diciembre 26, 2013, 09:55:25 PM

El reto consiste en implementar el cifrado RSA con el lenguaje que más gustéis.
Como ya sabréis RSA es un cifrado basado en asimetrías de problemas surgidos en la aritmética modular de números primos, el proceso para cifrado/descifrado es el siguiente:

General:
· Buscamos 2 nº primos medianamente grandes p y q (ponedle un rango entre 1,1000 y será suficiente, no para la práctica ya que la factorización de n, que veremos ahora, será mucho más simple y se podrán encontrar p y q fácilmente.
· Generar n:n=p*q y z:z=(p-1)*(q-1)

Cifrar:
· Generar un e:divisores(e) ∩ divisores(z) = {1}, para los no formales, buscar un e que no tenga ningún divisor en común con z (excepto el 1).
· Ej: Si z=8, coger e = 5. Un truco para esto es coger el inmediatamente inferior a z (o superior), en este caso e = 7 o e = 9
· Ciframos el mensaje: c = (m^e) % n

{c = cifrado,m = mensaje}

Descifrar:
· Buscamos d: e*d % z = 1
· c: c=(c^d) % n

{c = descifrado}

Ejemplo: (hacedlo en decimal, luego si queréis lo usáis para strings y esas cosas que quedan tan bien, además facilitaremos el reto

)
{p->3,q->7,n->21,z->12,m->14}
Divisores z = {1,2,3,4,6,12}
Buscamos e : divisores(e) ∩ divisores(z) = {1}, e.g e=5 -> {1,5} ∩ {1,2,3,4,6,12} = {1}, se cumple.
Generar d: 5*d % 12 = 1, sacamos d = 17
Cifrar: c: c=(14^5) % 21 = 14 -- Casualidad que sale el mismo xD
Descifrar c: c=(14^17)%21 = 14 -- Este es el texto inicial.

Os adjunto una posible solución en haskell:

Código: haskell


    type Prime = Int
    type PlainText = Char
    type Cipher = Int
   
   
    retN :: Prime -> Prime -> Int
    retN p q = p * q
   
    retZ :: Prime -> Prime -> Int
    retZ p q = (p-1)*(q-1)
   
    retE :: Int -> Int
    retE z = (z-1)
   
    retD :: Int -> Int -> Int -> Int
    retD d e z
             | (e*d) `mod` z == 1 = d
             | otherwise = retD (d+1) e z
             
    cipherCharRsa :: PlainText -> Prime -> Prime -> Cipher
    cipherCharRsa c p q = ((ord c)^(retE (retZ p q))) `mod` (retN p q)
   
    uncipherCharRsa :: Cipher -> Prime -> Prime -> PlainText
    uncipherCharRsa c p q = chr((c^(retD 0 (retE (retZ p q)) (retZ p q))) `mod` (retN p q) + 97)
   
    main :: String -> Prime -> Prime -> String
    main [] p q = ""
    main (x:xs) p q = " " ++ (show (cipherCharRsa x p q))++(main xs p q)

S10RIN · Diciembre 27, 2013, 05:17:31 PM

Hay alguna forma de elevar numeros grandes como 1234^937 en C sin que de error por ser un numero demasiado grande?
Según tengo visto C solo permite cálculos hasta cierto número y las potencias grandes como esta suelen producir error.

Sanko · Diciembre 30, 2013, 02:17:08 PM

Código: python

class RSA:
	
	#initializing
	def __init__(self, p, q):
		self.p = p
		self.q = q
		
		#defining n and z to resolve ops
		self.n = p * q
		self.z = (p-1) * (q-1)
		self.e = self.z - 1
		
		"""
		def _extD():
			for self.d in range(1, 100):
				if (self.e * self.d) % self.z == 1:
					return self.d
				
			return self.d
					
		_extD()
		"""
		
		self.encoded = []
		self.decoded = []
	
	# func to extract chars from a string
	def _extChar(self, text):
		self.text = text
		if text:
			self._encode(text[0])
			self._encode(self._extChar(text[1:]))
			
			
	
	#recive a char from extChar
	def _encode(self, m):
		self.m = m
		if m:
			m = ord(m)
			c = (m ^ self.e) % self.n
			self.encoded.append(c)
		
	"""		
	def _decode(self, m):
		self.m = m
		if m:
			c = (m ^ self.d) % self.n
			self.decoded.append(c)
	"""

#ejemplo de uso		
obj = RSA(3, 5)
obj._extChar("hola sanko")
print obj.encoded #output: [6, 14, 2, 12, 9, 11, 12, 0, 3, 14]

He comentado las func del decode porque tiraban algunos problemas y no quiero matarme la cabeza demasiado.
Saludos

[Reto Programación] Cifrado RSA

overxfl0w13

Diciembre 26, 2013, 09:55:25 PM Ultima modificación: Diciembre 30, 2013, 01:01:34 PM por overxfl0w13

S10RIN

Diciembre 27, 2013, 05:17:31 PM #1

Sanko

Diciembre 30, 2013, 02:17:08 PM #2