3. Passwort generator mit Bedingungen

Passwort generator mit Bedingungen

  • Z

    Ich würde vielleicht eher in Richtug des <random> headers schauen und dort was mit std::random_device und std::mt19937 basteln. Generell sollte hier noch gesagt werden (was aber eigentlich klar ist), dass du die Passwörter aus deinem Zufallsgenerator nicht für irgendwelche Kryptoprozesse nimmst. Also du solltest das so auch nicht für einen eigenen Passwortmanager und erst recht nicht zur Verschlüsselung von Daten nutzen.

    0
  • Mod

    Bis auf die zu kleine Entropie für den Seed ist das absolut in Ordnung, Passwörter so zu erzeugen. Na gut, das mit der zu kleinen Entropie für den Seed ist ein sehr gewichtiges Problem (Da war doch mal was mit einem bekannten Kryptosytstem, das genau dieses Problem hatte…) und nicht so ganz einfach zu beheben. Aber vom Prinzip her ist hier sonst alles ok.

    0
    F
     1 Antwort
  • F

    @SeppJ sagte in Passwort generator mit Bedingungen:

    Bis auf die zu kleine Entropie für den Seed ist das absolut in Ordnung, Passwörter so zu erzeugen.

    Vielleicht noch untersteichen, das das für den mt19937 gilt, und nicht für den LCG der hinter rand() steckt. Und natürlich sollte der Seed aus ner robusten Quelle stammen und nicht unbedingt von time(). Und gabs da nicht mal was mit dem seeden des mt19937? Der hat ein paar hundert Byte internen State, ich meine mal irgendwo in nem Vortrag gehört zu haben das es zumindest nicht ganz einfach ist, die Implementierung der Standardbibliothek korrekt zu seeden. Bin da aber nicht super-bewandert drin 😉

    Andererseits ist es wohl eine Übungsaufgabe, daher nicht ganz so wichtig, aber dennoch erwähnenswert, wenn man mal einen ernsthaften Generator stricken will.

    0
  • Mod

    Häh? Dass es aus time() stammt ist das Problem, nicht der Zufallsgenerator. Du wirst beim 30 Zeichen mit rand garantiert keine Probleme mit Korrelationen haben. Das Problem ist, dass es heute nur 86400 verschiedene time-Werte gab, dieses Jahr nur 31,536,000 und selbst diese Dekade nur 10x mehr. Was verschwindend geringe Zahlen für einen Computer sind, um alle Möglichkeiten durchzuprobieren, weil man ja weiß, dass das Passwort wahrscheinlich irgendwann in diesem Jahrzehnt erzeugt wurde. Viel, viel, viel weniger Möglichkeiten als ein 30-Zeichen-Passwort hätte, selbst wenn man die minimalen Korrelationen in rand zur Hilfe zieht.

    0
    F
     1 Antwort
  • S

    Hier ein paar Gedanken zum Thema Seed des mt19937. Wobei ich jetzt noch nicht verstanden habe, warum das für den mt19937 ein größeres Problem sein sollte, als für rand(). Habe da auf die Schnelle auch nichts zu gefunden.

    https://stackoverflow.com/a/45069417

    0
    F
     1 Antwort
  • F

    @SeppJ sagte in Passwort generator mit Bedingungen:

    Häh? Dass es aus time() stammt ist das Problem, nicht der Zufallsgenerator. Du wirst beim 30 Zeichen mit rand garantiert keine Probleme mit Korrelationen haben.

    Mein Gedanke war hier eher, dass z.B. ein 32-Bit-rand() mit dieser Methode nur 2322^{32} verschiedene Passwörter generieren kann, wenn man nicht noch ein paar extra srand() mit guten Seeds dazwischen schiebt. Das ist die Anzahl aller möglichen Zufallssequenzen und das schränkt meines erachtens bei 30 Zeichen langen Passwörtern des Passwort-Raum ganz schön ein.

    Wenn ich mal die Passwort-Regeln mal außer acht lasse, dann habe ich bei 30 aus 100 Zeichen 10030=1060100^{30}=10^{60} mögliche Passwörter, von denen aber nur etwa 4.29⋅1094.29 \cdot 10^{9} abgedeckt werden, oder etwa 1.84⋅10191.84 \cdot 10^{19} bei nem 64-Bit-rand(). Das sind schon ganz schön viele Größenordnungen weniger.

    0 1 Antwort
  • F

    @Schlangenmensch sagte in Passwort generator mit Bedingungen:

    Hier ein paar Gedanken zum Thema Seed des mt19937. Wobei ich jetzt noch nicht verstanden habe, warum das für den mt19937 ein größeres Problem sein sollte, als für rand(). Habe da auf die Schnelle auch nichts zu gefunden.

    Da müsste ich auch nochmal genauer suchen, habe da nur eine vage Erinnerung. Die Seed-Funktion, die nur einen einzigen Integer-Result-Typen entgegennimmt ist aber nicht ausreichend, den muss man schon mit einer Sequenz aus Seeds füttern, wie viele das auch immer sein müssen um den kompletten internen Zustand korrekt zu initialisieren.

    (btw., vielleicht driftet das hier mal wieder etwas zu speziell ab - immerhin scheint das nur eine Übungsaufgabe zu sein 😉 )

    0
  • Mod

    @Finnegan sagte in Passwort generator mit Bedingungen:

    Mein Gedanke war hier eher, dass z.B. ein 32-Bit-rand() mit dieser Methode nur 2322^{32} verschiedene Passwörter generieren kann, wenn man nicht noch ein paar extra srand() mit guten Seeds dazwischen schiebt. Das ist die Anzahl aller möglichen Zufallssequenzen und das schränkt meines erachtens bei 30 Zeichen langen Passwörtern des Passwort-Raum ganz schön ein.

    Ahh, das meintest du. Ja, stimmt. Ich dachte, du wolltest auf irgendwelche Korrelationen zwischen den Zeichen aus.

    0
  • E
    Gesperrt

    Ich möchte auch meinen Versuch zum Besten geben:

    #include <stdexcept>

