Thursday, May 05, 2022

We are nothing

There exist “undefinable” objects, one of them is the concept of “truth”. This concept cannot be definided in the standard model of a logic system within the system. This is a corollary of the Tarski undefinability theorem. 

Further, we know there are questions within certain logical systems that do not have a logical path to an answer (Gödel’s incompleteness).

Furthermore there exist questions that will never be asked due to the limitations and discreteness of our language e.g phonems, semiotics (Wittgenstein). As an algebraic analogy imagine that there are questions whose semantic particles lie in a transcendental extension of the object that stores our language. 

Most of the concepts of reality are not accesible to us it is like trying to describe a multiple of π using sequences of a finite subset of the integers. 

We are nothing, we are more basic than microbes compared with the complexity of reality.


Eduardo

@toorandom

Tuesday, April 02, 2019

Libertad de expresión y debate

El primer principio es que no debes engañarte a ti mismo, y tú eres la persona más fácil de engañar.

—Richard P. Feynman

La libertad de expresión es un concepto fundamental que se ha construido en algunas civilizaciones como parte fundamental de su estructura social, desde los griegos en la antigüedad hasta la declaración de los derechos humanos. Esto es el resultado de muchas acciones que sucedieron en el mundo occidental después de la ilustración y la revolución francesa. La libertad de expresión garantiza una mejor sinergia entre los seres humanos, de eso no hay duda. Hoy quiero hablar de errores en el debate que ocurren gracias al abuso del concepto de "libertad de expresión", antes de que me grites, trata de terminar de leerme.

Primero, formalmente la libertad de expresión es la capacidad de poder articular tus opiniones e ideas de cualquier tema (ej. política, sexualidad, arte) sin miedo, sin que te censuren o te sancionen, penalicen o agredan.

La libertad de expresión no es absoluta y esto es sabido. Podrá parecer un oxímoron decir que no es absoluta pero todos sabemos que existen temas donde no se es libre de expresar. Como ejemplos "blancos" tenemos secretos industriales, acuerdos de confidencialidad, copyrights, et cétera. Ejemplos más obscuros están la pedofilia, la violencia, la difamación, entre otros.

Una de las grandes consecuencias de la libertad de expresión es la capacidad de debate como herramienta de aprendizaje. Aquí quiero exponer unas ideas que he experimentado debatiendo de las cuales he sido el falaz y también victima de la falacia. El propósito de exponer esto es tratar de garantizar justamente que el debate sea una herramienta de aprendizaje y no de imposición ideológica. Hoy en día es necesario tener buenas bases para debatir debido al auge de las redes sociales y el impacto de estas. Con memes y opiniones violentas que reducen argumentos complejos a un dibujo que denota ironía, lo creas o no se están justificando personas a la hora de argumentar (inclusive políticos).

Los siguientes puntos son errores que considero graves y comunes en la lógica a la hora de debatir. Considero que han sido exponenciados con el uso de redes sociales y la sinergia que existe hoy en día en temas delicados (esto es una opinión con bases empíricas, no tengo fuente).

Nota importante: Estos diez puntos que expreso a continuación, antes que nada es conocimiento a posteriori. Lo que leerás es una opinión que estoy abierto a corregir si me es recalcado un error. Por lo tanto, con esta nota informo que no soy experto en el tema y sólo estoy expresando mi opinión potencialmente incompleta.

Errores comunes en el abuso de la libertad de expresión a la hora de debatir:

1. Uso de estadísticas inexistentes basadas en un potencial "sentido común". Es muy fácil decir 5 de cada 10 mujeres en el mundo han sufrido violencia de género cuando la realidad es que 7 de cada 10 mujeres en el mundo han sufrido violencia de género (Observatory of Gender (Women’s Coordinating Office, 2013)). El uso de estos números "a ojo de buen cubero", debe evitarse (y más si eres un personaje público)  porque la idea podría evolucionar de voz a voz a una mentira colectiva. A veces también se mezclan estadìsticas en espacios muestrales diferentes, cayendo en otra falacia.

2. Descalificación absoluta de argumentos basados en la ignorancia de la contraparte. Cuando una persona decide debatir con alguien, la premisa de las partes es que ambas pueden aportar al conocimiento mutuo. El utilizar argumentos no demostrables o sin fuentes es lo mismo que argumentar con falacias.
Cuando una parte decide utilizar estadísticas o afirmaciones de otras personas, deberá presentar una prueba de existencia de la fuente. Si esto no se tiene en mente, el objetivo del debate con alguien ignorante sólo será humillarlo o imponer una opinión sin propósitos de enseñanza.

3. Controlar el tema a través de obviedades, resultando en argumentos falaces. Aquí el perpetrador de la falacia supone que la contraparte no está alineada a la parte ética o moral superficial del tema en cuestión, generalmente llevando el argumento a otra falacia (por ejemplo, ad hominem). Esto podría suceder si el perpetrador de la falacia usa su opinión como absoluta e irrefutable por el hecho de estar débilmente alineada a un principio básico (e.j. libertad de expresión). El perpetrador de la falacia deberá darse cuenta que el argumento de la contraparte podría (o no) dar un contraejemplo a una situación o contexto específico, rompiendo con la generalidad de la idea. Aquí, quien controla el tema con obviedades insulta la inteligencia o ética de su contraparte gracias a la incapacidad de escuchar o de entender un panorama más complejo del superficial en el tema en cuestión. Yo y muchos le llamamos a veces a esto irse por la tangente, y es muy común.

Un ejemplo de esto es cuando alguien está en contra de la legalización de cambio de sexo a menores de edad. El falaz podría usar en su contra argumentos que van alineados a una posible transofobia o de estar en contra del movimiento LGBT o inclusive homofobia. En este caso no necesariamente la transofobia juega un papel en la contraargumentación por lo que el falaz usa argumentos obvios para explicar que la transofobia "es mala", queriendo justificar implícitamente que el no estar de acuerdo en el cambio de sexo a menores de edad es una implicación directa de "su transofobia". Esto insulta y humilla indirectamente a pesar de que esencialmente nadie en el debate sea transófobo.

4. Bases éticas y morales distintas entre ambas partes resultan en argumentos circulares. Si el tema a debatir se fundamenta en bloques fundamentales distintos de ambas partes, el debate sólo será un show.
En este caso lo que hay que debatir son los fundamentos y no las consecuencias de estos fundamentos. Como ejemplo es cuando una mujer denuncia y argumenta discriminación de género laboral y es tachada de mentirosa o exagerada por alguien alineado al patriarcado. En este ejemplo es claro que no se puede llegar a una conclusión debido a que el problema yace en los fundamentos de la argumentación (machismo vs feminismo) y no en la situación puntual del debate per sé.

5. Violencia verbal. La descalificación de un argumento con el uso de palabras arriba de tono o sarcasmo podría estar insultando indirectamente a tu contraparte, destruyendo su libertad de pensamiento. Esto sucede generalmente cuando algo es legítimamente "obvio" (teniendo una base moral y ética establecida para el debate). Opino que lo que debe recalcársele a quien no ve "lo obvio", no es la idea per sé, sino la base que fundamenta su idea, ya que ésta podría diferir con los axiomas preestablecidos para ejecutar un buen debate.

6. Uso de experiencias personales. Esto conlleva fácilmente a falacias debido a que la contraparte podría ignorar las circunstancias y contexto de tu argumento. Esto como herramienta argumentativa es pobre. A la hora de debatir ambas partes deben tener acceso a la misma información y antes de concluir un resultado, este debe estar basado en un camino lógico que una la base fundamental del debate y la conclusión.

7. Descontextualización del tema a debatir. Es fácil encontrar "contraejemplos" cuando cambias el universo de un problema, descalificando rápidamente a tu contraparte. Esto a veces está ligado al punto 4. Sin embargo puede ser más sutil y me parece que es un defecto muy grande y difícil de detectar el cual todos debemos estar alerta.

8. Tono de voz cambiante al ejecutar más estrés prosódico en ciertas palabras. Esto es muy interesante porque es un fenómeno fonético y no lingüístico que cambia la semántica. Este error argumentativo puede confundir a tu contraparte y usarse como herramienta de debate sucio después. Imagina que cuando pongo una palabra en mayúsculas, debes leerla con mayor fuerza.
YO, no leí el libro.  (otro lo leyó)
Yo NO leí el libro.   (no lo leí)
Yo no LEÍ el libro.   (hice otra cosa en vez de leer)
Yo no leí EL libro.   (leí otro)
Yo no leí el LIBRO.   (el libro no es un libro per sé).

