Prob hc P Prob hc P ProbP

Tonda Beneš

Ochrana informace – jaro 2011

Charakteristika dobré šifry Množství práce vynaložené na šifrování a dešifrování by m lo být úm rné požadovanému stupni utajení. Šifrovací algoritmus by nem l obsahovat zbyte ná omezení. Implementace algoritmu by m la být co nejjednodušší. Chyby p i šifrování by se nem ly p íliš ší it a ovliv ovat následující komunikaci. Zprávy by se zašifrováním nem ly zv tšovat. Security through obscurity NEFUNGUJE! Zmatení (confusion) - nelze predikovat, jakou zm nu zašifrovaného textu vyvolá by jen malá zm na otev eného textu složitá funk ní závislost mezi zašifrovaným textem a párem klí - otev ený text. Difuze (diffusion) - zm na otev eného textu se promítá do mnoha míst zašifrovaného textu. Bezpe ný systém - nelze získat otev ený text na základ znalosti odpovídající šifry kryptoanalytik hledá transformaci h : C

P, h nebývá jednozna ná

Efektivn bezpe ný systém - Prob(h(C) = P) < .

Ideální stav Perfektní utajení (perfect secrecy) - m jme n možných otev ených text , stejné množství klí a možných šifer.

ProbC1 h C1

P

Prob h C1

P

Prob P

Redundance po et bit nutný k reprezentaci všech znak abecedy

A

An

log 2 k

po et všech možných zpráv délky n = 2 , z toho R nazýváme rate jazyka. Redundance je definována Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

2 Rn

smysluplných.

1 / 19

Tonda Beneš


D

A R

Pokud algoritmus šifruje n kolik r zných zpráv, z nichž jedna je smysluplná, do stejné šifry, systém m že být bezpe ný.

Public-key systémy (systémy s ve ejným klí em) použití jednosm rných (trapdoor) funkcí - snadno vy íslitelná funkce, jejíž inversní funkci lze efektivn po ítat pouze se znalostí (malého) množství dodate ných informací. Nezávislé na zpráv . každý uživatel vlastní pár klí : ve ejný (public) klí - znám všem uživatel m systému, používá se k šifrování zpráv zasílaných tomuto uživateli tajný, soukromý (private) klí - uživatel uchovává v tajnosti, používá jej k dešifrování došlých zpráv tajný klí nelze efektivn odvodit ze znalosti odpovídajícího ve ejného klí e výhodou systém s ve ejnými klí i je relativn malé množství používaných klí , možnost vytvá ení ve ejn ov itelných elektronických podpis , v tší flexibilita správy klí ového materiálu

Merkle-Hellman systém založen na problému batohu, p enášená zpráva je chápána jako vektor ešení, enášena je výsledná suma - "hmotnost batohu" a1, a2, … an - posloupnost celých ísel, T cílová suma = hmotnost batohu, hledáme vektor v takový, aby

i

ai vi

T

nech posloupnost a1, a2, … an je superrostoucí, problém nalezení vektoru v je v tomto p ípad zvládnutelný v lineárním ase

Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

2 / 19

Tonda Beneš


Konstrukce systému zvolíme superrostoucí posloupnost s1, s2, … sn, dále vybereme íslo w a modul m, w bereme nesoud lné s m, m > sn. Ze zvolených hodnot sestavíme již obecnou posloupnost

hi

w * si mod m

Posloupnost {si}i=1…n a ísla w a m utajíme, dále budou sloužit jako soukromý klí . Posloupnost {hi}i=1…n zve ejníme jakožto ve ejný klí .

Šifrování Otev ený text P rozd líme na bloky délky n bit . Každý blok Pj nahradíme sumou

Cj

p ji hi i

Zašifrovaný text C odešleme

Dešifrování Autorizovaný p íjemce vypo ítá w-1 - z vlastností w a m ur it existuje. Pro každý blok Cj spo ítá Cj * w-1 . Vy eší problém batohu se superrostoucí posloupností {si}i=1…n pro všechny hodnoty získané v p edchozím bod . Konkatenací ešení vznikne p vodní zpráva P.

