Newsgroup: it.comp.sicurezza.crittografia
Titolo: Algoritmo IDEA

Salve a tutti,
volevo chiedere alcune spiegazioni per una tesina che sto facendo x
l'universita relativa alla crittografia.
Dunque..l'algoritmo IDEA prende la chiave a 128 bit e la divide in 8
blocchi da 16 bit ciascuno. Poi fa 8 round (cicli??) in cui prende
solamente 6 sottochiavi e nel 9° round prende 4 sottochiavi per un
totale di 52 sottochiavi utilizzate.
Chiedo io...ma le restanti sottochiavi???non le usa oppure le usa e io
non ho capito dove se le mette???
Inoltre chiedo se mi potete confermare che a oggi non risultano
fattibili attacchi a forza bruta.
grazie mille
ciao ciao

 ciao ciao
-- 
Saluti, Federico - 
http://www.quaqo.org
Ducati SuperSport 750 i.e. "Duchessa rossa"

> Non capisco cosa intendi per restanti sottochiavi...
Dunque....128 bit che vengono divisi in 8 blocchi da 16 bit.
Ad ogni iterazione vengono usate le prime 6 chiavi di ogni round.
I round sono 8...x cui 8x6=48 più il nono round che pero sono solo 4
le chiavi...x cui 48+4 = 52 come hai giustamente detto.
Pero i blocchi di sottochiavi iniziali sono 8 da 16 bit. Ora mi
domando....se i blocchi sono 8....xkè lui usa solamente le prime 6
chiavi di ogni round??????
Le altre 2 chiavi di ogni round??????
Forse sono io che nn capisco.....

 Forse sono io che nn capisco.....
Perchè probabilmente non hai ben presente come funziona l'algoritmo.
Il key scheduling avviene prima dei round. Genera le 52 chiavi e poi
inizia le iterazioni.
-- 
Saluti, Federico - 
http://www.quaqo.org
Le FAQ sulla crittografia: 
http://kb.quaqo.org/criptofaq/

 inizia le iterazioni.
Siccome ho scaravoltato internet e google per cercare queste
informazioni ma nn le trovo da nessuna parte tu riesci a spiegarmi
come funziona sto key scheduling???oppure anche passarmi un link....
grazie mille....
ciao

 ciao


> come funziona sto key scheduling???oppure anche passarmi un link....
Dimenticavo:
http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm


giuliano ha scritto:

Dimentichi, come ha detto Quaqo, la rotazione a sinistra di 25 bit ad
ogni round, quindi la chiave viene in realtà utilizzata tutta.
Considera il seguente schema, dove ogni numero identifica un bit della
chiave. Inizialmente la chiave arriva così:
01234567891111111111222222222233333333334....1
          0123456789012345678901234567890....2
                                             7
Nel primo round vengono presi solo i primi 6 gruppi:
0123456...9
          6
Poi l'intera chiave viene ruotata di 25 bit a sinistra, quindi è come se
 nel secondo round la disposizione dei bit della chiave fosse così:
2222233333333334444444444555555555...10123456789111111111122222
5678901234567890123456789012345678...           012345678901234
Cioè il 25° bit della chiave originaria è adesso il 1° bit della chiave
ruotata. Ed il 24° bit diventa l'ultimo bit.
E così via...
Come vedi, alla fine degli 8 round la chiave ha subìto una rotazione di
25*8=200 bit, e tutti i suoi bit sono stati utilizzati almeno una volta
nelle iterazioni dell'algoritmo. Quindi non è come nel caso del DES, ad
esempio, dove 8 bit vengono scartati (la chiave è lunga 64 bit ma ne
vengono in realtà usati solo 56) senza mai usarli.
-- 
Ciao.
Leo.
Web: 
www.leonardomiliani.com
E-mail: 
leon...@leonardomiliani.com
Scegli software opensource - Choose opensource software

 Confermo, ma è coperto da brevetto.
