Zahl verfremden

[Aektom]

Hallo zusammen,

ich suche einen einfachen Algorithmus um aus einer, in meinem Fall max. 6-stelligen Zahl eine verfremdete neue max. 6-Stellige Zahl zu generieren.
Dies benötige ich für alle zahlen von 0 - 999999. Der Algorithmus also jeder Zahl x aus [0 - 999999] eine EINDEUTIGE neue Zahl y ebenfalls aus [0 - 999999] zuordnen.
Dabei soll gelten dass x <> y ist.
Also aus z.B.

x y
123456 => 947325
000001 => 000815
004711 => 482928
usw.

Es soll also praktisch eine Umordnung passieren.
Hat jemand eine Idee, wie man so was machen könnte ?

Gruß
Oliver

 

[asdfman]

S-Box

 

[schmidmi]

Ich nehme mal an du möchtest zufällige Zahlen. Also nicht so das y immer 345 größer ist als x sondern einfach das jedem x ein zufälliges y zugeordnet wird.
Dann würde ich x als ID von 0 bis 999999 in einem array oder DB speichern und dann Zufallszahlen generieren. Du kannst ja überprüfen ob es die Zahl schon gibt.

 

[7H3 N4C3R]

Wenn es für genau eine Mio. Zahlen ist, ist es eventuell verkraftbar eine dumme Lookup-Tabelle zu bauen.
Man nehme ein Array, in dem die Zahlen von 0-999.999 gespeichert sind, vertausche lange genug zufällig jeweils 2 Einträge miteinander (über den Daumen gepeilt mindestens 2 Mio. Vertauschungen) und speichere es als Referenz. Dann benutzt man die eigentliche Zahl als Index auf das Array.

Bei 1. Mio. Zahlen und 4 Byte pro Zahl macht das, wenn man es denn im Arbeitsspeicher halten will, einen Speicherverbauch von knapp 4 MB. Das muss man für sich selbst entscheiden, ob das verkraftbar ist oder nicht.

Einen Algorithmus, der die dazugehörige Zahl eindeutig berechnen kann, stelle ich mir dagegen schon eine ganze Ecke schwieriger vor. Da kommt es dann auch ganz stark darauf an, welche Qualitätsanforderungen man an die zugeordneten Zahlen stellt. (x+1)%100000 (Modulo) würde diese Anforderungen auch erfüllen, wäre aber vermutlich unbrauchbar.

 

[asdfman]

Wenn du eine Formel haben willst, wär das hier eine Möglichkeit:

- Deine Eingabe ist I
- Wähle 2 Primzahlen, P und Q und bilde M = PQ
- M sollte knapp über 1000000 liegen
- Berechne J = I^M%M

Damit bekommst du eine Zahl im Bereich zwischen 0 und M-1 heraus, die für jedes I eindeutig ist.
Wenn du die Operation umkehren willst, wird es aber etwas komplizierter.

€:
Für P = 971 und Q = 1031 bekommst du einen Bereich zwischen 0 und 1001100. Vielleicht genügt
das deinen Anforderungen.

€2:
P = 101 und Q = 9901 ergibt genau einen Bereich zwischen 0 und 1000000. Viel Spaß.

 

[Aektom]

Danke!

Ich werde das gleich ausprobieren!

 

[7H3 N4C3R]

Kleine Einführung in RSA?

Für I^M wirst du aber eine Bibliothek brauchen, die mit sehr großen Zahlen umgehen kann. Da hängt es so etwas von deiner Plattform ab und verwendeten Programmiersprache.

Für C++ gibt's z.B. die GMP-Lib

€:
Auf der GMP-Seite kann man's ausprobieren:

The result of executing 1000001^999999 is:

computation took 836 ms
result is about 5999994 digits, not printing it

Für den "größten" Fall. Und 836 ms, naja je nach dem wie oft du das aufrufst, musst du die Ergebnisse aus Performancegründen vielleicht tabellieren.

 

[asdfman]

Nicht ganz RSA.
Bei RSA selbst muss man ja nicht I^M%M berechnen sondern E und D ermitteln, die relativ Prim zu (P-1)(Q-1) sind und dann I^E%M bzw zum Umkehren analog mit D rechnen.
Deshalb ist die inverse Operation hier auch anders, aber die wollte er anscheinend ja gar nicht wissen.

€: Für näheres siehe hier: http://web.archive.org/web/20030610193721/http://jya.com/ellisdoc.htm

 

[Aektom]

Die inverse Operation brauche ich tatsächlich nicht.
Aber 999.999^1.000.000 sprengt dann noch die Mittel die mir zur Verfügung stehen -> COBOL. Dort kann ich max. 18-stellige Zahlen verwenden.

 

[asdfman]

Es gibt einen optimierten Algorithmus zur modularen exponentiation, bei der man nur wiederholt modular quadrieren muss. bei a^b%c bleiben die Zwischenergebnisse immer unter c.
Ich google mal.

€: http://de.wikipedia.org/wiki/Diskrete_Exponentialfunktion

 

[Aektom]

Sehr schön!!
Vielen Dank für die schnelle Hilfe.