Korektnost dešifrování w-1e(p) mod m = w-1(p 1h1 + p 2h2 + … + p nhn) mod m = = p 1 w-1h1 + p 2 w-1h2 + … + p n w-1hn mod m = = p 1 w-1ws1 + p 2 w-1ws2 + … + p n w-1wsn mod m = = p 1s1 + p 2s2 + … + p nsn mod m.

Poznámky k implementaci Pro rozumné aplikace: m bývá voleno ve velikosti 100 až 200 íslic, si mají délku 200 až 400 íslic, Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

3 / 19

Tonda Beneš


batoh mívá p ibližn 200 položek

možný zp sob vytvo ení superrosotoucího batohu: vygenerujeme n náhodných ísel ri z intervalu <0, 2200> si = 2200 + i - 1 + ri

Analýza Merkle-Hellmanova systému Známe-li m, je možné odvodit prvky superrostoucího batohu. Položme

p

ho

h1

mod m

Pak ovšem platí

p

w * so w * s1

mod m

so

s1

mod m

Spo ítáme posloupnost

D

i * p mod m

2m i 1

Pro n jaké k ovšem nastane

k * p mod m

k * s0 * 1 s1 mod m

s0

Lze o ekávat, že s0 bude nejmenším prvkem D. Známe-li s0, lze spo ítat w a tedy všechny si. Hodnoty w a m je možné odhadovat pouze z posloupnosti {hi}i=1…n. Hodnota m je tší než libovolné hi. Budeme zkoušet r zné hodnoty pro w.


4 / 19

Tonda Beneš


Možné správné hodnoty w se nacházejí v p ekrývajících se bodech diskontinuity. K prolomení Merkle-Hellmanova systému tedy není nutné vy ešit obecný problém batohu, ale sta í použít nazna eného postupu, který je daleko rychlejší. M-H systém tedy není vhodný k ochran d ležitých informací.

El Gamal kryptosystém založen na obtížnosti výpo tu diskrétního logaritmu nad okruhem

Konstrukce kryptosystému Spole ný modul q, dále je zvoleno íslo g co nejvyššího ádu (nejlépe generátor). Každý ú astník i si zvolí tajný klí yi a vypo ítá ve ejný klí g

yi

mod q

Šifrování nech uživatel A posílá zprávu P (< q) uživateli B náhodn vybere íslo k a vypo ítá: k

g y B mod q

g mod q; P k

ob

ísla zašle B

Dešifrování uživatel B vypo ítá

g

k yB

mod q

a ur í inverzní prvek. S jeho použitím z druhého ísla zp tn získá P.

Korektnost dešifrování ejm

Pg

yB k

g

k yB

1

Pg

yB k

g

yB k

1

P

Analýza El Gamalova kryptosystému kryptosystém je považován za bezpe ný, nevýhodou je nutnost generování náhodných ísel k a zdvojnásobení objemu dat i šifrování, je relativn pomalý Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

5 / 19

Tonda Beneš


Rivest-Shamir-Adelman kryptosystém uve ejn ný v roce 1977, n kdy ozna ován jako kód Herkules Kryptoschéma je založeno na Eulerov formuli

a

n

1 mod n

1

kde (n) je po et ísel z intervalu 1,…, n, která jsou s n nesoud lná. Platí:

p1 1 p1a 1

n

1

p 2 1 p a2 2

1

p k 1 p ak k

1

2

kde

n

p1a1 p2a2

pka k

3

je prvo íselný rozklad ísla n.

Šifrování je t eba znát íslo n a malé prvo íslo e. Otev ený text P evedeme na posloupnost ísel modulo n. Každý blok Pj zašifrujeme dle vzorce

Cj

Pj

e

mod n

(4) Spojením výsledných blok Cj vznikne zašifrovaný text.

Dešifrování je t eba znát íslo n, a íslo d. Každý z blok Cj dešifrujeme takto:

Pj

Cj

d

mod n

(5)

Výpo et dešifrovacího klí e d Musí platit Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

6 / 19

Tonda Beneš


ed 1 mod

n

(6)