Girellando per internet alla ricerca di info sull'IDEA, ho trovato questo:
http://www.ietf.org/ietf/IPR/ASCOM-IDEA
Estratto (tradotto):
"[...]IDEA(TM) è protetto dalle leggi internazionali sul diritto
d'autore ed è brevettato in molti Paesi.
Ma siccome Ascom vuol far sì che questo algoritmo altamente sicuro sia
largamente diffuso, l'utilizzo per fini non commerciali è libero."
Quindi si può usare per software freeware ed opensource ma non per fini
di lucro.


 Dimentichi, come ha detto Quaqo, la rotazione a sinistra di 25 bit ad
(snip)
Permettimi il "tu": sei uno dei pochi italiani che scrive correttamente il
mio nickname. :-)
In molti tendono a non leggere completamente, quindi a scrivere "quaquo": la
cosa è dannatamente fastidiosa! :-P


 
A parte che basterebbe dire a chi lo storpia che esiste il
"copia-e-incolla" :-), cmq a me non piace distorcere i nick.
Parlando di nick e visto che mi hai chiesto il "tu", volevo dirit (in
via del tutto amichevole e goliardica, senza nessuna velatura di presa
in giro) che il tuo è curioso: vedo dal tuo sito che proviene dal tuo
cognome, ma comunque è curioso.
E per un toscano è anche difficile pronunciarlo perché quelle 2 "q" non
ti dico come rendono... :-)))


 ti dico come rendono... :-)))
Non solo per un toscano. :-)


Oh ragazzi cercate di avere pazienza...si vede che sono stupido!!!!!
Ma proprio nn ci salto fuori...
Dunque ricapitoliamo....
Facciamo la chiave così:
0123456789.........con bit fino a arrivare a 127 (visto che parto da
zero).
Dopodichè divido questi 128 bit in 8 gruppi da 16 bit.
Perciò
0123456789101112
1314151617181920
2122232425262728                      eccc......fino a arrivare a 8
blocchi
Quando dite che lui prende i primi 6 gruppi di ogni round, lui fa:
012345                  che sono i primi 6 bit del primo gruppo da 16
bit
oppure
0122 e poi nn so cosa....             che rappresenta il primo bit di
ogni gruppo da 8. Infatti 0 è il primo bit del primo..1 il primo bit
del secondo, 2 del terzo e cosi via
Dopodichè lui ha preso sti 6 bit...li intrippa come vuole lui con XOR
ADD e MUL e poi shifta la chiave di 25 bit
Trasformandola in:
7181920212223242
5262728293031323
3343536373839404                      eccc......fino a arrivare a 8
blocchi
Il 7 è il bit che compare alla posizione 25.
Dopodichè si ritorna al passaggio di prima.
Spero sia tutto chiaro. Vi prego chiaritemi sto dubbio xkè nn so piu
che fare.
grazie
giuliano

 ADD e MUL e poi shifta la chiave di 25 bit
No. Leggi meglio quei link.
-- 
Saluti, Federico - 
http://www.quaqo.org


 No... Lui prende: I, II, III, IV, V e VI; scarta: VII, VIII.
Tu hai detto:
"Il key scheduling avviene prima dei round. Genera le 52 chiavi e poi
inizia le iterazioni."
ok...quindi in questo al primo giro, durante la generazione delle
chiavi, prende i valori 0, 16, 32, 48, 64, 80, 96, 112.
Giusto???
Finito il primo giro lui fa lo shift di 25 posizioni e ridivide la
chiave ottenuta di nuovo in 8 blocchi sempre da 16 bit.
Al secondo passaggio prende i valori che corrispondono alla posizione
ora occupata da 1, 17, 33, 49, 65, 81, 97, 113 e via dicendo.
Confermi????

 Confermi????
No. Stai "creando" sottochiavi da 8 bit.
Lo ri-ri-ri-peto:
Hai una chiave da 128 bit:
1. la dividi in 8 blocchi da 16: questi 8 blocchi sono le
   prime 8 sottochiavi;
2. Finchè non ottieni 52 sottochiavi:
   fai uno shift di 25 bit, ridividi i risultanti 128 bit in
   altri 8 blocchi: sono le successive 8 chiavi.