€: Der RSA erzeugt ja auch eine eindeutige Zuordnung zwischen originaler und verfremdeter Zahl.
Dann könnte ich ja gleich auch diesen Algorithmus verwenden und habe was offizielles :-)

Also p = 101, q=9901 => N=p*q=1000001, wähle Verschlüsselungsexponent e = 23 (teilerfremd
zu (p-1)*(q-1) ) und berechne damit J = I^23 mod 1000001.

 

[asdfman]

Geht natürlich auch. Ich hab halt die andere Methode vorgeschlagen, weil die einfacher durchzuführen ist.
Man muss halt nicht noch extra eine Zahl finden, die Teilerfremd ist.

 

[Aektom]

Hallo,

habe den Algorithmus gerade mal ausprobiert.
Leider liefert er nicht das gewünschte Ergebnis.


Also ich habe die Werte folgendermaßen gewählt:
p = 101, q=9901 => N=p*q=1000001,
Verschlüsselungsexponent e = 1721 (teilerfremd zu (p-1)*(q-1) )

Damit ergibt sich: J = I^1721 mod 1000001

Wenn ich jetzt aber z.B. I = 1000 wähle, kommt für J ebenfalls 1000 raus.
Habe ich irgendeinen Denkfehler ?

 

[asdfman]

Sieht aus als wird 1000 damit auf sich selbst abgebildet. Das gilt aber für die allermeisten Zahlen nicht.

asdf@localh0rst ~ $ calc "1000^1721%1000001"
	1000
asdf@localh0rst ~ $ calc "12345^1721%1000001"
	425476
asdf@localh0rst ~ $ calc "54321^1721%1000001"
	335404
asdf@localh0rst ~ $ calc "2^1721%1000001"
	290565
asdf@localh0rst ~ $ calc "999999^1721%1000001"
	709436

Einen anderen Exponenten zu wählen, ändert das.

asdf@localh0rst ~ $ calc 1000^23%1000001
	999001
asdf@localh0rst ~ $ calc 12345^23%1000001
	548956
asdf@localh0rst ~ $ calc 54321^23%1000001
	536144
asdf@localh0rst ~ $ calc 2^23%1000001
	388600
asdf@localh0rst ~ $ calc 999999^23%1000001
	611401

 

[Aektom]

Das hab' ich auch schon probiert.
Aber dann bekommst du das gleiche Problem, nur bei anderen Zahlen, z.B. bei der 51712.

Selbst wenn ich N = p * q = 1009 * 9901 = 9990109 wähle, und damit die Zielmenge auf 7 Stellen erweitere, bekomme ich trotzdem noch Abbildungen auf sich selbst heraus, wie z.B. 19802.

Schade!!

Naja, vielleicht addiere/subtrahiere ich auf jede Zahl noch mal einen bestimmten Wert drauf,
damit es keine solche Fälle mehr gibt.

 

[[o.0]]

Also theoretisch würde es ja reichen wenn du die Zahl einfach umdrehst 0o

1234567 => 7654321
3456789 => 9876543

Jede Zahl auf der linken Seite hätte nen eindeutiges Gegenstück auf der Rechten, umkegehrt jede Zahl rechts was Eindeutiges auf der Linken.

Aber ok, das ist wahrscheinlich zu einfach... ist mir nur grade so dazu eingefallen, nich hauen plz^^

Edit: Ok, wie Savaron sagt funktioniert das doch nich 0o

 

[Savaron]

1111111?... kein besonders guter vorschlag

 

[Thunderstruck]

hi,

klingt nach ein bijektiven Abbildung die dann surjektiv und injektiv?...bitte nachlesen

Ansatz:
eineindeutige Zuordung: bijektive Abbildung p: N ---> N N:= Summe aller Natürliche Zahlen hier echte Teilmenge

y = f (x) Also eine Funktion muß Du wohl zusammen bastel, den momenta fällt mir nichts entsprechendes ein außer, daß vielleicht in der Zahlentheorie ein verwendbarer Algorithmus existiert.
Denn "zu Fuß " ist das Vorahaben crazy lol.

cya m8

TS

 

[tetris²]

kannst ja verschiedene ideen der Verschlüsselung benutzen:
1) die Zahl umdrehen oder halt vertauschen
2) die Zahlen verändern: z.b.die erste zahl mit eins addieren, die zweite mit zwei usw. [das ist nur ein einfaches beispiel kannst es ja auch verändern oder mit subtrahieren etc.

z.b.:
Zahl: 0122374
1) umgedreht: 4732210
2) bei der 1. +1 usw: 5966777

anderes beispiel:

Zahl: 9039725
1) 5279309
2) 6403866

EDIT: ich hoffe ich habe mich mitm kopfrechnen nicht vertan..

 

[Aektom]

@Tetris²: Auch ne gute Idee.

Die Vorgaben haben sich allerdings in der Zwischenzeit ein wenig geändert. Die Zielmenge ist jetzt doch nicht [0,999999] sondern darf max. 8-stellig sein.
Somit funktioniert der RSA wieder, wenn man das N groß genug wählt.

Danke an alle, für die guten Tipps!
Werde den einen oder anderen sicherlich noch mal brauchen...

Gruß
Olli