Funcionamiento del algoritmo ECDSA por KAKAROTO:
Following up on his status update for the PS3 4.0 Homebrew Enabler (HEN), today Sony PlayStation 3 hacker KaKaRoToKS has explained how the ECDSA algorithm works.
To quote: To popular demand, I have decided to try and explain how the ECDSA algorithm works. I've been struggling a bit to understand it properly and while I found a lot of documentation about it, I haven't really found any "ECDSA for newbies" anywhere.
So I thought it would be good to explain in simple terms how it works so others can learn from my research. I have found some websites that explain the basic principles but nowhere near enough to actually understand it, others that explains things without any basics, making it incomprehensible, and others that go way too deep into the the mathematics behind it.
ECDSA stands for "Elliptic Curve Digital Signature Algorithm", it's used to create a digital signature of data (a file for example) in order to allow you to verify its authenticity without compromising its security. Think of it like a real signature, you can recognize someone's signature, but you can't forge it without others knowing.
The ECDSA algorithm is basically all about mathematics.. so I think it's important to start by saying : "hey kids, don't slack off at school, listen to your teachers, that stuff might be useful for you some day!" But these maths are fairly complicated, so while I'll try to vulgarize it and make it understandable for non technical people, you will still probably need some knowledge in mathematics to understand it properly.
I will do this in two parts, one that is a sort of high level explanation about how it works, and another where I dig deeper into its inner workings to complete your understanding. Note however that I've just recently learned this stuff, so I'm definitely not an expert on the matter.
So the principle is simple, you have a mathematical equation which draws a curve on a graph, and you choose a random point on that curve and consider that your point of origin. Then you generate a random number, this is your private key, you do some magical mathematical equation using that random number and that "point of origin" and you get a second point on the curve, that's your public key. When you want to sign a file, you will use this private key (the random number) with a hash of the file (a unique number to represent the file) into a magical equation and that will give you your signature. The signature itself is divided into two parts, called R and S.
In order to verify that the signature is correct, you only need the public key (that point on the curve that was generated using the private key) and you put that into another magical equation with one part of the signature (S), and if it was signed correctly using the the private key, it will give you the other part of the signature (R). So to make it short, a signature consists of two numbers, R and S, and you use a private key to generate R and S, and if a mathematical equation using the public key and S gives you R, then the signature is valid. There is no way to know the private key or to create a signature using only the public key.
Alright, now for the more in depth understanding, I suggest you take an aspirin right now as this might hurt!
Let's start with the basics (which may be boring for people who know about it, but is mandatory for those who don't) : ECDSA uses only integer mathematics, there are no floating points (this means possible values are 1, 2, 3, etc.. but not 1.5..), also, the range of the numbers is bound by how many bits are used in the signature (more bits means higher numbers, means more security as it becomes harder to 'guess' the critical numbers used in the equation), as you should know, computers use 'bits' to represent data, a bit is a 'digit' in binary notation (0 and 1) and 8 bits represent one byte.
Every time you add one bit, the maximum number that can be represented doubles, with 4 bits you can represent values 0 to 15 (for a total of 16 possible values), with 5 bits, you can represent 32 values, with 6 bits, you can represent 64 values, etc.. one byte (8 bits) can represent 256 values, and 32 bits can represent 4294967296 values (4 Giga).. Usually ECDSA will use 160 bits total, so that makes well, a very huge number with 49 digits in it
ECDSA is used with a SHA1 cryptographic hash of the message to sign (the file). A hash is simply another mathematical equation that you apply on every byte of data which will give you a number that is unique to your data. Like for example, the sum of the values of all bytes may be considered a very dumb hash function.
So if anything changes in the message (the file) then the hash will be completely different. In the case of the SHA1 hash algorithm, it will always be 20 bytes (160 bits). It's very useful to validate that a file has not been modified or corrupted, you get the 20 bytes hash for a file of any size, and you can easily recalculate that hash to make sure it matches. What ECDSA signs is actually that hash, so if the data changes, the hash changes, and the signature isn't valid anymore.
Now, how does it work? Well Elliptic Curve cryptography is based on an equation of the form : y^2 = (x^3 + a * x + b) mod p
First thing you notice is that there is a modulo and that the 'y' is a square. This means that for any x coordinate, you will have two values of y and that the curve is symmetric on the X axis. The modulo is a prime number and makes sure that all the values are within our range of 160 bits and it allows the use of "modular square root" and "modular multiplicative inverse" mathematics which make calculating stuff easier (I think).
Since we have a modulo (p) , it means that the possible values of y^2 are between 0 and p-1, which gives us p total possible values. However, since we are dealing with integers, only a smaller subset of those values will be a "perfect square" (the square value of two integers), which gives us N possible points on the curve where N < p (N being the number of perfect squares between 0 and p). Since each x will yield two points (positive and negative values of the square-root of y^2), this means that there are N/2 possible 'x' coordinates that are valid and that give a point on the curve.
So this elliptic curve has a finite number of points on it, and it's all because of the integer calculations and the modulus. Another thing you need to know about Elliptic curves, is the notion of "point addition". It is defined as adding one point P to another point Q will lead to a point S such that if you draw a line from P to Q, it will intersect the curve on a third point R which is the negative value of S (remember that the curve is symmetric on the X axis). In this case, we define R = -S to represent the symmetrical point of R on the X axis. This is easier to illustrate with an image :
So you can see a curve of the form y^2 = x^3 + ax + b (where a = -4 and b = 0), which is symmetric on the X axis, and where P+Q is the symmetrical point through X of the point R which is the third intersection of a line going from P to Q. In the same manner, if you do P + P, it will be the symmetrical point of R which is the intersection of the line that is a tangent to the point P.. And P + P + P is the addition between the resulting point of P+P with the point P since P + P + P can be written as (P+P) + P.. This defines the "point multiplication" where k*P is the addition of the point P to itself k times here are two examples showing this :
Here, you can see two elliptic curves, and a point P from which you draw the tangent, it intersects the curve with a third point, and its symmetric point it 2P, then from there, you draw a line from 2P and P and it will intersect the curve, and the symmetrical point is 3P. etc you can keep doing that for the point multiplication. You can also already guess why you need to take the symmetric point of R when doing the addition, otherwise, multiple additions of the same point will always give the same line and the same three intersections.
One particularity of this point multiplication is that if you have a point R = k*P, where you know R and you know P, there is no way to find out what the value of 'k' is. Since there is no point subtraction or point division, you cannot just resolve k = R/P. Also, since you could be doing millions of point additions, you will just end up on another point on the curve, and you'd have no way of knowing "how" you got there. You can't reverse this operation, and you can't find the value 'k' which was multiplied with your point P to give you the resulting point R.
This thing where you can't find the multiplicand even when you know the original and destination points is the whole basis of the security behind the ECDSA algorithm, and the principle is called a "trap door function".
Now that we've handled the "basics", let's talk about the actual ECDSA signature algorithm. For ECDSA, you first need to know your curve parameters, those are a, b, p, N and G. You already know that 'a' and 'b' are the parameters of the curve function (y^2 = x^3 + ax + b), that 'p' is the prime modulus, and that 'N' is the number of points of the curve, but there is also 'G' that is needed for ECDSA, and it represents a 'reference point' or a point of origin if you prefer.
Those curve parameters are important and without knowing them, you obviously can't sign or verify a signature. Yes, verifying a signature isn't just about knowing the public key, you also need to know the curve parameters for which this public key is derived from.
So first of all, you will have a private and a public key.. the private key is a random number (of 20 bytes) that is generated, and the public key is a point on the curve generated from the point multiplication of G with the private key. We set 'dA' as the private key (random number) and 'Qa' as the public key (a point), so we have : Qa = dA * G (where G is the point of reference in the curve parameters).
So how do you sign a file/message ? First, you need to know that the signature is 40 bytes and is represented by two values of 20 bytes each, the first one is called R and the second one is called S.. so the pair (R, S) together is your ECDSA signature.. now here's how you can create those two values in order to sign a file.. first you must generate a random value 'k' (of 20 byes), and use point multiplication to calculate the point P=k*G. That point's x value will represent 'R'. Since the point on the curve P is represented by its (x, y) coordinates (each being 20 bytes long), you only need the 'x' value (20 bytes) for the signature, and that value will be called 'R'. Now all you need is the 'S' value.
To calculate S, you must make a SHA1 hash of the message, this gives you a 20 bytes value that you will consider as a very huge integer number and we'll call it 'z'. Now you can calculate S using the equation : S = k^-1 (z + dA * R) mod p
Note here the k^-1 which is the 'modular multiplicative inverse' of k it's basically the inverse of k, but since we are dealing with integer numbers, then that's not possible, so it's a number such that (k^-1 * k ) mod p is equal to 1. And again, I remind you that k is the random number used to generate R, z is the hash of the message to sign, dA is the private key and R is the x coordinate of k*G (where G is the point of origin of the curve parameters).
Now that you have your signature, you want to verify it, it's also quite simple, and you only need the public key (and curve parameters of course) to do that. You use this equation to calculate a point P : P= S^-1*z*G + S^-1 * R * Qa
If the x coordinate of the point P is equal to R, that means that the signature is valid, otherwise it's not.
Pretty simple, huh? now let's see why and how and this is going to require some mathematics to verify : We have :
P = S^-1*z*G + S^-1 * R *Qa
but Qa = dA*G, so:
P = S^-1*z*G + S^-1 * R * dA*G = S^-1 (z + dA* R) * G
But the x coordinate of P must match R and R is the x coordinate of k * G, which means that :
k*G = S^-1 (z + dA * R) *G
we can simplify by removing G which gives us :
k = S^-1(z + dA * R)
by inverting k and S, we get :
S = k^-1 (z + dA *R)
and that is the equation used to generate the signature.. so it matches, and that is the reason why you can verify the signature with it.
You can note that you need both 'k' (random number) and 'dA' (the private key) in order to calculate S, but you only need R and Qa (public key) to validate the signature. And since R=k*G and Qa = dA*G and because of the trap door function in the ECDSA point multiplication (explained above), we cannot calculate dA or k from knowing Qa and R, this makes the ECDSA algorithm secure, there is no way of finding the private keys, and there is no way of faking a signature without knowing the private key.
The ECDSA algorithm is used everywhere and has not been cracked and it is a vital part of most of today's security.
Now I'll discuss on how and why the ECDSA signatures that Sony used in the PS3 were faulty and how it allowed us to gain access to their private key.
So you remember the equations needed to generate a signature.. R = k*G and S= k^-1(z + dA*R) mod p.. well this equation's strength is in the fact that you have one equation with two unknowns (k and dA) so there is no way to determine either one of those.
However, the security of the algorithm is based on its implementation and it's important to make sure that 'k' is randomly generated and that there is no way that someone can guess, calculate, or use a timing attack or any other type of attack in order to find the random value 'k'. But Sony made a huge mistake in their implementation, they used the same value for 'k' everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z' and signatures S and S' respectively :
S - S' = k^-1 (z + dA*R) - k^-1 (z' + da*R) = k^-1 (z + da*R - z' -dA*R) = k^-1 (z - z')
So : k = (z - z') / (S - S')
Once you know k, then the equation for S because one equation with one unknown and is then easily resolved for dA :
dA = (S*k - z) / R
Once you know the private key dA, you can now sign your files and the PS3 will recognize it as an authentic file signed by Sony. This is why it's important to make sure that the random number used for generating the signature is actually "cryptographically random". This is also the reason why it is impossible to have a custom firmware above 3.56, simply because since the 3.56 version, Sony have fixed their ECDSA algorithm implementation and used new keys for which it is impossible to find the private key.. if there was a way to find that key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack.
Finally! I hope this makes the whole algorithm clearer to many of you.. I know that this is still very complicated and hard to understand. I usually try to make things easy to understand for non technical people, but this algorithm is too complex to be able to explain in any simpler terms. After all that's why I prefer to call it the MFET algorithm (Mathematics For Extra Terrestrials)
But if you are a developer or a mathematician or someone interested in learning about this because you want to help or simple gain knowledge, then I'm sure that this contains enough information for you to get started or to at least understand the concept behind this unknown beast called "ECDSA".
That being said, I'd like to thank a few people who helped me understand all of this, one particularly who wishes to remain anonymous, as well as the many wikipedia pages I linked to throughout this article, and Avi Kak thanks to his paper explaining the mathematics behind ECDSA, and from which I have taken those graph images aboves.
P.s: In this article, I used '20 bytes' in my text to talk about the ECDSA signature because that's what is usually used as it matches the SHA1 hash size of 20 bytes and that's what the PS3 security uses, but the algorithm itself can be used with any size of numbers. There may be other inaccuracies in this article, but like I said, I'm not an expert, I just barely learned all of this in the past week.
Traducción por "Google"
Hoy se ha actualizado el estado del PS3 4.0 Homebrew Enabler (HEN) de Kakarotoks: hoy uno de los hackers de Sony PlayStation 3 KaKaRoToKS ha explicado cómo funciona el algoritmo ECDSA. Explica: a la demanda popular, he decidido tratar de explicar cómo la ECDSA algoritmo. He estado luchando un poco para comprender adecuadamente y al mismo tiempo me encontré con un montón de documentación al respecto, no he encontrado ninguna "ECDSA para los novatos" en cualquier lugar. Así que pensé que sería bueno explicar en términos sencillos cómo se trabaja para que otros puedan aprender de mi investigación. He encontrado algunos sitios web que explican los básicos principios , pero en absoluto suficiente para realmente entender que, otros que explica las cosas sin fundamentos, por lo que es incomprensible, y otros que van demasiado profundamente en el de la matemática detrás de él. ECDSA significa "elíptica curva de Digital Firma algoritmo ", que es utilizado para crear una cámara digital de firma de datos (un archivo por ejemplo) a fin de permitir que verifique su autenticidad, sin comprometer su seguridad . Piense en ello como una verdadera firma , se puede reconocer a alguien de la firma , pero no se puede forjar sin los demás lo sepan. El algoritmo ECDSA es básicamente todo sobre las matemáticas .. así que creo que es importante empezar por decir: "hey chicos, no aflojar en la escuela, escuchar a sus maestros, eso podría ser útil para que algún día!" Pero estas matemáticas son bastante complicada, así que mientras yo tratar de vulgarizar y hacerlo comprensible para personas no técnicas, seguirá probablemente necesite un poco de conocimiento en las matemáticas para comprender correctamente. Lo haré en dos partes, una que es una especie de explicación de alto nivel sobre cómo funciona , y otro en el que profundizar en su funcionamiento interno para completar su comprensión . Note sin embargo que he aprendido hace poco estas cosas, así que definitivamente no soy un experto en la materia. Así, el principio es simple, usted tiene una ecuación matemática que dibuja una curva en un gráfico, y usted elige un punto al azar en que se curvan y considera que su punto de origen. A continuación, se genera un número al azar, esta es tu clave privada, haga un poco la ecuación mágica matemática usando ese número al azar y que "el punto de origen" y se obtiene un segundo punto en la curva, que es su clave pública. Cuando se quiere firmar un archivo, se utiliza la clave privada (el número aleatorio) con un hash del archivo (un número único para representar el archivo) en una ecuación mágica que le dará su firma . La firma en sí se divide en dos partes, llamadas R y S. Con el fin de verificar que la firma es correcta, sólo es necesario la clave pública (que punto de la curva que se ha generado utilizando la clave privada) y ponerlo en otro ecuación mágica con una parte de la firma (S), y si se firmó el uso correcto de la clave del sector privado, que le dará la otra parte de la firma (R). Así que para hacerlo en breve, una firma consiste en dos números, R y S, y se utiliza una clave privada para generar R y S, y si una ecuación matemática usando la clave pública y S le da R, entonces la firma es válida. No hay manera de saber la clave privada o para crear una firma utilizando la clave pública. Bien, ahora la más profunda comprensión , le sugiero que tome una aspirina en estos momentos ya que esto puede doler! Vamos a empezar con lo básico (que puede ser aburrido para la gente que sabe sobre él, pero es obligatorio para los que no): ECDSA sólo utiliza enteros de matemáticas , no hay números en coma flotante (es decir, los posibles valores son 1, 2, 3, etc, pero no 1.5. ..), también, el rango de los números está limitado por la cantidad de bits se utilizan en la firma (más bits se traduce en mayores números, significa más seguridad , ya que hace más difícil "adivinar" los números críticos utilizados en la ecuación), como usted debe saber, los equipos utilizan "bits" para representar los datos, un bit es un 'dígito' en notación binaria (0 y 1) y 8 bits representa un byte. Cada vez que añades un poco, el número máximo que se puede representar dobles , con 4 bits puede representar valores de 0 a 15 (de un total de 16 valores posibles), con 5 bits, que pueden representar 32 valores, con 6 bits, que pueden representar 64 valores, etc. un byte (8 bits) puede representar 256 valores, y de 32 bits puede representar valores 4294967296 (4 Giga) .. Por lo general, ECDSA se utiliza 160 bits en total, por lo que hace, así, un número muy grande de 49 dígitos que se utiliza ECDSA con un hash criptográfico SHA1 del mensaje a firmar (el archivo). Un hash es simplemente una ecuación matemática que se aplica en todos los bytes de datos que le dará un número que es único a sus datos. Como por ejemplo, la suma de los valores de todos los bytes se puede considerar una función de hash muy tonto. Así que si algo cambia en el mensaje (el archivo), el hash será completamente diferente. En el caso del algoritmo de hash SHA1, será siempre de 20 bytes (160 bits). Es muy útil para validar que un archivo no ha sido modificado o dañado, se obtiene el 20 bytes hash para un archivo de cualquier tamaño, y se puede fácilmente calcular el hash para asegurarse de que los partidos. ¿Qué signos ECDSA es en realidad el hash, así que si los datos cambian, los cambios de hash, y la firma no es válida. Ahora, ¿cómo funciona? Criptografía de curva elíptica bien se basa en una ecuación de la forma: y ^ 2 = (x ^ 3 + a * x + b) mod p Lo primero que notamos es que hay un módulo y que la 'Y' es un cuadrado. Esto significa que para cualquier coordenada x, tendrá dos valores de y, y que la curva es simétrica en el eje X. El módulo es un número primo y se asegura de que todos los valores están dentro de nuestra gama de 160 bits y permite el uso de la "raíz cuadrada modular" y "modular multiplicativa inversa" las matemáticas que hacen más fácil el cálculo de cosas (creo). Ya que tiene un modulo (p), significa que los valores posibles de y ^ 2 están entre 0 y p-1, lo que nos da p posibles valores totales. Sin embargo, dado que estamos tratando con números enteros, sólo un subconjunto más pequeño de estos valores será un "cuadrado perfecto" (el valor de cuadrados de dos números enteros), lo que nos da N puntos posibles en la curva donde N <p (siendo N el número de cuadrados perfectos entre 0 y p). Ya que cada x dará dos puntos (valores positivos y negativos de la raíz cuadrada de y ^ 2), esto significa que hay N / 2 posibles 'x' coordenadas que son válidos y que le dan un punto de la curva. Así que este curva elíptica tiene un número finito de puntos en ella, y todo es debido a los cálculos de enteros y el módulo. Otra cosa que usted necesita saber sobre curvas elípticas, es la noción de la "suma puntos". Se define como la adición de un punto P a otro punto Q conducirá hasta el punto de S que si se traza una línea entre P y Q, que se cruzan la curva en un punto R tercero que es el valor negativo de S (recordar que la curva es simétrica en el eje X). En este caso, definimos R =-S para representar el punto simétrico de R en el eje X. Esto es más fácil ilustrar con una imagen: Así que usted puede ver una curva de la forma y ^ 2 = x ^ 3 + ax + b (donde a = -4 yb = 0), que es simétrica en el eje X, y donde P + Q es el punto simétrico de X del punto R, que es el tercer cruce de una línea que va de P a Q. De la misma manera, si lo hace P + P, será el punto simétrico de R que se la intersección de la recta que es tangente al punto P.. Y P + P + P es el complemento entre el punto resultante de P + P con el punto P, ya que P + P + P se puede escribir como (P + P) + P.. Esto define la "multiplicación de punto", donde k * P es la adición del punto P a sí mismo k veces aquí hay dos ejemplos que muestran lo siguiente: Aquí, usted puede ver dos curvas elípticas, y un punto P de la cual se traza la tangente, intersección con la curva con un tercer punto, y su punto simétrico que 2P, entonces a partir de ahí, se dibuja una línea desde 2P y P y se cruzan la curva, y el punto simétrico es 3P. etc se puede seguir haciendo eso para la multiplicación punto. También se puede ya adivinar por qué tiene que tomar el punto simétrico de R cuando se hace la suma, de lo contrario, las adiciones múltiples de un mismo punto siempre le dará la misma línea y los mismos tres intersecciones. Una particularidad de esta multiplicación punto es que si tienen un punto de R = k * P, donde se sabe que R y P sabes, no hay manera de saber cuál es el valor de 'k' es. Puesto que no hay división en coma o el punto de sustracción, no sólo puede resolver k = R / P. Además, dado que usted podría estar haciendo millones de adiciones momento, acaba de terminar en otro punto de la curva, y usted no tendría ninguna manera de saber "cómo" tiene allí. No se puede revertir esta operación, y usted no puede encontrar 'k' el valor que se multiplicó con su punto P para darle el punto resultante R. Esta cosa que usted no puede encontrar el multiplicando incluso cuando sabe que el original y los puntos de destino es toda la base de la seguridad tras el algoritmo ECDSA, y el principio que se llama una "función trap door". Ahora que hemos manejado los "fundamentos", vamos a hablar sobre el algoritmo de firma ECDSA real. Para ECDSA, primero es necesario saber los parámetros de la curva, esos son a, b, N, P y G. Usted ya sabe que 'a' y 'b' son los parámetros de la función de la curva (y ^ 2 = x ^ 3 + ax + b), de que 'p' es el módulo principal, y que 'N' es el número de puntos de la curva, pero también hay 'G' que se necesita para ECDSA, y representa un "punto de referencia" o un punto de origen si así lo prefiere. Los parámetros de la curva son importantes y, sin saber ellos, que obviamente no puede firmar o verificar la firma. Sí, la verificación de una firma no se trata sólo de conocer la clave pública, también es necesario conocer los parámetros de la curva que se obtiene la clave pública del. Así que en primer lugar, usted tendrá una privada y una clave pública .. la clave privada es un número al azar (de 20 bytes) que se genera, y la clave pública es un punto de la curva generada a partir de la multiplicación de punto de G con la clave privada. Hemos creado 'da' como la clave privada (número aleatorio) y 'Qa' como la clave pública (un punto), por lo que tenemos:. Qa = dA * G (donde G es el punto de referencia en los parámetros de la curva) Por lo tanto ¿cómo firmar un archivo / message? En primer lugar, usted necesita saber que la firma es de 40 bytes y está representado por dos valores de 20 bytes cada uno, el primero se llama R y el segundo se llama S.. por lo que el par (R, S), junto a su firma ECDSA es .. Ahora aquí es cómo usted puede crear los dos valores con el fin de firmar un archivo .. primero debe generar un valor aleatorio 'k' (de 20 pases), y usar la multiplicación punto para calcular el punto P = k * G. Valor de dicho punto x representará 'R'. Desde el punto de la curva P está representado por su (x, y) las coordenadas (cada uno es de 20 bytes de longitud), sólo es necesario la 'x' valor (20 bytes) para la firma, y el valor que se llamará 'R' . Ahora todo lo que necesitamos es el valor de la 'S'. Para calcular S, usted debe hacer un hash SHA1 del mensaje, esto le da un valor de 20 bytes que se tendrá en cuenta como un número entero muy grande y lo vamos a llamar 'z . Ahora usted puede calcular S mediante la ecuación: S = k ^ -1 (z + dA * R) mod p Nótese aquí la k ^ -1 que es el "inverso multiplicativo modular 'de k es básicamente el inverso de la k, pero como estamos tratando con números enteros, entonces eso no es posible, por lo que es un número tal que (k ^ -1 * k) mod p es igual a 1. Y de nuevo, les recuerdo que k es el número aleatorio para generar R, z es el hash del mensaje a firmar, dA es la clave privada y R es la coordenada x del k * G (donde G es el punto de origen de los parámetros de la curva). Ahora que ya tiene su firma, usted quiere comprobarlo, es también bastante simple, y sólo necesita la clave pública (y parámetros de la curva, por supuesto) para hacer eso. Usted utilizará la siguiente fórmula para calcular un punto P: P = S ^ -1 * z * G + S ^ -1 * R * Qa Si la coordenada x del punto P es igual a R, que significa que la firma es válida, de lo contrario no lo es. Bastante simple, ¿eh? ahora vamos a ver cómo y por qué y esto va a requerir algo de matemáticas para verificar: Tenemos: P = S ^ -1 * z * G + S ^ -1 * R * Qa pero Qa = dA * G, así: P = S ^ -1 * z * G + S ^ -1 * R * da * G = S ^ -1 (z + dA * R) * G Pero la coordenada x de P deben coincidir con R y R es la coordenada x del k * G, lo que significa que: k * G = S ^ -1 (z + dA * R) * G se puede simplificar mediante la eliminación de G que nos da: k = S ^ -1 (z + dA * R) por k invertir y S, se obtiene: S = k ^ -1 (z + dA * R) y que es la ecuación utilizada para generar la firma .. para que coincida, y esa es la razón por la cual se puede verificar la firma con él. Usted puede notar que se necesita tanto 'k' (número aleatorio) y 'Da' (la clave privada) para el cálculo de S, pero sólo necesidad de R y Qa (clave pública) para validar la firma. Y como R = k * G y Qa = dA * G y debido a la función de puerta trampa en la multiplicación punto ECDSA (explicado anteriormente), no podemos calcular dA o k de saber Qa y R, esto hace que el algoritmo ECDSA seguro, no hay manera de encontrar las claves privadas, y no hay manera de falsificar una firma sin conocer la clave privada. El algoritmo ECDSA se utiliza en todas partes y no se ha roto sido y es una parte vital de la mayor parte de la seguridad de hoy. Ahora me Hablaremos sobre cómo y por qué las firmas ECDSA que Sony utiliza en la PS3 eran defectuosos y la forma en que nos ha permitido tener acceso a su clave privada. Así que recuerde las ecuaciones necesarias para generar una firma .. R = k * G y S = k ^ -1 (z + dA * R) mod p.. así la fuerza esta ecuación es el hecho de que usted tiene una ecuación con dos incógnitas (k y DA) así que no hay manera de determinar ya sea uno de ellos. Sin embargo, la seguridad del algoritmo se basa en su aplicación y que es importante hacer asegurarse de que 'k' se genera aleatoriamente y que no hay manera de que alguien pueda imaginar, calcular, o usar un ataque de oportunidad o de cualquier otro tipo de ataque con el fin de encontrar 'k' el valor aleatorio. Sin embargo, Sony cometió un gran error en su aplicación, que utiliza el mismo valor de "k" en todas partes, lo que significa que si usted tiene dos firmas, ambas con el mismo k, entonces ambos tienen el valor de R mismo, y eso significa que se puede calcular k con dos S firmas de dos archivos con los hashes de Z y Z 'y la firma S y S', respectivamente: S - S '= k ^ -1 (z + dA * R) - k ^ -1 (z' + da * R) = k ^ -1 (z + da * R - z '-DA * R) = k ^ -1 (z - z') Por lo tanto: K = (z - z ') / (S - S' ) Una vez que sepas k, entonces la ecuación para S por una ecuación con una incógnita y luego se resuelve fácilmente por dA: dA = (S * k - z) / R Una vez que sepa la clave privada dA, ahora se puede firmar sus archivos y la PS3 lo reconocerá como un archivo de documento auténtico autorizado por Sony. Es por eso que es importante para asegurarse de que el número aleatorio utilizado para generar la firma es en realidad "criptográficamente al azar". Esta es también la razón por la que es imposible tener un firmware personalizado por encima de 3,56, simplemente porque desde la versión 3.56, Sony ha fijado su implementación del algoritmo ECDSA y utilizar las nuevas claves para las que es imposible encontrar la clave privada .. si había una manera de encontrar la llave, entonces la seguridad de cada ordenador, sitio web, el sistema puede estar comprometida, ya que muchos de los sistemas se basan en ECDSA para su seguridad, y es imposible de romper. ¡Por fin! Espero que esto hace más claro el algoritmo completo para muchos de ustedes .. Yo sé que esto es muy complicado y difícil de entender. Por lo general tratan de hacer las cosas fáciles de entender para personas no técnicas, pero este algoritmo es demasiado complejo como para ser capaz de explicar en los términos más simples. Después de todo es por eso que yo prefiero llamarlo el algoritmo MFET (Matemática Para los extraterrestres) , pero si usted es un desarrollador o un matemático o alguien interesado en aprender acerca de esto porque quieren ayudar a obtener conocimiento o simple, entonces estoy seguro de que contiene la información suficiente para que pueda empezar o al menos entender el concepto detrás de esta bestia desconocida llamada "ECDSA". Dicho esto, me gustaría agradecer a algunas personas que me ayudaron a entender todo esto, un particular que desee permanecer en el anonimato, así como las muchas páginas de Wikipedia que vinculados a lo largo de este artículo, y Avi Kak gracias a su papel de explicar las matemáticas detrás de ECDSA, y del cual he tomado las imágenes del gráfico aboves. PS: En este artículo, he utilizado '20 bytes "en mi texto para hablar de la firma ECDSA porque eso es lo que se suele utilizar, ya que coincide con el tamaño de hash SHA1 de 20 bytes y eso es lo que la seguridad de PS3 usa, pero el algoritmo se puede utilizar con cualquier tamaño de los números. Puede haber errores de otros en este artículo, pero como he dicho, yo no soy un experto, apenas aprendió todo esto en la última semana. z es el hash del mensaje a firmar, dA es la clave privada y R es la coordenada x del k * G (donde G es el punto de origen de los parámetros de la curva). Ahora que ya tiene su firma, que desea comprobar él, es también bastante simple, y sólo necesita la clave pública (y parámetros de la curva, por supuesto) para hacer eso. Usted utilizará la siguiente fórmula para calcular un punto P: P = S ^ -1 * z * G + S ^ -1 * R * Qa Si la coordenada x del punto P es igual a R, que significa que la firma es válida, de lo contrario no lo es. Bastante simple, ¿eh? ahora vamos a ver cómo y por qué y esto va a requerir algo de matemáticas para verificar: Tenemos: P = S ^ -1 * z * G + S ^ -1 * R * Qa pero Qa = dA * G, así: P = S ^ -1 * z * G + S ^ -1 * R * da * G = S ^ -1 (z + dA * R) * G Pero la coordenada x de P deben coincidir con R y R es la coordenada x del k * G, lo que significa que: k * G = S ^ -1 (z + dA * R) * G se puede simplificar mediante la eliminación de G que nos da: k = S ^ -1 (z + dA * R) por k invertir y S, se obtiene: S = k ^ -1 (z + dA * R) y que es la ecuación utilizada para generar la firma .. para que coincida, y esa es la razón por la cual se puede verificar la firma con él. Usted puede notar que se necesita tanto 'k' (número aleatorio) y 'Da' (la clave privada) para el cálculo de S, pero sólo necesidad de R y Qa (clave pública) para validar la firma. Y como R = k * G y Qa = dA * G y debido a la función de puerta trampa en la multiplicación punto ECDSA (explicado anteriormente), no podemos calcular dA o k de saber Qa y R, esto hace que el algoritmo ECDSA seguro, no hay manera de encontrar las claves privadas, y no hay manera de falsificar una firma sin conocer la clave privada. El algoritmo ECDSA se utiliza en todas partes y no se ha roto sido y es una parte vital de la mayor parte de la seguridad de hoy. Ahora me Hablaremos sobre cómo y por qué las firmas ECDSA que Sony utiliza en la PS3 eran defectuosos y la forma en que nos ha permitido tener acceso a su clave privada. Así que recuerde las ecuaciones necesarias para generar una firma .. R = k * G y S = k ^ -1 (z + dA * R) mod p.. así la fuerza esta ecuación es el hecho de que usted tiene una ecuación con dos incógnitas (k y DA) así que no hay manera de determinar ya sea uno de ellos. Sin embargo, la seguridad del algoritmo se basa en su aplicación y que es importante hacer asegurarse de que 'k' se genera aleatoriamente y que no hay manera de que alguien pueda imaginar, calcular, o usar un ataque de oportunidad o de cualquier otro tipo de ataque con el fin de encontrar 'k' el valor aleatorio. Sin embargo, Sony cometió un gran error en su aplicación, que utiliza el mismo valor de "k" en todas partes, lo que significa que si usted tiene dos firmas, ambas con el mismo k, entonces ambos tienen el valor de R mismo, y eso significa que se puede calcular k con dos S firmas de dos archivos con los hashes de Z y Z 'y la firma S y S', respectivamente: S - S '= k ^ -1 (z + dA * R) - k ^ -1 (z' + da * R) = k ^ -1 (z + da * R - z '-DA * R) = k ^ -1 (z - z') Por lo tanto: K = (z - z ') / (S - S' ) Una vez que sepas k, entonces la ecuación para S por una ecuación con una incógnita y luego se resuelve fácilmente por dA: dA = (S * k - z) / R Una vez que sepa la clave privada dA, ahora se puede firmar sus archivos y la PS3 lo reconocerá como un archivo de documento auténtico autorizado por Sony. Es por eso que es importante para asegurarse de que el número aleatorio utilizado para generar la firma es en realidad "criptográficamente al azar". Esta es también la razón por la que es imposible tener un firmware personalizado por encima de 3,56, simplemente porque desde la versión 3.56, Sony ha fijado su implementación del algoritmo ECDSA y utilizar las nuevas claves para las que es imposible encontrar la clave privada .. si había una manera de encontrar la llave, entonces la seguridad de cada ordenador, sitio web, el sistema puede estar comprometida, ya que muchos de los sistemas se basan en ECDSA para su seguridad, y es imposible de romper. ¡Por fin! Espero que esto hace más claro el algoritmo completo para muchos de ustedes .. Yo sé que esto es muy complicado y difícil de entender. Por lo general tratan de hacer las cosas fáciles de entender para personas no técnicas, pero este algoritmo es demasiado complejo como para ser capaz de explicar en los términos más simples. Después de todo es por eso que yo prefiero llamarlo el algoritmo MFET (Matemática Para los extraterrestres) , pero si usted es un desarrollador o un matemático o alguien interesado en aprender acerca de esto porque quieren ayudar a obtener conocimiento o simple, entonces estoy seguro de que contiene la información suficiente para que pueda empezar o al menos entender el concepto detrás de esta bestia desconocida llamada "ECDSA". Dicho esto, me gustaría agradecer a algunas personas que me ayudaron a entender todo esto, un particular que desee permanecer en el anonimato, así como las muchas páginas de Wikipedia que vinculados a lo largo de este artículo, y Avi Kak gracias a su papel de explicar las matemáticas detrás de ECDSA, y del cual he tomado las imágenes del gráfico aboves. PS: En este artículo, he utilizado '20 bytes "en mi texto para hablar de la firma ECDSA porque eso es lo que se suele utilizar, ya que coincide con el tamaño de hash SHA1 de 20 bytes y eso es lo que la seguridad de PS3 usa, pero el algoritmo se puede utilizar con cualquier tamaño de los números. Puede haber errores de otros en este artículo, pero como he dicho, yo no soy un experto, apenas aprendió todo esto en la última semana. z es el hash del mensaje a firmar, dA es la clave privada y R es la coordenada x del k * G (donde G es el punto de origen de los parámetros de la curva). Ahora que ya tiene su firma, que desea comprobar él, es también bastante simple, y sólo necesita la clave pública (y parámetros de la curva, por supuesto) para hacer eso. Usted utilizará la siguiente fórmula para calcular un punto P: P = S ^ -1 * z * G + S ^ -1 * R * Qa Si la coordenada x del punto P es igual a R, que significa que la firma es válida, de lo contrario no lo es. Bastante simple, ¿eh? ahora vamos a ver cómo y por qué y esto va a requerir algo de matemáticas para verificar: Tenemos: P = S ^ -1 * z * G + S ^ -1 * R * Qa pero Qa = dA * G, así: P = S ^ -1 * z * G + S ^ -1 * R * da * G = S ^ -1 (z + dA * R) * G Pero la coordenada x de P deben coincidir con R y R es la coordenada x del k * G, lo que significa que: k * G = S ^ -1 (z + dA * R) * G se puede simplificar mediante la eliminación de G que nos da: k = S ^ -1 (z + dA * R) por k invertir y S, se obtiene: S = k ^ -1 (z + dA * R) y que es la ecuación utilizada para generar la firma .. para que coincida, y esa es la razón por la cual se puede verificar la firma con él. Usted puede notar que se necesita tanto 'k' (número aleatorio) y 'Da' (la clave privada) para el cálculo de S, pero sólo necesidad de R y Qa (clave pública) para validar la firma. Y como R = k * G y Qa = dA * G y debido a la función de puerta trampa en la multiplicación punto ECDSA (explicado anteriormente), no podemos calcular dA o k de saber Qa y R, esto hace que el algoritmo ECDSA seguro, no hay manera de encontrar las claves privadas, y no hay manera de falsificar una firma sin conocer la clave privada. El algoritmo ECDSA se utiliza en todas partes y no se ha roto sido y es una parte vital de la mayor parte de la seguridad de hoy. Ahora me Hablaremos sobre cómo y por qué las firmas ECDSA que Sony utiliza en la PS3 eran defectuosos y la forma en que nos ha permitido tener acceso a su clave privada. Así que recuerde las ecuaciones necesarias para generar una firma .. R = k * G y S = k ^ -1 (z + dA * R) mod p.. así la fuerza esta ecuación es el hecho de que usted tiene una ecuación con dos incógnitas (k y DA) así que no hay manera de determinar ya sea uno de ellos. Sin embargo, la seguridad del algoritmo se basa en su aplicación y que es importante hacer asegurarse de que 'k' se genera aleatoriamente y que no hay manera de que alguien pueda imaginar, calcular, o usar un ataque de oportunidad o de cualquier otro tipo de ataque con el fin de encontrar 'k' el valor aleatorio. Sin embargo, Sony cometió un gran error en su aplicación, que utiliza el mismo valor de "k" en todas partes, lo que significa que si usted tiene dos firmas, ambas con el mismo k, entonces ambos tienen el valor de R mismo, y eso significa que se puede calcular k con dos S firmas de dos archivos con los hashes de Z y Z 'y la firma S y S', respectivamente: S - S '= k ^ -1 (z + dA * R) - k ^ -1 (z' + da * R) = k ^ -1 (z + da * R - z '-DA * R) = k ^ -1 (z - z') Por lo tanto: K = (z - z ') / (S - S' ) Una vez que sepas k, entonces la ecuación para S por una ecuación con una incógnita y luego se resuelve fácilmente por dA: dA = (S * k - z) / R Una vez que sepa la clave privada dA, ahora se puede firmar sus archivos y la PS3 lo reconocerá como un archivo de documento auténtico autorizado por Sony. Es por eso que es importante para asegurarse de que el número aleatorio utilizado para generar la firma es en realidad "criptográficamente al azar". Esta es también la razón por la que es imposible tener un firmware personalizado por encima de 3,56, simplemente porque desde la versión 3.56, Sony ha fijado su implementación del algoritmo ECDSA y utilizar las nuevas claves para las que es imposible encontrar la clave privada .. si había una manera de encontrar la llave, entonces la seguridad de cada ordenador, sitio web, el sistema puede estar comprometida, ya que muchos de los sistemas se basan en ECDSA para su seguridad, y es imposible de romper. ¡Por fin! Espero que esto hace más claro el algoritmo completo para muchos de ustedes .. Yo sé que esto es muy complicado y difícil de entender. Por lo general tratan de hacer las cosas fáciles de entender para personas no técnicas, pero este algoritmo es demasiado complejo como para ser capaz de explicar en los términos más simples. Después de todo es por eso que yo prefiero llamarlo el algoritmo MFET (Matemática Para los extraterrestres) , pero si usted es un desarrollador o un matemático o alguien interesado en aprender acerca de esto porque quieren ayudar a obtener conocimiento o simple, entonces estoy seguro de que contiene la información suficiente para que pueda empezar o al menos entender el concepto detrás de esta bestia desconocida llamada "ECDSA". Dicho esto, me gustaría agradecer a algunas personas que me ayudaron a entender todo esto, un particular que desee permanecer en el anonimato, así como las muchas páginas de Wikipedia que vinculados a lo largo de este artículo, y Avi Kak gracias a su papel de explicar las matemáticas detrás de ECDSA, y del cual he tomado las imágenes del gráfico aboves. PS: En este artículo, he utilizado '20 bytes "en mi texto para hablar de la firma ECDSA porque eso es lo que se suele utilizar, ya que coincide con el tamaño de hash SHA1 de 20 bytes y eso es lo que la seguridad de PS3 usa, pero el algoritmo se puede utilizar con cualquier tamaño de los números. Puede haber errores de otros en este artículo, pero como he dicho, yo no soy un experto, apenas aprendió todo esto en la última semana.
*Recomiendo leerlo en inglés, ya que con un nivel medio (como el que puedo tener yo o cualquier otro usuario) se entiende perfectamente, de todas maneras lo traduciré bien si tengo tiempo estos días para los que no sepan nada de inglés 
Fuente de lo de Kakarotoks: http://www.ps3news.com/ps3-hacks-jailbr ... z1l7QHpQqD
. He pasado por el hilo TrueBlue pwned y está un pokito desvirtuado 
.
![[beer]](/images/smilies/nuevos2/brindando.gif "brindis")
![[qmparto]](/images/smilies/net_quemeparto.gif "Que me parto!")