Este tipo de error al debatir también puede darse de forma escrita con el uso de comillas (").

9. Falsas conclusiones porque tu contraparte sucede que tiene la misma opinión que tú. Esto es peligroso ya que es una falacia ad hominem, donde la conclusión estará basada en la coincidencia de argumentos de tu contraparte aunque estos no estén desarrollados. Por ejemplo dos racistas infiriendo que un argumento racista no es incorrecto en X o Y contexto (cuando con base en la ética occidental es incorrecto en todo contexto).

10. Uso de emociones ante temas sensibles. Este es el más controvertido a mi gusto pero es una realidad que es una herramienta usual en la argumentación moderna. Este pretende hacer sentir culpable a la contraparte de su postura con base en ejemplos en un contexto muy específico, forzando a la contraparte a abortar su postura por miedo a la humillación moral o descalificación social.

En mi opinión no hay argumentos que engloben la generalidad de una situación. En temas subjetivos cuya métrica de veracidad es inexistente y sólo es categórica o subjetiva siempre habrán contextos en donde tus ideas no embonen, por lo que a la hora de debatir siempre es importante plantear bases axiomáticas aceptadas por ambos para el inicio del debate.
Tratemos de eliminar la tendencia a fijarse solo en la evidencia que apoya nuestros puntos de vista, eso nos hace... tontos a la hora de debatir.

Más información, lee la interesante parte de "falacias informales" en la lista de Falacias de Wikipedia (https://en.wikipedia.org/wiki/List_of_fallacies#Informal_fallacies)

Eduardo Ruíz Duarte
Twitter: @toorandom
PGP: toorandom en Gmail.com FEE7 F2A0 

Tuesday, March 19, 2019

Quantum factorization intuition and how RSA is broken with examples from Fourier analysis


In this post I give an idea of how a quantum computer may factor an integer. This post is not formal and is intended for non experts, even non-mathematicians (in fact I wrote it for colleagues which are computer engineers). This is not exactly Shor's algorithm but I will explain the main essence of it. Therefore, some gaps may be here. I will explain how the Fourier Transform is used to factor an integer. Calculating the Fourier transform in a classical computer is expensive, however, for a quantum computer due to its physical nature, takes just 1 cycle using quantum gates. I won't delve into details about quantum gates in this post, just in the mathematical part but I will try to be as smooth as possible without any fancy words and language. This is intended for you to finally grasp how a quantum computer is supposed to break RSA and I will provide you some code to play with.


What you need to know first? 

a) What is GCD of two integers? :   If a and b are two integers, the Greatest common divisor (GCD) of a and b is the biggest integer g such that  a/g and b/g is “exact” (leaves no residue, this g is always a positive integer).   This GCD is very easy to calculate even that a and b are thousands of bits (this is how RSA public keys are being compared on the internet to find repeated factors in them and vulnerate its corresponding private keys)
The way of calculating the GCD number is really straightforward, for instance in python recursively as easy as:
        def gcd(a,b):
               if(b==0):
                       return a
               else:
                       return gcd(b,a%b)

Where % is the modulo operation in python, this is explained in (c).  GCD(a,b)=1 means that a and b share no factors and 1 is the biggest divisor of both.


b) A fact from highschool: The polynomial  $latex x^{2n}-1$   factors as  $latex (x^n + 1)(x^n -1)$. This is something you all know from highschool as difference of squares.

c) Modular arithmetic: $latex A=B \bmod N$   means “B is the residue of dividing A/N” and this residue of course is always strictly less than N.


d) Periodicity of modulo operation: Take any integer a, and build the sequence $latex a^0, a^1, a^2, a^3,\ldots, a^k\bmod N$ (this is a sequence “reduced” modulo N, which means dividing by N each element in the sequence and inserting the residue).

This list will be periodic eventually since N is finite. (patterns in the sequence will appear)
For example take N=14 the sequence $latex \lbrace 3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, 3^7, 3^8,\ldots\rbrace\bmod 14$ is reduced to $latex \lbrace 1,3,9,13,11,5,1,3,9,\ldots \rbrace$.

This “signal $latex 3^x \bmod 14$” has period 6 since $latex 3^{x+6} \bmod 14 = 3^x \bmod 14$  for all x (in highschool you see for example that $latex\sin(x)$ has period $latex 2\pi$ since $latex \sin(x)=\sin(x+2\pi)$

e) Fourier transform of periodic function: If you have a periodic signal and you feed it to a Fourier transform, this will output a function where in the x-axis you will have the frequencies of the original data. In the y-axis the magnitude (size) of the periodic data. 
To find the longest period of a signal, since Period = 1/Frequency (highschool) you just need to find all the highest amplitudes (y values) and check its corresponding x-coordinate (frequency)  and transform it to period. This is 1/x to get the period of the original high amplitude y value (you are interested in the highest period). For example, if you have a high Y value (amplitude), and its x-coordinate X is 0.1428 HZ then 1/X=1/0.1428 = 7 ( and the period is P=7).


Factorization Algorithm using periods mod N 
INPUT (An integer N to Factorize), OUTPUT (A factor)

  1. Pick a random $latex x$ between $latex 2$ and $latex N$
  2. If $latex g=\gcd(x,N)\geq 2$ then return $latex x$ (since $latex g$ is greater than $latex 1$ and $latex \gcd(x,N)$ is a common divisor of $latex N$, we found accidentally a factor $latex g$ which is improbable)
  3. Calculate the sequence $latex S:=\lbrace x^0, x^1, x^2, \ldots, x^N\rbrace \bmod N$ (this is a quantum step which is done in a quantum register in one cycle)
  4. Calculate the period $latex P$ of $latex S$ using quantum fourier transform (this is the same as the fourier transform but using quantum parallelism which for now you see as a blackbox since this is the fast part that is calculated in 1 Cycle on a quantum processor, since it is done using the physical nature of the processor)
  5. If $latex p$ is not even, goto  step 1  ($latex P$ will be even with high probability, this is a deep mathematical number theoretical argument)
  6. Since $latex P$ is the period, we have that $latex x^P \equiv 1 \bmod N$. Further since $latex P$ is even, put “1” in the other side of the previous equality and using (b) above we can factor       $latex (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$  .
  7. Since $latex (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$  this means that the left hand side of the equation leaves 0 residue when divided by $latex N$ (see c) above). This means that at least one of both factors shares a factor with N. This factor is one (or both) of $latex \gcd((x^{P/2}\pm 1),N)$.
Therefore, $latex f=\gcd(x^{P/2}+1) , N)$  OR $latex f=\gcd(x^{P/2}-1),N)$ is a factor of $latex N$ and Voila.

Example, factorizing N=15 using the previous algorithm:

We will factor the number 15 by hand using the previous algorithm.
  1. We pick randomly $latex x=7$
  2. We have that $latex \gcd(15,7) = 1$ therefore, we can stay with our choice of $latex x$ since this $latex x$ does not share factors with $latex N$, we verify this quickly (even that $latex N$ or $latex x$ have thousands of bits) as:
>>> N=15
>>> x=7
>>> from math import gcd
>>> gcd(N,x)
1

  1. We calculate the sequence $latex S=\lbrace 7^0, 7^1, \ldots , 7^N\rbrace \bmod N=15$
>>> N=15
>>> x=7
>>> S=[]
>>> for k in range(0,N+1):
...     S.append((x**k)%N)
...
>>> S
[1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13]

  1. We use the Fourier transform to calculate the period $latex P$ of $latex S$ looking at the frequencies (x coordinates) of the highest amplitudes (y coordinates). We can see this visually below (ignore the high frequency at 0.0 which is infinity and it is a technicality).
Note that the period of $latex S$ seems to be 4 just by looking the sequence $latex S$, but we do not know that, and in real life sequences will be much larger, and this is a toy example.
>>> import numpy as np
>>> S = np.array(S)
>>> fourierS=np.abs(np.fft.fft(S))
>>> freqdomain = np.fft.fftfreq(S.size,d=1)
### WE PLOT THE SIGNAL AND THE FOURIER TRANSFORM OF IT
>>> import matplotlib.pyplot as plt
>>> plt.subplot(2,1,1)
>>> plt.plot(np.arange(S.size), S, 'r--')
>>> plt.subplot(2,1,2)
>>> plt.plot(freqdomain,np.abs(fourierS),'ro')
>>> plt.show()



