Siguran sam da takvih algoritama ima gomila (meni pada na pamet ideja sa običnim ostatkom), ali je tu pitanje koliko su oni kriptografski bezbedni... Ako je algoritam trivijalan za razbijanje onda nema niakvog smisla koristiti ga.

Ne, čak na protiv - nemoguće ga je razbiti, čak ni teoretski, ako se za šifrovanje kao ključ koristi nasumični niz nekih npr. brojeva.
Sve što šifrantima treba je da posjeduju neki takav "svoj" niz, a njega mogu dobiti na milion načina: snimanjem pozadinskog šuma kosmičkog zračenja, šutanjem miša po stolu, miješanjem karata ili izvlačenjem kuglica iz šešira...

Stvar je u tome da i ne postoji neki matematički algoritam u striktnom smislu da se može proračunati - sam taj nasumični niz predstavlja ustvari sam mehanizam šifrovanja.

@Odin D.:

Razni takvi algoritmi izmišljali su se još od 1980. nadalje (ili je knjiga starija i više od toga?). Relativno pristojan uvod u ovu tematiku dat je i na Wikipediji: http://en.wikipedia.org/wiki/Three-pass_protocol.


Svaki algoritam je moguće razbiti. Razlika je samo u potrebnom vremenu (pa za algoritme koji zahtevaju nerealno mnogo vremena smatramo da su pouzdani).

Ovdje se ne radi o "algoritmu" u tom smislu.
Nema se šta razbijati kad se traga u suštini za besmislenim nizom (ako je šifrovanje obavljeno pomoću besmislenog nasumičnog niza brojeva).

Pokušaću na brzinu objasniti na jednostavnom primjeru, pa ako bude nejasno onda ću sutra detaljnije, jer sam se već zaputio u krevet.

Dakle, uzmimo jednostavnosti radi da se poruka sastoji od npr. samo teksta koji se sastoji od slova abecede (ovo se može proširiti na bilo koji skup znakova koji se koristi za zapis poruke...).

Operacija kojom se poruka kodira je jednostavno ciklično pomjeranje, ili ako kažem "offset", možda će biti jasnije.
Zamislimo kao da se npr. poruka nalazi zapisana na nizu mehaničkih prstenova tako što se prsteni na kojima su kružno ugravirana slova rotacijom poslažu tako da daju neku smislenu riječ od 5 slova (jednostavnosti radi) npr. "BOJAN". (Kao npr. oni katanci za biciklo sa brojčanikom na kome se namjesti kombinacija brojeva da bi se otključali).

Ova ilustracija prikazuje dio prstenova sa početnom porukom:


E sad, ja uzmem nekih 5 nasumičnih brojeva npr. 3, 19, 234, 11 i 28977656 i onda svaki taj prsten sa slovima kružno pomjerim za toliko mjesta u nekom smjeru, i dobiću naravno neku drugu sasvim slučajnu riječ. Znači, prvi prsten pomjerim za 3 pozicije, drugi za 19, treci za 234 itd.
Onda tu riječ pošaljem primaocu, a on na isti takav način ispomjera/zarotira prstenove pomoću slučajnog niza brojeva samo njemu znanog i pošalje meni to natrag.
Ja onda na tome izvršim suprotno pomjeranje od onoga što sam uradio na početku i njemu opet pošaljem takvu riječ.
Kada on sada na toj riječi izvrši suprotno pomjeranje prstenova od onoga što je on uradio dobice ustvari orginalnu poruku.
Stvar je u tome da ako ja zarotiram prsten prvo za 5 mjesta pa onda za 7, potpuno je svejedno kad ga vracam u originalnu poziciju da li cu to uraditi tako da ga prvo vratim unatrag za 7, pa onda za 5 pozicija ili prvo za 5 pa onda za 7 jer ce brojčanik na kraju pasti na isto slovo.

Dok su poruke na ovaj način šifrovane apsolutno su besmislene i nemoguće za dešifrovanje zato što i nema nikakvog "izračunljivog" algoritma - prstenovi su ispomjerani sasvim random, a bilo šta smisleno što se iz 5 slova može dobiti jednako je smisleno kao i sve drugo: avion, lopta, kreda, Milan, Bojan, Mesec,....