Cosa c'è di non chiaro?


 K1,6 = |80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|
Scusa ma se la chiave a 128 bit xkè tu adesso ne hai usati solo
96???????????????
Oh ragaz x voi sarà elementare ma vi giuro che non riesco a
capire........
Visto che divide la chiave in 8 blocchi xkè non fa anche K1,7 e
K1,8??????????

 K1,8??????????
Perchè quei bit li usa per K2,1 e K2,2.
Per curiosità: in cosa ti stai laureando e qual è il titolo della tesina?


> Per curiosità: in cosa ti stai laureando e qual è il titolo della tesina?
Mi sto laureando in Informatica....la tesina è sulla crittografia e
firma digitale ed è per l'esame di Complessità.
Per la crittografia simmetrica ho scelta l'algoritmo IDEA.
Per la crittografia asimmetrica ho scelta l'algoritmo RSA.
Per la firma digitale ho scelto le funzioni hash SHA e MD.
Per quanto riguarda IDEA direi di aver capito....
perciò lui prende in input la chiave, la divide in 8 blocchi da 16
bit...dopodichè prende i primi 6 bit (da K1,1 a K1,6). Fa uno shift
left di 25 posizioni e ridivide la chiave in 8 blocchi da 16 bit.
Prende sempre i primi 6 bit che in questo caso saranno poi K1,7, K1,8
K2,1 K2,2 K2,3 K2,4.
L'unico dubbio che mi è rimasto è questo...è stato detto che gli 8
round più l'half round li fa sulla chiave. Però ho letto da qualche
parte che li fa anche sul testo.
Ora sono due 8 round più l'halft separati...cosa che mi sembra più
giusta oppure ho capito male io.
Grazie x l'aiuto e la pazienza....:))

 giusta oppure ho capito male io.
Mi pare che guardando il diagramma a blocchi dell'IDEA qui:
http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm
si veda solo che sui blocchi di testo in chiaro esegue uno scambio fra
il blocco 2 ed il blocco 3 durante i vari round (si vede infatti che le
pipe di 16 bit l'una ingresso ai blocchi numerate 1-2-3-4 all'uscita del
round diventano 1-3-2-4). Stessa inversione avviene all'uscita del
semi-round finale.
Di shifting sul testo in chiaro non ne so.


 Di shifting sul testo in chiaro non ne so.
No infatti...lo shifting lo fa solo sulla chiave. Pero quaqo ha
scritto in un post precedente:
"Sono 8 iterazioni, da 6 chiavi l'una e un "half-round" da 4 chiavi."
Perciò significa che prima fa 8 iterazioni + l'half round e lo shift
sulla chiave....e poi sul testo in chiaro fa solo le iterazioni.
Giusto????

 Giusto????
No. Il senso della mia frase era che ad ogni round vengono "consumate" 6
chiavi, per ogni half-round 4.
Non dava nessuna informazione sull'implementazione, ma solo sull'uso delle
chiavi.
Infatti IDEA puo' essere implementato in più d'un modo.
Io ti consiglio di espandere la chiave nelle 52 sottochiavi prima di
iniziare la cifratura.
In questo caso l'implementazione sarebbe:
- key schedule
- round         * 8
- half-round    * 1


quaqo wrote:
[...]
Aggiungo, così al volo: per il key-schedule potresti adirittura crearti una
hash-table; ma se ti stai laureando in informatica lo saprai senz'altro
meglio di me.


 Per la firma digitale ho scelto le funzioni hash SHA e MD.
(snip)
Complimenti. :-)


 ma se ti stai laureando in informatica lo saprai senz'altro meglio di me.
