Hallo T_55,
ich hab mal ein bisschen gegrübelt und rumgespielt...
T_55 schrieb:
Jetzt überlege ich vergeblich wie man eine Funktion aufbaut die eine 8 Stellige Integer bekommt und eine daraus abgeleitete chaotische und kollisionssichere 8 stellige Integer ausgibt, was auch wieder rückgängig funktioniert.
Was Du brauchst ist eine Funktion, die Mathematiker
Bijektion nennen und zwar auf der Menge der Zahlen von 0 bis 99999999.
Nach ein bisschen Grübeln bin ich auf ein Verfahren (ich nenn es mal "ziffernweise Modulo-10-Addition") gekommen, das Deine Anforderungen erfüllt.
Beispiel:
Du hast die Zahl "51230567" und willst sie "verschlüsseln" (in Anführungszeichen deshalb, weil es keine "echte" Verschlüsselung ist, sondern nur eine "Verschleierung"), dazu verwenden wir einen "Schlüssel", der ebenfalls
8-stellig ist und dieser lautet für unser Beispiel "81748931".
Dazu addieren wir die beiden Zahlen im Modus "ziffernweise Modulo-10-Addition":
Code:
51230567
+81748931
---------
32978498
^
|
+----- Hunderter
Die "ziffernweise Modulo-10-Addition" funktioniert
fast wie eine normale Addition mit der Ausnahme daß es keinen Übertrag gibt, also um im obigen Beispiel zu bleiben betrachten wir die Hunderter-Stellen der beiden Zahlen "5" und "9", welche addiert "14" ergeben, was "Modulo-10" "4" als Ergebnis liefert (und es findet wie gesagt kein Übertrag statt, d.h. "0" plus "8" gibt "8" für die Tausender und
nicht "9" wie bei einer normalen Addition).
Die "Entschlüsselung" funktioniert natürlich per "Modulo-10-
Subtraktion", man kann sich aber relativ leicht herleiten, daß dies einer "ziffernweise Modulo-10-
Addition" mit einem "Gegenschlüssel" entspricht.
Der Gegenschlüssel wird berechnet, indem man von der Zahl "99999999" den Schlüssel abzieht und auf diese Zahl die Zahl "11111111" modulo-10 addiert.
Konkret für unseren Schlüssel "81748931":
Code:
99999999
-81748931
---------
18251068
+11111111
---------
29362179
Um also unser Ergebnis von oben "32978498" wieder zu entschlüsseln muss man nur die beiden Zahlen "32978498" und "29362179" modulo-10 addieren:
Code:
32978498
+29362179
---------
51230567
Jetzt sagt Du: "Ist ja schön und gut, ich will aber, daß sich zwei Zahlen, die sich
vor der Verschlüsselung "ähnlich" sehen
nach der Verschlüsselung eben
nicht mehr ähnlich sehen!"
Beispiel: Die beiden Zahlen "10000000" und "10000005" sehen sich
vor der Verschlüsselung ähnlich (7 von 8 Ziffern sind identisch) und auch
nach der Verschlüsselung sehe ich den beiden ihre Ähnlichkeit noch an.
Code:
10000000 ---Verschlüsselung---> 91748931
10000005 ---Verschlüsselung---> 91748936
Darauf sage ich: "Ja, Du hast absolut Recht, deshalb habe ich mir zwei "Tricks" ausgedacht, die mein Verfahren auf die nächste Evolutionsstufe heben."
Trick1: Wir verwenden nicht mehr
einen Schlüssel sondern 10 verschiedene (für jede Ziffer des Dezimalsystems einen anderen), die Auswahl welcher der 10 verwendet wird geschieht über eine Ziffer der zu verschlüsselnden Zahl (Indexierung).
Trick2: Die Ziffer anhand derer die Verschlüsselung vorgenommen wird bleibt unverschlüsselt (dies geschieht einfach dadurch, daß die Stelle dieser Ziffer mit "0" im Schlüssel belegt wird.
Wozu dieser Trick gut ist werden wir weiter unten noch sehen.
Das klingt wahrscheinlich erstmal völlig unverständlich, deshalb ein Beispiel:
Wir nehmen wieder unsere beiden Zahlen "1000000
0" und "1000000
5", als "Auswahlziffer" wählen wir die "Einerziffer" (welche "
0" und "
5" bei unseren beiden Zahlen sind).
Als Schlüssel-Array (Du merkst es geht langsam in Richtung Programmierung) mit 10 Schlüsseln wird
Code:
// 0 1 2 3 4 5 6 7 8 9
81748930, 22413790, 90451280, 88725490, 13529660, 72895010, 38495220, 52199380, 26501870, 44793580
verwendet.
Die erste Zeile mit den Zahlen "0 1 2 3 4 5 6 7 8 9" gibt nur den Index des darunterliegenden Schlüssels an.
Die zehn Schlüssel sind beliebige 8-stellige Zahlen, sie sollten sich nicht zu ähnlich sein (damit ähnliche Ausgangszahlen möglichst "unähnliche" Ergebnisse liefern) und als zweite Bedingung
müssen sie an der
gewählten "Auswahlziffer" (bei uns die "Einerziffer") eine "
0" besitzen (wie man leicht erkennen kann enden
alle 10 obigen Schlüssel mit "
0").
Die Verschlüsselung besteht nun aus zwei Schritten:
1.) Die Auswahlziffer (bei uns die "Einerziffer", also "
0" und "
5") der zu verschüsselnden Zahl liefert den Index für den zu benutzenden Schlüssel.
2.) Die Verschlüsselung selbst funktioniert wieder wie gehabt per "ziffernweise Modulo-10-Addition".
Code:
10000000 endet mit der "0", also Schlüssel mit Index "0" --> 81748930
+81748930
---------
91748930
bzw.
10000005 endet mit der "5", also Schlüssel mit Index "5" --> 72895010
+72895010
---------
82895015
Und schon sieht man den beiden verschlüsselten Zahlen "9174893
0" und "8289501
5" ihre ähnlichen Ursprungszahlen nicht mehr an!!!
Was man allerdings sieht ist, daß die beiden Einerziffern "
0" und "
5" dadurch daß unsere Schlüssel jeweils mit "
0" enden sozusagen "nicht verschlüsselt" werden. Dies ist gleichzeitig ein Vor- und Nachteil, warum werden wir gleich sehen.
Die Entschlüsselung funktioniert dank "Trick2" (siehe oben) sehr einfach: Da unsere Auswahlziffer (in diesem Beispiel die "Einerziffer") gleich ("
0" --> "
0" und "
5" --> "
5") geblieben ist, nehmen wir diese wieder als Index
und berechnen wie oben beschrieben den "Gegenschlüssel" ( s.o.: (99999999 - Schlüssel)+ 11111111 ):
Code:
91748930 endet mit der "0", also Schlüssel mit Index "0" --> 81748930 --> Gegenschlüssel ist 29362170
+29362170
---------
10000000
bzw.
82895015 endet mit der "5", also Schlüssel mit Index "5" --> 72895010 --> Gegenschlüssel ist 38215090
+38215090
---------
10000005
Jetzt sagt Du: "Ist ja schön und gut, aber ein böser Angreifer sieht einerseits, daß die Einerziffern "unverschlüsselt" geblieben ist und außerdem sehen sich die Chiffrate der Zahlen "10000000" und
"10000010" doch wieder ähnlich."
Darauf sage ich: "Ja, Du hast absolut Recht, deshalb müssen wir die nächste Evolutionsstufe zünden."
Diese heißt: "8-fach Verschlüsselung mit automatischer Nullsetzung der Auswahlziffer"
"8-fach" deswegen, weil einfach nach und nach jede der 8 Ziffern als Auswahlziffer genommen wird.
"automatische Nullsetzung der Auswahlziffer", da für die Verschlüsselung der jeweiligen Ziffer im Schlüssel diese Stelle (temporär) mit "0" besetzt werden muss (Trick2).
Nach diesen Vorbemerkungen dürfte der Quelltext relativ einfach zu verstehen sein. Ich habe ihn in Java verfasst, da ich erst beim Schreiben dieser Antwort das "C++" in Deinem Post gesehen habe (ich habe es
vorher schlicht überlesen). Es ist aber mMn sehr einfach dieses Programm nach C++ übersetzen.
Der Code ist nicht "schön", sondern noch "quick-and-dirty" und als Prototyp/Proof of concept zu verstehen. Insbesondere sollte man an einer zentralen Stelle die Konstanten "8" für die Anzahl der Ziffern und die "10"
für das Zahlensystem/die Anzahl der Schlüssel codieren. Desweiteren ist bei der "8-fach Encodierung" diese in eine eigene Funktion/Methode zu verlegen, usw.
Ich wollte einfach in der Praxis sehen, ob sich meine "Grübeleien" brauchbar umsetzen lassen.
Als Ergebnis würde ich diese Frage bejahen.
Code:
public class Mod10Add
{
public static void main(String[] args)
{
long[] input= { 10000000, 10000005, 11200736, 17460783, 51230567, 00000000, 99999999, 20000000, 20000001, 20000010, 20000100, 20001000, 20010000, 20100000, 21000000 };
// 0 1 2 3 4 5 6 7 8 9
long[] key1= { 81748930, 22413790, 90451280, 88725490, 13529660, 72895010, 38495220, 52199380, 26501870, 44793580 };
long[] encoded1= new long[input.length];
long[] decoded1= new long[input.length];
// single en-/decoding
for(int i= 0; i<input.length; i++) encoded1[i]= encode(input[i] , 0, key1);
for(int i= 0; i<input.length; i++) decoded1[i]= decode(encoded1[i], 0, key1);
System.out.println("");
System.out.println("Single encoding:");
System.out.println("");
System.out.println("original encoded decoded");
System.out.println("-------- -------- --------");
for(int i= 0; i<input.length; i++)
System.out.printf("%08d %08d %08d\n", input[i], encoded1[i], decoded1[i] );
// 8-fold en-/decoding with set zero
// 0 1 2 3 4 5 6 7 8 9
long[] key2= { 81249317, 27816794, 90453284, 88725413, 13529665, 72895314, 38495229, 52146387, 26541875, 44793532 };
// copy input
long[][] eee= new long[input.length][8+1];
for(int i= 0; i<input.length; i++) eee[i][0]= input[i];
// encode 8-fold
for(int d= 0; d<8; d++) for(int i= 0; i<input.length; i++) eee[i][d+1]= encode_set_zero(eee[i][d], d, key2);
// copy encoded values
long[][] ddd= new long[input.length][8+1];
for(int i= 0; i<input.length; i++) ddd[i][8]= eee[i][8];
// decode 8-fold
for(int d= 8-1; d>=0; d--) for(int i= 0; i<input.length; i++) ddd[i][d]= decode_set_zero(ddd[i][d+1], d, key2);
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("8-fold encoding:");
System.out.println("");
System.out.println("original encoded decoded");
System.out.println("-------- -------- --------");
for(int i= 0; i<input.length; i++)
System.out.printf("%08d %08d %08d\n", input[i], eee[i][8], ddd[i][0] );
System.out.println("");
for(int j= 0; j<=8; j++) System.out.printf("eee[%d] ", j);
System.out.print("x ");
for(int j= 8; j>=0; j--) System.out.printf("ddd[%d] ", j);
System.out.println("");
for(int j= 0; j<=8; j++) System.out.printf("-------- ");
System.out.print("x ");
for(int j= 8; j>=0; j--) System.out.printf("-------- ");
System.out.println("");
for(int i= 0; i<input.length; i++)
{
for(int j= 0; j<=8; j++)
System.out.printf("%08d ", eee[i][j]);
System.out.print("x ");
for(int j= 8; j>=0; j--)
System.out.printf("%08d ", ddd[i][j]);
System.out.println("");
}
}
static long encode(long value, int position, long[] key)
{
int digit= (int)nthDigit(value, position);
return addMod10(value, key[digit]);
}
static long decode(long value, int position, long[] key)
{
long[] decodeKey= new long[10];
for(int i= 0; i<10; i++) decodeKey[i]= addMod10(99999999-key[i], 11111111);
return encode(value, position, decodeKey);
}
static long addMod10(long value1, long value2)
{
long result= 0;
long factor= 1;
for(int i= 0; i<8; i++)
{
result+= ((nthDigit(value1, i) + nthDigit(value2, i))%10)*factor;
factor*= 10;
}
return result;
}
static long nthDigit(long l, int n)
{
long factor= 1;
for(int i= 0; i<n; i++) factor*=10;
return ((l/factor)%10);
}
static long encode_set_zero(long value, int position, long[] key)
{
long[] key_set_zero= new long[10];
int digit= (int)nthDigit(value, position);
long factor= 1;
for(int i= 0; i<position; i++) factor*= 10;
for(int i= 0; i<10; i++)
{
int keyDigit= (int)nthDigit(key[i], position);
key_set_zero[i]= key[i] - keyDigit*factor;
}
return addMod10(value, key_set_zero[digit]);
}
static long decode_set_zero(long value, int position, long[] key)
{
long[] decodeKey= new long[10];
for(int i= 0; i<10; i++) decodeKey[i]= addMod10(99999999-key[i], 11111111);
return encode_set_zero(value, position, decodeKey);
}
}
Als Ausgabe liefert obigber Code:
Code:
Single encoding:
original encoded decoded
-------- -------- --------
10000000 91748930 10000000
10000005 82895015 10000005
11200736 49695956 11200736
17460783 95185173 17460783
51230567 03329847 51230567
00000000 81748930 00000000
99999999 33682479 99999999
20000000 01748930 20000000
20000001 42413791 20000001
20000010 01748940 20000010
20000100 01748030 20000100
20001000 01749930 20001000
20010000 01758930 20010000
20100000 01848930 20100000
21000000 02748930 21000000
8-fold encoding:
original encoded decoded
-------- -------- --------
10000000 18127062 10000000
10000005 93952476 10000005
11200736 71102173 11200736
17460783 80463887 17460783
51230567 74013240 51230567
00000000 02550685 00000000
99999999 69205398 99999999
20000000 21764552 20000000
20000001 24468811 20000001
20000010 85147828 20000010
20000100 90891107 20000100
20001000 00403253 20001000
20010000 67211205 20010000
20100000 14557560 20100000
21000000 96641390 21000000
eee[0] eee[1] eee[2] eee[3] eee[4] eee[5] eee[6] eee[7] eee[8] x ddd[8] ddd[7] ddd[6] ddd[5] ddd[4] ddd[3] ddd[2] ddd[1] ddd[0]
-------- -------- -------- -------- -------- -------- -------- -------- -------- x -------- -------- -------- -------- -------- -------- -------- -------- --------
10000000 91249310 18055014 99294021 02714686 29510370 91505684 11311378 18127062 x 18127062 11311378 91505684 29510370 02714686 99294021 18055014 91249310 10000000
10000005 82895315 09601019 80840026 61080333 87581108 59576412 99269944 93952476 x 93952476 99269944 59576412 87581108 61080333 80840026 09601019 82895315 10000005
11200736 49695956 11480250 01833234 89553647 51358951 39373364 79066896 71102173 x 71102173 79066896 39373364 51358951 89553647 01833234 11480250 49695956 11200736
17460783 95185193 39878695 67263614 45983027 61484892 74403457 84922012 80463887 x 80463887 84922012 74403457 61484892 45983027 67263614 39878695 95185193 17460783
51230567 03376847 16895442 29314407 32834062 10539475 82524789 72977963 74013240 x 74013240 72977963 82524789 10539475 32834062 29314407 16895442 03376847 51230567
00000000 81249310 08055014 89294021 92714686 19510370 81505684 01311378 02550685 x 02550685 01311378 81505684 19510370 92714686 89294021 08055014 81249310 00000000
99999999 33682429 23035623 51420642 32660959 60065178 41004485 61810179 69205398 x 69205398 61810179 41004485 60065178 32660959 51420642 23035623 33682429 99999999
20000000 01249310 28055014 09294021 12714686 39510370 01505684 21311378 21764552 x 21764552 21311378 01505684 39510370 12714686 09294021 28055014 01249310 20000000
20000001 47816791 81509293 71952277 61302451 42501768 14596072 24015637 24468811 x 24468811 24015637 14596072 42501768 61302451 71952277 81509293 47816791 20000001
20000010 01249320 91692524 63487538 15527815 05920099 49913521 89606053 85147828 x 85147828 89606053 49913521 05920099 15527815 63487538 91692524 01249320 20000010
20000100 01249410 28055114 45861108 62671892 14777179 66713456 96108675 90891107 x 90891107 96108675 66713456 14777179 62671892 45861108 28055114 01249410 20000100
20001000 01240310 28056014 09295021 71085335 97586100 69571414 09264946 00403253 x 00403253 09264946 69571414 97586100 71085335 09295021 28056014 01240310 20001000
20010000 01259310 28065014 09204021 12724686 02127860 29133554 69826086 67211205 x 67211205 69826086 29133554 02127860 12724686 09204021 28065014 01259310 20010000
20100000 01349310 28155014 09394021 12814686 39610370 67605599 17741876 14557560 x 14557560 17741876 67605599 39610370 12814686 09394021 28155014 01349310 20100000
21000000 02249310 29055014 00294021 13714686 30510370 02505684 92958868 96641390 x 96641390 92958868 02505684 30510370 13714686 00294021 29055014 02249310 21000000
Als kleine Bemerkung zur 8-fach-Verschlüsselung ist vielleicht noch zu sagen, daß man bei "
original encoded decoded" sozusagen nur das Endergebnis zu sehen bekommt, d.h. insbesondere auch, daß der Algorithmus bei
ähnlichen Eingaben sich stark unterscheidende Ausgaben produziert.
Weiter unten im Bereich "
eee[0] eee[1] eee[2] ..." ("e" wie _e_ncoding) bzw. "
ddd[8] ddd[7] ddd[6] ..." ("d" wie _d_ecoding) kann man dem Algo schrittweise bei der Arbeit beobachten und meines Erachtens sehr
schön sehen wie sich anfangs noch ähnliche Zahlen ("
20000000" und Folgende) mehr und mehr unähnlicher werden, bis die Ergebnisse (eee[8]=ddd[8]) komplett differieren.
Bezüglich der Keys ("key2" im Quelltext) möchte ich nur anmerken, daß diese frei ausgedacht sind, ich habe lediglich weitestgehend die Ziffer "0" vermieden. Ob und falls ja wie weit sich durch die Auswahl der Keys das Ergebnis verändert habe ich nicht untersucht, falls jemand die Zeit und Muße hat dies zu tun würden mich eventuelle Ergebnisse durchaus interssieren.
Falls noch Fragen sind, gerne in diesem Thread, ansonsten verbleibe ich mit meiner klassischen Grußformel
HTH
BigNum
