密碼學 - RC4 演算法

上一頁
下一頁

Rivest 密碼 4 被稱為 RC4。這種名為 RC4 的流密碼是由 Ron Rivest 於 1987 年建立的。RC4 是一種流密碼，它逐位加密資料。在所有流密碼中，RC4 因其簡單性和速度而成為使用最廣泛的一種。

儘管 RC4 以其速度和易於在軟體中使用而聞名，但已發現它存在許多漏洞，使其不安全。如果未刪除輸出金鑰流的開頭，或者使用連結或非隨機金鑰，則它極易受到攻擊。特別是，RC4 的使用導致了 WEP 等相對不安全的協議的產生。

2015 年，有傳言稱某些國家密碼學組織可能會破解 RC4，如果它用於 TLS 協議的話。網際網路工程任務組的 RFC 7465 禁止在 TLS 中使用 RC4，Mozilla 和 Microsoft 也提出了類似的建議。

RC4 如何工作？

RC4 生成金鑰流或偽隨機位元流。這可以用於加密，方法是使用按位異或與明文組合，就像任何其他流密碼一樣。由於異或是一種對稱運算，因此解密也遵循相同的過程。

該密碼使用隱藏的內部狀態生成金鑰流，該狀態分為兩部分：

  • 所有 256 個可用位元組都被置換。
  • 每個索引指標有八位。

已知金鑰排程方法使用可變長度金鑰（通常在 40 到 256 位之間）來初始化置換。然後使用偽隨機生成方法生成位元流。

以下是使用 XOR 加密的影像。

RC4 Algorithm

加密

  • 使用者輸入明文和金鑰。
  • 加密演算法使用 KSA 和 PRGA 演算法為輸入的金鑰生成金鑰流。
  • 生成的金鑰流與明文進行異或運算。由於 RC4 是流密碼，因此使用逐位元組異或來建立密文。
  • 現在，目標接收者以加密形式接收此密文。

解密

  • 密文使用相同的逐位元組異或方法解密。

金鑰生成

使用長度從 1 到 256 位元組不等的可變長度金鑰初始化包含元素 S[0] 到 S[255] 的 256 位元組狀態向量 S。透過仔細選擇 255 個條目中的一個來建立用於加密和解密的位元組 k，之後 S 中的條目執行另一次置換。

金鑰排程

透過將 S 條目的值設定為從 0 到 255 的升序來生成臨時向量 T。如果其長度為 256 位元組，則將金鑰 k 分配給 T。否則，對於長度為 (k-len) 位元組的金鑰，T 的前 k-len 個元素從 K 複製，然後根據需要重複 K 以填充 T。以下是該概念的表示：

首先初始化陣列 S 和 T。接下來，我們使用陣列 K 來計算陣列 T。最後，我們將陣列 T 給出的方法應用於陣列 S 的第一次置換。

示例

// Initialize array S
int[] S = new int[256];
for (int i = 0; i < 256; i++) {
   S[i] = i;
}

// Calculate array T using array K
int[] T = new int[256];
for (int i = 0; i < 256; i++) {
   T[i] = K[i % K.length - len];
}

這段 Java 程式碼使用 0 到 255 的值初始化陣列 S，然後使用對陣列 K 的模運算來計算陣列 T。

# Initializing arrays S and T
S = list(range(256))
T = [0] * 256

# Calculating array T using array K
for i in range(256):
   T[i] = K[i % len(K) - len]

# Performing initial permutation of array S using array T
j = 0
for i in range(256):
   j = (j + S[i] + T[i]) % 256
   # Swap S[i] and S[j]
   S[i], S[j] = S[j], S[i]

設定向量 S 後，將不再使用輸入金鑰。在此步驟中，使用由 S 的當前配置確定的方案將每個 S[i] 演算法位元組與 S 中的不同位元組交換。到達 S[255] 後，該方法繼續，再次從 S[0] 開始。

# Initialize array S with values from 0 to 255
S = list(range(256))

# Start swapping process
i = 0
j = 0
for _ in range(256):
   i = (i + 1) % 256
   j = (j + S[i]) % 256
   # Swap S[i] and S[j]
   S[i], S[j] = S[j], S[i]

