Verschleierung einer ID

Ich suche nach einer Möglichkeit, eine Ganzzahl-ID in eine andere Ganzzahl zu verschlüsseln / zu verschleiern. Genauer gesagt, ich brauche eine Funktion int F(int x), damit

• x <-> F (x) ist eine Eins-zu-Eins-Entsprechung (wenn x! = y, F (x)! = F (y))
• Wenn F (x) gegeben ist, ist es einfach, x herauszufinden - F ist also keine Hash-Funktion
• Bei x und F (x) ist es schwer / unmöglich, F (y) herauszufinden, so etwas x ^ 0x1234funktioniert nicht

Aus Gründen der Klarheit suche ich keine starke Verschlüsselungslösung, sondern nur eine Verschleierung. Stellen Sie sich eine Web - Anwendung mit Urls wie example.com/profile/1, example.com/profile/2usw. Die Profile selbst nicht geheim sind, aber ich würde gerne lässig Voyeure Ansicht verhindern / holen alle Profile nacheinander, so dass ich sie lieber hinter etwas verstecken würde wie example.com/profile/23423, example.com/profile/80980234usw. Obwohl In der Datenbank gespeicherte Token können die Arbeit ganz einfach erledigen. Ich bin gespannt, ob dafür eine einfache Mathematik verfügbar ist.

Eine wichtige Anforderung war ich nicht klären ist , dass die Ergebnisse aussehen sollten „random“, das heißt, da eine Sequenz x,x+1,...,x+n, F(x),F(x+1)...F(x+n)sollte kein Fortschreiten jeglicher Art bilden.

Verschleiern Sie es mit einer Kombination aus 2 oder 3 einfachen Methoden:

• XOR
• mische einzelne Bits
• in modulare Darstellung konvertieren (D.Knuth, Vol. 2, Kapitel 4.3.2)
• Wählen Sie 32 (oder 64) überlappende Teilmengen von Bits und XOR-Bits in jeder Teilmenge (Paritätsbits von Teilmengen).
• Stellen Sie es in einem numerischen System mit variabler Länge und Shuffle-Ziffern dar
• ein Paar von ungeraden Zahlen wählen xund ydie multiplikative Inverse zueinander (Modulo 2 ³² ), dann multiplizieren mit xzu verschleiern und vermehren sich durch ydie Wiederherstellung sind alle Multiplikationen modulo 2 ³² (Quelle: „Eine praktische Anwendung der multiplikativen Umkehrungen“ von Eric Lippert )

Die numerische Systemmethode mit variabler Länge entspricht nicht allein Ihrer "Progressions" -Anforderung. Es werden immer kurze arithmetische Progressionen erzeugt. In Kombination mit einer anderen Methode ergeben sich jedoch gute Ergebnisse.

Gleiches gilt für die modulare Darstellungsmethode.

Hier ist ein C ++ - Codebeispiel für 3 dieser Methoden. Beispiel für Shuffle-Bits können verschiedene Masken und Entfernungen verwenden, um unvorhersehbarer zu sein. Andere 2 Beispiele sind gut für kleine Zahlen (nur um die Idee zu geben). Sie sollten erweitert werden, um alle ganzzahligen Werte richtig zu verschleiern.

// *** Numberic system base: (4, 3, 5) -> (5, 3, 4)
// In real life all the bases multiplied should be near 2^32
unsigned y = x/15 + ((x/5)%3)*4 + (x%5)*12; // obfuscate
unsigned z = y/12 + ((y/4)%3)*5 + (y%4)*15; // restore

// *** Shuffle bits (method used here is described in D.Knuth's vol.4a chapter 7.1.3)
const unsigned mask1 = 0x00550055; const unsigned d1 = 7;
const unsigned mask2 = 0x0000cccc; const unsigned d2 = 14;

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
t = (u ^ (u  >> d2)) & mask2;
y = u ^ t ^ (t << d2);

// Restore
t = (y ^ (y >> d2)) & mask2;
u = y ^ t ^ (t << d2);
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

// *** Subset parity
t = (x ^ (x >> 1)) & 0x44444444;
u = (x ^ (x << 2)) & 0xcccccccc;
y = ((x & 0x88888888) >> 3) | (t >> 1) | u; // obfuscate

t = ((y & 0x11111111) << 3) | (((y & 0x11111111) << 2) ^ ((y & 0x22222222) << 1));
z = t | ((t >> 2) ^ ((y >> 2) & 0x33333333)); // restore