Look that the frequency coordinate (in the x axis) of one of the highest amplitudes (in the y axis). In the Fourier spectrum, the marked high amplitude has frequency 0.250737 (x coordinate).  Using the highschool formula 1/Freq = Period we have that 1/0.250737  is 3.99  (which is rounded to 4) and this is the highest period $latex P$ of the original signal (we already knew it was 4 but we are literally looking at the frequency through Fourier analysis).   

  1. We saw that the highest amplitude (interpret it as highest length of a period of S, since there are a lot of small periods within our signa, for example 1,7 repeats also or 7,4,13 too with some gaps) has frequency 0.2507 Hz in the Fourier spectrum, and the period P was obtained by 1/T=P as 1/0.2507 which is 3.99 ~= 4 so the highest period P=4.
  1. We calculate  $latex x^{P/2} + 1$ and $latex x^{P/2} - 1$, namely $latex 7^2 + 1$ and $latex 7^2 - 1$  which are 50 and 49 respectively. Further, we check for common factors with $latex N$ (recall by b) and 7. above that $latex x^P \equiv 1 \bmod N$ since the signal has period $latex P$) and therefore $latex x^P-1 = (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$.
>>> P=4
>>> from math import gcd
>>> gcd(x**(int(P/2))+1,N)
5
>>> gcd(x**(int(P/2))-1,N)
3
>>> 


  1. Voila, we have the factors 5 and 3.

There are some technicalities to explain when the signal is cut suddenly at the end without finishing the “wave” , the period needs to be approximated since it wont be exact, but it is a matter of rounding correctly.

A more serious calculation using the fourier spectrum is for a 4 digit number


Using another technique to calculate periods via convolution:



Source code and more information

Source code that finds the periods using Fourier and other implementation with discrete Convolution (faster). Screenshots for more complex factorizations are in http://ff2.nl/quantum-factorization/

Eduardo Ruiz Duarte (beck)
toorandom@gmail.com
twitter: @toorandom

Wednesday, August 01, 2018

The arithmetic geometry of the Fields Medal 2018, perfectoid spaces (part 1/2, Affinoid Spaces)

Today, the fields medal was awarded. One of the recipients is the German director of the Max Planck institute Peter Scholze (he has only 30 years old!). He obtained his Ph.D. inventing and studying his notion of perfectoid spaces which is the topic that I will introduce, but first I will talk about affinoid spaces today.

I have been attending seminars with that is now ex-group of algebraic geometry at the university of Groningen where I made my Ph.D. during the past five months related to overconvergent sheaves and rigid geometry leaded by Jaap Top, Marius van der Put and Stephen Mueller. I learnt there about affinoid spaces and Frobenius structures. I will just define and give some motivation of their invention here and then I will try to give a very brief and informal description of a perfectoid space tomorrow in a continuation of this post.


Why?

One of the main purposes of all these mathematics is to study points on algebraic varieties. For example, is well known by Gerd Faltings  (see here) that the number of solutions of an algebraic curve defined by $latex C(x,y)=0$ of genus $latex g \geq 2$ has a finite number of solutions over any finite extension of $latex \mathbb{Q}$, which we denote by $latex k$. In other words, there is just a finite number of $latex (\tfrac{a}{b},\tfrac{c}{d})$ where $latex a,b,c,d\in O_k$ and $latex c,d\neq 0$ and $latex C(\tfrac{a}{b},\tfrac{c}{d})=0$.

There are bounds for the number of points of $latex C/k$, in fact, if we fix $latex k=\mathbb{Q}$, $latex O_k=\mathbb{Z}$ and $latex C/\mathbb{Q}$ is hyperelliptic, one has that #$latex C(k)\leq 8rg+33(g-1)+1$ where $latex r=\text{rank}(J)$ and $latex J$ is the algebraic group variety associated to the curve $latex C$ which must have rank at most $latex g-3$.  This bound was presented to me in Groningen by professor Michael Stoll from the University of Bayreuth (see here). He uses Chabauty-Coleman integration to obtain this.

The problem is that this bound is very restricted, does not work for varieties of arbitrary dimension, and only works for a very well behaved family of curves (hyperelliptic). For the restriction of $latex r\leq g-3$ there is current hot develpments by Bas Edixhoven, Rene Schoof and others in Leiden using Poincare Torsors on the Neron Severi group of $latex J$.


p-adic numbers (recall)

Consider the non-archimidean field $latex \mathbb{Q}_p$  (here you can construct them using the Cauchy completion of $latex \mathbb{Q}$ under the weird absolute value $latex |x|_p=|p^n\tfrac{a}{b} |_p=p^{-n}$ with $latex p$ prime and $latex a,b\in\mathbb{Z}$ (just as you construct $latex \mathbb{R}$ from the convergent sequences over $latex \mathbb{Q}$. It is handy to represent the elements of $latex \mathbb{Q}_p$ as the "Laurent series" of the form $latex \sum_{i=-m}^\infty a_ip^i\in\mathbb{Q}_p$ where $latex a_i\in\{0,...,p-1\}$ and $latex m\in\mathbb{Z}^+$ (see Theorem 3.4 here).

There is very nice theory that we wont expose here, such that taking the curve $latex C/\mathbb{Q}_p$ can tell us information of $latex C/\mathbb{Q}$. You can imagine this field $latex \mathbb{Q}_p$ as being something that approximates a solution point of $latex C$ over $latex \mathbb{Q}$, since its elements are power series in p, and we will use this "imagination" which is very informal, to indeed, pursue this objective. For the algebrist it is easier to define these numbers. We start with the inverse limit of the rings $latex \mathbb{Z}/p^n\mathbb{Z}$ which we denote by $latex \mathbb{Z}_p$. A p-adic integer $latex m$ is then a sequence $latex (a_n)_{n\geq 1}$ such that $latex a_n$ is in $latex \mathbb{Z}/p^n\mathbb{Z}$. If $latex n \leq m$, then $latex a_n \equiv a_m (\bmod p^n)$. It is easy to check that the ring of fractions of $latex \mathbb{Z}_p$ is in fact what we described before, the field $latex \mathbb{Q}_p$ which has characteristic 0.

Affinoid algebras and spaces.

Consider the field $latex \mathbb{Q}_p$ for some prime $latex p$. Consider the ring of formal power series in the variables $latex x_1,...,x_n$ and the subring $latex \tau_n\subset \mathbb{Q}_p[[x_1,...,x_n]]$ of all the strictly convergent series, that is, if we denote the power series in multi index notation as $latex \sigma:=\sum_{I} c_I x^I$,  then $latex \sigma\in\tau_n$ if and only if $latex |c_I|_p=0$ as $latex I\to \infty$. This give us a feature of $latex \tau_n$, first,... it is a ring and an algebra (prove it). Moreover, every element  $latex \sigma\in\tau_n$ has a norm, $latex ||\sigma||=\sup\{c_I\}_{I}$, making $latex \tau_n$ a Banach $latex \mathbb{Q}_p$-algebra of countable type. So here, we reduced the horribly big ring of formal power series to something which cohomologically will be more "manageable", in fact $latex \tau_n$ is a unique factorization domain with Krull dimension $latex n$.

An affinoid algebra is any $latex A:=\tau_n/(J)$ where $latex J$ is a closed ideal of $latex A$.  An affinoid space $latex X$ is the maximal spectrum of this ring, that is $latex X=\text{Specm}(A)$ (set of maximal ideals of $latex A$, which can be regarded as points).

Imagine that to study $latex C/\mathbb{Q}$ you will consider the space of points $latex X_C:=\text{Specm}\;\tau_2/(C(x,y))$, which can be given many topologies, like the Zariski (very coarse unfortunately), Grothendieck or étale Topology and others.


Tomorrow (I hope) I will continue with perfectoid spaces and I will try to develop an example of how to work with these spaces which allow us to work with "mixed characteristic", namely, characteristic 0 and p.


The geometry of curves over $latex K:= \mathbb{Q}_p$ is very interesting, here, as a matter of morbosity, I leave you of the Berkovich projective line using these ideas for $latex \mathbb{P}^1(K)$.




Eduardo Ruiz Duarte
Twitter: @torandom
PGP: FEE7 F2A0

Tuesday, March 27, 2018

Matemáticas, música y recuerdos

Hoy, en mi trabajo por alguna razón mientras trataba de entender algo un poco abstracto en álgebra, me acordé de mi maestro de piano cuando era niño (1993) y tuve una emoción un poco filosófica y nostálgica. Intenté buscarlo en internet para ver si existía algún registro de él, una foto o una grabación... no tuve éxito. Él vivía de dar conciertos en salones pequeños y de dar clases de canto y piano a niños y adultos en su casa ubicada en el barrio de Coyoacán. No era un virtuoso pero era muy trabajador, muy apasionado y una persona muy noble y pura. Él perfeccionaba cualquier pieza si se lo proponía. Tenía cuatro pianos de cola en su casa. Siempre sacaba piezas nuevas para interpretarlas en conciertos y salones locales en Coyoacán como la Sala Rodolfo Usigli y otros lugares. En su casa tenía una foto de Dolores del Río, era fanático de su belleza. Recuerdo que un sábado por la tarde de un 13 de octubre (era el día de San Eduardo por eso lo recuerdo), después de yo llegar de los "boy scouts", entré a mi casa en la calle de Malintzin en la colonia Del Carmen en Coyoacán y me topé con la sorpresa de que había un piano para mí (de hecho era una pianola). Las clases las tomaba antes de este piano en su casa. Mi madre y él lo escogieron muy cuidadosamente ya que "tenían que estar en perfectísimo estado los martinetes" para darme la gran sorpresa y por fin poder practicar en un instrumento de verdad, lo cual les agradezco infinitamente tanto a mi madre María G. Duarte como a él.
Él me entrenó para entrar a la Escuela Nacional de Música de la UNAM donde estudié piano desde 1996 hasta la huelga (2000). Pude pasar sin ningún problema gracias a que perfeccioné con él el Minueto en Sol Mayor de Johann Sebastian Bach que presenté en mi examen de admisión siendo un niño. Mi maestro tenía un sueño un poco peculiar, que era ir a la casa de Beethoven en Bonn, Alemania. Ahora que lo analizo, iré a Bonn este sábado, entonces tal vez me acordé hoy de mi maestro ya que siempre me decía: "Tú eres bueno en matemáticas porque te gusta tocar el piano" (noten la lógica). Otra anécdota es que solía decír que yo tenía muy "buen oído" y le encantaba al final de mi clase tocar acordes mientras yo miraba hacia otro lado y preguntarme cuáles notas eran las que él estaba tocando. Gracias a él pude interpretar varias melodías de Beethoven, (Sonata Opus 27 no. 2 fue a la que más tiempo le dedicamos), Preludios de Chopin, Mazurkas y varios arreglos de Mozart. Yo siempre era rebelde y quería tocar cosas "modernas". Recuerdo que le insistía en que tocáramos a Di Blassio o Richard Clayderman y él sólo se reía como diciéndome "no seas naco" (obvio él no decía eso pero seguro tenía la intención). Le agradezco mucho el haberme mostrado la belleza de la música clásica. Mi madre siempre le sugirió que vendiera uno de sus grandes pianos para poder viajar a Bonn y conocer a su héroe, pero él los amaba y jamás se quiso deshacer de alguno de ellos.
Falleció en la primavera del 2000 de cáncer prostático, justo cuando ya no podía pagar su casa y mantener sus pianos por culpa de su enfermdad. Había abandonado su casa de Coyoacán para ir a un pequeño departamento en Acoxpa. Como ya no tenía espacio en su nueva casa nos regaló sus macetas de jazmines que florecieron por muchos años.
Su nombre era Aurelio de Alba, era originario de Durango, mi emoción surgió al no encontrar absolutamente nada en internet. No tuvo hijos y sólo tenía un hermano de edad similar que era maestro particular de inglés. Ambos ya no viven. Mi maestro murió primero que su hermano quien vendió todos los pianos ya que no había más qué hacer con ellos. Qué difícil y triste es pensar en el hecho de que ya nadie se acuerde de él más que mi madre y yo; que no haya un sólo registro de sus bellas melodías. ¿Cuántos humanos así han dejado de existir en la mente de todos los que están vivos hoy en día?. Les dejo la melodía que él más amaba y que decenas de veces lo escuché interpretar (Intermezzo de Manuel María Ponce).
Que en Paz descanse maestro Aurelio.

Eduardo



Wednesday, April 19, 2017

Why finding big prime numbers? why study weird arithmetic sequences?

Now I am sitting on my desk thinking on a technique to help me to identify BIG prime numbers in certain arithmetic sequences using algebraic geometry.

This was part of my last project for my PhD, which I think it was very interesting. When I say "BIG" I mean thousands of digits, maybe millions.  When I say "primes in arithmetic sequences" I mean to separate prime numbers in a list like $latex \{ \alpha_n \}_{n=0}^\infty$.

A popular, a prostituted, an important and a "dumb" sequence.

Now we will describe some non trivial sequences and we will see a glimpse of why they are important (or not).

This is of course in my opinion, since there are infinitely many sequences which I ignore and could be more interesting. In fact there is a sequence of "uninteresting numbers" which contains all numbers which appear to not have known/interesting properties (like being prime, Mersenne prime, triangular number, cube, etc...).
But well, this sequence then..., is interesting as is unique, and then we get a paradox.

The popular sequence

The popular is a very famous arithmetic sequence, and is the "Mersenne Sequence", $latex \{ 2^n-1\}_{n=1}^\infty\subset\mathbb{N}$.

$latex \{ 2,7,15,31,63,127,255,...\}$

This is the sequence of all Mersenne numbers.  We denote by $latex M_n$ to the number $latex 2^n-1$.
To identify the primes in this sequence, note that if $latex n=2k$ (is even) then $latex 2^n-1=(2^k-1)(2^k+1)$ and hence... not a prime number. This means that in the sequence we can discard all the values $latex n\in 2\mathbb{Z}$, that is $latex M_{2k}$ is not prime. A less trivial fact is that if $latex n$ is composite, namely $latex n=ab$ then we have that:

 $latex 2^n-1=2^{ab}-1=(2^a-1)(\sum_{k=0}^{b-1}2^{ka})=(2^b-1)(\sum_{k=0}^{a-1}2^{kb})$

and then also $latex M_{pq}$ is not prime. So, we are left with all the elements in the sequence of the form $latex M_p$ for $latex p$ a prime number. A quick inspection says that $latex M_2, M_3, M_5, M_7$ are Mersenne primes. But $latex M_{11} = 2047 =23\cdot 89$ which is not prime. So, which Mersenne numbers are prime ?

This is a difficult question, there are big computer grids working in this, trying to find the most spectacular prime. The biggest Mersenne prime known, (and Biggest Prime in general) is $latex 2^{74207281}-1$. which has 22.3 million digits approximately. The way to check it without putting so much effort in the algebraic geometric or number theory rigor is the following:

 To check that $latex 2^p -1$ is prime:

Consider the sequence $latex \{ \sigma_1=4, \sigma_2=14,...,\sigma_j=(\sigma_{j-1}^2)-2...\}$
then $latex M_p=2^p-1$ is prime if and only if $latex \sigma_{p-1}\equiv 0 \bmod M_p$.

This is the fastest way known today. is called the Lucas-Lehmer test.
There are other elegant tests (but not necessarily faster) using elliptic curves which I knew its existence when I was talking with Benedict Gross at the conference on L-Functions at Harvard the past year, and in some sense I have to do something similar as part of my PhD program.

The prostituted

Another famous and prostituted sequence is the so called "Fibonacci sequence".

$latex \{ 1,1,2,3,5,8,13,...,F_{n-1}+F_{n-2}, ...\} $

This is famous and is always presented as the building blocks of beauty in the universe. This just an exaggeration, but well, that is another story.

Is known that $latex \lim_{n\to\infty} \frac{F_{n}}{F_{n-1}}=\phi=1.618033...$.

This number $latex \phi$ has the property that squared is equal to $latex \phi+1$ so, is appears as a root of the polynomial $latex x^2 -x -1=0$.
The value of $latex \phi$ can be found when you divide lengths of middle lines in some polygons by the length of the sides. Also in your body, if you divide your height by the distance of your feet to your belly button, and in a lot of parts of our body. This number can be analyzed in a Leonardo da Vinci drawing called "Le proporzioni del corpo umano secondo Vitruvio" which can be seen here.
This is why $latex \phi$ has some kind of mystic and esoteric significance for some people, and that is why is called sometimes The Golden Ratio. 

To identify primes in the Fibonacci sequence, there are no good ways. This is mainly because the sequence highly depends on the "addition" operation and not "multiplication", and believe it or not, addition in number theory is a mystery.
A very important Conjecture in mathematics about this mystery, predicts the possible relation between the multiplication and the addition of integers, through its prime factorization, called the abc conjecture, so Fibonacci, is difficult as a problem in terms of primality, but as seen, has more significance in geometry.

The important sequence

Now for the important sequence is this

$latex \{2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344...\}$

Do you see it?

Well, is not too easy to see, is called the "Hardy-Ramanujan sequence", if you denote by $latex \tau(n)$ the $latex n^{th}$ element of the sequence, it means that $latex \tau(n)$ can be written in $latex n$ different ways as a sum of two cubes. Fermat Proved that there are infinitely many of these numbers hundreds of years before, but they caught the attention of Hardy by Ramanujan in a very nice story.

When Ramanujan was dying at the hospital in England, Hardy went to visit him. Hardy told him that the number in his taxi to the hospital was a dull, boring number, 1729. Ramanujan said:

 'No, Hardy, it is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways' 


That is why we use the letter $latex \tau$ because these numbers are called "taxicab numbers" because of this story.

The importance of these numbers, is the new theory in arithmetic geometry that arose,  which in fact I am very interested personally, and professionally.

Practically Ramanujan discovered in his way of thinking, an integral solution to the equation $latex x^3+y^3=z^3+w^3$ which nowadays is studied over $latex \mathbb{Q}$ and then twisted.
This kind of surfaces are called K3 Surfaces (Kodaira-Kummer-Kahler, smooth minimal complete surface with trivial canonical bundle), there is no smart way of obtaining these numbers other than using this algebraic geometry in these surfaces. An example of these surfaces with a family of rational curves parametrized  (the curves may contain taxicab solutions in it) is:

  


And yeah 1729 has the desired property, that is, $latex \tau(2)$ is a sum of two cubes in only two different ways. 
Srnivasa Ramanujan was a human computer, in fact to verify this, we check for the $latex \tau(2)=1729$ and $latex \tau(6)=24153319581254312065344$ can be written as the sum of 2 cubes in 2 and 6 different ways respectively:

$latex \begin{matrix}\tau(2)&=&1729&=&1^3 + 12^3 \\&&&=&9^3 + 10^3\end{matrix}$
...
$latex \begin{matrix}\tau(6)&=&24153319581254312065344&=&582162^3 + 28906206^3 \\&&&=&3064173^3 + 28894803^3 \\&&&=&8519281^3 + 28657487^3 \\&&&=&16218068^3 + 27093208^3 \\&&&=&17492496^3 + 26590452^3 \\&&&=&18289922^3 + 26224366^3\end{matrix}$

The "dumb" sequence

There are plenty other sequences, for example, there are some "dumb" sequences that at the end... they are not so dumb, for example, consider the following sequence:

$latex \{1, 11, 21, 1211, 111221, 312211, 13112221, ... \}$

Do you see the pattern?

Well, the pattern is visual, you begin with "1" and then the following will be the "description of the previous", that is, you ask yourself "What symbols are in the preceding element of the sequence?", and you say "one one" (11) then the next is "two ones"  (21), and so on... This sequence is called "look and say sequence".

There are a lot of things you can do in your spare time with this sequence, for example, prove that a "4" cannot appear in any element of the sequence. The number 13112221 is in fact the biggest prime known in this sequence, are there others?

This apparently dumb sequence has an amazing property which transforms it from dumb to analytic and it was due to John Conway.
Consider the $latex k^{th}$ element of that sequence, call it $latex a_k$  , and define $latex \ell(a_k)=$number of digits of $latex a_k$.
Is proved that $latex \lim_{n\to\infty} \frac{\ell(a_k)}{\ell(a_{k-1})}=\lambda=1.303577269034...$. The surprising thing is that $latex \lambda$ is an algebraic number that can be found as a root of a polynomial of degree 71. This was proved by John Conway, for more information, look at wikipedia.


But why?, why you want to find big primes or classify properties of sequences?


 I have been questioned plenty of times "Why you want to find big primes?", today was one of these days where a master student asked me.
There is a FALSE answer which is very popular among a lot of people, namely

 "It has cryptographic applications, since prime numbers are the basis for today's e-commerce and the development of cryptographic schemes" 

This is false, since cryptographic schemes for public key cryptography need prime numbers with no more than 1000 decimal digits (and this is already too long). Using more than 1000 digits maybe would be more secure, but the speed will decrease exponentially, that is why you don't use 1 million bits of security.

 Identifying these "cryptographic" prime numbers at random with certain properties (Like being a Sophie-Germain prime) to generate a public key with 4096 bits which has approx 1234 digits, (which is already paranoid for the public techniques of cryptanalysis) takes less than a second in my workstation (try: time openssl genrsa 4096).
 So, cryptography is not a good excuse to generate BIG prime numbers, when I say big, I mean thousands of digits, millions.


The answer in my case is easy... To collect them...  they are difficult to find, but they are present in a lot of shapes, for example in the last sequence, which elements are prime ? which is the biggest known ? how to identify them with geometric techniques?.

That is how the theory in mathematics is born, with a question regarding classification.

So, finding big primes is difficult, so is valuable, there are only 49 Mersenne Primes and nobody has proved that they are infinite. (but is believed heuristically that they are).

A couple of years ago I wrote here about finding a big prime of the form $latex 3\cdot 8^n -1$ , which I found here, there are a lot of possible primes disguised in infinitely many shapes, you could just define whatever recursive relation and analyze it.

Other people could say to test a big cluster, or to get some money (yes you get money if you break the records). Maybe an analytic number theorist could say To understand more the distribution of prime numbers which is unknown.

Conclusion

So well in conclusion, I think is good to collect primes and analyze sequences. This to find something hidden in the unknown nature of the logic of sequences of natural numbers, since, we don't know yet how the prime numbers arise. There is still a mystery of how the prime numbers are distributed among all the natural numbers,  even with quantum computers is hard to find them arbitrarily large, so there are still work to do in mathematics.

For more information of all the known published sequences (yes, whatever you think will be there) go to www.oeis.org, this is the Online Encyclopedia of Integer Sequences.


Eduardo Ruíz Duarte (beck)
twitter: @toorandom


Wednesday, September 21, 2016

Dominios de factorización única, enteros Gaussianos y números de Heegner

Recientemente alguien me preguntó algo sobre factorización en anillos y unidades de los anillos, y decidí hacer un post sobre esto, esto es un post básico podría decirse de álgebra conmutativa.

Este post pretende que se comprenda el concepto de factorización en general en cualquier anillo numérico (extensión algebraica de $latex \mathbb{Z}$) a través de ejemplos y explorar, comprender y demostrar propiedades de la factorización de los enteros extendidos con una constante imaginaria (enteros gaussianos).

Todos conocemos el anillo $latex \mathbb{Z}$ que consiste en todos los enteros, y sabemos que los enteros son un subanillo de los números racionales $latex \mathbb{Q}$.

¿Qué es ser entero?, es decir, conocemos el caso particular mencionado anteriormente pero como vimos un  post pasado, hay otros campos que podemos extender.

Lo que queremos investigar es el fenómeno de "factorización única", es decir, en $latex \mathbb{Z}$ no es es muy natural decir que todo entero se puede factorizar en primos de manera única salvo permutación. Pero vamos a ver cómo el concepto de elemento primo es aún más general.


Definición: Un anillo $latex R$ conmutativo le llamamos dominio entero  si cuando ab=0 para $latex a,b\in R$ tenemos que $latex a=0$ o $latex b=0$.
También decimos que un elemento $latex u\in R$ es una unidad si tiene un inverso bajo la multiplicación del anillo $latex R$ , es decir, si existe un $latex u^{-1}$ tal que $latex uu^{-1}=1$. Siempre que todo elemento no cero de $latex R$ sea unidad, diremos que $latex R$ es un campo.

Aquí tenemos que el ejemplo usual $latex \mathbb{Z}$ es un dominio y sus únicos elementos invertibles son el $latex 1,-1$

Otra definición importante es la de irreducibilidad.

Definición: Sea $latex R$ un dominio y $latex a,b\in R$ , $latex a\mid b$ si existe un $latex c$ tal que $latex b=ac$ , es decir $latex a$ divide a $latex b$.  Un elemento no cero $latex p\in R$ es irreducible si no es unidad y si siempre que $latex a\mid p$ tenemos que $latex a$ es una unidad o $latex a=up$ para alguna unidad $latex u$.

Noten que si una unidad la podemos factorizar entonces todo factor debe ser también una unidad, por ejemplo si $latex u=ab$ entonces $latex abu^{-1}=1$ entonces $latex bu^{-1}$ debe ser un inverso de $latex a$ .

Con esto ya tenemos lo necesario para poder definir lo que es factorización única.

Definición: Un dominio $latex R$ tiene factorización única si todo elemento no cero $latex a\in R$ puede ser escrito de manera única como

$latex a=u\prod p_i^{d_i}$

Donde $latex u$ es una unidad y los $latex p_i$ son urreducibles. Nota que uso la palabra irreducible en vez de "primo", en general no son lo mismo, sólo significan lo mismo en los enteros, ya que todo irreducible es primo, pero veremos ejemplos donde no lo es.

Si un anillo cumple la definición única le diremos DFU (Dominio de factorización única)

Ejemplos:

* Los enteros $latex \mathbb{Z}$ son un dominio que no es un campo y sus únicas unidades son el 1 y -1, un entero es irreducible sí y sólo si es un número primo o un número primo negativo. Una consecuencia del teorema fundamental de la aritmética es justamente que $latex \mathbb{Z}$ es un DFU.

* Los campos $latex \mathbb{Q}$ y $latex \mathbb{R}$ son campos, y éstos no tienen irreducibles, por lo tanto son trivialmente un DFU.

*Una familia infinita de dominios la podemos construir si tomamos un entero $latex n\in \mathbb{Z}$ que no sea cuadrado

$latex \mathbb{Z}[\sqrt{n}]=\lbrace a+b\sqrt{n}:a,b\in\mathbb{Z} \rbrace$.

Vamos a profundizar en uno en especial en la siguiente sección cuando $latex n=-1$.

Enteros Gaussianos

Si $latex n=-1$ tenemos la colección de números complejos $latex a+bi$ con $latex a,b\in \mathbb{Z}$, imagínen los puntos de plano complejo o de $latex \mathbb{R}^2$ que tienen coordenadas enteras, es decir una retícula que asemeja cuadrados.

Estos enteros son muy importantes, son $latex \mathbb{Z}[i]$

Estos enteros son como $latex \mathbb{Z}$ pero con algunas cosas raras adicionales, ya que hay más unidades aparte del 1 y -1, también tenemos a $latex i$ y $latex -i$ ya que $latex i\cdot (-i)=1$ .

También tenemos que $latex 2$ es irreducible como un entero en $latex \mathbb{Z}$ pero no como un entero gaussiano en $latex \mathbb{Z}[i]$ ya que $latex 2=(1+i)(1-i)$.

De hecho si un número primo $latex p=a^2 + b^2$ es decir es suma de enteros cuadrados, entonces p no es irreducible como un entero Gaussiano, ya que siempre va a poder factorizarse como $latex p=(a+bi)(a-bi)$. (**)

Vamos a definir lo que es la norma en un anillo en general, pero por ahora, sólo la definiremos para estos enteros que es $latex N(a+bi)=|a+bi|^{2}=a^2 + b^2$, es decir $latex N:\mathbb{Z}[i]\to \mathbb{Z}^{+}$.

La propiedad importante de la norma es que $latex N(wz)=N(w)N(z)$ lo que implica que si $latex u$ es una unidad entonces
$latex 1=N(1)=N(uu^{-1})=N(u)N(u^{-1})$ y como $latex N(u)$ debe ser un entero no negativo por como está definida la norma entonces debe ser 1 forzosamente, por lo que toda unidad tiene norma 1.

 Ahora vamos a examinar la propiedad (**), si $latex p$ es un primo y supongamos que podemos factorizarlo de manera no trivial como $latex p=wz$ en $latex \mathbb{Z}[i]$ , entonces usando la norma sabemos que $latex N(p)=p^2$ por la definición de norma, pero también sabemos que p=wz por lo que $latex N(p)=N(w)N(z)$ por lo que $latex p^2=N(w)N(z)$, como la factorización es no trivial, tenemos que $latex N(w)$ y $latex N(z)$ no son 1 por lo que $latex w,z$ no son unidades, y esto implica que $latex N(w)=N(z)=p$  por lo que si $latex w=\alpha+\beta i$ entonces $latex N(w)=\alpha^2 + \beta^2 = p$ por lo que $latex p$ es suma de dos cuadrados.

Bueno con lo anterior, vemos el poder de la norma, de hecho nos permite diferenciar irreducibles en $latex \mathbb{Z}[i]$ ya que para todo factor $latex p$ de un entero $latex n$ si $latex p$ no es suma de dos cuadrados entonces es irreducible, y si $latex p=a^2  + b^2$ entonces podemos sustituir en la factorización de $latex n$ a las $latex p$ por $latex (a+bi)(a-bi)$ y cada uno de estos factores es irreducible.

Un dato interesante de los enteros gaussianos es que también es un DFU y de hecho con la norma podemos darnos cuenta de toda la factorización en $latex \mathbb{Z}[i]$ ya que todos los irreducibles son los primos $latex p$ que no son suma de dos cuadrados así como todos los $latex a\pm bi$ tal que $latex a^2+b^2$ es un número primo. Para mostrar lo último considera $latex z=a+bi \in \mathbb{Z}[i]$ entonces $latex N(z)=a^2+b^2=z\bar{z}$ (su conjugado) . Como $latex N(z)$ es un entero normal positivo, y sabemos que en $latex \mathbb{Z}$ hay factorización única por lo que todo factor irreducible de $latex z$ debe ser factor de $latex N(z)$  por lo que si $latex N(z)=a^2+b^2$ es primo es irreducible.


¿Quiénes no son DFU?

¿Y qué?, ¿Cuándo no es DFU?,

Para mostrar eso formalmente debería introducir un grupo especial, que se llama grupo de clases de ideales asociado a un anillo, pero eso terminaría con la naturaleza elemental de este post, pero pronto lo haré en una siguiente sección, éste consiste en el cociente del grupo de ideales fraccionarios del campo de fracciones del anillo $latex R$ módulo los ideales principales de $latex R$, este grupo está íntimamente asociado al grupo de Picard de orden 0 de una curva algebraica que se estudia mucho en criptografía pero se ve de manera más "fácil" esto es la generalización pero eso es otro tema.

Hay un problema en matemáticas que estudian los grupos de clases de ideales para saber cuándo hay o no factorización única, de hecho eso lo mide el grupo de clases de ideales en sus elementos ( el area de matemáticas es class field theory), por ejemplo algo raro es que $latex \mathbb{Z}[\sqrt{-5}]$ NO es DFU, pero si consideramos los anillos con raiz cuadrada de $latex n$ que son $latex \mathbb{Z}[\sqrt{-n}]$ para $latex n\in \lbrace 1,2,3,7,11,19,43,67,163 \rbrace$ estos son los ÚNICOS enteros cuya raíz cuadrada imaginaria nos forman un dominio de factorización única, es decir para -5 o -13 no tenemos la propiedad de DFU, y de hecho lo que sucede es que el Class Group asociado al anillo es trivial (tiene un sólo elemento) sí y sólo si el anillo es un DFU.

Esto fue conjeturado por Gauss, probado con errores por Heegner y formalizado por Baker y Stark, de hecho estos 9 números raritos se llaman Números de Heegner.

Esto es impresionante ¿no? , es decir, qué tienen de raro esos 9 números que nos forman anillos con factorización única que otros números primos no puedan hacer... ¿qué hay en la geometría de estas retículas?

Espero les haya gustado

Eduardo Ruíz Duarte (beck)
twitter: @toorandom


Saturday, August 27, 2016

Criptografía asimétrica con curvas elípticas isógenas súpersingulares resistentes a ataques cuánticos

Poco a poco la criptografía como la conocemos está desapareciendo, he hablado con Tanja Lange un par de veces en los congresos que hace la sociedad matemática holandesa y ella parece insistir mucho que estamos ya muy cerca presenciar la existencia de una computadora cuántica, ella afirma que entre el 2024-2030 ya existirá alguna.

Lo relevante es que toda la criptografía actual implementada en los ámbitos económicos, militares y gubernamentales, cuenta con seguridad extrema ante computo clásico como lo conocemos (modelos Von Neumann, Turing...) . El problema es que el modelo de cómputo cuántico rompe todos los algoritmos implementados hoy en día. Esto es debido a la existencia de un algoritmo por Peter Shor que factoriza y calcula logaritmos discretos, es decir, rompe RSA y criptografía basada en el problema de logaritmo discreto (Curvas elípticas) en tiempo polinomial. Esto significará que todos seríamos vulnerables ante el individuo/organización que construya computadora cuántica (IBM, DWave, Google por ejemplo).

Por lo que, las curvas elípticas e hiperelípticas como las implementamos hoy en día, comienzan a ser obsoletas en criptografía, aunque siguen siendo muy útiles para computación en teoría de números algebraica que sirve para hacer nuevos algoritmos, es decir, no estoy diciendo que ya no sirvan las curvas, sino que la criptografía que usa el problema de logaritmo discreto con curvas o variedades abelianas está vulnerado ante la presencia de una computadora cuántica.

En este post les voy a mostrar un análogo de Diffie Hellman que no es vulnerable ante la presencia de un atacante con recursos cuánticos. El post es autocontenido, sólo requieres saber la teoría básica de curvas elípticas la cual la puedes leer en mi blog, recomiendo (aunque no es obligatorio ya que trato de hacerlo autocontenido leer estos artículos aquí en mi blog antes)

Teorema de Hasse en curvas elípticas
Álgebras de endomorfismos en curvas elípticas
j-Invariante en curvas elípticas

El método de Diffie Hellman que funciona bajo cómputo cuántico que describiremos aquí necesita conocimiento de morfismos entre curvas elípticas (isogenias u homomorfismos de los grupos abelianos inducidos por las curvas).
El contenido de este post es el siguiente:

* Background en isogenias y kérneles de éstas antes de irse a lo cuántico.
* Grado de una isogenia

* p-Torsión, j-invariante y características de curvas elípticas súpersingulares
* Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.
* Algoritmo explítico Diffie Hellman con isogenias entre curvas elípticas supersingulares.
* ¿Pero por qué nos enfocamos en súpersingulares?
* ¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis?

Todo esto que escribo fue gracias a la emoción que me causaron las pláticas de Dimitar Jetchev (EPFL, Lausanne, Suiza), Frederik Vercauteren (KU Leuven, Bélgica), Benjamin Smith (INRIA, Francia) y René Schoof (Università di Roma, Italia) en el workshop "Mathematical structures for cryptography" el cual tuve la suerte de poder trabajar con grandes matemáticos del 22-26 de Agosto en Leiden, Países Bajos cuyo objetivo era juntar investigadores en matemáticas y criptografía para resolver problemas abiertos en esta teoría así como la basada en retículas para cómputo cuántico (Lattice Based Cryptography), todos los participantes aportamos algo interesante, y fue una de las más grandes experiencias profesionales que he tenido, aquí hay más información de la gente involucrada http://www.lorentzcenter.nl/lc/web/2016/834/participants.php3?wsid=834&venue=Oort

Comenzamos.

Background en isogenias y kérneles de éstas antes de irse a lo cuántico.

Sea $latex E$ una curva elíptica en forma de Weierstrass sobre un campo finito $latex \mathbb{F}_q$ , es decir $latex E:=\lbrace (x,y)\in \mathbb{F}_q\times\mathbb{F}_q : y^2 = x^3 + ax + b \rbrace$.

Como he explicado en posts anteriores, las curvas elípticas forman un grupo abeliano, es decir, $latex \langle E,\oplus\rangle$ es una estructura donde los puntos se pueden "sumar y restar" , es conmutativa, todos tienen inverso aditivo, es asociativa, cerrada y con elemento neutro $latex \infty$.

Hay fórmulas explícitas para calcular la suma de puntos como en el post anterior mencionado en el párrafo anterior, y también están muy bien explicadas en wikipedia, así que supondré que ya sabemos como funciona la adición elíptica que geométricamente la intuición es con la siguiente imagen:



Isogenias entre curvas 
(mapeos de curvas elípticas, homomorfismos de grupos abelianos inducidos)

Tenemos que si $latex \langle E_1, \oplus\rangle ,\langle E_2,\boxplus \rangle$ son dos curvas elípticas y existe un morfismo $latex \psi:E_1\to E_2$ que respeta la estructura de grupo de cada una, es decir $latex \psi(P\oplus Q)= \phi(P)\boxplus \phi(Q)$ y que mapea el $latex 0$ de una al $latex 0$ de la otra, entonces decimos que ambas son isógenas.

Ahora vamos a ver qué son esos ceros en la curva, ya que no es trivial desde el punto de vista afín.

Kérnel de isogenias

En curvas elípticas tenemos que una isogenia entre dos curvas se ve como $latex \psi(x,y) := (\frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} )$ donde más técnicamente es porque $latex \frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} \in \mathbb{F}_q(E_2)$ es decir son funciones bien definidas en los puntos de la curva en el codominio, son funciones de su campo de funciones (campo de fracciones de la gavilla de funciones del la curva vista como esquema).

Para entender el kérnel de un mapeo como el anterior, necesitamos ver la curva de manera proyectiva, ya que el 0 (cero) en $latex E_1$ y $latex E_2$ no es un punto afín.

Si $latex \psi:E_1\to E_2$ es una isogenia entre curvas elípticas, el kérnel está definido como:

$latex ker\psi := \lbrace P\in E_1 : \psi(P) = \infty_{E_2}\rbrace$

Es decir, todos los puntos que nos mandan al infinito.

Recuerden que las curvas son proyectivas, entonces lo que esto significa exactamente es que si la isogenia está definida por $latex (\frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)})$ entonces podemos proyectivizar estas ecuaciones con una nueva variable $latex z$ (cerradura proyectiva), los puntos que el mapeo manda al infinito veremos a continuación que son justamente donde no están definidas esas funciones racionales sin proyectivizar.

