[News] Porquê que tu não tens jailbreak para o meu Cech - 3002?

KaKaRoTo escreveu:
A demanda popular, eu decidi tentar e explicar como o ECDSA algoritmo funciona. Eu estive lutando um pouco para compreendê-lo corretamente e enquanto eu encontrei um monte de documentação sobre isso, eu realmente não tenho encontrado qualquer "ECDSA para iniciantes" em qualquer lugar. Então eu pensei que seria bom explicar em termos simples como funciona para que outros possam aprender com a minha pesquisa. Eu encontrei alguns sites que explicam os princípios básicos mas nem de longe suficiente para realmente entendê-lo, outros que explica as coisas, sem quaisquer fundamentos, tornando-se incompreensível, e outros que vão muito muito profundamente nos a matemática por trás dele.
ECDSA significa "Elliptic Curva Digital Signature Algorithm ", ele é usado para criar uma assinatura digital de dados (um arquivo por exemplo), a fim de lhe permitir verificar a sua autenticidade, sem comprometer a sua segurança. Pense nisso como uma assinatura real, você pode reconhecer a assinatura de alguém, mas você não pode forjar-lo sem saber outros. O algoritmo ECDSA é basicamente tudo sobre a matemática .. então eu acho que é importante começar por dizer: "hey crianças, não afrouxar na escola, ouvir seus professores, esse material pode ser útil para você algum dia!"  Mas estes matemática são bastante complicado, por isso, enquanto eu vou tentar banalizar-lo e torná-lo compreensível para as pessoas não técnicas, você ainda vai provavelmente precisar de algum conhecimento em matemática para compreendê-lo corretamente. Vou fazer isso em duas partes, uma que é uma espécie de alto nível explicação sobre como ele funciona, e outro onde eu cavar mais fundo em seu funcionamento interno para completar a sua compreensão. Note no entanto que eu aprendi apenas recentemente essas coisas, então eu definitivamente não sou um especialista sobre o assunto.
Assim, o princípio é simples, você tem uma equação matemática que desenha uma curva em um gráfico, e você escolhe um ponto aleatório no essa curva e consideram que o seu ponto de origem. Então você gerar um número aleatório, esta é a sua chave privada, você faz alguma equação matemática mágica usando esse número aleatório e que "ponto de origem" e você terá um segundo ponto na curva, que é a sua chave pública. Quando você quiser assinar um arquivo, você usará esta chave privada (o número aleatório) com um hash do arquivo (um número único para representar o arquivo) em uma equação mágica e que lhe dará a sua assinatura. A assinatura está dividida em duas partes, chamado R e S . A fim de verificar se a assinatura está correta, você só precisa da chave pública (que ponto da curva que foi gerado usando a chave privada) e você colocar isso em outra equação mágica com uma parte da assinatura ( S ), e se que foi assinado corretamente usando a chave privada, ele vai te dar a outra parte da assinatura ( R ). Então, para torná-lo curto, uma assinatura consiste em dois números, R e S , e você usa uma chave privada para gerar R e S , e se uma equação matemática utilizando a chave pública e S dá-lhe R , em seguida, a assinatura é válida. Não há nenhuma maneira de saber a chave privada ou para criar uma assinatura utilizando apenas a chave pública.
Tudo bem, agora para o mais profundo entendimento, eu sugiro que você tomar uma aspirina agora como isso pode machucar! Vamos começar com o básico (que pode ser chato para as pessoas que sabem sobre isso, mas é obrigatória para aqueles que não) fazer: ECDSA usa apenas matemática inteiros, não há pontos flutuantes (isto significa valores possíveis são 1, 2, 3, etc .. mas não 1,5 ..), também, a gama dos números é obrigado por quantos bits são utilizados na assinatura (mais bits significa números mais elevados, significa mais segurança uma vez que se torna mais difícil de 'suposição' os números críticos utilizados na equação), enquanto você deve saber, os computadores usam 'bits' para representar dados, um pouco é um 'dígito' na notação binária (0 e 1) e 8 bits representam um byte. Toda vez que você adicionar um bit, o número máximo que pode ser representado duplos, com 4 bits pode representar valores de 0 a 15 (para um total de 16 valores possíveis), com 5 bits, pode representar 32 valores, com 6 bits, você pode representar 64 valores, etc .. um byte (8 bits) pode representar 256 valores, e 32 bits pode representar 4294967296 valores (4 Giga) .. Normalmente ECDSA vai usar 160 bits no total, o que faz ... bem, um muito grande número com 49 dígitos nele ... ECDSA é usada com um SHA1 hash criptográfico da mensagem para assinar (o arquivo). Um de hash é simplesmente uma outra equação matemática que você aplica em cada byte de dados que lhe dará um número que é exclusivo aos seus dados. Como por exemplo, a soma dos valores de todos os bytes pode ser considerada uma função hash muito mudo. Então, se alguma coisa muda na mensagem (o arquivo), em seguida, o hash será completamente diferente. No caso de o algoritmo de hash SHA1, ele sempre será de 20 bytes (160 bits). É muito útil para validar que um arquivo não foi modificado ou corrompido, você começa o hash de 20 bytes para um arquivo de qualquer tamanho, e você pode facilmente recalcular esse hash para verificar se ele corresponde. Que sinais ECDSA é realmente esse hash, por isso, se os dados forem alterados, as alterações de hash, ea assinatura não é mais válido. Agora, como é que funciona? Bem     Curva Elíptica criptografia se baseia em uma equação da forma:

