El objetivo de este desafío es encontrar una implementación imposiblemente corta de la siguiente función p, en el idioma que elija. Aquí está el código C que lo implementa (vea este enlace TIO que también imprime sus resultados) y una página de Wikipedia que lo contiene.

unsigned char pi[] = {
    252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,
    233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,
    249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,
    5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,
    235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,
    181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,
    21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,
    50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,
    223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,
    224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,
    167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,
    173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,
    7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,
    225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,
    32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,
    89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182,
};

unsigned char p(unsigned char x) {
     return pi[x];
}

Que es `p`

pes un componente de dos estándares criptográficos rusos, a saber, la función hash Streebog y el cifrado de bloque Kuznyechik . En este artículo (y durante las reuniones de ISO), los diseñadores de estos algoritmos afirmaron que generaron la matriz piseleccionando permutaciones aleatorias de 8 bits.

Implementaciones "imposibles"

Hay permutaciones en 8 bits. Por lo tanto, para una permutación aleatoria dada, no se espera que un programa que la implemente necesite menos de 1683 bits. $256! \approx 2^{1684}$

Sin embargo, hemos encontrado múltiples implementaciones anormalmente pequeñas (que enumeramos aquí ), por ejemplo, el siguiente programa en C:

p(x){unsigned char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",l=0,b=17;while(--l&&x^1)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

que contiene solo 158 caracteres y, por lo tanto, cabe en 1264 bits. Haga clic aquí para ver que funciona.

Hablamos de una implementación corta "imposiblemente" porque, si la permutación fuera el resultado de un proceso aleatorio (como afirman sus diseñadores), entonces no existiría un programa tan corto (consulte esta página para obtener más detalles).

Implementación de referencia

Una versión más legible del código C anterior es:

unsigned char p(unsigned char x){
     unsigned char
         s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
         k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
     if(x != 0) {
         unsigned char l=1, a=2;
         while(a!=x) {
             a=(a<<1)^(a>>7)*29;
             l++;
         }
         unsigned char i = l % 17, j = l / 17;
         if (i != 0) return 252^k[i]^s[j];
         else return 252^k[j];
     }
     else return 252;
}

La tabla kes tal que k[x] = L(16-x), donde Les lineal en el sentido de que L(x^y)==L(x)^L(y), y donde, como en C, ^denota el XOR. Sin embargo, no logramos aprovechar esta propiedad para acortar nuestra implementación. No conocemos ninguna estructura sque pueda permitir una implementación más simple, aunque su salida siempre está en el subcampo, es decir donde la exponenciación se realiza en el campo finito. ¡Por supuesto, usted es absolutamente libre de usar una expresión más simple de si encuentra una! $s[x]^{16}=s[x]$ s

El ciclo while corresponde a la evaluación de un logaritmo discreto en el campo finito con 256 elementos. Funciona a través de una simple búsqueda de fuerza bruta: la variable ficticia aestá configurada para ser un generador del campo finito, y se multiplica por este generador hasta que el resultado sea igual a x. Cuando es el caso, tenemos que les el registro discreto de x. Esta función no está definida en 0, de ahí el caso especial correspondiente a la ifdeclaración.

La multiplicación por el generador puede verse como una multiplicación por en que luego se reduce el módulo del polinomio . El papel de la es garantizar que la variable permanezca en 8 bits. Alternativamente, podríamos usar , en cuyo caso podría ser un (o cualquier otro tipo de entero). Por otro lado, es necesario comenzar con lo que necesitamos tener cuando es igual a 1. $X$ $\mathbb{F}_2[X]$ $X^8+X^4+X^3+X^2+1$ unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

En nuestro documentop se presentan más detalles sobre las propiedades de , con un resumen de la mayoría de nuestras optimizaciones para obtener la implementación breve anterior.

Reglas

Proponga un programa que implemente la función pen menos de 1683 bits. Mientras más corto sea el programa, más anormal es, para un idioma dado, más corto es mejor. Si su idioma tiene Kuznyechik, Streebog o pcomo incorporado, no puede usarlos.

La métrica que usamos para determinar la mejor implementación es la longitud del programa en bytes. Usamos la longitud de bits en nuestro trabajo académico, pero nos quedamos con los bytes aquí por simplicidad.

Si su lenguaje no tiene una noción clara de función, argumento o salida, la codificación depende de usted para definir, pero trucos como codificar el valor pi[x]como xobviamente están prohibidos.

Ya hemos presentado un trabajo de investigación con nuestros hallazgos sobre este tema. Está disponible aquí . Sin embargo, si se publica en un lugar científico, con gusto reconoceremos a los autores de las mejores implementaciones.

Por cierto, ¡gracias a xnor por su ayuda al redactar esta pregunta!

code-golf math kolmogorov-complexity cryptography picarresursix
fuente

12

Espero que alguien envíe una respuesta en Seed.

Robin Ryder

66

Del mismo modo, ¿se puede calificar, por ejemplo, el código brainfuck a 3 bits por carácter si no tiene nops? ¿Y es la 1683 bits at mostrestricción estricta [sic?] O la meta?

alguien el

31

" Si la permutación fuera el resultado de un proceso aleatorio (como afirman sus diseñadores), entonces un programa tan corto no existiría " No estoy de acuerdo (aunque no importa para el desafío). Si fuera el resultado de un proceso aleatorio, sería poco probable que dicho programa existiera; o sería difícil de encontrar

Luis Mendo

8

@Grimy La afirmación de que un programa tan corto no existiría es conceptual (no de programación). Usando sus términos, pertenece al mundo de las matemáticas puras, no al mundo de la programación

Luis Mendo

77

Puede que ya se haya notado, pero por si acaso: da como resultado solo 8 valores distintos: (comenzando con y suponiendo ) .

s_{i} XOR s_{i - 1}

$s_i \text{ XOR } s_{i-1}$

1, 10, 68, 79, 146, 153, 220, 221

$1,10,68,79,146,153,220,221$

i = 1

$i=1$

s_{0} = 0

$s_0=0$

Arnauld

35

Conjunto AMD64 (78 bytes o 624 bits de código de máquina)

uint8_t SubByte (uint8_t x) {
    uint8_t y, z;
    uint8_t s [] =
      {1,221,146,79,147,153,11,68,214,215,78,220,152,10,69};

    uint8_t k [] =
      {0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};

    si (x) {
      para (y = z = 1; (y = (y << 1) ^ ((y >> 7) * 29))! = x; z ++);
      x = (z% 17);
      z = (z / 17);
      x = (x)? k [x] ^ s [z]: k [z];
    }
    retorno x ^ 252;
}

Conjunto x86 de 64 bits

    ; 78 bytes de ensamblaje AMD64
    ; odzhan
    bits 64

    % ifndef BIN
      SubBytex global
    %terminara si

SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    llamar a L0
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    pop rbx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc dl; z ++
    agregar al, al; y = y + y
    jnc $ + 4; omita XOR si no lleva
    xor al, 29;
    cmp al, cl; if (y! = x) pasa a L1
    jne L1    

    xchg eax, edx; eax = z
    cdq; edx = 0
    mov cl, 17; al = z / 17, dl = z% 17
    div ecx

    mov cl, [rbx + rax + 17]; cl = s [z]
    xlatb; al = k [z]
    prueba dl, dl; si (x == 0) pasa a L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2
    jubilado

Código de 64 bits desmontado

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 llamada qword 0x2a
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
0000002A 5B pop rbx
0000002B B001 mov al, 0x1
0000002D 99 cdq
0000002E FEC2 inc dl
00000030 00C0 add al, al
00000032 7302 jnc 0x36
00000034 341D xor al, 0x1d
00000036 38C8 cmp al, cl
00000038 75F4 jnz 0x2e
0000003A 92 xchg eax, edx
0000003B 99 cdq
0000003C B111 mov cl, 0x11
0000003E F7F1 div ecx
00000040 8A4C0311 mov cl, [rbx + rax + 0x11]
00000044 D7 xlatb
00000045 84D2 prueba dl, dl
00000047 7404 jz 0x4d
00000049 92 xchg eax, edx
0000004A D7 xlatb
0000004B 30C8 xor al, cl
0000004D C3 ret

Ensamblado x86 de 32 bits

    ; 72 bytes de ensamblaje x86
    ; odzhan
    bits 32

    % ifndef BIN
      SubBytex global
      global _SubBytex
    %terminara si

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    llamar a L0
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    pop ebx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc edx; z ++
    agregar al, al; y = y + y
    jnc $ + 4; omita XOR si no lleva
    xor al, 29;
    cmp al, cl; if (y! = x) pasa a L1
    jne L1    
    xchg eax, edx; al = z
    aam 17; al | x = z% 17, ah | z = z / 17
    mov cl, ah; cl = z
    cmove eax, ecx; si (x == 0) al = z más al = x
    xlatb; al = k [z] o k [x]
    jz L2; si (x == 0) pasa a L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2
    jubilado

Código de 32 bits desmontado

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 llamada dword 0x29
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
00000029 5B pop ebx
0000002A B001 mov al, 0x1
0000002C 99 cdq
0000002D 42 inc edx
0000002E 00C0 add al, al
00000030 7302 jnc 0x34
00000032 341D xor al, 0x1d
00000034 38C8 cmp al, cl
00000036 75F5 jnz 0x2d
00000038 92 xchg eax, edx
00000039 D411 aam 0x11
0000003B 88E1 mov cl, ah
0000003D 0F44C1 cmovz eax, ecx
00000040 D7 xlatb
00000041 7404 jz 0x47
00000043 32440B11 xor al, [ebx + ecx + 0x11]
00000047 C3 ret

odzhan
fuente

1

¡Buena respuesta! Como el OP buscaba un recuento de bits, este (85 bytes) llega a 680 bits , usando 8 bits por byte, o 595 bits usando 7 bits por byte (posible ya que todos los caracteres son ASCII). Probablemente podría acortarse si se comprime a un conjunto de caracteres aún más restrictivo.

Cullub

1

Bienvenido a PPCG; Buena primera solución.

Shaggy

99

@Cullub Mi punto fue que el código en esta respuesta es solo C / Assembler que se compila, por lo que el recuento de bytes no es el del código dado, sino el código compilado. Y eso no es ASCII.

ArBo

77

Solo para aclarar, ¿los 84 bytes son el tamaño del código de la máquina después de que se haya ensamblado? Si es así, el título debe actualizarse para reflejar que esta es una respuesta de código de máquina en lugar de una respuesta de ensamblaje.

Patata44

1

Y, por cierto, no tiene que usar una convención de llamadas estándar; puede usar una convención personalizada en la que RBX recibe llamadas, ahorrando 2 bytes para push / pop. (Y donde los uint8_targumentos son extendidos a cero a 64 bits para JRCXZ). Además, si escribe código dependiente de la posición, puede colocar la dirección de la tabla en un registro con 5 bytes en mov ebx, imm32lugar de 6 bytes call/ pop. O utilizarlo como disp32en mov al, [table + rax], pero que podría perder ya que tiene dos xlatby una movya. Sin embargo, el truco call + pop shellcode gana vs. LEA relativo a RIP de 7 bytes con los datos después del ret.

Peter Cordes

23

CJam ,72 67 66 63 bytes

ri{_2md142*^}es*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i

es* repite algo con la marca de tiempo actual, que es un gran número, y tardaría demasiado en terminar.

Versión realmente comprobable, 64 bytes:

ri{_2md142*^}256*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i

00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22dd 3024 2612 dc99 d644 0092 0b0a  2b".0$&....D....
00000030: 98d7 454f 934e 0122 2e2a 4c74 733a 5e69  ..EO.N.".*Lts:^i

Probar que un estándar criptográfico ruso está demasiado estructurado

Que es p

Implementaciones "imposibles"

Implementación de referencia

Reglas

Respuestas:

Conjunto AMD64 (78 bytes o 624 bits de código de máquina)

Conjunto x86 de 64 bits

Código de 64 bits desmontado

Ensamblado x86 de 32 bits

Código de 32 bits desmontado

CJam ,72 67 66 63 bytes

Explicación

Jalea 71 59 bytes

Explicación

Enfoque original

Gelatina , 71 66 bytes

Explicación

C (gcc) , 157148140139 bytes

C (gcc) , 150 142 127 126 bytes

05AB1E , 101 100 98 97 95 94 bytes

Stax , 65 64 62 59 58 bytes

Python 3 , 151 bytes

JavaScript (ES6), 139 bytes

JavaScript (Node.js) , 149 148 bytes

Codificación

sss

C # (compilador interactivo de Visual C #) , 141 bytes

Python 3 , 182 bytes

Python 3 , 176 bytes

Python 3 , 173 bytes

Rust , 170 163 bytes

05AB1E , 74 bytes

Que es `p`

$s$