Jasno je to što si napisao, i tačno je da je to nemoguće razbiti. No, ovde imamo očigledan problem da dužina „ključa“ (to je taj niz brojeva koji koristiš) mora biti jednaka dužini poruke, tj. ključ mora zavisiti od poruke. No, ako imamo da algoritam za šifrovanje prihvata na ulazu samo jednu poruku (onu koju hoćeš da šifruješ) i onda na izlazu dobiješ šifrovanu poruku, jasno je da se ovo tvoje ne uklapa u tu koncepciju.

Pa sad, koliko je to "problem" to vjerovatno zavisi od primjene i upotrebe.
Pretpostavljam da nijednom računaru ili mobilnom telefonu nije nikakav problem da izgeneriše ključ od 2M slučajnih brojeva ako poruka ima 2MB teksta i tome slično. Poznata zavisnost "dužina ključa = dužina poruke" mislim da ama baš ništa ne doprinosi u pogledu potencijalnog odgonetanja ključa.

E sad, ovo je sve prilično trivijalno, tako da ja ne vjerujem da se niko ranije nije toga sjetio, pa me ustvari više zanima da li se nešto slično ovome uopšte primjenjuje ili ne, i ako ne - onda zašto ne?

@Časlav Ilić:
One-Time Pad je jedina enkripcija koja ukoliko se pravilno primenju je ne moguća za razbijanje, ali ovde nije reč o tome.

@Odin D.:
Ovaj tvoj koncept iako je matematički curiosity se može vrlo lako razbiti, te se stoga ni ne koristi. Osnovni problem je što Alice mora da pošalje random generisane brojčanike u celosti Bobu zajedno sa svojim cipertekstom, i to kvari celu priču.

Problem u celom tvom konceptu je ta "Eve" koja jbe sve kriptografe od početka vremena pa naovamo :)

Dakle, kako izgleda situacija:


Alice i Bob žele da komuniciraju koristeći tvoj sistem enkripcije, dok Eve sedi negde u sredini i presreće njihovu kriptovanu komunikaciju.

Alice želi da pošalje šifrovanu poruku koja se sastoji od samo jednog slova "X" Bobu, i ona generiše random listu simbola koji ne smeju da se ponavljaju, pri čemu "X" dobija nultu poziciju na tom njenom brojčaniku, dakle ovako:


I dalje procedura teče ovako:
1. Alice zamišlja broj +5, dodaje ga na brojčanik i šalje cipertext "V" zajedno sa celom listom (brojčanikom). Eve koja prisluškuje u ovom trenutku nema pojma koji broj je odabrala Alice.
2. Bob prima listu i slovo "V", on sada zamišlja broj -8 i dobija ciphertext "I" koji šalje Alice. Eve koja prisluškuje sada zna da je bob odabrao -8.
3. Alice dobija ciphertext "I" i na njega dodaje -5 i dobija "Q" koji šalje Bobu. Eve sada zna da je Alice odabrala +5, i može da dekriptuje poruku pre nego što Bob dobije sledeću.
4. Bob dobija cipertext "Q", dodaje +8 i dobija originalan tekst "X", međutim pošto mu je žena (Eve) već pročitala poruku od švalerke (Alice) pre nego što je on dobio poslednju poruku, već je dobio oklagijom po glavi :)

Taj metod koji si predložio je trivijalno razbiti.

Ako bi osobe koristile ostatak po raznim deliocima, postupci šifrovanja ne bi komutirali, pa protokol jednostavno ne bi funkcionisao.

Ako bi koristili iste module, onda bi računali ostatke pri množenju nekim brojem uzajamno prostim sa deliocem. Međutim, kada se pročita šifrat koji je A poslao ka B, a onda onaj koji je B poslao ka A, najobičnijim proširenim euklidskim algoritmom bi se odredio činilac od B, Kada bi nakon toga A poslao ka B poruku sa skinutim svojim ključem, opet bi se znajući ključ od B lako skinuo i onda bi se poruka znala.

Za ovu svrhu se može koristiti stepenovanje sa zajedničkom osnovom, bilo po nekom modulu, bilo nad grupom eliptičkih krivih. No, i jedno i drugo se razbija kvantnim računarima.

To sam i rekao.. Dao sam primer algoritma koji služi svrsi koju je on naveo, a kog je trivijalno razbiti.

Pa zna tada dok je poruka još uvijek kodirana i sa Bobovim -8, o kome nema pojma.
Za sledeću poruku niko ne tjera Alice da opet koristi +5; zar je problem da komp izlupa neki sledeći skup random brojeva za sifrovanje sledeće poruke?
To je barem - za računar u smislu računanja - daleko jedonostavnija operacija nego proračun nekog zaguljenog kriptografskog algoritma...

Znači, sve se vrti oko toga da je bez ključa nemoguće razbiti ovakvo šifrovanje poruka, a da se sa druge strane ključevi uopšte ne razmjenjuju jer su potpuno privatni.
Sve što treba je dobar generator random brojeva za "vrćenje zupčanika" i da ključevi pošiljaoca i primaoca ostaju kod njih.


Na brzinu sam proletio kroz taj članak i čini mi se da je to to.
Hvala.

Nema veze sta ce da koristi za sledecu poruku kad eavesdroper Eve presrece komunikaciju svake poruke i svaku pojedinacno moze da desifruje na osnovu te razmene sifrovanih infofmacija kljucevima.

Mislim da sam ili ja ili ti nešto propustio.
U kom tom momentu Eve saznaje ključ od Boba?

EDIT:
... da, pogledah jos jednom, pa vidim sad gdje je problem, to mi je promaklo....


_{[Ovu poruku je menjao Odin D. dana 20.01.2013. u 14:12 GMT+1]}

U drugom koraku.

1. Alice salje Bobu ciphertext i random 'brojcanike'
2. Bob vraca Alice ciphertext (Eve sada zna kljuc od Boba)
3. Alice ponovo vraca cipertext Bobu (Eve sada zna i kljuc od Alice i moze da dekriptuje poruku)
4. Bob sada svojim kljucem dekriptuje poruku


Problem ovog koncepta je sto se brojcanici prenose javno i Eve moze da ih presretne. Kada bi brojcanici bili tajna koju znaju samo Alice i Bob onda bi to bila varijanta one-time pad, ali u tom slucaju ovaj na in komunikacije samo slabi OTP jer daje vise materijala za kriptoanalizu.

U, ovo i te kako jeste problem. Veliki je problem softverski generisati niz slučajnih brojeva; tako dobijaš samo niz pseudoslučajnih brojeva. Oni se u nekim aspektima ponašaju kao slučajni brojevi, ali zapravo među njima postoji pravilnost i moguće ju je provaliti.

Da, to je jasno, cisto softverski generator je problematican, ali nasumicno ocitavanje nekog od senzora kod mobilnog telefona, pseudo-slucajno skeniranje piksela neke slike i tome slicno... trebalo bi bez problema izgenerisati zaguljen skup relativno "besmislenih" brojeva.

Bojane, postoje kriptografski sigurni generatori pseudoslučajnih brojeva. No, i oni zahtevaju dobar izvor slučajnosti za osemenjivanje, a povremeno osemenjivanje je vrlo poželjno, što naravno košta vremrna čekanja da se nakupi entropija, tako da na kraju, nasumično generisanih 2 megabajta nije tako naivno.

Ovde random generator nije problem, ovde je problem sam koncept koji pada u vodu ako postoji neko ko prisluškuje, a kriptografija se bazira upravo na zaštiti protiv takvih.

Ventura, kriptografija uopšte ne rešava problem prislučkivanja procesa unutar računara o kome govoriš. Tema se bavi zaštitom kanala veze od prisluškivanja, što nema nikakve veze nisakakvim procesom unutar računara kao što je generisanje slučajnih ili pseudoslučajnih brojeva.

Problem sa generisanjem dugih nizova slučajnih brojeva je što treba čekati da se nakupi entropija.

Nedeljko, ako ne planiraš da pročitaš temu, onda nemoj ni da pišeš poruke bez ikakve poente. U temi od 19 poruka uspeo si dva puta da repliciraš na nešto što niko nije ni spomenuo.

Zamislimo da Alisa treba da pošalje oruku Bobu, a da je na kanalu veze aktivni napadač Melori.

Melori se lažno predstavlja Alisi kao Bob, a Bobu kao Alisa.

Alisa pošalje Meloriju poruku šifrovanu njenim ključem, tj. misleći da je on Bob. Bob će poruku da šifruje svojim ključem i da prosledi Alisi rezultat, tj. . Alisa će da skine svoj ključ i poslaće Meloriju (misleći da je on Bob) rezultat, tj. . Melori skida svoj ključ i dobija poruku jer je . Sada Melori šalje Bobu poruku , tj. šifrat neke poruke svojim ključem predstavljajući se kao Alisa. Bob će šifrovati svojim ključem poruku i poslati Meloriju misleći da je Alisa rezultat, tj. . Melori skida svoj ključ i šalje Bobu rezultat, tj. . Bob skida svoj ključ i dobija poruku i ne primećuje ništa čudno.

