Das Ziel dieser Herausforderung ist es, eine unglaublich kurze Implementierung der folgenden Funktion pin der Sprache Ihrer Wahl zu finden. Hier ist C-Code, der es implementiert (siehe diesen TIO-Link , der auch seine Ausgaben druckt) und eine Wikipedia-Seite, die es enthält.

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

Was ist `p`

pist Bestandteil zweier russischer kryptographischer Standards, nämlich der Hash-Funktion Streebog und der Blockchiffre Kuznyechik . In diesem Artikel (und während ISO-Meetings) behaupteten die Entwickler dieser Algorithmen, dass sie das Array pidurch Auswahl zufälliger 8-Bit-Permutationen generierten .

"Unmögliche" Implementierungen

Es gibt Permutationen auf 8 Bits. Für eine gegebene zufällige Permutation wird daher nicht erwartet, dass ein Programm, das sie implementiert, weniger als 1683 Bits benötigt. $256! \approx 2^{1684}$

Wir haben jedoch mehrere ungewöhnlich kleine Implementierungen gefunden (die wir hier auflisten ), zum Beispiel das folgende C-Programm:

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

die nur 158 Zeichen enthält und somit in 1264 Bit passt. Klicken Sie hier, um zu sehen, dass es funktioniert.

Wir sprechen von einer "unmöglich" kurzen Implementierung, da, wenn die Permutation die Ausgabe eines zufälligen Prozesses wäre (wie von seinen Designern behauptet), ein Programm dieser kurzen Art nicht existieren würde (siehe diese Seite für weitere Details).

Referenzimplementierung

Eine besser lesbare Version des vorherigen C-Codes ist:

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

Die Tabelle kist so, dass k[x] = L(16-x), wo Lin dem Sinne linear ist L(x^y)==L(x)^L(y), und wo, wie in C, ^das XOR bezeichnet. Es ist uns jedoch nicht gelungen, diese Eigenschaft zu nutzen, um unsere Implementierung zu verkürzen. Wir kennen keine Struktur s, die eine einfachere Implementierung ermöglichen könnte - ihre Ausgabe befindet sich jedoch immer im Unterfeld, dh wobei die Exponentiation im endlichen Feld erfolgt. Natürlich steht es Ihnen frei, einen einfacheren Ausdruck zu verwenden, falls Sie einen finden sollten! $s[x]^{16}=s[x]$ s

Die while-Schleife entspricht der Auswertung eines diskreten Logarithmus im endlichen Feld mit 256 Elementen. Es funktioniert über eine einfache Brute-Force-Suche: Die Dummy-Variable awird als Generator des endlichen Feldes festgelegt und mit diesem Generator multipliziert, bis das Ergebnis gleich ist x. Wenn dies der Fall ist, haben wir ldas diskrete Protokoll von x. Diese Funktion ist nicht in 0 definiert, daher der der ifAnweisung entsprechende Sonderfall .

Die Multiplikation mit dem Generator kann als Multiplikation mit in die dann modulo des Polynoms reduziert wird . Die Aufgabe von ist es sicherzustellen, dass die Variable auf 8 Bits bleibt. Alternativ könnten wir verwenden , in welchem Fall ein (oder ein anderer ganzzahliger) Typ sein könnte. Auf der anderen Seite ist es notwendig, mit zu beginnen, da wir haben müssen, wann gleich 1 ist. $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

Weitere Details zu den Eigenschaften von pfinden Sie in unserem Artikel, in dem die meisten Optimierungen beschrieben werden, um die vorherige kurze Implementierung zu erhalten.

Regeln

Schlagen Sie ein Programm vor, das die Funktion pin weniger als 1683 Bit implementiert . Je kürzer das Programm ist, desto anormaler ist es, je kürzer die Sprache ist, desto besser. Wenn Ihre Sprache Kuznyechik, Streebog oder pein eingebautes hat, können Sie sie nicht verwenden.

Die Metrik, mit der wir die beste Implementierung ermitteln, ist die Programmlänge in Byte. Wir verwenden die Bitlänge in unserer wissenschaftlichen Arbeit, aber der Einfachheit halber halten wir uns hier an Bytes.

Wenn Ihre Sprache nicht über eine klare Vorstellung von Funktion, Argument oder Ausgang, ist die Codierung an Ihnen zu definieren, aber Tricks wie kodieren den Wert pi[x]als xoffensichtlich verboten.

Wir haben bereits ein Forschungspapier mit unseren Ergebnissen zu diesem Thema eingereicht. Es ist hier erhältlich . Sollte es jedoch an einem wissenschaftlichen Ort veröffentlicht werden, werden wir gerne die Autoren der besten Implementierungen auszeichnen.

Übrigens, danke an xnor für seine Hilfe beim Verfassen dieser Frage!

code-golf math kolmogorov-complexity cryptography picarresursix
quelle

12

Ich hoffe jemand gibt eine Antwort in Seed.

Robin Ryder

6

Kann Brainfuck-Code zum Beispiel mit 3 Bits pro Zeichen bewertet werden, wenn er keine Nops hat? Und ist das 1683 bits at mosteine strenge Einschränkung oder das Ziel?

Jemand

31

