Mensajes

Es posible que n_i sea igual a otro n_k?

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

X = y (mod n_i)
X = z (mod n_i)

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 n_i, 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!

Pregunta casual,

Tengo algo en mente y necesito enviar un correo electronico a una cuenta de Outlook, pero necesito agregarle unas cabeceras al correo electronico que voy a enviar. Por ejemplo, necesito enviar la cabecerá X-Originating-Email y/o Return-Path modificando esos valores.

Esto podría hacerlo directamente con C#? Algun ejemplo?

Échale un vistazo a https://msdn.microsoft.com/en-us/library/system.net.mail.mailmessage.headers%28v=vs.110%29.aspx.

Cito:

The Headers property allows an application to access the headers collection for the message. While this collection is read-only (a new collection can not be set), custom headers can be added to or deleted from this collection. Any custom headers added will be included when the MailMessage instance is sent. Before a message is sent, only headers specifically added to this collection in the Headers property are included in the collection. After the MailMessage instance is sent, the Headers property will also include headers that are set using the associated properties of the MailMessage class or parameters passed when a MailMessage is used to initialize a MailMessage object.

Puedes incluir nuevas headers antes de enviar el mensaje, pero teniendo en cuenta que ciertas headers ya son creadas cuando creas la instancia de la clase MailMessage (checkea el link), pero las que tu nombras deberían de ser añadidas antes del envío, sin problemas, supongo.

Ya nos cuentas

Saludos!

Detalles 

El algoritmo estaba funcionando bien pero su puso lento... el problema fue la multiplicacion, era algo ineficiente, lo mejore con multiplicacion modular y posteriomente volvio a ir lento, ahora era la exponenciacion, ya la optimize tambien ahora tendre que ver como se comporta.

Por cierto cuantos testigos recomiendan para el Test de primalidad de fermat estoy usando 5 actualmente pero en wikipedia dicen que solo use 4.

¿Que opinan?

Saludos!

Sobre la exponenciación, te recomiendo que checkees https://en.wikipedia.org/wiki/Montgomery_modular_multiplication y si estás utilizando exponentiation by squaring mejor migra a éste. Revisa https://en.wikipedia.org/wiki/Modular_exponentiation también.

Sobre los witness en Fermat, bueno hay una regla que indica que la mitad de la clase de residuos son witnesses, por lo tanto testigos de que 'n' es compuesto, como ves hay una alta probabilidad de acierto a la hora de testear si n es compuesto (a no ser que sea un nº de carmichael), 5 en total estarían bien.

También tienes el Lehmann test, que particularmente me gusta mucho por su simpleza y eficacia, se centra en el teorema de Cauchy el cúal afirma que existen elementos dentro del grupo cuyo orden multiplicativo es un factor primo del orden del grupo, por lo tanto si cogemos varios elementos del grupo (bases) y las elevamos a (p-1)/2 y no obtenemos 1 congruente, entonces no satisface el teorema, pero cuidado, que hay algo llamado raíz primitiva, cuyo orden multiplicativo en el grupo es el propio orden en el grupo, pero sólo hay una cantidad de totient(totient(p)), por lo tanto un par de vueltas de este test son muy RECOMENDABLES.

Lehmann:

http://en.algoritmy.net/article/48610/Lehmann-test
https://en.wikipedia.org/wiki/Cauchy's_theorem_%28group_theory%29

Saludos!

[¿Nunca os ha pasado que estaís viendo la TV con amigos o con familiares, ponen los anuncios y se quedan como hipnotizados mirándolos?]

Como dicen por arriba, en spain tenemos mil canales y solo un par que merecen la pena pues hablan de ciencia, historia, antiguedades, religiones, viajes etc Pero cuando ponen los anuncios la caja tonta se vuelve insoportable, y bueno os lanzo una pregunta:

¿Nunca os ha pasado que estaís viendo la TV con amigos o con familiares, ponen los anuncios y se quedan como hipnotizados mirándolos? Yo siempre vacilo y digo, ¿qué pasa te molan los anuncios? En mi caso, no tengo ni face ni twitter ni nada, imagínate de lo que me entero cuando están hablando de gente a la que siguen, cotilleos de redes sociales, fotos mías que rulan por ahí etc... Lo único que sigo de cerca son las noticias, cosa controladísima, así que yo no me creo nada ya.

