Matematické Fórum

xy3000 · 29. 12. 2009 18:37 — Editoval xy3000 (29. 12. 2009 18:37)

Ahoj, mám problém s následující úlohou, tedy spíše s její druhou půlkou.

Tady je postup :

Code:

1. Zvolit dvě různá náhodná prvočísla p a q.
2. Spočítat jejich součin n = pq.
3. Spočítat hodnotu Eulerovy funkce φ(n) = (p − 1)(q − 1).
4. Zvolit celé číslo e menší než φ(n), které je s φ(n) nesoudělné.
5. Naleznou číslo d tak, aby platilo de ≡ 1 (mod φ(n)).
6. Jestli e je prvočíslo tak d = (1+r*φ(n))/e, kde r = [(e-1)φ(n)^(e-2)]

1. Mám prvočísla: p=61 , q=53
2. Součin je 3233.
3. Eulerova funkce mě vychází 3120, tady si už ale nejsem jist jestli je to správně
4. Tady nevím, prosím pomoct
5. Tady nevím, prosím pomoct
6. Tady nevím, prosím pomoct

Olin · 29. 12. 2009 18:46

A co je v tom za problémy? Ten postup hovoří poměrně jasně. Co je nejasného na tom, že
$\varphi(n) = (p-1)(q-1) = 60 \cdot 52 = 3120$ ?

mikee · 29. 12. 2009 18:50

↑ xy3000:
Myslim, ze hodnotu Eulerovej funkcie mas dobre.
Co sa tyka bodu (4), tak jednoducho si rozloz cislo 3120 na sucin prvocisel, no a potom hladane cislo 'e' dostanes ako sucin nejakych prvocisel, lubovolne zvolenych, ale ktore nie su na tomto zozname (zozname prvociselnych delitelov cisla 3120).
Je to dostatocne zrozumitelne? :)

xy3000 · 29. 12. 2009 19:21 — Editoval xy3000 (29. 12. 2009 19:23)

mikee napsal(a):
↑ xy3000:
Myslim, ze hodnotu Eulerovej funkcie mas dobre.
Co sa tyka bodu (4), tak jednoducho si rozloz cislo 3120 na sucin prvocisel, no a potom hladane cislo 'e' dostanes ako sucin nejakych prvocisel, lubovolne zvolenych, ale ktore nie su na tomto zozname (zozname prvociselnych delitelov cisla 3120).
Je to dostatocne zrozumitelne? :)

Ale jak ten rozklad mám udělat ? Nešlo by to napsat názorně.

Ani nerozumím tomu jak dostanu to číslo d.

mikee · 29. 12. 2009 19:38

↑ xy3000:
No rozklad na prvocisla ziskame tak, ze delime dane cislo prvocislami az kym nam z neho neostane prvocislo, pricom tie delitele zapisujeme :) Napriklad v nasom pripade mame cislo 3120. Je delitelne cislom 2 a 3120 : 2 = 1560 (zoznam prvocisel je zatial: 2). Cislo 1560 sa stale da delit dvomi, takze 1560 : 2 = 780 (zoznam prvocisel je zatial 2.2). Takto pokracujeme, samozrejme pravdepodobne coskoro dospejeme k cislu, ktore uz dvomi delitelne nebude, potom skusime 3 atd :) Skoncime ked nam po vydeleni zostane prvocislo a toto prvocislo tiez pridame do zoznamu a mame rozklad na prvocisla :)

FailED · 29. 12. 2009 19:42 — Editoval FailED (29. 12. 2009 19:46)

↑ xy3000:

4) Nejjednodušší je když zvolíš číslo o 1 menší, to je určitě nesoudělné (dělitelnost rozdílu). A i 5) Pak uděláš snadno když víš, že $e \equiv -1\qquad $mod\quad \varphi (n)$$

xy3000 · 29. 12. 2009 20:59 — Editoval xy3000 (29. 12. 2009 21:01)

Chtěl jsem jen ověřit jistý výpočet napíši ho sem celý. Stále tomu nerozumím, čím dál více tomu nerozumím.

Zde je text.

Code:

Tvorba klíčového páru

1. Nejprve si bude Alice muset vyrobit pár veřejného a soukromého klíče:
2. Zvolí dvě různá velká náhodná prvočísla p a q.
3. Spočítá jejich součin n = pq.
4. Spočítá hodnotu Eulerovy funkce φ(n) = (p − 1)(q − 1).
5. Zvolí celé číslo e menší než φ(n), které je s φ(n) nesoudělné.
6. Nalezne číslo d tak, aby platilo de ≡ 1 (mod φ(n)).
7. Jestli e je prvočíslo tak d = (1+r*φ(n))/e, kde r = [(e-1)φ(n)^(e-2)]