Prvo íslo e nesmí d lit (n). d ur íme z p edchozího vztahu rozší eným Euclidovým algoritmem. Mimochodem, uvažte následující postup: Nalezneme

r

n e

Ze (2) plyne

r

e 2

mod e

(7)

e 1 , s použitím (1)

n

n

e

1

mod e

(8)

Položíme tedy

r

d

n e

1 (9)

… tedy existuje více než jeden dešifrovací klí V praxi volíme e pevné (65535), pro každého ú astníka nalezneme zvláštní n a dopo ítáme dešifrovací klí . d se po ítá rozší eným Euklidovým algoritmem.

Korektnost dešifrování S použitím (1) a (6) postupn dostáváme

Pj Výb r klí

ed

Pj

ed mod

n

Pj

1

Pj

mod n

, implementa ní poznámky

Ve ejný klí tvo í pár (n, e), soukromý klí pár (n, d). íslo n musí být velmi velké, nesmí mít malé faktory. Pro reálné použití p ibližn 100 až 200 bit . Nech n je sou inem prvo ísel p a q. Klí e volíme jako prvo íslo v tší než (p - 1) a (q - 1). Hranice bezpe nosti 1024 bit modulu n, rozumné 1500 bit , lépe 2048 Nejlepším sou asným algoritmem pro faktorizaci velkých ísel je NFS (Number Field Sieve), které rozkládá ísla prakticky bez ohledu na strukturu Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

7 / 19

Tonda Beneš


2n i této volb

má nep ítel na výb r zhruba

ln n

1050 100 ln 10 možných

prvo íselných initel .

Invertování ísla v okruhu lení ísel, p ípadn výpo et inverzní hodnoty v rámci okruhu (t lesa) – nelze samoz ejm pro tzv. d litele nuly používá se rozší ený Euclid v algoritmus (viz. níže), uvažte, že ax 1 (mod d)

Rozší ený Euclid v algoritmus vstup: nezáporná ísla a a b, a b výstup: d = gcd(a, b) a celá ísla x, y tž. ax + by = d if (b = 0) do d enddo x2 1, x1 0, y2 while b > 0 do q

a, x 0, y1

0, return (d, x, y)

1

a b ,r

b, b enddo d a, x x2, y return (d, x, y)

1, y

a qb, x r, x2 x1, x1

x2 q x1, y y2 q y1 x, y2 y1, y1 y

y2

Volba prvo ísel Vygenerujeme náhodné liché íslo zvoleného ádu Otestujeme prvo íselnost Není-li prvo íslo, pokra ujeme bodem 1.

Testy prvo íselnosti Pro každé liché p irozené íslo n definujeme množinu W(n) pro a Zn lze v polynomiálním ase ov it, zda a W(n) pokud je n prvo íslo, W(n) = pokud je n složené, | W(n)| >= n/2 Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

Zn :

8 / 19

Tonda Beneš


Prvky množiny W(n) nazýváme sv dky toho, že íslo n je složené.¨, ostatním ísl m v Zn - W(n) íkáme lhá i.

Solovay-Strassen v test prvo íselnosti Základem je tzv. Eulerovo kritérium: Pro liché prvo íslo p platí r spl ující nsd(p, r) = 1

p 1 2

J r , p mod n pro všechna celá ísla r

Ze skute nosti, že pro p liché existuje maximáln p-1 lze odvodit následující algoritmus:

p / 2 lhá pro ísla 1, 2, ...

p íslo, které zkoumáme, r libv. íslo, pak nutn nsd(p, r) = 1 a zárove

J r, p

rp

12

mod p

kde J(r, p) je Jacobiho funkce, definovaná následovn

pro r

1 J r, p

J r 2, p *

1

J p mod r , r *

p2 1 8

1

r 1 p 1 4

1

pro r sudé pro r liché , r

1

zvolíme náhodn r tž. 2 r p 2 p 1 2 mod p spo ítáme n r pokud n 1 a n p 1 konec, je složené spo ítáme s = J(r, p), pokud není n s konec, je složené asi prvo íslo Opakováním testu pro r zné hodnoty r lze docílit požadované jistoty, že p je skute prvo íslo.

