Šifrování ACE - ACE Encrypt

ESO (Pokročilý kryptografický stroj) - sběr jednotek, implementující jak schéma šifrování veřejného klíče, tak schéma digitálního podpisu. Odpovídající názvy těchto schémat - «ACE Encrypt» a «ACE Sign». Schémata jsou založena na schématu šifrování veřejného klíče Cramer-Shoup a schématu podpisu Cramer-Shoup. Představené varianty těchto schémat jsou určeny k dosažení dobré rovnováhy mezi výkonem a zabezpečením celého šifrovacího systému.

Autoři

Všechny algoritmy implementované v ACE jsou založeny na algoritmech vyvinutých Victorem Shoupem a Ronaldem Cramerem. Úplnou specifikaci algoritmů napsal Victor Shoup. Implementaci algoritmů provádějí Thomas Schweinberger a Mehdi Nassehi, jeho podporu a údržbu provádí Victor Shoup. Thomas Schweinberger se podílel na konstrukci dokumentu specifikace ACE a také napsal uživatelskou příručku.

Ronald Cramer v současné době zůstává na univerzitě v Aarhusu, Dánsko. Během svého pobytu v ETH pracoval na projektu ACE Encrypt Curych, Švýcarsko.

Mehdi Nassehi a Thomas Schweinberger pracovali na projektu ACE ve výzkumné laboratoři IBM v Curych, Švýcarsko.
Victor Shoup pracuje ve výzkumné laboratoři IBM v Curych, Švýcarsko.

Bezpečnostní

Schéma šifrování v ACE lze prokázat jako bezpečné za rozumných a přirozených předpokladů praktičnosti. Tyto čtyři předpoklady jsou:

• Předpoklad Rozhodovací Diffie-Hellman (DDH)
• Silný předpoklad RSA
• Odolnost proti kolizi SHA - 1 sekunda
• Pseudonáhodnost režimu MARS součet / čítač

Základní terminologie a notace

Zde uvádíme několik notací, které se používají v tomto článku.

Základní matematická notace