#include <iostream>

#include <random>

#include <vector>

#include <algorithm>

using namespace std;

vector < vector < char16_t >> all_chars;
int32_t all_size = 0;

void init() {
  if (all_size != 0) {
    throw logic_error("already init");
  } {
    vector < char16_t > v;
    for (char16_t i = 'a'; i <= 'z'; i++) {
      v.push_back(i);
    }
    all_chars.push_back(v);
  } {
    vector < char16_t > v;
    for (char16_t i = 'A'; i <= 'Z'; i++) {
      v.push_back(i);
    }
    all_chars.push_back(v);
  } {
    vector < char16_t > v;
    for (char16_t i = '0'; i <= '9'; i++) {
      v.push_back(i);
    }
    all_chars.push_back(v);
  } {
    vector < char16_t > v;
    for (char16_t i = '!'; i <= '/'; i++) {
      v.push_back(i);
    }
    all_chars.push_back(v);
  }
  for (auto i: all_chars) {
    all_size += i.size();
  }
}

char16_t get_ch(int32_t i) {
  if (i < 0 || i >= all_size) {
    throw invalid_argument("");
  }
  for (int j = 0; j < all_chars.size(); j++) {
    if (i < all_chars[j].size()) {
      return all_chars[j][i];
    }
    i -= all_chars[j].size();
  }
  return 0;
}

int is_valid(string s) {
  {
    int i = 0;
    int c = 0;
    for (auto j: s) {
      if (find(all_chars[i].begin(), all_chars[i].end(), j) != all_chars[i].end()) {
        c++;
      }
    }
    if (c == 0) {
      return i;
    }
  } {
    int i = 1;
    int c = 0;
    for (auto j: s) {
      if (find(all_chars[i].begin(), all_chars[i].end(), j) != all_chars[i].end()) {
        c++;
      }
    }
    if (c < 6) {
      return i;
    }
  } {
    int i = 2;
    int c = 0;
    for (auto j: s) {
      if (find(all_chars[i].begin(), all_chars[i].end(), j) != all_chars[i].end()) {
        c++;
      }
    }
    if (c < 8) {
      return i;
    }
  } {
    int i = 3;
    int c = 0;
    for (auto j: s) {
      if (find(all_chars[i].begin(), all_chars[i].end(), j) != all_chars[i].end()) {
        c++;
      }
    }
    if (c < 2 || c > 5) {
      return i;
    }
  }
  return 4;
}

