Le but de ce défi est de trouver une implémentation incroyablement courte de la fonction suivante p, dans le langage de votre choix. Voici le code C l’implémentant (voir ce lien TIO qui affiche également ses sorties) et une page wikipedia le contenant.

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

Quel est `p`

pest un composant de deux standards cryptographiques russes, à savoir la fonction de hachage Streebog et le chiffrement de bloc Kuznyechik . Dans cet article (et lors des réunions ISO), les concepteurs de ces algorithmes ont affirmé avoir généré le tableau pien choisissant des permutations aléatoires de 8 bits.

Implémentations "impossibles"

Il y en a permutations sur 8 bits. Par conséquent, pour une permutation aléatoire donnée, un programme qui l'implémente ne doit pas nécessiter moins de 1683 bits. $256! \approx 2^{1684}$

Cependant, nous avons trouvé plusieurs implémentations anormalement petites (que nous énumérons ici ), par exemple le programme C suivant:

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

qui ne contient que 158 caractères et tient donc dans 1264 bits. Cliquez ici pour voir que cela fonctionne.

Nous parlons d'une implémentation courte "impossible" parce que, si la permutation était la sortie d'un processus aléatoire (comme l'affirment ses concepteurs), un programme de cette durée n'existerait pas (voir cette page pour plus de détails).

Mise en oeuvre de référence

Une version plus lisible du code C précédent est:

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

Le tableau kest tel que k[x] = L(16-x), où Lest linéaire en ce sens L(x^y)==L(x)^L(y)et où, comme en C, ^désigne le XOR. Cependant, nous n'avons pas réussi à tirer parti de cette propriété pour raccourcir notre mise en œuvre. Nous ne connaissons aucune structure squi pourrait permettre une implémentation plus simple - sa sortie est toujours dans le sous-champ, c.-à- où l’exponentiation est effectuée dans le champ fini. Bien sûr, vous êtes absolument libre d'utiliser une expression plus simple de si vous en trouvez une! $s[x]^{16}=s[x]$ s

La boucle while correspond à l'évaluation d'un logarithme discret dans le corps fini à 256 éléments. Cela fonctionne via une recherche simple par force brute: la variable factice aest définie pour être un générateur du corps fini, et elle est multipliée par ce générateur jusqu'à ce que le résultat soit égal à x. Quand c'est le cas, nous avons c'est lle journal discret de x. Cette fonction n'est pas définie à 0, d'où le cas particulier correspondant à l' ifinstruction.

La multiplication par le générateur peut être vue comme une multiplication par dans qui est alors réduite modulo le polynôme . Le rôle de l ' est de s'assurer que la variable reste sur 8 bits. Alternativement, nous pourrions utiliser , auquel cas ce pourrait être un type (ou tout autre type entier). D'autre part, il est nécessaire de commencer par ce que nous devons avoir quand est égal à 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

Plus de détails sur les propriétés de psont présentés dans notre article , avec un résumé de la plupart de nos optimisations pour obtenir la mise en œuvre courte précédente.

Règles

Proposez un programme qui implémente la fonction pen moins de 1683 bits. Plus le programme est court, plus il est anormal, pour une langue donnée, plus c'est court, mieux c'est. Si votre langue est Kuznyechik, Streebog ou pintégrée, vous ne pouvez pas les utiliser.

La métrique que nous utilisons pour déterminer la meilleure implémentation est la longueur du programme en octets. Nous utilisons la longueur de bit dans notre article académique, mais nous nous en tenons aux octets pour des raisons de simplicité.

Si votre langue ne dispose pas d' une notion claire de la fonction, l' argument ou de sortie, le codage est à vous de définir, mais des trucs comme codant pour la valeur pi[x]que xsont évidemment interdites.

Nous avons déjà soumis un document de recherche contenant nos conclusions sur ce sujet. Il est disponible ici . Toutefois, s’il est publié dans un lieu scientifique, nous nous ferons un plaisir de reconnaître les auteurs des meilleures implémentations.

En passant, merci à xnor pour son aide lors de la rédaction de cette question!

code-golf math kolmogorov-complexity cryptography picarresursix
la source

12

J'espère que quelqu'un soumet une réponse dans Seed.

Robin Ryder le

6

De même, un code brainfuck, par exemple, peut-il être noté à 3 bits par caractère s'il n'a pas de nops? Et est-ce 1683 bits at mostune restriction stricte [sic?] Ou un objectif?

quelqu'un

31

" Si la permutation était le résultat d'un processus aléatoire (comme le prétendent ses concepteurs), alors un programme aussi court n'existerait pas ". Je ne suis pas d'accord (même si cela n'a pas d'importance pour le défi). S'il s'agissait d'un processus aléatoire, il serait peu probable qu'un tel programme existe; ou il serait difficile à trouver

Luis Mendo

8

@Grimy L'affirmation qu'un programme de ce court-circuit n'existerait pas est un programme conceptuel (et non un programme). Selon vos termes, il appartient au monde des mathématiques pures, pas au monde de la programmation

Luis Mendo

7

Cela a peut-être déjà été remarqué, mais juste au cas où: donne que 8 valeurs distinctes: (commençant par et supposant que ) .

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 le

35

Assemblage AMD64 (78 octets ou 624 bits de code machine)

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) {
      pour (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];
    }
    retour x ^ 252;
}

