Dos-muchas salidas

17

El reto

Te presento otro desafío espía contra espía que enfrenta a los ofuscadores frente a los crackers. En este caso, sin embargo, el dato a proteger no es una entrada sino una salida .

Las reglas del desafío son simples. Escriba una rutina con las siguientes especificaciones:

  1. La rutina puede estar escrita en cualquier idioma pero no puede exceder los 320 bytes.
  2. La rutina debe aceptar tres enteros con signo de 32 bits como entradas. Puede tomar la forma de una función que acepta 3 argumentos, una función que acepta una sola matriz de 3 elementos o un programa completo que lee 3 enteros de cualquier entrada estándar.
  3. La rutina debe generar un entero de 32 bits con signo.
  4. Sobre todas las entradas posibles, la rutina debe generar entre 2 y 1000 valores únicos (inclusive). El número de valores únicos que puede generar una rutina se denomina clave .

Como ejemplo, el programa C

int foo( int i1, int i2, int i3 ) {
    return 20 + (i1^i2^i3) %5;
}

tiene una llave de 9, ya que (esperemos) sólo tiene salida de los nueve valores 16, 17, 18, 19, 20, 21, 22, 23, y 24.

Algunas limitaciones adicionales son las siguientes:

  1. La rutina debe ser totalmente determinista e invariante en el tiempo, devolviendo salidas idénticas para entradas idénticas. La rutina no debe llamar a los generadores de números pseudoaleatorios.
  2. Es posible que la rutina no dependa de "variables ocultas", como datos en archivos, variables del sistema o características de lenguaje esotérico. Por ejemplo, las rutinas generalmente no deberían referirse a constantes a menos que las constantes estén claramente definidas en el código mismo. Las rutinas que se basan en peculiaridades del compilador, resultados de operaciones matemáticamente indefinidas, errores aritméticos, etc., también se desaconsejan. En caso de duda, por favor pregunte.
  3. Usted (el codificador) debe saber con precisión cuántas salidas únicas puede producir la rutina y debe poder proporcionar al menos una secuencia de entrada que produzca cada salida. (Dado que potencialmente puede haber cientos de salidas únicas, este conjunto solo se solicitará en caso de que su clave sea impugnada).

Dado que este problema se parece mucho menos al cifrado clásico que el anterior, espero que sea accesible para un público más amplio.

Cuanto más creativo, mejor.

La puntuación

Los envíos más cortos sin descifrar por conteo de bytes se declararán ganadores.

Si hay alguna confusión, no dude en preguntar o comentar.

El contra desafío

Se alienta a todos los lectores, incluidos los que han presentado sus propias rutinas, a "descifrar" los envíos. Un envío se agrieta cuando su clave se publica en la sección de comentarios asociados. Si un envío persiste durante 72 horas sin ser modificado o agrietado, se considera "seguro" y cualquier éxito posterior en el agrietamiento será ignorado por el concurso.

Solo se permite un intento de craqueo por envío por lector. Por ejemplo, si presento al usuario X: "su clave es 20" y me equivoco, el usuario X rechazará mi suposición como incorrecta y ya no podré enviar suposiciones adicionales para ese envío.

Las presentaciones agrietadas se eliminan de la contienda (siempre que no sean "seguras"). No deben ser editados. Si un lector desea enviar una nueva rutina, debe hacerlo en una respuesta separada.

El puntaje de un cracker es el número de envíos (que cumplen o no) que descifra. Para los crackers con recuentos idénticos, la clasificación se determina por el recuento total de bytes en todas las presentaciones agrietadas (cuanto mayor, mejor).

Los cracker (s) con los puntajes más altos serán declarados ganadores junto con los desarrolladores de las rutinas ganadoras.

Por favor no descifre su propia presentación.

La mejor de las suertes. :)

Tabla de clasificación

Última actualización 2 de septiembre, 10:45 AM EST

Barreras inamovibles (presentaciones no agrietadas):

  1. CJam, 105 [Dennis]

Fuerzas imparables (crackers):

  1. Dennis [ Java, 269 ; C 58 ; Mathematica, 29 ]
  2. Martin Büttner [ Java, 245 ]
COTO
fuente
11
¿Puedo sugerir [policías y ladrones] como la etiqueta para estos desafíos? Creo que es un nombre bastante establecido para tales juegos en seguridad y probablemente provocará más interés que [adversario].
Martin Ender
Seguro. Lo cambiaré ahora.
COTO
¿Qué tipo de salida es aceptable? STDOUT return
,,
2
Tu ejemplo es incorrecto; su firma es 9.% 5 puede devolver cualquier cosa de -4 a 4, inclusive.
Keith Randall
1
@ Dennis, estaría bien si lo intentaras de nuevo. Fue mi culpa que estuviera en mal estado.
Stretch Maniac

Respuestas:

7

CJam, 105 bytes

1q~]4G#b2A#md"M-k^XM-WHM-n^GM-0%M-uwM-gM-^XeM-kM-^VO^Ph,M-^MM-^PM-qM-!M-8M-AM-OM-~tM-^FM-cM-h^AM-0M-0M-lM-@M-^[MF=M-^Z^SM-1M-KM-T2M-9M-UmSM-N
M-8M-^^M-n$4M-^M^SM-x M-OM-^@^?"256b@D#Y256#%2+md!A3#*)%)%

Lo anterior usa notación caret y M, ya que contiene caracteres no imprimibles. Después de convertir la secuencia de bytes en un entero ( 256b), se ejecuta el siguiente código:

1q~]4G#b2A#md
12313030820310059479144347891900383683119627474072658988524821209446180284434934346766561958060381533656780340359503554566598728599799248566073353154035839
@D#Y256#%2+md!A3#*)%)%

Puede probar esta versión en línea en el intérprete de CJam .

Cómo funciona

Esta presentación utiliza la teoría de números en lugar de la ofuscación. El programa devolverá 0 para casi todas las entradas. De las pocas entradas que resultan en una salida distinta de cero, se deriva un módulo secreto que se aplica a los 10 bits menos significativos del tercer entero.

La forma más eficiente de resolver este desafío (que se me ocurre) sería factorizar el entero de 512 bits, que espero no se pueda lograr en 72 horas.

" Prepend 1 to the numbers read from STDIN and convert the resulting array into an integer
  (“N”) by considering them digits of a base 2**32 number.                                 ";

1q~]4G#

" Compute “N / 1024” and “N % 1024”.                                                       ";

2A#md

" Push a carefully selected 512 bit semi-prime (“S”).                                      ";

12313030820310059479144347891900383683119627474072658988524821209446180284434934346766561958060381533656780340359503554566598728599799248566073353154035839

" Compute P = (N / 1024) ** 13 % 2 ** 256 + 2.                                             ";

@D#Y256#%2+

" Compute “S / P” and “S % P”.                                                             ";

md

" Compute “M = (S / P) % (1000 * !(S % P) + 1) + 1”.

  “M” is the key if P is a divisor of S; otherwise, “M == 1”.                              ";

!A3#*)%)

" Compute the final output: “N % 1024 % M”.                                                ";

%

Ejecución de ejemplo

$ base64 -d > outputs.cjam <<< MXF+XTRHI2IyQSNtZCLrGNdI7gewJfV355hl65ZPEGgsjZDxobjBz/50huPoAbCw7MCbTUY9mhOxy9QyudVtU84KuJ7uJDSNE/ggz4B/IjI1NmJARCNZMjU2IyUyK21kIUEzIyopJSkl
$ wc -c outputs.cjam
105 outputs.cjam
$ LANG=en_US cjam outputs.cjam < outputs.secret; echo
1
$ LANG=en_US cjam outputs.cjam <<< '1 2 3'; echo
0
Dennis
fuente
Eres demasiado bueno con las cosas de cifrado. ;)
COTO
11
"Esta presentación utiliza la teoría de números en lugar de la ofuscación". Mira el código "Hmm, cierto".
Sepıʇǝɥʇuʎs
4

Java - 269

Gracias por la paciencia de todos, esto ahora debería solucionarse.

acortado:

int a(int a,int b,int c){double d=180-360.0/(int)(Math.abs(Math.sin(a*60))*50+2),e=180-360.0/(int)(Math.abs(Math.cos(b*60))*50+2),f=180-360.0/(int)(Math.atan2(c*60, a*60)*51+2);if(Math.abs(d+e+f-360)<.1)return Integer.valueOf((int)d+""+(int)e+""+(int)f);else return 1;}

No acortado:

int a(int a, int b, int c) {
    double d = 180 - 360.0 / (int) (Math.abs(Math.sin(a * 60)) * 50 + 2);
    double e = 180 - 360.0 / (int) (Math.abs(Math.cos(b * 60)) * 50 + 2);
    double f = 180 - 360.0 / (int) (Math.atan2(c * 60, a * 60) * 51 + 2);
    if (Math.abs(d + e + f - 360) < .1)
        return Integer.valueOf((int) d + "" + (int) e + "" + (int) f);
    else
        return 1;
}
Estiramiento maniaco
fuente
Puede guardar cuatro caracteres cambiando double e,f,d=...;e=...;f=...;adouble d=...,e=...,f=...;
Ypnypn
@Ypnypn ¡Gracias! agregado a la versión de golf.
Stretch Maniac
1
Segundo intento ( con permiso explícito ): 122
Dennis
1
@Dennis buen trabajo! (Eso es todo)
Stretch Maniac
1
@Dennis En ese caso, te estás olvidando 1y tu respuesta también es incorrecta;) (123 está en lo correcto ... alguien viene y toma el puntaje de craqueo ...). Y supongo que Stretch Maniac no tuvo en cuenta sin == 1.0cuando dijo que 122 es correcto.
Martin Ender
2

Un muestreador

No es una entrada oficial, por supuesto, y el recuento de caracteres es demasiado alto, pero imagino que si alguien quiere un desafío para aturdir la mente, pueden intentar determinar cuántas salidas únicas produce la siguiente función (dadas tres entradas como se describe en el OP) :

function z(y,_,$){M=[];N=[];O=[];C=1792814437;P=72;r=t=0;(f=function(a,k,L){if(k<a.length){for(L=a[k],a[k]=0;a[k]<L;a[k]++)f(a,k+1)}else
if(!t){f([P-1,P-1],0,++t);N=M;while(t<2*P){s=!(t&1);f([P,P,P,P],0,++t);r=r||(s?0:t);t&1&&(N=O);O=[]}}else
((t<2)&&(((d=P*a[0]+(P+1)*a[1]+P)<(P<<6))&&(M[d]=(((y^~_)>>a[0])+((_^~$)>>(a[0]-32)))&1),((a[1]<P-a[0])&&
(M[a[1]+(P+1)*a[0]]=(($^C)>>a[0]+16-a[1])&1))||1))||((t&1)&&((O[P*a[2]+a[3]]|=M[a[1]+P*a[2]]&N[P*a[0]+a[3]]&&
!(a[0]-a[1]))||1))||(s|=N[(a[0]+1)*a[1]+a[3]]);})([],0,0);return r;}

De hecho, estoy tan seguro de que es indescifrable que otorgaré a cualquiera que lo descifre el "Premio Supremo Imparable de la Fuerza de la Naturaleza".

Porque realmente, se lo merecen.

