Nom : CHOUBIK
Prénom : HOUSSAM
Filière : CS2C-1
Exercice 1 : Étude de la sécurité des LFSR (Linéarité et Périodes)
Partie : Implémentation et Propriétés Algébriques
- Arithmétique dans Z/2Z : Écrire une fonction ProdPoly(P1, P2) qui effectue le produit de deux polynômes dans Z/2Z .
- Le moteur LFSR : Écrire une fonction LFSR(poly, seed, NbBits) qui simule le registre.
- Analyse de la période : Écrire une fonction PeriodLFSR (poly, seed) qui retourne le nombre d'itérations nécessaires avant que le registre ne retrouve son état initial.
Partie : Application au Chiffrement
- Chiffrement d'un message.
Partie : Cryptanalyse et Robustesse
- Attaque "Known Plaintext" (Message Clair Connu) : Supposons qu'un attaquant connaisse les 24 premiers bits du message clair m et les 24 premiers bits du texte chiffré c.
- Vers la robustesse : Composition de LFSR : Pour masquer la linéarité, on utilise souvent plusieurs LFSR combinés par une fonction non-linéaire (Ex: le générateur de Geffe).
from typing import List, Tuple
def ProdPoly(P1, P2):
res = [0] * (len(P1) + len(P2) - 1)
for i in range(len(P1)):
for j in range(len(P2)):
res[i + j] ^= (P1[i] & P2[j])
return res
a=[1,0,1,1]
b=[0,1,1,1]
c=ProdPoly(a, b)
c
[0, 1, 1, 0, 0, 0, 1]
def AddPoly(P1: List[int], P2: List[int]) -> List[int]:
max_len = max(len(P1), len(P2))
result = [0] * max_len
for i in range(len(P1)):
result[i] ^= P1[i]
for i in range(len(P2)):
result[i] ^= P2[i]
while len(result) > 1 and result[-1] == 0:
result.pop()
return result
def poly_to_int(poly: List[int]) -> int:
result = 0
for i, coef in enumerate(poly):
result |= (coef << i)
return result
def int_to_poly(n: int, length: int = None) -> List[int]:
if n == 0:
return [0]
poly = []
while n > 0:
poly.append(n & 1)
n >>= 1
if length and len(poly) < length:
poly.extend([0] * (length - len(poly)))
return poly
def LFSR(poly: List[int], seed: List[int], NbBits: int) -> List[int]:
n = len(seed)
state = seed.copy()
output = []
for _ in range(NbBits):
output_bit = state[0]
output.append(output_bit)
feedback = 0
for i in range(n):
feedback ^= (state[i] * poly[i])
state = state[1:] + [feedback]
return output
def LFSR_state_evolution(poly: List[int], seed: List[int], steps: int) -> List[List[int]]:
n = len(seed)
state = seed.copy()
states = [state.copy()]
for _ in range(steps):
feedback = 0
for i in range(n):
feedback ^= (state[i] * poly[i])
state = state[1:] + [feedback]
states.append(state.copy())
return states
def PeriodLFSR(poly: List[int], seed: List[int]) -> int:
if all(bit == 0 for bit in seed):
return 1
n = len(seed)
initial_state = seed.copy()
state = seed.copy()
period = 0
max_period = 2**n
while True:
feedback = 0
for i in range(n):
feedback ^= (state[i] * poly[i])
state = state[1:] + [feedback]
period += 1
if state == initial_state:
return period
if period >= max_period:
return -1
def is_primitive_poly(poly: List[int]) -> bool:
n = len(poly) - 1
max_period = 2**n - 1
seed = [1] + [0] * (n - 1)
period = PeriodLFSR(poly, seed)
return period == max_period
def string_to_bits(message: str) -> List[int]:
bits = []
for char in message:
byte = ord(char)
for i in range(8):
bits.append((byte >> i) & 1)
return bits
def bits_to_string(bits: List[int]) -> str:
chars = []
for i in range(0, len(bits), 8):
byte = 0
for j in range(min(8, len(bits) - i)):
byte |= (bits[i + j] << j)
chars.append(chr(byte))
return ''.join(chars)
def encrypt_LFSR(message: str, poly: List[int], seed: List[int]) -> Tuple[List[int], List[int]]:
message_bits = string_to_bits(message)
keystream = LFSR(poly, seed, len(message_bits))
ciphertext = [m ^ k for m, k in zip(message_bits, keystream)]
return ciphertext, keystream
def decrypt_LFSR(ciphertext: List[int], poly: List[int], seed: List[int]) -> str:
keystream = LFSR(poly, seed, len(ciphertext))
plaintext_bits = [c ^ k for c, k in zip(ciphertext, keystream)]
return bits_to_string(plaintext_bits)
def solve_linear_system_gf2(matrix: List[List[int]], vector: List[int]) -> List[int]:
n = len(matrix)
m = len(matrix[0])
aug = [row + [vector[i]] for i, row in enumerate(matrix)]
pivot_row = 0
for col in range(m):
# Trouver un pivot
found = False
for row in range(pivot_row, n):
if aug[row][col] == 1:
aug[pivot_row], aug[row] = aug[row], aug[pivot_row]
found = True
break
if not found:
continue
for row in range(n):
if row != pivot_row and aug[row][col] == 1:
for j in range(m + 1):
aug[row][j] ^= aug[pivot_row][j]
pivot_row += 1
solution = [0] * m
for i in range(min(pivot_row, m)):
pivot_col = -1
for j in range(m):
if aug[i][j] == 1:
pivot_col = j
break
if pivot_col != -1:
solution[pivot_col] = aug[i][-1]
return solution
def known_plaintext_attack(plaintext_bits: List[int], ciphertext_bits: List[int],
lfsr_length: int) -> Tuple[List[int], List[int]]:
keystream = [p ^ c for p, c in zip(plaintext_bits, ciphertext_bits)]
if len(keystream) < 2 * lfsr_length:
raise ValueError(f"Pas assez de bits connus (besoin de {2*lfsr_length}, obtenu {len(keystream)})")
seed = keystream[:lfsr_length]
matrix = []
vector = []
for i in range(lfsr_length, min(len(keystream), 2 * lfsr_length)):
row = keystream[i - lfsr_length:i]
matrix.append(row)
vector.append(keystream[i])
poly = solve_linear_system_gf2(matrix, vector)
return poly, seed
def geffe_generator(poly1: List[int], seed1: List[int],
poly2: List[int], seed2: List[int],
poly3: List[int], seed3: List[int],
NbBits: int) -> List[int]:
stream1 = LFSR(poly1, seed1, NbBits)
stream2 = LFSR(poly2, seed2, NbBits)
stream3 = LFSR(poly3, seed3, NbBits)
output = []
for b1, b2, b3 in zip(stream1, stream2, stream3):
bit = (b1 & b2) ^ ((1 ^ b1) & b3)
output.append(bit)
return output
def shrinking_generator(poly1: List[int], seed1: List[int],
poly2: List[int], seed2: List[int],
NbBits: int) -> List[int]:
stream1 = LFSR(poly1, seed1, NbBits * 4)
stream2 = LFSR(poly2, seed2, NbBits * 4)
output = []
i = 0
while len(output) < NbBits and i < len(stream1):
if stream1[i] == 1:
output.append(stream2[i])
i += 1
return output[:NbBits]
Exercice 2 : Comparaison de chiffrements par flux
Objectif : Comparer la performance de différents générateurs de flux : LFSR, Trivium, Salsa20 et ChaCha20.
- Génération du texte clair.
- Chiffrement par flux.
- Déchiffrement.
- Mesure des performances.
!pip install pycryptodome
Collecting pycryptodome Using cached pycryptodome-3.23.0-cp37-abi3-win_amd64.whl.metadata (3.5 kB) Using cached pycryptodome-3.23.0-cp37-abi3-win_amd64.whl (1.8 MB) Installing collected packages: pycryptodome Successfully installed pycryptodome-3.23.0
import os
import time
from Crypto.Cipher import Salsa20, ChaCha20
from Crypto.Util import Counter
class LFSR:
def __init__(self, size, poly, state):
self.size = size
self.poly = poly
self.state = state
def clock(self):
feedback = 0
for bit in self.poly:
feedback ^= (self.state >> bit) & 1
out = self.state & 1
self.state = (self.state >> 1) | (feedback << (self.size - 1))
return out
def nlf_encrypt(plaintext, lfsrs):
ciphertext = bytearray()
for byte in plaintext:
encrypted_byte = 0
for i in range(8):
s1 = lfsrs[0].clock()
s2 = lfsrs[1].clock()
s3 = lfsrs[2].clock()
keystream_bit = (s1 & s2) ^ s3
encrypted_byte |= (keystream_bit << i)
ciphertext.append(byte ^ encrypted_byte)
return ciphertext
class Trivium:
def __init__(self, key, iv):
self.state = [0] * 288
for i in range(80): self.state[i] = (key[i//8] >> (i%8)) & 1
for i in range(80): self.state[i+93] = (iv[i//8] >> (i%8)) & 1
self.state[285] = self.state[286] = self.state[287] = 1
for _ in range(1152): self._gen_bit()
def _gen_bit(self):
t1 = self.state[65] ^ (self.state[90] & self.state[91]) ^ self.state[92] ^ self.state[170]
t2 = self.state[161] ^ (self.state[174] & self.state[175]) ^ self.state[176] ^ self.state[68]
t3 = self.state[242] ^ (self.state[285] & self.state[286]) ^ self.state[287] ^ self.state[241]
out = self.state[65] ^ self.state[161] ^ self.state[242]
self.state = [t3] + self.state[:92] + [t1] + self.state[93:176] + [t2] + self.state[177:287]
return out
def encrypt(self, data):
res = bytearray()
for b in data:
keystream_byte = 0
for i in range(8):
keystream_byte |= (self._gen_bit() << i)
res.append(b ^ keystream_byte)
return res
plaintext = os.urandom(1024 * 1024)
results = {}
lfsrs = [LFSR(19, [18, 17, 16, 13], 0x12345),
LFSR(22, [21, 20], 0x23456),
LFSR(23, [22, 21, 20, 7], 0x34567)]
start = time.perf_counter()
nlf_cipher = nlf_encrypt(plaintext, lfsrs)
results['LFSR Non-linéaire'] = time.perf_counter() - start
key_80 = os.urandom(10)
iv_80 = os.urandom(10)
triv = Trivium(key_80, iv_80)
start = time.perf_counter()
triv_cipher = triv.encrypt(plaintext)
results['Trivium'] = time.perf_counter() - start
key_32 = os.urandom(32)
nonce_8 = os.urandom(8)
cipher_salsa = Salsa20.new(key=key_32, nonce=nonce_8)
start = time.perf_counter()
salsa_cipher = cipher_salsa.encrypt(plaintext)
results['Salsa20'] = time.perf_counter() - start
cipher_chacha = ChaCha20.new(key=key_32, nonce=nonce_8)
start = time.perf_counter()
chacha_cipher = cipher_chacha.encrypt(plaintext)
results['ChaCha20'] = time.perf_counter() - start
for algo, duration in results.items():
print(f"{algo:18}: {duration:.4f} secondes")
LFSR Non-linéaire : 24.5955 secondes Trivium : 46.9626 secondes Salsa20 : 0.0074 secondes ChaCha20 : 0.0065 secondes