string get_pw() {
  string s = ""; {
    random_device rd; // obtain a random number from hardware
    mt19937 gen(rd()); // seed the generator
    uniform_int_distribution < > distr(0, all_size - 1); // define the range
    while (s.size() < 30) {
      s += (char) get_ch(distr(gen));
    }
  } {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution < > distr1(0, all_size - 1);
    int v;
    while ((v = is_valid(s)) != 4) {
      uniform_int_distribution < > distr2(0, all_chars[v].size() - 1);
      int r1 = distr1(gen);
      int r2 = distr2(gen);
      s[r1] = (char) all_chars[v][r2];
    }
  }
  return s;
}

int main() {
  init();
  cout << get_pw();
  return 0;
}

    Wäre sehr "lieb", wenn da mal jemand drüberschauen könnte...

    0
  • Mod

    Wenn sich der fast gleiche Code 5x wiederholt, macht man was falsch.

    0
    E
     1 Antwort
  • E
    Gesperrt

    Dieser Beitrag wurde gelöscht!
    0 1 Antwort
  • E
    Gesperrt

    Ok:

    #include <stdexcept>

#include <iostream>

#include <random>

#include <vector>

#include <algorithm>

using namespace std;

vector < vector < char16_t >> all_chars;
int32_t all_size = 0;

void add(char16_t from, char16_t to) {
  vector < char16_t > v;
  for (char16_t i = from; i <= to; i++) {
    v.push_back(i);
  }
  all_chars.push_back(v);
  all_size += v.size();
}

void init() {
  if (all_size != 0) {
    throw logic_error("already init");
  }
  add('a', 'z');
  add('A', 'Z');
  add('0', '9');
  add('!', '/');
  add('a', 'z');
}

char16_t get_ch(int32_t i) {
  if (i < 0 || i >= all_size) {
    throw invalid_argument("");
  }
  for (int j = 0; j < all_chars.size(); j++) {
    if (i < all_chars[j].size()) {
      return all_chars[j][i];
    }
    i -= all_chars[j].size();
  }
  return 0;
}

bool is_valid(string s, int i, int min, int max) {
  int c = 0;
  for (auto j: s) {
    if (find(all_chars[i].begin(), all_chars[i].end(), j) != all_chars[i].end()) {
      c++;
    }
  }
  return c >= min && c <= max;
}

int is_valid(string s) {
  if (!is_valid(s, 0, 1, all_size)) {
    return 0;
  }
  if (!is_valid(s, 1, 6, all_size)) {
    return 1;
  }
  if (!is_valid(s, 2, 8, all_size)) {
    return 2;
  }
  if (!is_valid(s, 3, 2, 5)) {
    return 3;
  }
  return 4;
}

string get_pw() {
  string s = ""; {
    random_device rd; // obtain a random number from hardware
    mt19937 gen(rd()); // seed the generator
    uniform_int_distribution < > distr(0, all_size - 1); // define the range
    while (s.size() < 30) {
      s += (char) get_ch(distr(gen));
    }
  } {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution < > distr1(0, all_size - 1);
    int v;
    while ((v = is_valid(s)) != 4) {
      uniform_int_distribution < > distr2(0, all_chars[v].size() - 1);
      int r1 = distr1(gen);
      int r2 = distr2(gen);
      s[r1] = (char) all_chars[v][r2];
    }
  }
  return s;
}

