Kryptosystem Okamoto – Uchiyama - Okamoto–Uchiyama cryptosystem

Okamoto-Uchiyama Kryptosystem jest klucz kryptograficzny publicznej zaproponowany w 1998 roku przez Tatsuaki Okamoto i Shigenori Uchiyama . System działa w multiplikatywnej grupie liczb całkowitych modulo n , gdzie n ma postać p ² q oraz p i q są dużymi liczbami pierwszymi . ${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$

Operacja

Podobnie jak wiele kryptosystemów z kluczem publicznym , ten schemat działa w grupie . Ten schemat jest homomorficzny, a zatem plastyczny . ${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$

Generacja klucza

Para kluczy publiczny / prywatny jest generowana w następujący sposób:

1. Wygeneruj dwie duże liczby pierwsze i . ${\ displaystyle p}$${\ displaystyle q}$
2. Oblicz . ${\ Displaystyle n = p ^ {2} q}$
3. Wybierz losową liczbę całkowitą takie, że . ${\ displaystyle g \ in \ {2 \ kropki n-1 \}}$${\ Displaystyle g ^ {p-1} \ nie \ equiv 1 \ mod p ^ {2}}$
4. Oblicz . ${\ displaystyle h = g ^ {n} {\ bmod {n}}}$

Klucz publiczny jest wtedy, a klucz prywatny jest . ${\ displaystyle (n, g, h)}$${\ displaystyle (p, q)}$

Szyfrowanie

Wiadomość można zaszyfrować za pomocą klucza publicznego w następujący sposób. ${\ displaystyle m <p}$${\ displaystyle (n, g, h)}$

1. Wybierz losową liczbę całkowitą . ${\ displaystyle r \ in \ {1 \ kropki n-1 \}}$
2. Oblicz . ${\ displaystyle c = g ^ {m} h ^ {r} {\ bmod {n}}}$

Wartością jest szyfrowanie . ${\ displaystyle c}$${\ displaystyle m}$

Deszyfrowanie

Zaszyfrowaną wiadomość można odszyfrować za pomocą klucza prywatnego w następujący sposób. ${\ displaystyle c}$${\ displaystyle (p, q)}$

1. Oblicz . ${\ Displaystyle a = {\ Frac {(c ^ {p-1} {\ bmod {p ^ {2}}}) - 1} {p}}}$
2. Oblicz . i będą liczbami całkowitymi. ${\ Displaystyle b = {\ Frac {(g ^ {p-1} {\ bmod {p ^ {2}}}) - 1} {p}}}$${\ displaystyle a}$${\ displaystyle b}$
3. Korzystając z rozszerzonego algorytmu euklidesowego , obliczyć odwrotność modulo : ${\ displaystyle b}$${\ displaystyle p}$

   ${\ Displaystyle b '= b ^ {- 1} {\ bmod {p}}}$ .

4. Oblicz . ${\ displaystyle m = ab '{\ bmod {p}}}$

Wartość to odszyfrowanie . ${\ displaystyle m}$${\ displaystyle c}$

Przykład

Niech i . Wtedy . Wybierz . Wtedy . ${\ displaystyle p = 3}$${\ displaystyle q = 5}$${\ Displaystyle n = 3 ^ {2} \ cdot 5 = 45}$${\ displaystyle g = 22}$${\ Displaystyle h = 22 ^ {45} {\ bmod {4}} 5 = 37}$

Teraz, aby zaszyfrować wiadomość , wybieramy losowo i obliczamy . ${\ Displaystyle m = 2}$${\ displaystyle r = 13}$${\ Displaystyle c = g ^ {m} h ^ {r} {\ bmod {n}} = 22 ^ {2} 37 ^ {13} {\ bmod {4}} 5 = 43}$

Aby odszyfrować wiadomość 43, obliczamy

${\ Displaystyle a = {\ Frac {(43 ^ {2} {\ bmod {3}} ^ {2}) - 1} {3}} = 1}$ .

${\ Displaystyle b = {\ Frac {(22 ^ {2} {\ bmod {3}} ^ {2}) - 1} {3}} = 2}$ .

${\ Displaystyle b '= 2 ^ {- 1} {\ bmod {3}} = 2}$ .

I wreszcie . ${\ displaystyle m = ab '= 2}$

Dowód poprawności

Chcemy udowodnić, że wartość obliczona w ostatnim kroku deszyfrowania jest równa oryginalnej wiadomości . Mamy ${\ displaystyle ab '{\ bmod {p}}}$${\ displaystyle m}$

${\ Displaystyle (g ^ {m} h ^ {r}) ^ {p-1} \ equiv (g ^ {m} g ^ {nr}) ^ {p-1} \ equiv (g ^ {p-1 }) ^ {m} g ^ {p (p-1) rpq} \ equiv (g ^ {p-1}) ^ {m} \ mod p ^ {2}}$

Aby odzyskać , musimy wziąć logarytm dyskretny o podstawie . ${\ displaystyle m}$${\ displaystyle g ^ {p-1}}$

Grupa

${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*} \ simeq (\ mathbb {Z} / p ^ {2} \ mathbb {Z}) ^ {*} \ times (\ mathbb {Z} / q \ mathbb {Z}) ^ {*}}$ .

Definiujemy H, które jest podgrupą i jego liczność to p-1${\ Displaystyle \ mathbb {Z} / p ^ {2} \ mathbb {Z} ^ {*}}$

${\ Displaystyle H = \ {x: x ^ {p-1} \ mod p ^ {2} = 1 + rp, 0 <r <p \}}$ .

Dla dowolnego elementu x w mamy x ^{p −1}  mod  p ² jest w H , ponieważ p dzieli x ^{p −1}  - 1. ${\ Displaystyle (\ mathbb {Z} / p ^ {2} \ mathbb {Z}) ^ {*}}$

Mapę należy traktować jako logarytm z cyklicznej grupy H do grupy addytywnej i łatwo jest sprawdzić, czy L ( ab ) =  L ( a ) +  L ( b ) i że L jest izomorfizmem między nimi dwie grupy. Podobnie jak w przypadku zwykłego logarytmu, L ( x ) / L ( g ) jest w pewnym sensie logarytmem x o podstawie  g . ${\ Displaystyle L (x) = {\ Frac {x-1} {p}}}$${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$

co jest realizowane przez

${\ Displaystyle {\ Frac {L \ lewo ((g ^ {p-1}) ^ {m} \ prawej)} {L (g ^ {p-1})}}} = m \ mod p.}$

Bezpieczeństwo

Bezpieczeństwo na całej wiadomości można wykazać równoważne faktoringowej n . W semantyczne bezpieczeństwa spoczywa na str -subgroup założeniu, która zakłada, że trudno jest określić, czy element x w w podgrupie rzędu p . Jest to bardzo podobne do problemu z pozostałościami kwadratowymi i problemu wyższych pozostałości . ${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$

Bibliografia

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). „Nowy kryptosystem klucza publicznego tak bezpieczny jak faktoring”. Postępy w kryptologii - EUROCRYPT'98 . Notatki do wykładów z informatyki . 1403 . Skoczek. s. 308–318. doi : 10.1007 / BFb0054135 .