Sie möchten, dass die Transformation reversibel und nicht offensichtlich ist. Das klingt nach einer Verschlüsselung, die eine Zahl in einem bestimmten Bereich akzeptiert und eine andere Zahl im gleichen Bereich erzeugt. Wenn Ihr Bereich 64-Bit-Zahlen umfasst, verwenden Sie DES. Wenn Ihr Bereich 128-Bit-Zahlen beträgt, verwenden Sie AES. Wenn Sie einen anderen Bereich wünschen, ist Ihre wahrscheinlich beste Wahl die Hasty Pudding-Chiffre , die für unterschiedliche Blockgrößen und Nummernkreise ausgelegt ist, die nicht genau in einen Block passen, z. B. 100.000 bis 999.999.

Die Verschleierung ist aus Sicherheitsgründen nicht ausreichend.

Wenn Sie jedoch versuchen, den zufälligen Betrachter zu vereiteln, würde ich eine Kombination aus zwei Methoden empfehlen:

• Ein privater Schlüssel, den Sie mit der ID kombinieren, indem Sie sie zusammenfügen
• Drehen der Bits um einen bestimmten Betrag vor und nach dem Anlegen des Schlüssels

Hier ist ein Beispiel (unter Verwendung von Pseudocode):

  def F(x)
    x = x XOR 31415927       # XOR x with a secret key
    x = rotl(x, 5)           # rotate the bits left 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    x = rotr(x, 5)           # rotate the bits right 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    return x                 # return the value
  end

Ich habe es nicht getestet, aber ich denke, das ist reversibel, sollte schnell sein und nicht zu einfach, um die Methode zu testen.

Ich fand diesen speziellen Python / PHP-Code sehr nützlich:

https://github.com/marekweb/opaque-id

Ich habe JS-Code mit einigen der Ideen in diesem Thread geschrieben:

const BITS = 32n;
const MAX = 4294967295n;
const COPRIME = 65521n;
const INVERSE = 2166657316n;
const ROT = 6n;
const XOR1 = 10296065n; 
const XOR2 = 2426476569n;


function rotRight(n, bits, size) {
    const mask = (1n << bits) - 1n;
    // console.log('mask',mask.toString(2).padStart(Number(size),'0'));
    const left = n & mask;
    const right = n >> bits;
    return (left << (size - bits)) | right;
}

const pipe = fns => fns.reduce((f, g) => (...args) => g(f(...args)));

function build(...fns) {
    const enc = fns.map(f => Array.isArray(f) ? f[0] : f);
    const dec = fns.map(f => Array.isArray(f) ? f[1] : f).reverse();

    return [
        pipe(enc),
        pipe(dec),
    ]
}

[exports.encode, exports.decode] = build(
    [BigInt, Number],
    [i => (i * COPRIME) % MAX, i => (i * INVERSE) % MAX],
    x => x ^ XOR1,
    [x => rotRight(x, ROT, BITS), x => rotRight(x, BITS-ROT, BITS)],
    x => x ^ XOR2,
);

Es liefert einige schöne Ergebnisse wie:

1 1352888202n 1 'mdh37u'
2 480471946n 2 '7y26iy'
3 3634587530n 3 '1o3xtoq'
4 2225300362n 4 '10svwqy'
5 1084456843n 5 'hxno97'
6 212040587n 6 '3i8rkb'
7 3366156171n 7 '1jo4eq3'
8 3030610827n 8 '1e4cia3'
9 1889750920n 9 'v93x54'
10 1017334664n 10 'gtp0g8'
11 4171450248n 11 '1wzknm0'
12 2762163080n 12 '19oiqo8'
13 1621319561n 13 'qtai6h'
14 748903305n 14 'cdvlhl'
15 3903018889n 15 '1sjr8nd'
16 3567473545n 16 '1mzzc7d'
17 2426613641n 17 '144qr2h'
18 1554197390n 18 'ppbudq'
19 413345678n 19 '6u3fke'
20 3299025806n 20 '1ik5klq'
21 2158182286n 21 'zoxc3y'
22 1285766031n 22 'l9iff3'
23 144914319n 23 '2ea0lr'
24 4104336271n 24 '1vvm64v'
25 2963476367n 25 '1d0dkzz'
26 2091060108n 26 'ykyob0'
27 950208396n 27 'fpq9ho'
28 3835888524n 28 '1rfsej0'
29 2695045004n 29 '18kk618'
30 1822628749n 30 'u559cd'
31 681777037n 31 'b9wuj1'
32 346231693n 32 '5q4y31'

