Zahl "komprimieren"

[hirnstroem]

'loha Folks,

ich habe mir gerade Gedanken darüber gemacht, wie sich wohl eine Zahl am besten "komprimieren" lässt - sprich, wie sich Zeichen einsparen lassen, kam aber nicht allzu weit.

Es geht um folgendes:

Auf einem Schlüssel befindet sich ein 64-bit langer Code. Dieser Code soll für niemanden zugänglich sein. Um sämtliche möglichen Schlüssel Codes eindeutig bestimmen zu können, werden nun also auch wieder 64-bit benötigt, wie das halt bei den Zahlen so ist. Von dieser eindeutigen Identifikation soll nicht direkt auf den ursprünglichen Code geschlossen werden können. Zudem muss die eindeutige Identifikation mit weniger Zeichen auskommen (warum lass ich jetzt einmal offen).

Die einfachste Möglichkeit ist wohl, die grösstmögliche Basis im Stellenwertsystem zu verwenden. Da Sonderzeichen und Kleinbuchstaben unerwünscht sind, käme Basis 36 (0..9, A..Z - wobei Zahlen und Buchstaben zufällig durchmischt werden) in Frage. Leider lassen sich damit nur zwei Zeichen einsparen.

Nun wollte ich mich erkundigen, ob man da noch etwas rausholen kann (weniger Zeichen um jeden Preis)?!

Grüsse
hirnstroem

[mkinzler]

Schau mal nach Hash.

[Der_Unwissende]

Zitat von hirnstroem:

Auf einem Schlüssel befindet sich ein 64-bit langer Code. Dieser Code soll für niemanden zugänglich sein.
... Zudem muss die eindeutige Identifikation mit weniger Zeichen auskommen (warum lass ich jetzt einmal offen).

Hi,
hier steckt ein gewisses Problempotential drin, wenn ich Dich richtig verstehe. Erstmal vorab, einen Code von 64 Bit kannst Du nicht kleiner als 64 Bit machen, da sonst Informationen verloren gehen. Bei einem Hash wird genau das in Kauf genommen: Hashfunktionen stellen i.d.R. auch keine bijektive Abbildung dar. Dass sie trotzdem in Sicherheitsrelevanten Anwendungen zum Einsatz kommen liegt nur daran, dass es sehr unwahrscheinlich ist, dass man zwei Eingaben findet, die auf den gleichen Hash abgebildet werden. Was auch immer Du für eine Funktion verwendest, die 64-Bit möglichst gleichverteilt auf eine kleinere Menge abbildet, je kleiner die Zielmenge ist, desto schneller findet man etwas mit gleichem Wert. Eindeutig kannst Du zwei alle 64-Bit Schlüssel wirklich nur mit 64-Bit größe Unterscheiden!

Gruß Der Unwissende

[Robert Marquardt]

Nach meiner Rechnung nur mit Dezimalziffern = 64 / 3 = 22, mit Hexziffern = 64 / 4 = 16 und mit Ziffern und Buchstaben = 64 / 5 = 13.
Hash ist schon die richtige Idee. In diesem Fall will man aber von Hashnummer eindeutig auf Codenummer kommen und das bedeutet das Hash und Code gleiche Laenge haben muessen. Der Hash degeneriert also zu einer Verwuerfelung. Entweder Tabelle oder Formel.

[kolbaschedder]

Kodierung könnte wie folgt aussehen :

Delphi-Quellcode:

input : string[8];
output :array[0..7] of byte;
for i :=0 to 7 do
begin
  case ord(string[i+1]) of
    48..57 : output[i] := ord(string[i+1])-48;    // Zahlen minus Offset
    65..90 : output[i] := ord(string[i+1])-65+10; // Großbuchstaben minus offset +bereich der Zahlen
  else
    FEHLER !!!
  end;
end;

ergibt Werte zwischen 0 und 35. Dekodierung eben genau andersrum.

Packen in DWord oder ähnliches

Delphi-Quellcode:

input string[8];
input: array[0..7] of byte;
res : DWord;

res := 0;
for i :=0 to 7 do
begin
  res := res+36*i*input[i];
end;

auspacken aus DWord

Delphi-Quellcode:

input string[8];
input : DWord;
output: array[0..7] of byte;

for i :=7 downto 0 do
begin
  output[i]:= input div (36*i);
  input := input -(input div (36*i));
end;

Alles ungetestet, aber ich hoffe die Idee dahinter ist klar.

[hirnstroem]

Also mit einem Hash werde ich definitiv nicht auskommen, da dieser zu viel Spielraum lässt.

Vielleicht noch ein Paar Zusatzinformationen:

Diese "komprimierte" Zahl wird dazu benötigt, Schlüssel optisch zu Erfassen und diese nachher in einer Datenbank zu speichern. Die optische Erfassung geschieht indem ein an einem CAN-Bus angeschlossenes Gerät dazu auserkoren wird, die nächsten 100 Schlüsselähnlichen Objekte zu fotografieren, aus dem den Schlüssel repräsentierenden Teil des Fotos einen Code zu berechnen und siesen an einen Server zu schicken. Auf dem Server wird dann ausgewertet wievielmal welcher Schlüssel erkannt wurde. Dies wiederum ist notwendig, weil es schier unmöglich ist, einen genügend schnellen Algorithmus zu schreiben, welcher immer den richtigen Code erkennt. Wie auch immer...es wird ausgewertet. Kommt nun ein Schlüssel viele male mehr vor als ein anderer, kann man davon ausgehen, dass der Richtige erkannt wurde, jedoch bleibt eine "Restunsicherheit" (z.B. wenn ein Teil des Schlüssels vom Finger des Benutzers abgedeckt wurde etc.). Diese "Restunsicherheit" lässt sich umgehen, indem man erstens, eine eindeutige Identifikation vergibt und diese auf den Schlüssel schreibt, zweitens, den Benutzer beim einlesen auffordert diese eindeutige Itentifikation einzugeben und, drittens, den erkannten Schlüsselcode vom Server in diese eindeutige Identifikationsnummer umwandeln lässt. So kann kein Falscher Schlüssel mehr erfasst werden.

Nun, dass diese 64-bit 64-bit bleiben leuchtet mir ein. An der Darstellung habe ich ja durch das Miteinbeziehen einer anderen Basis etwas nachgeholfen...mit mässigem Erfolg.

Aber so wie es scheint, lässt sich auch nicht mehr machen.