Informalmente pero no incorrectamente, definir la imagen de estos puntos "no definidos bajo $latex \phi$" como $latex \infty_{E_2}$ se hace, deshaciéndose de los denominadores en la isogenia y homogeneizando, eso será la isogenia vista en la cerradura proyectiva de la curva que es $latex zy^2 = x^3 + az^2x + bz^3$ .

Entonces tendremos que los puntos afines de la cerradura proyectiva de la curva están dados por los puntos $latex (x:y:1)$ , es decir, la imagen afín de $latex \psi$ es  $latex (\frac{a_1(x)}{a_2(x)}:y\frac{b_1(x)}{b_2(x)}:1)$ , por lo que entonces la ecuación proyectiva es: $latex (a_1(x)b_2(x):yb_1(x)a_2(x):a_2(x)b_2(x))$ , y todos los puntos $latex (x:y:1)$ donde no está definida la curva afín, justamente estarán bien definidos aquí proyectivamente y esos puntos, son los que tienen imagen al infinito , es decir, que tienen como imagen el punto $latex \infty := (0:1:0)$, y son los puntos en el $latex ker\psi$ incluyendo al $latex \infty_{E_1}$ ya que es requisito de una isogenia mapear infinitos.

Pueden ustedes demostrar de hecho que $latex ker\psi := \lbrace (x,y)\in E_1 : a_2(x)=0\rbrace$ con el hint de que $latex a_2^3 \mid b_2^2$ siempre, y así como que $latex b_2^2\mid f_1a_1^3$ donde $latex f_1$ es la ecuación que define a $latex E_1$ en $latex y^2 = x^3 + a_1x + b_1$, recuerden que esto lo demuestran en el campo de funciones de la curva, es decir tienen que tomar en cuenta la ecuación de la curva al momento de demostrar esto.

