Kétértelmű kódolt üzenet előállítása

Algoritmusok

Sziasztok!

Nemrég jutott eszembe az alábbi kódolási feladat, és szerintem érdekes, cserébe hátha másnak is.

Adott két kódolandó üzenet, körülbelül azonos hosszúságúak. Feladat: állítsunk elő egy kódolt üzenetet és két jelszót. A két jelszóval ugyanabból a kódolt üzenetből dekódolhatjuk az eredetieket.

Egyik triviális megoldás a Vigenère-rejtjel, ahol a kódolt üzenettel megegyező hosszúságú jelszóval minden annál rövidebb üzenet előállítható – ezért a feladatnak legyen mondjuk kritériuma, hogy a jelszavak lényegesen rövidebbek a kódolt szövegnél.

Másik triviális megoldás, ha a két kódolt üzenetet egymás után fűzzük – az algoritmus visszaadja azt a részét az üzenetnek, amelyet képes dekódolni a megadott jelszóval. Ezt is kerüljük.

Van olyan rejtjelezési megoldás, amivel a fenti feladat megoldható?

  • 10529 megtekintés

( Aadaam v | 2013. 05. 23., cs – 20:51 )

bitenként egymás mellé rakod elkódolva, mögéraksz valami paritásbitet vagy CRC-t?

ha nem tudja megoldani páratlan bitekkel az adott jelszóra, megpróbálja a párosakra. Ha egyiken se stimmel feloldáskor a CRC, nem nyert. Azt a bitsorozatot adja vissza, amelyiknek stimmelt a CRC-je a másikat eldobja.

Az elv ugyan ez, a megvalósítás kicsit más a truecryptben: van két N hosszú üzeneted. Előállítasz egy kb. 2N hosszú random adatot. Ebbe az elejéről a vége felé haladva felírod az első üzenetet, a végéről az eleje felé pedig a másodikat. A program a megadott jelszót minden esetben megpróbálja előröl és hátulról is.

( uid_18247 | 2013. 05. 23., cs – 22:06 )

szükséges, hogy a kódolás kriptográfiai erősségű random stringet állítson elő?

( denke v | 2013. 05. 24., p – 16:22 )

Esetleg megprobalhatnad olyasmi modszerrel mint a cdma elv erosen modositott valtozata (kod osztas multilpex, ez az alapja a 3G rendszerek mukodesenek).

Az otlet az hogy a titkos kulcs, leir egy mintazatot hogy a nyilvanos uzenet mely reszei tartalmazzak a neked szukseges reszleteket. Ha a jo reszeket egymas melle rakod vagy xor-ozod izlestol fuggoen (igen, a cdma-ban szuperpolalni kell a megfelelo frekvenciaszeleteket) akkor megkapod az eredeti uzenetet.

Ezt a dolgot meg lehet bonyolitani mondjuk meg egy scramble mintazattal is ha szukseges, bar ha eleg kis szeletekre vagod es eleg bonyolult a kodolo mintazatod, akkor nem latom kulonosebb ertelmet.

A metematikai alapokat megtalalod hozza itt:
http://hu.wikipedia.org/wiki/K%C3%B3doszt%C3%A1sos_t%C3%B6bbsz%C3%B6r%C…

--------------------------------------------------------------------------------------
Viacom Informatikai Kft. Egyedi fejlesztesu, felho alapu webhosting szolgaltatasok. Hureg, Lir, AS.

Érdekes, köszönöm – rémlik, hogy ezt a Mindentudás Egyetemén is előadta valaki, de sajnos azóta sem találom.

A dolog szépséghibája, hogy kis mennyiségű dekódolandó üzenet esetén nem túlzottan hatékony, de ha így átfutva jól értelmezem, a hatásfoka javul, ahogy újabb résztvevők kapcsolódnak be.

int getRandomNumber() { return 4; }  // ← aláírás
//szabályos kockadobással választva. garantáltan véletlenszerű.  xkcd

Ha kis mennyisegu adatod van akkor azt igyis ugyis gyorsan fel tudod dolgozni hatasfoktol fuggetlenul :)

Amugy az eredeti otlet valahogy ugy nez ki hogy minden kliens kap egy kodot, ez megmondja hogy egy nagyon savszelessegu tartomanyon belul, melyik szeletet, es milyen elojellel kell osszeadnod hogy megkapd a neked szolo jelet. igy a valodi jelet el lehet rejteni a zaj ala, kulso szemlelodo meg azt se tudja megmondani hogy ott jelatvitel folyik.

Ezt lekepezve a Te problemadra: egy hosszu, binary, latszolag teljesen random adathalmazbol a megfelelo szegmenseket (szukseg szerint azok inverzet) xor-olod es igy megkapod a kododhoz tartozo dekodolt szoveget. Teny hogy ezt a rendszert az elejetol a varhato uzenet meretek alapjan kell tervezned, ezek alapjan kell kivalasztanod mind a bekodolt allomany (vegulis lehet akar jelfolyan is ha periodikus...) valamint a xor-olando szegmensek meretet. Ha eredetileg sok adatra szamoltal, de vegul keves adatot kozolsz, akkor eleg nagy overheaddel jar a dolog, igen, ellenben a parameterek jatekaval tetszoleges szamu, eltero uzenetet kuldhetsz ki egyetlen kodolt allomanyban / jelfolyamban.

Remelem segitett a dolog, a pontos megvalositasra es a matemetikai fogasokra mar nem emlekszem, regen volt mar az a kozepiskola :), de minden bizonnyal megtalalsz minden ilyet itt a neten.

--------------------------------------------------------------------------------------
Viacom Informatikai Kft. Egyedi fejlesztesu, felho alapu webhosting szolgaltatasok. Hureg, Lir, AS.