Schloss knacken in C?
In dieser Aufgabe geht es darum, für ein digitales Schloss den passenden Schlüssel zu finden. Dabei werden sowohl Schloss als auch Schlüssel durch eine Integer-Variable repräsentiert (genauer gesagt die Binärrepräsentation). Damit ein Schlüssel zu einem Schloss passt, muss der Schlüssel an Stellen, an denen 0-en im Schloss zu finden sind, eine 1 aufweisen. Das Gleiche gilt im Gegenzug für die 1-en. Also muss der Schlüssel das bitweise Komplement des Schlosses sein.
Schlüssel: 010001110
Schloss: 101110001
Die Schwierigkeit besteht nun darin, dass der Aufbau des Schlosses nicht bekannt ist. Es muss also probiert werden. Dieses kann mit einer Funktion checkKey(....) geschehen. Sie nimmt einen Schlüssel, testet ihn am Schloss und liefert die Anzahl der richtigen Bits als Rückgabewert. Falls der richtige Schlüssel gefunden ist, wird eine entsprechende Meldung ausgegeben.
das heißt ich gebe zum Beispiel 3 ein wandle sie in binär umwandeln und dan das Komplement bilden oder was
5 Antworten
Da ich jetzt nur das Handy zum Schreiben zur Hand habe verzichte ich auf c-Code und schreibe den Lösungsweg einfach als Pseudocode...
Als erstes weißt Du der vorzeichenlose Integervariable schloss den den Wert in binäre Schreibweise zu.
unsigned int schloss = 0b101110001
Da es blöd wäre jeden Schlüssel vor dem Vergleichen in ein "Negativ" zu verwandeln , machst Du das Schloss "links".
unsigned int antischloss = ~schloss ; bitweise complement.
Jetzt musst du nur noch in einer Schleife testen welcher Integerwert gleich Antischloss ist.
unsigned int schluessel
for( schluessel= 0 ; schluessel < 0b111111111; i÷÷)
{
printf("\nteste Schluessel: %u ", schluessel);
if( schluessel == antischloss )
{
printf("der Schlüssel war es");
break; //Schleife abbrechen
}
}
So in etwa sollte es aussehen...
Wie man einen uint in einen String aus 0en und 1en verwandelt erspare ich mir auf dem Handy.
Wichtig ist eigentlich nur die complement-operation...
So in etwa sollte es aussehen... compilieren oder testen von Code geht leider nicht auf dem Handy...deshalb kann ich nur "aus der Hüfte schießen "
Zumindest solltest Du jetzt einen Lösungsvorschlag haben, den Du weiterverfolgen kannst.
In der Frage waren 9 Bit vorgegeben... insoweit genügt es einfach bruteforce das Komplement zu vergleichen.
Mir ist durchaus klar das dies bei einem höherbitigen Schlüssel nicht so einfach geht.
Jemand der seine Frage im GF stellen muss und nicht selbst eine so triviale Lösung findet, dürfte mit mit heuristischen oder gar genetischen Algorithmen völlig überfordert sein. (Zumal auch genetische Algorithmen nicht greifen, wenn der Schlüssel absolut zufällig generiert wurde und keinem Psychologischen Muster entspricht)
Irgendwann hatte ich hier für jemanden einen Zufallsschlüssel-Generator (32 Byte X 35 mögliche Zeichen - 2 aufeinander folgende Zeichen sind nie identisch) in Batch (war so gewünscht) geschrieben. Es wäre nur per Bruteforce möglich gewesen die Buchstaben-Zahlenkombination zu replizieren.
Na, aber dass es die Funktion checkKey gibt deutet ja schon stark darauf hin, dass man sie wohl auch verwenden soll. Zur Erinnerung, die Funktion gibt die Anzahl der korrekten Bits zurück.
Zumal auch genetische Algorithmen nicht greifen, wenn der Schlüssel absolut zufällig generiert wurde und keinem Psychologischen Muster entspricht
Ich hab grad einen genetischen Algorithmus implementiert um das Problem zu lösen. Das Schloss wird völlig zufällig generiert. Die Startschlüssel werden völlig zufällig generiert.
und keinem Psychologischen Muster entspricht
Bitte? Was ist ein "psychologisches Muster"?
Meine Fitnessfunction ist einfach die Anzahl der korrekten Bits zu zählen. Ziel des Algorithmus ist das Ergebnis der Fitnessfunction zu maximieren, also die Anzahl der korrekten Bits zu steigern.
Eine wesentlich bessere Laufzeit erreicht man schon, wenn man jedes Bit einzeln verändert und danach den Schlüssel testet. Geht das Ergebnis von checkKey um 1 hoch, dann war die Bit-Änderung korrekt, ansonsten eben nicht.
In dem Fall muss man dann checkKey maximal so oft aufrufen, wie der Schlüssel lang ist. x mal checkKey aufrufen ist immer noch wesentlich besser als 2^x mal. Selbst das lässt sich natürlich noch wesentlich optimieren.
Gefühlt müsste der worst case bei O(log(n)) liegen, wobei n die Schlüssellänge ist.
Schade dass die Aufgabe nicht näher darauf eingeht.
Gruß
Eine vielleicht nicht optimale aber einfache Lösung:
Teste 00000001 und 00000000
Wenn beim ersten Versuch mehr richtige Stellen vorhanden sind, ist das erste Bit eine "1".
Das wird nun mit jeder Bit-Stelle wiederholt.
das heißt ich gebe zum Beispiel 3 ein wandle sie in binär umwandeln und dan das Komplement bilden oder was
Warum Komplement bilden? Du hast dann den Schlüssel sofern er passt.
Die Aufgabe zielt eher darauf ab eine intelligente Lösung zu finden. Dumm wäre einfach alle möglichen Kombinationen zu prüfen.
Bei 9 Bit hast Du schon 2^9 Möglichkeiten. Das ist für einen Computer easy, aber was wenn das 2^100 werden, also der Schlüssel länger? Ab einer gewissen Schlüssellänge ist brute force (einfach durchprobieren) nicht mehr schlau.
Was wäre also schlauer?
Angenommen Du probierst den den Schlüssel: 000000000 und die Funktion gibt x zurück, dann weißt Du schon mal, dass x 0en enthalten sein müssen. Das macht die Aufgabe schon mal leichter. Nun gilt es einen Algorithmus zu finden, der durch möglichst wenig Versuche den richtigen Schlüssel findet.
[Anmerkung: 000000000 ist vielleicht kein guter Startpunkt. Es sollte nur verdeutlichen, dass man damit eine Information herausfindet, die über reines durchprobieren hinaus geht.]
Der Trick ist auszunutzen, dass Du weißt wie viele Stellen des probierten Schlüssels korrekt waren. Du weißt nicht welche Stellen, aber Du weißt wie viele.
Der Algorithmus erinnert dann etwas an das Spiel https://en.wikipedia.org/wiki/Mastermind_(board_game). Dort muss man allerdings einen Schlüssel mit mehreren Variablen finden.
Viel Spaß. Ich glaub ich implementiere einen genetischen Algorithmus. Die Aufgabe ist echt gut. Danke dafür.
Gruß
Hier mal ein Prototyp für signed int.
#include <stdio.h>
#include <stdlib.h>
int geheimerSchluessel = 5;
int main(void)
{
printf("Der geheime Schluessel lautet: ");
for(int i = 31; i >= 0; i--)
{
if((1 << i) & geheimerSchluessel)
{
printf("1");
}
else
{
printf("0");
}
}
return 0;
}
Also um einfach mal zu verstehen wie das generell funktioniert. Die Lösung für das Problem musst du dir selbst erarbeiten, es soll nur ein Denkanstoß sein.
Das Komplementär bilden musst du gar nicht, weil das wird ja bloss zu einer anderen Zahl... einfach alle Zahlen in binär umwandeln und ausprobieren... (dann noch irgendwie clever mit den erhaltenen tipps umgehen hehe)
dann noch irgendwie clever mit den erhaltenen tipps umgehen
Schön beschrieben. Und ich breche mir da einen ab das zu erklären.
Manchmal kann es so einfach sein.
Gruß
Ok und jetzt bitte mit einem 512 Bit Schlüssel.