root of n. Okay, so that's the end of ou r derivation. So now we know that the first

absolute value is less than one over two d square - square root of n. The second

absolute value is less than one over square root of n and therefore the sum is

less than one over two d squared. And this is the expression that I want you to stare

at, so here let me circle it a little bit. So, let me circle this part And this part.

Now so let's stir a little bit of a distraction here and what we see is first

of all as before. Now we know the value of e / n and what we'd like to find out is

the value k / d. But what do we know about this fraction k over d? We know somehow

that the difference of these two fractions is really small, it's less than one over

two d squared. Now this turns out to happen very and frequently that k over d.

Approximate e over n so well That the distance between the two is less than the

square of the denominator of k over d. It turns out that, that can happen very

often. It turns out there are very few fractions of the form k / d than

approximate another fraction so well that their difference is less than one of the

2d squared. And in fact the number of such factions is gonna be most logarithmic in

n. So now there's a continued fraction of algorithm. It's a very famous fraction

that basically what it would do Si from the fraction e / n it would recover and

possible candidate for k / d so we just try them all one by one until we find the

direct k / over d. And then we're done. We're done because we know that well e d

is one [inaudible] k, therefore, d is relatively prime to k. So if we just

represent k over d as a rational fraction, you know? Numerator by denominator, then

denominator must be d. And so we've just recovered, you know? We've tried all

possible log in fractions that approximate e over n so well that the difference is

less than one over 2d squared and then we just look at the denominator of all of

those fractions and one of those denominators must be d and then we're

done, we're just recovered the private key. So this is a pretty huge attack and

it shows basically how if the private exponent is small, smaller than the fourth

root of n, then we can recover d completely and quite easily. Okay. So,

De acuerdo, así que vamos a usar esta desigualdad en sólo un minuto.

Pero ahora vamos a emézar usando el hecho de que sabemos algo de d,

a saber que d es pequeña. Así que si vemo esta desigualdad aquí,

d es menor que la raíz cuadrada de N dividida entre 3.

Es en realidad bastante fácil de ver si cuadro ambos lados.

y sólo manipulo las cosas un poquito, [no] es difícil de ver que

esto implica directamente la siguiente relación,

básicamente 1 sobre 2 d cuadrada menos e sobre raíz cuadrada de N es mayor que 3 sobre raíz cuadrada de N.

Como dije, esto básicamente continúa cuadrando ambos lados, luego tomando la

inversa de ambos lados, y entonces supongo multiplicar un lado y medio.

Bien, así que pueden fácilmene derivar esta relación, y necesitaremos esta relación en sólo un minuto.

Por lo que vamos a ver, lo que me gustaría hacer es ligar

la diferencia de e sobre N y k sobre d. Bueno, ¿qué sabemos?

Según la desigualdad triangular, sabemos que esto es igual a

la distancia entre e sobre N y e sobre phi(N) más

la distancia de e sobre phi(N) a k sobre d.

Esto es lo que se llama una desigualdad triangular; esta es sólo una propiedad de valores absolutos.

Entonces este valor absoluto de aquí, ya sabemos como ligarlo.

Si piensan en eso es básicamente la liga que ya hemos derivado.

Así que sabemos que este valor absoluto aquí es básicamente menor que 1 sobre raíz cuadrada de N.

Entonces ¿que sabemos de este valor absoluto de aquí? ¿Qué es e sobre N menos e sobre phi(N)?

Bueno vamos a hacer denominadores comunes y veremos lo que obtenemos.

Por lo tanto el común denominador va a se N veces phi(N).

y el numerador en este caso va a ser e veces phi(N) menos N.

Que sabemos de esta expresión aqui es menor que 3 veces raíz cuadrada de N.

Entonces en realidad este numerador va a ser e veces 3 raíz cuadrada de N.

El numerador va a ser menor que e veces 3 raíz cuadrada de N.

Así que ahora sabemos que es menor que phi(N), por lo que sé que e sobre phi(N) es menor que 1.

En otras palabras, si borro e y borro phi(N) sólo ha hecho más larga la fracción.

Bien, así que este valor inicial absoluto entonces va a ser

más pequeña que 3 sobre raíz cuadrada de N sobre N, lo cual es simplemente,

3 raíz cuadrada de N sobre N es simplemente 3 sobre raíz cuadrada de N.

Bien, pero ¿qué sabemos de 3 sobre raíz cuadrada de N?

Sabemos que es menos que 1 sobre 2 d cuadrada menos 1 sobre raíz cuadrada de N.

Bien, por lo tanto este es el fina de nuestra derivación.

Así que entonces sabemos que el primer valor absoluto es menor que 1 sobre 2 d cuadrada menos raíz cuadrada de N.

el segundo valor absluto es menor que 1 sobre raíz cuadrada de N.

Y por lo tanto su suma es menor que 1 sobre 2 d cuadrada.

Y esta es la expresión que quiero mirar fijamente.

Entonces aquí, déjenme hacer un círculo alrededor un poco. Así que déjenme hacer un círculo en esta parte y esta parte.