Kryptosystém Nakasha-Stern

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. října 2019; kontroly vyžadují 4 úpravy .

Kryptosystém Nakasha- Stern je kryptografický algoritmus s veřejným klíčem založený na výpočetní složitosti problému diskrétního logaritmu . Na rozdíl od RSA je homomorfní s ohledem na sčítání a odčítání, nikoli na násobení .

Vyvinuli David Nakache a Jacques Stern v roce 1998 [1] ve dvou verzích: deterministické a pravděpodobnostní. Jde o vylepšení schématu Benalo [2] - autoři dokázali vybudovat pravděpodobnostní homomorfní kryptosystém se sémantickým zabezpečením a výrazně snížit poměr mezi velikostí šifrového textu a velikostí otevřeného textu .

Existuje implementace (python3) generování klíčů, šifrování a dešifrování algoritmů [3] .

Srovnání s RSA

Podobnosti

Použití čísel RSA [1]

Rozdíly

Použití různých jednosměrných funkcí s tajným vstupem . Jak zdůrazňují autoři [1] , tento bod je velmi teoreticky zajímavý, protože podle jejich názoru v současné době existuje pouze malá paleta jednosměrných funkcí s tajným vstupem, což přímo ovlivňuje rychlost vytváření nové kryptosystémy s veřejným klíčem [1] .
Síla tohoto algoritmu přímo nesouvisí se silou šifrovacího algoritmu kryptosystému RSA . Jmenovitě, bezpečnost RSA souvisí se složitostí problému faktorizace celého čísla a bezpečnost kryptosystému Nakas-Stern souvisí se složitostí problému diskrétního logaritmu [4] .
Kryptosystém RSA je homomorfní s ohledem na násobení, zatímco kryptosystém Nakas-Stern je homomorfní s ohledem na sčítání [1] .

Popis deterministické varianty kryptosystému

Obecně lze deterministickou verzi kryptosystému Nakasha-Stern popsat takto: nechť je B-hladké (B je malé – obvykle 10bitové číslo), liché číslo bez čtverečků a nechť je RSA číslo (obvykle se předpokládá, že je to alespoň 768bitové číslo), které se dělí a je coprime s , kde je Eulerova funkce . Dále nechte objednat . Potom trojice čísel tvoří soukromý klíč. Zpráva menší než je zašifrována jako . Dešifrování je založeno na použití prvočíselných dělitelů čísla [1] . $\sigma$ $n=pq$ $n$ $\sigma$ $\phi(n)$ $\phi (n)/\sigma$ $\phi(n)$ $g\in \mathbb {Z} /n\mathbb {Z}$ $\phi(n)/4$ $p,\ q,\ \sigma$ $m$ $\sigma$ $g^{m}mod\ n$ $\sigma$

Generování klíčů

Vyberte "malá prvočísla " , kde je sudé. Zde fráze "malá prvočísla" znamená, že buď první z prvočísel (1, 3, 5, ...) jsou převzata nebo generována jiným způsobem než pomocí algoritmů pro generování velkých prvočísel. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Nechte , a ${\displaystyle u=\prod _{i=1}^{k/2}p_{i))$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Vyberte 2 "velká prvočísla" , takže , jsou prvočísla. Zde se výraz „velká prvočísla“ používá ve smyslu, ve kterém se používá v algoritmech pro generování velkých prvočísel. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Nechte _ V literatuře se číslo – součin „velkých prvočísel“ – nazývá RSA číslo. $n=pq$ $n$
Vyberte náhodné číslo tak, aby y bylo pořadí $g\ mod\ n$ $G$ $\phi(n)/4$

Poté je veřejný klíč tvořen trojicí čísel . A zavřeno - [1] $\sigma ,\ n,\ g$ $p,\ q$

S narůstajícím počtem se generování klíče stává velmi časově náročnou operací, protože číslo a musí být ve vhodném rozsahu a navíc musí splňovat testy primality spolu s číslem . Aby se tento problém obešel, autoři navrhují nejprve generovat prvočísla a poté výběrem pomocných prvočísel dosáhnout rovnosti a , kde jsou prvočísla [1] . $n$ $p=2au+1$ $a,\ b,\ u,\upsilon$ $p',q'$ $p=2aup'+1$ $q=2b\upsilon q'+1$ $p,\ q$