y ^ 2 = (x ^ 3 + a * x + b) mod p

A primeira coisa que você nota é que há um módulo e que o ' y 'é um quadrado. Isto significa que para qualquer x coordenada, terá dois valores de y e que a curva é simétrica sobre o eixo X . O módulo é um número primo e garante que todos os valores estão dentro de nossa gama de 160 bits e permite o uso de " raiz quadrada modular "e" inverso multiplicativo modular "matemática que tornam mais fácil calcular coisas (eu acho). Uma vez que tem um módulo ( p ), isso significa que os possíveis valores de y ^ 2 estão entre 0 e p -1, o que nos dá p dadas valores possíveis. No entanto, uma vez que estamos a lidar com números inteiros, apenas um subconjunto menor desses valores será um " quadrado perfeito "(o valor quadrado de dois inteiros), o que nos dá N possíveis pontos na curva onde N

Assim, é possível ver uma curva da forma y = x ^ 2 ^ 3 + ax + b (em que A = -4 e b = 0 ), que é simétrica sobre o eixo X , e onde P + Q é o ponto simétrico através X do ponto R , que é o terceiro de intersecção de uma linha que vai de P para Q . Do mesmo modo, se o fizer P + P , será o ponto simétrico de R que é a intersecção da linha que é uma tangente ao ponto P .. e P + P + P é a adição entre o ponto resultante de P + P com o ponto P desde P + P + P pode ser escrita como (P + P) + P .. Este define o " ponto de multiplicação "onde P * k é a adição do ponto P para si k vezes ... aqui estão dois exemplos que mostram isso:

