Proudová šifra A5/1
Jedná se o jednoduchou proudovou šifru využívanou při šifrování GSM hovorů. Šifrování a dešifrování probíhá identicky operací XOR klíče na hodnotu vstupu (otevřený text) na příslušném místě. Klíče se generují ve 228 bitových blocích.
Princip
Pro pochopení pomůže rozdělit proces generování klíče do několika kroků.
První krok
V rámci šifry se využívají tři lineární posuvné registry různých délek. Na registr lze pohlížet jako na pole nul a jedniček indexované od nuly.
První posuvný registr má délku 19 bitů. Důležitý je 8. časovací bit (indexujeme od nuly) a dále výpočetní bity na indexech 13, 16, 17, 18.
Druhý posuvný registr má délku 22 bitů. Důležitý je 10. časovací bit (indexujeme od nuly) a dále výpočetní bity na indexech 20, 21.
Druhý posuvný registr má délku 23 bitů. Důležitý je 10. časovací bit (indexujeme od nuly) a dále výpočetní bity na indexech 7,20, 21,22.
Počáteční hodnota v registrech je 0 na všech bitech.
V rámci tvorby programu je vhodné registry implementovat jako standardní pole celých čísel.
Druhý krok
V rámci komunikace s retranslační stanicí obdrží jak mobilní telefon, tak stanice, 64 bitový klíč pro dané sezení (tzv. session key).
S bity tohoto klíče se v následujících 64 iteracích operuje. Každá iterace algoritmu má následující podobu:
První registr se posune takto: na první pozici se zapíše hodnota XOR(13 bit registru, 16 bit registru, 17 bit registru, 18 bit registru, i-tá pozice klíče - indexujeme od nuly), kde i-tá pozice odpovídá aktuálnímu pořadí iterace (v rámci první iterace se vezme 1. bit, v rámci druhé 2. bit, atd. až do 64). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Druhý registr se posune takto: na první pozici se zapíše hodnota XOR(20 bit registru, 21 bit registru, i-tá pozice klíče - indexujeme od nuly), kde i-tá pozice odpovídá aktuálnímu pořadí iterace (v rámci první iterace se vezme 1. bit, v rámci druhé 2. bit, atd. až do 64). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Třetí registr se posune takto: na první pozici se zapíše hodnota XOR(7 bit registru, 20 bit registru, 21 bit registru, 22 bit registru, i-tá pozice klíče - indexujeme od nuly), kde i-tá pozice odpovídá aktuálnímu pořadí iterace (v rámci první iterace se vezme 1. bit, v rámci druhé 2. bit, atd. až do 64). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Třetí krok
Je funkčně naprosto identický s prvním krokem, pouze nepoužíváme 64 bitový klíč, ale 22 bitový klíč zvaný čítač rámců. Logicky je iterací pouze 22. Hodnotu čítače rámců si předá mobil s retranslační stanicí, následně se převede na binární hodnotu a ta se zapíše do 22 prvkového pole. Nyní se s ní operuje stejně jako výše.
Čtvrtý krok
V rámci tohoto kroku je situace trochu složitější. Registr se v tomto kroku posouvá pouze tehdy, pokud na jeho časovacím bitu je hodnota, která odpovídá většině hodnot v rámci časovacích bitů všech registrů. Tedy pokud je například u prvního registru na časovacím bitu nula, u druhého také, a u třetího jednička, tak u prvního registru dojde k posunu, u druhého také dojde k posunu, ale u třetího nikoli (neboť jedniček je menšina). Počet iterací tohoto kroku je 100.
Iterace mají následující formu:
První registr: pokud se v rámci iterace posouvá, zapisuje se na jeho první pozici hodnota XOR(13 bit registru, 16 bit registru, 17 bit registru, 18 bit registru - indexujeme od nuly). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Druhý registr: pokud se v rámci iterace posouvá, zapisuje se na jeho první pozici hodnota XOR(20 bit registru, 21 bit registru - indexujeme od nuly). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Třetí registr: pokud se v rámci iterace posouvá, zapisuje se na jeho první pozici hodnota XOR(7 bit registru, 20 bit registru, 21 bit registru, 22 bit registru - indexujeme od nuly). Všechny ostatní hodnoty se posunou o jeden bit doprava. Poslední hodnota z registru se zahazuje, v tuto chvíli s ní algoritmus nepočítá.
Pátý krok
V rámci tohoto kroku se již generuje proud klíče. Ten vzniká jako XOR hodnot posledních políček registrů před posunem (tj. těch hodnot, které se v předchozích krocích zahazovali).
Funkčně se v rámci tohoto kroku pracuje s registry identicky, jako v kroku předchozím (čtvrtém). Pouze počet iterací se liší, nyní jich je 228, což odpovídá velikosti generovaného klíče.
Generování delšího klíče
V rámci algoritmu se inkrementuje hodnota čítače rámců, vše ostatní zůstává stejné (klíč sezení). Algoritmus se vrací na první pozici a vše se opakuje znovu.
Implementace šifry
Následuje zjednodušená implementace šifry v jazyce Python verze 3.
#----------------------------------
#Uzitecne funkce pro dalsi pouziti:
#Vraci pole bitu z ciselne hodnoty
def bitfield(n):
return [1 if digit=='1' else 0 for digit in bin(n)[2:]]
#Funkce XOR
def xor(x, y):
return int(bool(x) ^ bool(y));
#-----------------------------------
#Class implements the A5/1 cipher
#Trida implementujici sifru A5/1
class a51cipher:
#First 19 bit linear shift register;
#Prvni 19 bitovy posuvny registr
lfsr1 = [0]*19;
#Second 22 bit linear shift register;
#Druhy 22 bitovy posuvny registr
lfsr2 = [0]*22;
#Third 23 bit linear shift register;
#Treti 23 bitovy posuvny registr
lfsr3 = [0]*23;
#Methods shifts the 1. registr, at the beginning it writes the value XOR(position 18, position 17, position 16, position 13) and in situation that inputVal > -1 also XOR inputVal
#Metoda posouva 1. registr, na zacatek pripisuje hodnotu XOR(pozice 18, pozice 17, pozice 16, pozice 13) a je-li parametr inputVal > -1 tak jeste XOR inputVal
def shiftFirst(self, inputVal=-1):
beginVal = xor(xor(xor(self.lfsr1[18],self.lfsr1[17]), self.lfsr1[16]), self.lfsr1[13]);
if(inputVal >= 0):
beginVal = xor(beginVal, inputVal);
for i in range(len(self.lfsr1) - 1, 0, -1):
self.lfsr1[i] = self.lfsr1[i-1];
self.lfsr1[0] = beginVal;
return;
#Methods shifts the 2. registr, at the beginning it writes the value XOR(position 20, position 21) and in situation that inputVal > -1 also XOR inputVal
#Metoda posouva 2. registr, na zacatek pripisuje hodnotu XOR(pozice 20, pozice 21) a je-li parametr inputVal > -1 tak jeste XOR inputVal
def shiftSecond(self, inputVal=-1):
beginVal = xor(self.lfsr2[20],self.lfsr2[21]);
if(inputVal >= 0):
beginVal = xor(beginVal, inputVal);
for i in range(len(self.lfsr2) - 1, 0, -1):
self.lfsr2[i] = self.lfsr2[i-1];
self.lfsr2[0] = beginVal;
return;
#Methods shifts the 3. registr, at the beginning it writes the value XOR(position 7, position 20, position 21, position 22) and in situation that inputVal > -1 also XOR inputVal
#Metoda posouva 3. registr, na zacatek pripisuje hodnotu XOR(pozice 7, pozice 20, pozice 21, pozice 22) a je-li parametr inputVal > -1 tak jeste XOR inputVal
def shiftThird(self, inputVal=-1):
beginVal = xor(xor(xor(self.lfsr3[7],self.lfsr3[20]), self.lfsr3[21]), self.lfsr3[22]);
if(inputVal >= 0):
beginVal = xor(beginVal, inputVal);
for i in range(len(self.lfsr3) - 1, 0, -1):
self.lfsr3[i] = self.lfsr3[i-1];
self.lfsr3[0] = beginVal;
return;
#The method for the first and second step of algorithm, it shifted registers with input values in array
#Metoda pro implementaci prvniho a druheho kroku algoritmu, posouva registry se vstupni podminkou v poli
def clockRegisters(self,keyArray, inSize):
if(len(keyArray) != inSize):
print("Wrong input lenght; Chybna velikost vstupu");
return;
for i in range(0, inSize):
self.shiftFirst(keyArray[i]);
self.shiftSecond(keyArray[i]);
self.shiftThird(keyArray[i]);
return;
#Fourth and fifth step of algorithm, it shifted the registers with special conditions
#Pro ctvrty a paty krok algoritmu, posouva registry dle specialnich podminek
def clockNTimes(self, number, printKeyStream = False):
for i in range(0,number):
if(printKeyStream == True):
print(str(i+1) + ". bit klice: " + str(xor(xor(self.lfsr3[22], self.lfsr2[21]), self.lfsr1[18])));
lfsr1B = self.lfsr1[8];
lfsr2B = self.lfsr2[10];
lfsr3B = self.lfsr3[10];
if(lfsr1B == 0 and (lfsr2B + lfsr3B <= 1)):
self.shiftFirst();
elif(lfsr1B == 1 and (lfsr2B + lfsr3B >= 1)):
self.shiftFirst();
#-----
if(lfsr2B == 0 and (lfsr1B + lfsr3B <= 1)):
self.shiftSecond();
elif(lfsr2B == 1 and (lfsr1B + lfsr3B >= 1)):
self.shiftSecond();
#-----
if(lfsr3B == 0 and (lfsr1B + lfsr2B <= 1)):
self.shiftThird();
elif(lfsr3B == 1 and (lfsr1B + lfsr2B >= 1)):
self.shiftThird();
#-----
return;
#Write all values in shift registers
#Vypise vsechny hodnoty posuvnych registru
def printLfsrAll(self):
outLsfr1 = "";
for i in range(0,len(self.lfsr1)):
outLsfr1 = outLsfr1 + str(self.lfsr1[i]);
outLsfr2 = "";
for i in range(0,len(self.lfsr2)):
outLsfr2 = outLsfr2 + str(self.lfsr2[i]);
outLsfr3 = "";
for i in range(0,len(self.lfsr3)):
outLsfr3 = outLsfr3 + str(self.lfsr3[i]);
print("LSFR1: " + outLsfr1);
print("LSFR2: " + outLsfr2);
print("LSFR3: " + outLsfr3);
return;
#Create an instance of A5/1 ciphery class
#Vytvori instanci tridy pro sifru A5/1
#Hodnotu si predaji retranslacni stanice a mobilni telefon
frameCounter = 3847115;
#Pro 5 iteraci, tj. 5 x 228 bitu klice:
for i in range(0,5):
test = a51cipher();
#Session key, Klic sezeni; generuje se dle hodnoty na SIM karte. Je stejny pro vsechny iterace
test.clockRegisters([0,1,0,0,1,1,1,0,0,0,1,0,1,1,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,1,0],64);
#Frame counter, citac ramu (hodnota prenesena mezi stanici a zarizenim)
test.clockRegisters(bitfield(3847115 + i),22);
#100 times clock
test.clockNTimes(100);
#228 bit key:
test.clockNTimes(228,True);
#Nyni by se mel cely algoritmus opakovat s prictenim 1 k hodnote framu
#test.printLfsrAll();