int main() {
  init();
  cout << get_pw();
  return 0;
}

    Beispiel für ein sicheres Passwort: qJb1t3SdXL3-iymtN+90h1rOS,z8+7 😉 (Nur ein Spaß, jedes "bekannte" Passwort ist nicht mehr sicher...)

    Aber... ich laufe doch damit in ein Halteproblem - oder nicht?

    0
  • B

    @Jockelx sagte in Passwort generator mit Bedingungen:

    @Belli sagte in Passwort generator mit Bedingungen:

    Na klar, warum soll das hässlich sein?

    Weil ich nichts von shufflen geschrieben habe!? Und dann passt es zur Aufgabe, ist aber hässlich.

    Ach ja klar, weil Du es nicht geschrieben hast, logisch ...

    0
    J
     1 Antwort
  • B

    @helpinfo sagte in Passwort generator mit Bedingungen:

    @Belli wie shuffle ich die einzelnen bedingungen in einem string?

    mit std::random_shuffle

    0
  • Mod

    @EinNutzer0 sagte in Passwort generator mit Bedingungen:

    @SeppJ sagte in Passwort generator mit Bedingungen:

    Wenn sich der fast gleiche Code 5x wiederholt, macht man was falsch.

    fast 😉

    Ich weiß schon, was ich gesagt habe. Dass du das nicht verstehst, weiß ich. Aber trotzdem ist meine Aussage korrekt, dass du hier was falsch machst, mit genau der genannten Begründung.

    0
    E
     1 Antwort
  • E
    Gesperrt

    @SeppJ sagte in Passwort generator mit Bedingungen:

    @EinNutzer0 sagte in Passwort generator mit Bedingungen:

    @SeppJ sagte in Passwort generator mit Bedingungen:

    Wenn sich der fast gleiche Code 5x wiederholt, macht man was falsch.

    fast 😉

    Ich weiß schon, was ich gesagt habe. Dass du das nicht verstehst, weiß ich. Aber trotzdem ist meine Aussage korrekt, dass du hier was falsch machst, mit genau der genannten Begründung.

    Siehe doch https://www.c-plusplus.net/forum/topic/353721/passwort-generator-mit-bedingungen/19#

    ... anstatt eine unkonstruktive Antwort zu schreiben.

    Meiner Meinung nach, gibt es ein algorithmisches Problem, wenn es zu viele Sonderzeichen gibt.

    0
  • S

    Das sieht an einigen Stellen irgendwie umständlich aus.

    Prinzipiell fände ich es schön, so einen PW Generator als Klasse zu kapseln. Der Klasse könnte man dann verschiedene Alphabete, aus denen zu ziehen ist mit geben, so wie zugehörige Einschränkungen. Das würde dir vlt auch helfen, das Problem weiter zu abstrahieren und den Code klarer zu schreiben.

    Außerdem @EinNutzer0 könnte dir ein Blick in die Standard Lib helfen, std::random_shuffle wurde schon genannt, ich hätte noch std::generate_n hilfreich gefunden, eine Art std::count hast du selbst geschrieben.

    @EinNutzer0 sagte in Passwort generator mit Bedingungen:

    Aber... ich laufe doch damit in ein Halteproblem - oder nicht?

    Das Halteproblem ist eine bestimmte Fragestellung aus der theoretischen Informatik, ich gehe davon aus, dass du meinst, dass dein Algo nicht deterministisch ist. Und ja, du gehst halt davon aus, dass deine Erstellung irgendwann schon zufällig eine gültige Kombination findet. Das kann auch mal länger dauern.

    Eine Mögliche Lösung dafür wurde im Thread ja auch schon genannt, Anforderungen nacheinander Abarbeiten und dann nochmal durchwürfeln.

    1
    E
     1 Antwort
  • E
    Gesperrt

    @Schlangenmensch sagte in Passwort generator mit Bedingungen:

    Prinzipiell fände ich es schön, so einen PW Generator als Klasse zu kapseln.

    Danke, ich hab es mal neu gemacht:

    #include <stdexcept>
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

#define SIZEC 30

using namespace std;

class alphabet
{
private:
    vector<char16_t> all_chars;
    size_t min;
    size_t max;

public:
    static vector<alphabet> alphabets;
    static size_t all_count;
    static random_device rd;
    static mt19937 gen;
    alphabet(char16_t from, char16_t to, size_t min, size_t max);
    char16_t get_random_char();
    static char16_t get_random_overall_char();
    int search_random_char(string s);
    int is_valid(string s);
    string make_valid(string s);
};

alphabet::alphabet(char16_t from, char16_t to, size_t min, size_t max)
{
    for (char16_t i = from; i <= to; i++)
    {
        all_chars.push_back(i);
    }
    all_count += all_chars.size();
    this->min = min;
    this->max = max;
}