Miller-Rabin v test prvo íselnosti Založen na následující skute nosti: Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

9 / 19

Tonda Beneš


Pro liché p irozené íslo p tž. p - 1 = 2ls, kde s je liché bu a celé íslo takové, že s nsd(a,p) = 1. Potom a

0

j

1 mod p , nebo

a2

j

s

1 mod p

pro n jaké j tž.

l 1

Odtud odvodíme následující algoritmus: Dáno testované íslo p. Nech p - 1 = 2ls, pro n jaké liché s Náhodn zvolíme a { 2, … , p - 2}

a s mod p . Pokud q 1mod p konec, asi prvo íslo. p 1 2 1mod p , konec ítáme q2, q2, … , q = ap - 1, vše mod p. Pokud není a

Spo ítáme

q

l

Po - nem že být prvo íslo.

q2

k

1 mod n . Pokud q 2

k

Nalezeme nejv tší k tak, že asi prvo íslo, jinak nem že být prvo íslo.

1 mod p , konec -

Analýza RSA není známa metoda vedoucí k rozbití tohoto algoritmu. slabostí je hypotetická možnost vytvo it elektronický podpis zprávy bez znalosti dešifrovacího klí e na základ zachycení vhodných p edchozích zašifrovaných zpráv.

M d Ld

ML

d

Systémy nad eliptickými k ivkami Problémem „klasického“ po ítání kryptografických algoritm nad Zn je zna ná existence relativn rychlých faktoriza ních i logaritmujících algoritm trikem je p enést po ítání známých algoritm do algebraických struktur, kde by tyto kryptoanalytické metody nefungovaly jme q p r , p 5 a vhodné a a b rozumíme množinu bod E Fq

{( x, y ) Fq2 | y 2

Fq. Eliptickou k ivkou nad okruhem Fq

x 3 ax b} { }


10 / 19

Tonda Beneš


nazýváme bod v nekone nu. Plní úlohu nulového prvku. Nech P = (x, y) je bod k ivky. Zavedeme –P = (x, –y), P + Q je pr se ík k ivky s p ímkou definovanou body P a Q, pokud P = Q, bereme tangentu. Ozna ení nP používáme pro

P P

P

n-krát

Obdobou umoc ování p irozených ísel je zde práv uvedené násobení. Problém hledání diskrétního logaritmu zde má podobu: Pro dané P, Q nalézt n takové, že Q = nP

uvedený popis problému diskrétního logaritmu nad eliptickou k ivkou p ímo umož uje implementovat El-Gamal kryptosystém, nebo D-H. podobn je možné zavést problém faktorizace a definovat Eulerovu funkci (n ) , což umož uje implementovat RSA

Konstrukce kryptosystému nad takto definovanou grupou m žeme používat obvyklé šifrovací algoritmy, jako El-Gamal v kryptosystém, RSA, Diffie-Hellman v systém vým ny klí . žné umoc ování pouze nahradíme s ítáním

Analýza systém nad eliptickými k ivkami Obecn se má za to, že použití eliptických k ivek p ináší zvýšení bezpe nosti algoritmu. Pro dosažení stejné míry bezpe nosti vysta íme s kratším klí em. Odhaduje se, že 1024 bitovému klí i „normálního“ RSA odpovídá eliptický klí o délce pouhých 163 bit . Naopak, pro dosažení bezpe nosti odpovídající 571 bitovému eliptickému klí i je t eba 15360 bit „normálního“ klí e.


11 / 19

Tonda Beneš


Podepisovací schémata digitální podpis asociuje zprávu a (jejího) odesílatele obecn v rámci podepisovacího procesu se nejprve provede mapování prvku prostoru zpráv do tzv. podepisovacího prostoru (zpravidla p idáním redundance, paddingem, hashováním, ...), odkud jej podepisovací schéma (na základ tajného klí e) mapuje do prostoru podpis klasifikace podepisovacích schémat - s p íponou (dig. signature with appendix) – pot ebují p vodní zprávu jako vstup verifika ního procesu - s obnovou zprávy (dig. signature with message recovery) – p vodní zpráva je rekonstruována z dat vlastního podpisu v závislosti na tom, zda existuje pouze jedno mapování (bijekce) z prostoru zpráv do podepisovacího prostoru rozd lujeme podepisovací schémata na - randomizovaná - deterministická

