Merkle–Hellmanův kryptosystém

Tato asymetrická šifra byla představena v roce 1978, dnes je prolomena (tudíž je zde představena pouze pro ukázku, v praxi se již nedá využívat). Představuje kryptosystém postavený na odlišném principu, nežli většina moderních asymetrických kryptosystémů, sice na problému batohu (anglicky Knapsack problem). Tento problém je na vysvětlení podstatně jednoduší, nežli problém diskrétního logaritmu či faktorizace čísel.

Princip

Šifra je konkrétně odvislá od problému sumace podmnožiny (anglicky Subset Sum Problem), což je varianta problému batohu (anglicky Knapsack problem). Tento problém lze popsat: mějme množinu čísel A, dále číslo b, které představuje sumu VYBRANÝCH (tj. standardně ne všech) prvků množiny. Úloha zní: najděte podmnožinu množiny A, kde suma prvků této podmnožiny odpovídá číslu b.

Dále předpokládáme, že Alice chce přijímat n-bitové zprávy, Bob je připraven ji jednu takovou zprávu zaslat.

Generování klíče

1. Alice vygeneruje n-prvkovou posloupnost kladných přirozených čísel w takovou, že je tzv. super-rostoucí, to znamená, že každý další prvek posloupnosti je ostře větší, nežli suma všech prvků předchozích.

   w = (w₁, w₂, w₃, …, w_n), w_i > ∑_j=1ⁱ w_j

2. Alice vybere náhodné přirozené číslo q takové, že suma všech prvků posloupnosti je ostře menší než toto číslo q. A dále náhodné přirozené číslo r, které je s číslem q nesoudělné.

   q > ∑_j=1ⁿ w_j

   Význam těchto dvou čísel je takový, že bez jejich znalosti by nebylo možné zprávu jednoznačně dešifrovat.

3. Alice vypočte posloupnost b velikosti n, jednotlivé prvky mají tvar (pro i-tý prvek):

   b_i = r·w_i mod q

4. Veřejným klíčem je posloupnost b. Privátním klíčem jsou čísla q, r a posloupnost w.

Šifrování

Předpokládáme, že Bob má k zašifrování zprávu zakódovanou do posloupnosti m velikosti n:

m = (m₁, m₂, m₃, …, m_n),

kde m_i nabývá hodnoty 0 nebo 1, tj. představuje i-tý bit zprávy.

Šifrování, tj. hledání čísla c, se provádí dle vzorce:

c = ∑_j=1ⁿ m_j·b_j

Šifru, tj. hodnotu čísla c, odešle Bob Alici.

Dešifrování

Pokud Alice obdrží šifru c provede k dešifrování následující kroky:

1. Alice vypočte multiplikativní inverzi r^-1 mod q.

2. Alice vypočte hodnotu d₀ = cr^-1 mod q.

3. Nyní probíhá dešifrování v následující smyčce:

   1. Nalezne se nejvyšší hodnota v posloupnosti w, která je zároveň ale nižší než číslo d₀.

   2. Nalezená hodnota se odečte od d₀, vznikne tak číslo d₁.

   3. Algoritmus se opakuje krokem (a.), kde d₀ nyní představuje d₁, v kroku (b.) navíc d₁ bude mít význam d₂. Algoritmus končí, pokud d_k = 0 pro nějaké k.

4. Čísla z posloupnosti w, která se v algoritmu popsaném v kroku (3.) odečítala, představují bity, na kterých je v dešifrované zprávě hodnota 1, na ostatních pozicích je hodnota 0. Takto je tedy zpráva dešifrována.

Programování

Naprogramujte algoritmus realizující Merkle–Hellmanovu šifru.