Optimální asymetrické šifrování s odsazením

OAEP ( anglicky  O optimal A symmetric Encryption P added, Optimal asymetrické šifrování s přidáním) je schéma sčítání , které se obvykle používá ve spojení s nějakou jednosměrnou funkcí s tajným vstupem (například funkce RSA nebo Rabin ) ke zvýšení šifrovací síly . toho druhého. OAEP navrhli Mihir Bellare a Phillip Rogaway a jeho aplikace na RSA byla následně standardizována v PKCS#1 a RFC 2437 .

Historie

Původní verze OAEP, navržená Bellare a Rogaway v roce 1994, byla prohlašována za odolná vůči útokům založeným na zvoleném šifrovém textu v kombinaci s jakoukoli jednosměrnou funkcí tajného vstupu . Další studie ukázaly, že takové schéma je odolné pouze vůči útokům založeným na neadaptivním zvoleném šifrovém textu . Navzdory tomu bylo prokázáno, že v modelu náhodného orákula při použití standardního RSA s exponentem šifry je schéma také odolné vůči útokům založeným na adaptivně zvoleném šifrovém textu . Novější práce ukázaly, že ve standardním modelu (když hašovací funkce nejsou modelovány jako náhodná orákula) není možné prokázat odolnost vůči útokům adaptivních šifrových textů při použití RSA .

Algoritmus OAEP

schéma OAEP

Klasické schéma OAEP je dvoubuněčná síť Feistel , kde jsou v každé buňce data transformována pomocí kryptografické hašovací funkce . Jako vstup síť obdrží zprávu s přidanými kontrolními nulami a klíčem - náhodným řetězcem .

Diagram používá následující zápis:

• $n$ - počet bitů v bloku připraveném pro asymetrické šifrování .
• $k_{0}$a  jsou protokolově pevná celá čísla.$k_{1}$
• $m$ — prostý text zprávy, -bitový řetězec.${\displaystyle n-k_{0}-k_{1))$
• $G$a  jsou kryptografické hashovací funkce dané protokolem.$H$

Šifrování

1. Zpráva je připojena nulami, díky čemuž dosahuje délky bitů.$m$$k_{1}$$n-k_{0}$
2. Vygeneruje se náhodný bitový řetězec .$k_{0}$$r$
3. $G$rozšíří kousek řetězce na bity.$k_{0}$$r$$n-k_{0}$
4. $X=m00..0\bigoplus G(r)$.
5. $H$komprimuje bit na bit.$n-k_{0}$$X$$k_{0}$
6. $Y=r\bigoplus H(X)$.
7. zašifrovaný text .$X||Y$

Dešifrování

1. Náhodný řetězec je obnoven$r=Y\bigoplus H(X)$
2. Původní zpráva je obnovena jako$m00..0=X\bigoplus G(r)$
3. Poslední znaky dešifrované zprávy jsou kontrolovány na nulu. Pokud obsahuje nenulové znaky, pak byla zpráva zfalšována útočníkem.$k_{1}$

Aplikace

Algoritmus OAEP se používá k předběžnému zpracování zprávy před použitím RSA . Zpráva je nejprve doplněna na pevnou délku pomocí OAEP a poté zašifrována pomocí RSA. Souhrnně se toto schéma šifrování nazývá RSA-OAEP a je součástí současného standardu šifrování veřejného klíče ( RFC 3447 ). Viktor Bojko také dokázal, že funkce zobrazení v modelu náhodných orakulů je transformací typu vše nebo nic . $g^{G,H}(x)=f(OAEP^{G,H}(x,r))$

Úpravy

Kvůli takovým nedostatkům, jako je nemožnost prokázat kryptografickou odolnost vůči útokům na základě zvoleného šifrového textu , a také nízká rychlost schématu , byly následně navrženy úpravy na bázi OAEP, které tyto nedostatky eliminují.

Algoritmus OAEP+

Victor Shoup , které je odolné vůči adaptivním útokům šifrovaným textem v kombinaci s jakoukoli jednosměrnou funkcí zadních vrátek .

• $n$ - počet bitů v bloku připraveném pro asymetrické šifrování .
• $k_{0}$a  jsou protokolově pevná celá čísla.$k_{1}$
• $m$textová zpráva, -bitový řetězec.${\displaystyle n-k_{0}-k_{1))$
• $G$a jsou kryptografické hashovací funkce  definované protokolem.$H$$H'$

Šifrování

1. Vygeneruje se náhodný bitový řetězec .$k_{0}$$r$
2. $H'$převede na řetězec délky .$r||m$$k_{1}$
3. $G$převede na řetězec délky .$r$${\displaystyle n-k_{0}-k_{1))$
4. Levá strana zprávy se skládá .$X=(G(r)\bigoplus m)||H'(r||m)$
5. $H$převede na řetězec délky .$X$$k_{0}$
6. Pravá strana zprávy se skládá .$Y=H(X)\bigoplus r$
7. zašifrovaný text .$X||Y$

Dešifrování

