Spritz

Ο αλγόριθμος Spritz έγινε από τον Ronald Rivest και τον Jacob Schuldt και είναι μια βελτιωμένη έκδοση του RC4 και μπορεί να βγάλει αποτέλεσμα μετά από 24 γύρους υπολογισμών. Ακόμη οι πρώτες μελέτες δείχνουν πως χρειάζεσαι $281$ bytes πριν μπορέσει κάποιος να ξεχωρίσει την έξοδο του Spritz από μια τυχαία έξοδο. Ακόμη ο αλγόριθμος έχει μια συνάρτηση όπου δουλεύει σαν σφουγγάρι δηλαδή μπορεί να δεχτεί δεδομένα οποιαδήποτε στιγμή και από αυτά να βγάλει ψευδοτυχαίους αριθμούς. Για περισσότερες πληροφορίες για τους αλγόριθμους σφουγγάρια δείτε:«Duplexing the sponge: single-pass authenticated encryption and other applications» (PDF).

Αλγόριθμος Επεξεργασία

Ορολογία Επεξεργασία

Ν: Όλες οι τιμές στον Spritz ανήκουν στον δακτύλιο $\mod {N}$ , $Ζ Ν$ .

Για προεπιλογή έχουμε $N=256$

Πράξεις: Όταν έχουμε την πράξη + μεταξύ δυο αριθμών εννοούμε πως πρέπει να τους προσθέσουμε και στο αποτέλεσμα να εφαρμόσουμε την πράξη mod N. Το ίδιο γίνεται και τα υπόλοιπα σύμβολα
Μεταβλητές: Οι μεταβλητές είναι I,j,k,w,z και α. Κάθε φορά όπου καλείται η συνάρτηση WHIP το w αλλάζει και γίνεται πάντα σχετικά πρώτος με τον Ν, στο i προστίθεται η τιμή του w modulo N και οι j,k αλλάζουν ψευδοτυχαία. Το z κρατά το τελευταίο αποτέλεσμα του αλγορίθμου μας. Τέλος το α μας δίνει τον συνολικό αριθμό από nibbles όπου έχουν απορροφηθεί από την τελευταία φορά όπου καλέσαμε την SHUFFLE για το S.
Αντιμεταθέσεις: Όπως ο RC4, ο πίνακας S με μήκος Ν κρατά ανακατεμένα τα στοιχεία του $Ζ Ν$ .
Κατάσταση: Η κατάσταση του $Q t$ σημαίνει πως σε χρονική στιγμή t το αποτελείται από τις μεταβλητές I,j,k,w,z και α και από τον πίνακα S. Οι περισσότερες καταστάσεις όπου μπορεί ο αλγόριθμος να πάρει είναι $Ν 6 *Ν!$ . Ουσιαστικά το Q είναι μια δομή όπου έχει τις τιμές όλων των μεταβλητών.
Κλειδί: Το κλειδί κρυπτογράφησης Κ, είναι ένας πίνακας με μήκος L και τα στοιχεία του κλειδιού είναι ένα byte.
Nibbles: To nibble είναι το μισό byte και χωρίζεται σε χαμηλό, υψηλό nibble. Έστω b ένα byte, για να υπολογιστεί στον Spritz πρώτα υπολογίζουμε το temp=√N και μετά το D= $\lceil temp\rceil$ , στην συνέχεια το χαμηλό $nibble=b{\pmod {D}}$ , ενώ το υψηλό $nibble=\lfloor b/D\rfloor$ .

Ψευδοκώδικας Επεξεργασία

INITIALIZE STATE
1. i=j=k=z=a=0
2. w=1
3. for u = 0 to N-1
4. S[u]=u
ABSORB(I)
1. for u=0 to I.length-1
2. ABSORBBYTE(I[u])
ABSORBBYTE(b)
1. ABSORBNIBBLE(LOW(b))
2. ABSORBNIBBLE(HIGH(b))
ABSORBNIBBLE(x)
1. if a == $\lfloor$ N/2 $\rfloor$
2. SHUFFLE()
3. SWAP(S[a],S[ $\lfloor$ N/2 $\rfloor$ + x])
4. a=a+1
ABSORBSTOP
1. if a == $\lceil$ N/2 $\rceil$
2. SHUFFLE()
3. a=a+1
SHUFFLE
1. WHIP(2 $\cdot \!\,$ N)
2. CRUSH()
3. WHIP(2 $\cdot \!\,$ N)
4. CRUSH()
5. WHIP(2 $\cdot \!\,$ N)
6. CRUSH()
7. a = 0
WHIP(r)
1. for u = 0 to r-1
2. UPDATE()
3. do w = w+1
4. until GCD(w,N)==1
CRUSH()
1. for u = 0 to $\lfloor$ N/2 $\rfloor$ - 1
2. if S[u] > S[N-1-u]
3. SWAP(S[u],S[N-1-u])
SQUEEZE(r)
1. if a>0
2. SHUFFLE()
3. P=ARRAY.NEW(r)
4. for u=0 to r-1
5. P[u]=DRIP()
6. return P
DRIP
1. if a>0
2. SHUFFLE()
3. UPDATE()
4. return OUTPUT()
UPDATE
1. i=i+w
2. j=k+S[j+S[i]]
3. k=i+k+S[j]
4. SWAP(S[i],S[j])
OUTPUT
1. z=S[j+S[i+S[z+k]]]
2. return z

