Podstawa wykładowa: Część 6 - slajdy 11, 35, 36, 43: zarządzanie kluczem głównym szyfrowania macierzy (Key Encryption Key / KEK), problem pojedynczego punktu
zaufania (Single Point of Failure), wieloosobowa autoryzacja k-z-n, schemat progowy Shamira nad ciałem skończonym GF(p), wielomiany losowe i interpolacja Lagrange'a.
Cel
Celem zadania jest zaprojektowanie i wdrożenie mechanizmu bezpiecznego rozproszenia klucza głównego macierzy pamięci masowej (KEK) za pomocą progowego schematu dzielenia
sekretu Shamira (k, n) w języku Python. Student implementuje wielomianowe dzielenie 256-bitowego klucza AES nad ciałem liczb pierwszych GF(p), generuje unikalne udziały dla n
administratorów storage, demonstruje niemożliwość odzyskania klucza przy posiadaniu k-1 udziałów oraz przeprowadza bezbłędną rekonstrukcję klucza za pomocą interpolacji Lagrange'a po
zebraniu kworum k udziałów.
Scenariusz – opis
W wielkoskalowych centrach danych klucz szyfrujący macierzy dyskowej KEK (Key Encryption Key) chroni dostęp do petabajtów składowanych informacji. Powierzenie klucza KEK pojedynczemu administratorowi tworzy krytyczny pojedynczy punkt awarii oraz stwarza ryzyko nadużyć lub szantażu. Z kolei utrata klucza w wyniku wypadku losowego skutkuje nieodwracalną utratą wszystkich wolumenów w centrum danych.
Rozwiązaniem tego dylematu jest kryptograficzny schemat progowy Shamira (k, n) Secret Sharing zaproponowany przez Adiego Shamira w 1979 roku. W schemacie tym sekret dzielony jest na n niezależnych udziałów (shares) w taki sposób, że do odtworzenia klucza wymagane jest dowolne kworum co najmniej k udziałów. Posiadanie dowolnych k minus jeden udziałów nie daje atakującemu absolutnie żadnej informacji o sekrecie w sensie teorii informacji Shannona.
Matematyczną podstawą schematu jest fakt, że wielomian stopnia k-1 jest jednoznacznie wyznaczony przez dokładnie k punktów w ciele skończonym GF(p). Sekret umieszczany jest jako wyraz wolny a_0 losowego wielomianu, a kolejne współczynniki losowane są kryptograficznie z ciała liczb pierwszych. Każdy administrator otrzymuje punkt (x, f(x)), a rekonstrukcja klucza polega na obliczeniu wartości f(0) za pomocą wielomianu interpolacyjnego Lagrange'a.
Wdrożenie schematu Shamira pozwala macierzy pamięci masowej wymagać obecności np. 3 z 5 uprawnionych oficerów bezpieczeństwa do odblokowania wolumenów po restarcie.
W tym zadaniu zaimplementujesz pełny schemat Shamira w ciele liczb pierwszych w Pythonie i przetestujesz odporność na niekompletne kworum.
Co ma wykonać student / grupa
Pracę rozpoczynasz od utworzenia skryptu shamir_storage.py w katalogu roboczym środowiska laboratoryjnego. Wybierasz bezpieczną liczbę
pierwszą p większą od przestrzeni 256-bitowych kluczy AES (np. 257-bitowa liczba pierwsza Mersenne'a lub liczba zdefiniowana w FIPS). Implementujesz funkcje arytmetyki
modularnej w ciele GF(p), w tym dodawanie, odejmowanie, mnożenie oraz modularną odwrotność za pomocą rozszerzonego algorytmu Euklidesa. Implementujesz funkcję split_secret(secret_int,
k, n), która generuje losowy wielomian stopnia k-1 i oblicza n unikalnych punktów (x_i, y_i).
Zasymulujesz wygenerowanie 256-bitowego klucza KEK macierzy dyskowej i podzielenie go pomiędzy n = 5 administratorów przy progu k = 3.
Zapisujesz wygenerowane udziały do osobnych plików poświadczeń dla pięciu oficerów bezpieczeństwa storage. Implementujesz procedurę kryptoanalityczną: próbujesz odtworzyć klucz przy
użyciu jedynie 2 udziałów (mniej niż próg k = 3). Wykazujesz matematycznie, że każda możliwa 256-bitowa wartość jest w równym stopniu prawdopodobna, co dowodzi
bezpieczeństwa w sensie informacji (information-theoretic security).
Następnie implementujesz funkcję reconstruct_secret(shares) opartą na interpolacji Lagrange'a i rekonstruujesz klucz z 3 dowolnych udziałów. Potwierdzasz poprawność
odzyskania oryginalnego klucza KEK i odblokowania wolumenu macierzy. Dokumentujesz kod, wyprowadzenia matematyczne interpolacji Lagrange'a oraz zrzuty ekranu konsoli w sprawozdaniu.
Przykładowe kroki do wykonania jako sugestia
-
W terminalu utwórz katalog roboczy:
mkdir -p ~/shamir_lab
&& cd ~/shamir_lab.
- Utwórz plik skryptu:
nano shamir_engine.py.
- Zaimportuj moduły standardowe: secrets,
os, sys.
-
Zdefiniuj liczbę pierwszą p: wybierz
257-bitową liczbę pierwszą
(np. p =
pow(2, 256) + 297).
-
Zaimplementuj rozszerzony algorytm Euklidesa:
egcd(a, b)
oraz modularną odwrotność mod_inv(a, p) =
pow(a, -1, p).
-
Zaimplementuj funkcję generowania wielomianu:
poly = [secret] +
[secrets.randbelow(p) for _
in range(k - 1)].
-
Zaimplementuj obliczanie punktów:
f(x) =
sum( poly[i] * pow(x, i)
for i in range(k)) % p.
-
Wygeneruj klucz główny macierzy
KEK: kek_bytes
= os.urandom(32); kek_int
= int.from_bytes(kek_bytes, 'big').
-
Podziel klucz na
n=5 udziałów z progiem
k=3: wylicz punkty dla x od 1 do 5.
-
Zapisz udziały do plików:
share_1.json do share_5.json.
-
Zaimplementuj interpolację Lagrange'a w zerze:
L(0) =
sum(y_j * prod((0 - x_m) *
mod_inv(x_j - x_m, p)
for m != j)) % p.
-
Przetestuj próbę rekonstrukcji z 2 udziałów (
k-1): wykaż, że wynik jest całkowicie
błędny i zależy od arbitralnego wyboru brakującego punktu.
-
Przetestuj rekonstrukcję z udziałów [
1, 2, 3]:
potwierdź, że recovered_kek == kek_int.
-
Przetestuj rekonstrukcję z innej kombinacji kworum [
2, 4,
5]: potwierdź identyczny poprawny wynik.
- Przekształć zrekonstruowaną liczbę z powrotem na 32 bajty i upewnij się o tożsamości z kek_bytes.
-
Zbadaj odporność schematu na podrzucenie sfałszowanego udziału (
bad share) i zaproponuj weryfikowalny schemat
Verifiable Secret Sharing (Feldman VSS).
- Wykonaj zrzuty ekranu kodu, wygenerowanych udziałów oraz pomyślnej rekonstrukcji klucza z różnych podzbiorów administratorów.
- Sformułuj procedurę operacyjną wdrożenia schematu Shamira dla zarządzania kluczami w uczelnianym centrum danych.
Kontrola zaliczenia (checklist):
- Rozproszono KEK Shamirem (k,n) na wektorze ze startera: udziały wielomianowe w GF(p), rekonstrukcja Lagrange'em przy k, zero wiedzy przy k−1.
- Wykazano różnicę: k udziałów (odzysk) vs k−1 (entropia pełna, test statystyczny); dołączono logi.
- Dołączono log podziału/interpolacji + kod łatki (k,n do ryzyka, HSM na udziały, rotacja).
- Opisano w 3–5 zdaniach kompromis: brak single-point vs ceremonia udziałów, bezpieczeństwo teoriomnogościowe.
Wariant offline (fallback): Praca w pełni offline na wektorach ze startera w lokalnym Pythonie 3 bez sieci; dołącz kod ataku, log rekonstrukcji oraz opis kompromisu bezpieczeństwo–wydajność i wytyczne hardeningu.
Sugerowane wnioski i podsumowanie - co student ma osiągnąć
Sprawozdanie z realizacji zadania musi zawierać następujące kluczowe wnioski i osiągnięcia:
- Zrozumienie matematycznych podstaw progowego podziału sekretu Shamira (k, n) opartego na ciałach skończonych GF(p).
- Praktyczna umiejętność implementacji podziału wielomianowego oraz interpolacji Lagrange'a w języku Python.
- Weryfikacja bezpieczeństwa w sensie teorii informacji gwarantującego zerowy wyciek wiedzy przy k-1 udziałach.
- Znajomość zastosowania schematów progowych w eliminacji pojedynczego punktu zaufania w zarządzaniu pamięcią masową.
