elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Seguridad Informática
| |-+  Seguridad
| | |-+  Criptografía (Moderador: kub0x)
| | | |-+  [Taller] Chinese Remainder Theorem
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Taller] Chinese Remainder Theorem  (Leído 2,255 veces)
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.115


S3C M4NI4C


Ver Perfil
[Taller] Chinese Remainder Theorem
« en: 14 Mayo 2016, 12:28 »

Chinese Remainder Theorem

Buenas.

Hoy os traigo uno de los pilares matemáticos más impresionantes descubierto múltiples veces en la historia. Se le atribuye al gran Sun Tzu, es por eso que lo suelen nombrar Chinese Remainder Theorem (Teorema del resto chino), aunque otras culturas lo reinventaran con otro enunciado diferente ( para los amantes de la historia revisad: http://www.math.harvard.edu/~knill/crt/lib/Kangsheng.pdf )

¿De que trata este teorema? El siguiente planteamiento del mismo no difiere del planteamiento ancestral descrito por aquellas intrigantes culturas:

¿Cómo podemos hallar el número X que al dividir por 3 nos deja resto 2, al dividir por 5 nos deja resto 3 y al dividir por 7 nos deja resto 2? Simple, ¿verdad?. Es como si hubiera repartido una serie de objetos entre varias personas y hubiera olvidado la cantidad de objetos y solo me acuerdo de a cuantas personas he repartido y el resto de dichas operaciones.

El gran Grauss formalizó los teoremas de Euler, Lagrange, Fermat y Legendre entre tantos, formalizando de esta forma la aritmética modular en su obra maestra Disquisitiones Arithmeticae (si teneís una biblioteca en la uni corred a leerlo), y cómo no, no pudo dejar pasar la ocasión de plantear este mismo teorema, en su caso con calendarios y ciclos lunares.

Explicado el planteamiento, empecemos a adentrarnos en las profundidades matemáticas (ojalá algún día pongan LateX en este foro ... )

ATENCIÓN: Tanto la explicación algebraíca general como el ejemplo posterior son fruto de mi conocimiento y práctica, pudiendo haber mínimas diferencias con el proceso estándar/general.

Primero definamos lo que es una relación de congruencia:

3\equiv 7\pmod 4 lo expresamos como "3 es congruente a 7 módulo 4" porque "(4*1)+3=7" y porque "4 divide a 7-3".
3\equiv 11\pmod 4 "4 divide a 11-3" además "4*2 + 3 = 11"

De forma general tenemos:

b\equiv a\pmod n , su expresión en forma de ecuación sería "a = n*k + b", además "n | a-b" es decir "a-b es el múltiplo k de n". Si "a" es divisible entre "n" tendríamos 0\equiv a\pmod n

Si no entendiste la parte anterior, tranquilo, revisa este tema https://en.wikipedia.org/wiki/Modular_arithmetic y vuelve cuando quieras.

Por lo tanto el CRT se basa en resolver el siguiente sistema de congruencias:

Dada una coleción de pares (ai, ni) tal que ai < ni donde ai es el residuo y ni el módulo de cada congruencia,

hallar x tal que:

x\equiv a_{1}\pmod n_1
x\equiv a_{2}\pmod n_2
x\equiv a_{3}\pmod n_3
...
x\equiv a_i\pmod n_i

Es decir, x dejará residuo a_{1} al dividir por n_1, residuo  a_2 al dividir por n_2 etc.

Para que este sistema tenga solución, los módulos desde n_1 hasta n_i deben de ser coprimos es decir gcd(n1...ni)=1. En cristiano, ninguno de los módulos puede estar compuesto por factores primos de otro módulo.

Si la coprimalidad se cumple, entonces expresaremos el módulo total como:

N = n_1*n_2*n_3*...*n_i -> lcm(n_1...n_i)

y aplicamos la siguiente fórmula:

q = \sum_{k=0}^i a_k*N_k*[N_k^{-1}]_{n_k} Donde N_k= \frac{N}{n_k} y [N_k^{-1}]_{n_k} denota la multiplicativa modular inversa, 1\equiv N_k*t\pmod n_k

Si lo reescribimos tenemos:

q = \sum_{k=0}^i a_k*N_k*t_k

Una vez calculadas y almacenadas en "q" las sucesivas iteraciones, obtenemos el residuo de nuestro nuevo sistema de la siguiente forma:

u\equiv q\pmod N por lo tanto nuestra solucion al sistema final quedaría:

 x = N*k + u

Ejemplo:
x\equiv 2\pmod 3
x\equiv 3\pmod 5
x\equiv 2\pmod 7

Primero probamos que los módulos son coprimos entre sí. Para ello comprobamos que gcd(3,5)=1 gcd(3,7)=1 gcd(5,7)=1.
Ahora calculamos el módulo total o variable multiplicativa del módulo:

N = 3*5*7 = 105

y aplicamos la fórmula arriba descrita paso por paso:

q = \sum_{k=1}^i a_k*N_k*[N_k^{-1}]_{n_k}

Empezamos por k=1, por lo tanto tenemos:

a_1 = 2<br />n_1 = 3<br />N_1= \frac{N}{n_1} = \frac{105}{ 3} = 35
[N_1^{-1}]_{n_1} => para ello calculamos "t1" mediante la multiplicativa modular inversa de N1 en n1, 1\equiv 35*t_k\pmod 3, a través de euler t_1\equiv 35^{\phi(3)-1}\pmod 3 por lo tanto t1=2. Si hacemos 1=35*2 (mod 3) se satisface la relación.

Ahora multiplicamos a1*N1*t1 y lo dejamos en q:

q = 2*35*2 = 140

Sigamos

i=1

a2 = 3
n2 = 5
N2 = N / n2 = 105 / 5 = 21
[(N2)-1]n2 -> Resolvemos t2 para hallar la mult. inv. mod. 1=21*t2 (mod 5) de la siguiente forma: t2 = 21phi(5)-1 (mod 5), que equivale a t2 = 213 (mod 5), por lo tanto t2=1.

y sumamos en q:

q = q + a2*N2*t2 = q + 63 = 140 + 63 = 203

Última iteración

i = 2

a3 = 2
n3 = 7
N3 = N / n3 = 105 / 7 = 15
[(N3)-1]n3 -> Resolvemos t3 para hallar la mult. inv. mod. 1=15*t3 (mod 7) de la siguiente forma: t3 = 15phi(7)-1 (mod 7), que equivale a t3 = 155 (mod 7), por lo tanto t3=1.

y sumamos en q:

q = q + a3*N3*t3 = q + 30 = 203 + 30 = 233

Ahora falta el último paso para obtener la solución al sistema inicial:

Para ello computamos:

u = q (mod N)

u = 233 (mod 105)

u = 23

y la solución al sistema inicial sería:

x = u (mod N)

x = 23 (mod 105)

Para comprobar que la solución es fidedigna sustituimos x por 23 en el sistema inicial:

2 = 23 (mod 3)
3 = 23 (mod 5)
2 = 23 (mod 7)

Y como vemos se satisfacen las congruencias en su totalidad. Otras soluciones para X serían x = 105*k + 23 -> {23, 128, 233...}

Cosas a tener en cuenta:

En la vida real las multiplicativas modulares inversas se computan mediante el Extended Euclidean y no cómo yo he hecho en mi ejemplo, ya que necesitas la factorización de cada módulo mediante el procedimiento de Euler.

CONCEPTOS A TENER EN CUENTA:

https://en.wikipedia.org/wiki/Congruence_relation
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
https://en.wikipedia.org/wiki/Modulo_operation
https://en.wikipedia.org/wiki/Euler's_totient_function
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
https://en.wikipedia.org/wiki/Pairwise_coprime
https://en.wikipedia.org/wiki/Disquisitiones_Arithmeticae
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures

He implementado una función en C# la cual dadas dos listas que representan un sistema de congruencias, una de residuos y otra de módulos, devuelve una lista donde el primer elemento es X y el segundo elemento es N = n1*n2*..*ni. La multiplicativa inversa modular se computa de forma iterativa sin el Extended Euclidean, ya que "ai*ti" dejarán un múltiplo "ki" de "ni" pequeño.



Código
  1. private static BigInteger MultInv(BigInteger a, BigInteger b)
  2.        {
  3.            BigInteger inv = BigInteger.Zero, rem = BigInteger.Zero;
  4.            BigInteger i = BigInteger.One;
  5.            bool found = false;
  6.            while (!found)
  7.            {
  8.                inv = BigInteger.DivRem(BigInteger.Add(BigInteger.Multiply(b, i), BigInteger.One), a, out rem);
  9.                if (rem == BigInteger.Zero)
  10.                    found = true;
  11.                i++;
  12.            }
  13.            return inv;
  14.        }
  15.  
  16.        private static List<BigInteger> ChineseRT(List<BigInteger> residues, List<BigInteger> modules)
  17.        {
  18.            List<BigInteger> sol = new List<BigInteger>(2);
  19.            BigInteger N = BigInteger.One, ai = BigInteger.Zero, Ni = BigInteger.Zero, res = BigInteger.Zero;
  20.            foreach (BigInteger m in modules)
  21.                N = BigInteger.Multiply(N, m);
  22.            for (int i = 0; i < modules.Count; i++)
  23.            {
  24.                ai = residues[i];
  25.                Ni = BigInteger.Divide(N,modules[i]);
  26.                res += BigInteger.Multiply(BigInteger.Multiply(ai, Ni), MultInv(Ni, modules[i]));
  27.            }
  28.            res = BigInteger.Remainder(res, N);
  29.            sol.Add(res);
  30.            sol.Add(N);
  31.            return sol;
  32.        }
  33.  
  34.        static void Main(string[] args)
  35.        {
  36.            List<BigInteger> residues = new List<BigInteger>();
  37.            List<BigInteger> modules = new List<BigInteger>();
  38.            residues.Add(2); residues.Add(3); residues.Add(2);
  39.            modules.Add(3); modules.Add(5); modules.Add(7);
  40.            List<BigInteger> sol = ChineseRT(residues, modules);
  41.        }

EDIT: Seguiré adaptándolo a LateX.

Saludos!


« Última modificación: 9 Junio 2016, 01:44 por kub0x » En línea

No hay amigos, ni enemigos, lucha necia, todos contra todos.

"Music directly represents the passions of the soul. If one listens to the wrong kind of music, he will become the wrong kind of person".

AlbertoBSD
💻🌎🌍🌏🌐 NWO📱
Colaborador
***
Conectado Conectado

Mensajes: 3.088


Libertad!!!!!


Ver Perfil WWW
Re: [Taller] Chinese Remainder Theorem
« Respuesta #1 en: 21 Mayo 2016, 01:09 »

Es posible que ni sea igual a otro nk?

Lo lei el otro dia y hoy amaneci con la idea de usarlo para buscar a un testigo correcto parael test de fermat fe numero primo ya sabes por aquello de los liars.. peto no se si sea aplicable

¿Que otros  validos usos puede tener?


En línea

Crackeame si puedes Wallet.dat
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.115


S3C M4NI4C


Ver Perfil
Re: [Taller] Chinese Remainder Theorem
« Respuesta #2 en: 21 Mayo 2016, 08:02 »

Es posible que ni sea igual a otro nk?

Realmente no, pues X es un valor común relacionado con todos los ni por lo tanto si tenemos lo siguiente:

X = y (mod ni)
X = z (mod ni)

Como ves este sistema de congruencias lineales no se sostiene, ya que es imposible que un mismo número X deje dos restos 'y' 'z' distintos con el mismo módulo ni, por eso los módulos deben de ser coprimos entre sí.

Bueno este teorema tiene varias aplicaciones en la criptografía:

- Secret Sharing con interpolación de polinomios (i.e de Lagrange) (el secreto se reconstruye con el Chinese Remainder Theorem).
- Pohlig-Hellman para computar el logaritmo discreto en grupos multiplicativos finitos, si el orden del módulo tiene factores triviales, CRT y consigues la privada.
- En RSA a la hora de computar el par de claves y firmar/cifrar mensajes, ya que el coste computacional queda reducido a dos exponenciales modulares.

Luego tiene más aplicaciones en otras ramas de la matemática, como en las Fourier transform.

Saludos!
En línea

No hay amigos, ni enemigos, lucha necia, todos contra todos.

"Music directly represents the passions of the soul. If one listens to the wrong kind of music, he will become the wrong kind of person".

Gh057


Desconectado Desconectado

Mensajes: 1.190



Ver Perfil
Re: [Taller] Chinese Remainder Theorem
« Respuesta #3 en: 24 Mayo 2016, 04:59 »

(casi off. topic XD) No pude dejar de comentar el excelente aporte que haz dejado kub0x; si bien es cierto que se dificulta por la notación, desde ya agradecido por las referencias indicadas para seguir el hilo del tema. También aprovecho el medio para agradecerte por las referencias anteriormente indicadas, las cuales sigo intentando dedicar tiempo de mis ratos libres  -y disfrutando!-  como es el caso de una edición de tapas duras de B. Scheider "Applied Cryptography". Sublime. XD

A mi corto entender, e intentando responder la consulta de AlbertoBSD, la aplicación más práctica que me viene a la mente del CRT es la de acelerar el descifrado en el intercambio de claves... al tener k y siendo primos p y q, puede utilizar números más pequeños que sean a su vez primos, y de esa forma realizar operaciones modulares en el orden de la mitad de bits... Saludos.
En línea

4 d0nd3 1r4 3l gh057? l4 r3d 3s 74n v4s74 3 1nf1n1t4...
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Chinese Theme [Photoshop and Flash]
Diseño Gráfico
MinusFour 5 1,667 Último mensaje 27 Mayo 2006, 02:55
por MinusFour
Taller de Vic_Thor: PROTOCOLO 802.11. TALLER WiFi « 1 2 »
Hacking Wireless
ChimoC 10 50,422 Último mensaje 8 Agosto 2009, 12:04
por ChimoC
Chinese Win
Windows
jacksonkynh 1 973 Último mensaje 20 Mayo 2010, 22:22
por Randomize
[Resuelto] Chinese - Japanese
Programación Visual Basic
Miseryk 2 1,358 Último mensaje 26 Diciembre 2010, 16:52
por Psyke1
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines