An RC4 state is a 256 bytes states with two 8-bit index pointers i and j denoted

Question

An RC4 state is a 256 bytes states with two 8-bit index pointers i and j denoted by (S, i, j). The
initial RC4 state is generated by KSA denoted by (S0, i = 0, j = 0).
An important feature of RC4 is that the RC4 state is reversible. That is, if (S*, i*, j*) = PRGAn
(S,
i, j), it has (S, i, j) = IPRGAn
(S*, i*, j*) where PRGA
denotes applying n rounds PRGA (same
for IPRGAn
) and IPRGA is the reverse algorithm of PRGA. This feature means that any former
RC4 state can be recovered from a lot later RC4 state by applying certain rounds IPRGA. Write code
to implement both the PRGA algorithm and the following IPRGA algorithm and design and
implement a way to confirm that any RC4 state can go forward by PRGA and backward by
IPRGA. I want this program in python

Explanation / Answer

The RC4 Algorithms:

1) Key-Scheduling Algorithm (KSA):

for i from 0 to 255

S[i] := i

endfor

j := 0

for i from 0 to 255

j := (j + S[i] + key[i mod keylength]) mod 256

swap(S[i],S[j])

endfor

Python code:

{

A = ord('a')

def info_num(text):

for c in text:

print(ord(c) - A, " ", end="")

print()

Implementation for Keystream:

def keystream(plain, key):

i = 0

length = len(plain)

result = ""

while i < length:

byte = (ord(plain[i]) - A + ord(key[i % 26]) - A) % 26

print(byte, " ", end="")

result += chr(byte + A)

i = i + 1

print()

print("text: ", result)

}

  

def KSA(key):

S = [c for c in range(256)]

j = 0

keylength = len(key)

for i in range(256):

j = (j + S[i] + key[i % keylength]) % 256

S[i], S[j] = S[j], S[i]

return S

  

  

2) Pseudo-Random Generation Algorithm (PRGA) :

i := 0

j := 0

while GeneratingOutput:

i := (i + 1) mod 256

j := (j + S[i]) mod 256

swap(S[i],S[j])

output S[(S[i] + S[j]) mod 256]

endwhile

3) Reverse Pseudo-Random Generation Algorithm (IPRGA) :

while GeneratingOutput:

swap(S[i],S[j])

j := (j - S[i]+256) mod 256

i := (i - 1+256) mod 256

output S[(S[i] + S[j]) mod 256]

endwhile

Python code:

def PRGA(data, S):

i = 0

j = 0

m = 0

length = len(data)

while m < length:

i = (i + 1) % 256

j = (j + S[i]) % 256

S[i], S[j] = S[j], S[i]

k = data[m] ^ S[(S[i] + S[j]) % 256]

print("%02X" % k, end="")

m += 1;

print()

def IPRGA(data, S):

i = 0

j = 0

m = 0

length = len(data)

S[i], S[j] = S[j], S[i]

while m < length:

j = (j - S[i]+256) % 256

i = (i - 1+256) % 256

  

k = data[m] ^ S[(S[i] + S[j]) % 256]

print("%02X" % k, end="")

m += 1;

print()

  

  

def rc4(data_text, key_text):

data = [ord(c) for c in data_text]

key = [ord(c) for c in key_text]

S = KSA(key)

PRGA(data, S)

IPRGA(data, S)

def test_keystream():

plain = "attackatdawn"

key = "kjcngmlhylyu"

info_num(plain)

info_num(key)

keystream(plain, key)

def test_KSA():

key = [97, 98, 99, 100, 101]

S = KSA(key)

print(S)

def test_rc4():

rc4("Plaintext", "Key")

test_keystream()

test_KSA()

test_rc4()

Proof to confirm that any RC4 state can go forward by PRGA and backward by
IPRGA:

Any RC4 state can be shifted forward by and shifted backward by to another RC4 state, which is called the forward and backward property of RC4 states.

The feature that any RC4 state is reversible is proved in Theorem 1.

Let (S0,i0 , j0 ) be the RC4 state initialized by KSA, where i0 = 0 and j0 = 0 is the initial index values of i and j, and S0 is the initial state vector for PGRA in RC4.

If PRGAn (S0 ,i0 , j0 ) = (Sn ,in , jn ) , it has the following property:

Theorem 1:

For any r , n ? r ? 0 , we have: IPRGA r (S n , in , jn ) = (S n ? r , in ? r , jn ?r )

Proof. Our proof is conducted by induction on integer r

Base Case: r = 0 . It is true: IPRGA0 (S n , in , jn ) = (S n , in , jn )

Inductive Step:

Assume that for any r ? k we have: IPRGA k (S n ,in , jn ) = (S n ? k ,in ? k , jn ?k )

Consider case of r = k +1

IPRGA k +1 (S n ,in , jn ) = IPRGA (IPRGA k (S n ,in , jn )) = IPRGA (S n ? k ,in ? k , jn ?k )

Let IPRGA (S n ? k , in ? k , jn ?k ) = (S * , i * , j* )

According to PRGA and our notation, we have

PRGA (S n ? k ?1 , in ? k ?1 , jn ? k ?1 ) = (S n ? k , in ? k , jn ?k ) where in ? k = in ? k ?1 +1

j = j ? k ?1 + S i +1

n ? k n n ? k ?1 [ n ? k ?1 ]

S n ?k [ m ] = S n ? k ?1 [ m ] where m ? i and m ? j + S n ? k i ? k ?1 +1

n ? k ?1 n ? k ?1 ?1 [ n ]

S n ? k [ i ?1 + 1 = S j n ? k ?1 + S n ? k i +1

n ? k ] n ? k ?1 ?1 [ n ? k ?1 ]

S j + S i + 1 = S i +1

n ? kn ? k ?1 n ? k ?1 [ n ? k ?1 ] n ? k ?1 [ n ? k ?1 ]

According to IPRGA (S n ? k , in ? k , jn ?k ) = ( S * , i * , j* ) ,

we have S * [ m ] = S n ?k [ m ] = S n ? k ?1 [ m ] where m ? i ? k ?1 and m ? j n ? k ?1 + S n i +1

n ? k ?1 [ n ? k ?1 ]

and S * i + 1 = S j ?1 + S i + 1 = S n ? k i + 1

[ n ? k ?1 ] n ? k n ? k n ? k ?1 [ n ? k ?1 ] ?1 [ n ? k ?1 ]

S * j + S n ? k ?1 [ i ?1 + 1 = S n ? k [ i + 1 = S j n ? k ?1 + S i +1

n ? k ?1 n ? k ] n ? k ?1 ] n ? k ?1 n ? k ?1 [ n ? k ?1 ]

Thus S * = Sn ? k ?1

j * = j ? S * i = j n ? k ?1 + S n ? k i + 1 ? S i + 1 = j

n ?k [ n ? k ] ?1 [ n ? k ?1 ] n ? k ?1 [ n ? k ?1 ] n ? k ?1

i * = in ? k ? 1 = in ? k ?1

Therefore, we have (S * , i * , j * ) = ( S n ? k ?1 , in ? k ?1 , jn ? k ?1 )

That is, for any n ? r ? 0 , we have IPRGA r (S n , in , jn ) = (S n ? r , in ? r , jn ?r )

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.