Buscando un bijective, función discreta que se comporta tan caótica como sea posible

Question

Tengo que escribir un código de cupón sistema, pero no quiero guardar cada código de cupón en la base de datos. (Para el rendimiento y el diseño). Más bien me gustaría generar códigos posteriores que son marca de agua con otro código.

Se debe, como una especie de fantasía y de azar. En la actualidad se parecen a esto:

1: AKFCU2, 2: AKFDU2, 3: AKFDW2, 4: AKHCU2, 5: AKHCW2, ..., 200: CLFSU2, 201: CLFSW2, ...

Es obvio que después de códigos de aspecto muy similar, como acabo de convertir mi código de ingredientes (la marca de agua y el entero en la frente) a binario la base y permutated la orden por un esquema fijo. Pero para evitar que la gente fácilmente adivinar otro código válido o incluso accidentalmente introducir otro código válido (por lo tanto hacer que el otro código no válido mediante el uso de ella) yo preferiría algo más caótico, como este:

1: FIOJ32, 2: X9NIU2, 3: SIUUN7, 4: XTVV4S, ...

Al final el problema es encontrar un bijective, función discreta en el dominio {0,1}^27 (o, alternativamente,{0,1,2,3,4, ..., [10^(8.5)]}) que está lejos de ser continua. También debería ser tan simple como sea posible de implementar. (EDIT: yo también la necesidad de implementar la función de inversión.)

Cualquier sugerencia para tal función?

Answer 1

Tomar cualquier extraño $a$ y calcular el $x \mapsto ax + b \pmod{2^{27}}$.

EDIT: he Aquí una más sofisticada sugerencia. Las siguientes funciones son todos los invertible y fáciles de implementar:

• Multiplicación por un número impar modulo $2^{27}$.
• Adición de un número arbitrario modulo $2^{27}$.
• XOR de un arbitrario 27-número de bits.
• La rotación de los bits (puede ser implementado usando dos turnos).

Si usted componer en repetidas ocasiones se vuelven más difíciles de romper (pero probablemente todavía fácil para alguien que ya conoce la forma general de su sistema de cifrado).

Al componer, me refiero a que se aplican a varios de ellos en la sucesión (se puede aplicar una determinada asignación de más de una vez con las mismas o diferentes parámetros).

---

Otra sugerencia es el uso de una permutación aleatoria. No es difícil generar una permutación aleatoria, y dada una permutación para calcular su inversa. Usted puede almacenar tanto las permutaciones en un archivo y cargar a la memoria (si tienes suficiente - es de 1GB para ambos) cada vez que su principal programa se inicia.

Answer 2

usted podría hacer algo inspirado por RSA, donde no se necesitan dos llaves. como este:

calcular todo el modulo $p$ donde $p$ es prim. que será entonces el GF[$p$] (GaloisField). ahora en lugar de encontrar un generador de $g$ para que GF[$p$] y el cálculo de nada en potencias de $g$, se puede utilizar cualquiera de los grandes números para la multiplicación y la suma. este allone entonces será muy inseguro, pero va a ser muy caótico en combinación con algunos de los bits de las operaciones.

la codificación y decodificación de las funciones pueden ser combinadas sencillas funciones no seguras. la combinación hace más impredecible, sobre todo con el poco de operaciones.

(calcular una vez que el recíproco ($m^{-1}\equiv m^{p-2}$) de todos los $m$, que se utiliza para multiplicar; vas a necesitar para el descifrado.)

---

vamos a definir las funciones de enc1 y dec1 basado en la multiplicación:

$enc1_m(x)=x·m$ (mod p)

$dec1_m(y)=y·m^{-1}$ (mod p)

..................................................

y otro par basado en la adición:

$enc2_a(x)=x+a$ (mod p)

$dec2_a(y)=y-a$ (mod p)

..................................................

y otro par basada en bits de revolver, pero que necesitan ser invertible y nunca generar un valor de $\geq p$:

deje $(\odot,\oplus,\otimes,\neg)$ ser el bit a bit (and,or,xor,not) las operaciones de

deje $permutateAndXorLowestNBits_{s}(x,n)$ cambio de los más bajos de n bits de x, de modo que es invertible. en otras palabras, esta condición se tiene: $$\forall x,s,n: permutateAndXorLowestNBits_{s}^{-1}(permutateAndXorLowestNBits_{s}(x,n),n)=x$$

deje que N(x) es el número de bits más bajos de x que puede ser "segura" cambiado de modo que después de cambiar los bits, N dará como resultado el mismo número y el valor no supera p. en otras palabras, estas dos condiciones: $$x \oplus (2^{N(x)}-1) < p$$ $$\forall y. x \odot \neg(2^{N(x)}-1) \leq y \leq x \oplus (2^{N(x)}-1) \Rightarrow N(y)=N(x)$$

$enc3_s(x) = permutateAndXorLowestNBits_{s}(x,N(x))$

$dec3_s(y) = permutateAndXorLowestNBits_{s}^{-1}(y,N(y))$

..................................................

ahora, la clave resultante será (m,a,s) y las funciones de:

$enc_{m,a,s}(x)=enc1_m(enc2_a(enc3_s(x)))$

$dec_{m,a,s}(y)=dec3_s(dec2_a(dec1_m(y)))$

pero cualquier otro más complec combinación sería válido, también. recuerde que cualquier combinación de varios enc1s y enc2s puede ser expresado como una combinación sencilla de enc1 y enc2; por lo tanto, la alternativa con enc3.

---

no sé, lo difícil que será para romper este si sólo p es conocido. sin el bit de operaciones, una ecuación lineal rompería esta, pero con los bits de las operaciones será muy caótico. ¿alguien sabe?

de lo contrario, usted todavía puede hacer algo como un sistema de cifrado de Feistel, pero no sé si sería más seguro o cómo medir eso.