Algoritmo A5
Possibile implementazione

L'algoritmo di seguito riportato rappresenta una possibile implementazione del vero algoritmo A5 utilizzato nelle reti GSM. NON é comunque garantita la sua autenticità e nemmeno il suo corretto funzionamento. E' stato riportato qui per completezza di informazione e semplice curiosità.

A cura di: M. Bresco, G. Pradal, E. Tomasco
Coordinamento: Prof. Alfredo De Santis
Sistemi di elaborazione dell'informazione (Sicurezza su Reti)
Università di Salerno - Anno Acc.1999-2000

Descrizione dell'algoritmo in PDL

(carica la chiave segreta Kc)

FOR ogni bit della chiave segreta from 1 to 64
	carica il bit nella corrispondente posizione nell'LFSR
END FOR
 
(Carica il numero di frame)
FOR ogni bit del numero di frame from 1 to 22
	shift_bits = f()
	FOR ogni registro i, from 1 to 3
		Esegui lo XOR del bit della chiave pubblica nell'LSB
		IF il bit i dello shift_bits is set
			THEN Shift
		END IF
	END FOR
END FOR
 
(produce entrambi gli stream di cifratura e decifratura)
FOR i from 1 to 2
 
	(esegui shift adizionali)
	FOR j from 1 to 100
		shift_bits = f()
	FOR ogni registro k from 1 to 3
		IF il bit k dello shift_bits is set
			THEN Shift
		END IF
	END FOR
 
	(output stram di 114 bits)
	FOR j from 1 to 114
		shift_bits = f()
		FOR ogni registro k from 1 to 3
			IF bit k of shift_bits is set
				THEN Shift
			END IF
		END FOR
		Output = XOR degli MSB di tutti e tre i registri
	END FOR
END FOR
 
 
 
Shift function f
 
BEGIN FUNCTION f
	FOR ogni registro i from 1 to 3
		Poni middle[i] = il bit 'medio' del registro i
	END FOR
	IF almeno due 'bit medi' sono 1
		THEN bit-complement code
	END IF
	RETURN code
END FUNCTION

Implementazione in linguaggio 'C' dell'algoritmo A5

/*
 * The following implementation of A5 is due to Mike Roe.
 *
 * Reading this program, note that:
 *
 * 1. Which bit of the key are loaded into which bits of the shift register
 * 2. Which order the frame sequence number is shifted into the SR (MSB first or LSB first)
 * 3. The position of the feedback taps on R2 and R3 (R1 is known).
 * 4. The position of the clock control taps. These are on the `middle' one, 
 *    it has been assumed to be 9 on R1, 11 on R2, 11 on R3.
*/

/*
 * Look at the `middle' stage of each of the 3 shift registers.
 * Either 0, 1, 2 or 3 of these 3 taps will be set high.
 * If 0 or 1 or one of them are high, return true. This will cause each of the
 * middle taps to be inverted before being used as a clock control. In all
 * cases either 2 or 3 of the clock enable lines will be active. Thus, at least
 * two shift registers change on every clock-tick and the system never becomes stuck.
*/

static int threshold(r1, r2, r3)
unsigned int r1;
unsigned int r2;
unsigned int r3;
{
	int total;

	total = (((r1 >>  9) & 0x1) == 1) +
		(((r2 >> 11) & 0x1) == 1) +
		(((r3 >> 11) & 0x1) == 1);
	if (total > 1)
		return (0);
	else
		return (1);
}

unsigned long clock_r1(ctl, r1)
int ctl;
unsigned long r1;
{
	unsigned long feedback;

	/* Primitive polynomial x**19 + x**5 + x**2 + x + 1 */
	ctl ^= ((r1 >> 9) & 0x1);
	if (ctl){
		feedback = (r1 >> 18) ^ (r1 >> 17) ^ (r1 >> 16) ^ (r1 >> 13);
		r1 = (r1 << 1) & 0x7ffff;
		if (feedback & 0x01)
			r1 ^= 0x01;
	}
	return (r1);
}

unsigned long clock_r2(ctl, r2)
int ctl;
unsigned long r2;
{
	unsigned long feedback;
 	/* Primitive polynomial x**22 + x**9 + x**5 + x + 1 */   
 	ctl ^= ((r2 >> 11) & 0x1);
	if (ctl){
		feedback = (r2 >> 21) ^ (r2 >> 20) ^ (r2 >> 16) ^ (r2 >> 12);
		r2 = (r2 << 1) & 0x3fffff;
		if (feedback & 0x01)
			r2 ^= 0x01;
	}
	return (r2);
}

