NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Generování hesla o délce 8 znaků

V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
Caster
Člen
Avatar
Caster:20.10.2022 20:47

Pokouším se rychle generovat všechny možné kombinace hesla o délce 8 znaků z předem dané množiny znaků. Jde o 628 = 2,18 E14 kombinací. Později budu paralelně počítat v jednom okamžiku na 10240 GPU vláknech současně.

Zkusil jsem:

#include <iostream>

#define pole_l 62
#define slovo_l 8

const char pole[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char slovo[8];

static int n = 8;
static int p = pole_l - 1;

void gen_slovo(void) {
        //slovo[n] = pole[p];
        printf("%c\n", pole[p]);
        p--;
        if (p < 0)
                return;
        gen_slovo();
        return;
}

int main()
{
        gen_slovo();

}

Chci docílit: Nyní funguje generování hesla pomocí rekurze pouze na jeden znak, potřebuji rozšířit na generování hesla o délce 8 znaků. Je také otázkou, zda generovat bez rekurze, aby např. nedošlo k přetečení paměti.

Program by měl vygenerované heslo uložit do pole "slovo" a vytisknout ho (pro kontrolu, lze pak okomentovat).

 
Odpovědět
20.10.2022 20:47
Avatar
Caster
Člen
Avatar
Caster:21.10.2022 8:53

Klasický přístup (bez dalších aktiv proběhne na stisk tlačítka):

#include <iostream>

#define pole_l 62
#define slovo_l 8

const char pole[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char slovo[8];

static int n = 8;
static int p = pole_l - 1;

void gen_slovo(void) {
        //slovo[n] = pole[p];
        printf("%c\n", pole[p]);
        p--;
        if (p < 0)
                return;
        gen_slovo();
        return;
}

int main()
{
        //gen_slovo();
        for (int i1 = 25; i1 > 0; i1--) {
                printf("x");
                for (int i2 = 25; i2 > 0; i2--) {
                        for (int i3 = 25; i3 > 0; i3--) {
                                for (int i4 = 25; i4 > 0; i4--) {
                                        for (int i5 = 25; i5 > 0; i5--) {
                                                for (int i6 = 25; i6 > 0; i6--) {
                                                        for (int i7 = 25; i7 > 0; i7--) {
                                                                for (int i8 = 25; i8 > 0; i8--) {

                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }

}
 
Nahoru Odpovědět
21.10.2022 8:53
Avatar
Caster
Člen
Avatar
Caster:21.10.2022 17:19

Další úprava:

#include <iostream>

#define pole_len 62


const char pole[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char slovo[] = "12345678";

int main()
{
        uint64_t t;
        uint64_t d;

        //62^8 = 2,18 E14
        t = pole_len;
        for (int p = 7; p > 0; p--) {
                t *= pole_len;
        }
        //t/65536
        d = t >> 16;
        t = 0;

        //gen_slovo();
        for (int i1 = 61; i1 >= 0; i1--) {
                /*printf("x");*/
                for (int i2 = 61; i2 >= 0; i2--) {
                        for (int i3 = 61; i3 >= 0; i3--) {
                                for (int i4 = 61; i4 >= 0; i4--) {
                                        for (int i5 = 61; i5 >= 0; i5--) {
                                                for (int i6 = 61; i6 >= 0; i6--) {
                                                        for (int i7 = 61; i7 >= 0; i7--) {
                                                                for (int i8 = 61; i8 >= 0; i8--) {
                                                                        slovo[0] = pole[i1];
                                                                        slovo[1] = pole[i2];
                                                                        slovo[2] = pole[i3];
                                                                        slovo[3] = pole[i4];
                                                                        slovo[4] = pole[i5];
                                                                        slovo[5] = pole[i6];
                                                                        slovo[6] = pole[i7];
                                                                        slovo[7] = pole[i8];
                                                                        if (t == 0) {
                                                                                printf("%s\n", slovo);  //Výpis vždy po 3 331 605 615 vygenerovaných heslech (62^8 / 65536)
                                                                                t = d;
                                                                        }
                                                                        t--;
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }

}
 
Nahoru Odpovědět
21.10.2022 17:19
Avatar
LacoS.
Člen
Avatar
LacoS.:11.11.2022 19:51

Ahoj.
v Tvojom rekurzivnom programe je dost chyb.

  • p ... nemoze byt globalna premenna, ale by sa mala ako parameter odovzdavat do rekurzie
  • rekurz.fcia: gen_slovo() ... by mala vracat cast slova, a potom ju pripajat
  • a dost podstatne je, ze rekurzivna fcia Ti vrati vzdy 1 hodnotu, takze tazko z toho vytiahnes vsetky mozne variacie
  • ak to chces rozhodit do viacerych procesorov, tak musis vymysliet, aby 1. CPU vypocitalo povedzme prvych 1.000.000 moznosti, 2. CPU zasa druhy milion atd.
 
Nahoru Odpovědět
11.11.2022 19:51
Avatar
Caster
Člen
Avatar
Odpovídá na LacoS.
Caster:11.11.2022 20:52

Díky za tipy. Program jsem mezitím již upravil pro paralelní práci na více jádrech GPU:

#include "cuda_runtime.h"
#include "device_launch_parameters.h"

#include <stdio.h>
#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

# define blocks 4
# define threads 992
# define characters 8

cudaError_t cudaStatus;

// "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
__constant__ char1 charset[] = { 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 password[characters];

        uint8_t counters[characters];
        uint64_t n = (pow(62, characters) / threads);   // Number of search cycles per thread

        // Nastavení počátečních hodnot hesla pro každé vlákno, odkud se mají začít generovat
        for (int i = characters - 1; i >= 0; i--) {
                counters[i] = (n * threadIdx.x / (uint64_t)pow(62, characters - 1 - i) % 62);
        }

        while (n > 0) {

                bool flag = false;
                for (int i = characters - 1; i >= 0; i--) {
                        password[i] = charset[counters[i]];
                        if (i == characters - 1) {
                                counters[i]++;
                                if (counters[i] > 61) {
                                        counters[i] = (uint8_t)0;
                                        flag = true;
                                }
                        }
                        else {
                                if (flag) {
                                        counters[i]++;
                                        if (counters[i] > 61) {
                                                counters[i] = (uint8_t)0;
                                        }
                                        else {
                                                flag = false;
                                        }
                                }
                        }
                }
                // Po odkomentování vypíše poslední 3 generované hesla
                //if (threadIdx.x == threads - 1 && blockIdx.x == blocks - 1 && n < 4) {
                //      printf("Thread[%d]",threadIdx.x);
                //      for (int i = 0; i < characters; i++) {
                //              printf(" %c", password[i]);
                //      }
                //      printf("\n");
                //}

                /* Test zda jsme našli password,
                pokud ano vypíšeme password, 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() {

        auto start = high_resolution_clock::now();

        cudaSetDevice(0);
        cudaStatus = cudaGetLastError();
                if (cudaStatus != cudaSuccess) {
                fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
         }
        blackcat << <blocks, threads >> > ();
        cudaStatus = cudaGetLastError();
                if (cudaStatus != cudaSuccess) {
                fprintf(stderr, "Kernel launch failed: %s\n", cudaGetErrorString(cudaStatus));
        }
        cudaDeviceSynchronize();
        cudaStatus = cudaGetLastError();
                if (cudaStatus != cudaSuccess) {
                fprintf(stderr, "cudaDeviceSynchronize returned error code %d after launching addKernel!\n", cudaStatus);
         }

        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<microseconds>(stop - start);
        printf("\nTime  = %llx (HEX)\n", duration.count());

        return 0;
}

Testováním na poslední vlákno a blok pro výpis posledních tři hesel se program hodně zpomalí. Bez výpisu trvá vygenerování všech hesel o délce 8 znaků 500 ms (cca 200 bilionů kombinací). S výpisem posledních 3 hesel pro heslo o délce 6 znaků běží program 21,5 s viz:

Thread[960] 9 9 9 9 9 7
Thread[960] 9 9 9 9 9 8
Thread[960] 9 9 9 9 9 9

Time  = 1490212 (HEX)

Program běží na mé grafické kartě NVIDIA GeForce GTX 960M v notebooku ASUS.

Akceptované řešení
+5 Zkušeností
Řešení problému
 
Nahoru Odpovědět
11.11.2022 20:52
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.