1. Náhodný řetězec je obnoven .$r=Y\bigoplus H(X)$
2. $X$je rozdělena na dvě části a , s velikostmi a bity, v tomto pořadí.$X_{1}$$X_{2}$${\displaystyle n-k_{1}-k_{0))$$k_{1}$
3. Původní zpráva je obnovena jako .${\displaystyle m=G(r)\bigoplus X_{1))$
4. Pokud není splněna , je zpráva zfalšována.$H'(r||m)=X_{2}$

Algoritmus SAEP/SAEP+

Dan Bonet navrhl dvě zjednodušené implementace OAEP, pojmenované SAEP a SAEP+. Hlavní myšlenkou zjednodušení šifrování je absence posledního kroku – zpráva byla „přilepena“ původně vygenerovaným náhodným řetězcem . Obvody se tedy skládají pouze z jednoho Feistelova článku , díky čemuž je dosaženo zvýšení rychlosti provozu . Vzájemný rozdíl mezi algoritmy je vyjádřen v záznamu kontrolních bitů. V případě SAEP se jedná o nuly, zatímco u SAEP+ se jedná o hash z (respektive jako v OAEP a OAEP+) . Nevýhodou algoritmů je výrazné zkrácení délky zprávy. Spolehlivost schémat v případě použití Rabinovy ​​funkce a RSA byla prokázána pouze s následujícím omezením délky přenášeného textu: pro SAEP + a navíc pro SAEP . Stojí za zmínku, že při přibližně stejné rychlosti má SAEP+ méně omezení na délku zprávy než SAEP , díky čemuž je uznáván jako výhodnější . $r$$m||r$${\displaystyle m\leqslant n/2+k_{0))$$m\leqslant n/4$

Diagram používá následující zápis:

• $n$ - počet bitů v bloku RSA nebo Rabinově kryptosystému .
• $k_{0}$a  jsou protokolově pevná celá čísla.$k_{1}$
• $m$textová zpráva, -bitový řetězec.${\displaystyle n-k_{0}-k_{1))$
• $G$a  jsou kryptografické hashovací funkce dané protokolem.$H$

SAEP+ šifrování

1. Vygeneruje se náhodný bitový řetězec .$k_{0}$$r$
2. $G$převede na řetězec délky .$m||r$$k_{1}$
3. $H$převede na řetězec délky .$r$$n-k_{0}$
4. Vypočteno .$X=(m||G(m||r))\bigoplus H(r)$
5. zašifrovaný text .$X||r$

SAEP+ dešifrování

1. Vypočteno , kde a  jsou řetězce velikosti a , resp.$X_{1}||X_{2}=X\bigoplus H(r)$$X_{1}$$X_{2}$${\displaystyle n-k_{0}-k_{1))$$k_{0}$
2. Rovnost je kontrolována . Pokud je rovnost pravdivá, pak původní zpráva , pokud ne, pak je zpráva podvržena útočníkem.$X_{2}=G(X_{1}||r)$$X_{1}$

Viz také

• RSA-KEM

Literatura

• M. Bellare, P. Rogaway. Optimální asymetrické šifrování – Jak šifrovat pomocí  RSA . - Springer Berlin Heidelberg, 1995. - Sv. 950.-P. 92-111. - ISBN 978-3-540-60176-0 . — ISSN 0302-9743 . - doi : 10.1007/BFb0053428 .
• Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval a Jacques Stern. RSA–OAEP je zabezpečený za předpokladu RSA  . - Springer Berlin Heidelberg, 2001. - Sv. 2139. - S. 260-274. — ISBN 978-3-540-42456-7 . — ISSN 0302-9743 . - doi : 10.1007/3-540-44647-8_16 .
• P. Paillier a J. Villar. Jednosměrné obchodování proti zabezpečení vybraného šifrovaného textu v  šifrování založeném na faktoringu . - Springer Berlin Heidelberg, 2006. - Sv. 4284. - S. 252-266. - ISBN 978-3-540-49475-1 . — ISSN 0302-9743 . - doi : 10.1007/11935230_17 .
• Petr Schartner. Nízkonákladová alternativa pro  OAEP . - 2001. - ISBN 978-1-4503-0882-3 . - doi : 10.1145/2349913.2349914 .
• Obchod Victor. Přehodnoceno OAEP  . - Springer Berlin Heidelberg, 2001. - Sv. 2139. - S. 239-259. — ISBN 978-3-540-42456-7 . — ISSN 0302-9743 . - doi : 10.1007/3-540-44647-8_15 .
• D. Boneh. Zjednodušené OAEP pro funkce RSA a  Rabin . - Springer Berlin Heidelberg, 2001. - Sv. 2139. - S. 275-291. — ISBN 978-3-540-42456-7 . — ISSN 0302-9743 . - doi : 10.1007/3-540-44647-8_17 .
• Viktor Bojko. O bezpečnostních vlastnostech OAEP jako transformace typu vše nebo nic  . - Springer Berlin Heidelberg, 1999. - Sv. 1666. - S. 503-518. — ISBN 978-3-540-66347-8 . — ISSN 0302-9743 . - doi : 10.1007/3-540-48405-1_32 .