Celem tego wyzwania jest znalezienie niemożliwie krótkiej realizacji następującej funkcji p, w wybranym przez ciebie języku. Oto kod C implementujący go (zobacz ten link TIO, który również drukuje jego wyniki) i zawierającą go stronę wikipedii .

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

Co jest `p`

pjest składnikiem dwóch rosyjskich standardów kryptograficznych, mianowicie funkcji skrótu Streebog i szyfru blokowego Kuźnyechik . W tym artykule (i podczas spotkań ISO) projektanci tych algorytmów twierdzili, że wygenerowali tablicę pi, wybierając losowe permutacje 8-bitowe.

Implementacje „niemożliwe”

Jest permutacji na 8 bitach. Dlatego dla danej losowej permutacji program, który ją implementuje, nie powinien wymagać mniej niż 1683 bitów. $256! \approx 2^{1684}$

Znaleźliśmy jednak wiele nienormalnie małych implementacji (które wymieniliśmy tutaj ), na przykład następujący program 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;}

który zawiera tylko 158 znaków, a zatem mieści się w 1264 bitach. Kliknij tutaj, aby zobaczyć, czy to działa.

Mówimy o „niemożliwie” krótkiej implementacji, ponieważ jeśli permutacja byłaby wynikiem losowego procesu (jak twierdzą jej projektanci), to taki program nie istniałby ( więcej szczegółów na tej stronie ).

Realizacja referencyjna

Bardziej czytelna wersja poprzedniego kodu C to:

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

Tabela kjest taka, że k[x] = L(16-x)gdzie Ljest liniowy w tym sensie L(x^y)==L(x)^L(y), i gdzie, podobnie jak w C, ^oznacza XOR. Nie udało nam się jednak wykorzystać tej właściwości, aby skrócić nasze wdrożenie. Nie jesteśmy świadomi żadnej struktury, sktóra mogłaby pozwolić na prostszą implementację --- jednak jej dane wyjściowe są zawsze w polu podrzędnym, tj. gdzie potęgowanie odbywa się w polu skończonym. Oczywiście masz absolutną swobodę w stosowaniu prostszego wyrażenia, jeśli go znajdziesz! $s[x]^{16}=s[x]$ s

Pętla while odpowiada ocenie dyskretnego logarytmu w polu skończonym z 256 elementami. Działa poprzez proste wyszukiwanie siłowe: zmienna fikcyjna ajest ustawiona na generator pola skończonego i jest mnożona przez ten generator, aż wynik będzie równy x. W takim przypadku mamy do czynienia lz dyskretnym dziennikiem x. Ta funkcja nie jest zdefiniowana w 0, stąd specjalny przypadek odpowiadający ifinstrukcji.

Mnożenie przez generator może być postrzegane jako mnożenie przez w który jest następnie redukowany modulo do wielomianu . Rolą tego jest zapewnienie, że zmienna pozostaje na 8 bitach. Alternatywnie, możemy użyć , w którym to przypadku może być (lub dowolny inny typ całkowity). Z drugiej strony należy zacząć od tego, co musimy mieć, gdy jest równe 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

Więcej szczegółów na temat właściwości pprzedstawiono w naszym artykule , z podsumowaniem większości naszych optymalizacji w celu uzyskania poprzedniej krótkiej implementacji.

Zasady

Zaproponuj program, który implementuje funkcję pw mniej niż 1683 bitach. Im krótszy program, tym bardziej nienormalny, dla danego języka, krótszy jest lepszy. Jeśli twój język ma Kuznyechik, Streebog lub pjako wbudowany, nie możesz ich używać.

Miarą używaną do określenia najlepszej implementacji jest długość programu w bajtach. W naszej pracy naukowej używamy długości bitów, ale dla uproszczenia trzymamy się tu bajtów.

Jeśli język nie ma jasnego pojęcia funkcji, argumentu lub wyjścia, kodowanie jest do ciebie, aby określić, ale sztuczki jak kodowania wartości pi[x]jak xsą oczywiście zabronione.

Przedłożyliśmy już dokument badawczy z naszymi ustaleniami na ten temat. Jest dostępny tutaj . Jeśli jednak zostanie opublikowany w miejscu naukowym, chętnie uznamy autorów najlepszych wdrożeń.

Nawiasem mówiąc, dzięki xnor za pomoc w przygotowaniu tego pytania!

code-golf math kolmogorov-complexity cryptography picarresursix
źródło

12

Mam nadzieję, że ktoś prześle odpowiedź w Seed.

Robin Ryder

6

Podobnie, na przykład, czy kod pieprzenia mózgu może być oceniany przy 3 bitach na znak, jeśli nie ma nops? A czy jest 1683 bits at mostto ścisłe ograniczenie [sic?] Czy cel?

ktoś

31

„ Gdyby permutacja była wynikiem losowego procesu (jak twierdzą jej projektanci), to taki krótki program nie istniałby ” Nie zgadzam się (choć nie ma to znaczenia dla wyzwania). Gdyby był to wynik losowego procesu, mało prawdopodobne byłoby istnienie takiego programu; lub byłoby trudno znaleźć

Luis Mendo

8

