Introduction to Cryptography Part 2

Introduction:

We’ve discussed in the previous part Stream ciphers and how they are simple just by XOR the key bit stream with the message we get the cipher-text in this part I’ll continue this discussion by talking about Linear Feedback Shift Registers (LFSR) and Rivest Cipher 4 (RC4)

Linear Feedback Shift Registers ( LFSR )

a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

Wikipedia

LFSR parts (shift register, feedback function, output stream, tap sequences) The shift register is a sequence of bits, The feedback function in an LFSR has several names: XOR, odd parity, sum modulo 2. Whatever the name, the function is simple: 1) Add the selected bit values, 2) If the sum is odd, the output of the function is one; otherwise the output is zero. Table 1 shows the output for a 3 input XOR function.

So what this means is that an LFSR consist of clocked storage elements called Flip-Flop which is basically used to store state information the number of Flip-Flops is the degree of the LFSR Let’s take an example to see how this work.

Example 2.1: Consider LFSR with degree of 3 which means it has 3 flip-flops with initial values of s2,s1,s0 = (1, 0, 0)undefined

so the first clock_0 the FF_2 , FF_1, FF_0 = (1,0,0) will have the value of initial state the next clock_1 FF_2 , FF_1, FF_0 = (0,1,0) , the third clock_2 FF_2 , FF_1, FF_0 = (1,0,1) and so on

General LFSR

the general form of LFSR is shown in the figure below, the figure shows the LFSR can have m flip-flops and m possible feedback locations all combined with XOR operation , there’s a multiplexer in the feedback path which is defined by the feedback coefficient p_0, p_1, ….,p_m-1: if p_i = 1 then we have (closed switch) else p_i = 0 (open switch).

the next LFSR output can be computed like this: S_m = S_m-1 * P_m-1 + … + s_1*p_1 + s_0 * p_0 mod 2

Theorem 2.1: the maximum period generated by a LFSR is 2^n -1 where n is the number of bits.

Example 2.2 : consider the have n = 4 so the maximum period is 15.

the feedback path coefficient vector (p_n-1 …, p_0) can be represented as mathematical polynomial P(x) = x^m + P_m-1*X^m-1 + … + P_1 * x + P_0

For instance, the LFSR from the example above with coefficients (p_3 = 0, p_2 =0, p_1 = 1, p_0 = 1) can alternatively be specified by the polynomial x^4 + x + 1.

The following is LFSR implementation in C:

Rivest Cipher 4

RC4 Designed in 1987 by Ron Rivest of RSA Security, then reverse
engineered and leaked in 1994, RC4 has long been the most widely used
stream cipher.

RC4 has been used in countless applications, most famously in the first Wi-Fi encryption standard Wireless Equivalent Privacy (WEP) and in the Transport Layer Security (TLS) protocol used to establish HTTPS connections.

RC4 is a surprisingly simple algorithm. It consist of two algorithms: the Key Scheduling Algorithm (KSA) and the Pseudo-Random Generation Algorithm (PRGA). Both of these algorithms use array of 256 numbers that are both unique and range in value from 0 to 255. The KSA does the initial scrambling of the array based on the seed fed into it.

key-scheduling algorithm (KSA) to initialize the permutation
in the array S[], we have the key-length which is from 1<=key-length<=256, S[] will be filled with sequential values from 1-256 in each cell in the array, then the KSA algorithm will take care of scrambling the S[] based on the SEED array call it K[] it’s concatenation of the IV and the key. This is done with the following pseudo-cod.

by this pseudocode
     for i from 0 to 255
       S[i] := i
   endfor
   j := 0
   for i from 0 to 255
       j := (j + S[i] + K[i mod keylength]) mod 256
       swap values of S[i] and S[j]
   endfor

Now when keystream data is needed, the Pseudo-Random Generation Algorithm (PRGA) is used. This algorithm has two counters i, j which are both initialized to zero, the following pseudo-code is used:

  i := 0
  j := 0
  while GeneratingOutput:
      i := (i + 1) mod 256
      j := (j + S[i]) mod 256
      swap values of S[i] and S[j]
      K := S[(S[i] + S[j]) mod 256]
      output K
  endwhile

the following is RC4 implementation in python:

def KSA(key):
	keylength = len(key)
	S = list(range(256))

	j = 0 
	for i in range(256):
		j = (j + S[i] + key[i % keylength ]) % 256
		S[i], S[j] = S[j], S[i] # swap in python 

	return S


def PRGN(S):
	i = 0
	j = 0

	while True: 
		i = (i + 1) % 256
		j = (j + S[i]) % 256
		S[i], S[j] = S[j], S[i] # swap in python 
		
		K = S[(S[i] + S[j]) % 256]
		yield K	

def RC4(key):
    S = KSA(key)
    return PRGN(S)


if __name__ == '__main__':
	key = "Key"
	plaintext = "Text"

	key = [ord(k) for k in key]
	keystream = RC4(key)
	
	for c in plaintext:
		print ('%02x' % (ord(c) ^ next(keystream)))

Well that’s it for this part , please if you have any question or idea to improve my articles feel free to e-mail me on omarobaniessa@gmail.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s