Trädvy Permalänk
Medlem
Registrerad
Dec 2018

Kryptering med SHA256

Här kan man testa:
kryptering och openmp

Det fungerar med min c-kompilator. Men jag är lite förbryllad över hur det fungerar.
Man behöver vänta en stund för att kunna köra 2 gånger.
Är man otålig får man ingen utskrift!
Normalt för kryptering?
Blockering efter första körningen?

Trädvy Permalänk
Medlem
Registrerad
Dec 2018

Open SSL/SHA

För Raspberry Pi 4 ingår denna kryptering i gcc.
För X86(gcc version9.2) behöver den laddas ner från Github.

Trädvy Permalänk
Medlem
Plats
NördCentrum
Registrerad
Jun 2011

SHA256 är inte en krypteringsalgoritm, utan en hashningsalgoritm. Både kryptering och hashning kan användas i kryptografiska sammanhang, men de är inte samma sak och används inte till samma syfte. Kryptering är en tvåvägsrelation -- med en nyckel kan du kryptera din hemliga data till ett otolkningsbart format, och med samma eller en annorlunda nyckel kan du dekryptera den krypterade datan till orginalet. Hashning å andra sidan är en enkelriktad relation -- förutom via brute-force är tanken att du bara ska kunna "kryptera" datan åt ett håll, från ursprungsformatet till ett otolkningsbart format, men inte tillbaka.

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

Trädvy Permalänk
Medlem
Plats
NördCentrum
Registrerad
Jun 2011
Skrivet av Greyguy1948:

Här kan man testa:
kryptering och openmp

Det fungerar med min c-kompilator. Men jag är lite förbryllad över hur det fungerar.
Man behöver vänta en stund för att kunna köra 2 gånger.
Är man otålig får man ingen utskrift!
Normalt för kryptering?
Blockering efter första körningen?

För att svara på din fråga så är programmet du länkar inkorrekt -- det innehåller ett race condition som ofta resulterar i att inte alla resultat skrivs ut. Specifikt är det följande rader som felar när programmet körs multitrådat:

byte *hash = SHA256(password, 5, 0); if (matches(one, hash) || matches(two, hash) || matches(three, hash)) printResult(password, hash);

I dokumentationen för SHA256 funktionen står det att "If md is NULL, the digest is placed in a static array. Note: setting md to NULL is not thread safe.". md är den tredje parametern, som i ovan kod precis sätts till just 0 (null). SHA256 lägger alltså resultatet i en global, statisk array, och om flera trådar exekverar den sektionen samtidigt kommer de skriva över samma array hejvilt. Ofta kommer en tråd skriva sitt resultat, men läsa en annan tråds resultat på raden efter. Lösningen är att allokera ut-arrayen i förväg och skicka in den som tredje parameter till SHA256, så försvinner data-racet. En alternativ lösning är att använda en mutex för att se till att bara en tråd i taget exekverar just ovanstående sektion, men det är en sämre och mer komplex lösning.

Den bästa lösningen hade nog dock varit att inte försöka skriva parallell kod i C/C++ från första början -- språken är verkligen inte gjorda för det! Bättre att använda ett språk som gör data-races omöjliga genom ett smart typsystem eller dyl., e.g. Rust som garanterar att data som är delad inte får muteras utan mutex och att data som muteras inte får delas. Ett annat språk (som dock inte är lämpligt för just systemprogrammering) är Haskell, som garanterar trådsäkerhet genom att aldrig tillåta mutation, oavsett om datan är delad eller inte.

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

Trädvy Permalänk
Medlem
Plats
NördCentrum
Registrerad
Jun 2011

Följande är implementation och benchmark för båda mina föreslagna lösningar. Jag har kört båda flera ggr i rad, och de ger alltid rätt svar. De kör på min server med 2st Xeon X5570 processorer, och export OMP_NUM_THREADS=16.

Lösning 1 med förallokerad ut-array till SHA256, ca. 0.6s:

int main(int argc, char **argv) { #pragma omp parallel for for (int a = 0; a < 26; a++) { byte password[5] = { 97 + a }; byte* one = StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"); byte* two = StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"); byte* three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"); for (password[1] = 97; password[1] < 123; password[1]++) { for (password[2] = 97; password[2] < 123; password[2]++) { for (password[3] = 97; password[3] < 123; password[3]++) { for (password[4] = 97; password[4] < 123; password[4]++) { byte hash[32]; SHA256(password, 5, hash); if (matches(one, hash) || matches(two, hash) || matches(three, hash)) printResult(password, hash); } } } } free(one); free(two); free(three); } return 0; }

Lösning 2 med mutex-lås (mer specifikt omp critical annotering, men i praktiken lär det vara mutex-lås), ca. 10s:

int main(int argc, char **argv) { #pragma omp parallel for for (int a = 0; a < 26; a++) { byte password[5] = { 97 + a }; byte* one = StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad"); byte* two = StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b"); byte* three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f"); for (password[1] = 97; password[1] < 123; password[1]++) { for (password[2] = 97; password[2] < 123; password[2]++) { for (password[3] = 97; password[3] < 123; password[3]++) { for (password[4] = 97; password[4] < 123; password[4]++) { #pragma omp critical { byte* hash = SHA256(password, 5, 0); if (matches(one, hash) || matches(two, hash) || matches(three, hash)) printResult(password, hash); } } } } } free(one); free(two); free(three); } return 0; }

Som jag förväntade mig var den första lösningen överlägset den snabbaste. Låsen i den andra lade på otroligt mycket overhead -- så mycket så att den till och med är långsammare än en sekventiell version som tog ca. 4s på samma dator!

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

Trädvy Permalänk
Medlem
Registrerad
Dec 2018
Skrivet av Bryal:

SHA256 är inte en krypteringsalgoritm, utan en hashningsalgoritm. Både kryptering och hashning kan användas i kryptografiska sammanhang, men de är inte samma sak och används inte till samma syfte. Kryptering är en tvåvägsrelation -- med en nyckel kan du kryptera din hemliga data till ett otolkningsbart format, och med samma eller en annorlunda nyckel kan du dekryptera den krypterade datan till orginalet. Hashning å andra sidan är en enkelriktad relation -- förutom via brute-force är tanken att du bara ska kunna "kryptera" datan åt ett håll, från ursprungsformatet till ett otolkningsbart format, men inte tillbaka.

Tack!
I mitt första exempel används tydligen en nyckel.
Men i övriga exempel man ser på Rosertta code finns ingen sådan.
SHA256
Varför två bibliotek vid kompilering -lssl och -lcrypto om det inte är någon kryptering?
Bitcoin validation
Här räcker det tydligen med -lcrypto.

Bitcoin_public_point
Ingen uppgift om kompilering....

Trädvy Permalänk
Medlem
Registrerad
Dec 2018

Stäng av Open MP

Skrivet av Greyguy1948:

Här kan man testa:
kryptering och openmp

Det fungerar med min c-kompilator. Men jag är lite förbryllad över hur det fungerar.
Man behöver vänta en stund för att kunna köra 2 gånger.
Är man otålig får man ingen utskrift!
Normalt för kryptering?
Blockering efter första körningen?

När jag stängt av Open MP fungerar det bättre.
Alla tre svaren kommer i rätt ordning varje gång!

Trädvy Permalänk
Medlem
Plats
NördCentrum
Registrerad
Jun 2011
Skrivet av Greyguy1948:

Varför två bibliotek vid kompilering -lssl och -lcrypto om det inte är någon kryptering?

-lssl behövs inte faktiskt -- ytterligare ett fel som uppladdaren på Rosettacode gjort. Vidare innehåller libcrypto inte bara krypteringgsalgoritmer, utan även andra kryptografiska funktioner som hashningsalgoritmer.

Skrivet av Greyguy1948:

När jag stängt av Open MP fungerar det bättre.
Alla tre svaren kommer i rätt ordning varje gång!

Ja, som jag sa beror felet på ett data-race som uppstår när det citerade stycket exekveras parallellt. Kör man koden på bara en tråd kan inte data-races uppstå -- varför man kan använda mutexer för att se till att bara en tråd exekverar sektionen i taget.

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC