» »

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

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.

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.
c-c-c-c

Zgodovina sprememb…

  • spremenil: st0n3 ()


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

pra števila.. (strani: 1 2 )

Oddelek: Znanost in tehnologija
784795 (1134) Yacked2
»

Digitalna evolucija (strani: 1 2 3 426 27 28 29 )

Oddelek: Znanost in tehnologija
141655254 (5423) pietro
»

Hekerji (strani: 1 2 3 )

Oddelek: Programiranje
1337552 (1121) darkolord
»

Kako so ugotovili, da je 2<sup>13466917</sup>-1 praštevilo. (strani: 1 2 )

Oddelek: Znanost in tehnologija
525089 (3592) larpo

Več podobnih tem