mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Mathematikfrage: Algorithmus erstellen


Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo liebe Leute!

Da ich zur Zeit an einem Problem hänge, denke ich, in diesem Forum 
richtig aufgehoben zu sein.

Und zwar geht es um folgendes:

Eine Blackbox(x) schickt 2 Bytes an eine andere Blackbox(y).

 09 78


Nun hat Blackbox(y) einen bestimmten Algorithmus verpflanzt, der die 2 
Bytes von Blackbox(x) verwurschtelt.
Blackbox(y) schickt nach dem "verwurschteln" 2 Bytes an Blackbox(x) 
zurück:

 93 77.

Wie komme ich an diesen Algorithmus in Blackbox(y) ??

Ich habe insgesamt 10 Muster mit jeweils Anfrage und Antwort.
Helfen die mir weiter beim Finden des Algorithmuses?


ich weiß leider nicht mal einen Ansatz. Würde jetzt wüst hin- und 
hershiften, logisch verknüpfen, usw.

Wie würdet ihr sowas machen?



Danke!

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
entweder sieht man das muster oder man hat kaum eine chance. Weist du 
überhaupt das die Boxen sich Determinisich verhalten? Kommt also immer 
wenn du 09 78 reingibst 93 77 raus.

Es kann also auch gut sein das dort einfach ein Tabelle hinterlegt ist, 
dann gibt es keinen Algorithmus.

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Erfahrungsgemäß sind es Algorithmen, die sich dahinter verbergen. Aber 
ausschließen kann man es natürlich nicht.

> Kommt also immerwenn du 09 78 reingibst 93 77 raus?

ja tut es. Es kommt bei gleicher Anfrage immer die gleiche Antwort.


Danke!

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du die Frage vom Peter mit ja beantworten kannst, dann poste bitte 
deine 10 Muster, ansonsten sehe ich schwarz.

Autor: byte (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gibt kryptografische Tools die dir evtl. weiterhelfen können. 
Allgemein würd ich die ganzen werte mal in allen Varianten darstellen. 
Byte, Hex, Bin... also die einzelnen Bits. Anhand der Bitdarstellung 
kann man evtl. schnell ein Muster herausfinden. (xor, schieben, etc) 
Aber wie der Vorgänger schon geschrieben hat... hast ne Tabelle oder 
eine erweitere (evlt. abhängige) Logik drin hast verloren.

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
stell doch einfach mal die Werte hier rein, eventuell erkennt jemand ein 
Muster.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> des Algorithmuses
OT und zur Allgemeinbildung:
Der Genitiv von dem Algorithmus ist der selbe wie der des Algorithmus... 
;-)


> Eine Blackbox(x) schickt 2 Bytes an eine andere Blackbox(y).
> 09 78
Sind das ASCII-Zeichen oder Hex-Werte?

> Ich habe insgesamt 10 Muster mit jeweils Anfrage und Antwort.
Poste die doch mal, evtl. hat einer einen Lichtblick...
Du kennst die Geschichte mit dem blinden Huhn?

Autor: Mara (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du hast 2 Byte eingabe, und 2 Byte Ausgabe,
Du hast 10 Muster.

Du hast keinerlei Information über die Aufgabe/Funktion der Blackbox.

Es ist nicht möglich einen exakten Algorithmus anzugeben, weil es nicht 
möglich ist mit nur 10 Mustern das Problem ausreichend zu 
generalisieren.

Das einzige was du weißst sind deine 10 Muster, die kannst du als 
Tabelle hinterlegen, für alle anderen Eingabekombinationen kann man 
keine Aussaage machen die auch nur näherungsweise akzeptabel ist!

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Sind das ASCII-Zeichen oder Hex-Werte?

Das sind Hexwerte: Zur Berichtigung:    0x09   0x78


Im folgenden poste ich mal das "Muster":

Anfrage:                          Antwort:
========                          ========

00000000 00000001  10011111 00101001
00000000 00000010  10001110 00010000
00000000 00000011  00011000 10010010
00000000 00000100  10001111 00110010
00000000 00000101  11010010 11001000
00000000 00000110  11000011 11110001
00000000 00000111  01010101 01110011
00000000 00001000  10011111 00100000
00000000 00001001  10110101 11011010
00000000 00001010  10100100 11100011
00000000 00001011  00110010 01100001



Danke :)

Autor: dito (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du müsstest schon weitere Zahlenpaare (also Ein- und Ausgänge) angeben. 
Sonst kann man kein vernünftiges Muster erkennen.

Mit den Zahlen, die du gegeben hast, könnte ich z.B. sagen: Blackbox y 
addiert auf das erste Byte immer 84 und dekrementiert das zweite Byte.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da die Veränderungen in der Antwort selbst bei Einzelbitänderungen in 
der Eingabe schon recht heftig sind, denke ich nicht dass es irgendetwas 
einfaches ala 'XOR über alle Bytes' oder 'Summe' oder sowas in der 
Richtung ist.

Viel Hoffnung sehe ich da nicht, das Verfahren zu erraten. Selbst wenn 
man wüsste, dass es sich um eine CRC oder Abart davon handelt, sind die 
Karten schlecht.

Autor: Ninola (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm, das sind aber 11 Muster. Sagtest du nicht, du hättest nur 10?

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Hmm, das sind aber 11 Muster. Sagtest du nicht, du hättest nur 10?

Dann sinds eben 11. Das ist glaube ich nicht das größte Problem ;-)

Autor: ich (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Welches von denen soll eigentlich das 0x09   0x78
darstellen? Bei mir ist das erste Byte der Anfrage immer 0x00

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das erste Beispiel von mir war KEIN anzunehmender Wert, er war 
ausschließlich zur Veranschaulichung gedacht. Hat also NICHTS mit dem 
Algorithmus selbst zutun.

Autor: sonstwer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du die Eingangswerte schnell reinschieben, und die Ausgangswerte 
schnel mitschreiben kannst, dann kannst du doch alle 2^16 Möglichkeiten 
durchgehen.

Vielleicht reicht dir dann schon eine Tabelle zum nachbauen.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was khabe ich mir unter den Blackboxen vorzustellen? Smartcards?

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> 00000000 00000001  10011111 00101001
> 00000000 00000010  10001110 00010000
> 00000000 00000011  00011000 10010010
> 00000000 00000100  10001111 00110010
> 00000000 00000101  11010010 11001000
> 00000000 00000110  11000011 11110001
> 00000000 00000111  01010101 01110011
> 00000000 00001000  10011111 00100000
> 00000000 00001001  10110101 11011010
> 00000000 00001010  10100100 11100011
> 00000000 00001011  00110010 01100001

dito schrieb:
> Mit den Zahlen, die du gegeben hast, könnte ich z.B. sagen: Blackbox y
> addiert auf das erste Byte immer 84 und dekrementiert das zweite Byte.

Wie bitte? Erklär mir das mal.

@Markus:
Du stellst Dir das etwas einfach vor. Nimm einen 
Verschlüsselungsalgorithmus. Der hat die Aufgabe Daten so zu 
verschlüsseln, daß man selbst dann, wenn man den Algorithmus kennt und 
Millionen von Ein-Ausgabepaaren hat, den Schlüssel nicht zurückberechnen 
können soll.
Insofern würde sich eine Lösung für Dein Problem nur dann finden, wenn 
ein sehr simpler Algorithmus in Deinem System steckt.
Und wenn Du nur 10 Wertepaare hast, aber 256 * 256 Mögliche Eingabedaten 
kannst Du nie wissen ob Deine Lösung korrekt ist, dazu müsstest Du schon 
alle 65Tausend und verquetschte mögliche Paare kennen und mit Deiner 
Lösung verifizieren.

Autor: dito (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
U.R. Schmitt schrieb:
> dito schrieb:
>> Mit den Zahlen, die du gegeben hast, könnte ich z.B. sagen: Blackbox y
>> addiert auf das erste Byte immer 84 und dekrementiert das zweite Byte.
>
> Wie bitte? Erklär mir das mal.

Ganz einfach: Vergleich mal die Zeiten. Als ich meinen Beitrag verfasst 
habe, kannte ich die Muster noch nicht.

Autor: byte (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wieso hab ich eigentlich das gefühl das du was ilegales machst? ;)

Das hier ist interessant....

00000000 00000001  10011111 00101001
00000000 00000010  10001110 00010000
00000000 00000100  10001111 00110010
00000000 00001000  10011111 00100000

Irgendwie kann ich das Muster schon fühlen.... %-)

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein ich mache definitiv nichts illegales, ich möchte einfach nur 
wissen, wie man Schritt-für-Schritt einen Algorithmus baut, wenn man 
EINGANG und AUSGANG weiß.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> Nein ich mache definitiv nichts illegales, ich möchte einfach nur
> wissen, wie man Schritt-für-Schritt einen Algorithmus baut, wenn man
> EINGANG und AUSGANG weiß.

Wenn du nichts anderes darüber weißt

Alle Eingangswerte allen Ausgansgwerten gegenüber stellen und eine 
Lookup Tabelle.

Alles andere mag in bestimmten Einzelfällen gehen, es gibt aber kein 
Schema dafür und das kann es auch nicht geben.

Autor: Tomy (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wie würde die antwort auf
00000000 00000000
aussehen?

Autor: Stefan Hennig (stefanhennig)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> Nein ich mache definitiv nichts illegales, ich möchte einfach nur
>
> wissen, wie man Schritt-für-Schritt einen Algorithmus baut, wenn man
>
> EINGANG und AUSGANG weiß.

Ja, aber Du weißt das ja nicht. Du nennst uns 10 (OK, 11) von 2^16 
Werten. Das ist nicht 'wissen'.

Und selbst wenn Du alle Daten kennst, ist die pragmatischste Lösung 
tatsächlich eine Lookup-Tabelle.

Ansonsten gilt es genau die Fragen zu beantworten, die bereits gestellt 
wurden:
- Kommt auf die selbe Frage immer dieselbe Antwort (d.h. gibt es innere 
Zustände)`?
- Sind die Antworten linear? D.h. wenn a die Antwort A liefert und b die 
Antwort B, liefert dann a+b die Antwort A+B?
- Sind alle Antworten verschieden? (Alternativ: Gibt es mindestens zwei 
Fragen, die dieselbe Antwort liefern?)

Beantworte mal diese Fragen (für Dich, nicht für uns), dann wirst Du 
sicherlich ein paar Schritte weiter sein.

Grüße,
  Stefan

Autor: Zwölf Mal Acht (hacky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine erste Frage waere  : Hat die Blackbox einen Speicher, ein 
Gedaechtnis ? Hat es offensichtlich nicht.
Dann wuerde ich alle moeglichen Werte reinschieben und die Ausgaben 
darauf aufzeichnen, dann nach einem Muster suchen. Sind ja nur 65k 
wortpaare. das geht schneller als hier zu fragen.

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A...aha Soooo. schrieb:
> ine erste Frage waere  : Hat die Blackbox einen Speicher, ein
> Gedaechtnis ? Hat es offensichtlich nicht.
> Dann wuerde ich alle moeglichen Werte reinschieben und die Ausgaben
> darauf aufzeichnen, dann nach einem Muster suchen. Sind ja nur 65k
> wortpaare. das geht schneller als hier zu fragen.

Wobei zu klären wäre, ob das System wirklich nur 2Byte-Weise 
verarbeitet.
Wenn Du einen guten alten DES mit einem festen Schlüssel nimmst, kommt 
bei Eingabe von 2 mal 2 Bytes immer das Gleiche raus (weil er intern die 
2 Byte immer auf 56 Bit auffüllt) aber wenn man statt dessen 4 Bytes auf 
einmal reingibt, kommt was völig anderes raus.

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> 09 78
>
>  93 77

Waren das jetzt nur Beispiele oder ist das das 12. Sample?

Autor: Lehrmann Michael (ubimbo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
2 Möglichkeiten:

- Weitere Muster raussuchen/abfragen

oder schreib dir ein C-Programm das dir alle möglichen Algorithmen (bis 
zu einem gewissen Grad) durchmacht. Wenn ein Match da ist dann die 
anderen überprüfen. Musst halt viel Zeit haben und einen flotten 
Computer.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da muss man nichts irgendwie probieren. Das machen Hardwaredesigntools 
z.B. für FPGAs tagtäglich...
Wenn es nur diese Zuordnung gibt, dann muß hier gar nichts geraten 
werden: mit einer Wahrheitstabelle und einem Minterm-Verfahren kann ich 
eine logische Verknüpfung basteln, die für diese Eingangswerte genau die 
passenden Ausgangswerte bringt (zur Not von Hand mit einem KV-Diagramm).
Blöd ist nur, dass damit alle (unbekannten) Zustände beliebig sind... 
:-/

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
das KV diagram will ich sehen.

Autor: Herr Umbrarum (mxvalentine)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmmm ich weiß ja nicht ob das jetzt völlig fehl am Platz ist aber die 
Anfrage ist doch einach nur binär durchnumeriert O.o sieht man es so 
kommen hinten einfach nur weitere Zahlenwerte raus ^^

00000000 00000001  10011111 00101001
0/1 -> 159/41
00000000 00000010  10001110 00010000
0/2 -> 142/16
00000000 00000011  00011000 10010010
0/3 -> 24/146

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Geruch wird stärker:

00000000 00000001    10011111 00101001
00000000 00000010    10001110 00010000
00000000 000000 11  0 0011000 10010010
00000000 00000100    10001111 00110010
00000000 00000101    11010010 11001000
00000000 00000110    11000011 11110001
00000000 000001 11  0 1010101 01110011
00000000 00001000    10011111 00100000
00000000 00001001    10110101 11011010
00000000 00001010    10100100 11100011
00000000 000010 11  0 0110010 01100001

Autor: Hallbergmoser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist ein denumerator!

Autor: Markus Richel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Erst mal vielen Dank dass ihr alle so zahlreich am Knobeln seid.

:)


Wisst ihr irgendein Programm, was das mit BruteForce o.ä. errät?

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Spielchen hab ich auch mal gespielt, dabei ging es um einen alten 
FastEYE LPt Dongle, der hat schlussendlich aber verloren.
Falls du ein ähnliches Spiel spielst, musst du viel mehr Werte 
mitloggen, denn wenn das Teil schlauer ist als der von mir und solche 
Sachen verwendet:
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
dann musst brauchst du viele bis seeeehr viele Werte um das Ergebnis zu 
berechnen.

Autor: Abdul K. (ehydra) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich weiß zwar nicht was Martin riecht... verrate es doch!


Aber beim beliebten LFSR reichen unter Umständen nur wenige Zustände in 
eines Strings aus, die ganze Kette zu generieren. Das gilt insbesondere 
für die der Klasse maximum-length.
Eine weitere interessante Eigenschaft ergibt sich bei differentieller 
Codierung, in dem die Kette sich dann ohne und mit dem Differentialcoder 
nur um eine Verschiebung um die (Registerbreite-1) unterscheidet!

Nein, das ist jetzt nicht die direkte Lösung!

Autor: X- Rocka (x-rocka)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hey, meine Alarmanlage kommuniziert genau so zwischen Master und Slaves!
;-)

Ist das jetzt ein tatsächliches Gerät, oder ein reines 
Gedankenexperiment?

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus Richel schrieb:
> Wisst ihr irgendein Programm, was das mit BruteForce o.ä. errät?

Hast Du gelesen und verstanden was weiter oben geschrieben wurde?
Wenn Du uns 10 Wertepaare gibst und selbst WENN das System kein internes 
Gedächtnis hat und WENN keine 2 Eingangswerte den gleichen Ausgangswert 
haben, dann gibt es immer noch (2^16 - 10)! ((Zwei hoch 16 - 10) 
Fakultät) mögliche Lösungen. Versuch das mal mit Deinem Taschenrechner 
auszurechnen und erkläre uns warum da "Err" oder "Ovf" herauskommt.
Wenn diese WENNS nicht gelten gibts noch mehr mögliche Lösungen.
Man kann allenfalls aus wenigen Werten vermuten, daß es ein einfaches 
System gibt, mit dem man die Ausgangswerte aus den Eingangswerten 
berechnen/bestimmen kann. Ob diese Vermutung tatsächlich korrekt ist 
weisst Du nur, wenn Du alle möglichen Eingangskombinationen geprüft 
hast.

Autor: Joe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Alle 2^16 Words auslesen, in ein Eprom brennen, Zugriff über uC regeln, 
fertig.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.