RC4 的特點

  • RC4 使用對稱金鑰，這意味著相同的金鑰用於加密和解密。
  • RC4 是流密碼演算法的一個示例，這意味著資料一次一個位元組地進行加密和解密。密文是透過將它生成的偽隨機位金鑰流與明文進行異或運算建立的。
  • RC4 允許 40 位到 2048 位的不同金鑰大小，因此它可以靈活適應各種安全需求。
  • RC4 加密技術快速有效，非常適合低功耗裝置和需要高速傳送資料的應用程式。
  • RC4 廣泛用於許多不同的應用程式，例如檔案加密、虛擬專用網路 (VPN)、安全套接字層 (SSL) 和無線網路。
  • RC4 容易受到多種攻擊，其中一種攻擊是金鑰流的初始幾個位元組中的偏差，可用於檢索金鑰。因此，不再建議在新應用程式中使用 RC4。

使用 Python 實現

現在我們將藉助Python實現RC4。

示例

# Function for encryption
def encrypt_rc4():

   global secret_message, secret_key, n

   # Given text and key
   secret_message = "101101100110"
   secret_key = "001010010010"

   # n is the number of bits 
   n = 3

   print("Secret message : ", secret_message)
   print("Secret key : ", secret_key)
   print("n : ", n)

   print(" ")

   # The initial state vector array
   S = [i for i in range(0, 2**n)]
   print("S : ", S)

   key_list = [secret_key[i:i + n] for i in range(0, len(secret_key), n)]

   # Convert key stream to decimal
   for i in range(len(key_list)):
      key_list[i] = int(key_list[i], 2)

   # Convert secret message to decimal
   global pt

   pt = [secret_message[i:i + n] for i in range(0, len(secret_message), n)]

   for i in range(len(pt)):
      pt[i] = int(pt[i], 2)

   print("Secret message (in array form): ", pt)

   # Making key stream equal to the length of state vector
   diff = int(len(S)-len(key_list))

   if diff != 0:
      for i in range(0, diff):
         key_list.append(key_list[i])

   print("Key list : ", key_list)
   print(" ")

   # Perform the KSA algorithm
   def key_scheduling_algorithm():
      j = 0
      N = len(S)
		
      # Iterate over the range [0, N]
      for i in range(0, N):
		
         # Find the key
         j = (j + S[i]+key_list[i]) % N
			
         # Update S[i] and S[j]
         S[i], S[j] = S[j], S[i]
         print(i, " ", end ="")
			
         # Print S
         print(S)

      initial_permutation_array = S
		
      print(" ")
      print("Initial permutation array : ",
         initial_permutation_array)

   print("KSA process : ")
   print(" ")
   key_scheduling_algorithm()
   print(" ")

   # Perform PGRA algorithm
   def pseudo_random_generation_algorithm():

      N = len(S)
      i = j = 0
      global key_stream
      key_stream = []

      # Iterate over [0, length of pt]
      for k in range(0, len(pt)):
         i = (i + 1) % N
         j = (j + S[i]) % N
			
         # Update S[i] and S[j]
         S[i], S[j] = S[j], S[i]
         print(k, " ", end ="")
         print(S)
         t = (S[i]+S[j]) % N
         key_stream.append(S[t])

      # Print the key stream
      print("Generated key stream : ", key_stream)
      print(" ")

   print("Key stream generation : ")
   print(" ")
   pseudo_random_generation_algorithm()

   # Performing XOR between generated key stream and secret message
   def perform_xor():
      global cipher_text
      cipher_text = []
      for i in range(len(pt)):
         c = key_stream[i] ^ pt[i]
         cipher_text.append(c)

   perform_xor()

   # Convert the encrypted text to bits form
   encrypted_to_bits = ""
   for i in cipher_text:
      encrypted_to_bits += '0'*(n-len(bin(i)[2:]))+bin(i)[2:]

   print(" ")
   print("Cipher text : ", encrypted_to_bits)

# Execute function
encrypt_rc4()

print("*********************************************************")