Šifrování

Šifrování se skládá z jediné operace umocnění modulo : zpráva menší než , je zašifrována jako . A zde se nijak nepoužívají . [jeden] $n$ $m$ $\sigma$ $E(m)=g^{m}mod\ n$ $\sigma$

Dešifrování

Dešifrování je založeno na čínské větě o zbytku . Nechť je prvočíslo dělitele . Algoritmus vypočítá a poté dešifruje zprávu m pomocí čínské věty o zbytku [1] . $p_{i},\ 1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$

Algoritmus vypočítá m i zadaným šifrovým textem , což je přesně . Vyplývá to z následujících výpočtů - zde : . Porovnáním tohoto výsledku se všemi možnými mocninami , lze najít hodnotu . Formálněji je dešifrovací funkce reprezentována pseudokódem [1] : $c=g^{m}mod\ n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$ $g^{m_{i}\phi (n)/p_{i))\ mod\ n$ ${\displaystyle y_{i}=(m-m_{i})/p_{i))$ ${\textstyle c_{i}\ =\ c^{\phi (n)/p_{i))\ =\ g^{m\phi (n)/p_{i))\ =\ g^{(m_ {i}+y_{i}p_{i})\phi (n)/p_{i}}\ =\ g^{m_{i}\phi (n)/p_{i}}g^{y_{ i}\phi (n)}\ =\ g^{m_{i}\phi (n)/p_{i}}\ mod\ n}$ $g^{j\phi (n)/p_{i))$ $m_{{i}}$

pro = 1 až : $i$ $k$
$c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$

pro = 0 až - 1: $j$ $p_{i}$

pokud : $c_{i}==g^{j\phi (n)/p_{i))\ mod\ n$

$m_{i}=j$

$X$ = ChineseReminder( , ) $m_i$ $p_{i}$

Příklad

Generování klíče pro $k = 6$

[cm. "Popis deterministické varianty kryptosystému"]

$p=21211=2*101*3*5*7+1$

$q=928643=2*191*11*13*17+1$

$n=21211*928643=19697446673$

$g=131$

$\sigma =3*5*7*11*13*17$

$p_{1}=3,...,p_{6}=17$

{\displaystyle \{i,j\))

obsahuje

g^{j\phi (n)/p_{i}}\ mod\ n\ mod\ 10000

	i=1	i=2	i=3	i=4	i=5	i=6
j = 0	jeden	jeden	jeden	jeden	jeden	jeden
j = 1	1966	6544	1967	6273	6043	372
j = 2	9560	3339	4968	7876	4792	7757
j = 3		9400	1765	8720	262	3397
j = 4			6488	8651	6291	702
j = 5			2782	4691	677	4586
j = 6				9489	1890	8135
j = 7				8537	6878	3902
j = 8				2312	2571	5930
j = 9				7701	7180	6399
j = 10					8291	9771
j = 11					678	9771
j = 12						609
j = 13						7337
j = 14						6892
j = 15						3370
j = 16						3489

Šifrování $m=202$

$c=g^{m}mod\ n=131202\ mod\ 19697446673$

Dešifrování

$c^{\phi (n)/p_{1}}\ mod\ nmod\ 10000=1996$

$c^{\phi (n)/p_{2}}\ mod\ n\ mod\ 10000=3339$

$c^{\phi (n)/p_{3}}\ mod\ n\ mod\ 10000=2782$

$c^{\phi (n)/p_{4}}\ mod\ n\ mod\ 10000=7994$

$c^{\phi (n)/p_{5}}\ mod\ n\ mod\ 10000=1890$

$c^{\phi (n)/\ p_{6))\ mod\ n\ mod\ 10000=3370$

Dále pomocí výše uvedené tabulky:

$m_{1}=m\ mod\ 3=table(1996)=1$

$m_{2}=m\ mod\ 5=table(3339)=2$

$m_{3}=m\ mod\ 7=table(2782)=1996$

$m_{4}=m\ mod\ 11=table(7994)=4$