En fin si hubiera un botón de reset lo pulsaría hasta quedarme sin dedos. Ojalá hubiera nacido en la ilustración (o un poquito antes) y no en esta etapa negra, que los descubrimientos de ahora no son ni tan emocinantes como lo fueron en el s. XVI,XVII,XVIII.

Saludos y que le den a la matrix   

Me alegro de que lo pongas en práctica, es un tema muy apasionante. Miller-Rabin corre en tiempo polinomial, aunque lo que suelen recomendar es hacer varias rondas de Fermat y si el número parece primo pasarlo por Miller-Rabin. Otras implementaciones primero hacen trial division con una lista de primos considerables, lo pasan a Fermat y a Miller-Rabin, en fin, como más cómodo te sientas.

Ojo que si lo que buscas es hacer una criba de números primos, hay métodos más eficientes, lo único que necesitas una estructura auxiliar para ir guardando los números.

Saludos!

Vaya, y yo que cambié el método de cifrado por defecto justamente para aumentar la seguridad en el intercambio SSL y ahora resulta que es lo que me está impidiendo hacer la reversa xD, creo que optaré por usar RSA, lo había deshabilitado ya que me aparecía un problema conocido de una vulnerabilidad con el tipo de cifrado en RSA tal como estaba configurado.

Finalmente en el ssl.conf del apache que venia por defecto:

Código [Seleccionar] Expandir

SSLCipherSuite DEFAULT:!EXP:!SSLv2:!DES:!IDEA:!SEED:+3DES

Puse este orden:
El problema es que si habilito RSA nuevamente volveré a tener alertas de seguridad.

De todas maneras no es que quiera hacer un ataque, lo que quiero es realizar monitoreo ssl a servidores en modo promiscuo sin tener que intervenir el servidor web, el problema es que si hay un servidor que necesite monitorear que tenga el método de cifrado ECDHE antepuesto a los demás quiere decir que será imposible hacer el seguimiento, estaré obligado a hacer un reverse proxy y aumentar la capacidad del hardware a la altura del servidor físico donde se aloja el servidor WEB.

Se me ocurre que configurando un proxy TLS intermedio puedes mejorar la seguridad del procedimiento, me explico:

Tu eres el poseedor de la clave privada RSA del certificado, por lo tanto el Server puede negociar una sesión mediante RSA con tu proxy, y después le dices al cliente que utilice ECDHE, y como eres poseedor de la clave privada ECDHE ya puedes descifrar el tráfico entrante/saliente.

Simplemente has de interceptar el ServerHello que va hacia el cliente, cambiar la suite de RSA por ECDHE y recomputar el Finished.

Aunque lo óptimo no sería degradar la suite, sino utilizar ECDHE e invalidar el ClientKeyExchange del cliente, es decir, mandarle tu al server desde el proxy tu propio ClientKeyExchange, por lo tanto tienes que computar dos claves de sesión, una con el cliente y otra con el server, por lo que son dos TLS Handshakes. El problema es que cualquier cambio en el Handshake es detectable por la parte afectada al final del procedimiento (Ver mensajes Finished), por lo que tienes que recomputar dichos mensajes y hacer su MAC correspondiente.

RSA en sí no es vulnerable si se utiliza un tamaño de más de 1024 (2048 está bien), academicamente no se ha llegado a romper una clave de 1024 pero se teoriza que los gobiernos interesados podrían ser capaces de ello, ya que 1024 bit son 2⁸⁰ operaciones con el GNFS (el alg. más óptimo de factoring con números grandes).