Ανάλυση Ψευδοκώδικα Επεξεργασία

ABSORB: Δέχεται σαν είσοδο τον πίνακα i, ανανεώνει τον Spritz με βάσει το Ι, ο Spritz απορροφά το Ι κατά ομάδες μεγέθους [κάτω όριο του Ν/2] nibble την φορά, μετά από κάθε απορρόφηση ομάδας εκτελείται η συνάρτηση SHUFFLE. Ο Spritz μπορεί να απορροφήσει στοιχεία ακόμη και όταν έχει βγάλει και κάποια έξοδο αυτό γίνεται επειδή η συνάρτηση ABSORB ανανεώνει την τωρινή κατάσταση δεν την αντικαθιστά. Τέλος άμα καλέσουμε το ABSORB(Χ) και μετά το ABSORB(Υ) είναι ισοδύναμο με το να καλέσουμε το ABSORB(ΧΥ).
ABSORBBYTE: Ανανεώνει την τωρινή κατάσταση του Spritz με βάση του byte όπου δόθηκε χωρίζοντας το byte σε δυο nibbles και ανανεώνει την κατάσταση με βάση πρώτα το χαμηλό nibble.
ABSORBNIBBLE: Πρώτα ελέγχει αν το Spritz είναι γεμάτο από δεδομένα δηλαδή άμα το α == [με το κάτω όριο του Ν/2]. Αν είναι γεμάτο καλή την συνάρτηση SHUFFLE για να ανάμιξη τα δεδομένα και βάζεI στο α το 0. Τέλος ανανεώνει την κατάσταση με βάση το x όπου x είναι το nibble όπου δέχτηκε αυτό γίνεται με το να ανταλλάζεις το S[a] με το S[[κάτω όριο του Ν/2]+x].
ABSORBSTOP Αυτός ο αλγόριθμος είναι ίδιος με τον ABSORBNIBBLE με τη διαφορά ότι δεν κάνει στο τέλος την ανταλλαγή. Τέλος αυτή η συνάρτηση μπορεί να χρησιμοποιηθεί για να σπάσουμε δυο στοιχεία δηλαδή άμα κάνουμε το ABSORB(Χ) μετά το ABSORB() και τέλος το ABSORB(Y) θα είναι διαφορετικό από το ABSORB(ΧΥ).
CRUSH: Η συνάρτηση έχει μια μη αναστρέψιμη διαδικασία στην οποία χαρτογραφεί $2^{N/2}$ καταστάσεις σε μία. Αυτό γίνεται καθώς χωρίζει τον πίνακα S σε $N/2$ ζευγάρια και κάθε ζευγάρι το ταξινομεί με αύξουσα σειρά.
DRIP: Αυτή η συνάρτηση έχει ως στόχο να παράγει ψευδοτυχαίους αριθμούς. Κάθε φορά όπου καλείται η DRIP πρώτα καλεί την SHUFFLE, an θεωρηθεί ότι χρειάζεται, και κατόπιν ανανεώνει τον Spritz κάνοντας χρήση της UPDATE. Τέλος, παράγει ένα byte σαν έξοδο καλώντας την συνάρτηση OUTPUT.
INITIALIZE STATE: Τοποθετεί τον Spritz στο αρχικό του στάδιο. Βάζει τις πέντε μεταβλητές ίσες με το μηδέν, την w ίση με 1 και βάζει στην S τυχαία στοιχεία του συνόλου $Ζ Ν$ .
OUTPUT: Δέχεται ένα byte και το αποθηκεύει στο z. Κατόπιν επιστρέφει την τιμή του byte.
UPDATE: Η Update προχωρά το σύστημα στην επόμενη κατάσταση με το να προσθέτει το w στο i, κακτόπιν δίνει στο j και k τις επόμενες τιμές τους και με το να αλλάζει τo S[i] με το S[j]. Τέλος να σημειωθεί πως από την στιγμή όπου το w είναι σχετικά πρώτος με το Ν (δηλ. $\gcd(w,N)=1$ ) το i αλλάζει τιμές $\mod N$ .
WHIP: Η συνάρτηση έχει ως είσοδο το r και καλή την update r φορές. Να σημειωθεί ότι μεταβλητές παίρνουν νέες τιμές οι οποίες είναι παράγωγες της αρχικής τους τιμής. Τέλος σε κάθε whip το w παίρνει νέα τιμή η οποία είναι πάντα πρώτη σε σχέση με το Ν.
SHUFFLE: Η συνάρτηση καλεί την WHIP, CRUSH, WHIP, CRUSH και την WHIP. Με τις whip ανακατεύει την τωρινή κατάσταση ενώ με τις crush χρησιμοποιείτε για να μην μπορείς να αναγνωρίσεις τον χειρισμό της εισόδου.
SQUEEZE: Είναι η κύρια συνάρτηση που παράγει μια έξοδο. Η μεταβλητή r όπου δέχεται σαν είσοδος δείχνει τις πόσες εξόδους πρέπει να το δημιουργήσει. Το να καλέσεις την SQUEZE είναι σαν να καλείς την DRIP r φορές και να επιστρέφεις ένα πίνακα με r θέσεις.