COTO
fuente
1
¡Deberías ofrecer una recompensa por ello!
Orby
1
@Orby Eso sería bueno, pero es difícil otorgar una recompensa por un comentario.
Geobits
@COTO ¿Este desafío aún está vigente?
Soham Chowdhury
@SohamChowdhury: Absolutamente. Si te das cuenta, expondré tu victoria en el OP. Si no, avíseme y publicaré la solución.
COTO
2

C, 58 bytes (agrietado)

Una simple:

f(a,b,c){return(long long)a*b*c-0x1d21344f8479d61dLL?0:a;}
O por
fuente
2
7 ( -15485867, -1299721, -104287, 0, 104287, 1299721, 15485867).
Dennis
Eso fue rápido :)
Orby
2

Java - 245

Craqueado por Martin Büttner

int a(int[]_$){return $($($_(_$[0],0)))+$_(_$[1],1)*11+$($($_(_$[1+1],0)))*(1+1);}int $_(int $,int $_){int OO=0,o=1,O=1;for($=$<0?-$:$;++O*O<=$;OO+=$%O<1?O:0,o+=$%O<1?1:0,$/=$%O<1?O--:1);return $_>0?o:OO+$;}int $(int $){return(int)Math.sqrt($);}

Alimente la entrada como una matriz int: a(new int[]{1,2,3}) . No espero que dure 72 horas, pero diviértete con eso.

Aquí está con saltos de línea, para que sea un poco más legible:

int a(int[]_$){return $($($_(_$[0],0)))+$_(_$[1],
1)*11+$($($_(_$[1+1],0)))*(1+1);}int $_(int $,int
$_){int OO=0,o=1,O=1;for($=$<0?-$:$;++O*O<=$;OO+=
$%O<1?O:0,o+=$%O<1?1:0,$/=$%O<1?O--:1);return $_>
0?o:OO+$;}int $(int $){return(int)Math.sqrt($);}
Geobits
fuente
¿Solo por fuerza bruta ... 90?
Vectorizado el
@bitpwner No, lo siento.
Geobits
1
Me deobfuscated un poco: pastebin.com/8pvvfFYB (. Espero que no cometí ningún error, mientras que la sustitución de los nombres de variables)
Martin Ender
44
Bien, aquí está mi intento: ¿965?
Martin Ender
1
@ MartinBüttner Correcto. Gracias por la versión ofuscada: D
Geobits
1

Mathematica, 29 bytes, clave: 715, descifrado por Dennis

Esta es solo una versión fija de mi respuesta inicial, que no funcionó para entradas no positivas.

f=Plus@@Mod[NextPrime@#,240]&

Toma una lista de enteros como

f[{1,2,3}]
Martin Ender
fuente
Encontré 349resultados únicos. El rango era de 3a 717.
PhiNotPi
@PhiNotPi Incorrecto. (Lo comprobé dos veces)
Martin Ender
Bueno, encontré mi error y la respuesta correcta. Demasiado tarde sin embargo.
PhiNotPi
1
Si las cosas que ensamblé de la documentación de Mathematica y WolframAlpha son correctas, la clave es 715 ( 3 ... 717).
Dennis
2
Mathematica parece un lenguaje agradable, pero es demasiado caro o soy demasiado barato ...
Dennis
0

207 caracteres, en C / C ++, aún no ofuscados:

int x(int a, int b, int c) {
    int d, e, f;
    for (int i=0; i!=1<<31; ++i) {
        d=10*(b-a);
        e=a*(28-c)-b;
        f=a*b-2.7*c;
        a += d;
        b += e;
        c += f;
    }
    return ((a%5+5)*10+(b%5+5))*10+c%5+5;
}
ldgabbay
fuente
Solo estoy probando suerte ... 729.
Vectorizado el
@bitpwner Maldición, solo iba a decir eso. : D ... Si eso está mal, ese es el límite superior.
Martin Ender
2
Esta no es una presentación válida. Todas las asignaciones dentro del bucle pueden provocar un desbordamiento de enteros con signo , que tiene un comportamiento indefinido.
Dennis