# Function for decryption of data
def decrypt_rc4():

   # The initial state vector array
   S = [i for i in range(0, 2**n)]

   key_list = [secret_key[i:i + n] for i in range(0, len(secret_key), n)]

   # Convert key stream to decimal
   for i in range(len(key_list)):
      key_list[i] = int(key_list[i], 2)

   # Convert secret message to decimal
   global pt

   pt = [secret_message[i:i + n] for i in range(0, len(secret_message), n)]

   for i in range(len(pt)):
      pt[i] = int(pt[i], 2)

   # Making key stream equal to the length of state vector
   diff = int(len(S)-len(key_list))

   if diff != 0:
      for i in range(0, diff):
         key_list.append(key_list[i])

   print(" ")

   # KSA algorithm
   def key_scheduling_algorithm():
      j = 0
      N = len(S)
		
      # Iterate over the range [0, N]
      for i in range(0, N):
         j = (j + S[i]+key_list[i]) % N
			
         # Update S[i] and S[j]
         S[i], S[j] = S[j], S[i]
         print(i, " ", end ="")
         print(S)

      initial_permutation_array = S
      print(" ")
      print("Initial permutation array : ",
         initial_permutation_array)

   print("KSA process : ")
   print(" ")
   key_scheduling_algorithm()
   print(" ")

   # Perform PRGA algorithm
   def pseudo_random_generation_algorithm():

      N = len(S)
      i = j = 0
      global key_stream
      key_stream = []

      # Iterate over the range
      for k in range(0, len(pt)):
         i = (i + 1) % N
         j = (j + S[i]) % N
			
         # Update S[i] and S[j]
         S[i], S[j] = S[j], S[i]
         print(k, " ", end ="")
         print(S)
         t = (S[i]+S[j]) % N
         key_stream.append(S[t])

      print("Generated key stream : ", key_stream)
      print(" ")

   print("Key stream generation : ")
   print(" ")
   pseudo_random_generation_algorithm()

   # Perform XOR between generated key stream and cipher text
   def perform_xor():
      global original_text
      original_text = []
      for i in range(len(cipher_text)):
         p = key_stream[i] ^ cipher_text[i]
         original_text.append(p)

      perform_xor()

   # convert the decrypted text to the bits form
   decrypted_to_bits = ""
   for i in original_text:
      decrypted_to_bits += '0'*(n-len(bin(i)[2:]))+bin(i)[2:]

   print(" ")
   print("Decrypted text : ",
      decrypted_to_bits)

# execute function
decrypt_rc4()

以下是上述示例的輸出：

輸入/輸出

Secret message :  101101100110
Secret key :  001010010010
n :  3
 
S :  [0, 1, 2, 3, 4, 5, 6, 7]
Secret message (in array form):  [5, 5, 4, 6]
Key list :  [1, 2, 2, 2, 1, 2, 2, 2]
 
KSA process : 
 
0  [1, 0, 2, 3, 4, 5, 6, 7]
1  [1, 3, 2, 0, 4, 5, 6, 7]
2  [1, 3, 7, 0, 4, 5, 6, 2]
3  [1, 0, 7, 3, 4, 5, 6, 2]
4  [1, 0, 7, 3, 6, 5, 4, 2]
5  [1, 0, 7, 3, 6, 5, 4, 2]
6  [1, 0, 7, 4, 6, 5, 3, 2]
7  [1, 0, 7, 4, 6, 5, 3, 2]
 
Initial permutation array :  [1, 0, 7, 4, 6, 5, 3, 2]
 
Key stream generation : 
 
0  [0, 1, 7, 4, 6, 5, 3, 2]
1  [0, 1, 2, 4, 6, 5, 3, 7]
2  [0, 1, 2, 4, 6, 5, 3, 7]
3  [0, 6, 2, 4, 1, 5, 3, 7]
Generated key stream :  [1, 1, 0, 7]
 
 
Cipher text :  100100100001
*********************************************************
KSA process : 
 