Aqui, você pode ver duas curvas elípticas, e um ponto P a partir do qual você desenhar a tangente, que intercepta a curva com um terceiro ponto, e seu ponto simétrico que 2P , em seguida, a partir daí, você desenhar uma linha de 2P e P e cruzará a curva, eo ponto simétrico é 3P . etc ... você pode continuar fazendo isso para a multiplicação ponto. Você também já pode adivinhar por que você precisa para tomar o ponto simétrico de R ao fazer a adição, caso contrário, adições múltiplas do mesmo ponto vai sempre dar a mesma linha e os mesmos três cruzamentos.
Uma particularidade deste multiplicação ponto é que se você tem um ponto R = k * P , onde você sabe que R e você sabe P , não existe uma maneira de descobrir o que o valor de ' k 'é. Desde que não há nenhum ponto de subtração ou divisão ponto, você não pode simplesmente resolver k = R / P . Também, desde que você poderia estar fazendo milhões de adições de pontos, você só vai acabar em outro ponto da curva, e você não teria nenhuma maneira de saber "como" você chegou lá. Você não pode reverter esta operação, e você não pode encontrar o valor ' k ', que foi multiplicado com o seu ponto P para dar-lhe o ponto resultante R .
Essa coisa que você não consegue encontrar o multiplicando mesmo quando você sabe o pontos originais e de destino é toda a base da segurança por trás do algoritmo ECDSA, eo princípio é chamado de " função de porta armadilha ".
Agora que já lidou com os "princípios básicos", vamos falar sobre o algoritmo de assinatura ECDSA real. Para ECDSA, primeiro você precisa conhecer seus parâmetros da curva, esses são a, b, p, N e G . Você já sabe que ' a 'e' b 'são os parâmetros da função de curva ( y ^ 2 = x ^ 3 + ax + b ), que ' p 'é o módulo principal, e que « N »é o número de pontos da curva, mas há também ' G 'que é necessário para ECDSA, e representa um "ponto de referência" ou um ponto de origem, se preferir. Esses parâmetros da curva são importantes e sem conhecê-los, você obviamente não pode assinar ou verificar uma assinatura. Sim, verificar uma assinatura não é só saber a chave pública, você também precisa conhecer os parâmetros da curva para que esta chave pública é derivada.
Então, primeiro de tudo, você terá uma privada e uma chave pública .. o chave privada é um número aleatório (de 20 bytes) que é gerado, e a chave pública é um ponto na curva gerada a partir da multiplicação ponto de L , com a chave privada. Montamos ' dA 'como a chave privada (número aleatório) e' Qa "como a chave pública (um ponto), por isso temos: Qa = dA * G (onde G é o ponto de referência nos parâmetros da curva).
Então, como você assinar um arquivo / mensagem? Primeiro, você precisa saber que a assinatura é de 40 bytes e é representado por dois valores de 20 bytes cada, o primeiro é chamado de R eo segundo é chamado de S .. por isso o par (R, S) em conjunto é a sua ECDSA assinatura .. agora é aqui como você pode criar esses dois valores, a fim de assinar um arquivo .. primeiro você deve gerar um valor aleatório ' k '(de 20 byes), e usar ponto de multiplicação para calcular o ponto P = k * L . Desse ponto x valor vai representar ' R '. Desde o ponto na curva de P é representada por seus (x, y) coordenadas (cada um sendo 20 bytes de comprimento), você só precisa do ' x value '(20 bytes) para a assinatura, e esse valor será chamado' R ' . Agora tudo que você precisa é o ' S valor '.
Para calcular S , você deve fazer um hash SHA1 da mensagem, isto dá-lhe um valor de 20 bytes que você irá considerar como um muito grande número inteiro e nós vamos chamá-lo de ' z '. Agora você pode calcular S usando a equação:
S = k ^ -1 (z + dA * R) mod p
Note aqui o k ^ -1 que é o " inverso multiplicativo modular 'de k ... é basicamente o inverso do k , mas uma vez que estamos lidando com números inteiros, então isso não é possível, por isso é um número tal que (k ^ -1 * k) mod p é igual a 1. E mais uma vez, gostaria de lembrar que k é o número aleatório usado para gerar R , z é o hash da mensagem para assinar, dA é a chave privada e R é o x coordenar de k * G (onde G é o ponto de origem dos parâmetros da curva).
Agora que você tem a sua assinatura, você quer verificar-lo, é também bastante simples, e você só precisa da chave pública (e parâmetros da curva de curso) para faça isso. Você usa esta equação para calcular um ponto P :
P = S ^ -1 * z * G + S ^ -1 * R * Qa
Se o x coordenada do ponto P é igual a R , que significa que a assinatura é válida, caso contrário, não é.
Bem simples, hein? agora vamos ver como e por que ... e isso vai exigir um pouco de matemática para verificar:
Nós temos: P = S ^ -1 * z * G + S ^ -1 * R * Qa mas Qa = dA * G , assim: P = S ^ -1 * z * G + S ^ -1 * R * DA * G = S ^ -1 (z + dA * R) * G Mas o x coordenadas de P deve coincidir com R e R é o x coordenada do G k * , o que significa que: k * L = S ^ -1 (z + dA * R) * G podemos simplificar removendo G que nos dá: k = S ^ -1 ( z + dA * R) , invertendo k e S , temos: S = k ^ -1 (z + dA * R) e que é a equação utilizada para gerar a assinatura .. para que ela corresponda, e que é a razão pela qual você pode verificar a assinatura com ele. Você pode notar que você precisa tanto ' k '(número aleatório) e' dA '(a chave privada), a fim de calcular S , mas você só precisa de R e Qa (público chave) para validar a assinatura. E uma vez que R = K * L e Qa = dA * L e por causa da função de porta armadilha na multiplicação ponto ECDSA (explicado acima), não podemos calcular dA ou k do conhecimento de Qa e R , isso faz com que o algoritmo ECDSA seguro, existe há nenhuma maneira de encontrar as chaves privadas, e não há nenhuma maneira de falsificar uma assinatura sem conhecer a chave privada. O algoritmo ECDSA é usado em todos os lugares e não foi rompido e é uma parte vital de mais de segurança de hoje. Agora Vou discutir sobre como e por que as assinaturas ECDSA que a Sony usadas no PS3 foram falho e como ela nos permitiu ter acesso à sua chave privada. Então você se lembra das equações necessárias para gerar uma assinatura .. R = k * L e S = k ^ -1 (z + dA * R) mod p .. bem a força deste equação está no fato de que você tem uma equação com duas incógnitas ( k e dA ) para que não há nenhuma maneira de determinar ou um daqueles . No entanto, a segurança do algoritmo baseia-se na sua implementação e é importante ter certeza de que ' k 'é gerada aleatoriamente e que não há nenhuma maneira que alguém pode adivinhar, calcular, ou usar um ataque de temporização ou qualquer outro tipo de ataque em a fim de encontrar o valor aleatório ' k '. Mas a Sony fez um grande erro na sua implementação, eles usaram o mesmo valor para ' k 'em todos os lugares, o que significa que se você tiver duas assinaturas, ambos com o mesmo k , então eles vão ambos têm o mesmo R valor, e isso significa que você pode calcular k usando dois S assinaturas de dois arquivos com hashes z e z ' e assinaturas S e 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') Então: k = (z - z ') / (S - S ') Uma vez que você sabe k , então a equação para S porque uma equação com um desconhecido e é, então, facilmente resolvido por dA : dA = (S * k - z) / R Depois de saber a chave privada dA , você agora podem assinar seus arquivos eo PS3 irá reconhecê-lo como um arquivo autêntico assinado pela Sony. É por isso que é importante ter certeza de que o número aleatório usado para gerar a assinatura é realmente "criptograficamente aleatório". Esta é também a razão pela qual é impossível ter um firmware personalizado acima 3,56, simplesmente porque desde a versão 3.56, a Sony ter corrigido seu algoritmo ECDSA implementação e utilizado novas chaves para as quais é impossível encontrar a chave privada .. se havia uma maneira de encontrar essa chave, então a segurança de todos os computadores, web site, sistema poderá estar comprometido uma vez que muitos sistemas estão contando com ECDSA para a sua segurança, e é impossível de crack. Finalmente! Espero que isso faz todo o algoritmo mais claro para muitos de vocês .. Eu sei que isso ainda é muito complicado e difícil de entender. Eu costumo tentar fazer as coisas mais fáceis de entender para pessoas não técnicas, mas este algoritmo é complexo demais para ser capaz de explicar em quaisquer termos mais simples. Afinal é por isso que eu prefiro chamar-lhe o algoritmo MFET (Matemática Para extraterrestres) Mas se você é um desenvolvedor ou um matemático ou alguém interessado em aprender sobre isso porque você quer ajudar ou conhecimento ganho simples, então eu tenho certeza que esta contém informações suficientes para que você possa começar ou, pelo menos, entender o conceito por trás desta besta desconhecido chamado "ECDSA". Dito isto, eu gostaria de agradecer a algumas pessoas que me ajudaram a entender tudo isso, um particularmente que deseja permanecer anônimo, bem como as muitas páginas da Wikipédia I ligadas ao longo deste artigo, e Avi Kak graças ao seu papel explicando a matemática por trás ECDSA, e do qual eu tomei essas imagens gráfico aboves. Ps: Neste artigo , eu usei '20 bytes 'no meu texto para falar sobre a assinatura ECDSA porque isso é o que geralmente é usado como ele corresponde ao tamanho de hash SHA1 de 20 bytes e é isso que a segurança PS3 usa, mas o próprio algoritmo pode ser usado com qualquer tamanho de números. Pode haver outras imprecisões neste artigo, mas como eu disse, eu não sou um especialista, eu apenas mal aprendeu tudo isso na semana passada.