Noto una punta di ironia...non è che se uno si sta laureando significa
implicitamente che la crittografia sia il suo forte...caso mai gli
interessano di piu i database oppure la programmazione oppure le
reti....però si sa all'università non è che gli esami li scegli...a me
tocca questo e cerco di farlo:
1) nel modo migliore;
2) usando argomenti interessanti anche se sono un po più difficili;
Potevo portare un altro algoritmo come il DES (che sicuramente offre
più documentazione) ma ho preferito sbattermi un po di più anche se
incontro mille difficoltà!!!!
Tra l'altro al corso universitario neanche è stato trattato come
argomento.
Poi se l'ironia nn voleva esserci allora lascia perdere quello che ho
scritto.
Giuliano

 scritto.
Qui c'hai preso; vada così.


 A quel punto applica l'half-round.
Ok...penso di srci!!!!
In sintesi...parte il primo round con la chiave intera.
La chiave viene divisa in 8 blocchi da 16 bit.
Vengono presi i primi 6 blocchi di chiave e il primo blocco in chiaro
da 64 bit che viene diviso in 4 parti da 16 bit.
A sto punto fa tutte le sue operazioni producendo un output che poi
diventa l'input del secondo round con la chiave shiftata di 25 bit a
sx.
E' corretto????

 E' corretto????
No perchè ti devi ricordare di usare le due sottochiavi "avanzate" dal primo
round (hai diviso la chiave in 8, ma ne hai usate solo 6).
Ti riconsiglio di considerare il key-scheduling a parte per due motivi:
i)  Una volta che hai generato tutte le sottochiavi, puoi
    semplicemente iterare 8 funzioni "round" e una half-round, passando
    le sottochiavi in sequenza
ii) Le sottochiavi per la decifrazione vengono derivate da quelle per
    la cifratura: se usi delle funzioni a parte puoi riusarne il codice.
    Infatti la decifratura a quel punto consisterà in:
     - key schedule uguale alla cifratura (stessa funzione)
     - derivazione chiavi di decifratura (input: le sottochiavi per
       cifrare; output: quelle per decifrare)
     - vari round di decifrazione


      - vari round di decifrazione
        Decifra(Sottochiavi_Decif(Sottochiavi_Cif), testoCifrato)
Mentre per cifrare:
        Cifra(Sottochiavi_Cif(chiave128bit), testoInChiaro)


 Decifra(Sottochiavi_Decif(Sottochiavi_Cif), testoCifrato)
Sarebbe:
Decifra(Sottochiavi_Decif(Sottochiavi_Cif(chiave128bit)), testoCifrato)
;-)


 Ok, quindi non fai (come avevo suggerito sopra) il key schedule a parte.
Secondo me qua c'è qls che tocca da qualche parte!!!!
In precedenza ti avevo chiesto se le 8 iterazioni dovevo farle prima
sulla chiave e poi sul testo e mi è stato detto di farle insieme,
quindi le 8 iterazioni le faccio contemporaneamente sul testo e sulla
chiave.
Poi mi dici che nn faccio il key scheduling.
Ma per fare sto key scheduling non devo fare le 8
iterazioni??????????????
Alla fine di ogni iterazione non c'è lo shift-left di 25 bit?????????
Se ho capito male io per favore spiegami passaggio x passaggio come se
lo spiegassi a un bambino di 5 anni. (come dice Denzel Washington in
Filadelfia)!!!!!!!

 
http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm
C'è un diagramma.
Tu su quale documentazione ti stai basando? Tagliamo la testa al toro, dicci
quali passaggi ti sono oscuri.


 Filadelfia)!!!!!!!
Sono convinto che un qualsiasi documento che spieghi come funziona IDEA te
lo possa spiegare meglio di me.
Non capisco se tu sei venuto qui avendo letto gli algoritmi, o se sei
arrivato con una vaga idea pensando che qualcuno potesse illustrarteli.
Perchè fin'ora abbiamo assunto il primo caso.
In caso la risposta giusta sia la due: non c'è niente di male, ma dillo
perbacco! :-P
Altrimenti si esce scemi.


 quali passaggi ti sono oscuri.
Ho una presentazione, direi fatta discretamente bene, trovata su
internet.
http://www.dia.uniroma3.it/~dispense/rota/Algoritmo_IDEA.pdf

 come funziona sto key scheduling???oppure anche passarmi un link....