Obecný postup podepisování s p íponou zvolíme mapování k zajiš ující redundanci ~ m - spo ítáme m ~ , kde S je podepisovací algoritmus závislý na tajném - podpisem je s S A,k m A,k klí i entity A a konkrétním algoritmu pro p idání redundance k pro hashování se volí vhodná CRHF pro verifikaci je t eba podpis s a p vodní zpráva m ~ m ~, s - spo ítáme m a u VA m - podpis je p ijat pokud u je true

Obecný postup podepisování s obnovou zprávy - zvolíme mapování k zajiš ující redundanci ~ Rm - spo ítáme m ~ , kde S je podepisovací algoritmus závislý na tajném - podpisem je s S A,k m A,k klí i entity A a konkrétním algoritmu pro p idání redundance k Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

12 / 19

Tonda Beneš


funkce pro dopln ní redundance R musí být invertibilní a je ve ejn známa, podepisovací prostor, do kterého mapuje prostor zpráv musí být podstatn v tší, jinak bude schéma náchylné na existenciální podvržení, tj. bude možné sestavovat páry zpráva-podpis bez znalosti tajného klí e (by bez možnosti kontrolovat obsah zprávy) pro verifikaci je t eba podpis s a p vodní zpráva m ~ V s - spo ítáme a m A ~ je prvkem obrazu prostoru zpráv v podepisovacím - podpis je p ijat pokud m prostoru 1 ~ - rekonstruujeme p vodní zprávu m R m

Podepisovací schéma RSA deterministické podepisovací schéma s obnovou zprávy založeno na obtížnosti faktorizace velkých ísel Inicializace – generování klí stejn jako v p ípad RSA šifrování zvolíme dv velká prvo ísla p a q spo ítáme n = pq a = (p – 1)(q – 1) zvolíme e nesoud lné s a spo ítáme d tž. ed 1 mod ve ejným klí em je dvojice (n, e), tajným klí em d Podpis ~ Rm - spo ítáme m - a následn podpis s

~ d mod n m

Ov ení podpisu ~ s e mod n a ov íme, že není poškozena redundance - spo ítáme m 1 ~ - obnovíme p vodní zprávu m R m Bezpe nost podp. schématu RSA schéma trpí vlastností multiplikativnosti ( i. homomorfismu), tj. pokud znám podpis dvou zpráv, mohu bez znalosti klí e sestavit podpis t etí zprávy, která je jejich sou inem, pokud by funkce pro p idání redundance byla sama multiplikativní volba parametr odpovídá volb pro RSA šifrování Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

13 / 19

Tonda Beneš


Rabinovo podepisovací schéma podobné RSA, ale používá sudý pevn stanovený ve ejný exponent e podepisovací prostor je prostorem kvadratických reziduí mod n Inicializace – generování klí každý ú astník vygeneruje dv velká prvo ísla p a q a spo ítá n = pq n je ve ejným klí em, dvojice (p, q) tajným klí em Podpis ~ - spo ítáme m

Rm e ~ m mod n - podpisem je s

obvykle se e volí 2 ~ je skute není jisté, že výsledné m kvadratickým reziduem, existuje modifikace schématu, která to zajistí, p ípadn je možné p idat ke zpráv ást náhodných dat, jejichž zm nou docílíme residuosity (v pr ru 2 pokusy) Ov -

ení podpisu ~ s e mod n spo ítáme m ~ ov íme, že není poškozena redundance v m 1 ~ obnovíme p vodní zprávu m R m

Bezpe nost Rabinova podepisovacího schématu bezpe nost zavisí na kvalit funkce p idávající redundanci