0  [1, 0, 2, 3, 4, 5, 6, 7]
1  [1, 3, 2, 0, 4, 5, 6, 7]
2  [1, 3, 7, 0, 4, 5, 6, 2]
3  [1, 0, 7, 3, 4, 5, 6, 2]
4  [1, 0, 7, 3, 6, 5, 4, 2]
5  [1, 0, 7, 3, 6, 5, 4, 2]
6  [1, 0, 7, 4, 6, 5, 3, 2]
7  [1, 0, 7, 4, 6, 5, 3, 2]
 
Initial permutation array :  [1, 0, 7, 4, 6, 5, 3, 2]
 
Generated key stream :  [1, 1, 0, 7]
 
Key stream generation : 
 
0  [0, 1, 7, 4, 6, 5, 3, 2]
1  [0, 1, 2, 4, 6, 5, 3, 7]
2  [0, 1, 2, 4, 6, 5, 3, 7]
3  [0, 6, 2, 4, 1, 5, 3, 7]
 
Decrypted text :  101101100110

RC4的用途

多年來，RC4越來越受歡迎，併成為商業應用中的標準。它以簡單、快速和廉價的加密技術而聞名。

RC4的主要優點是易於實現和使用，以及其執行和部署速度快。它能夠高效快速地處理大型資料流。在記憶體使用方面，RC4流密碼也很高效。

然而，由於近年來發現了缺陷和網路攻擊的證據，人們呼籲停止使用RC4加密演算法。還發現了其他缺點，例如無法處理小型資料流以及在實施新系統之前需要進行額外調查。

網際網路工程任務組 (IETF) 在 2015 年禁止在 TLS 協議中使用 RC4。由於威脅漏洞，微軟和Mozilla也釋出了限制使用RC4的建議。許多基於RC4的生態系統，例如WEP、WPA、BitTorrent協議加密、Microsoft點對點加密等。

RC4A是RC4功能更強大的變體。RC4A+是RC4的修改版本，具有更復雜的3階段金鑰排程，比基本RC4長1.7倍。

RC4的優點

以下是使用RC4時需要考慮的一些RC4優點：

  • RC4是一種非常快速且高效的加密方法，使其適用於需要這些特性的場景。
  • 由於RC4是一種相當基本的演算法，因此可以在硬體或軟體中輕鬆實現。
  • RC4是動態的，並且可以適應各種安全需求，因為它允許不同的金鑰大小。
  • RC4 廣泛用於許多不同的應用程式，例如檔案加密、虛擬專用網路 (VPN)、安全套接字層 (SSL) 和無線網路。

RC4的缺點

使用RC4時，我們需要考慮一些嚴重的缺點：

  • 由於許多已追蹤到的漏洞，RC4不適用於新的應用程式。例如，可以透過利用金鑰流前幾個位元組中存在的偏差來恢復金鑰。
  • 與AES或ChaCha20等其他加密演算法相比，由於其架構中存在一些內建漏洞，RC4安全性較低。
  • RC4的2048位最大金鑰長度對於某些需要更高級別加密的應用程式可能不夠。
  • 由於其漏洞和缺陷，不再建議在新應用程式中使用RC4。取而代之的是，需要使用兩種更安全的流密碼演算法：AES-CTR或ChaCha20。

RC4和WEP

WEP（有線等效隱私）是一種用於保護無線網路的安全機制。它具有與有線網路類似的隱私和安全功能。WEP在Wi-Fi的早期被廣泛使用，但它存在一些已知的漏洞，使得它非常容易受到攻擊。這些弱點包括弱金鑰排程機制（基於RC4）、短初始化向量（IV）和缺乏金鑰管理工具。

在WEP中，資料首先使用RC4技術加密，然後透過無線網路傳送。由於WEP協議中的弱點，網路安全很容易受到各種攻擊的影響，例如Fluhrer-Mantin-Shamir (FMS)攻擊和KoreK攻擊，這些攻擊可以檢索WEP金鑰。

WEP是一種強大的流密碼，但RC4的實現引入了問題。因此，更安全的加密協議，如WPA（Wi-Fi保護訪問）和WPA2最終取代了WEP。

列印頁面
上一頁
下一頁
廣告