Duplo sifrovanje - pitanje za kriptografe

Prije par godina listao sam neku knjižicu o kriptografiji, u kojoj sam između ostalog pročitao nešto o šifrovanoj razmjeni podataka (recimo nekog fajla) između dvije osobe, tako da ne postoji neka šifra koja se između njih razmjenjuje, nego svako ima svoju privatnu šifru koju ne mora da razmjenjuje nisakim.
Recimo kada pošiljalac A hoće da pošalje poruku primaocu B, to ide ovako:

1. Pošiljalac A šifruje poruku pomoću nekog svog samo njemu znanog ključa.
2. Primalac B kada primi tu poruku dodatno je šifruje nekim svojim, samo njemu znanim ključem i vrati tu "duplo šifrovanu" poruku nazad ka A.
3. A ukloni iz takve poruke svoje "šifrovanje", te poruku koja je sad šifrovana samo sa B ključem pošalje nazad primaocu B.
4. B pomoću svog privatnog ključa dešifruje orginalnu poruku.

E sad, ono što me kopka je to da - ako se dobro sjećam (moguće je da sam loše zapamtio) - je tamo bilo napisano da navodno još nije pronađen neki pouzdan (ili čak ikakav?!) algoritam koji bi podržavao takvo de/šifrovanje (da se višestruko kriptovana poruka može dešifrovati proizvoljnim redom u nazad, bez obzira kojim se redom kriptovala).
Sasvim sam spontano, ubijajući dosadu 8-časovnog puta autobusom, došao do krajnje jednostavnog rješenja ovog problema, pa se sjetih i te knjige.

Pitanje je sad za ove što su sa time u toku - jeli navedeni problem još uvijek "problem" ili sam ja nešto krivo zapamtio ili je možda čak i knjiga "u krivu"?

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

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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?

http://en.wikipedia.org/wiki/One-time_pad

@Č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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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

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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.