Otro gran fallo, y yo creo que es el más a tener en cuenta, es que RSA no ofrece Perfect-Forward Secrecy, por lo que si un tercero recolecta negociaciones de claves simétricas utilizando RSA durante 10 años y consigue romper la clave RSA al de un tiempo, podrá descifrar la clave simétrica AES, TDES que protege la información cifrada, si señores, ese día llegará ya pasó en la primera/segunda mundial que al de un tiempo de acabar la guerra consiguieron descifrar mensajes del enemigo. Al utilizar algs. ephemeral daría igual a no ser que computen el DLP en un tiempo razonable, cosa que hasta que no llegue el cuántico y apliquen Shor's... La pena es que las primeras en caer serán las curvas elípticas, ya que "simulan" la seguridad de RSA/DH con menos tamaño de clave en bits, por lo que se necesitan menos qubits para dicho propósito.

Saludos!

El problema reside en que utilizas ECDHE (Curvas elípticas con Diffie-Hellman efímero), en cristiano, en cada intercambio de clave o TLS Handshake se eligen unos parámetros distintos a los previamente empleados. Todo esto sucede en el ServerKeyExchange donde se eligen los mismos (uno de ellos es la clave privada) y se crea una firma digital (HASH + RSA signature en tu caso), por lo tanto, el atacante es imposible que sepa la clave privada, solo sabe la firma digital de los miembros públicos.

Te doy dos soluciones parciales:

- Antes de que a la víctima (ya se que lo haces en local) le llegue el ServerKeyExchange, eliminas dicho paquetes, generas tu los parámetros sobre el grupo finito y recomputas la firma digital (tienes la clave privada RSA, es trivial) y mandas el paquete a la vícitma. Al final del Handshake tendrías que recomputar los mensajes Finished para el cliente y para el server, ya que ambos han visto mensajes distintos, trivial también porque tienes la clave simétrica de cifrado.

- Eliges otra suite de cifrado, preferiblemente solo cambiar ECDHE por RSA, ya que si eliges ECDH o DH (Diffie-Hellman o DH sobre ECC) los parámetros tienen que ir en el propio certificado, por lo que recomiendo RSA, o sino reconstruir el certificado hardcodeando dichos parámetros (creo que el 99% de la comunidad criptógrafa te mataríamos ).

Saludos!

Perdón por el doble post, pero no me puedo resistir a publicar esta información (a ver si ejerzo presión).

This mod integrates the MathJax library into SMF forum. MathJax is the modern javascript-based LaTeX rendering solution for the Internet [...]

http://custom.simplemachines.org/mods/index.php?mod=4077

Aunque la versión de SMF parece no coincidir con la del foro... Todo es probarlo, si os lo estoy dando hecho    

P.D = Puede que parezca pesado pero estate casi 7 años en estos lares escribiendo fórmulas en bbcode 

Saludos!

Ahora se que si es posible usar LateX (o al menos un subconjunto de las reglas) através de MathJAX (que es lo que usan en Stack Exchange). Lo único que necesitamos es agregar una etiqueta BBC para mathjax (por ejemplo [mjx]). No creo que puedas cambiar el comportamiento de code solo para "LaTeX" porque GeSHI tiene reglas para esa entrada:

Código (LaTeX) [Seleccionar] Expandir

\left(\frac{x^2}{x - 2x}\right)\times2

Gracias por tu respuesta MinusFour. Por lo que dices, si se integrase LateX al 100% habría que implementar un motor que lo interpretase, por lo que es mejor tirar de MathJax, que es integrable desde bbcode/SMF.

Espero que se comente más respecto al tema. Aunque no tengo muchas esperanzas, puesto que lo único que se cambia en el foro ocasionalmente son los emoticonos , espero equivocarme (al parecer no supone tanto esfuerzo integrarlo).

Saludos!

[Chinese Remainder Theorem]

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:

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

De forma general tenemos:

[latex]b\equiv a\pmod n[/latex] , 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 [latex]0\equiv a\pmod n[/latex]

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 (a_i, n_i) tal que a_i < n_i donde a_i es el residuo y n_i el módulo de cada congruencia,

hallar x tal que:

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

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

Para que este sistema tenga solución, los módulos desde [latex]n_1[/latex] hasta [latex]n_i[/latex] deben de ser coprimos es decir gcd(n₁...n_i)=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:

[latex]N = n_1*n_2*n_3*...*n_i -> lcm(n_1...n_i)[/latex]