Teorema: Si dos curvas elípticas son isógenas sobre un campo finito, entonces tienen el mismo número de puntos.

Grado de una isogenia


Antes de demostrar el teorema, necesitamos entender qué es el grado de una isogenia.

Sea $latex \psi:E_1\to E_2$ una isogenia definida sobre un campo finito $latex \mathbb{F}_q$.

Decimos que el mapeo $latex \psi$ es separable si la extensión de los campos inducida por $latex \mathbb{\psi}$ es separable.

Es decir si $latex \mathbb{F}(E_1)/\psi^{*}\mathbb{F}_q(E_1)$ es separable, y su dimensión como espacio vectorial la usamos para definir:

$latex \text{grad}\psi := dim_{\mathbb{F}_q}(\mathbb{F}_q(E_1)/\psi^{*}\mathbb{F}_q(E_1))=[\mathbb{F}(E_1):\psi^{*}\mathbb{F}_q(E_1)]$

Si esta extensión de campos inducida por $latex \psi$ es separable, decimos que es $latex \psi$ es separable, y una propiedad de isogenias separables es que $latex \text{grad}\psi :=$#$latex ker\psi$.

Pero que no cunda el pánico, vamos a ver cómo encontrar este grado sin meternos en la teoría dura, esto sólo es para definir algo (grado) y luego ver que su cálculo se puede hacer sin tener que calcular bases de espacios vectoriales.

