Förstå hur ECDSA skyddar dina data. (14 / 15 steg)

Steg 14: Betydelsen av en slumpmässig k

Låt oss diskutera nu hur och varför ECDSA underskrifter som Sony Playstation 3 var felaktig och hur det tillät hackare att få tillgång till PS3 ECDSA privata nyckel.

Så du kommer ihåg de ekvationer som behövs för att generera en signatur... R = k * G och S = k ^ -1 (z + dA * R) mod p... Tja denna ekvation styrka ligger i att du har en ekvation med två obekanta (k och dA) så det finns inget sätt att fastställa antingen en av dessa.

Dock säkerheten av algoritm baseras på dess genomförande och det är viktigt att se till att "k" genereras slumpmässigt och att det finns något sätt som någon kan gissa, beräkna eller använda en timing attack eller någon annan typ av attack för att hitta random värdet "k". Men Sony gjort ett stort misstag i genomförandet, de använde samma värde för "k" överallt, vilket innebär att om du har två signaturer, båda med samma k, då de båda har samma R -värdet, och det innebär att du kan beräkna k med två S underskrifter av två filer med kontrollsummor z och z' och signaturer S och S' respektive :

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’)

När du vet k, sedan ekvationen för S blir en ekvation med en okänd och löses sedan enkelt för dA :

dA = (S * k-z) / R

När du vet privat nyckel dA, kan du nu registrera dina filer och PS3 kommer att erkänna det som en giltig fil undertecknats av Sony. Det är därför det är viktigt att se till att slumptal används för att generera signaturen är faktiskt "kryptografiskt slumpmässiga". Detta är också anledningen till att det är omöjligt att ha en egen firmware ovan 3,56, helt enkelt för att sedan 3,56 version, Sony har fast ECDSA algoritm genomförandet och använde nya nycklar som det är nu omöjligt att hitta den privata nyckeln...

Ett annat exempel på denna fråga är när vissa bitcoin klienter används en icke-kryptografiskt slumptalsgenerator (på vissa webbläsare och vissa Android klienter) som fick dem att registrera sina transaktioner med samma värde för "k", och illvilliga människor kunde hitta den privata nyckeln i sin bitcoin plånbok och stjäla deras fonder.

Detta visar vikten av att använda ett verkligt slumptal varje gång du gör en signatur, som du kommer att utsätta den privata nyckeln om R (R, S) signatur paret värdet samma på två olika signaturer.

Ett bra skämt om detta visas i xkcd tecknad 221 (se bilden ovan) som blev gå till bilden att illustrera problemet. Bilden användes ofta åter när sådant genomförande fel av algoritmen hände.

ECDSA algoritmen är mycket säkert för vilka det är omöjligt att hitta den privata nyckeln... så länge genomförandet sker korrekt naturligtvis. Om det fanns ett sätt att hitta den privata nyckeln, kan då säkerheten för varje dator, webbplatsen, systemet äventyras eftersom en mängd system förlitar sig på ECDSA för deras säkerhet, och det är omöjligt att knäcka.