Ôtant une ID

Je suis à la recherche d'un moyen de crypter/obscurcir un ID d'entier dans un autre entier. Plus précisément, j'ai besoin d'une fonction int F(int x), de sorte que

x<->F(x) est one-to-one correspondance (si x != y, F(x) != F(y))
donnée F(x), il est facile à trouver x donc F n'est pas une fonction de hachage
x et F(x), il est difficile/impossible de trouver F(y), quelque chose comme x ^ 0x1234 ne fonctionne pas

Pour plus de clarté, je ne suis pas à la recherche d'une forte solution de chiffrement, c'est seulement de l'obscurcissement. Imaginez une application web avec les url comme example.com/profile/1, example.com/profile/2 etc. Les profils eux-mêmes ne sont pas secrets, mais je tiens à prévenir casual voyeurs à vue/chercher tous les profils, l'un après l'autre, donc, je préfère les cacher derrière quelque chose comme example.com/profile/23423, example.com/profile/80980234 etc. Bien que la base de données stockée jetons peuvent faire le travail assez facilement, je suis curieux de savoir si il y a quelques calculs simples disponibles pour cela.

Une exigence importante je n'ai pas été clair, c'est que les résultats devraient regarder "aléatoire", c'est, étant donné une séquence x,x+1,...,x+n , F(x),F(x+1)...F(x+n) ne devrait pas former une progression de tout genre.

Est int F(int x) d'une obligation, ou pourrait-il en être de type int[2]F(int x) ?
Rieck, dans l'idéal, j'aimerais x et F(x) soit dans la gamme de nombre
Peut-F(X) secret?
oui la fonction sera gardé secret
puisque vous avez dit que vous aimeriez aller sans jeton, est-ce à dire que vous voulez éviter tout type de table de recherche?
Mošmondor, oui, exactement.
L'homme, cette question est parfaitement indiqué et c'est exactement ce que je cherche. Nice job.

InformationsquelleAutor georg | 2011-12-18

algorithm encryption

37

Dissimuler avec une combinaison de 2 ou 3 méthodes simples:
- XOR
- shuffle bits individuels
- convertir représentations modulaires (D. Knuth, Vol. 2, Chapitre 4.3.2)
- choisissez 32 (ou 64) le chevauchement des sous-ensembles de bits et XOR bits dans chaque sous-ensemble (parité bits de sous-ensembles)
- représenter dans de longueur variable numberic système de lecture aléatoire des chiffres
- choisissez une paire d'entiers impairs x et y qui sont multiplicatif inverses les uns des autres (modulo 2³²), puis multiplier par x pour dissimuler et de se multiplier par y à restaurer, toutes les multiplications sont modulo 2³² (source: "Une utilisation pratique de multiplicative inverses" par Eric Lippert)
De longueur Variable numberic méthode de système de ne pas obéir à votre "progression" exigence sur son propre. Il produit toujours de courte progressions arithmétiques. Mais lorsqu'il est combiné avec une autre méthode, il donne de bons résultats.

La même chose est vraie pour les représentations modulaires méthode.

Voici le code C++ exemple pour 3 de ces méthodes. Lecture aléatoire de bits exemple possible d'utiliser certains de ces masques et les distances à être de plus en plus imprévisibles. 2 autres exemples sont bons pour de petits nombres (juste pour donner l'idée). Ils devraient être étendus pour dissimuler toutes les valeurs entières correctement.
```
//*** 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
```
- Je vous remercie pour votre réponse. Si vous pouvez fournir quelques exemples de pseudo-code, si ce serait formidable.
- J'ai utilisé le C++ au lieu de pseudo-code. Ne veux pas la donner non testé exemples.
- Merci. Qui semble bien fonctionner.
- Quand j'essaie de le système numérique de la base de code ci-dessus avec x=99, je reçois z=44.
- pour obtenir réversible obfuscator le produit de toutes les bases devraient être plus grand que le nombre d'occulter. Dans cet exemple 3*4*5=60, de sorte que n'importe quel plus grand nombre (comme 99) ne sera pas nécessairement être restaurée à la même valeur.
- Comment pourrais-je l'utiliser pour encoder n'importe quel nombre de 32 bits? J'ai besoin d'utiliser 64 bits?
- Il est également possible d'obtenir des produits de toutes les bases plus petites, mais très proche de 2^32, puis de masquer les valeurs restantes à l'aide d'une petite table. Dans ce cas, tout reste dans des nombres de 32 bits.
InformationsquelleAutor Evgeny Kluev
9