Code:

Zašifrování zprávy

Bob nyní chce Alici zaslat zprávu M. Tuto zprávu převede 
nějakým dohodnutým postupem na číslo m (m < n). Šifrovým textem
 odpovídajícím této zprávě pak je číslo
c = me mod n

Tento šifrový text poté zašle nezabezpečeným kanálem Alici.

Code:

Dešifrování zprávy

Alice od Boba získá šifrovaný text c. Původní zprávu m získá následujícím výpočtem:
m = cd mod n.

Fakt, že tímto výpočtem získáme původní zprávu, je důsledkem následující rovnosti:
cd ≡ (me)d ≡ med (mod n).

A jelikož ed ≡ 1 (mod p − 1) a ed ≡ 1 (mod q − 1), díky malé Fermatově větě platí, že
med ≡ m (mod p)

a zároveň
med ≡ m (mod q)

Jelikož p a q jsou různá prvočísla, pomocí čínské věty o zbytcích je dáno
med ≡ m (mod pq).

Tudíž
cd ≡ m mod n.

Code:

Příklad

V tomto příkladu jsou pro jednoduchost použita extrémně malá čísla,
v praxi se používají o mnoho řádů větší.
p = 61 (první prvočíslo)
q = 53 (druhé prvočíslo)
n = pq = 3233 (modul, veřejný)
e = 17 (veřejný, šifrovací exponent)
d = 2753 (soukromý, dešifrovací exponent)

Pro zašifrování zprávy 123 probíhá výpočet:
šifruj(123)^17 = 123^17 mod 3233 = 855

Pro dešifrování pak:
dešifruj(855) = 855^2753 mod 3233 = 123

Kde vzali čísla 17 a 2753 ??? V rozkladu na prvočísla žádné číslo 17 není. a už vůbec nechápu co znamenají ty tři čárky u de ≡ 1 (mod φ(n)). Prosím o pomoc.

mikee · 29. 12. 2009 21:12

↑ xy3000:
No cislo 17 nie je v rozklade, ale ono prave v rozklade ani nesmie byt :) My sme hladali nesudelitelne cislo, a to znamena, ze nema s danym cislom ziadneho ineho spolocneho delitela okrem jednotky. Keby bolo v rozklade, tak by prave bolo delitelom druheho cisla a to nechceme.
Co sa tyka tych 'troch ciarok', je to tzv. 'kongruencia modulo', definicia hovori, ze $a \equiv b \ (mod \ m)$ prave vtedy, ked plati, ze $m \ | \ (a - b)$ .
Napriklad $4 \equiv 19 \ (mod \ 5)$ , pretoze plati, ze $5 | (4 - 19)$ :)

xy3000 · 30. 12. 2009 10:18

Dobře, když teda platí :

Code:

de ≡ 1 (mod φ(n))

e=17

d17 ≡ 1 (mod 3120)

Co mě teda vyjde ? Jak z toho dostanu těch 2753, jak je v příkladu ?

mikee · 30. 12. 2009 12:42

↑ xy3000:
No je dolezite si uvedomit, ze takato modulo rovnica ma nekonecne vela rieseni.
Ak ma platit d.17 ≡ 1 (mod 3120), tak podla deficie musi platit 3120 | (17d - 1), inak povedane: zvysok po deleni cisla 17d cislom 3120 musi byt 1. Pre cislo 2753 to plati, ale plati to aj pre nekonecne vela dalsich prirodzenych cisel :)

Matematické Fórum

#1 29. 12. 2009 18:37 — Editoval xy3000 (29. 12. 2009 18:37)

Prvočísla

Code:

#2 29. 12. 2009 18:46

Re: Prvočísla

#3 29. 12. 2009 18:50

Re: Prvočísla

#4 29. 12. 2009 19:21 — Editoval xy3000 (29. 12. 2009 19:23)

Re: Prvočísla

mikee napsal(a):

#5 29. 12. 2009 19:38

Re: Prvočísla

#6 29. 12. 2009 19:42 — Editoval FailED (29. 12. 2009 19:46)

Re: Prvočísla

#7 29. 12. 2009 20:59 — Editoval xy3000 (29. 12. 2009 21:01)

Re: Prvočísla

Code:

Code:

Code:

Code:

#8 29. 12. 2009 21:12

Re: Prvočísla

#9 30. 12. 2009 10:18

Re: Prvočísla

Code:

#10 30. 12. 2009 12:42

Re: Prvočísla

Zápatí