El reto
Un simple desafío "espía versus espía".
Escriba un programa con las siguientes especificaciones:
- El programa puede estar escrito en cualquier idioma pero no debe exceder los 512 caracteres (como se representa en un bloque de código en este sitio).
- El programa debe aceptar 5 enteros de 32 bits con signo como entradas. Puede tomar la forma de una función que acepta 5 argumentos, una función que acepta una sola matriz de 5 elementos o un programa completo que lee 5 enteros de cualquier entrada estándar.
- El programa debe generar un entero de 32 bits con signo.
- El programa debe devolver 1 si y solo si las cinco entradas, interpretadas como una secuencia, coinciden con una secuencia aritmética específica de la elección del programador, llamada "clave". La función debe devolver 0 para todas las demás entradas.
Una secuencia aritmética tiene la propiedad de que cada elemento sucesivo de la secuencia es igual a su predecesor más alguna constante fija a
.
Por ejemplo, 25 30 35 40 45
es una secuencia aritmética ya que cada elemento de la secuencia es igual a su predecesor más 5. Asimismo, 17 10 3 -4 -11
es una secuencia aritmética ya que cada elemento es igual a su precesor más -7.
Las secuencias 1 2 4 8 16
y 3 9 15 6 12
no son secuencias aritméticas.
Una clave puede ser cualquier secuencia aritmética que elija, con la única restricción de que no se permiten secuencias que impliquen desbordamiento de enteros. Es decir, la secuencia debe ser estrictamente creciente, estrictamente decreciente o tener todos los elementos iguales.
Como ejemplo, suponga que elige la clave 98021 93880 89739 85598 81457
. Su programa debe devolver 1 si las entradas (en secuencia) coinciden con estos cinco números, y 0 en caso contrario.
Tenga en cuenta que los medios para proteger la clave deben ser de su propio diseño novedoso. Además, las soluciones probabilísticas que pueden devolver falsos positivos con cualquier probabilidad distinta de cero no están permitidas. En particular, no utilice ningún hash criptográfico estándar, incluidas las funciones de biblioteca para los hashes criptográficos estándar.
La puntuación
Los envíos más cortos sin descifrar por conteo de personajes serán declarados 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 propios programas, 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.
Consulte "Descargo de responsabilidad" a continuación para obtener detalles sobre la política actualizada de puntaje de craqueo.
Las presentaciones agrietadas se eliminan de la contienda (siempre que no sean "seguras"). No deben ser editados. Si un lector desea enviar un nuevo programa, debe hacerlo en una respuesta por separado.
Los cracker (s) con los puntajes más altos serán declarados ganadores junto con los desarrolladores de los programas ganadores.
Por favor no descifre su propia presentación.
La mejor de las suertes. :)
Tabla de clasificación
Penúltima clasificación (pendiente de seguridad de la presentación de Dennis CJam 49).
Armarios seguros
- CJam 49, Dennis
- CJam 62, Dennis seguro
- CJam 91, Dennis seguro
- Python 156, caja fuerte de Maarten Baert
- Perl 256, chilemagic safe
- Java 468, Geobits seguro
Galletas Imparables
- Peter Taylor [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Dennis [Pyth 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
- Martin Büttner [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
- Tyilo [C 459, Javascript 958 *]
- Freddieknets [Mathematica 67 *]
- Ilmari Karonen [Python27 182 *]
- nitroso [C 212 *]
* envío no conforme
Descargo de responsabilidad (actualizado a las 11:15 PM EST, 26 de agosto)
Con los problemas de puntuación llegando finalmente a la masa crítica (dado que dos tercios de los envíos descifrados no cumplen hasta ahora), clasifiqué a los mejores crackers en términos de número de envíos craqueados (primarios) y número total de caracteres en envíos crackeados compatibles (secundario).
Como antes, las presentaciones exactas quebradas, la duración de las presentaciones y su estado de cumplimiento / no cumplimiento están todos marcados para que los lectores puedan inferir sus propias clasificaciones si creen que las nuevas clasificaciones oficiales son injustas.
Mis disculpas por enmendar las reglas tan tarde en el juego.
Respuestas:
CJam, 62 caracteres
Stack Exchange es propenso a enviar caracteres no imprimibles, pero copiar el código de esta pasta y pegarlo en el intérprete de CJam funciona bien para mí.
Cómo funciona
Después de reemplazar la cadena Unicode con una cadena ASCII, se ejecuta el siguiente código:
Este enfoque utiliza Bivium-B (consulte Análisis algebraico de cifrados similares a Trivium ), una versión debilitada del cifrado de flujo Trivium .
El programa usa la secuencia de enteros como estado inicial, actualiza el estado 434 veces (354 rondas logran una difusión completa) y genera 177 bits de salida, que se compara con los de la secuencia correcta.
Dado que el tamaño del estado es precisamente 177 bits, esto debería ser suficiente para identificar de forma exclusiva el estado inicial.
Ejecución de ejemplo
fuente
CJam, 91 caracteres
Stack Exchange es propenso a enviar caracteres no imprimibles, pero copiar el código de esta pasta y pegarlo en el intérprete de CJam funciona bien para mí.
Cómo funciona
Después de reemplazar la cadena Unicode con enteros (considerando los dígitos de los caracteres de los números base 65533), se ejecuta el siguiente código:
Dado que 13 es coprimo al totient del módulo (el totient es secreto, por lo que solo tendrá que confiar en mí), diferentes bases generarán diferentes resultados, es decir, la solución es única.
A menos que alguien pueda explotar el pequeño exponente (13), la forma más eficiente de romper este bloqueo es factorizar el módulo (ver problema RSA ). Elegí un número entero de 512 bits para el módulo, que debería soportar 72 horas de intentos de factorización.
Ejecución de ejemplo
fuente
found 1740001 rational and 1739328 algebraic entries
; Han pasado casi 100 horas para procesarlos e informessieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Probemos este:
(Se espera que el usuario ingrese 5 números separados por comas, por ejemplo
1,2,3,4,5
).fuente
32416190039,32416190047,32416190055,32416190063,32416190071
Java: 468
La entrada se da como
k(int[5])
. Fianzas anticipadas si no están espaciadas uniformemente. De lo contrario, lleva un tiempo descubrir si los diez hashes son correctos. Para números grandes, "un poco" puede significar diez segundos o más, por lo que puede disuadir a los crackers.fuente
Java: 342
Aquí hay un casillero basado en cadenas que depende tanto del recuento de caracteres de entrada como de la entrada específica. La secuencia podría basarse en oscuras referencias de la cultura pop. ¡Que te diviertas!
Un poco ignorante:
fuente
-8675309
, delta es5551212
.Pitón, 147
Editar: versión más corta basada en el comentario de Dennis. También actualicé la secuencia para evitar filtrar información.
Basado en el problema de logaritmo discreto que se cree que es indescifrable, sin embargo, el principal que estoy usando es probablemente demasiado pequeño para ser seguro (y puede tener otros problemas, no lo sé). Y puede hacerlo por fuerza bruta, por supuesto, ya que las únicas incógnitas son dos enteros de 32 bits.
fuente
c=1
, calculandoc=(c<<32)+d
y cambiando la constante en consecuencia.Javascript 125
Este debería resolverse bastante rápido. Seguiré con algo más fuerte.
fuente
0, 3913, 7826, 11739, 15652
Rubí, 175
A diferencia del uso de un hash criptográfico o
srand
, esto es demostrablemente único (que es una pequeña pista). Toma cinco números a través de STDIN, delimitados por cualquier carácter o caracteres que no sean dígitos ni líneas nuevas. Salidas a STDOUT.fuente
622238809,1397646693,2173054577,2948462461,3723870345
(mi suposición anterior tuvo un error, pero este está probado). Sin embargo, no creo que esto sea válido, porque el último número no cabe en un entero de 32 bits con signo.GolfScript (116 caracteres)
Toma la entrada como enteros separados por espacios.
fuente
-51469355 -37912886 -24356417 -10799948 2756521
C 459 bytes
RESUELTO POR Tyilo - LEER EDITAR A CONTINUACIÓN
Necesitamos a alguien para escribir una solución C, ¿no? No estoy impresionando a nadie con la longitud, no soy golfista. ¡Sin embargo, espero que sea un desafío interesante!
¡No creo que haya una manera obvia de descifrar este, y espero con impaciencia todos los intentos! Sé que esta solución es única. Ofuscación muy mínima, principalmente para cumplir con los requisitos de longitud. Esto se puede probar simplemente:
PD: Hay un significado para
a[0]
como un número en sí mismo, ¡y me gustaría ver a alguien señalarlo en los comentarios!EDITAR:
Solución:
6174, 48216, 90258, 132300, 174342
Una nota sobre grietas:
Si bien este no es el método utilizado (ver los comentarios), descubrí mi propio cifrado con una fuerza bruta muy fácil. Ahora entiendo que es de vital importancia hacer que los números sean grandes. El siguiente código puede descifrar cualquier cifrado donde
upper_bound
sea un límite superior conocidoa[0] + a[1] + a[2] + a[3] + a[4]
. El límite superior en el cifrado anterior es457464
, que se puede derivar del sistema de ecuacionesb[]
y algunos detalles del algoritmo. Se puede demostrar esob[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.Con
a[0] = 6174
esto, este ciclo rompió mi trabajo en poco menos de un minuto.fuente
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Corriendo:
Probablemente bastante fácil de descifrar, también podría tener múltiples soluciones.
Actualización: Golf mejorado al hacer lo que Martin Büttner sugirió. La funcionalidad de la función y la clave no ha cambiado.
fuente
{58871,5592,-47687,-100966,-154245}
NextPrime
podría devolver valores negativos. ¿Cómo lo encontraste?Python27,
283182Muy bien, tengo mucha confianza en mi casillero, sin embargo, es bastante largo ya que agregué cálculos 'difíciles de revertir' a la entrada, para hacerlo bien, difícil de revertir.
editar: Gracias a colevk por seguir jugando al golf. Durante la edición me di cuenta de que había un error y un defecto en mi algoritmo, tal vez tendré mejor suerte la próxima vez.
fuente
121174841 121174871 121174901 121174931 121174961
funciona, pero solo si la lista[1,3,5,7]
de la línea 7 se reemplaza por[1,3,5,7,11]
.Mathematica
142146EDITAR : la clave no era única, agregó 4 caracteres, ahora lo es.
(Se agregaron espacios y líneas nuevas para facilitar la lectura, no se cuentan ni se necesitan).
Uso:
fuente
256208
, delta-5
.IntegerDigits
y luego factorizar para obtener candidatos para el término inicial y el delta.NextPrime
; si lo variamos por más o menos uno, al menos uno de ellos dará el mismo primo siguiente.Craqueado por @Dennis en 2 horas
Solo una simple para comenzar, espero que esto se resuelva rápidamente.
Pyth , 13
Toma entradas separadas por comas en STDIN.
Ejecútelo así (-c significa tomar el programa como argumento de línea de comando):
Se arregló el programa: no había entendido la especificación.
Este lenguaje puede ser demasiado esotérico para esta competencia. Si OP lo cree, lo eliminaré.
fuente
1,2,3,4,5
es la clave?97,96,95,94,93
(Acabo de matar mi puntuación de craqueo.)Lua 105
Sospecho que no pasará mucho tiempo antes de que se rompa, pero aquí vamos:
(espacios agregados para mayor claridad, pero no son parte del conteo)
fuente
3, 7, 11, 15, 19
o6, 14, 22, 30, 38
t1==0
cuando sea queS
esté aumentando. Además, ambas condiciones son homogéneas; siS
es una solución, también lo eskS
.Perl - 256
Tuve que poner mucha lógica de manejo de errores y esto definitivamente se puede reducir mucho más. Imprimirá un
1
cuando obtenga los cinco números correctos. Con suerte, imprimirá un0
para todo lo demás (puede haber errores o nada, no lo sé). Si alguien quiere ayudar a mejorar el código o jugarlo más, ¡no dude en ayudar!Llamar con:
fuente
Rubí - 130
Basado en el registro de desplazamiento de retroalimentación lineal. Entradas por argumentos de línea de comando.
Debe ser único en función de la naturaleza de los LFSR. Pista: ascendente y todo positivo.
Dará más pistas si nadie lo resuelve pronto.
fuente
Rubí, 249
Debe ser divertido. ¿Quién necesita las matemáticas?
fuente
309, 77347, 154385, 231423, 308461
Pero no creo que sea único.103, 232041, 463979, 695917, 927855
y3, 7966741, 15933479, 23900217, 31866955
. Y estoy bastante seguro de que hay otras expresiones regulares válidas mediante el uso de+
s adicionales .()
o similar.CJam, 49 caracteres
Pruébalo en línea.
Cómo funciona
El resultado será 1 si y solo si el segundo entero es un factor del primero, que es un producto de dos números primos: uno correspondiente a la secuencia secreta y otro que no corresponde a ninguna secuencia válida. Por lo tanto, la solución es única.
Factorizar un número entero de 512 bits no es que difícil, pero espero que nadie será capaz de 72 horas. Mi versión anterior con un entero de 320 bits se ha roto .
Ejecución de ejemplo
fuente
Javascript 958
Convierte las entradas en varios tipos de datos y realiza algunas manipulaciones relevantes para cada tipo de datos en el camino. Debería revertirse con bastante facilidad para cualquiera que se tome el tiempo.
fuente
320689, 444121, 567553, 690985, 814417
C, 239 (agrietado por Dennis)
Ve aqui para mi envío actualizado.
Probablemente podría jugar al golf un poco más a fondo. Es cierto que no me he tomado el tiempo para demostrar que la clave es única (probablemente no lo sea), pero definitivamente está en el orden de una colisión de hash. Si lo rompes, comparte tu método :)
fuente
0 0 0 0 0
?C, 212 por Orby - Agrietado
https://codegolf.stackexchange.com/a/36810/31064 por Orby tiene al menos dos claves:
Orby preguntó por el método que usé para descifrarlo. La función p verifica si x es primo al verificar
x%i==0
todo i entre 2 y x (aunque usando en(x/i)*i==x
lugar dex%i==0
) y devuelve verdadero si x es un número primo. La función f verifica que todos a, b, c, dye sean primos. También verifica si el número m, una concatenación de las representaciones decimales de e, d, c, by a (en ese orden), es primo. La clave es tal que a, b, c, d, e y m son primos.Green y Tao (2004) muestran que existen infinitas secuencias aritméticas de primos para cualquier longitud k, por lo que solo necesitamos buscar estas secuencias que también satisfacen que m sea primo. Al tomar mucho tiempo como limitado por -9.223372037e + 18 y 9.223372037e + 18, sabemos que para que la cadena concatenada encaje en un largo largo, los números tienen un límite superior de 9999. Entonces, al usar un script de Python para generar todos secuencias aritméticas dentro de todos los primos <10000 y luego verificando si su concatenación inversa es un primo, podemos encontrar muchas soluciones posibles.
Por alguna razón se me ocurrieron falsos positivos, pero los dos anteriores son válidos según el programa. Además, puede haber soluciones donde e es negativo y el resto es positivo (p usa el módulo de x), pero no busqué esas.
Las claves que proporcioné son todas secuencias aritméticas, pero el script de Orby no parece requerir que las entradas sean una secuencia aritmética, por lo que también puede haber claves no válidas.
fuente
MATLAB: aparentemente inválido
Muy simple, solo tienes que generar el número aleatorio correcto.
Todavía puede fallar, pero eso no debería ser un problema.
fuente
MATLAB (con caja de herramientas simbólica), 173 caracteres
Esta no es una entrada oficial y no contará para el puntaje de craqueo de nadie, pero le otorgará derechos de fanfarronear. ;)
La caja de herramientas simbólica solo es necesaria para manejar la resta de enteros grandes.
La fuerza bruta debe ser un perro, pero si está familiarizado con la serie que implica, la solución es trivial.
fuente
Pitón 2 (91)Editar: Esto no está permitido porque el argumento para la unicidad es probabilístico. Me doy por vencido.
Toma listas de enteros como entrada, como
[1,2,3,4,5]
.El bucle está destinado a operar en las entradas de una manera molesta, dejando una torre de sumas y exponentes. La idea es como un registro discreto, pero con complicación complicada en lugar de simplicidad matemática. Tal vez la composición del módulo es una vulnerabilidad, en cuyo caso podría hacer algo así
7**58+8
.Realmente no sé cómo probaría que mi clave es la única, pero el rango de salidas es al menos 10 veces mayor que el rango de entradas, ¿entonces probablemente? Aunque tal vez solo se pueda lograr una pequeña fracción de los posibles resultados. Siempre podría aumentar el número de dígitos a costa de los caracteres. Te dejaré a ti decidir qué es justo.
Feliz cracking
fuente
Mathematica - 72
Versión 2 de mi script, con la misma clave que la destinada para mi versión 1.
Básicamente, esto elimina los números primos negativos para
NextPrime
.Corriendo:
fuente
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 caracteres
Ingrese los números como
1,2,3,4,5
.fuente
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
no es un número de 32 bits.Python, 78
(Agrietado por Tyilo en 14 minutos)
¡Divertido!
De acuerdo, no se muestra correctamente aquí :(
Espera una lista de cinco números, por ejemplo. [1,2,3,4,5]
fuente
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 caracteres (rotos)
Pruébalo en línea.
Cómo funciona
Mira mi nueva respuesta.
Ejecución de ejemplo
fuente
737262825 208413108 3974530688 3445680972 2916831257
funciona pero no es una progresión aritmética. Factorizado en 3 horas 20 minutos. Aparentemente, los números de 512 bits eran factibles en 72 horas por $ 75 en EC2 hace dos años, por lo que creo que hubiera sido seguro.737262825 208413109 -320436607 -849286323 -1378136039
C, 212 (agrietado)
Esta es la misma idea que mi presentación anterior , golfé más a fondo, con un error corregido que pasó 0,0,0,0,0 (Gracias a Dennis por señalar el error). Compilar con -std = c99.
fuente
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37