${ displaystyle Z ,}$ - Sada celých čísel.
${ displaystyle F_ {2} [T] ,}$ - Sada jednorozměrných polynomů s koeficienty v konečném poli ${ displaystyle F_ {2} ,}$ mohutnosti 2.
${ displaystyle Aremn ,}$ - celé číslo ${ displaystyle r in left {0, ..., n-1 right }}$ takhle ${ displaystyle A equiv r (modn)}$ pro celé číslo ${ displaystyle n> 0 ,}$ a ${ displaystyle A v Z ,}$.
${ displaystyle Aremf ,}$ - polynom ${ displaystyle r in F_ {2} [T]}$ s ${ displaystyle deg (r)$ takhle ${ displaystyle A equiv r (modf)}$ s ${ displaystyle A, f ve F_ {2} [T], f neq 0 ,}$.

Základní řetězcová notace

${ displaystyle A ^ { ast} ,}$ - Sada všech řetězců.
${ displaystyle A ^ {n} ,}$ - Sada všech řetězců o délce n.
Pro ${ displaystyle x v A ^ { ast} L (x)}$ - délka provázku ${ displaystyle x ,}$. Řetězec délky nula je označen ${ displaystyle lambda _ {A} ,}$.
Pro ${ displaystyle x, y v A ^ { ast}}$ ${ displaystyle x || y ,}$ - výsledek ${ displaystyle x ,}$ a ${ displaystyle y ,}$ zřetězení.

Bity, bajty, slova

${ displaystyle b { stackrel { mathrm {def}} {=}} vlevo {0,1 vpravo }}$ - Sada bitů.
Vezměme si všechny sady formulářů ${ displaystyle b, b ^ {n_ {1}}, (b ^ {n_ {1}}) ^ {n_ {2}}, ...}$. Pro takovou množinu A definujeme "nulový prvek":

${ displaystyle 0_ {b} { stackrel { mathrm {def}} {=}} 0 v b}$;
${ displaystyle 0_ {A ^ {n}} { stackrel { mathrm {def}} {=}} (0_ {A}, ..., 0_ {A}) v A ^ {n}}$ pro ${ displaystyle n> 0 ,}$.

Definujeme ${ displaystyle B { stackrel { mathrm {def}} {=}} b ^ {8}}$ jako sada bajtů a ${ displaystyle W { stackrel { mathrm {def}} {=}} b ^ {32}}$ jako soubor slov.

Pro ${ displaystyle x v A ^ { ast} ,}$ s ${ displaystyle A in left {b, B, W right } ,}$ a ${ displaystyle l> 0 ,}$ definujeme operátor výplně:

${ displaystyle pad_ {l} (x) { stackrel { mathrm {def}} {=}} { begin {cases} x, & L (x) geq l x || 0_ {A ^ {lL (x)}}, & L (x)$.

Operátor převodu

Operátor převodu ${ displaystyle I_ {src} ^ {dst}: src rightarrow dst}$ provede převod mezi prvky ${ displaystyle Z, F_ {2} [T], b ^ { ast}, B ^ { ast}, W ^ { ast}}$.

Schéma šifrování

Pár šifrovacích klíčů

Schéma šifrování využívá dva typy klíčů:
Veřejný klíč ACE: ${ displaystyle (P, q, g_ {1}, g_ {2}, c, d, h_ {1}, h_ {2}, k_ {1}, k_ {2}) ,}$.
Soukromý klíč ACE: ${ displaystyle (w, x, y, z_ {1}, z_ {2}) ,}$.
Pro daný velikostní parametr m ${ displaystyle m ,}$, takový, že ${ Displaystyle 1024 leq m leq 16384}$, klíčové komponenty jsou definovány jako:
${ displaystyle q ,}$ - 256bitové prvočíslo.
${ displaystyle P ,}$ - m-bitové prvočíslo, takové ${ displaystyle P equiv 1 (modq)}$.
${ displaystyle g_ {1}, g_ {2}, c, d, h_ {1}, h_ {2} ,}$ - elementy ${ displaystyle left {1, ..., P-1 right }}$ (jehož multiplikativní pořadí modulo ${ displaystyle P ,}$ rozděluje ${ displaystyle q ,}$).
${ displaystyle w, x, y, z_ {1}, z_ {2} ,}$ - elementy ${ displaystyle left {0, ..., q-1 right }}$.
${ displaystyle k_ {1}, k_ {2} ,}$ - elementy ${ displaystyle B ^ { ast}}$ s ${ displaystyle L (k_ {1}) = 20l ^ { prime} +64}$ a ${ displaystyle L (k_ {2}) = 32 levý lceil l / 16 pravý rceil +40}$, kde ${ displaystyle l = levý lceil m / 8 pravý rceil}$ a ${ displaystyle l ^ { prime} = L_ {b} ( left lceil (2 left lceil l / 4 right rceil +4) / 16 right rceil)}$.

Generování klíčů

Algoritmus. Generování klíčů pro šifrovací schéma ACE.
Vstup: parametr velikosti m ${ displaystyle m ,}$, takový, že ${ Displaystyle 1024 leq m leq 16384}$.
Výstup: pár veřejného / soukromého klíče.

1. Vytvořte náhodný prime ${ displaystyle q ,}$, takový, že ${ displaystyle 2 ^ {255}$.
2. Vytvořte náhodný prime ${ displaystyle P ,}$, ${ displaystyle 2 ^ {m-1}$

   , takový, že ${ displaystyle P equiv 1 (modq)}$.

3. Vygenerujte náhodné celé číslo ${ displaystyle g_ {1} in left {2, ..., P-1 right }}$, takový, že ${ displaystyle g_ {1} ^ {q} ekviv 1 (modP)}$.
4. Generujte náhodná celá čísla ${ displaystyle w in left {1, ..., q-1 right }}$ a ${ displaystyle x, y, z_ {1}, z_ {2} in left {0, ..., q-1 right }}$
5. Vypočítejte následující celá čísla v ${ displaystyle left {1, ..., P-1 right }}$:${ displaystyle g_ {2} leftarrow g_ {1} ^ {w} remP}$,
   ${ displaystyle c leftarrow g_ {1} ^ {x} remP}$,
   ${ displaystyle d leftarrow g_ {1} ^ {y} remP}$,
   ${ displaystyle h_ {1} leftarrow g_ {1} ^ {z_ {1}} remP}$,
   ${ displaystyle h_ {2} leftarrow g_ {1} ^ {z_ {2}} remP}$.
6. Generujte náhodné bajtové řetězce ${ displaystyle k_ {1} v B ^ {20l ^ { prime} +64}}$ a ${ displaystyle k_ {2} v B ^ {2 vlevo lceil l / 16 vpravo rceil +40}}$, kde ${ displaystyle l = L_ {B} (P) ,}$ a ${ displaystyle l ^ { prime} = L_ {B} ( left lceil (2 left lceil l / 4 right rceil +4) / 16 right rceil)}$.
7. Vraťte pár veřejného a soukromého klíče ${ displaystyle ((P, q, g_ {1}, g_ {2}, c, d, h_ {1}, h_ {2}, k_ {1}, k_ {2}), (w, x, y , z_ {1}, z_ {2})) ,}$

Zastoupení šifrovacího textu

Šifrovací text šifrovacího schématu ACE má formu

${ displaystyle (s, u_ {1}, u_ {2}, v, e) ,}$,

kde jsou komponenty definovány jako:
${ displaystyle u_ {1}, u_ {2}, v ,}$ - celá čísla z ${ displaystyle left {1, ..., P-1 right }}$ (jehož multiplikativní pořadí modulo ${ displaystyle P ,}$ rozděluje ${ displaystyle q ,}$).
${ displaystyle s ,}$ - prvek ${ displaystyle W ^ {4} ,}$.
${ displaystyle e ,}$ - prvek ${ displaystyle B ^ { ast} ,}$.
${ displaystyle s, u_ {1}, u_ {2}, v ,}$ říkáme preambule, a ${ displaystyle e ,}$ - kryptogram. Pokud je cleartext řetězec skládající se z ${ displaystyle l ,}$ байт, pak délka ${ displaystyle e ,}$ je rovný ${ Displaystyle l + 16 left lceil l / 1024 right rceil}$.
Musíme představit funkci ${ displaystyle CEncode ,}$, který mapuje ciphertext na jeho bajtový řetězec

reprezentace a odpovídající inverzní funkce ${ displaystyle CDecode ,}$. Pro celé číslo ${ displaystyle l> 0 ,}$, řetězec slov ${ displaystyle s ve W ^ {4}}$celá čísla ${ displaystyle 0 leq u_ {1}, u_ {2}, proti <256 ^ {l}}$a bajtový řetězec ${ displaystyle e v B ^ { ast}}$,

${ displaystyle CEncode (l, s, u_ {1}, u_ {2}, v, e) { stackrel { mathrm {def}} {=}} I_ {W ^ { ast}} ^ {B ^ { ast}} (s) || pad_ {l} (I_ {Z} ^ {B ^ { ast}} (u_ {1})) || pad_ {l} (I_ {Z} ^ {B ^ { ast}} (u_ {2})) || pad_ {l} (I_ {Z} ^ {B ^ { ast}} (v)) || e v B ^ { ast}}$.

Pro celé číslo ${ displaystyle l> 0 ,}$, bajtový řetězec ${ displaystyle psi v B ^ { ast}}$, takový, že ${ displaystyle L ( psi) geq 3l + 16}$,

${ displaystyle CDecode (l, psi) { stackrel { mathrm {def}} {=}} (I_ {B ^ { ast}} ^ {W ^ { ast}} ({ Bigl [} psi { Bigr]} _ {0} ^ {16}), I_ {B ^ { ast}} ^ {Z} ({ Bigl [} psi { Bigr]} _ {16} ^ {16+ l}), I_ {B ^ { ast}} ^ {Z} ({ Bigl [} psi { Bigr]} _ {16 + l} ^ {16 + 2l}), I_ {B ^ { ast}} ^ {Z} ({ Bigl [} psi { Bigr]} _ {16 + 2l} ^ {16 + 3l}), { Bigl [} psi { Bigr]} _ {16+ 3l} ^ {L ( psi)}) ve W ^ {4} krát Z krát Z krát Z krát B ^ { ast}}$.

Proces šifrování

Algoritmus. Provoz asymetrického šifrování ACE.
vstup: veřejný klíč ${ displaystyle (P, q, g_ {1}, g_ {2}, c, d, h_ {1}, h_ {2}, k_ {1}, k_ {2}) ,}$ a bajtový řetězec ${ displaystyle M v B ^ { ast} ,}$.
Výstup: byte byte - ciphertext ${ displaystyle psi }$ z ${ displaystyle M ,}$.

1. generovat ${ displaystyle r in left {0, ..., q-1 right }}$ nahodile.
2. Vygenerujte úvodní část šifrovacího textu:
   1. generovat ${ displaystyle s ve W ^ {4} ,}$ nahodile.
   2. Vypočítat ${ displaystyle u_ {1} leftarrow g_ {1} ^ {r} remP}$, ${ displaystyle u_ {2} leftarrow g_ {2} ^ {r} remP}$.
   3. Vypočítat ${ displaystyle alpha leftarrow UOWHash ^ { prime} (k_ {1}, L_ {B} (P), s, u_ {1}, u_ {2}) v Z ,}$; Všimněte si, že ${ displaystyle 0 < alpha <2 ^ {160} ,}$.
   4. Vypočítat ${ displaystyle v leftarrow c ^ {r} d ^ { alpha r} remP ,}$.
3. Vypočítejte klíč pro operaci symetrického šifrování:
   1. ${ displaystyle { tilde {h_ {1}}} leftarrow h_ {1} ^ {r} remP}$, ${ displaystyle { tilde {h_ {2}}} leftarrow h_ {2} ^ {r} remP}$.
   2. Vypočítat ${ displaystyle k leftarrow ESHash (k, L_ {B} (P), s, u_ {1}, u_ {2}, { tilde {h_ {1}}}, { tilde {h_ {2}} }) ve W ^ {8} ,}$.
4. Vypočítejte kryptogram ${ displaystyle e leftarrow SEnc (k, s, 1024, M)}$.
5. Zakódujte šifrovací text: ${ displaystyle psi leftarrow CEncode (L_ {B} (P), s, u_ {1}, u_ {2}, v, e)}$.
6. Vrátit se ${ displaystyle psi }$.

Před zahájením procesu symetrického šifrování zadejte vstupní zprávu ${ displaystyle M v B ^ { ast} ,}$ je rozdělen do bloků ${ displaystyle M_ {1}, ..., M_ {t} ,}$, kde každý z bloku, případně kromě posledního, má 1024 bajtů. Každý blok je šifrován proudovou šifrou. Pro každý šifrovaný blok ${ displaystyle E_ {i} ,}$ Vypočítá se 16bajtový ověřovací kód zprávy. Dostaneme kryptogram

${ displaystyle e = E_ {1} || C_ {1} || ... || E_ {t} || C_ {t} ,}$.${ Displaystyle L (e) = L (M) +16 levý lceil L (M) / m pravý rceil}$.

Všimněte si, že pokud ${ displaystyle L (M) = 0 ,}$, pak ${ displaystyle L (e) = 0 ,}$.

Algoritmus. Proces asymetrického šifrování ACE.
Vstup: ${ displaystyle (k, s, M, m) ve W ^ {8} krát W ^ {4} krát Z krát B ^ { ast} ,}$ ${ displaystyle m> 0 ,}$
Výstup: ${ displaystyle e v B ^ {l}}$, ${ Displaystyle l = L (M) +16 levý lceil L (N) / m pravý rceil}$.

1. Li ${ displaystyle M = lambda _ {B} ,}$, pak se vraťte ${ displaystyle lambda _ {B} ,}$.
2. Inicializovat stav pseudonáhodného generátoru:${ displaystyle genState leftarrow InitGen (k, s) v GenState}$
3. Vygenerujte klíč ${ displaystyle k_ {AXU} AXUHash ,}$: ${ displaystyle (k_ {AXU}, genState) leftarrow GenWords ((5L_ {b} ( left lceil m / 64 right rceil) +24), genState).}$.
4. ${ displaystyle e leftarrow lambda _ {B}, i leftarrow 0}$.
5. Zatímco ${ displaystyle i$, Udělej následující:
   1. ${ displaystyle r leftarrow min (L (M) -i, m)}$.
   2. Generovat hodnoty masky pro šifrování a MAC:
      1. ${ displaystyle (mask_ {m}, genState) leftarrow GenWords (4, genState)}$.
      2. ${ displaystyle (mask_ {e}, genState) leftarrow GenWords (r, genState)}$.
   3. Šifrovat holý text: ${ displaystyle enc leftarrow { Bigl [} M { Bigr]} _ {i} ^ {i + r} oplus mask_ {e}}$.
   4. Vygenerujte ověřovací kód zprávy:
      1. Li ${ displaystyle i + r = L (M) ,}$, pak ${ displaystyle lastBlock leftarrow 1}$; jiný ${ displaystyle lastBlock leftarrow 0}$.
      2. ${ displaystyle mac leftarrow AXUHash (k_ ​​{AXU}, lastBlock, enc) ve W ^ {4}}$.
   5. Aktualizujte šifrovací text: ${ displaystyle e leftarrow e || enc || I_ {W ^ { ast}} ^ {B ^ { ast}} (mac oplus mask_ {m})}$.
   6. ${ displaystyle i leftarrow i + r}$.
6. Vrátit se ${ displaystyle e ,}$.

Proces dešifrování

Algoritmus. Proces dešifrování ACE.
Vstup: veřejný klíč ${ displaystyle (P, q, g_ {1}, g_ {2}, c, d, h_ {1}, h_ {2}, k_ {1}, k_ {2}) ,}$ a odpovídající soukromý klíč ${ displaystyle (w, x, y, z_ {1}, z_ {2}) ,}$, byt e řetězec ${ displaystyle psi v B ^ { ast}}$.
Výstup: Dešifrovaná zpráva ${ displaystyle M v B ^ { ast} cup {Odmítnout}}$.

1. Dešifrovat šifrovací text:
   1. Li ${ displaystyle L ( psi) <3L_ {B} (P) +16 ,}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
   2. Vypočítat: ${ displaystyle (s, u_ {1}, u_ {2}, v, e) leftarrow CDecode (L_ {B} (P), psi) v W ^ {4} krát Z krát Z krát Z krát B ^ { ast}}$;
      Všimněte si, že ${ displaystyle 0 leq u_ {1}, u_ {2}, proti <256 ^ {l}}$, kde ${ displaystyle l = L_ {B} (P) ,}$.
2. Ověření preambule šifrovacího textu:
   1. Li ${ displaystyle u_ {1} geq P}$ nebo ${ displaystyle u_ {2} geq P}$ nebo ${ displaystyle v geq P}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
   2. Li ${ displaystyle u_ {1} ^ {q} neq 1remP}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
   3. ${ displaystyle odmítnout leftarrow 0 ,}$.
   4. Li ${ displaystyle u_ {2} neq u_ {1} ^ {w} remP}$, pak ${ displaystyle odmítnout leftarrow 1 ,}$.
   5. Vypočítat ${ displaystyle alpha leftarrow UOWHash ^ { prime} (k_ {1}, L_ {B} (P), s, u_ {1}, u_ {2}) v Z}$; Všimněte si, že ${ displaystyle 0 leq alpha leq 2 ^ {160}}$.
   6. Li ${ displaystyle v neq u_ {1} ^ {x + { alpha} y} remP}$, pak ${ displaystyle odmítnout leftarrow 1 ,}$.
   7. Li ${ displaystyle reject = 1 ,}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
3. Vypočítejte klíč pro operaci symetrické dešifrování:
   1. ${ displaystyle { tilde {h_ {1}}} leftarrow u_ {1} ^ {z_ {1}} remP}$, ${ displaystyle { tilde {h_ {2}}} leftarrow u_ {1} ^ {z_ {2}} remP}$.
   2. Vypočítat ${ displaystyle k leftarrow ESHash (k_ ​​{2}, L_ {B} (P), s, u_ {1}, { tilde {h_ {1}}}, { tilde {h_ {2}}}) ve W ^ {8}}$.
4. Vypočítat ${ displaystyle M leftarrow SDec (k, s, 1024, e)}$;Všimněte si, že ${ displaystyle SDec ,}$ může se vrátit ${ displaystyle Odmítnout ,}$.
5. Vrátit se ${ displaystyle M ,}$.

Algoritmus. Dešifrovací operace ${ displaystyle SDec ,}$.
Vstup: ${ displaystyle (k, s, m, e) ve W ^ {8} krát W ^ {4} krát Z krát B ^ { ast} ,}$ ${ displaystyle m> 0 ,}$
Výstup: Dešifrovaná zpráva ${ displaystyle M v B ^ { ast} cup {Odmítnout}}$.

1. Li ${ displaystyle e = lambda _ {B} ,}$, pak se vraťte ${ displaystyle lambda _ {B} ,}$.
2. Inicializovat stav pseudonáhodného generátoru: ${ displaystyle genState leftarrow InitGen (k, s) v GenState}$
3. Vygenerujte klíč ${ displaystyle k_ {AXU} AXUHash ,}$: ${ displaystyle (k_ {AXU}, genState ^ { prime}) leftarrow GenWords ((5L_ {b} ( left lceil m / 64 right rceil) +24), genState).}$.
4. ${ displaystyle M leftarrow lambda _ {B}, i leftarrow 0}$.
5. Zatímco ${ Displaystyle i$, Udělej následující:
   1. ${ displaystyle r leftarrow min (L (e) -i, m + 16) -16}$.
   2. Li ${ displaystyle r leq 0}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
   3. Generovat hodnoty masky pro šifrování a MAC:
      1. ${ displaystyle (mask_ {m}, genState) leftarrow GenWords (4, genState)}$.
      2. ${ displaystyle (mask_ {e}, genState) leftarrow GenWords (r, genState)}$.
   4. Ověřte ověřovací kód zprávy:
      1. Li ${ Displaystyle i + r + 16 = L (M) ,}$, pak ${ displaystyle lastblock leftarrow 1}$; jiný ${ displaystyle lastblock leftarrow 0}$.
      2. ${ displaystyle mac leftarrow AXUHash (k_ ​​{AXU}, lastBlock, { Bigl [} e { Bigr]} _ {i} ^ {i + r}) ve W ^ {4}}$.
      3. Li ${ displaystyle { Bigl [} e { Big]} r_ {i + r} ^ {i + r + 16} neq I_ {W ^ { ast}} ^ {B ^ { ast}} (mac oplus mask_ {m})}$, pak se vraťte ${ displaystyle Odmítnout ,}$.
   5. Aktualizujte holý text: ${ displaystyle M leftarrow M || ({ Bigl [} e { Bigr]} _ {i} ^ {i + r}) oplus mask_ {e})}$.
   6. ${ displaystyle i leftarrow i + r + 16}$.
6. Vrátit se ${ displaystyle M ,}$.

Podpisové schéma

Schéma podpisu využívá dva klíčové typy:
Veřejný klíč podpisu ACE: ${ displaystyle (N, h, x, e ^ { prime}, k ^ { prime}, s) ,}$.
Soukromý klíč podpisu ACE: ${ displaystyle (p, q, a) ,}$.
Pro daný parametr velikosti ${ displaystyle m ,}$, takový, že ${ Displaystyle 1024 leq m leq 16384}$, klíčové komponenty jsou definovány následujícím způsobem:
${ displaystyle p ,}$ — ${ Displaystyle left lfloor m / 2 right rfloor}$-bitové prvočíslo s ${ displaystyle (p-1) / 2 ,}$ - je také prvočíslo.
${ displaystyle q ,}$ — ${ Displaystyle left lfloor m / 2 right rfloor}$-bitové prvočíslo s ${ displaystyle (q-1) / 2 ,}$ - je také prvočíslo.
${ displaystyle N ,}$ — ${ displaystyle N = pq ,}$a má buď ${ displaystyle m ,}$ nebo ${ displaystyle m-1 ,}$ бит.
${ displaystyle h, x ,}$ - elementy ${ displaystyle left {1, ..., N-1 right }}$ (kvadratické zbytky modulo ${ displaystyle N ,}$).
${ displaystyle e ^ { prime} ,}$ - 161bitové prvočíslo.
${ displaystyle a ,}$ - prvek ${ displaystyle left {0, ..., (p-1) (q-1) / 4-1 right }}$
${ displaystyle k ^ { prime} ,}$ - elementy ${ displaystyle B ^ {184} ,}$.
${ displaystyle s ,}$ - elementy ${ displaystyle B ^ {32} ,}$.

Generování klíčů

Algoritmus. Generování klíčů pro schéma podpisu veřejného klíče ACE.
Vstup: parametr velikosti ${ displaystyle m ,}$, takový, že ${ Displaystyle 1024 leq m leq 16384}$.
Výstup: pár veřejného / soukromého klíče.

1. Generujte náhodná prvočísla${ displaystyle p, q ,}$, takový, že ${ displaystyle (p-1) / 2 ,}$ a ${ displaystyle (q-1) / 2 ,}$ - je také prvočíslo a ${ displaystyle 2 ^ {m_ {1} -1}$

   , ${ displaystyle 2 ^ {m_ {2} -1}$,

   č ${ Displaystyle p neq q}$,
   kde
   ${ displaystyle m_ {1} = levý lfloor m / 2 pravý rfloor}$ a ${ displaystyle m_ {1} = levý lceil m / 2 pravý rceil}$.
2. Soubor ${ displaystyle N leftarrow pq}$.
3. Vygenerujte náhodné prvočíslo ${ displaystyle e ^ { prime} ,}$, где ${ displaystyle 2 ^ {160} leq e ^ { prime} leq 2 ^ {161}}$.
4. Generovat náhodně ${ displaystyle h ^ { prime} in left {1, ..., N-1 right }}$, s přihlédnutím ${ displaystyle gcd (h ^ { prime}, N) = 1}$ a ${ displaystyle gcd (h ^ { prime} pm 1, N) = 1}$a vypočítat ${ displaystyle h leftarrow (h ^ { prime}) ^ {- 2} remN}$.
5. Generovat náhodně ${ displaystyle a in left {0, ..., (p-1) (q-1) / 4-1 vpravo }}$a počítat ${ displaystyle x leftarrow h ^ {a} remN}$.
6. Generujte náhodné bajtové řetězce ${ displaystyle k ^ { prime} v B ^ {184} ,}$, a ${ displaystyle s v B ^ {32} ,}$.
7. Vrátit pár veřejného a soukromého klíče ${ displaystyle ((N, h, x, e ^ { prime}, k ^ { prime}, s), (p, q, a)) ,}$.

Podpisové prohlášení

Podpis v podpisovém schématu ACE má formu ${ displaystyle (d, w, y, y ^ { prime}, { tilde {k}})}$, kde jsou komponenty definovány následujícím způsobem:
${ displaystyle d ,}$ - prvek ${ displaystyle B ^ {64} ,}$.
${ displaystyle w ,}$ - celé číslo, takové ${ displaystyle 2 ^ {160} leq w leq 2 ^ {161}}$.
${ displaystyle y, y ^ { prime} ,}$ - elementy ${ displaystyle left {1, ..., N-1 right }}$.
${ displaystyle { tilde {k}} ,}$ - prvek ${ displaystyle B ^ { ast} ,}$;Všimněte si, že ${ displaystyle L ({ tilde {k}}) = 64 + 20L_ {B} ( left lceil (L (M) +8) / 64 right rceil)}$, kde ${ displaystyle M ,}$ - podepsaná zpráva.

Musíme představit ${ displaystyle SEncode ,}$ funkce, která mapuje podpis do jeho reprezentace bajtového řetězce, a odpovídající inverzní funkce ${ displaystyle SDecode ,}$. Pro celé číslo ${ displaystyle l> 0 ,}$, bajtový řetězec ${ displaystyle d v B ^ {64}}$celá čísla ${ displaystyle 0 leq w leq 256 ^ {21}}$ a ${ displaystyle 0 leq y, y ^ { prime} <256 ^ {l}}$a bajtový řetězec ${ displaystyle { tilde {k}} v B ^ { ast}}$,

${ displaystyle SEncode (l, d, w, y, y ^ { prime}, { tilde {k}}) { stackrel { mathrm {def}} {=}} d || pad_ {21} ( I_ {Z} ^ {B ^ { ast}} (w)) || pad_ {l} (I_ {Z} ^ {B ^ { ast}} (y)) || pad_ {l} (I_ { Z} ^ {B ^ { ast}} (y ​​^ { prime})) || { tilde {k}} v B ^ { ast}}$.

Pro celé číslo ${ displaystyle l> 0 ,}$, bajtový řetězec ${ displaystyle sigma v B ^ { ast}}$, kde ${ displaystyle L ( sigma) geq 2l + 53}$,

${ displaystyle CSecode (l, sigma) { stackrel { mathrm {def}} {=}} ({ Bigl [} sigma { Bigr]} _ {0} ^ {64}, I_ {B ^ { ast}} ^ {Z} ({ Bigl [} sigma { Bigr]} _ {64} ^ {85}), I_ {B ^ { ast}} ^ {Z} ({ Bigl [ } sigma { Bigr]} _ {85} ^ {85 + l}), I_ {B ^ { ast}} ^ {Z} ({ Bigl [} sigma { Bigr]} _ {85+ l} ^ {85 + 2l}), { Bigl [} sigma { Bigr]} _ {85 + 2l} ^ {L ( sigma)}) v B ^ {64} krát Z krát Z krát Z krát B ^ { ast}}$.

Proces generování podpisu

Algoritmus. Proces generování podpisu ACE.
Vstup: veřejný klíč ${ displaystyle (N, h, x, e ^ { prime}, k ^ { prime}, s) ,}$ a odpovídající soukromý klíč ${ displaystyle (p, q, a) ,}$ a bajtový řetězec ${ displaystyle M v B ^ { ast} ,}$, ${ displaystyle 0 leq L (M) leq 2 ^ {64}}$.
Výstup: bajtový řetězec - digitální podpis ${ displaystyle sigma v B ^ { ast} ,}$.

1. K hašování vstupních dat proveďte následující kroky:
   1. Vygenerujte hash klíč ${ displaystyle { tilde {k}} v B ^ {20m + 64}}$ náhodně, takhle ${ displaystyle m = L_ {b} ( vlevo lceil (L (M) +8) / 64 vpravo rceil)}$.
   2. Vypočítat ${ displaystyle m_ {h} leftarrow I_ {W ^ { ast}} ^ {Z} (UOWHash ^ { prime prime} ({ tilde {k}}, M))}$.
2. Vybrat ${ displaystyle { tilde {y}} in left {1, ..., N-1 right }}$ náhodně a vypočítat ${ displaystyle y ^ { prime} leftarrow { tilde {y}} ^ {2} remN}$.
3. Vypočítat ${ displaystyle x ^ { prime} leftarrow (y ^ { prime}) ^ {r ^ { prime}} h ^ {m_ {h}} remN}$.
4. Vytvořte náhodný prime ${ displaystyle e ,}$, ${ displaystyle 2 ^ {160} leq e leq 2 ^ {161}}$a jeho osvědčení o správnosti ${ displaystyle (w, d) ,}$: ${ displaystyle (e, w, d) leftarrow GenCertPrime (s) ,}$. Tento krok opakujte do ${ displaystyle e neq e ^ { prime} ,}$.
5. Soubor ${ displaystyle r leftarrow UOWHash ^ { prime prime prime} (k ^ { prime}, L_ {B} (N), x ^ { prime}, { tilde {k}}) v Z }$; Všimněte si, že ${ displaystyle 0 leq r <2 ^ {160}}$.
6. Vypočítat ${ displaystyle y leftarrow h ^ {b} remN}$, kde ${ displaystyle b leftarrow e ^ {- 1} (a-r) rem (p ^ { prime} q ^ { prime})}$,
   a kde ${ displaystyle p ^ { prime} = (p-1) / 2}$ a ${ displaystyle q ^ { prime} = (q-1) / 2}$.
7. Zakódujte podpis: ${ displaystyle sigma leftarrow SEncode (L_ {B} (N), d, w, y, y ^ { prime}, { tilde {k}})}$.
8. Vrátit se ${ displaystyle sigma ,}$

Poznámky

V definici procesu šifrování ACE a procesu ACE Signature se používají některé pomocné funkce (např.UOWHash, ESHash a některé další), jejichž definice přesahuje tento článek. Více podrobností najdete na в.^[1]

Implementace, využití a výkon

Šifrovací schéma ACE doporučuje NESSIE (New European Schemes for Signatures, Integrity and Encryption) jako asymetrické šifrovací schéma. Tisková zpráva je vydána do února 2003.

Obě schémata byla implementována v ANSI C s využitím knihovny GNU GMP. Testy byly prováděny na dvou platformách: Power PC 604 model 43P pod systémem AIX a 266 MHz Pentium pod systémem Windows NT. Tabulky výsledků:

Tabulka 1. Časové náklady na základní operace.

Tabulka 2. Výkon šifrovacího schématu a podpisového schématu.

Literatura

externí odkazy

• http://www.alphaworks.ibm.com/tech/ace
• http://www.zurich.ibm.com/security/ace/
• NESSIE Portfolio doporučených kryptografických primitiv