$m_{5}=m\ mod\ 13=table(1890)=7$

$m_{6}=m\ mod\ 17=table(3370)=15$

a čínskou větou o zbytku dostáváme: [1] $m=202$

Popis pravděpodobnostní varianty kryptosystému

Pravděpodobnostní varianta kryptosystému je vylepšením předchozích pravděpodobnostních kryptosystémů (například kryptosystému Benalo).

Předchozí kryptosystémy měly velmi podstatnou nevýhodu: pro šifrování malého souboru dat (například hlasy 0, 1 při elektronickém hlasování) nejsou vhodné deterministické kryptosystémy, jako je RSA [1] , protože pro dešifrování bude stačit porovnejte šifrovaný text se zašifrovanými prvky sady . Tato vlastnost kryptosystémů – neschopnost rozlišit šifrové texty různých prvků množiny S, se nazývá sémantická bezpečnost [5] . Ale s kombinací homomorfismu a sémantické síly začaly předchozí kryptosystémy generovat asi kilobajt šifrového textu, aby zašifrovaly otevřený text v několika bitech [1] . V kryptosystému Nakasha-Stern, kromě toho, že má vlastnosti homomorfismu, sémantickou sílu, je poměr mezi velikostí šifrového textu a velikostí otevřeného textu přesně roven . Autoři uvádějí, že je bezpečné užívat [1] . $S$ $S$ $n/\sigma$ $\sigma /n<{\frac {1}{4))$

Generování klíčů

Zvolte "malá prvočísla" , kde je sudé. Zde fráze "malá prvočísla" znamená, že buď první z prvočísel (1, 3, 5, ...) jsou převzata nebo generována jiným způsobem než pomocí algoritmů pro generování velkých prvočísel. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Nechte , a ${\displaystyle u=\prod _{i=1}^{k/2}p_{i))$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Vyberte 2 "velká prvočísla" , takže , jsou prvočísla. Zde se výraz „velká prvočísla“ používá ve smyslu, ve kterém se používá v algoritmech pro generování velkých prvočísel. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Nechť je číslo RSA. $n=pq$
Vyberte náhodné číslo tak, aby y bylo pořadí $g\ mod\ n$ $G$ $\phi(n)/4$

Poté je veřejný klíč tvořen trojicí čísel . A zavřeno - [1] $\sigma ,\ n,\ g$ $p,\ q$

Šifrování

Pravděpodobnostní šifrování je velmi podobné deterministickému šifrování . „Popis deterministické varianty kryptosystému“] . Jmenovitě nechť je náhodně vybrané kladné číslo z okruhu zbytků modulo : . Pak je algoritmus zapsán jako [1] $X$ $n$ $x\in \mathbb {Z} /n\mathbb {Z}$ $E(m)=x^{\sigma }g^{m}mod\ n$

Dešifrování

Dešifrování v pravděpodobnostní verzi algoritmu D. Nakache a J. Sterna zůstává ve srovnání s deterministickou verzí nezměněno [viz. „Popis deterministické varianty kryptosystému“] . Efekt násobení v šifrování je zohledněn, když zvýšíme šifrovaný text na sílu . Udělejme nějaké výpočty, abychom to ověřili. $x^{\sigma }$ ${\displaystyle \phi (n)/p_{i))$

Nechť je prvočíslo dělitele . Algoritmus vypočítá a poté dešifruje zprávu pomocí čínské věty o zbytku. $p_{i},1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$ $m$

Algoritmus počítá s daným šifrovým textem , což je přesně . Vyplývá to z následujících výpočtů: $m_i$ $c=x^{\sigma }g^{m}mod\ n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$ $g^{m_{i}\phi (n)/p_{i))\ mod\ n$

