Java - charArray nach Buchstaben nummerieren (Index-Permutation)

[CrAc]

Moin!

Folgendes Problem: ein charArray (A-Z) soll nach dem Alphabet durchnummeriert werden. (Keine eindeutige Zuordnung von Werten zu Chars, wie A=1!)

Beispiel:

PETER
20413

Die Zahlen sind eine Permutation der Indizes der sortierten Chars.
Also zunächst erstmal den String zu einem charArray umwandeln, und mit Arrays.sort() sortieren. Da komme ich jetzt eben von hier aber nicht wieder zurück:

EEPRT
01234

((01234)->(20413))

Ich hatte schon verschiedene Ansätze ausprobiert, die alle Müll waren.

Da ich trauriger weise schon seit 4 Tagen daran tüftle, hoffe ich dass mich hier jemand in die richtige Richtung schubsen kann.

Viele Grüße

PS: zweidimensionale Arrays sind ausgeschlossen.

 

[Tsjuder]

Also wenn ich das jetzt richtig verstanden habe:
Du nimmst einen String der Länge x. Permutierst die Indizes von 0 bis x-1, weist den einzelnen Chars einen Wert davon zu und sortierst anschließend den String nach diesen permutierten Indizes.

In deinem Beispiel hast du also einen String der Länge 5, damit die Indizes 0-4, permutierst diese Zahlen zu "20413" und weißt dann dem ersten Char, die erstze Ziffer zu, dem zweiten Char die zweite Ziffer usw.

Die Lösung des Problems sollte doch dann sein das inverse deiner Permutationsoperation anzuwenden auf den nach der Permutation geordneten String.
Wenn deine Permutation komplett zufällig abläuft, sind wir bei Cryptoanalysen gelandet.

 

[CrAc]

Also wenn ich das jetzt richtig verstanden habe:
Du nimmst einen String der Länge x. Permutierst die Indizes von 0 bis x-1, weist den einzelnen Chars einen Wert davon zu und sortierst anschließend den String nach diesen permutierten Indizes.

Jain. Der String ist eine Merkhilfe für die Permutation. Die Permutation wird dadurch bestimmt, dass man jedem Buchstaben nach alphabetischer Reihenfolge eine Zahl zuordnet. (Ich hab mich vorhin unklar ausgedrückt, sorry! War früh ) Die Permutation ist also nicht beliebig.

Bsp.
String "Peter", Länge 5.

Wenn man das per Hand machen würde, geht man durch, weist dem ersten 'e' die 0 zu, dem zweiten die 1, dem 'p' die 2, dem 'r' die 3 und schließlich dem 't' die 4.
Man erhält also zu Peter die Zahlenzuordnung von "20413".

Umzusetzen ist das m.M.n. eben dadurch, dass man den String "sortiert", die Indizes inkrementierend bestimmt, und dann wieder zurück auf den unsortierten String überträgt. (Genau da hakt es halt, ich weiß den Rückweg nicht umzusetzen!) Quasi die Umkehrabbildung von (EEPRT,01234)->(PETER,20413) ...

Hintergrund: zu Implementieren ist das Doppelwürfel verfahren, oder auch "doppelte Spaltentransposition". Die Permutation der Indizes gibt die Vertauschung der Spalten vor.

Siehe:
http://cryptblog.de/doppelwuerfel/index.html
http://andreas-romeyke.de/Projekt1/ffbr/web.html (unter Transpositionsverfahren)

Originale Aufgabenstellung: https://docs.google.com/file/d/0B8b-7wTIgOZwTEJ2S2U3RFlraHc/edit?usp=sharing

 

[Tsjuder]

Umzusetzen ist das m.M.n. eben dadurch, dass man den String "sortiert", die Indizes inkrementierend bestimmt, und dann wieder zurück auf den unsortierten String überträgt. (Genau da hakt es halt, ich weiß den Rückweg nicht umzusetzen!) Quasi die Umkehrabbildung von (EEPRT,01234)->(PETER,20413) ...

Hintergrund: zu Implementieren ist das Doppelwürfel verfahren, oder auch "doppelte Spaltentransposition". Die Permutation der Indizes gibt die Vertauschung der Spalten vor.

Siehe:
http://cryptblog.de/doppelwuerfel/index.html

Moment mal: Vielleicht ist mein Gedankengang jetzt falsch, wollte jetzt aber heute auch nicht soviel Zeit darein investieren .

Das Wort "PETER" dient doch nur dazu Ziffern (bzw. bei großen Wörtern wohl auch Zahlen) für die Permutation zu erzeugen. Es ist doch im Prinzip dein Schlüssel für die Kryptofunktion. Ich glaube du versuchst bzw. willst eher etwas anderes versuchen, weil so wie es bis jetzt hier steht ergibt sich doch einfach folgendes Problem:

(PETER, 20413) wird anhand der Funktion zu (EEPRT, 01234). Es gibt aber im Prinzip keine Umkehrfunktion dieser Abbildung ohne (wie es z.B. xrayn) Zusatzinformationen abzuspeichern. Denn (EEPRT,01234) könnte genauso gut aus einem beliebigen String entstanden sein wie z.B. (ERTEP,03412). Ums mathematisch auszudrücken: Deine Funktion, die anhand eines Strings wie PETER die Permutation erzeugt, ist surjektiv, d.h. mehrere String führen zu (EEPRT, 01234) und damit ist die Umkehrfunktion nicht vorhanden.

Zusammengefasst: "PETER" ist dein Schlüssel und dieser soll ja eben nicht zurückberechnet werden können. Hast du einen Klartext und verschlüsselt diesen mithilfe des Schlüssels "PETER" und willst das Klartext Wort wiederzurückbekommen, dann erhälst du alle Informationen durch die Kenntnis der Funktion die benutzt wird und dem Schlüssel "PETER". Ansonsten wäre das komplette Kryptoverfahren totaler Unsinn.

 

[CrAc]

Danke für Eure Antworten!

xrayn: So wie du es implementiert hast, ist es verkehrt herum. Ich habe Peter, und will 20413. Ich denke halt, dass man das so machen kann, indem man Peter sortiert (EEPTR) und wie oben schon beschrieben nach einander jedem Buchstaben in alphabetischer Reihenfolge die nächst höhere Zahl zuordnet.

Also:

PETER -> EEPRT -> PETER
         01234 -> 20413

20413 ist das, was ich eben brauche. Wie Tsjuder sagte, das Wort ist nur ein Alias für die Permutation. Eben eine andere Darstellung, damit man sich das merken kann.

PS: Das Verfahren ist nicht das sicherste, unter dem einen Link im obigen Beitrag wird auch ein entsprechender Angriff beschrieben. Der Prof. ist halt nur der Meinung, es wäre 'ne nette Nebenaufgabe. Es geht eigentlich um GUIs ...

/e: Ich habs gelöst!

		int[] perm = new int[klartext.length()];
		char[] sortedChars = klartext.toCharArray();
		Arrays.sort(sortedChars);

		for (int i = 0; i < klartext.length(); i++) {

			for (int j = 0; j < sortedChars.length; j++) {
				if (klartext.charAt(i) == sortedChars[j]) {
					// pruefe nun die vorherigen vorkommen des chars
					int count = 0;

					// gehe vom anfang des klartextes bis zum aktuellen char und
					// zähle die vorkommnisse des chars bis hier
					for (int i1 = 0; i1 < i; i1++) {
						if (klartext.charAt(i1) == klartext.charAt(i)) {
							count++;
						}
					}
					perm[i] = j + count;
					
					break;
				}
			}
		}

Irgendwie nicht so einfach wie ich gedacht habe, aber es funktioniert. Ich danke Euch für euer Bemühen!