Χρήστης:Κωστας

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Είμαι Ηλεκτρονικός Μηχανικός απο το ΤΕΙ ΚΡΗΤΗΣ Το Ε-mail μου είναι kdf@in.gr

Το ενδιαφέρων μου είναι πάνω σε σχεδιασμό συμμετρικών αλγορίθμων κρυπτογράφησης



Θελώ να μοιράστω μαζί σας την πρώτη σχεδίαση ενός απλου μοντέλου συμμετρικού κρυπταλγορίθμου


O Κρυπταλγόριθμος Hellas1

Ο hellas1 είναι μια πειραματική έκδοση ενός νέου αλγορίθμου που δημιουργήθηκε το 2005 για την ανάλυση χαρακτηριστικών τόσο της δομής feistel όσο και των επιμέρους στοιχείων.


Πίνακας περιεχομένων

[Επεξεργασία] Περιοχές Εφαρμογής

Ένας κρυπτογραφικός αλγόριθμος πρέπει να είναι κατάλληλος για ένα πλήθος εφαρμογών

• Κρυπτογράφησης δέσμης. Ο αλγόριθμος θα πρέπει να είναι αποτελεσματικός για κρυπτογράφηση αρχείων όσο και μιας συνεχόμενης ροής ψηφίων (bits) • Γεννήτρια τυχαίων ψηφίων .Ο αλγόριθμος θα πρέπει να είναι αποτελεσματικός στην παραγωγή μια σειράς από τυχαία ψηφία(bits) • Κρυπτογράφηση πακέτων . . Ο αλγόριθμος θα πρέπει να είναι αποτελεσματικός για την κρυπτογράφηση δεδομένα πακέτων • Συνάρτηση κατακερματισμού . Ο αλγόριθμος θα πρέπει να είναι αποτελεσματικός στο να μετατρέπεται σε μονόδρομη συνάρτηση κατακερματισμού.


[Επεξεργασία] Πλατφόρμες Ανάπτυξης

Ένας κρυπτογραφικός αλγόριθμος πρέπει να υλοποιήσιμος σε μια ποικιλία διαφορετικών πλατφορμών ανάπτυξης.