Vous voulez que la transformation est réversible, et pas évident. Qui sonne comme un chiffrement qui prend un nombre dans un intervalle donné et produit un nombre différent dans la même gamme. Si votre portée est de 64 bits, puis utiliser DES. Si votre portée est de 128 bits, puis d'utiliser AES. Si vous souhaitez une autre gamme, alors votre meilleur pari est probablement Hasty Pudding de chiffrement, qui est conçu pour faire face à différentes tailles de bloc et avec des tranches de numéros qui ne sont pas parfaitement dans un bloc, comme 100 000 à 999,999.
- Des choses intéressantes, mais il peut être un peu difficile de demander à quelqu'un de mettre en œuvre un algorithme de chiffrement qui 1) n'a pas été testé et 2) n'avait pas été testé parce que c'est si difficile à comprendre 🙂
- Merci! Je suis en train de le garder aussi simple que possible.
- Si vous ne trouvez pas de mise en œuvre de Hasty Pudding (vous avez seulement besoin de l'un de la taille autorisée), alors vous pouvez facilement mettre en place un simple 4-tour de chiffrement Feistel (en.wikipedia.org/wiki/Feistel_cipher) dans une même taille de bloc. Il suffit de garder le chiffrement jusqu'à ce que la sortie est dans la plage correcte, comme avec Hasty Pudding. Pas sûr, mais assez pour obscurcir.
- La NSA a publié aujourd'hui le Paille de chiffre qui inclut les versions qui comprend 32-bit et 48-bit tailles de bloc. Qui peut également être utile pour affaiblir les nombres avec ces tailles. La version 32 bits, en particulier, est susceptible d'être utile.
InformationsquelleAutor rossum
6

Obscurcissement n'est pas vraiment suffisante en termes de sécurité.

Toutefois, si vous essayez de déjouer le spectateur occasionnel, je vous recommande une combinaison de deux méthodes:
- Une clé privée que vous combinez avec l'id par utilise xor ensemble
- Une rotation des bits d'un certain montant, à la fois avant et après la clé
  a été appliqué
Voici un exemple (à l'aide de pseudo-code):
```
  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
```
Je ne l'ai pas testé, mais je pense que c'est réversible, doit être rapide, et pas trop facile à démêler la méthode.
- Il y a également plus d'une constante mod 2^32 (parce que votre peu de rotation m'a rappelé de rot13, préférée de tout le monde trivialement fonction réversible).
- C'est vraiment juste return x XOR rotr(31415927, 5) bien, non? La dernière xor annule la première, et la tourne annuler eachother.. et bien sûr, toute la chaîne réversible est également réversible, de sorte qu'il ne satisfait à cette condition.
- J'ai couru quelques tests et je suis convaincu que les résultats sont comme prévu. Comme ccoakley mentionne, rot13 peut être utilisé à la place de rot5, les rotations de travail (mise en garde: 0 > rot > entier-size) et peuvent être considérés comme une autre touche. Il y a d'autres choses que vous pourriez jeter dans ici, tout comme le module comme il le suggère, et du moment qu'ils sont réversibles que harold mentionné.
- Ouais, juste en tournant une fois à gauche avec un premier et une fois à droite avec un premier serait plus judicieux. Ajouter et de jeter les transporter (identique au mod le plus grand entier + 1) ajouter un peu de dissimulation ainsi. Vous pouvez combiner toutes ces tant que vous n'avez pas accidentellement l'annuler les opérations précédentes. L'inverse est tout l'inverse.
- Désolé, mais @harold est la plupart du temps correct - l'ensemble de votre fonction est équivalente à x = x XOR F(0), ou x = x XOR 3087989491, ou x = x XOR rotr(31415927, 5). Votre prénom et votre xors annuler les uns les autres, de sorte que tous vous avez à faire est xoring la bitshifted entrée avec la touche - ou, de manière équivalente, xoring de l'entrée avec la bitshifted clé. Remarque c'est vrai même si vous avez utilisé des clés différentes pour chaque étape - toutes les touches pourraient être composés dans une seule clé peut être xored avec le texte en clair.
- C'est encore pire, il est assez facile de prouver que toute la chaîne de tourne par un décalage constant et xors avec une constante peut être résumés à une seule rotation et juste un xor. Deux tourne à tour de rôle peuvent être combinés (ajouter leur offset), deux xors après eux peuvent être combinés (xor avec le xor de deux constantes), et un xor/rot paire peut être échangé à la pourriture/xor en appliquant la même rotation de la constante dans le xor.
InformationsquelleAutor IAmNaN
5

J'ai trouvé ce morceau particulier de Python/PHP code très utile:

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

InformationsquelleAutor miracle2k
2

J'ai écrit un article sur sécuriser les permutations avec des algorithmes de chiffrement par bloc, qui devrait répondre à vos exigences comme indiqué.

Que je vous suggère, cependant, que si vous voulez dur à deviner identifiants, vous devez simplement les utiliser en premier lieu: générer des Uuid, et les utiliser comme clé primaire pour vos dossiers, en premier lieu - il n'y a pas besoin d'être en mesure de convertir vers et à partir d'un "vrai" ID.
- Des choses intéressantes, merci!
- Si vous êtes intéressé par cette démarche, utile en terme de recherche est "Format de la Préservation de Chiffrement". La page de wikipedia couvre le Noir/Rogaway document mentionné dans le Nick de l'article, ainsi que les développements les plus récents. J'ai utilisé avec succès FPE pour quelque chose de semblable à ce que vous êtes en train de faire, même si, dans mon cas, j'ai ajouté quelques morceaux en plus de l'id que j'ai utilisé pour la lumière de vérification de la validité.
InformationsquelleAutor Nick Johnson
2

Faire n'importe quoi avec les bits de l'IDENTIFIANT qui ne les détruisent pas. Par exemple:
- tourner la valeur
- utilisez la fonction rechercher remplacer certaines pièces de la valeur
- xor avec une certaine valeur
- swap bits
- swap d'octets
- miroir de l'ensemble de la valeur
- miroir d'une partie de la valeur
- ... utilisez votre imagination
Pour le décryptage, faire tout ce qui dans l'ordre inverse.

Créer un programme pour "chiffrer" certains les valeurs intéressantes pour vous et les mettre dans un tableau, vous pouvez examiner. Ont le même programme de TEST de cryptage/décryptage de routine AVEC tout un ensemble de valeurs que vous voulez avoir dans votre système.

Ajouter des éléments à la liste ci-dessus dans les routines jusqu'à ce que vos numéros regarde bien mutilé pour vous.

Pour quoi que ce soit d'autre, d'obtenir une copie de Le Livre.
- Ce que vous décrivez sont les blocs de construction d'un algorithme de chiffrement par bloc. Il est plus logique d'en utiliser un existant que d'inventer votre propre.
- Je sais que, avez-vous cliqué sur le lien dans la dernière ligne de mon post?
- Je n'ai pas réussi à mettre ensemble un rotl/xor combinaison donne des résultats que l'aspect "aléatoire" assez (voir la mise à jour). Les pointeurs?
- J'ai ajouté un peu plus d'activités...
- Je sais ce que vous êtes en reliant le cas - mais qui ne change pas le fait que vous êtes d'abord ce qui suggère qu'il construire quelque chose de lui-même, lorsqu'il fait beaucoup plus de sens d'utiliser un existant?
- évidemment, l'OP ne veut pas utiliser les crypto, comme il veut apprendre ou ne pas apprendre de nouvelles Api. Je suis totalement peux comprendre ça.
- Je ne pense pas que c'est évident à tous à partir de sa question. À l'aide d'un simple mais robuste de chiffrement comme XXTEA semble totalement justifié sur la base de sa question.
InformationsquelleAutor Daniel Mošmondor

J'ai écrit quelques code JS à l'aide de certaines des idées dans ce fil:

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,
);