Assemblage x86 64 bits

    ; 78 octets d'assemblage AMD64
    ; Odzhan
    bits 64

    % ifndef BIN
      SubBytex global
    %fin si

SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    appelez 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 ++
    ajouter al, al; y = y + y
    jnc $ + 4; sauter XOR si aucun report
    xor al, 29;
    cmp al, cl; si (y! = x) passez à 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]
    test dl, dl; si (x == 0) passe à L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    ret

Code 64 bits désassemblé

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 appel 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 test dl, dl
00000047 7404 jz 0x4d
00000049 92 xchg eax, edx
0000004A D7 xlatb
0000004B 30C8 xor al, cl
0000004D C3 ret

Assemblage 32 bits x86

    ; 72 octets d'assemblage x86
    ; Odzhan
    bits 32

    % ifndef BIN
      SubBytex global
      global _SubBytex
    %fin si

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    appelez 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 ++
    ajouter al, al; y = y + y
    jnc $ + 4; sauter XOR si aucun report
    xor al, 29;
    cmp al, cl; si (y! = x) passez à 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 sinon al = x
    xlatb; al = k [z] ou k [x]
    jz L2; si (x == 0) passe à L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    ret

Code 32 bits désassemblé

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 appel 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
la source

1

Bonne réponse! Comme l'OP recherchait le nombre de bits, ce nombre (85 octets) s'élevait à 680 bits , en utilisant 8 bits par octet, ou 595 bits en utilisant 7 bits par octet (possible, tous les caractères étant en ASCII). Vous pourriez probablement aller plus vite si vous comprimiez un jeu de caractères encore plus restrictif.

Cullub

1

Bienvenue chez PPCG; belle première solution.

Shaggy

9

@ Cullub Mon point était que le code dans cette réponse est juste le C / Assembler qui est compilé, donc le nombre d'octets n'est pas celui du code donné, mais celui du code compilé. Et ce n'est pas ASCII.

ArBo

7

Juste pour clarifier, les 84 octets sont la taille du code machine une fois celui-ci assemblé? Si tel est le cas, le titre devrait être mis à jour pour indiquer qu'il s'agit d'une réponse de code machine plutôt que d'une réponse d'ensemble.

Potato44

1

Et BTW, vous n’avez pas à utiliser une convention d’appel standard; vous pouvez utiliser une convention personnalisée selon laquelle RBX est codé en appels, ce qui permet d'économiser 2 octets pour les transferts. (Et où les uint8_targuments sont étendus à 64 bits pour JRCXZ). De plus, si vous écrivez un code dépendant de la position, vous pouvez mettre l'adresse de la table dans un registre avec un 5 octets mov ebx, imm32au lieu d'un 6 octets call/ pop. Ou utilisez-le comme un disp32dans mov al, [table + rax], mais cela pourrait perdre puisque vous avez déjà deux xlatbet un mov. Le piège call + pop shellcode l'emporte sur le LEA relatif relatif au RIP sur 7 octets avec les données qui suivent ret.

Peter Cordes Le

23

CJam ,72 67 66 63 octets

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

es* répète quelque chose en fonction de l'horodatage actuel, ce qui est un grand nombre, et cela prendrait trop de temps.

Version actuellement testable, 64 octets:

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

Prouver qu'une norme cryptographique russe est trop structurée

Quel est p

Implémentations "impossibles"

Mise en oeuvre de référence

Règles

Réponses:

Assemblage AMD64 (78 octets ou 624 bits de code machine)

Assemblage x86 64 bits

Code 64 bits désassemblé

Assemblage 32 bits x86

Code 32 bits désassemblé

CJam ,72 67 66 63 octets

Explication

Gelée 71 59 octets

Explication

Approche originale

Gelée , 71 à 66 octets

Explication

C (gcc) , 157 148 140 139 octets

C (gcc) , 150 142 127 126 octets

05AB1E , 101 100 98 97 95 94 octets

Stax , 65 64 62 59 58 octets

Python 3 , 151 octets

JavaScript (ES6), 139 octets

JavaScript (Node.js) , 149 148 octets

Codage

Bâtimentsss

C # (compilateur interactif Visual C #) , 141 octets

Python 3 , 182 octets

Python 3 , 176 octets

Python 3 , 173 octets

Rouille , 170 163 octets

05AB1E , 74 octets

Quel est `p`

Bâtiment $s$