DSA – data signature algorithm založen na problému diskrétního logaritmu podepisovací schéma s p íponou (appendix), pro hashování se používá SHA-1 standardizováno jako FIPS186 (DSS) Inicializace – generování klí - každý ú astník zvolí náhodn prvo ísla q a p t.ž. q | (p – 1) g p 1 q mod p pro libovoln zvolené g aby - a generátor - dále zvolí náhodn a t.ž. 1 a

1

q 1


14 / 19

Tonda Beneš


a

mod p - a spo ítá y ve ejným klí em je tve ice (p, q, , y), tajným klí em je a. Podpis pro podpis zprávy m: - zvolíme náhodn k, 0 < k < q k mod p mod q , s spo ítáme r podpisem je pár (r, s)

-

k

1

m

ar mod q

Ov ení podpisu - ov ovatel verifikuje, že 0 < r < q a 0 < s < q 1 m mod q a u2 s 1r mod q - spo ítá u1 s u1

u2

y mod p mod q - a následn v podpis je p ijat pokud v = r a platí shora uvedené požadavky na r a s

Bezpe nost DSA q se volí ve velikosti 160 bit , zatímco p má délku násobku 64 mezi 512 a 1024 bity, doporu uje se alespo 768 bit bezpe nost se opírá o obtížnost po ítání diskrétního logaritmu v *p a jeho cyklické podgrup o ádu q bezpe nostní vlastnosti jsou podobné jako v p ípad El-Gamalova podepisovacího schématu.

Podepisovací schéma ElGamal randomizované podepisovací schéma s p íponou je zobecn ním principu DSA Inicilizace – generování klí každý ú astník zvolí náhodn prvo íslo p a generátor dále vybere náhodné íslo a, 1 a

multiplikativní grupy

* p

p 2

a

mod p a spo ítá y ve ejným klí em je trojice (p, , y), tajným klí em je a Podepisování Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

15 / 19

Tonda Beneš


- zvolíme náhodné celí íslo k, 1 k p 2 nesoud lné s p – 1 k mod p a s k 1 m ar mod p 1 - spo ítáme r podpisem je dvojice (r, s) Ov ení podpisu - ov ovatel verifikuje, že 1 r p 1 m r s - a spo ítá v1 y r mod p a v2 podpis je p ijat pokud v1 = v2 a platí shora uvedené požadavky na r Bezpe nost schéma je bezpe né pokud z stává t žký problém diskrétního logaritmu je nutné volit k náhodn pro každou podepisovanou zprávu, v opa ném p ípad je možné s velkou pravd podobností k zjistit a následn dopo ítat tajný parametr a, nebo k

m1 m2 mod p 1 s1 s2

pro volbu velikosti parametr platí p ibližn totéž, co pro RSA

Podepisovací schéma Merkle pro jednorázové podpisy umož uje s daným tajným klí em podepsání práv jedné zprávy i podepsání další zprávy je možná fabrikace podpisu je nezbytná d ryhodná t etí strana na validaci parametr algoritmu Inicializace zvolíme t n lg n 1 náhodných et zc k1, k2, ... kt, každý o délce l a uchováme je v tajnosti spo ítáme vi ki pro 1 i t pomocí vhodné CRHF ve ejným klí em je t-tice (v1, v2, ... vt,), tajným (k1, k2, ... kt,) Podpis pro podpis zprávy m o délce n: - spo ítáme c .... po et nul ve zpráv m - a sestavíme w = m|c = (a1, a2, ... at,) - podpisem je výb r (s1, s2, ... su,), který vznikne z (k1, k2, ... kt,) vybráním t ch ki, kde ai=1 Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

16 / 19

Tonda Beneš


Ov ení podpisu - spo ítáme c .... po et nul ve zpráv m - a sestavíme w = m|c = (a1, a2, ... at,) s j pro všechny pozice, kde ai=1 - ov íme, že vi j Bezpe nost Merkelova schématu pokud je použita kvalitní CRHF, je schéma bezpe né

Neodmítnutelné (Undeniable) podpisy ... k ov ení podpisu je nezbytná spolupráce podepisujícího