Elle produit de bons résultats comme:

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'

Test avec:

  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));
   }

XOR1 et XOR2 sont juste des nombres aléatoires entre 0 et MAX. MAX est 2**32-1; vous devez définir ce que vous pensez que votre ID plus sera.

COPRIME est un nombre premier ' w/MAX. Je pense premier les nombres eux-mêmes sont premiers entre eux avec chaque autre numéro (à l'exception des multiples d'eux-mêmes).

INVERSE est difficile à comprendre. Ces billets de blog ne donne pas une réponse directe, mais WolframAlpha peut le comprendre pour vous. Fondamentalement, suffit de résoudre l'équation (COPRIME * x) % MAX = 1 pour x.

La build fonction est quelque chose que j'ai créé pour faciliter la création de ces encoder/décoder des pipelines. Vous pouvez nourrir autant d'opérations que vous voulez que [encode, decode] paires. Ces fonctions doivent être égales et opposées. Le XOR fonctions sont leurs propres compliments de sorte que vous n'avez pas besoin d'une paire de là.

Voici un autre plaisir l'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;
}

(ce qui suppose que 24 bits entiers -- il suffit de changer les numéros pour toute autre taille)

cool, merci pour le partage! BTW, c'est quoi "32n"? N'a jamais vu ça avant.
n est un certain nombre de postfix pour BigInts. C'est un nouveau JS fonctionnalité qui vous permet vraiment de grands nombres. J'avais besoin de l'utiliser parce que je suis en multipliant par vraiment des grands nombres qui peuvent causer l'une des valeurs intermédiaires temporairement dépasser Number.MAX_SAFE_INTEGER et perdre de la précision.
wow, c'est incroyable!

