OMAC: moltiplicazione in un campo finito - come posso calcolare il polinomio corretto

Question

OMAC: moltiplicazione in un campo finito - come posso calcolare il polinomio corretto

#1 da (5 voti)
#2 da (3 voti)

5

We explain the notation used in the deﬁnition of OMAC. The value of iL (line 40: i an integer in {2, 4} and L ∈ {0, 1}ⁿ) is the n-bit string that is obtained by multiplying L by the n-bit string that represents the number i. The multiplication is done in the ﬁnite ﬁeld GF(2ⁿ) using a canonical polynomial to represent ﬁeld points. The canonical polynomial we select is the lexicographically ﬁrst polynomial among the irreducible polynomials of degree n that have a minimum number of nonzero coefﬁcients. For n = 128 the indicated polynomial is x¹²⁸ + x⁷ + x² + x + 1. In that case, 2L = L << 1 if the ﬁrst bit of L is 0 and 2L = (L << 1) ⊕ 0¹²⁰10000111 otherwise, where L << 1 means the left shift of L by one position (the ﬁrst bit vanishing and a zero entering into the last bit). The value of 4L is simply 2(2L). We warn that to avoid side-channel attacks one must implement the doubling operation in a constant-time manner.

Fondamentalmente mi è stato dato solo che il polinomio da usare nella moltiplicazione finita per n = 128 è x ¹²⁸ + x ⁷ + x ² + x + 1. Voglio che la mia implementazione sia astratta in quanto non dipende dalle specifiche del cypher in uso. Per consentire alla dimensione del blocco n di essere qualsiasi numero piuttosto che di codifica 128 o pochi altri, come posso fare in modo che il mio software calcoli il polinomio corretto?

cryptography encryption

posta jnm2 22.06.2011 - 02:33

fonte

2 risposte

5

Non farlo. Per la maggior parte delle persone, non vi è alcun motivo per implementare la propria libreria crittografica. Ottieni una libreria crittografica esistente con un'implementazione di CMAC (nota anche come AES-OMAC1) e utilizza quel codice. L'implementazione da soli è soggetta a errori (con il rischio di problemi di sicurezza) e spesso non consente l'ottimizzazione delle prestazioni trovata nelle librerie standard. Per la maggior parte degli scopi, non vi è alcun motivo per implementarlo da soli e poco motivo per utilizzare qualsiasi altro codice di AES o, in particolare, un codice a blocchi con qualcosa di diverso da una dimensione di blocco di 128 bit.

risposta data 22.06.2011 - 04:25

fonte

Leggi altre domande sui tag cryptography encryption

Script FrameBusting Esiste una lista di cifrature SSH deboli?

score 3 · Accepted Answer

@ D.W. dà la risposta importante e corretta, ovviamente. Non reimplementare la tua libreria crittografica (o, almeno, fallo per imparare e per divertirti, ma non fidati!).

Ora, per i dettagli, il testo che citi effettivamente fornisce tutti i dettagli che sono necessari, anche se in un modo matematico piuttosto conciso. La frase importante è questa:

The canonical polynomial we select is the lexicographically ﬁrst polynomial among the irreducible polynomials of degree n that have a minimum number of nonzero coefﬁcients.

Quando calcoli con polinomi binari modulo un P polinomiale di grado n , ottieni un campo finito (denotato GF (2 ⁿ) ) solo se P è irreducible .

Ci sono 2 ⁿ polinomi binari di grado n ; possono essere tutti scritti come:

P = p ₀ + p ₁ X + p ₂ X ² + .. . + p _n-1 X ^n-1 + X ⁿ

dove ogni p _i è o 0 o 1. Si noti che per i polinomi binari, calcoliamo tutti i valori in GF (2) , quindi l'aggiunta è XOR e la moltiplicazione è AND.

Per implementazioni più veloci, lo preferiamo quando il numero di p _i non zero è minimo; è anche meglio se p _i non zero sono per piccoli valori di i . È facile vedere che, P è irriducibile, p ₀ deve essere uguale a 1, e deve esserci un numero dispari di non-zero p _i per i tra 1 e n-1 . Come dice la specifica EAX, proviamo tutti i polinomi fino a raggiungere uno che è irriducibile; iniziamo con i polinomi con solo uno non zero p _i (ce ne sono n-1 ), e, se nessuno è irriducibile , quindi proviamo i polinomi con tre valori p _i non nulli (ci sono (n-1) (n-2) (n-3) / 6 di loro). E iniziamo con quelli in cui p _i sono per i valori più bassi possibili i , cioè iniziamo da 1 + X + X ² + X ³ + X ⁿ .

Quindi tutto ciò che dovresti fare sarebbe enumerare i polinomi binari di grado n , con il numero minimo di coefficienti diversi da zero, in ordine lessicografico, e testarli per irriducibilità. Per quel test, consulta il Manuale di crittografia applicata , capitolo 4, sezione 4.5.1.