Diskuze: xorshift128 generátor
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
DarkCoder:2.11.2022 10:48
Než řešit Xorshift by mohlo být lepší zajímat se rovnou o Xoroshiro128+, který je jeho nástupcem
Caster:2.11.2022 11:38
Ten ale nemá tak dobré recenze
ohledně rozložení generovaných čísel viz
The lowest bits of the output generated by xoroshiro128+ have low quality.
Jde mi hlavně o generování celých čísel do 100.
DarkCoder:2.11.2022 12:19
Pokud Ti jde o tak malý rozsah tak přeci není problém nejnižší bity
před výstupem odstranit.
Popřípadě není nic jednoduššího než se dotázat autora tím že mu
pošleš email.
Ti určitě z fleku doporučí vhodnou variantu.
Caster:2.11.2022 13:12
Už jsem mu poslal mail. Nicméně než dostanu odpověď bych chtěl vyzkoušet "můj" kód viz výše.
Co tam dát místo funkce arc4random(), např.
timems() případně použít
_rdrand64_step(unsigned long long*); bigstate proměnné jsou ale
256 bitů.
int main()
{
bigstate0 = arc4random();
bigstate1 = arc4random();
vysledek = rbinom_AVX2((size_t) 8);
printf("Vysledek = %llx\n", vysledek);
return 0;
}Caster:2.11.2022 13:38
Zkusil jsem ještě zadat
bigstate0 = _mm256_setr_epi32(0x1234, 0x2345, 0x3456, 0x4567, 0x5678, 0x6789, 0x789A, 0x89AB);
bigstate1 = _mm256_setr_epi32(0x1234, 0x2345, 0x3456, 0x4567, 0x5678, 0x6789, 0x789A, 0x89AB);ale jako výsledek dostanu 0. Nevím přesně jestli mohu jako parametr
funkce (int64_t size) zadat takto
rbinom_AVX2((int64_t) 8);Caster:2.11.2022 16:32
Odpověď od Sebastiana z Itálie:
I noticed your article about Xoroshiro128+. I am trying to run AVX2 with the code suggested in the Generating random number from a binomial distribution but don't know how to replace Linux function arc4random() with Visual Studio 2022 C++ function to seed the bigstate0, bigstate1 variables.
First, this is xorshift. Don't use it. Use, like, xoroshiro or xoshiro instead.
https://prng.di.unimi.it/
I would like to generate the integer number in the range 0-100.
You need a way to do range reduction. https://lemire.me/…o-reduction/
Z těch odkazů mi není úplně jasné, jak udělat generátor náhodných čísel pro generování hesel (malá, velká písmena abecedy a číslice tj. 62 možností) o délce 8 znaků s tím, že program pro prolomení hesla spustím současně na 20 480 vláknech GPU. Potřebuji, aby každé vlákno dostalo jiné heslo k otestování.
DarkCoder:4.11.2022 12:59
Z odkazů to nevyčteš, tam to není. Je to o představivosti a logice. Máš-li seznam povolených znaků, pak z počtu znaků můžeš určit maximální hodnotu čísla které můžeš použít k vygenerování znaku. Každý znak hesla vygeneruješ ze seznamu tak že vygenerované číslo použiješ jako index pole povolených znaků.
Abys měl jasnější představu, zde je příklad který generuje 100 hesel o délce 8 znaků, kde znak je tvořen malými písmeny, velkými písmeny a číslicemi. V příkladu jsou použity funkce srand() a rand() ze standardní knihovny. Ty si můžeš nahradit jinou funkcí.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SIZE 8
#define LIMIT 100
int main(void) {
const char* signs = "abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";
size_t count = strlen(signs);
char pass[SIZE];
srand((unsigned)time(NULL));
for (size_t i = 0; i < LIMIT; i++) {
for (size_t j = 0; j < SIZE; j++) {
pass[j] = signs[rand() % count];
putchar(pass[j]);
}
putchar('\n');
}
return 0;
}Unikátnost hesla je v rozporu s náhodným generováním, pokud neprovádíš generování se seznamu a upravování limitu, což neděláš. A dělat nebudeš při tak velkém počtu variací. Stejně tak i v mém uvedeném případě unikátnost hesla není zaručena. To bys musel postupovat tak jak už jsem Ti v předchozích diskuzích radil - systematicky. Pro každé vlákno konkrétní rozsah s jasným zdvihem hodnot (jako mechanický elektroměr).
Caster:4.11.2022 13:06
Chtěl bych vyzkoušet dva přístupy.
- s generováním náhodných hesel
- "natvrdo" v cyklu projet všech 628 kombinací
Tam mám problém, jak zadat 20 480 vláknům rozsah cyklu (tj. na každé vlákno "zbude" prověřit "jen" 10,7 E9 kombinací).
DarkCoder:4.11.2022 13:54
Však to vyzkoušej. V prvním případě jsem Ti poslal takřka řešení, ve druhém detailně poradil jak to udělat. Počet variací je n na k, počet hesel na vlákno je (n na k) / pocet_vlaken. Rozsah pro první vlákno je 0 až ((n na k) / pocet_vlaken) - 1.
Máš počet znaků které tvoří heslo 62. První testované heslo je heslo, jehož prvky jsou nulovými indexy pole povolených znaků. Tedy aaaaaaaa. 62. heslo je heslo, kde poslední prvek pole hesla je 61. prvek pole povolených znaků a to je aaaaaaa9.
Z prvního odstavce je patrný jasný rozsah na vlákno, ty teď potřebuješ
napsat funkci která převádí číslo na heslo.
Tedy:
0 odpovídá aaaaaaaa (1. heslo)
61 odpovídá aaaaaaa9 (62. heslo)
62 odpovídá aaaaaaba (63. heslo)
atd..
To co budeš potřebovat je práce s celočíselným dělením a zbytkem po celočíselném dělení.
Takže kdyby Ti vyšel rozsah pro první vlákno 0 až 62, tak máš rozsah
hesel aaaaaaaa až aaaaaaba.
Druhé vlákno bude mít rozsah 63 - 125, třetí 126 - 188, atd...
Poté co budeš mít napsanou funkci na převod čísla na odpovídající heslo. Vytvoříš funkci pro inkrementaci hesla. Kde z hesla aaaaaaaa dostaneš aaaaaaab. To už je již zmiňovaný mechanický elektroměr. Funkci pak budeš volat v cyklu. Počet hesel na vlákno znáš. To je celé.
Nastavení hodnot proměnných cyklu pro heslo o délce 2 znaků jsem si musel vyzkoušet v Excelu. h0 a h1 je index na pole možných hodnot znaků pro první a druhé písmeno, který se budu v cyklu incrementovat a po dosažení 62 se h0 a h1 vždy vynuluje. Další proměnná bude samozřejmě počítat, zda již proběhl počet cyklů pro dané vlákno (kombinaci / threads).
Výsledek zkušebního programu níže:
Vlakno[0]: 0 0
Vlakno[1]: 15 31
Vlakno[2]: 31 0
Vlakno[3]: 46 31#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>
#include <iostream>
# define threads 4
//# define kombinaci 218340105584896
# define kombinaci 3844
__global__ void blackcat(void) {
//uint8_t h0, h1, h2, h3, h4, h5, h6, h7;
//printf("Vlakno[%i] = %i: %i %i %i %i %i %i %i %i\n", threadIdx.x, h0, h1, h2, h3, h4, h5, h6, h7);
uint8_t h0, h1;
h0 = kombinaci / threads * threadIdx.x / 62;
h1 = kombinaci / threads * threadIdx.x % 62;
printf("Vlakno[%i]: %i %i\n", threadIdx.x, h0, h1);
}
int main() {
cudaSetDevice(0);
blackcat << <1, threads >> > ();
cudaDeviceSynchronize();
return 0;
}Ještě zvážím, zda nedat indexy pole hodnot znaků do pole místo používání samostatných proměnných. Půjde samozřejmě o rychlost, což si v programu změřím.
DarkCoder:4.11.2022 19:40
Na Excel úplně zapomeň, nepřináší Ti žádný užitek. Piš vše v C, stejně to v něm musíš napsat. Nezadávej konstantní literaly ručně ale dopočítávej je. Podívej se na můj příklad co jsem Ti poslal jak určuji počet znaků. První co teď musíš udělat je vytvořit funkci počítadla v rozsahu. Přesah hodnoty není jen nulování daného prvku pole ale i inkrementace vyššího bytů dokud nezkonci přesah. Samozřejmě že s jednotlivými buňkami pracuješ v poli, přeci to pak nebudeš skládat dohromady.
DarkCoder:4.11.2022 19:52
To vše je ale jen začátek toho co tě teprve čeká, neboť rozdělení do vláken Ti pouze urychluje mezivypočty. Jelikož roura kterou budeš stavět má jen jeden vstup, budeš muset přepínat mezi vlákny nebo ve funkci alokovat cyklické frontu pro uchovávání výsledků, aby byl potenciál vlákna vyčerpán na maximum. V opačném případě extrémně ztratíš výkon. Dále lepší než práce s rozsahy bude lepší aby funkce brala začátek a počet interakcí nikoli krajní koncovou hodnotu. Výsledkem bude opět vyšší navýšení výkonu. Výhodou funkce s rozsahem je ze můžeš rozdělit hledání do několika fází když by kalkulace byla extrémně dlouhá. Což je tvůj případ.
DarkCoder:4.11.2022 20:45
Nejlepší bude, když si vše vyzkoušíš v programu s menšími hodnotami, aby si se dostal brzy k výsledku o ověřil si tak funkčnost dřív než vše budeš aplikovat a požadovanou verzi.
Takže 4 vlákna, povolené znaky jen čísla, heslo o délce 4 znaků. Tedy 10000 variací, 2500 hesel na vlákno.
Nakonec když se podíváš tak je vše o tom připravit si heslo. Můžeš vyzkoušet verzi, kde vlákna budou generovat buffery o n heslech podle potřeby a pak vše akorát z bufferu tahat.
Zkusím to nejdříve na 4 vláknech a 4 znacích jak píšeš.
Program bude používat pouze proměnné v GPU včetně sady znaků viz deklarace dostupná všem vláknům. Další vývoj programu (vlastní šifrování hesla pomocí PKCS5_PBKDF2_HMAC_SHA1 a HMAC(EVP_sha1() mám odzkoušené, jde v podstatě o dva řádky kódu + porovnání výsledku pomocí memcmp()).
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>
#include <iostream>
// NVIDIA GeForce GTX 960M v NB má 5 Multiprocessors * 32 vláken * 128 CUDA Cores/MP = 20 480
# define threads 20480
# define pismen 8
// "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
__constant__ char1 sada[] = { 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 };
__global__ void blackcat(void) {
char1 heslo[pismen];
uint8_t pole[pismen];
uint64_t n = 62 ^ pismen / threads; // Počet cyklů hledání na jednom vlákně
for (int i = pismen; i > 0; i--) {
pole[i] = n * threadIdx.x / 62 ^ i % 62;
}
while (n > 0) {
for (int i = pismen; i > 0; i--) {
heslo[i] = sada[pole[i]];
}
/* Test zda jsme našli heslo,
pokud ano vypíšeme heslo, ukončíme všechna vlákna a předčasně se vrátíme z funkce,
možná bude dobré občas vypsat čas běhu, abychom věděli, že program stále běží */
// Incrementace indexů pole[], ošetřit jejich vynulování při přetečení 61
n--;
}
}Caster:5.11.2022 22:05
Generování hesel na více vláknech (961) pro 4 písmena (14 776 336 kombinací) mi už funguje v pořádku viz:
Thread[960] 9 9 9 7
Thread[960] 9 9 9 8
Thread[960] 9 9 9 9a testovací CUDA program:
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>
#include <iostream>
// NVIDIA GeForce GTX 960M v NB má 5 Multiprocessors * 32 vláken * 128 CUDA Cores/MP = 20 480
# define threads 961
# define pismen 4
// "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
__constant__ char1 sada[] = { 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 };
__global__ void blackcat(void) {
char1 heslo[pismen];
uint8_t pole[pismen];
uint64_t n = (pow(62, pismen) / threads); // Počet cyklů hledání na jednom vlákně
for (int i = pismen - 1; i >= 0; i--) {
pole[i] = (n * threadIdx.x / (uint64_t)pow(62, pismen - 1 - i) % 62);
}
while (n > 0) {
bool flag = false;
for (int i = pismen - 1; i >= 0; i--) {
heslo[i] = sada[pole[i]];
if (i == pismen - 1) {
pole[i]++;
if (pole[i] > 61) {
pole[i] = (uint8_t)0;
flag = true;
}
}
else {
if (flag) {
pole[i]++;
if (pole[i] > 61) {
pole[i] = (uint8_t)0;
}
else {
flag = false;
}
}
}
}
if (threadIdx.x == 960 && n < 4) {
printf("Thread[%d]",threadIdx.x);
for (int i = 0; i < pismen; i++) {
printf(" %c", heslo[i]);
}
printf("\n");
}
/* Test zda jsme našli heslo,
pokud ano vypíšeme heslo, ukončíme všechna vlákna a předčasně se vrátíme z funkce,
možná bude dobré občas vypsat čas běhu, abychom věděli, že program stále běží */
n--;
}
}
int main() {
cudaSetDevice(0);
blackcat << <1, threads >> > ();
cudaDeviceSynchronize();
return 0;
}Teď má ale "problém", kam do projektu CUDA programu ve VS 2022 přidat adresář s include OpenSSH knihovnou, abych mohl začít šifrovat. V C++ programu bez CUDA s tím nemám žádný problém: C/C++. Obecné, Další adrsáře k zahrnutí: C:\Program Files\FireDaemon OpenSSL 3\include. V CUDA vlastnostech programu je to ale jiné.
Caster:6.11.2022 23:46
Bez výpisu posledních 3 generovaných hesel jsem pro 8 písmen dosáhl na GPU rychlosti 404 522 305 937 022 hesel/s (tj. 404 bilionů hesel/s). Doba výpočtu 539,7 ms 😎 (z toho spuštění jádra cca 500 ms). Jeden cyklus je 2,5E-15 s (na CPU pouze prázdný cyklus jen decrement čítače (628 = 218 340 105 584 896) 175,2E-12 s; program běžel 10,6 hodin).
Teď se pustím do naprogramování šifrovacích funkcí PKCS5_PBKDF2_HMAC_SHA1 a HMAC(EVP_sha1() na GPU 😉.
Zobrazeno 18 zpráv z 18.