@Grimy Stwierdzenie, że tak krótki program nie istniałby, jest koncepcyjne (nie programowe). Używając twoich warunków, należy do świata czystej matematyki, a nie do świata programowania

Luis Mendo

7

Być może zostało to już zauważone, ale na wszelki wypadek: daje tylko 8 różnych wartości: (zaczynając od i zakładając, że ) .

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

Zestaw AMD64 (78 bajtów lub 624 bitów kodu maszynowego)

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,2, 2,44,48,16,2,54,36,52,38,18,0};

    jeśli (x) {
      dla (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];
    }
    zwraca x ^ 252;
}

64-bitowy zestaw x86

    ; 78 bajtów zestawu AMD64
    ; odzhan
    bity 64

    % ifndef BIN
      globalny SubBytex
    % endif

SubBytex:
    mov al, 252
    jecxz L2; jeśli (x) {
    zadzwoń do 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 ++
    add al, al; y = y + y
    jnc $ + 4; pomiń XOR, jeśli nie nosisz
    Xor al. 29;
    cmp al, cl; jeśli (y! = x) masz 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; jeśli (x == 0) mam L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    gnić

Zdemontowany 64-bitowy kod

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 wywołanie 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, kl
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, kl
0000004D C3 ret

32-bitowy zestaw x86

    ; 72 bajty zestawu x86
    ; odzhan
    bity 32

    % ifndef BIN
      globalny SubBytex
      globalny _SubBytex
    % endif

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; jeśli (x) {
    zadzwoń do 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 ++
    add al, al; y = y + y
    jnc $ + 4; pomiń XOR, jeśli nie nosisz
    Xor al. 29;
    cmp al, cl; jeśli (y! = x) masz 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] lub k [x]
    jz L2; jeśli (x == 0) mam L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    gnić

Zdemontowany 32-bitowy kod

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 połączenie 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, kl
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
źródło

1

Niezła odpowiedź! Ponieważ OP szukał liczby bitów, to (85 bajtów) wychodzi na 680 bitów , używając 8 bitów na bajt lub 595 bitów, używając 7 bitów na bajt (możliwe, ponieważ wszystkie znaki są ASCII). Prawdopodobnie możesz skrócić, jeśli skompresujesz do jeszcze bardziej restrykcyjnego zestawu znaków.

Cullub

1

Witamy w PPCG; fajne pierwsze rozwiązanie.

Kudłaty

9

@Cullub Chodzi mi o to, że kod w tej odpowiedzi to tylko C / Asembler, który jest kompilowany, więc liczba bajtów nie jest liczona dla danego kodu, ale dla skompilowanego kodu. A to nie ASCII.

ArBo

7

Tylko dla wyjaśnienia, 84 bajty to rozmiar kodu maszynowego po jego złożeniu? Jeśli tak, tytuł powinien zostać zaktualizowany, aby odzwierciedlić, że jest to odpowiedź kodu maszynowego, a nie odpowiedź zestawu.

Potato44

1

A BTW, nie musisz stosować standardowej konwencji połączeń; możesz użyć niestandardowej konwencji, w której RBX jest zapętlony, oszczędzając 2 bajty dla push / pop. (A gdzie uint8_targumenty są rozszerzone zera do 64-bit dla JRCXZ). Ponadto, jeśli napiszesz kod zależny od pozycji, możesz umieścić adres tabeli w rejestrze z 5 bajtami mov ebx, imm32zamiast 6 bajtów call/ pop. Lub wykorzystać go jako disp32IN mov al, [table + rax], ale że może stracić skoro masz dwa xlatba movjuż. Jednak sztuczka call + pop shellcode wygrywa w porównaniu z 7-bajtowym LEA zależnym od RIP z danymi po ret.

Peter Cordes

23

CJam ,72 67 66 63 bajty

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

es* powtarza coś według aktualnego znacznika czasu, który jest dużą liczbą, a jego ukończenie zajęłoby zbyt dużo czasu.

Rzeczywista wersja testowa, 64 bajty:

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

Udowodnienie, że rosyjski standard kryptograficzny jest zbyt uporządkowany

Co jest p

Implementacje „niemożliwe”

Realizacja referencyjna

Zasady

Odpowiedzi:

Zestaw AMD64 (78 bajtów lub 624 bitów kodu maszynowego)

64-bitowy zestaw x86

Zdemontowany 64-bitowy kod

32-bitowy zestaw x86

Zdemontowany 32-bitowy kod

CJam ,72 67 66 63 bajty

Wyjaśnienie

Galaretka 71 59 bajtów

Wyjaśnienie

Oryginalne podejście

Galaretka , 71 66 bajtów

Wyjaśnienie

C (gcc) , 157 148 140 139 bajtów

C (gcc) , 150 142 127 126 bajtów

05AB1E , 101 100 98 97 95 94 bajtów

Stax , 65 64 62 59 58 bajtów

Python 3 , 151 bajtów

JavaScript (ES6), 139 bajtów

JavaScript (Node.js) , 149 148 bajtów

Kodowanie

sss

C # (interaktywny kompilator Visual C #) , 141 bajtów

Python 3 , 182 bajty

Python 3 , 176 bajtów

Python 3 , 173 bajtów

Rdza , 170 163 bajtów

05AB1E , 74 bajty

Co jest `p`

$s$