Fondamenta di CryptographyProf. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BangaloreLecture-12Practical Instantiations of PRGHello All, welcome to lezione 11. (Fare Slide Time: 00 :30) Il piano per questa lezione è il seguente. In questa lezione discuteremo delle instantiazioni pratiche di generatori pseudo casuali, ovvero vedremo la costruzione basata sul registro dei turni di feedback lineare e RC4 e discuteremo dei recenti sviluppi nel settore delle instantiazioni pratiche di pseudo generatore casuale. Il motivo per cui chiamiamo queste instanziamenti come pratici è che sono super veloci, rispetto alle costruzioni provvibilmente sicure di generatori pseudo casuali di cui avevamo discusso nell'ultima lezione basata su una sola modalità di funzionamento e una sola permutazione. Tuttavia, purtroppo, per queste instantiazioni pratiche di pseudo generatori casuali, non abbiamo alcuna prova matematica che siano effettivamente dei generatori di pseudo casualità. Il che significa che non abbiamo la teoria del teorema, che dimostra che ehi non c'è nessun distinguo tempo polinomiale che possa distinguere l'uscita di questo generatore di numeri casuali dall'uscita di un vero generatore di numeri casuali. È solo perché da quando la costruzione di queste istanziazioni pratiche di PRGs non abbiamo trovato alcun attacco adatto o qualsiasi distinguo adatto, crediamo che queste costruzioni siano sicure, mentre per le costruzioni provvibilmente - sicure basate su una funzione di modo e hard-core che abbiamo discusso nell'ultima lezione, abbiamo una prova matematica che anzi sono sicuri nel senso che non esiste un distinguo tempo polinomiale per distinguere l'output di quegli algoritmi dall'output del corrispondente vero generatore di numeri casuali. Così in pratica, ovunque tu abbia una costruzione crittografica dove si ha voglia di istanziare un generatore pseudo - casuale, in realtà andiamo per queste instantiazioni pratiche. (Vedi Slide Time: 02 :08) Quindi in tutte le instantiazioni pratiche di generatori pseudo - casuali, possiamo seguire la seguente astrazione. Immaginate di ricevere un generatore pseudo - casuale, che espande un input di l - bit ad un output di? - bit. Possiamo supporre che il generatore pseudo - casuale sia costituito da una coppia di algoritmi, ovvero un algoritmo di inizializzazione e algoritmo GetNextBit. E ciò che fondamentalmente questi algoritmi fanno sono come seguis.Così, l'algoritmo Init è in realtà l'algoritmo di inizializzazione che imposta lo stato iniziale del vostro algoritmo ed è una funzione deterministica. E ci vuole il seme per l'algoritmo? come input e insieme a quello di un vettore di inizializzazione opzionale, quindi questo vettore di inizializzazione è opzionale. Non è necessario che ogni istanziazione pratica di generatore pseudo - casuale prenda questo vettore di inizializzazione, dipende dalla costruzione sottostante. Tuttavia, se l'??? viene dato come input, è noto pubblicamente, e basato sul seme e??, l'algoritmo di inizializzazione produce uno stato iniziale dell'algoritmo che denottiamo da? ?0. Ora, l'algoritmo di GetNextBit fa quanto segue. Ci vuole lo stato attuale del tuo algoritmo o del PRG, che io denoto di? ???, e aggiorna lo stato in? ?? + 1 e insieme a quello produce il bit di uscita successivo del tuo algoritmo?, right.Quindi, se vuoi generare una sequenza di bit, quello che facciamo è l'algoritmo di inizializzazione, ottenere lo stato iniziale??? e dire se siete interessati a ottenere un output di big? - bit, praticamente invitiamo questo algoritmo di GetNextBit? numero di volte in sequenza e in ogni richiamo lo stato viene aggiornato e i bit di output continuano ad essere generati uno per uno. Ecco allora l'astrazione che possiamo usare per astrarre qualsiasi strumentazione pratica di pseudo generatore casuale. (Vedi Slide Time: 04 :03) Così vediamo, una popolarmente utilizzata instantiere pratica di generatore pseudo - casuale, che usiamo nell'hardware. E questo si chiama registro di turno di feedback lineare o LFSR. Così, storicamente, è stato usato come PRG. Ed è molto veloce quando implementato in hardware. Tuttavia, non è consigliabile essere utilizzati per applicazioni critiche, perché è molto facile per un avversario recuperare l'intera chiave solo vedendo pochi bit di output del LFSR.Quindi, un LFSR di laurea? in sostanza sono costituiti? registri denotati da? 0to?? − 1. E insieme a quello, avrà? coefficienti di feedback? 0to?? − 1, dove i coefficienti saranno valori booleani. Così ad esempio, qui abbiamo un LFSR di grado 4 composto da 4 registri e i coefficienti di feedback sono 0, 1, 0, 1. Così, come opera un LFSR. Per quanto riguarda lo stato di un LFSR, lo stato non è altro che i valori di bit che vengono memorizzati nel singolo register.Quindi, se prendiamo questo particolare esempio, allora lo stato del LFSR non è altro che una stringa di 4 bit e cioè i 4 memorizzati nei registri? 3,? 2 e? 0 e? 0 e aggiornamento dello stato succede come segue: dopo ogni ciclo di clock, il bit che è presente in? 0is va prodotto come il bit di uscita e il contenuto di tutti i registri sono spostati a destra. Di conseguenza, quello che succederà è che la corrente? 1 diventerà il prossimo? 0. La corrente? 2 diventerà il prossimo? 1 e così via. E di conseguenza? 3 diventeranno vuoti. E il valore aggiornato dell'ultimo registro, in questo caso? 3, sarà determinato prelevando uno XOR dei sottoinsiemi dei bit dello stato attuale. E i sottoinsiemi dei registri il cui XOR che prendiamo è effettivamente determinato dal coefficiente di feedback. Ancora in questo esempio, dato che i coefficienti di feedback sono 0, 1, 0, 1, questo significa, dopo ogni ciclo di clock una volta che facciamo il mutare giusto qui, il valore di? 3, non è niente, ma lo XOR della corrente? 2, e la corrente? 0. Se prendi lo XOR che sarà il valore che verrà alimentato come nuovo valore di? 3. Ecco perché il nome del registro dei turni di feedback lineare. In ogni ciclo di clock spostiamo il contenuto di tutti i registri per una posizione ed è per questo che il registro di turno. E un feedback lineare, perché abbiamo un loop di feedback che determina il valore del contenuto di?? − 1, nel ciclo di clock successivo. E questa funzione di feedback è una funzione lineare dell'attuale serie di registri. Ecco perché il nome lineare di feedback di feedback lineare. (Fare Slide Time: 06 :54) Quindi per esempio, se prendi questo LFSR di grado 4, e supponiamo che lo stato iniziale sia 0011, poi dopo il primo orologio, tutto sarà spostato da una posizione, e di conseguenza, il bit 1 sarà il primo bit di uscita e il feedback che andrà in LFSR per la prossima iterazione sarà di 1 € e 1 perché i tuoi coefficienti di feedback sono 0, 1, 0, 1 e di conseguenza il prossimo stato di LFSR sarà 1001.Again dopo il prossimo ciclo di clock, il bit value 1 sarà svuotato di output test; quello sarà il secondo output bit del tuo LFSR e il feedback che andrà sarà di 1 e di conseguenza il tuo stato verrà aggiornato a 1100 e così via. Quindi, ecco come un LFSR di laurea? opera. (Fare Slide Time: 07 :49) Ora facciamo discutere se questo LFSR sia sicuro o meno, questo significa che possiamo considerare questo LFSR un generatore pseudo casuale. E il requisito da un generatore pseudo casuale è che se qualcuno ti dà il campione di un LFSR, in cui non ti viene dato lo stato iniziale dell'algoritmo perché se ti viene dato lo stato iniziale di LFSR allora puoi effettivamente calcolare tutti i bit di output di LFSR. Quindi, immaginate di non aver dato lo stato di ingresso del LFSR e insieme a questo immaginate di non aver dato i coefficienti di feedback altrettanto bene ma vi viene dato il grado di LFSR, cioè si conosce il numero di registri che vengono utilizzati in LFSR. Poi è possibile che l'aggressore compia o preveda l'esito di LFSR. Si scopre che se abbiamo un LFSR di grado?, allora può avere al massimo 2? − 1 stati non zero. E perché siamo interessati a Stati non zero? Perché una volta che LFSR occupa lo Stato, dove il contenuto di tutti i registri è 0, poi dopo che non importa quante volte o quanti cicli di clock operiamo il LFSR,tutti gli stati successivi saranno 0. Il che significa che una volta raggiunto uno stato tutto zero, dovremmo smettere di generare i fusi di LFSR. Quindi il caso interessante è quando in realtà ci concentriamo sugli stati non zero di LFSR. Definiamo LFSR una lunghezza massima LFSR, se la sequenza di output si ripete dopo esattamente 2? − 1number di stati non zero. E in modo interessante, si scopre che non importa con quale stato di ingresso si inizi con, se si inizia con uno stato iniziale non zero, allora è sempre possibile impostare i coefficienti di feedback in modo che il tuo LFSR diventi effettivamente una lunghezza massima LFSR.Che significa partire da quello stato iniziale non zero, puoi passare attraverso tutti i 2? − 1 non zerostati e poi solo la sequenza ripeterà. Quindi immagina per il momento che hai una lunghezza massima LFSR. Intuitivamente, potreste sentire che tutte le stringhe? - bit saranno prodotte con uguale frequenza, poi vuol dire che il vostro LFSR è un PRG sicuro perché se lo stato di uscita verrà ripetuto dopo 2? − 1 numero di stati, questo significa per un aggressore, deve aspettare il 2? − 1 numero di stati, che è una quantità esponenziale di quantità. E di qui non può distinguere l'uscita di LFSR dall'uscita di un vero generatore di numeri casuali. Potrebbe essere la tua intuizione sottostante in base alla quale puoi dichiarare il tuo LFSR per essere sicuro. Ma si scopre che non è così. Per un LFSR di grado?, solo osservando il numero polinomiale dei bit di output, (Fare Slide Time: 10 :26) un avversario può recuperare l'intera chiave e una volta recupera l'intera chiave, può prevedere tutti i futuri bit di output di destra LFSR. Quindi immaginate di ricevere un LFSR di laurea?, dove donate i coefficienti di feedback e non conoscete gli stati iniziali di LFSR e immaginate che l'avversario abbia osservato i primi 2? bit di output del LFSR che io denotano da? 1, …? ?.E lo stato iniziale non zero del LFSR è denotato dalla notazione (?? − 1 (0), …,? 0 (0)). Quindi in questa notazione, nella sovrascrittura, sto mettendo 0 nella parentesi che denota il 0 stato di LFSR ovvero lo stato iniziale, e questo è sconosciuto anche per l'aggressore, l'aggressore ha visto solo i primi 2? bit di output. Inoltre ipotizziamo che l'avversario non sia a conoscenza dei coefficienti di feedback; dal punto di vista dell'avversario potrebbe essere qualsiasi sottoinsieme di? registri che in realtà stanno prendendo XORed per decidere il feedback. Quindi i coefficienti sconosciuti?? − 1to? 0 sono quindi anche l'aggressore. Si scopre che l'avversario conosce il rapporto che lo stato iniziale del LFSR non è altro che il primo? bit di output che ha visto perché se si vede il funzionamento del LFSR, dopo ogni ciclo di clock, il contenuto di? 0is in realtà esce come output e dopo ogni ciclo di clock, il nuovo contenuto di? 0is in realtà il contenuto precedente di? 1, che a sua volta è il precedente? 2 e così via. Questo significa avversario sa che il primo? i bit di output del tuo LFSR non sono niente, ma il tuo stato iniziale. Ecco allora la prima informazione che ora è a disposizione dell'avversario, che ora è una quantità significativa di informazioni per l'avversario. E si scopre che i prossimi bit di uscita, ovvero?? + 1to? 2?, in realtà dà un sistema di equazioni lineari nelle incognite nei coefficienti di feedback all'avversario. L'avversario sa che il? + 1 ?h output bit?? + 1is niente, ma? 0?1 ⨁?1?2  ?? − 1 ??. Allo stesso modo, il bit di output 2 ??h soddisfa la relazione? 2? =? 0??⨁?1?? + 1 €    ?? − 1 ?2? − 1. Così l'avversario ottiene un sistema di? equazioni indipendenti in? variabili. E risolverli, può recuperare completamente i coefficienti di feedback. Così ora sia le chiavi che i coefficienti di feedback sono noti all'avversario.E da qui può determinare completamente tutti i successivi output del vostro LFSR. Questo significa solo osservando 2? bit di output del LFSR, l'avversario può rompere completamente questo LFSR. E di qui non si fa, in realtà si tratta di un generatore pseudo casuale. (Fare Slide Time: 13 :27) Quindi un metodo che serve per preservare la sicurezza del LFSR è quello di aggiungere qualche tipo di non? linearità. Se si vede l'attacco, o la strategia, utilizzata dall'aggressore qui è quella di esplorare il sistema di equazione lineare, ovvero, l'aggressore utilizza il fatto che il feedback è in realtà una funzione lineare del sottoinsieme del registro. Quindi un modo per aggirarsi è quello di aggiungere qualche tipo di non? linearità nel registro dei turni di feedback. E ci sono diversi modi di introdurre la non - linearità nella costruzione del registro dei turni di feedback lineare. Il primo metodo di aggiunta della non - linearità è quello di fare in modo che il proprio feedback sia non lineare. Ovvero, quello che supponiamo qui è che il contenuto del? ?hregister al ciclo dell'orologio? + 1 sarà il contenuto dell'? + 1 ?hRegistro al ciclo dell'orologio?, questo significa che tutto è ancora spostato da una posizione dopo ogni ciclo di clock. Ma il contenuto dell'ultimo registro è ormai una funzione non lineare degli attuali registri. Quindi, nella precedente costruzione in LFSR, la funzione? era in realtà una funzione lineare. Ma la proposta qui è che invece di garantire che il feedback sia una funzione lineare, il feedback sarà ora una funzione non lineare del set di bit che ci sono nel registro corrente. Ecco, questo è un modo per aggiungere non linearità che è seguito nelle moderne costruzioni di generatori pseudo casuali basati su registri di spostamento di feedback. L'altro modo di aggiungere la nonlinearità è quello di aggiungere non linearità nell'output stesso. Quindi fino ad ora stiamo discutendo il caso in cui la produzione è in realtà il contenuto della corrente? 0, dove? 0is il valore di? 1in il ciclo dell'orologio precedente e così via e ogni ciclo di clock tutto viene spostato da una posizione. Ma potrei avere un altro modo di determinare l'output, dove la produzione è in realtà una funzione non lineare. E ci sono 2 modi per determinare generatori di combinazione non lineare. Variante uno è il seguente: usiamo ancora il singolo LFSR, dove tutto si sposta di una posizione e abbiamo un feedback lineare. Ma invece di garantire semplicemente che? 0is il bit di uscita, il bit di uscita si rivela essere una funzione non lineare dei registri correnti. E la variante due è, invece di usare un LFSR, ora avremo diversi LFSR, preferibilmente di diversi gradi. E il bit di output complessivo del LFSR combinato sarà una complicata funzione non lineare dell'output dei singoli LFSR. Ecco quindi che è la seconda variant.Quindi, questo significa aggiungere non linearità hai 2 opzioni, non - linearità nel feedback e non linearità nell'output, dove la non linearità nell'output può essere ottenuta in 2 modi. Basta usare 1 LFSR, con l'output essendo una complicata funzione nonlineare e l'opzione due è quella di utilizzare diversi LFSRs, con l'output essendo una complicata funzione non lineare dell'output dei singoli LFSRs. (Fare Slide Time: 16 :31) E si scopre che le moderne costruzioni di PRGs basate su LFSR utilizzano effettivamente questi principi. Ecco quindi una costruzione candidata a base di LFSR, che si chiama Trivium. Ed è una instantificazione altamente popolare di pseudo generatore casuale. Se vedete pittoricamente, è in realtà una combinazione di 3 registri di spostamento di feedback. Così si ha il primo LFSR composto da 93 registri, che noi denottiamo come registro dei turni di feedback A. Poi si ha il prossimo LFSR, che noi denottiamo B composto da 84 registri. E poi abbiamo i prossimi registri di turno di feedback C, costituiti da 111 registri. Ora, il motivo per cui si utilizza 93, 84, 111 non sono chiaramente noti; sono il principio di progettazione utilizzato dai progettisti del trivium. Tuttavia ci sono alcuni principi ben noti che servono a selezionare il valore di FSR A, FSR B, FSR C come quello. Ma altrimenti in generale non ci sono linee guida fisse che servono a selezionare le dimensioni di FSR A, FSR B, FSR C per essere così. E ora, si vede che ogni FSR ha una produzione individuale. Quindi, se considero la produzione di FSR A, quindi, è sostanzialmente lo XOR del registro più a destra, in questo caso il 93 registro e un altro registro dello stesso FSR. Quindi questa è la prima differenza nella costruzione di Trivium rispetto al regolare LFSR.Nel regolare LFSR, la 93 uscita, il contenuto del 93 registro sarà considerato l'output bit dopo ogni ciclo di clock. Ma ora dopo ogni ciclo di clock, si tratta dello XOR del 93 registro e di un 66 ?hregister in FSR A, che sarà considerato come l'uscita del FSR A dopo i singoli cicli di clock. E lo stesso vale per il FSR B così come il FSR C. Questo è il primo modo di aggiungere la nonlinearità qui. E l'output complessivo del FSR è sostanzialmente lo XOR dell'output del FSR A, FSR B, FSR C. Così è il secondo modo di aggiungere qui la nonlinearità. Per quanto riguarda il feedback qui, se si vede ad esempio, il FSR A qui, ora che cosa sta andando come feedback? Quindi il feedback non è altro che fondamentalmente una funzione di uno dei registri nello stesso FSR e un sottoinsieme di registri del FSR sopra di esso. Quindi quello che intendo “ qui sopra di esso ” è il seguente: come ho detto la sequenza dei primi 93 registri è il FSR A e il registro successivo 84 è FSR B e il registro successivo 1011 è FSR C. Si può immaginare questa costruzione come una sorta di costruzione circolare, dove sopra il FSR B abbiamo il FSR A e sopra il FSR C abbiamo il FSR B. Ecco cosa intendo di “ in questo contesto. E il feedback del FSR A è sostanzialmente uno XOR di uno dei registri del FSR C. Allo stesso modo, il feedback del FSR B è uno XOR di alcuni registro del FSR B insieme ad alcuni registri del FSR A, e allo stesso modo il feedback per il FSR C è uno XOR di alcuni registri del FSR C insieme ad alcuni registri del FSR B. Ecco come stiamo introducendo la nonlinearità. Quindi, l'idea qui è realizzando questa complicata costruzione, stiamo effettivamente rimuovendo completamente la linearità che era presente nella costruzione originale del LFSR. Ed è così che il Trivium è progettato. E questo è considerato un PRG sicuro perché, dopo lo sviluppo di questa costruzione, non abbiamo avuto alcun attacco pratico. Questo significa che non è stato segnalato alcun algoritmo in tempo polinomiale, che può effettivamente prevedere l'esito del trivium se lo stato iniziale del trivium non è noto a you.Quindi, non sto entrando nei dettagli completi della costruzione, quali sono i principi di progettazione utilizzati, perché i 3 FSR utilizzati, i loro gradi sono costruiti così e così via. Se volete saperne di più sui dettagli di tali costruzioni potete fare riferimento ad uno qualsiasi dei riferimenti che stiamo seguendo in questo corso. (Fare Slide Time: 20 :56) Ora valuteremo un'altra istanza popolare di pseudo generatore casuale, ovvero RC4 super veloce quando implementato in software. E anche se è stato molto popolare tillalcuni anni fa, recentemente sono state riportate diverse vulnerabilità. Ed è per questo che non è più consigliabile essere utilizzato per scopi critici. Infatti è stato usato come uno degli standard in WEP.E dopo che le vulnerabilità sono state riportate in RC4 non è più utilizzata nella norma. Quindi, ricordati che ogni istanziazione pratica di generatore pseudo casuale è composta da 2 algoritmi, ovvero un algoritmo di inizializzazione e un algoritmo di aggiornamento di stato. E nell'algoritmo di inizializzazione, lo stato viene inizializzato e all'interno dell'algoritmo di updazione dello stato, lo stato viene aggiornato e i successivi bit di output generati. Così per quanto riguarda lo stato in RC4, lo stato è sostanzialmente costituito da una schiera, costituita da 256 bytes. E in tutto l'algoritmo sarà garantito che questi 256 bytes siano effettivamente costituiti da una permutazione del set da 0 a 255. Questo significa che ognuno dei valori da 0 a 255 si verificherà come uno dei byte tra questi 256 bytes. Ed è per questo che si tratta di una permutazione del set da 0 a 255.Now l'algoritmo di inizializzazione per questo RC4 è il seguente. L'algoritmo di inizializzazione crea una pseudo permutazione casuale dipendente dal set da 0 a 255. E insieme a quello, inizializzare i puntini 2index? e? nell'intervallo da 0 a 255. Ovvero il modo in cui avviene l'inizializzazione per RC4, andremo nei dettagli dell'inizializzazione molto presto. E una volta effettuata l'inizializzazione, nell'algoritmo di aggiornamento di stato in ogni iterazione i byte di?, che sono in realtà una pseudo permutazione casuale dipendente del set da 0 a 255 sono mescolati in giro, e dopo lo shuffling uno dei byte è in uscita, cioè il modo in cui lo stato è aggiornato. (Fare Slide Time: 23 :02) Così ora lasciatevi entrare nei dettagli dell'algoritmo di inizializzazione. Quindi la chiave o il seme per il RC4algorithm è sostanzialmente un tasto 16 byte, che sarà un tasto 16 byte casuale. Quindi ci denottiamo? 0to? 15. E l'output sarà una pseudo permutazione casuale del set da 0 a 255. Quindi quello sarà la schiera?. Così inizializziamo la schiera? composto da valori da 0 a 255 in sequence.Namely, il primo byte è impostato su 0. Il byte successivo è impostato su 1 e l'ultimo byte si dice thevalue 255. Questa è una permutazione di identità. E ora dobbiamo ad alcuni come rimpasto il contenuto della schiera? in base al valore dell'array chiave?. Questo significa che dipende dal contenuto dei byte chiave, dobbiamo mischiare il contenuto della matrice?, garantendo che dopo lo shuffling, la modifica? rappresenta ancora una permutazione del set da 0 a 255.So per farlo, in realtà ripetiamo i valori della chiave e facciamo in modo che la matrice chiave diventi di dimensione 255. E questo è fatto eseguendo l'operazione,? [?] =? [? mod 16], questo significa che prendiamo i primi 16 bytes secondi, e lo ripetiamo ancora e ancora, per assicurarci di avere ormai un array chiave espanso di dimensione 256. Questo è il modo in cui facciamo l'espansione chiave. E poi impostiamo il puntatore dell'indice iniziale? per essere 0. E una volta il puntatore? è impostato su 0, per le prossime 256 iterazioni, facciamo quanto segue. Facciamo lo shuffling e per fare lo shuffling, in realtà cambia il valore di? come questo: ci siamo messi? di essere la sommatoria della corrente? e contenuti correnti del byte? ?h di? e il byte chiave? ?h. Ovvero? =? +? [?] +? [?]. E una volta che abbiamo l'indice aggiornato?, ci scambia il contenuto di? [?] e? [?]. Ecco come facciamo lo shuffling. Quindi, intuitivamente quello che si può immaginare qui è che in ogni iterazione, l'indice? viene incrementato di 1. E in ogni iterazione l'indice? viene mescolato casualmente, a seconda del byte delle chiavi. E una volta il puntatore? viene aggiornato, andiamo a quella posizione nella schiera? .E scambiare il contenuto? [?] con il contenuto di quella località. Ecco come si genera in realtà una permutazione casuale di tipo pseudo - dipendente di?. Perché si tratta di una permutazione casuale di tipo pseudo - dipendente di? è perché in ogni iterazione il valore di? dipende dal contenuto della matrice chiave. Che si occupa di come la permutazione risultante sia una permutazione chiave - dipendente. (Fare Slide Time: 26 :01) Ora una volta che lo stato è stato inizializzato, andiamo all'algoritmo di aggiornamento e output dello stato. Quindi, nell'algoritmo di aggiornamento dello stato, in ogni richiamo, il contenuto attuale dell'? verranno mescolate in giro e uno dei byte sarà in uscita. Quindi, il modo in cui viene generato è il seguente: Immaginiamo di avere la corrente? e la corrente?, quello che facciamo è aumentare il valore di?. E poi decidiamo casualmente il valore di?, a seconda dei contenuti attuali di? come segue. Quindi, il valore di? viene aggiornato in modo pseudo casuale impostando:? Ragazza (? +? [?]) mod 256. Questo significa qualunque sia l'indice attuale di?, a che aggiungiamo il valore di byte che viene memorizzato nella? ?hlocation della schiera?, e per garantire che facciamo il wraparound, tutte le operazioni sono fatte modulare 256. Quindi, facendo questa operazione aggiriamo il valore del contatore dell'indice? in una moda pseudo? casuale. E poi quello che facciamo è scambiarci il contenuto di? ?hlocation di schiera? e? ?hposizione della schiera?. Ecco come facciamo in realtà l'aggiornamento di Stato. Per determinare l'output, quello che facciamo è determinare un nuovo indice?, che non è altro che sommità del contenuto della? ?hlocation della schiera? e la? ?hlocation della schiera? .Che sia,? Ultime (? [?] +? [?]) mod 256. E andiamo in quella località, cioè la? ?hlocation e qualunque sia il valore di byte che vi viene memorizzato, cioè il valore di byte che stiamo andando in uscita. (Riferimento Slide Time: 27 :46) Quindi ora parliamo della sicurezza dell'algoritmo RC4. Quindi se vedete lo pseudocodice dell'algoritmo di aggiornamento di stato e di inizializzazione, potete vedere che non stiamo facendo alcuna operazione complicata. Ecco perché questo algoritmo è superveloce quando lo si implementa in software. Ed è per questo che era molto popolare. Poi le persone hanno iniziato a segnalare le vulnerabilità nella sicurezza di RC4. Quindi, vogliamo analizzare qui se effettivamente RC4 è un generatore di numero pseudo - casuale candidato o meno. Quindi se si ricorda, in ogni alterazione dell'aggiornamento dello stato, RC4 outmette un byte. Quindi dobbiamo confrontare l'algoritmo del generatore di byte RC4 con un vero e proprio algoritmo di generatore di byte casuali Un vero e proprio algoritmo di generatore di byte casuali produrrà qualsiasi byte nel set da 0 a 255, uniformemente. E il risultato atteso dal RC4 è che in ogni richiamo dell'algoritmo di aggiornamento dello stato, il byte di uscita potrebbe essere quasi come un valore uniformemente casuale dal set da 0 a 255. Si scopre che in una delle precedenti opere, Mantin e Shamir hanno dimostrato che anche se supponiamo che l'inizializzazione dell'algoritmo del RC4 sia un'inizializzazione uniforme (questo significa che non dipende dall'algoritmo chiave), se iniziamo a eseguire l'algoritmo di aggiornamento dello stato, allora il secondo byte di output di RC4 è più probabile che sia il 0 che significa, la probabilità che il secondo byte di output di RC4is 0 sia 2256, rispetto al 1256. E questo può essere dimostrato formalmente. Quindi, se volete vedere i dettagli formali esatti che come esattamente questa probabilità derivate potete fare riferimento ad uno dei riferimenti che stiamo seguendo. Quindi, ipotizzando che questo sia il caso, allora ecco un RC4distinguisher molto semplice che sa distinguere un byte di esempio generato dal generatore di byte RC4, da un campione generato da un generatore di byte davvero casuale. Immaginate quindi che il distinguo sia dato un campione?, e deve determinare se è prodotto dal generatore di byte RC4 o da un generatore di byte casuali. Quindi cosa fa il distinguo, visto che conosce il risultato di Mantin e Shamir, controlla solo il secondo byte di?, e poi se il secondo byte di? si scopre di essere 0, poi etichette che il campione? viene generato dal generatore di byte RC4. Altrimenti etichette il campione? di essere generato da un output davvero casuale. Ora calcoliamo il vantaggio distintivo del distinguo che abbiamo progettato. Se effettivamente il campione? che è una sequenza di byte viene generato dal RC4 per generatore è dato al distinguo allora la probabilità che effettivamente il secondo byte sia 0 è di 2256. Quindi la probabilità che il nostro distinguo quando dato un campione casuale generato dal generatore di byte RC4 lo etichetta come l'esito di RC4 è di 2256. Mentre se la sequenza di byte viene generata da un generatore di byte davvero casuale viene dato al distinguo, rispetto alla probabilità che il suo secondo byte sia 0 è in realtà 1 su 256. Questo significa in quel caso solo, con quella molto probabilità solo, il nostro distinguo finirà per etichettare una vera sequenza casuale di byte per essere un risultato di un RC4. Quindi qual è il vantaggio distintivo dell'aggressore in questo caso? Ebbene, la differenza assoluta è di 1256, che è una probabilità significativa. Ciò significa che non possiamo più sostenere che la sequenza di byte generati dal bytegenerator RC4 sia vicina alla sequenza di byte, che un generatore di byte davvero casuale avrebbe prodotto ed è per questo che questo RC4 non è più considerato sicuro. Per concludere, in questa lezione abbiamo visto su un livello molto alto alcune delle instantiazioni pratiche di pseudo generatore casuale. Poi abbiamo visto una costruzione basata su hardware, che chiamiamo come registro di turno di feedback lineare. Il registro dei turni di feedback lineare originale non è più utilizzato nella forma che è stato proposto, perché osservando il numero polinomiale di outputs, un avversario può scoprire l'intero stato così come i coefficienti di feedback e quindi poter prevedere tutti i successivi bit di output di LFSR. Ecco perché le moderne istanze di generatori casuali pseudo casuali basati sul registro dei turni di feedback introdugono una sorta di non - linearità che può essere fatta da diversi modi, come la nonlinearità sotto forma di coefficienti di feedback non lineari, bit di output non lineari e così via. Abbiamo anche discusso di una costruzione chiamata Trivium, basata su quel principio, e una seconda costruzione che abbiamo visto è la costruzione software che può essere implementata in software ed è super? veloce, ovvero RC4. Purtroppo abbiamo visto anche alcune delle vulnerabilità che sono state riportate in RC4 a causa delle quali non è più consigliabile utilizzare.