Podepisovací schéma Chaum-van Antwerpen neodmítnutelné podepisovací schéma Inicializace – generování klí - každý ú astník zvolí náhodn prvo íslo p = 2q + 1 pro n jaké prvo íslo q p 1 q mod p tak, aby 0 - náhodn zvolí v *p a spo ítá a

mod p - dále náhodn vybere 0 < a < q a spo ítá y ve ejným klí em je trojice (p, , y), tajným klí em a Podpis pro podpis zprávy m podepisující a spo ítá podpis s m mod p Ov ení podpisu - ov ovatel zvolí náhodná ísla x1, x2, tž. 0 < xi < q x x - spo ítá z s 1 y 2 mod p a výsledek zašle podepisujícímu - podepisující zašle ov ujícímu w z x x mod p - ov ující spo ítá w m - podpis je p ijat pokud w = w 1

a

1

mod p , kde aa

1

1 mod q

2

Odmítnutí podpisu


17 / 19

Tonda Beneš


používá se pro ov ení, zda podepisovatel odmítá potvrdit platný podpis, i zda podpis je podvrhem - ov ovatel zvolí náhodná ísla x1, x2, tž. 0 < xi < q a spo ítá z výsledek zašle podepisujícímu a

s x1 y x2 mod p a

1

1 1 mod q - podepisující zašle ov ujícímu w z mod p , kde aa x x mod p ov ovatel akceptuje a ukon í protokol - pokud w m x x - ov ovatel zvolí náhodná ísla x 1, x 2, tž. 0 < xi < q a spo ítá z s 1 y 2 mod p a výsledek zašle podepisujícímu 1

2

a

1

z mod p , kde aa 1 1 mod q - podepisující zašle ov ujícímu w x x mod p ov ovatel akceptuje a ukon í protokol - pokud w m 1

2

x1

x

x2 1 mod p - ov ovatel spo ítá c w x mod p a c w - pokud c = c , ov ovatel potvrdí, že podpis je podvrhem, v opa ném p ípad se domnívá, že podepisovatel odmítá potvrdit platný podpis 2

Pravd podobnostní šifrování zajiš uje, že stejný plaintext je p i opakovaném použití stejného klí e šifrován na jiný zašifrovaný text

Kryptosystém Blum – Goldwasser založen na složitosti faktorizace celých ísel jádrem BBS generátor náhodných ísel

inicializace každý ú astník zvolí dv prvo ísla p a q kongruentní s 3 mod 4 n = pq ... tzn. n je Blumovo íslo pomocí rozší eného Euklidova algoritmu ur íme a a b tž. ap + bq = 1 n je ve ejný klí , (p, q, a, b) je tajný klí

šifrování i inicializaci šifrování zvolíme náhodn r a spo ítáme x0 = r2 mod n Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

18 / 19

Tonda Beneš


tzn. x0 je kvadratické reziduum mod n i-tý blok plaintextu pi šifrujeme takto:

xi

xi2 1 mod n

ci = p i

xi

výsledkem šifrování zpráva (c1, c2, ..., ct, xt+1)

dešifrování spo ítáme

u

xt

p 1 4 1

t 1

mod p 1

mod p a v

xt

q 1 4 1

t 1

mod q 1

mod q

odsud x0 = vap + ubq mod n dále obdobn jako v p ípad šifrování spo ítáme xi pro dešifrování i-tého bloku korektnost dešifrování uvažme p 1 4

xt p1 1 4 xt2 xt p 1 2 xt xt (mod p ) , nebo kvadratické reziduum), opakováním dostaneme

u

x

p 1 4 t 1

t 1

xt p

1 2

1(mod p )

(xt

je

x0 (mod p )

obdobn lze dovodit

v

xt

q 1 4 1

t 1

x0 (mod q)

protože ap + bq = 1, vap ubq x0 mod p a vap ubq x0 mod q nutn x0 = vap + ubq mod n je zkonstruováno správn

Bezpe nost algoritmus je ekvivalentní s problémem faktorizace velkých ísel velikost n volit obdobn jako v p ípad RSA náchylný na choosen-ciphertext attack


19 / 19

Prob hc P Prob hc P ProbP

Recommend Documents