• Ειδικό Υλικό(Hardware) . Ένας κρυπτογραφικός αλγόριθμος πρέπει να είναι αποδοτικός σε VLSI υλικό. • Μεγάλους Επεξεργαστές. Ένας κρυπτογραφικός αλγόριθμος πρέπει να είναι αποδοτικός σε 32-bit επεξεργαστές με 4 kbyte πρόγραμμα . • Μεσαίου μεγέθους Επεξεργαστές . Ένας κρυπτογραφικός αλγόριθμος πρέπει να μπορεί να τρέχει σε μικροελεκτές και άλλους μικροεπεξεργαστές • Μικρούς Επεξεργαστές . Ένας κρυπτογραφικός αλγόριθμος πρεπει να μπορεί να υλοποιηθεί σε (Έξυπνες Κάρτες (smart cards).


[Επεξεργασία] Επιπλέων Απαιτήσεις

Ένας κρυπτογραφικός αλγόριθμος πρέπει να είναι κατάλληλος

• Ένας αλγόριθμος θα πρέπει να είναι απλός στον προγραμματισμό. Η εμπειρία με τον DES έδειξε ότι οι προγραμματιστές κάνουν συχνά λάθη υλοποίησης αν ο αλγόριθμος είναι πολύπλοκός. • Ο αλγόριθμος πρέπει να έχει επίπεδη και ομοιόμορφη περιοχή κλειδοχώρου επιτρέποντας οποιαδήποτε τυχαία ψηφιοσειρά να μπορεί να είναι το πιθανό κλειδί .Δεν θα πρέπει να υπάρχουν αδύναμα κλειδιά • Χρησιμοποίηση μίας σχεδίασης που είναι εύκολο να κατανοηθεί . Αυτό επιτρέπει την ανάλυση και αυξάνει την αυτοπεποίθηση στην ασφάλεια του αλγορίθμου.


[Επεξεργασία] Περιγραφή του αλγόριθμου - Αποφάσεις σχεδιασμού

Ο αλγόριθμός σχεδιάστηκε με μέγεθος πληροφορίας εισόδου 64 Bits ο λόγος που χρησιμοποίησα το μέγεθος αυτό είναι ότι ήθελα να είναι συμβατός με τους υπάρχων αλγορίθμους αλλά και να είναι εύκολο στο χειρισμό και να εμποδίζει την ανάλυση .Το μέγεθος του κλειδιού είναι 128bits το οποίο επιλέχθηκε σαν ελάχιστή πλέων τιμή ενός αλγορίθμου καθώς εμφανίζει μεγάλο παράγοντα εργασίας και καθιστά την επίθεση ωμής βίας μη πρακτική για τα τρέχων συστήματα . Από την πλευρά της σχεδίασης θα ήταν προτιμότερο για ένα μεταβλητό μήκος κλειδιού αλγόριθμό το οποίο θα εξυπηρετούσε διαφορετικές τάξης ασφάλειας εφαρμογές Επιλέχθηκε σαν σκελετός του αλγορίθμου ένα ισορροπημένο δίκτυο feistel δηλαδή τα δύο μισά του αλγορίθμου έχουν ίδιο μέγεθος ο λόγος που χρησιμοποίησα αυτή την δομή είναι ότι είναι η πιο αναλυμένη από πλευράς κρυπτανάλυσης και η πιο απλή και ο ίδιος αλγόριθμος χρησιμοποιείται για την κρυπτογράφηση και για την αποκρυπτογράφηση άρα από πλευράς υλικού δεν χρειάζεται άλλη σχεδίαση για την κρυπτογράφηση και άλλη για την αποκρυπτογράφηση. Τα ισορροπημένα δίκτυα από πλευράς κρυπτανάλυσης έχουν εμφανίσει καλύτερα κρυπτογραφικά στοιχεία ασφάλειας. Επέλεξα να έχει μεταβλητό αριθμό γύρων για να μπορέσω να μελετήσω κάποια χαρακτηριστικά όπως το φαινόμενο χιονοστιβάδας (κάθε δεξιό Bit εισόδου επηρεάζει κάθε αριστερό Bit εισόδου) και επιπλέων για να έχω την επιλογή διαφορετικών χρόνων εκτέλεσης του αλγορίθμου άρα και ταχύτητας του συνολικού αλγορίθμου. Η μη αναστρέψιμη συνάρτηση F σχεδιαστικέ για ασφάλεια και ταχύτητα Επέλεξα τέσσερα 8*32bit S-box αντί για ένα είναι για να αποφύγω το φαινόμενο της συμμετρίας πχ( Κάποια bytes της εισόδου είναι ίσα άρα και στην έξοδο εμφανίζει το S-box κάτι που διαδίδεται στους επόμενους γύρους το οποίο δημιουργεί την ικανότητα μιας στατιστικής επίθεσης). Ο λόγος που χρησιμοποίησα μέγεθος S-box 8*32 είναι διότι εμφανίζουν καλύτερη αντίσταση στην διαφορική κρυπτανάλυση από ότι κουτιά μικρότερου μεγέθους βέβαια αυτό τα κάνει πιο ευπρόσβλητα σε επιθέσεις γραμμικής κρυπτανάλυσης αλλά αυτή η αδυναμία μπορεί να αντιμετωπιστεί συνδυάζοντας την έξοδο των 4 κουτιών. Δεν χρησιμοποίησα παραπάνω μέγεθος διότι δεν θα ήταν αποδοτικά και πρακτικά σε υλοποίησης συστημάτων με μικρό χώρο αποθήκευσης όπως Έξυπνες κάρτες (κάθε κουτί έχει στοιχεία άρα κάθε ψηφίο επιπλέων διπλασιάζει το μέγεθος) Τα στοιχεία των S-box είναι τα αποτελέσματα ειδικών συναρτήσεων bent τα οποία παρουσιάζουν υψηλή μη γραμμικότητα σύμφωνα με τον μετασχηματισμό Walsh-Hardmand .Επέλεξα τα S-box που χρησιμοποιήθηκαν στον σχεδιασμό του CAST αλγορίθμου σαν πρότυπο σχεδίασης. Η πύλη που χρησιμοποίησα για το συνδυασμό είναι η πύλη Xor ό λόγος που την χρησιμοποίησα σαν ένα στοιχείο συνδυασμού είναι ότι παρουσιάζει ισοπίθανη τιμή άσσων και μηδενικών 50% όταν έχω 0 στην είσοδο ή 1 από την πλευρά του παρατηρητή ενώ η πύλη And εμφανίζει μια ακολουθία μηδενικών με πιθανότητα 75% και η πύλη OR εμφανίζει με πιθανότητα 25% μηδενικά.. Ο αλγόριθμος παραγωγής κλειδιών σχεδιάστηκε για να διατηρήσει ολόκληρη την εντροπία του κλειδιού και για να διανείμει την εντροπία ομοιόμορφα στα υποκλειδιά .Η αρχική ιδέα ήταν να κάνω τον αλγόριθμό αυτών πιο πολύπλοκο με το να εισάγω Μετασχηματισμούς ανάμιξης που είναι η βασική καρδιά του IDEA ( πολλαπλασιασμούς πρόσθεσης και Xor ) και εξαρτημένες περιστροφές από τα δεδομένα και το κλειδί (DDR-KDR) του αλγορίθμου RC5 . Τελικά περιορίστηκα στο να φτιάξω ένα επαναληπτικό αλγόριθμο χρησιμοποιώντας σαν κρυπτογραφικό μετασχηματισμό την συνάρτηση F και της μεταβλητές περιστροφές επιλογής κλειδιού. Ανακάλυψα στην συνέχεια ότι αυτή το κριτήριο της σχεδίασης το είχαν χρησιμοποίηση άλλοι δημοφιλής κρυπταλγόριθμοι.. Χρησιμοποίησα την επαναληπτική δομή του αλγορίθμου (τέσσερις περιστροφές για την εξαγωγή κάθε υποκλειδιού) για να αυξήσω την σύγχυση και διάχυση των χαρακτηριστικών του κλειδιού στα υποκλειδια και για να εμποδίσω την κρυπτανάλυση του αλγορίθμου στην περίπτωση που ο κρυπταναλυτής έφθανε στην εξαγωγή του κλειδιού του τελευταίου γύρου (Διαφορική κρυπτανάλυση).Θα ήταν αδύνατο για αυτόν να προχωρήσει στην ανάκτηση των υποκλειδιών των προηγούμενων γύρων. Χρησιμοποίησα εξαρτημένες περιστροφές βάση των bytes του κλειδιού δανειζόμενος στοιχεία από τις M-sequence. Επέλεξα να προϋπολογίζεται πρώτα η μήτρα κλειδιών και μετά να τρέχει ο κύριο αλγόριθμος και αυτό το έκανα για λόγους ταχύτητας..


5.5 Τεστ χιονοστιβάδας(Avalanche) και Ασφάλεια Hellas1

Ο αλγόριθμος Hellas1 σχεδιάστηκε σε δύο μορφές με ιδιαίτερο χαρακτηριστικό την ικανοποίηση του κριτηρίου της χιονοστιβάδας. Το τεστ το έφτιαξα με το εργαλείο matlab γεμίζοντας ένα πίνακα με όλες τις πιθανές εισόδους και εξόδους .

Στην πρώτη σχεδίαση ο αλγόριθμος έφθασε να εκπλήρωση το κριτήριο αυτό στους 16 γύρους . Στην δεύτερη σχεδίαση του ο αλγόριθμός έφθασε για το συντριπτικό αριθμό Test vectors να εκπληρώσει το κριτήριο αυτό στους 9 γύρους. Αυτό είναι ικανοποιητικό σε σχέση με τον αλγόριθμό Des ο οποίος εμφανίζει το φαινόμενο αυτό στους 16 γύρους .

Για οποιαδήποτε μορφή κρυπτανάλυσης από την σχεδιαστική πλευρά απαιτείται η κατασκευή ενός μινι αλγόριθμου για απλοποίηση και μέτρηση καθώς επίσης και η φιλοσοφία της ανάλυσης κάθε κρυπτογραφικού στοιχείου ξεχωριστά και της λεγόμενης αφαιρετικής λειτουργίας (αφαιρούμε όλα τα στοιχεία εκτός από ένα και παρατηρούμε την ασφάλεια του αλγορίθμου βασιζόμενη μόνο σε αυτό το στοιχείο αν τα υπόλοιπα έχουν παρακαμφτεί πχ Twofish)

Για την διαφορική κρυπτανάλυση τα S-box το οποία είναι το μόνο μη γραμμικό στοιχείο στον κρυπταλγόριθμο  παρουσιάζουν υψηλή μη γραμμικότητα και επίπεδη κατανομή ζευγών εισόδου και εξόδου και αυτό δεν επιτρέπει την εύρεση ενός  διαφορικού χαρακτηριστικού και ενός γραμμικού χαρακτηριστικού.Οι bent συναρτήσεις παρουσιάζουν την υψηλότερη μη γραμικκιτητα σε ένα S-box και αυτό καθιστά δύσκολή την γραμμική κρυπτανάλυση.

[Επεξεργασία] Συμπεράσματα

Ο Hellas1 αποτελεί ένα πειραματικό μοντέλο ενός σύγχρονου κρυπταλγορίθμου τμήματος. Δεν προτείνεται για χρησιμοποίηση μιας και δεν είναι ολοκληρωμένη έκδοση. Η κρυπτογραφική δύναμη ενός αλγορίθμου δεν βρίσκεται στην σχεδίαση του αλγορίθμου αλλά βρίσκεται στην ανάλυση του.


[Επεξεργασία] Σχεδίαση 2

Σχήμα 5.4 Γύρος κρυπτογράφησης
Μεγέθυνση
Σχήμα 5.4 Γύρος κρυπτογράφησης
Σχήμα 5.5 Γύρος αποκρυπτογράφησης
Μεγέθυνση
Σχήμα 5.5 Γύρος αποκρυπτογράφησης
Σχήμα 5.6 Συνάρτηση F
Μεγέθυνση
Σχήμα 5.6 Συνάρτηση F
Σχήμα 5.7 Αλγόριθμος γεννήτριας κλειδιών
Μεγέθυνση
Σχήμα 5.7 Αλγόριθμος γεννήτριας κλειδιών


Ο κώδικας έτρεξε σε matlab R14




[Επεξεργασία] Τc.m

% Αυτό είναι μια δοκιμαστική έκδοση ενός νέου κρυπτογραφικού αλγορίθμου

Ch=input('Πατηστε Ε για κρυπτογραφηση και D για αποκρυπτογραφηση ','s');

% plaintext_hex = {'00' '11' '22' '33' '44' '55' '66' '77'};

 %       plaintext = hex2dec (plaintext_hex);

% plaintext =double('12345678') %plaintext = [53,54,55,56,18,120,93,28] plaintext = [165 146 10 37 30 158 155 138] key = double('1111111111111111');

if (Ch == 'E')

  ciphertext = cipher (plaintext,key,Ch)

else

   dec_plaintext = cipher (plaintext,key,Ch)

end


[Επεξεργασία] Cipher.m

function ciphertext = cipher (plaintext,key,Ch) global N N= input('Posous girous ? ')

Skeys= Sbkeygeneration(key,Ch,N);

for i=1:1:4

   Bl(i)=plaintext(i);
   Br(i)=plaintext(i+4);

end for i=1:1:N

   s=Skeys(i,:);
   xresult=F(Br,s);
   
   if length(xresult) == 1
       kxt=dec2hex(xresult);

k=0;

if length(kxt)<8

           kx=[zeros(1,8-(length(kxt))),kxt];
       else
           kx=kxt;
       end
       

for i=1:1:4

   for j=1:1:2
       k=k+1;
       b(i,j)=kx(k);
       end
       end
       
       for i=1:1:4
           b1(i)=hex2dec(b(i,:));
       end
       result=b1;
   else
      result=xresult; 
   end
   

Blx=bitxor(result,Bl); B=Br; Br=Blx; Bl=B; end ciphertext= [Br,Bl]; end



[Επεξεργασία] Sbkeygeneration.m

function Skeys = Sbkeygeneration(key,Ch,N)

global skys; global tempx; skys=key; regist=[0,0,0,0]; for round=1:1:N

   if round>1
       rot1(skys);% rotate
   end
   
   for j=1:1:4
       key1=choicebitselction(skys,j);
    regist=bitxor(regist,key1);
       xresult=F(regist,key1);
   regist=xresult;
   regist= rot2(key1,regist); 

end

   kx=dec2hex(xresult);

k=0; for i=1:1:4

   for j=1:1:2
       k=k+1;
       b(i,j)=kx(k);
       end
       end
       
       for i=1:1:4
           tp(i)=hex2dec(b(i,:));
       end
       

Skeys(round,:)=tp; end

if (Ch == 'D')

   j=1;
   if N == 1
   else
       
   for i=16:-1:1
       temp(j,:)=Skeys(i,:);
       j=j+1;
   end
   Skeys=temp;

end end end


[Επεξεργασία] rot1.m

function rot1(skys)

A=bitxor(skys(1),skys(4)); offset=bitxor(skys(16),A);

temp=dec2bin(skys);

k=0; y=length(temp(1,:)); for i=1:1:16

   for j=1:1:length(temp(1,:))
       k=k+1;
       kx(k)=temp(i,j);
       end
       end

for i=1:1:offset

for j=1:1:length(kx)

   if j==length(kx)
       b(j)=kx(1);
   else
   b(j)=kx(j+1);

end end kx=b; end

k=1; for i=1:1:16

   for j=1:1:y
       tmp(i,j)=kx(k);
       k=k+1;
   end

end skeys=bin2dec(tmp)'; end


choicebitselction.m

function key1 = choicebitselction(skys,j)

if j==1

    b=1;
elseif j ==2 
        b=5;
    elseif j==3
        b=9;
    elseif j==4
        b=13;
    end
   

key1(1)=skys(b); key1(2)=skys(b+1); key1(3)=skys(b+2); key1(4)=skys(b+3);

end


[Επεξεργασία] rot2.m

function regist = rot2 (key1,regist)

A=bitxor(key1(1),key1(4)); offset= bitxor(bitor(key1(2),A),key1(3));


kxt=dec2hex(regist); k=0;


if length(kxt)<8

           kx=[zeros(1,8-(length(kxt))),kxt];
       else
           kx=kxt;
       end
       

for i=1:1:4

   for j=1:1:2
       k=k+1;
       b(i,j)=kx(k);
       end
       end
       
       for i=1:1:4
           tp(i)=hex2dec(b(i,:));
       end

z=length(tp); temp=dec2bin(tp); k=0; y=length(temp(1,:));

for i=1:1:4

   for j=1:1:length(temp(1,:))
       k=k+1;
       ky(k)=temp(i,j);
       end
       end

for i=1:1:offset

for j=1:1:length(ky)

   if j==length(ky)
       b(j)=ky(1);
   else
   b(j)=ky(j+1);

end end ky=b; end

k=1; for i=1:1:z

   for j=1:1:y
       tmp(i,j)=ky(k);
       k=k+1;
   end

end regist=bin2dec(tmp)'; end


[Επεξεργασία] F.m

function xresult = F(Br,Skeys) load C:\MATLAB6p5\work\ptix\sboxs1.mat x=Br; Br =bitxor(x,Skeys); S=Br(1); P=Br(2); Q=Br(3); R=Br(4); if S == 0

   S=1;

end if P == 0

   P=1;

end if Q == 0

   Q=1;

end if R == 0

   R=1;

end

sout1= sb1(S); sout2=sb2(P); sout3=sb3(Q); sout4=sb4(R); temp=bitxor(sout1,sout2); temp1=bitxor(sout3,sout4); xresult=bitxor(temp,temp1); end

[Επεξεργασία] Εξωτερικές Συνδέσεις