Puncte:0

Forma normală algebrică a unei funcții în $\operatorname{GF}(2^{n})$

drapel cn

Luați în considerare funcția $f(x)=x^{2k+1}$ în $\operatorname{GF}(2^{n})$ pentru $n$ ciudat și $\gcd(k,n)=1$, care este o funcție diferențială 2-uniformă.

Pentru $n=3$, $k=1$, vreau să găsesc Forma normală algebrică a functiei. Există vreo cale?

user3571 avatar
drapel us
Vă rugăm să revizuiți întrebarea și să explicați mai multe despre conceptul de ANF sau să faceți un link pentru acest subiect. Spuneți mai multe despre aplicarea ANF în criptografie și folosind exemple, clarificați întrebările pentru utilizatori. De fapt, pentru a primi un răspuns bun, vă rugăm să vă adresați corect întrebarea. Mulțumiri
fgrieu avatar
drapel ng
Este ceva greșit cu elementul de bază: presupuneți un polinom de reducere pentru $\operatorname{GF}(2^n)$, utilizați-l pentru a calcula în mod explicit $f(x)$ ca șir de biți de $n$-biți pentru doar $2^n$ valorile $n$-biți șir de biți $x$, face ca $n$ funcții booleene pentru $n$ argumente booleene, găsiți ANF-ul fiecăruia folosind [o metodă sistematică](https://en.wikipedia.org/wiki/ Algebric_normal_form#Recursively_deriving_multiargument_Boolean_functions)?
Puncte:1
drapel sa

După cum a subliniat @fgrieu, ANF este o reprezentare polinomială multivariată. De obicei peste câmpul de bază binar, deci $n$ se obţin variabile binare. Presupun că dacă $n$ este compus, poate fi definit și peste $GF(2^m)$ Unde $m|n,$ și $m>1$ dar nu văd niciun avantaj specific în a face acest lucru.

Există două răspunsuri explicite legate de sugestie din comentariul de la întrebarea de mai jos:

https://crypto.stackexchange.com/questions/47957/generate-anf-from-sbox/47959

Puncte:0
drapel in

Rețineți că aveți $n=3$ biți de ieșire, fiecare dintre ei are propriul său ANF. Iată cum se calculează cu SageMath:

sage: din sage.crypto.sbox import SBox
salvie: n = 3; k = 1sage: F = GF(2**n)
sage: s = SBox([(F.fetch_int(x)**(2*k+1)).integer_representation() for x in range(F.order())])
sage: [s.component_function(2**i).algebric_normal_form() for i in range(n)]
[x0 + x1*x2 + x1 + x2, x0*x1 + x0*x2 + x1, x0*x1 + x2]

Acest lucru oferă ANF-urile în ordine de la bitul cel mai puțin semnificativ la cel mai semnificativ bit (acest lucru este definit de convenția SageMath pentru fetch_int/integer_representation).

În fiecare ANF, ordinea variabilelor este similară: x0 este bitul de intrare cel mai puțin semnificativ.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.