Prima di venire qui a rompere le scatole il materiale su wikipedia
l'ho letto e riletto almeno 20 volte oltre a tutti i pdf che sono su
internet.
Forse sono io che nn capisco sto key scheduling...
Cmq sono arrivato qui con l'idea che qls avevo capito...ma che mi
sarebbe servita una qualche delucidazione...evidentemente sbagliavo....

 faccio????
Io non ho mai detto di non fare il left-shift: t'ho detto di fare il key
scheduling a parte e non assieme agli 8,5 round.
È chiaro che il key scheduling avrà un ciclo iterativo al suo interno ed è
quello che ho scritto; riporto ancora:
| Hai un> a chiave da 128 bit: 
| 
| 1. la dividi in 8 blocchi da 16: questi 8 blocchi sono le
|    prime 8 sottochiavi;
| 2. Finchè non ottieni 52 sottochiavi:
|    fai uno shift di 25 bit, ridividi i risultanti 128 bit in
|    altri 8 blocchi: sono le successive 8 chiavi.
È l'n-esima volta che lo riporto. Cosa c'è di non chiaro?


 
http://www.dia.uniroma3.it/~dispense/rota/Algoritmo_IDEA.pdf
Tombola. Ho trovato il tuo problema: quella presentazione.
Effettivamente ad una prima lettura dell'unica diapositiva riguardande il
key schedule ("IDEA – Gestione della chiave (1)"), si ha l'impressione che
IDEA scarti 4 sottochiavi se uno già non conosce l'algoritmo.
In realtà non è così: facendo un left-shift la chiave la usi tutta.
Io t'ho proposto di usare un key-schedule esterno ai round proprio per
questo.
Il risultato è lo stesso ma è concettualmente molto più semplice da capire,
nonchè più efficiente da implementare per i vari motivi già citati.


 sarebbe servita una qualche delucidazione...evidentemente sbagliavo....
Su usenet a volte non si capiscono i toni, ma ribadisco che non ti sto
assolutamente attaccando. Te l'ho già chiarito questo rispondendo al
messaggio "Noto una punta di ironia...".
Non vorrei che ti stesse rivenendo il dubbio, perchè nelle tue risposte noto
un tono stizzito. :-P
E vediamo di risolverlo sto problema. Se mi dai il tuo indirizzo email ti
spedisco una scansione dell'algoritmo di IDEA, key-schedule compreso.
Va bene così? :-)


 spedisco una scansione dell'algoritmo di IDEA, key-schedule compreso.
giulia...@hotmail.com

 Se io ho questa chiave:
(snip)
No. Probabilmente mi spiego male io.
Ti sto inviando la scansione che sicuramente è più chiara di quanto io
riesca ad essere. Ragiona su quella e poi eventualmente partiamo da lì come
base.


Scusatemi se mi reintrometto...
Giuliano, perché non segui alla lettera il funzionamento dell'IDEA, così
da evitarti ulteriori confusioni?
Se il metodo di Quaqo ti suona astruso, segui quello dell'algoritmo
originale.
Considera un round come un passo del processo di codifica, fatto
all'interno di una funzione reiterata 8 volte.
Quindi:
1)
prendi 4 blocchi di 16 bit di testo in chiaro;
2)
prendi 6 blocchi di 16 bit di chiave (key-schedule);
3)
esegui il round;
4)
esegui lo shift della chiave a sinistra di 25 bit;
5)
torni al punto 3) per 8 volte;
6)
esegui il mezzo round;
7)
torni al punto 1) finché non hai finito tutto il testo in chiaro.


 originale.
L'ha detto: perchè non l'ha capito. :-)


 > da evitarti ulteriori confusioni?
Ci sono....ora ci sono...l'ho capito...probabilmente in uno dei tanti
post di quaqo sbagliavo io il senso del post e ciò mi suonava male e
non riuscivo a capire.
Ma ora è chiaro....
grazie mille a tutti!!!!!

 grazie mille a tutti!!!!!
In bocca al lupo! Facci sapere! :-D
