[Reto Programación] Cifrado RSA

  • 2 Respuestas
  • 2719 Vistas

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado overxfl0w13

  • *
  • Underc0der
  • Mensajes: 26
  • Actividad:
    0%
  • Reputación 0
  • Hola1
  • Skype: overxfl0w13
    • Ver Perfil

[Reto Programación] Cifrado RSA

  • en: 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
  1.     type Prime = You are not allowed to view links. Register or Login
  2.     type PlainText = You are not allowed to view links. Register or Login
  3.     type Cipher = You are not allowed to view links. Register or Login
  4.    
  5.    
  6.     retN :: Prime -> Prime -> You are not allowed to view links. Register or Login
  7.     retN p q = p * q
  8.    
  9.     retZ :: Prime -> Prime -> You are not allowed to view links. Register or Login
  10.     retZ p q = (p-1)*(q-1)
  11.    
  12.     retE :: You are not allowed to view links. Register or Login -> You are not allowed to view links. Register or Login
  13.     retE z = (z-1)
  14.    
  15.     retD :: You are not allowed to view links. Register or Login -> You are not allowed to view links. Register or Login -> You are not allowed to view links. Register or Login -> You are not allowed to view links. Register or Login
  16.     retD d e z
  17.              | (e*d) `You are not allowed to view links. Register or Login` z == 1 = d
  18.              | You are not allowed to view links. Register or Login = retD (d+1) e z
  19.              
  20.     cipherCharRsa :: PlainText -> Prime -> Prime -> Cipher
  21.     cipherCharRsa c p q = ((ord c)^(retE (retZ p q))) `You are not allowed to view links. Register or Login` (retN p q)
  22.    
  23.     uncipherCharRsa :: Cipher -> Prime -> Prime -> PlainText
  24.     uncipherCharRsa c p q = chr((c^(retD 0 (retE (retZ p q)) (retZ p q))) `You are not allowed to view links. Register or Login` (retN p q) + 97)
  25.    
  26.     main :: You are not allowed to view links. Register or Login -> Prime -> Prime -> You are not allowed to view links. Register or Login
  27.     main [] p q = ""
  28.     main (x:xs) p q = " " ++ (You are not allowed to view links. Register or Login (cipherCharRsa x p q))++(main xs p q)

« Última modificación: Diciembre 30, 2013, 01:01:34 pm por overxfl0w13 »

Desconectado S10RIN

  • *
  • Underc0der
  • Mensajes: 23
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil

Re:[Reto Programación] Cifrado RSA

  • en: 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.

Desconectado Sanko

  • *
  • Underc0der
  • Mensajes: 541
  • Actividad:
    0%
  • Country: 00
  • Reputación 0
  • ¿Puedes?
    • Ver Perfil
    • Underc0de

Re:[Reto Programación] Cifrado RSA

  • en: Diciembre 30, 2013, 02:17:08 pm
Código: Python
  1. class RSA:
  2.    
  3.    #initializing
  4.    def __init__(self, p, q):
  5.       self.p = p
  6.       self.q = q
  7.      
  8.       #defining n and z to resolve ops
  9.       self.n = p * q
  10.       self.z = (p-1) * (q-1)
  11.       self.e = self.z - 1
  12.      
  13.       """
  14.      def _extD():
  15.         for self.d in range(1, 100):
  16.            if (self.e * self.d) % self.z == 1:
  17.               return self.d
  18.            
  19.         return self.d
  20.              
  21.      _extD()
  22.      """
  23.      
  24.       self.encoded = []
  25.       self.decoded = []
  26.    
  27.    # func to extract chars from a string
  28.    def _extChar(self, text):
  29.       self.text = text
  30.       if text:
  31.          self._encode(text[0])
  32.          self._encode(self._extChar(text[1:]))
  33.          
  34.          
  35.    
  36.    #recive a char from extChar
  37.    def _encode(self, m):
  38.       self.m = m
  39.       if m:
  40.          m = ord(m)
  41.          c = (m ^ self.e) % self.n
  42.          self.encoded.append(c)
  43.      
  44.    """      
  45.   def _decode(self, m):
  46.      self.m = m
  47.      if m:
  48.         c = (m ^ self.d) % self.n
  49.         self.decoded.append(c)
  50.   """
  51.  
  52. #ejemplo de uso      
  53. obj = RSA(3, 5)
  54. obj._extChar("hola sanko")
  55. 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
Sigueme en Twitter : @Sankosk
Estos nuevos staff no tienen puta idea XD

 

Reto "Crackea el Menú"

Iniciado por Zekro

Respuestas: 2
Vistas: 3400
Último mensaje Noviembre 29, 2012, 05:57:24 pm
por Zekro
[Solucionario] Reto "Descubre la frase"

Iniciado por q3rv0

Respuestas: 10
Vistas: 6871
Último mensaje Agosto 13, 2012, 04:24:40 pm
por hdbreaker
Un Crackme que hice hace tiempo, haber si alguien lo resuelve [RETO]

Iniciado por LauBuru

Respuestas: 2
Vistas: 5289
Último mensaje Abril 04, 2016, 12:07:45 pm
por rush
[RETO] Desofusca mi codigo y dime por que siempre gano ;)

Iniciado por 79137913

Respuestas: 9
Vistas: 6670
Último mensaje Febrero 15, 2013, 07:05:19 pm
por Harkonidaz
Reto Java - Para probar un poco los conocimientos

Iniciado por ~ Yoya ~

Respuestas: 5
Vistas: 4242
Último mensaje Agosto 03, 2013, 12:01:59 am
por ~ Yoya ~