" Wenn die Permutation die Ausgabe eines zufälligen Prozesses wäre (wie von seinen Designern behauptet), gäbe es kein so kurzes Programm ", widerspreche ich (obwohl es für die Herausforderung keine Rolle spielt). Wenn es sich um die Ausgabe eines zufälligen Prozesses handeln würde, wäre es unwahrscheinlich, dass ein solches Programm existiert. oder es wäre schwer zu finden

Luis Mendo

8

@Grimy Die Aussage, dass ein Programm, das so kurz wäre, nicht existieren würde, ist eine konzeptionelle (keine programmierende). Mit Ihren Begriffen gehört es zur Welt der reinen Mathematik, nicht zur Programmierwelt

Luis Mendo,

7

Es wurde möglicherweise bereits bemerkt, aber nur für den Fall: ergibt nur 8 verschiedene Werte: (beginnend mit und unter der Annahme von ) .

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

AMD64-Assembly (78 Byte oder 624 Bit Maschinencode)

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

    if (x) {
      für (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];
    }
    return x ^ 252;
}

64-Bit x86-Assembly

    ; 78 Bytes AMD64-Assembly
    ; odzhan
    Bits 64

    % ifndef BIN
      globaler SubBytex
    % endif

SubBytex:
    mov al, 252
    jecxz L2; if (x) {
    rufe L0 an
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 ++
    add al, al; y = y + y
    jnc $ + 4; XOR überspringen, wenn kein Übertrag vorhanden ist
    xor al, 29;
    cmp al, cl; if (y! = x) gehe zu 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; if (x == 0) gehe zu L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    ret

Zerlegter 64-Bit-Code

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 qword 0x2a aufrufen
; 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

32-Bit-x86-Assembly

    ; 72 Byte x86-Assembly
    ; odzhan
    Bits 32

    % ifndef BIN
      globaler SubBytex
      global _SubBytex
    % endif

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; if (x) {
    rufe L0 an
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 ++
    add al, al; y = y + y
    jnc $ + 4; XOR überspringen, wenn kein Übertrag vorhanden ist
    xor al, 29;
    cmp al, cl; if (y! = x) gehe zu 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; if (x == 0) al = z else al = x
    xlatb; al = k [z] oder k [x]
    jz L2; if (x == 0) gehe zu L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    ret

Zerlegter 32-Bit-Code

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 dword 0x29 aufrufen
; 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
quelle

1

Gute Antwort! Da das OP nach der Anzahl der Bits gesucht hat, ergibt dies (85 Byte) 680 Bit , wobei 8 Bit pro Byte verwendet werden, oder 595 Bit, wobei 7 Bit pro Byte verwendet werden (möglich, da alle Zeichen ASCII-Zeichen sind). Sie könnten wahrscheinlich kürzer werden, wenn Sie auf einen noch restriktiveren Zeichensatz komprimiert würden.

Cullub

1

Willkommen bei PPCG; schöne erste lösung.

Shaggy

9

@Cullub Mein Punkt war, dass der Code in dieser Antwort nur C / Assembler ist, der kompiliert wird, daher ist die Byteanzahl nicht die des angegebenen Codes, sondern des kompilierten Codes. Und das ist kein ASCII.

ArBo

7

Nur zur Verdeutlichung sind die 84 Bytes die Größe des Maschinencodes, nachdem dieser zusammengestellt wurde? In diesem Fall sollte der Titel aktualisiert werden, um darauf hinzuweisen, dass es sich um eine Maschinencode-Antwort und nicht um eine Assembly-Antwort handelt.

Potato44

1

Übrigens müssen Sie keine Standard-Anrufkonvention verwenden. Sie können eine benutzerdefinierte Konvention verwenden, bei der RBX überlastet ist und 2 Bytes für Push / Pop spart. (Und wo uint8_tArgs für JRCXZ auf 64-Bit erweitert werden). Wenn Sie einen positionsabhängigen Code schreiben, können Sie die Tabellenadresse auch in ein Register mit einem 5-Byte-Wert mov ebx, imm32anstelle eines 6-Byte-Werts call/ einfügen pop. Oder benutze es als disp32in mov al, [table + rax], aber das könnte verlieren, da du schon zwei xlatbund ein hast mov. Der Call + Pop-Shellcode-Trick gewinnt gegenüber dem 7-Byte-RIP-relativen LEA mit den Daten nach dem 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* wiederholt etwas durch den aktuellen Zeitstempel, der eine große Zahl ist, und es würde zu lange dauern, um fertig zu werden.

Aktuell testbare Version, 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

Beweisen, dass ein russischer kryptografischer Standard zu strukturiert ist

Was ist p

"Unmögliche" Implementierungen

Referenzimplementierung

Regeln

Antworten:

AMD64-Assembly (78 Byte oder 624 Bit Maschinencode)

64-Bit x86-Assembly

Zerlegter 64-Bit-Code

32-Bit-x86-Assembly

Zerlegter 32-Bit-Code

CJam ,72 67 66 63 Bytes

Erläuterung

Jelly 71 59 Bytes

Erläuterung

Ursprünglicher Ansatz

Jelly , 71 66 Bytes

Erläuterung

C (gcc) , 157 148 140 139 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 Byte

JavaScript (Node.js) , 149 bis 148 Byte

Codierung

sss

C # (Visual C # Interactive Compiler) , 141 Byte

Python 3 , 182 Bytes

Python 3 , 176 Bytes

Python 3 , 173 Bytes

Rust , 170 163 Bytes

05AB1E , 74 Bytes

Was ist `p`

$s$