unsigned long clock_r3(ctl, r3)
int ctl;
unsigned long r3;
{
	unsigned long feedback;
 	/* Primitive polynomial x**23 + x**5 + x**4 + x + 1 */
 	ctl ^= ((r3 >> 11) & 0x1);
	if (ctl){
		feedback = (r3 >> 22) ^ (r3 >> 21) ^ (r3 >> 18) ^ (r3 >> 17);
		r3 = (r3 << 1) & 0x7fffff;
		if (feedback & 0x01)
			r3 ^= 0x01;
	}
	return (r3);
}

int keystream(key, frame, alice, bob)
unsigned char *key;   /* 64 bit session key              */
unsigned long frame;  /* 22 bit frame sequence number    */
unsigned char *alice; /* 114 bit Alice to Bob key stream */
unsigned char *bob;   /* 114 bit Bob to Alice key stream */
{
	unsigned long r1;   /* 19 bit shift register */
	unsigned long r2;   /* 22 bit shift register */
	unsigned long r3;   /* 23 bit shift register */
	int i;              /* counter for loops     */
	int clock_ctl;      /* xored with clock enable on each shift register */
	unsigned char *ptr; /* current position in keystream */
	unsigned char byte; /* byte of keystream being assembled */
	unsigned int bits;  /* number of bits of keystream in byte */
	unsigned int bit;   /* bit output from keystream generator */

	/* Initialise shift registers from session key */
 	r1 = (key[0] | (key[1] << 8) | (key[2] << 16) ) & 0x7ffff;
	r2 = ((key[2] >> 3) | (key[3] << 5) | (key[4] << 13) | (key[5] << 21)) & 0x3fffff;
	r3 = ((key[5] >> 1) | (key[6] << 7) | (key[7] << 15) ) & 0x7fffff;

	/* Merge frame sequence number into shift register state, 
	 * by xor'ing it into the feedback path
	*/
	for (i=0;i<22;i++){
		clock_ctl = threshold(r1, r2, r2);
		r1 = clock_r1(clock_ctl, r1);
		r2 = clock_r2(clock_ctl, r2);
		r3 = clock_r3(clock_ctl, r3);
		if (frame & 1){
			r1 ^= 1;
			r2 ^= 1;
			r3 ^= 1;
		}
		frame = frame >> 1;
	}

	/* Run shift registers for 100 clock ticks to allow frame number to
	 * be diffused into all the bits of the shift registers
	*/
	for (i=0;i<100;i++){
		clock_ctl = threshold(r1, r2, r2);
		r1 = clock_r1(clock_ctl, r1);
		r2 = clock_r2(clock_ctl, r2);
		r3 = clock_r3(clock_ctl, r3);
	}
	
	/* Produce 114 bits of Alice->Bob key stream */
	ptr = alice;
	bits = 0;
	byte = 0;
	for (i=0;i<114;i++){
		clock_ctl = threshold(r1, r2, r2);
		r1 = clock_r1(clock_ctl, r1);
		r2 = clock_r2(clock_ctl, r2);
		r3 = clock_r3(clock_ctl, r3);
		bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01;
		byte = (byte << 1) | bit;
		bits++;
		if (bits == 8){
			*ptr = byte;
			ptr++;
			bits = 0;
			byte = 0;
		}
	}
	if (bits)
		*ptr = byte;

	/* Run shift registers for another 100 bits to hide relationship between
	 * Alice->Bob key stream and Bob->Alice key stream.
	*/
	for (i=0;i<100;i++){
		clock_ctl = threshold(r1, r2, r2);
		r1 = clock_r1(clock_ctl, r1);
		r2 = clock_r2(clock_ctl, r2);
		r3 = clock_r3(clock_ctl, r3);
	}
 
	/* Produce 114 bits of Bob->Alice key stream */
	ptr = bob;
	bits = 0;
	byte = 0;
	for (i=0;i<114;i++){
		clock_ctl = threshold(r1, r2, r2);
		r1 = clock_r1(clock_ctl, r1);
		r2 = clock_r2(clock_ctl, r2);
		r3 = clock_r3(clock_ctl, r3);
		bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01;
		byte = (byte << 1) | bit;
		bits++;
		if (bits == 8){
			*ptr = byte;
			ptr++;
			bits = 0;
			byte = 0;
		}
	}
	if (bits)
		*ptr = byte;
	return (0);
}