Es fácil demostrar que el grado de la extensión de campos se mide siempre de una manera inocente contando el número de elementos en la imagen inversa de cualquier punto (sin ramificación) en el codominio.

O sea si el grado de $latex \psi$ fuera 1, significa que los espacios vectoriales inducidos por $latex \psi$ son los mismos, por lo que la imagen inversa de cualquier punto tiene sólo 1 punto ya que en este caso $latex \psi$ sería un isomorfismo.

El grado mide qué tan "complejo" es $latex \psi$ , por lo que de hecho el grado de una isogenia está definido también por la cantidad de elementos en la imágen inversa de $latex \psi$ para un punto ordinario general, es decir de $latex \psi^{-1}(Q_{E_2})$ donde $latex Q_{E_2}\in E_2$ es un punto ordinario, es decir no presenta ramificación (Por ejemplo un punto $latex (x,y)$ cuya coordenada $latex x$ no sea raíz de $latex x^3 + ax + b$ , ya que estos puntos son de ramificación, pero no entraremos en eso por ahora).

Como $latex \psi$ es un homomorfismos, tenemos que #$latex \psi^{-1}(Q_{E_2}) =$#$latex ker\psi$, por lo que tenemos otra igualdad más.

De tarea ustedes entonces dicho lo anterior pueden probar que $latex \text{grad}\psi$ es fácilmente calculable ya que si $latex P\in E_1$ y $latex Q:=\psi(P)$ es un punto con coordenadas $latex (s,t)$ en $latex E_2$ entonces #$latex \psi^{-1}(Q)$ es exactamente el número de ceros diferentes del polinomio $latex a_1(x)-sa_2(x)$ pero como $latex \psi$ es separable entonces este polinomio no tendrá raíces repetidas, por lo que #$latex \text{grad}\psi = \text{Deg}(a_1(x)-sa_2(x))=$#$latex ker\psi$.

