Forum » Šola » Enosmerne funkcije
Enosmerne funkcije
tx-z ::
Informally, a function f is a one-way function if
1. The description of f is publicly known and does not require any secret information for its operation.
2. Given x, it is easy to compute f(x).
3. Given y, in the range of f, it is hard to find an x such that f(x)=y. More precisely, any efficient algorithm solving a P-problem succeeds in inverting f with negligible probability.
The existence of one-way functions is not proven. If true, it would imply P!=NP. Therefore, it would answer the complexity theory NP-problem question of whether all apparently NP-problems are actually P-problems.
Za začetek me zanima če prav razumem: vprašanje "Do one-way functions exist?" sprašuje ali obstaja takšna funkcija, katere inverza (torej v zgornji razlagi št. x) ne bi mogli najti v polinomskem času?
tx-z
- premaknilo iz Znanost in tehnologija: snow ()
darkkk ::
Da.
1. poglej RSA algoritem
2. poglej kompleksni logaritem
3. poglej eliptične funkcije
Vsi trije so zelo znani (in uporabljani) v kriptografiji. Malo browsaj internetse po tem, mogoče poglej, če dobiš A. Jurišić-evo skripto (slide, ali pa kaj tretjega) za kriptografijo kje.
Glede zadnjega komentarja - za kompleksni logaritem sem že precej pozabil, za eliptične funkcije nisem nikoli čisto dobro vedel, sem pa precej podrobno študiral RSA in njegovo vsebino.
RSA temelji na tem, da ne znamo efektivno (tj, v P) izračunati faktorizacije velikega števila (vzameš produkt dveh ogromnih praštevil in ne boš naračunal prafaktorjev v par letih), sam ne tega mešat s problemom praštevilskosti (tj. da je neki praštevilo, se da ugotoviti v P času). Kakorkoli, RSA je tolk varen kolikor je dolgotrajna faktorizacija velikih števil, zaenkrat ni znanega dobrega algoritma.
1. poglej RSA algoritem
2. poglej kompleksni logaritem
3. poglej eliptične funkcije
Vsi trije so zelo znani (in uporabljani) v kriptografiji. Malo browsaj internetse po tem, mogoče poglej, če dobiš A. Jurišić-evo skripto (slide, ali pa kaj tretjega) za kriptografijo kje.
Glede zadnjega komentarja - za kompleksni logaritem sem že precej pozabil, za eliptične funkcije nisem nikoli čisto dobro vedel, sem pa precej podrobno študiral RSA in njegovo vsebino.
RSA temelji na tem, da ne znamo efektivno (tj, v P) izračunati faktorizacije velikega števila (vzameš produkt dveh ogromnih praštevil in ne boš naračunal prafaktorjev v par letih), sam ne tega mešat s problemom praštevilskosti (tj. da je neki praštevilo, se da ugotoviti v P času). Kakorkoli, RSA je tolk varen kolikor je dolgotrajna faktorizacija velikih števil, zaenkrat ni znanega dobrega algoritma.
Zgodovina sprememb…
- spremenil: darkkk ()
st0n3 ::
v resnici so te one-way funkcije kar problematicne.
There is no proof that one-way functions exist, or even real evidence that they can be constructed.
Even so, there are examples that seem one-way: they are easy to compute but we know of no easy way to reverse them.
Ubistvu ce bi formalno obstajale bi s tem resili P!=NP problem.
Imas pa vseeno funkcije ki se "na videz" obnasajo kot one-way.
Npr:
x^2 mod n = pq je preprosto za izracunat
x^(1/2) mod n = pq pa ni preprosto za izracunat
@dark
tudi p in q kot dva velika prastevila morata biti primerno izbrana. Ni dovolj da sta samo uber velika. Ce nista primerno izbrana jih lahko preprosto faktoriramo (eden od nacinov) z naprimer Fermat factorization @ Wikipedia
ECC kriptografija temelji na problemu da: Given two points A and B on an elliptic curve, it is diffcult (complex) to find a number k so that B = kA = A + A + ...+ A.
There is no proof that one-way functions exist, or even real evidence that they can be constructed.
Even so, there are examples that seem one-way: they are easy to compute but we know of no easy way to reverse them.
Ubistvu ce bi formalno obstajale bi s tem resili P!=NP problem.
Imas pa vseeno funkcije ki se "na videz" obnasajo kot one-way.
Npr:
x^2 mod n = pq je preprosto za izracunat
x^(1/2) mod n = pq pa ni preprosto za izracunat
@dark
tudi p in q kot dva velika prastevila morata biti primerno izbrana. Ni dovolj da sta samo uber velika. Ce nista primerno izbrana jih lahko preprosto faktoriramo (eden od nacinov) z naprimer Fermat factorization @ Wikipedia
ECC kriptografija temelji na problemu da: Given two points A and B on an elliptic curve, it is diffcult (complex) to find a number k so that B = kA = A + A + ...+ A.
c-c-c-c
Zgodovina sprememb…
- spremenil: st0n3 ()
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Zaporedna praštevila nimajo rada enakih zadnjih števkOddelek: Novice / Znanost in tehnologija | 7681 (5622) | Jst |
| » | pra števila.. (strani: 1 2 )Oddelek: Znanost in tehnologija | 8786 (5125) | Yacked2 |
| » | php+enkripcija geslaOddelek: Programiranje | 2185 (1690) | Housy |
| » | Januarski poizkus dokaza problema P = NP neuspešenOddelek: Novice / Znanost in tehnologija | 4259 (2795) | Thomas |
| » | Hekerji (strani: 1 2 3 )Oddelek: Programiranje | 13158 (4603) | darkolord |