Testen mit:

  const {encode,decode} = require('./obfuscate')

  for(let i = 1; i <= 1000; ++i) {
        const j = encode(i);
        const k = decode(j);
        console.log(i, j, k, j.toString(36));
   }

XOR1und XOR2sind nur Zufallszahlen zwischen 0 und MAX.MAXist 2**32-1; Sie sollten dies auf das einstellen, was Ihrer Meinung nach Ihre höchste ID sein wird.

COPRIMEist eine Zahl, die Koprime w / MAX. ich denke, Primzahlen selbst sind Koprime mit jeder anderen Zahl (außer Vielfachen von sich selbst).

INVERSEist die schwierige Frage. Diese Blog-Beiträge geben keine klare Antwort, aber WolframAlpha kann es für Sie herausfinden . Lösen Sie einfach die Gleichung(COPRIME * x) % MAX = 1 für x.

Die buildFunktion wurde von mir erstellt, um das Erstellen dieser Codierungs- / Decodierungs-Pipelines zu vereinfachen. Sie können beliebig viele Operationen als [encode, decode]Paare eingeben. Diese Funktionen müssen gleich und entgegengesetzt sein. DasXOR Funktionen sind ihre eigenen Komplimente, so dass Sie dort kein Paar benötigen.

Hier ist eine weitere lustige Involution :

function mixHalves(n) {
    const mask = 2n**12n-1n;
    const right = n & mask;
    const left = n >> 12n;
    const mix = left ^ right;
    return (mix << 12n) | right;
}

(geht von 24-Bit-Ganzzahlen aus - ändern Sie einfach die Zahlen für eine andere Größe)

Machen Sie alles mit den Bits der ID, die sie nicht zerstören. Beispielsweise:

• Drehen Sie den Wert
• Verwenden Sie Lookup, um bestimmte Teile des Werts zu ersetzen
• xoder mit einem gewissen Wert
• Bits tauschen
• Bytes austauschen
• spiegeln den gesamten Wert
• einen Teil des Wertes spiegeln
• ... Nutze deine Vorstellungskraft

Führen Sie dies zur Entschlüsselung in umgekehrter Reihenfolge durch.

Erstellen Sie ein Programm, das einige interessante Werte für Sie "verschlüsselt" und in eine Tabelle einfügt, die Sie untersuchen können. Lassen Sie dasselbe Programm Ihre Verschlüsselungs- / Entschlüsselungsroutine mit allen Werten testen, die Sie in Ihrem System haben möchten.

Fügen Sie der obigen Liste Dinge zu den Routinen hinzu, bis Ihre Zahlen für Sie richtig verstümmelt aussehen.

Für alles andere erhalten Sie eine Kopie des Buches .

Ich habe einen Artikel über sichere Permutationen mit Blockchiffren geschrieben , der Ihre Anforderungen wie angegeben erfüllen sollte.

Ich würde jedoch vorschlagen, dass Sie, wenn Sie schwer zu erratende Bezeichner möchten, diese zunächst verwenden sollten: Generieren Sie UUIDs und verwenden Sie diese zunächst als Primärschlüssel für Ihre Datensätze - Sie müssen nicht in der Lage sein in und von einer "echten" ID konvertieren.

Ich bin mir nicht sicher, wie "hart" es sein muss, wie schnell oder wie wenig Speicher verwendet werden soll. Wenn Sie keine Speicherbeschränkungen haben, können Sie eine Liste aller Ganzzahlen erstellen, diese mischen und diese Liste als Zuordnung verwenden. Selbst für eine 4-Byte-Ganzzahl würden Sie jedoch viel Speicher benötigen.

Dies könnte jedoch kleiner gemacht werden, sodass Sie anstelle der Zuordnung aller Ganzzahlen nur 2 (oder im schlimmsten Fall 1) Byte zuordnen und diese auf jede Gruppe in der Ganzzahl anwenden würden. Wenn Sie also 2 Bytes verwenden, wäre eine Ganzzahl (Gruppe1) (Gruppe2). Sie würden jede Gruppe durch die zufällige Zuordnung zuordnen . Dies bedeutet jedoch, dass die Zuordnung für Gruppe1 gleich bleibt, wenn Sie nur Gruppe2 ändern. Dies könnte "behoben" werden, indem jeder Gruppe unterschiedliche Bits zugeordnet werden.