Ovo se zove napad čoveka u sredini. Kao što primećujemo, Melori može ako želi čak i da pošelje drugu poruku, a da Bob ništa čudno ne primeti. Jedini način da se odbrani od ovoga je identifikacija sagovornika. Ovde je problem u tome što Alisa ne zna da li razgovara sa Bobom ili sa Melorijem koji se lažno predstavlja kao Bob i što Bob ne zna da li razgovara sa Alisom ili sa Melorijem koji se lažno predstavlja kao Alisa. Taj problem se rešava uvođenjem Treda koji je neko od poverenja (sertifikaciono telo, npr. policija), koji izdaje digitalne isprave Alisi i Bobu potpisane svojim digitalnim potpisom.

Ovo ti je treća poruka koja nema veze nisačim ko je bilo ko napisao na ovoj temi.

Ovde na ovoj temi baš niko nije spominjao Man-In-The-Middle napad nego prosti eavesdropping (Eve) odnosno prevedno na srpski - prisluškivanje.

Izvoli slikovito objašnjenu razliku između ta dva pojma:

Kada sam napisao da je onaj algoritam trivijalno razbiti, napisao si da si upravo to napisao. Ne znam, na šta si mislio, ali to što tvrdiš da si napisao jednostavno tamo ne piše. Piše da je pitanje koliko je takav sistem kriptografski bezbedan. Odatle sam jedino mogao da zaključim da ti nije poznato da li je takav sistem bezbedan.

Posle si na Odinovo pitanje u vezi generisanja nizova koji su stvarno slučajni pisao o prisluškivanju koje nema veze s tim. Doduše, napisao si da je "ovde" problem ovo, a ne ono, pa sad to "ovde" može da znači svašta.

Pišeš vrlo skraćeno i dvosmisleno i onda optužuješ druge da ne čitaju tvoje poruke. Ja barem vodim računa ne samo da napišem ono što se uklapa u ono što mislim, već i da to po mogućsvu bude jedino moguće tumačenje. Mogao bi i ti.

Ventura, hvala na prosvetljenju. Koliko vidim, Melorija nisam nazvao "prisluškivačem", već "aktivnim napadačem". Iskreno, jesi li pročitao neku ozbiljnu knjigu o kriptografiji?

Tačno je da man in middle attack niko nije pominjao na temi, ali upravo u tome i jeste problem sa temom za nekoga ko hoće nešto da nauči. Man in middle attack je fundamentalan i mora znati za njega bilo ko ko hoće da nauči nešto o ovome. Dakle, ima veze sa temom.

Da, nazvao si ga aktivnim napadačem, i to je prvi put na temi da je neko spomenuo MITM, bez ikakve reference na prethodnu diskusiju.


Da, nekih 20-30 komada, plus redovne publikacije IACR-a čij sam bio član do pre par godina jer me je to zanimalo kao hobi.


Vidi, ti ovde pričaš o tome da li je za zaštitu sefa dovoljno da imaš 30 ili 150cm čeličnih vrata, a propuštaš činjenicu da su zidovi tog sefa napravljeni od kartona... Bespredmetno je uopšte diskutovati o MITM impersonizaciji, (pseudo)random problemima itd. kada sam algoritam ima daleko elementarniji propust.

Ako tvrdiš da si pročitao 20-30 knjiga o kriptografiji, onda definitivno nisi iskren, jer se onda ne bi bavio strujom i poljoprivredom (bez imalo omalovažavanja, dobar biznis cenim kao i sve ostalo što je dobro), nego bi objavljivao naučne radove iz kriptografije. Ne može se stići i jedno i drugo. Pre nekog vremena si me pitao elementarne stvari iz matematike, što je OK, ali mani me tih priča o tome da si pročitao sa razumevanjem bar jednu knjigu iz kriptografije pre toga. To je bez vrlo ozbiljnog znanja matematike jednostavno nemoguće. Po ovoj temi o kriptografiji bi se reklo da nisi pročitao nijednu.

Kažeš da sam algoritam ima elementaran propust. Koji algoritam? Onaj što si ti predložio? Pa, ko o njemu diskutuje osim tebe?

Dobri algoritmi postoje. Ja sam predložio dva. Oba su stepenovanja sa fiksnom osnovom, samo je jedan u polju Z_p, a druga u grupi eliptičkih krivih nad konačnim poljem. Taj će zid biti od kartona tek u eri kvantnih računara.