y aplicamos la siguiente fórmula:

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

Si lo reescribimos tenemos:

[latex]q = \sum_{k=0}^i a_k*N_k*t_k[/latex]

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

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

[latex] x = N*k + u [/latex]

Ejemplo:
[latex]x\equiv 2\pmod 3[/latex]
[latex]x\equiv 3\pmod 5[/latex]
[latex]x\equiv 2\pmod 7[/latex]

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:

[latex]N = 3*5*7 = 105[/latex]

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

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

Empezamos por k=1, por lo tanto tenemos:

[latex]a_1 = 2
n_1 = 3
N_1= \frac{N}{n_1} = \frac{105}{ 3} = 35[/latex]
[latex][N_1^{-1}]_{n_1}[/latex] => para ello calculamos "t₁" mediante la multiplicativa modular inversa de N₁ en n₁, [latex]1\equiv 35*t_k\pmod 3[/latex], a través de euler [latex]t_1\equiv 35^{\phi(3)-1}\pmod 3[/latex] por lo tanto t₁=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

a₂ = 3
n₂ = 5
N₂ = N / n₂ = 105 / 5 = 21
[(N₂)^-1]_n2 -> Resolvemos t₂ para hallar la mult. inv. mod. 1=21*t₂ (mod 5) de la siguiente forma: t₂ = 21^phi(5)-1 (mod 5), que equivale a t₂ = 21³ (mod 5), por lo tanto t₂=1.

y sumamos en q:

q = q + a₂*N₂*t₂ = q + 63 = 140 + 63 = 203

Última iteración

i = 2

a₃ = 2
n₃ = 7
N₃ = N / n₃ = 105 / 7 = 15
[(N₃)^-1]_n3 -> Resolvemos t₃ para hallar la mult. inv. mod. 1=15*t₃ (mod 7) de la siguiente forma: t₃ = 15^phi(7)-1 (mod 7), que equivale a t₃ = 15⁵ (mod 7), por lo tanto t₃=1.

y sumamos en q:

q = q + a₃*N₃*t₃ = 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 = n₁*n₂*..*n_i. La multiplicativa inversa modular se computa de forma iterativa sin el Extended Euclidean, ya que "a_i*t_i" dejarán un múltiplo "k_i" de "n_i" pequeño.

Código (csharp) [Seleccionar] Expandir

private static BigInteger MultInv(BigInteger a, BigInteger b)
        {
            BigInteger inv = BigInteger.Zero, rem = BigInteger.Zero;
            BigInteger i = BigInteger.One;
            bool found = false;
            while (!found)
            {
                inv = BigInteger.DivRem(BigInteger.Add(BigInteger.Multiply(b, i), BigInteger.One), a, out rem);
                if (rem == BigInteger.Zero)
                    found = true;
                i++;
            }
            return inv;
        }

        private static List<BigInteger> ChineseRT(List<BigInteger> residues, List<BigInteger> modules)
        {
            List<BigInteger> sol = new List<BigInteger>(2);
            BigInteger N = BigInteger.One, ai = BigInteger.Zero, Ni = BigInteger.Zero, res = BigInteger.Zero;
            foreach (BigInteger m in modules)
                N = BigInteger.Multiply(N, m);
            for (int i = 0; i < modules.Count; i++)
            {
                ai = residues[i];
                Ni = BigInteger.Divide(N,modules[i]);
                res += BigInteger.Multiply(BigInteger.Multiply(ai, Ni), MultInv(Ni, modules[i]));
            }
            res = BigInteger.Remainder(res, N);
            sol.Add(res);
            sol.Add(N);
            return sol;
        }

        static void Main(string[] args)
        {
            List<BigInteger> residues = new List<BigInteger>();
            List<BigInteger> modules = new List<BigInteger>();
            residues.Add(2); residues.Add(3); residues.Add(2);
            modules.Add(3); modules.Add(5); modules.Add(7);
            List<BigInteger> sol = ChineseRT(residues, modules);
        }

EDIT: Seguiré adaptándolo a LateX.

Saludos!