Αλγόριθμος σφουγγάρι στον spritz Επεξεργασία

Στον spritz δεν χρησιμοποιείται ακριβώς ένας αλγόριθμος τύπου σφουγγαριού αλλά μια τροποποιημένη μέθοδός του. Ακολουθούν οι λόγοι για τους οποίους δεν είναι επακριβώς ο αλγόριθμος spritz ένας αλγόριθμος σφουγγαριού:

Το κύριο κομμάτι των συνιστωσών δεν είναι μια συμβολοσειρά από bits αλλά μια μετάλλαξη S.
Η κύρια κατάσταση περιέχει bytes από το S τα οποία έχουν αλλάζει θέσεις.
Ο πρωταρχικός στόχος της SHUFFLE είναι να χαρτογράφηση πολλά προς ένα.
Η παραγωγή της εξόδου κάνοντας χρήση της SQUEEZE είναι βασισμένη στην λειτουργία DRIP η οποία κάνει αλλαγές στην τοπική κατάσταση.
Ο spritz με την χρήση της ABSORBSTOP μπορεί να απορρίψει σύμβολα όπου δεν ανήκουν στο αλφάβητο

Ψευδοκώδικας για το σφουγγάρι Επεξεργασία

ENCRYPT(K,M)
1. KEYSETUP(K)
2. C=M+SQUEEZE(M.length)
3. return C
DECRYPT(K,C):
1. KEYSETUP(K)
2. M=C-SQUEEZE(M.length)
3. return M
KEYSETUP(K):
1. INITIALISESTATE(K)
2. ABSORB(K)

Ανάλυση ψευδοκώδικα για το σφουγγάρι Επεξεργασία

ENCRYPT: Δέχεται σαν είσοδο το Κ και το Μ. Χρησιμοποιεί τον αλγόριθμο KEY-SETUP για να δώσει την αρχική κατάσταση και να απορρόφηση το Κ, στην συνέχεια προσθέτει το υπόλοιπο του Ν σε κάθε byte του Μ με τα αντίστοιχα byte της εξόδου του SQUEEZE δημιουργώντας το κρυπτογραφημένο κείμενο C.
DECRYPT: Η διαδικασία της αποκρυπτογράφησης είναι ίδια εκτός ότι αλλάζει το Μ με το C και αντί να προσθέσουμε το υπόλοιπο του N το αφαιρούμε.
KEYSETUP: Αυτή η διαδικασία απλός ορίζει το κλειδί

Πρόσθετα για το σφουγγάρι Επεξεργασία

Γίνεται χρήση της πρόσθεσης-αφαίρεσης με το υπόλοιπο για να δουλεύει για όλα τα Ν ανεξάρτητος άμα είναι πολλαπλάσια του 2. Ακόμη άμα κάποιος θέλει να κρυπτογράφηση ένα IV(initialization vector)θα πρέπει να κάνει χρήση αυτού του αλγορίθμου

ENCRYPTWITHIV(K,IV,M)

KEYSETUP(K)
ABSORBSTOP
ABSORB(IV)
C = M + SQUEEZE(M.length)
return C

Προσθετες λειτουργίες Επεξεργασία

Συνάρτηση κατακερματισμού Επεξεργασία

Πρώτα καλεί την ABSORB με παράμετρο το Μ, στην συνέχεια καλεί την ABSORBSTOP για να μπει το τέλος του μηνύματος του Μ, έπεται καλεί την ABSORB με παράμετρο το r και επιστρέφει το SQUEEZE του r. Τέλος να σημειωθεί πως το άμα δεν χρησιμοποιούταν το r η μια 16 byte έξοδος θα ήταν απλός το πρόθεμα της 32 byte εξόδου.

HASH(M,r)

INITIALIZESTATE()
ABSORB(M);
ABSORBSTOP();
ABSORB(r)
return SQUEEZE(r)

DOMAIN SEPARATION-Συνάρτηση DOMHASH Επεξεργασία

DOMHASH(J,M,r)

INITIALIZESTATE()
ABSORB(J)
ABSORBSTOP()
ABSORB(M)
ABSORBSTOP()
ABSORB(r)
return SQUEEZE(r)

MAC Επεξεργασία

MAC(K,M,r)

INITIALIZESTATE()
ABSORB(K)
ABSORBSTOP()
ABSORB(M)
ABSORBSTOP()
ABSORB(r)
return SQUEEZE(r)

Πηγές Επεξεργασία

Ronald L. Rivest, Jacob C. N. Schuldt. «Duplexing the sponge: Spritz a spongy RC4-like stream cipher and hash function» (PDF).