Demostración de teorema

Dicho todo esto, considera el mapeo $latex \phi_1\in End_{\mathbb{F}_q}(E_1)$ y $latex \phi_2\in End_{\mathbb{F}_q}(E_2)$ tal que si $latex (x_i,y_i) \in E_i$ entonces $latex \phi_i(x_i,y_i) = (x_i^q, y_i^q)$ .

Es decir son los endomorfismos de Frobenius de cada una de las curvas.

Recuerden que queremos demostrar que dos curvas $latex E_1,E_2$ isógenas sobre $latex \mathbb{F}_q$ tienen el mismo números de puntos, y tenemos que la isogenia es $latex \psi:E_1\to E_2$.

Es fácil ver que $latex \psi\circ \phi_1 = \phi_2\circ \psi$, ya que si $latex P:=(x_1,y_1)\in E_1$ y $latex (x_2,y_2):=\phi(P)$ entonces $latex \psi(\phi_1(P)) = \psi(x_1^q,y_1^q)$ y en el otro lado $latex \phi_2(\psi(P)) = \phi_2(x_2,y_2)=(x_2^q,y_2^q)$.

Es decir, en el párrafo anterior afirmo que  $latex (x_2^q,y_2^q) = \psi(x_1^q,y_1^q)$, ya que recuerden que $latex \psi$ está formada por funciones racionales en $latex x$ y en $latex y$, entonces es un ejercicio de álgebra básica demostrar que si $latex r(x)$ es un polinomio sobre un campo finito entonces $latex r^q(x)=r(x^q)$, es decir se cumple el sueño de todo niño de secundaria, que por ejemplo si $latex x+y\in \mathbb{F}_q(x,y)$ entonces $latex \phi(x+y)=(x+y)^q = x^q + y^q$.

Entonces con toda mi informalidad que me caracteriza, tenemos ya que $latex \psi\circ \phi_1 = \phi_2\circ \psi$

Por lo que como la operación $latex \circ$ de composición en $latex End_{\mathbb{F}_q}(E_i)$ es distributiva, podemos inferir que:

$latex \psi\circ (\mathbbm{1}_{E_1} - \phi_1) = (\mathbbm{1}_{E_2}- \phi_2)\circ \psi$   (*)

Tal que $latex \mathbbm{1}_{E_i}$ es el mapeo de identidad en $latex End_{\mathbb{F}_q}(E_i)$ .

Calculemos el grado de  (*) .

Sabemos que el $latex \text{grad}\psi_1\circ \psi_2 = \text{grad}\psi_1\cdot \text{grad}\psi_2$ , esto lo pueden demostrar usando mi demostración anterior de que el grado de una isogenia está directamente relacionado con el grado de un polinomio dado por el mapeo, y pues al componerlos, el grado incrementa multiplicativamente.

También tenemos que el grado de $latex \mathbbm{1}_{E_i}-\phi_i$, como es un mapeo separable, es el número de elementos en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$... Pregunta ¿quién está en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$?

Recordemos que el endomorfismo de Frobenius tiene una propiedad interesante, es decir, si tenemos que $latex \mathbb{F}_{p^n}$ es un campo finito, y definimos para todo $latex x\in \mathbb{F}_{p^n}$ el mapeo $latex \phi_m(x) := x^{p^m}$ entonces $latex \phi_m(x)=x$ sí y sólo sí $latex x\in \mathbb{F}_{q^m}$ por lo que $latex x\in \overline{\mathbb{F}_p}$  es $latex \mathbb{F}_{p^m}$-racional si $latex \phi_m(x)=x$ , es decir, donde el endomorfismo de Frobenius se comporta como la identidad, nos caracteriza a los puntos racionales.

Entonces el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$ son los puntos $latex (x_i,y_i)\in E_i$ que son iguales ante Frobenius y ante la identidad... es decir, puntos racionales $latex \mathbb{F}_q$-racionales.

Con lo anterior tenemos que  $latex \text{grad} (\mathbbm{1}_{E_i}-\phi_i)=$#$latex E_i$ .
Con esto tenemos tenemos que el grado de (*) es:

$latex \text{grad}\psi\cdot$#$latex E_1 = \text{grad}\psi\cdot$#$latex E_2$ por lo que #$latex E_1=$#$latex E_2$. q.e.d. $latex \blacksquare$.


p-Torsión, j-invariante y características de curvas elípticas súpersingulares

Definición: $latex E/\mathbb{F}_{p^n}$ una curva elíptica, entonces definimos la n-torsión de la curva como:

$latex E[n] := \lbrace P\in E : nP=\infty \rbrace$


Es decir, los puntos que al sumarse $latex n$ veces, se anulan.

Definición: Sea $latex E/\mathbb{F}_{p^n}$ entonces decimos que $latex E$ es ordinaria si $latex E[p]\cong \mathbb{Z}/(p)$ y es supersingular si $latex E[p]\cong\lbrace\infty\rbrace$.

Es decir, si no tiene p-torsión más que la trivial, le llamamos supersingular.

La palabra "supersingular" no tiene nada que ver con "singular", ya que una curva es singular si tiene singularidades, pero una curva elíptica por definición no es singular, es decir, no tiene puntos raros (discriminante de la curva es distinto de cero), ni tampoco raices repetidas.

La palabra supersingular es porque realmente son excepcionales,  y de hecho una cosa interesante de estas curvas es que SIEMPRE están bien definidas sobre $latex \mathbb{F}_{p^2}$ para cualquier $latex p$ , es decir, al reducir una ecuación de una curva a $latex \mathbb{F}_{p^2}$ nunca presentará singularidades.


Ahora vamos a ver otra definición importante que justamente será usada por el protocolo Diffie-Hellman.

Definición: Definimos el j-invariante de una curva elíptica $latex E/k$ donde $latex k$ es cualquier campo de caracteristica mayor que 3 y la forma de Weierstrass de $latex E$ es $latex y^2=x^3 + ax+b$ lo definimos como:


$latex j(E):=1728 \frac{4a^3}{4a^3+27b^2}$

Esta función loquita es muy importante en análisis complejo, y se preguntarán de donde sale ese 1728. Primero necesitamos saber para qué es esto.

El j-invariante tiene la propiedad de que si dos curvas tienen el mismo j-invariante, es decir $latex j(E_1)=j(E_2)$ entonces tenemos que $latex E_1\cong E_2$ sobre su campo de definición $latex k$.

Noten que el denominador del j-invariante nunca es 0, ya que es justamente el discriminante de $latex x^3 + ax+b$ y este no es cero porque sino la curva tendría singularidades y por definición una curva elíptica no es singular.

Otro teorema importante es que para todo $latex j_0\in k$ existe una curva elíptica $latex E_{j_0}$ tal que $latex j(E_{j_0})$ por lo que automáticamente podemos inferir que sobre cualquier campo... el moduli de TODAS las curvas elípticas sobre cualquier campo finito o infinito... es unidimensional... es decir, todas las curvas elípticas forman una línea.

Otros teoremas importantes es que los endomorfismos extendidos a $latex \mathbb{Q}$ definido como $latex End_0(E):= End_k(E)\otimes_{k}\mathbb{Q}$ cuando $latex E$ es supersingular, forman una álgebra de cuaternios, es decir no es conmutativa.

En el caso ordinario donde $latex E$ no sea supersingular , tenemos que $latex End_0(E)$ siempre es una extensión cuadrática de $latex Q$ compleja, es decir $latex End_0(E)\cong \mathbb{Q}(\sqrt{d})$  con $latex d$ negativo y libre de cuadrados.


Corolario: Sea $latex E/\mathbb{F}_q$ una curva elíptica supersingular, entonces #$latexE(\mathbb{F}_q)=p+1$.

Demostración:

No lo haré, pero usen el teorema de Hasse, deduzcan que si la curva es supersingular, entonces la traza del endomorfismo de frobenius es 0, todo esto se puede demostrar con lo anterior.

Teorema: Sea $latex \psi:E_1\to E_2$ una isogenia tal que $latex E_1$ es súpersingular, entonces $latex E_2$ también es supersingular.

Lo mismo aplica para curvas ordinarias, es decir, los dos tipos de curvas, súpersingulares y ordinarias sólo "se llevan" entre sus respectivas categorías, esto es importante, porque el protocolo que describiré pronto asegura que todas las isogenias serán entre curvas súpersingulares.

Pero antes veamos cómo construir isogenias cuyo kernel sea el subgrupo del dominio de la isogenia, es decir, dado un $latex H_P\subset E$ un subgrupo de una curva elíptica sobre un campo finito, en este caso $latex H_P$ es el generado por $latex P$ , construiremos explícitamente $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P=H_P$ y la ecuación explícita de $latex E_P$.

Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.

Recuerden que #$latex E(\mathbb{F}_q)=N$ es finito, ya que el campo de definición es finito.
Entonces por el teorema de lagrange, sabemos que la información de sus subgrupos está escondida en la factorización de $latex N$.


Sea $latex P\in E$, definimos el subgrupo $latex H_P\subsetneq E$ como:

$latex H_P:=\lbrace nP : n \in \mathbb{Z}\rbrace$