InformationsquelleAutor mpen

1

Pas sûr de savoir comment "dur" que vous en avez besoin, comment rapide, ou comment peu de mémoire à utiliser. Si vous n'avez pas de contraintes de mémoire, vous pourriez faire une liste de tous les nombres entiers, les mélanger et utiliser cette liste comme une cartographie. Cependant, même pour un 4 octets entier vous aurait besoin de beaucoup de mémoire.

Toutefois, cela pourrait être plus petits de sorte qu'au lieu de la cartographie de tous les nombres entiers vous mappez seulement 2 (ou pire des cas 1) octet de poids fort et de les appliquer à chaque groupe en entier. Donc, à l'aide de 2 octets entier serait (groupe1)(groupe2) vous mappez chaque groupe par le biais de la carte aléatoire. Mais cela signifie que si vous modifiez uniquement le groupe2 le mappage pour le groupe1 resterait la même. Cela pourrait "fixe" de la cartographie des différents bits de chaque groupe.

Donc, *(groupe2) pourrait être (peu 14,12,10,8,6,4,2,0) donc, l'ajout de 1 changerait à la fois groupe1 et groupe2.

Encore, ce n'est que la sécurité par l'obscurité, quelqu'un qui peut nourrir des numéros dans votre fonction (même si vous gardez la fonction secret) pourrait assez facilement le comprendre.
- Selon les contraintes du système, ce ne sera probablement pas travailler, parce que si vous pouvez inverser F(x) à x, alors vous devez avoir la permutation disponibles, à partir de laquelle vous pouvez facilement calculer F(y) donné toute l'arbitraire y.
- Comme je l'ai dit, ce n'est que la sécurité par l'obscurité. La permutation aurait à être connu, mais on pouvait voir la permutation comme la "clé". Le plus grand problème ici est que l'OP semble vouloir être en mesure de chiffrer tous les messages dans un ensemble (une petite) où le message chiffré doit tenir dans le même ensemble et cela devrait être valable pour tous les messages dans le jeu.
- Merci. Je suis en essayant d'éviter les tables de recherche.
InformationsquelleAutor Roger Lindsjö
1

Générer un privé clé symétrique pour l'utiliser dans votre application, et chiffrer votre entier avec elle. Cela permettra de satisfaire aux trois exigences, y compris les plus difficiles #3: on aurait besoin de deviner votre clé afin de briser votre système.
- thg435 demandé entier entier (et comme je le comprends, il doit travailler pour tous les entiers). Pouvez-vous suggérer un algorithme à clé privée qui aurait ces propriétés?
InformationsquelleAutor dasblinkenlight
1