Ajde sad kad si toliko knjiga pročitao, kaži mi koja ključna osobina treba da bude zadovoljena da bi protokol prošao? Ionako imaš žarku želju da me prosvećuješ.

A za MIMA je dovoljna referenca prva poruka sa teme. Koga interesuje to, mora da zna i ovo.

Kao što rekoh, kriptografija me zanima kao hobi, samim tim nisam preterano fokusiran na suvoparne matematičke probleme u kriptografiji već na nege generalne stvari. Knjige koje sam čitao na temu se uglavnom bave nekom laganom opštom tematikom, istorijatom, i vrlo laganom kriptoanalizom i tehnikama. Nisam matematičar pa se samim tim ne mogu baviti kompleksnim matematičkim problemima i izdavati naučne radove.

A što se tiče mog razumevanja tematike, smatram da je i više nego dovoljna za ovaj nivo diskusije. Uostalom, koliko se praktično razumem u tematiku trebalo bi da ti pokaže moj rank na 3564020356.org. 96 pozicija, Riddle/Nivo 23. Ako želiš da uporediš znanje sa mojim, nema problema, dajem ti par meseci fore da dođeš barem do 12-15 nivoa, ne verujem da ćeš dogurati dalje od toga.


Algoritam koji je predložio Odin D. O njemu se sve vreme diskutuje.


Sve je u redu to što si ti predložio, međutim niti je to neka novina, sve su to rešenja koja su dobro poznata decenijama, niti ta rešenja imaju ikakve veze sa temom i sa konkretnim algoritmom koji je Odin D. predložio.

Drugim rečima, nisi fokusiran na "suvoparne kriptografske probleme" i ne možeš se baviti "kriptografskim problemima".

To što si čitao o istorijatu i supstitucionim šiframa danas nije primenljivo.


A koliko je onaj sajt ozbiljan, može se videti po tome što ne može da se otvori nov nalog. I šta kažeš, nisi pročitao ništa o kriptografiji što nije slikovnica, a našao si druge da procenjuješ.

To što je decenijama poznato (a algoritmi sa eliptičkim krivama nisu baš toliko, ali su poznati više od deset godine) ne znači da postavljač teme to zna i zato sam i napisao. On je pitao kako se nešto rešava i ja sam napisao.

Moze se otvoriti nalog bez problema, samo postoji inicijalni filter sa n00b-ove.


Eto, registruj se na onom sajtu, stigni bar do 15-tog nivoa, ne moraš do 23 kao ja, i skidam ti kapu. Možda se usput iznenadiš koliko stvari čovek nauči iz slikovnica.

_{[Ovu poruku je menjao ventura dana 21.01.2013. u 15:05 GMT+1]}

Pa, eto, kad si toliko učen odgovori na najprostije pitanje:

Sajt je naravno toliko ozbiljan da na njemu ne piše ni čime se bavi. Stvarno jaka referenca. Mora da si imao mnogo jaku konkurenciju.

Ju ju ju, Nedeljko, nisi u tematici pa razumem da ne znaš šta je 3564020356.org, ali bolje malo pretraži po netu, nemoj da se blamiraš sa takvim izjavama...

Hint: Imaš temu i ovde na forumu

Tačno, ne znam i ne zanima me i nije me blam što ne znam šta su neki opskurni sajtovi.

Inače, lično poznajem ovog lika

http://www.mi.sanu.ac.rs/cv/cvmihaljevic.htm

Baš me zanima da li on zna za taj sajt. Verovatno ni on nije u tematici i ne bi umeo da se registruje jer je n00b. (Našao sam index2 stranu, ali čemu dalje da kopam?) Mogu da ga emajliram. Pitao sam ga mogu li da ga kontaktiram ako mi zatreba i rekao mi je da nije problem, što ne znači da sad treba da krene lavina meilova na njegovu adresu.

Na toj temi se ne vidi ništa ozbiljno. Sve to je danas potpuno neprimenljivo. No, sad je jasno šta podrazumevaš pod "tematikom" i zašto si se iščuđavao kakva je veza između MIMA i ove teme, ako si uopšte i zao za taj napad

Nema veze, bitno je da sam ja pokretaču teme dao odgovor na njegovo pitanje, a ti slobodno možeš da nastaviš diskusiju sam sa sobom.

Pitanje je samo kakav odgovor si dao. Stoga sam morao da intervenisem.