char16_t alphabet::get_random_char()
{
    uniform_int_distribution<> distr(0, all_chars.size() - 1);
    return all_chars[distr(gen)];
}

char16_t alphabet::get_random_overall_char()
{
    uniform_int_distribution<> distr(0, all_count - 1);
    int i = distr(gen);
    for (auto a : alphabets)
    {
        if (i < a.all_chars.size())
        {
            return a.all_chars[i];
        }
        i -= a.all_chars.size();
    }
    return 0;
}

int alphabet::search_random_char(string s)
{
    uniform_int_distribution<> distr(0, s.size() - 1);
    int i;
    do
    {
        i = distr(gen);
    } while (find(all_chars.begin(), all_chars.end(), s[i]) == all_chars.end());
    return i;
}

int alphabet::is_valid(string s)
{
    int c = 0;
    for (auto i : s)
    {
        if (find(all_chars.begin(), all_chars.end(), i) != all_chars.end())
        {
            c++;
        }
    }
    if (c < min)
    {
        return -1;
    }
    if (c > max)
    {
        return +1;
    }
    return 0;
}

string alphabet::make_valid(string s)
{
    uniform_int_distribution<> distr(0, s.size() - 1);
    int v;
    while ((v = is_valid(s)) != 0)
    {
        if (v < 0)
        {
            s[distr(gen)] = (char)get_random_char();
        }
        else
        {
            s[search_random_char(s)] = get_random_overall_char();
        }
    }
    return s;
}

void init()
{
    alphabet::all_count = 0;
    alphabet::rd;
    alphabet::gen = mt19937(alphabet::rd());
    alphabet::alphabets.push_back(alphabet('a', 'z', 1, SIZEC));
    alphabet::alphabets.push_back(alphabet('A', 'Z', 6, SIZEC));
    alphabet::alphabets.push_back(alphabet('0', '9', 8, SIZEC));
    alphabet::alphabets.push_back(alphabet('!', '/', 2, 5));
}

string generate_valid_password()
{
    string s = "";
    while (s.size() < SIZEC)
    {
        s += (char)alphabet::get_random_overall_char();
    }
    bool f;
    do
    {
        f = false;
        for (auto a : alphabet::alphabets)
        {
            if (a.is_valid(s) != 0)
            {
                f = true;
                a.make_valid(s);
            }
        }
    } while (f);
    return s;
}

int main()
{
    init();
    cout << generate_valid_password();
    cout << endl;
    return 0;
}

    Leider ist jetzt irgendwo ein Übersetzungsfehler, den ich nicht sehe... Habt ihr eine Idee?

    0
    S
     1 Antwort
  • S

    @EinNutzer0 Warum hat deine Klasse statische Membervariablen? Die Initalisierung dieser findet nicht in einer Funktion statt, dann meckert der Linker auch nicht.

    size_t alphabet::all_count = 0;
random_device alphabet::rd;
mt19937 alphabet::gen = mt19937(alphabet::rd());
vector<alphabet> alphabet::alphabets;

void init()
{
  alphabet::alphabets.push_back(alphabet('a', 'z', 1, SIZEC));
  alphabet::alphabets.push_back(alphabet('A', 'Z', 6, SIZEC));
  alphabet::alphabets.push_back(alphabet('0', '9', 8, SIZEC));
  alphabet::alphabets.push_back(alphabet('!', '/', 2, 5));
}

    Warum heißt deine Klasse alphabet, finde ich bei der Aufgabenstellung irreführend.

    Und nochmal, warum dieses ganze Static?

    0
  • E
    Gesperrt

    @Schlangenmensch Hattest recht, static überflüssig...

    Ich hab es doch noch hinbekommen... 😆 Auch, wenn ich nicht weiß, wie...

    siehe bitte neuen Thread

    Würde mich wieder darüber freuen, wenn jemand noch einmal kurz drüberschauen könnte.

    Das soll natürlich nicht besser sein als shuffle, es ist nur ein anderer Ansatz.

    0
    S
     2 Antworten
Anmelden zum Antworten