Este es el grupo de "todos los múltiplos de $latex P$:" en la curva, es trivial que es un subgrupo de $latex E$.

Vamos ahora a construir una isogenia asociada a $latex P\in E$ que denotamos por $latex \psi_P$ cuyo kernel sea $latex H_P$ hacia otra curva que denotaremos como $latex E_P$.

Es decir vamos a construir $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P = H_P$
Todos sabemos que el kérnel de un morfismo de grupos es un subgrupo normal del grupo, así que esto no debe causarles conflicto.


La notación de las coordenadas para los puntos en $latex \langle E,\oplus\rangle$  será $latex P:=(x_P,y_P), Q:=(x_Q,y_Q), P\oplus Q:=(x_{P+Q},y_{P+Q})$.

Definición-Teorema-Vélu: Sea $latex \langle E/\mathbb{F}_q,\oplus\rangle$ una curva elíptica y $latex P_0\in E$, tal que $latex y^2 = x^3 + ax + b$ construyamos como vimos anteriormente el grupo generado por los "múltiplos de $latex P_0$" , $latex H_{P_0}$.

Entonces tenemos que para todo $latex P\notin H_{P_0}$:

$latex \psi_{P_0}:E\to E_{P_0}$
           $latex P\mapsto \Big( x_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(x_{P+Q}-x_Q), y_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(y_{P+Q}-y_Q)\Big)$

Y si $latex P\in H_{P_0}$ definimos $latex \psi_{P_0}(P)=\infty$.


Es fácil mostrar que $latex ker\psi_{P_0}:=H_{P_0}$ , de hecho, ústedes háganlo y verán como todo se reduce a hacer matemáticas lindas, no es tan difícil.

Pero bueno, esta función $latex \psi_{P_0}$ no está dada por la forma que mostrarmos al principio, es decir por la isogenia definida con los polinomios $latex \big( \frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)} \big)$.

Pero Dustim Moody y Daniel Shumow ya lo hicieron en la sección 2.3 de un paper, aquí dejo su páper , así que ya tenemos la isogenia explícita, y de hecho en ese mismo paper se describe la ecuación de la curva $latex E_{P_0}$ la cual es $latex y^2 = x^3 + (a-5v)x + (b-7w)$ donde $latex v,w$ son constantes que dependen de $latex H_{P_0}$ y son explícitamente calculables.

Ahora sí, el algoritmo

Algoritmo explícito Diffie Hellman con isogenias entre curvas elípticas supersingulares.



Considera una curva elíptica supersingular $latex E$ definida sobre $latex \mathbb{F}_{p^2}$  tal que $latex p=w_A^{e_A}\cdot w_B^{e_B}\cdot f \pm 1$, es decir es un número primo especial, donde $latex w_A,w_B$ son números primos chicos y $latex f$ es cualquier entero, así como $latex e_A,e_B$ los cuales se escogerán de tamaños parecidos y tal que $latex p$ cumpla el nivel de seguridad requerido en bits para este esquema, que está probado que es aproximadamente de 3000 bits (referencia aquí). Entonces con todo lo que dijimos en la sección de curvas súpersingulares es fácil inferir que el tamaño de la curva está dado por #$latex E(\mathbb{F}_{p^2})=(p\pm 1)^2$.

Sean A=Artemisa y B=Boris , dos personas que desean intercambiar una llave en un canal no seguro intervenido por un atacante con recursos cuánticos.

Entonces ellos harán lo siguiente:

Algoritmo SIDH (Supersingular Isogeny Diffie-Hellman)

Públicamente harán lo siguiente: 

Se ponen de acuerdo en los siguiente: $latex p=w_A^{e_A}\cdot \w_B^{e_B}\cdot f \pm 1,\langle E/\mathbb{F}_{p^2},\oplus\rangle,P_A,Q_A,P_B,Q_B\in E$ tal que $latex E$ es súpersingular.
donde intercambiar una curva $latex E/\mathbb{F}_{p^2}$ equivale a mandar $latex \lbrace a,b\rbrace$ tal que $latex y^2 = x^3 + ax+b$.

Tenemos que $latex P_A,Q_A$ y $latex P_B,Q_B$ fueron escogidos tal que tienen orden $latex w_A^{e_A}$ y $latex w_B^{e_B}$ respectivamente, lo cual es fácil por el número primo que construimos.


Vamos a denotar por nA, nB, el paso $latex n$ que tiene que hacer Artemisa o Boris respectivamente,.

Protocolo:

1A: A genera dos números aleatorios $latex m_A,n_A$ < $latex w_A^{e_A}$
2A: A genera $latex R_A := m_A\cdot P_A \oplus n_A\cdot Q_A$ (secreto)
3A: A usa el punto $latex R_A$ para crear el subgrupo $latex H_{R_A}$ que funcionará como kernel del mapeo $latex \psi_{A}:E\to E_A$, por lo que ya tiene $latex R_A,\psi_{A},E_A$ donde los últimos dos son gracias a las fórmulas de Vélu mostradas en la sección anterior.
4A: A forma los puntos $latex \psi_{A}(P_B)$ y $latex \psi_{A}(Q_B)$ con su isogenia creada en el paso anterior.
5A: A le manda a B $latex \lbrace E_A,\psi_A(P_B),\psi_A(Q_B)\rbrace$
Pero NO le manda la isogenia, sino la imagen de los puntos bajo la isogenia secreta $latex \psi_A$

1B-4B: Ahora Boris hace los mismos primeros 4 que Artemisa, sólo intercambiamos las letras de los subscripts A por B

5B: B manda a A $latex \lbrace E_B,\psi_B(P_A),\psi_B(Q_A)\rbrace$
6A: A tiene $latex m_A,n_A,\psi_B(P_A),\psi_B(Q_A)$ y forma el punto $latex S_{BA}:=m_A\cdot\psi_B(P_A)\oplus n_A\cdot\psi_B(Q_A)$.
7A: A usa el punto para generar la isogenia $latex \psi_{BA}$ usando fórmula de Vélu, así como la imagen de la isogenia que será la nueva curva $latex E_{BA}$ que es isógena a $latex E$ gracias a $latex \psi_{BA}$.
8A. A calcula el j-invariante  de la curva $latex E_{BA}$ que será $latex \kappa:=j(E_{BA})$.
6B: Similarmente al paso 6A, Boris tiene $latex m_B,n_B,\psi_A(P_B),\psi_A(Q_B)$ por lo que forma el punto $latex S_{AB}:=m_B\cdot\psi_A(P_B)\oplus n_B\cdot\psi_A(Q_B)$.
7B: Boris usa el punto $latex S_{AB}$ para generar la isogenia con las fórmulas de Velú asociada al subgrupo generado por $latex S_{AB}$ , esta isogenia es $latex \psi_{AB}$ y genera también el codominio de esta isogenia que es la curva $latex E_{AB}$ que es isógena a $latex E$ gracias a $latex \psi_{AB}$.
8B: B calcula el j-invariante de la curva $latex E_{AB}$ que será $latex \kappa:=j(E_{AB})$.

Las curvas $latex E_{AB}$ y $latex E_{BA}$ son isomorfas, ustedes lo pueden demostrar si hacen todo el diagrama, por lo que el j-invariante será el mismo, y ya ambos pueden usar como password $latex  \text{Hash}(\kappa)$ o cualquier función en Kappa.

¿Pero por qué nos enfocamos en súpersingulares?

La verdad nunca usamos nada de las características supersingulares... Pero recuerden que el álgebra de endomorfismos de una curva elíptica supersingular NO es conmutativa, ya que es isomorfa a un álgebra de cuaternios.

Existe un ataque, que resuelve el problema "difícil" en el que está basado este protocolo en tiempo subexponencial cuántico. El algoritmo está descrito en este paper por Andrew M. Childs, David Jao y Vladimir Soukharev.  El cuál hace uso extenso de la CONMUTATIVIDAD del anillo de endomorfismos de la curva elíptica para resolver subexponencialmente el "Abelian Hidden Shift Problem" que es el nombre del problema que hace seguro al algoritmo descrito en la sección anterior.

Por lo que debemos enfocarnos a curvas cuyo anillo de endomorismos no sea conmutativo... es decir... súpersingulares.

¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis a este algoritmo?


Lo que hay que romper es el "Abelian Hidden Shift Problem".  Algo así en español como "Problema oculto de desplazamiento oculto", ya que lo que estamos haciendo en el algoritmo anterior, es desplazar grupos, y adquireir nuevas curvas "desplazando" con puntos nuevos.

Este problema en general consta de lo siguiente.

-Sea $latex A$ un grupo abeliano finito.
-Sea $latex S$ un conjunto finito.
-Sea $latex f:A\to S$ y $latex g:A\to S$ dos funciones inyectivas.
-Existe una $latex b\in A$ tal que para todo $latex x\in A$ tenemos que $latex f(x)=g(xb)$
-El valor que un atacante quisiera saber es $latex b$.

Vamos a reformular esto en términos de curvas elípticas de manera básica.

-Tenemos dos curvas isógenas $latex E,\hat{E}$
-Decimos que $latex f_0(a)=a*E$ y $latex f_1(a)=a*\hat{E}$.
-Entonces $latex b*E=\hat{E}$
-También $latex f_1(a)=a*\hat{E}=a*b*E=f_0(ab)$

Resolver el Abelian Hidden Shift Problem en $latex f_0$ y $latex f_1$ es descubrir $latex b$.

Esto realmente significa calcular la acción en las curvas elípticas

Dicho esto, SIDH con curvas elípticas súpersingulares, la seguridad se obtiene es con llaves de 3000 bits para obtener seguridad cuántica exponencial de 128 bits, la cual es más que suficiente.

Esto es todo por hoy, ahora saben cómo implementar un algoritmo que tenga seguridad cuántica.

Espero les haya gustado.

Más información, pueden ver el paper original de Luca De Feo, David Jao y Jerome Plut.
https://eprint.iacr.org/2011/506.pdf


Eduardo Ruíz Duarte (beck)
Twitter: @toorandom