Ce que vous décrivez ici semble être à l'opposé d'une fonction: il est facile d'inverser mais super difficile à appliquer. Une option serait d'utiliser une norme, hors-the-shelf de la clé publique de chiffrement algorithme dans lequel vous fixer un (secret, au hasard choisi) de la clé publique que vous garder un secret et d'une clé privée que vous partagez avec le monde entier. De cette façon, votre fonction F(x) serait le chiffrement de x à l'aide de la clé publique. Vous pouvez ensuite facilement décrypter F(x) à x en utilisant le privé, clé de déchiffrement. Notez que les rôles des clés publiques et privées sont reprises ici - vous donner la clé privée à tout le monde afin qu'ils puissent décrypter la fonction, mais de garder la clé publique de secret sur votre serveur. De cette façon:
1. La fonction est une bijection, donc c'est inversible.
2. Donnée F(x), x est efficace calculable.
3. X et F(x), il est extrêmement difficile de calculer F(y) de y, puisque sans la clé publique (en supposant que vous utilisez un cryptage fort schéma de chiffrement) il n'y a aucun moyen possible de chiffrer les données, même si la clé de déchiffrement est connu.
Cela a de nombreux avantages. Tout d'abord, vous pouvez être assuré que la crypto système est sûr, car si vous utilisez un réseau bien établi d'algorithme de type RSA, alors vous n'avez pas besoin de vous soucier accidentelle de l'insécurité. Deuxièmement, il y a déjà des bibliothèques pour ce faire, de sorte que vous n'avez pas besoin de code beaucoup et peut être à l'abri de côté les attaques par canaux. Enfin, vous pouvez rendre possible pour quiconque d'aller et inverser F(x) sans que personne effectivement en mesure de calculer F(x).

Un détail vous devriez certainement pas juste être en utilisant le standard de type int ici. Même avec les entiers 64 bits, il y a si peu de combinaisons possible pour un attaquant de juste force brute essayer d'inverser tout jusqu'à ce qu'ils trouvent le chiffrement F(y) pour un certain y même si elles n'ont pas la clé. Je suggère d'utiliser quelque chose comme un 512-bit de la valeur, étant donné que même la science-fiction attaque ne serait pas en mesure de forcer cette.

Espérons que cette aide!
- Mais thg435 semble poser pour le chiffrement qui peut chiffrer un petit ensemble de messages (4 octets messages) dans la même série de messages, et le chiffrement doit travailler pour tous les messages.
- Je vous remercie pour votre réponse. À l'aide d'un complet de cryptage cadre est peut-être la meilleure façon de le faire, mais un peu trop "lourd" pour mes besoins.
InformationsquelleAutor templatetypedef
1

Si xor est acceptable pour tout, mais inférer F(y) donné x et F(x) alors je pense que vous pouvez le faire avec un sel. Choisissez d'abord un secret une sorte de fonction. Par exemple S(s) = MD5(secret ^ s). Puis F(x) = (s, S(s) ^ x) où s est choisi au hasard. J'ai écrit que comme un tuple, mais vous pouvez combiner les deux pièces en un entier, par exemple F(x) = 10000 * s + S(s) ^ x. Le déchiffrement des extraits du sel s de nouveau et utilise F'(F(x)) = S(extract s) ^ (extract S(s)^x). Compte tenu de x et F(x) vous pouvez voir s (même si elle est légèrement obscurci) et vous pouvez déduire S(s) mais pour un autre utilisateur y avec un autre hasard sel t l'utilisateur sachant F(x) ne pouvez pas trouver S(t).
- Merci, mais cela n'a pas l'air suffisamment aléatoire pour moi (voir la mise à jour)
- Le sel est choisi au hasard et le hachage S(s) permettra également de regarder de manière aléatoire de sorte F(x) n'importe quel type de progression de la maladie à tous.
InformationsquelleAutor Ben Jackson

Vous devez vous connecter pour publier un commentaire.