Also könnte * (Gruppe2) sein (Bit 14,12,10,8,6,4,2,0), also würde das Hinzufügen von 1 sowohl Gruppe1 als auch Gruppe2 ändern .

Dies ist jedoch nur Sicherheit durch Unbekanntheit. Jeder, der Zahlen in Ihre Funktion einspeisen kann (selbst wenn Sie die Funktion geheim halten), kann dies ziemlich leicht herausfinden.

Generieren Sie einen privaten symmetrischen Schlüssel zur Verwendung in Ihrer Anwendung und verschlüsseln Sie Ihre Ganzzahl damit. Dies wird alle drei Anforderungen erfüllen, einschließlich der schwierigsten Nr. 3: Man müsste Ihren Schlüssel erraten, um Ihr Schema zu brechen.

Was Sie hier beschreiben, scheint das Gegenteil einer Einwegfunktion zu sein: Es ist leicht zu invertieren, aber sehr schwierig anzuwenden. Eine Möglichkeit wäre die Verwendung eines Standardverschlüsselungsalgorithmus für öffentliche Schlüssel von der Stange, bei dem Sie einen (geheimen, zufällig ausgewählten) öffentlichen Schlüssel festlegen, den Sie geheim halten, und einen privaten Schlüssel, den Sie mit der Welt teilen. Auf diese Weise wäre Ihre Funktion F (x) die Verschlüsselung von x mit dem öffentlichen Schlüssel. Mit dem privaten Entschlüsselungsschlüssel können Sie dann F (x) problemlos wieder nach x entschlüsseln. Beachten Sie, dass die Rollen des öffentlichen und des privaten Schlüssels hier vertauscht sind. Sie geben den privaten Schlüssel an alle weiter, damit diese die Funktion entschlüsseln können, aber den öffentlichen Schlüssel auf Ihrem Server geheim halten. Dieser Weg:

1. Die Funktion ist eine Bijektion, also invertierbar.
2. Bei F (x) ist x effizient berechenbar.
3. Bei x und F (x) ist es äußerst schwierig, F (y) aus y zu berechnen, da es ohne den öffentlichen Schlüssel (vorausgesetzt, Sie verwenden ein kryptografisch starkes Verschlüsselungsschema) keine praktikable Möglichkeit gibt, die Daten zu verschlüsseln, selbst wenn es sich um private Daten handelt Entschlüsselungsschlüssel ist bekannt.

Das hat viele Vorteile. Erstens können Sie sicher sein, dass das Kryptosystem sicher ist, denn wenn Sie einen etablierten Algorithmus wie RSA verwenden, müssen Sie sich keine Sorgen über versehentliche Unsicherheit machen. Zweitens gibt es bereits Bibliotheken, die dies tun. Sie müssen also nicht viel programmieren und können gegen Seitenkanalangriffe immun sein. Schließlich können Sie es jedem ermöglichen, F (x) zu invertieren, ohne dass jemand tatsächlich F (x) berechnen kann.

Ein Detail - Sie sollten hier definitiv nicht nur den Standard-Int-Typ verwenden. Selbst bei 64-Bit-Ganzzahlen sind so wenige Kombinationen möglich, dass ein Angreifer nur mit brutaler Gewalt versuchen kann, alles umzukehren, bis er für einige y die Verschlüsselung F (y) findet, selbst wenn er nicht über den Schlüssel verfügt. Ich würde vorschlagen, so etwas wie einen 512-Bit-Wert zu verwenden, da selbst ein Science-Fiction-Angriff dies nicht brutal erzwingen könnte.

Hoffe das hilft!

Wenn xores für alles akzeptabel ist, aber darauf schließen F(y), xund F(x)dann denke ich, dass Sie das mit einem Salz tun können . Wählen Sie zuerst eine geheime Einwegfunktion. Zum Beispiel S(s) = MD5(secret ^ s). Dann , F(x) = (s, S(s) ^ x)wo swird zufällig ausgewählt. Ich habe das als Tupel geschrieben, aber Sie können die beiden Teile zu einer ganzen Zahl kombinieren, z F(x) = 10000 * s + S(s) ^ x. Die Entschlüsselung extrahiert das Salz swieder und verwendet F'(F(x)) = S(extract s) ^ (extract S(s)^x). Gegeben xund F(x)Sie können sehen s(obwohl es leicht verschleiert ist) und Sie können schließen, S(s)aber für einen anderen Benutzer ymit einem anderen zufälligen Salz, tden der Benutzer F(x)nicht finden kann S(t).