{\begin{matrix}c^{\phi (n)/p_{i))&\equiv &x^{\sigma \phi (n)/p_{i))g^{m\phi (n )/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\& \equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}

Porovnáním tohoto výsledku se všemi možnými mocninami lze najít hodnotu [1] $g^{j\phi (n)/p_{i))$ $m_{{i}}$

Aplikace

V převážné většině oblastí použití kryptosystému Nakasha-Stern se využívá vlastnosti homomorfismu tohoto kryptosystému s ohledem na sčítání a odčítání [6] [2] :

Předpokládejme, že klient má bankovní účet a chce vybrat malou částku . Předpokládáme také, že zůstatek je uložen v zašifrované podobě a zástupce banky, který provádí operaci výběru částky z účtu klienta , nemá přístup k dešifrování údajů o účtu. S pomocí kryptosystému Nakasha-Stern je prostřednictvím operace navrženo jednoduché řešení tohoto problému - jedná se o hodnotu nového zůstatku na účtu v zašifrované podobě: . Formálněji: nechť je účet šifrovací algoritmy , pak se účet rovná součtu a vypočítá se podle následujícího vzorce: [1] . $m$ $u$ $m$ $E(m)$ $u$ $E(m)/E(u)\ mod\ n$ $mu$ $E(m_{1})=g^{m_{1}}mod\ n,\ E(m_{2})=g^{m_{2}}mod\ n$ $m_{1},\ m_{2}$ $m_1$ $m_2$ $E(m_{1})E(m_{2})=g^{m_{1}}g^{m_{2}}mod\ n=g^{m_{1}+m_{2} }mod\n$
Zabezpečení cloud computingu . Předpokládejme, že cloud obsahuje mnoho uživatelů (klientů) . Uživatel má citlivá data uložená v cloudu. Tato cloudová služba se nazývá Storage aaS (storage as a service). Uživatel se může přihlásit do cloudu s požadavkem na výpočet hodnoty některé funkce v závislosti na důvěrných datech. Požadavek musí obsahovat popis funkce , ID uživatele a veřejný klíč uživatele . Cloud musí zkontrolovat výpočetní autoritu uživatele . Takové ověření lze provést pomocí standardního postupu elektronického digitálního podpisu . Pokud uživatel ověřil svá práva k výpočtu funkce , musí cloud vypočítat hodnotu a odeslat ji uživateli. Jako šifrovací funkci lze vzít jakýkoli homomorfní kryptosystém s veřejným klíčem, jako je například kryptosystém Nakache-Stern. Uživatel, který uloží svá citlivá data do úložiště a odešle požadavek na vyhodnocení funkce , cloudu nedůvěřuje a musí přijmout vhodná opatření a požadavky k zajištění jejich bezpečnosti. Je zřejmé, že mnohem bezpečnější by bylo přenášet data tak, aby při operacích, které jsou na nich prováděny, nedocházelo k žádnému šíření informací o těchto datech. Data tedy musí být nejprve zašifrována a na server musí dorazit již v zašifrované podobě. To znamená, že šifrování musí stále provádět uživatel. Zadruhé je nutné tato data zpracovávat bez dešifrování, protože pro přenos a uložení tajného klíče je nutné dodržovat určité postupy , zvláště složité, pokud jsou informace zpracovávány v nedůvěryhodném prostředí. Kryptosystémy s homomorfním šifrováním právě pomáhají tyto problémy řešit [7] [2] . $S$ ${\displaystyle p_{1},...,p_{i},...,p_{l))$ $p_{i}$ $x_{i}$ $p_{i}$ $F$ $F$ ${\displaystyle pk_{i))$ $p_{i}$ $F(x_{i})$ $F$ $E(pk_{i},\ F(x_{i}))$ $E$ $F$

Zmatek k ochraně softwarových produktů. Poprvé bylo použití obfuskace v kryptografii zmíněno v práci Diffieho a Hellmana [8] . V něm se pro sestavení asymetrického kryptosystému navrhuje využít složitost úlohy, která spočívá v analýze programů v nízkoúrovňovém programovacím jazyce (assembler, bytecode). Hlavním účelem mlžení je ztížit pochopení fungování programu. Protože všechny tradiční počítačové architektury používají binární řetězce, použitím plně homomorfního šifrování přes bity lze vypočítat jakoukoli funkci. Proto je možné homomorfně zašifrovat celý program tak, aby si zachoval funkčnost [9] .
Elektronické hlasování. Totiž Budiž kandidáti a ředitelství, které má tento kryptosystém, rozdělí mezi účastníky hlasovací vektor , kde je příjmení kandidáta. A každý účastník má veřejný klíč . V důsledku toho dostaneme - každý volič se vrátí směrem a vector , kde je vektor preferencí. Vítězem volby se stává kandidát, který celkově získal nejvíce hlasů – tento počet – součet hlasů – se počítá přes zašifrované vektory voličů. To je umožněno homomorfismem. A výhodou tohoto přístupu je, že není potřeba dešifrovat voličská data pro sčítání hlasů – zvyšuje se bezpečnost voleb pro voliče [10] . $n$ $(p_{1},...,\ p_{n})$ $p_{i}$ $i$ $pk$ $(\nu _{1},...,\nu _{n})$ ${\displaystyle \nu _{i}\in \{0,1\))$
Oblast vodoznaku [11] . Homomorfismus kryptosystému umožňuje aplikovat na zašifrovaná data vodoznak [12] .
Důkaz nulových znalostí . Homomorfní systémy se používají, když je nutné potvrdit vlastnictví jakékoli informace, kterou lze ověřit, aniž by byla informace samotná prozrazena [13] [14] .

Útoky

Široce známé útoky na tento kryptosystém nejsou zdokumentovány. Sami autoři vybízejí k práci na prolomení kryptosystému. Původní článek nabízel [1] 768 $ někomu, kdo by mohl dešifrovat šifrový text a publikovat metodu kryptoanalýzy . Níže jsou uvedena data pro tento úkol. $C$

$C$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a 16

$G$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743 16

$n$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d 16

Zde ( — se tvoří z prvních prvočísel, kromě 2) [1] . $k=30$ $p_{i}$ $i$

Odkazy

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Jacques, Stern. Nový kryptosystém s veřejným klíčem založený na vyšších zbytcích // ACM . - 1998. - S. 59–66 . Archivováno z originálu 6. prosince 2006.
↑ 1 2 3 A.I. Troubey. Homomorfní šifrování: Zabezpečení cloud computingu a další aplikace (recenze) (ruština) // Informatika. - 2015. - leden. Archivováno z originálu 26. listopadu 2018.
↑ Implementace šifrování, dešifrování, algoritmů generování klíčů v kryptosystému Nakashe-Stern . Získáno 16. prosince 2018. Archivováno z originálu dne 28. prosince 2020. (neurčitý)
↑ Thomas W. Cusick. Srovnání RSA a kryptosystému veřejného klíče Naccache-Stern // Security Protocols. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. — S. 111–116 . — ISBN 9783540624943 , 9783540680475 . - doi : 10.1007/3-540-62494-5_10 . Archivováno z originálu 2. prosince 2018.
↑ S. Goldwasser, S. Micali. Pravděpodobnostní šifrování (anglicky) // JCSS. - 1984. - Duben. - str. 270-299 .
↑ Stručný přehled homomorfních kryptosystémů a jejich aplikací // International Journal of Computer Applications. — 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. O databankách a homomorfismech soukromí // Základy bezpečného počítání.
↑ W. Diffie, M. Hellman. Nové směry v kryptografii // IEEE Trans. inf. teorie.
↑ J. Alwen [et al.] O vztahu mezi funkčním šifrováním, mlžením a plně homomorfním šifrováním // Cryptography and Coding – 14th IMA Intern. Konf., IMACC-2013..
↑ JD Cohen Benaloh. Verifiable Secret-Ballot Elections (anglicky) // Yale University: Ph-D disertační práce. — 1988.
↑ B. Pfitzmann, M. Schunter. Asymetrické otisky prstů (anglicky) // Spinger-Verlag. - 1996. - S. 84-95 .
↑ Vytvoření bezpečného schématu vodoznaku závislého na obsahu pomocí homomorfního šifrování.
↑ O. Goldreich, S. Micali, A. Wigderson. Důkazy, které nepřinášejí nic jiného než jejich platnost a metodologie návrhu kryptografických protokolů . - 1986. - S. 174-187 .
↑ G. Brassard, D. Chaum, C. Crepeau. Minimální diskusní důkazy znalostí // JCSS. - 1988. Archivováno 27. září 2011.

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta