Odporuje to autorskému právu? 2.

2.11.2010 08:11 | Přečteno: 1294×

V předcházejícím zápisku jsem uvedl mimo jiné právní otázku související se skutečností, že ze dvou naprosto náhodných čísel lze rekonstruovat autorsky chráněné dílo. Uživatel CiV mě upozornil na Owner Free Filesystem, který využívá operaci XOR. Problém konstrukce obdobných souborových systémů mě z matematického hlediska zaujal a navrhl jsem algoritmus pro následující zobecnění.

Nechť mám n stejně velkých souborů. Vygeneruji m stejně velkých souborů, takže výsledných n+m stejně velkých souborů kóduje zprávu přibližně o délce m souborů. Žádná n-tice souborů nijak se zakódovanou zprávou nesouvisí. Konstrukce algoritmus funguje pro libolnou dvojici n,m, kdy m je nenulové.

Konkrétní příklad : Potřebuji zakódovat jedno CD, což je 700MB. Mějme tři libovolné předem dané stomegové soubory, kterými mohou být třeba zašifrované zálohy třetích osob. Nyní k nim vygeneruji sedm dalších stomegových souborů. Z výsledných deseti souborů žádná libovolná trojice nijak nesouvisí s CD; souvislost s CD vznikne až u (libovolné) čtveřice. Z těchto deseti souborů o celkové velikosti 1GB, lze zpětně rekonstruovat CD. (Poznámka : Ve skutečnosti zakódovaná zpráva bude o něco menší než m souborů. Účinnost algoritmu se může u velkých souborů volbou velkých parametrů v algoritmu libovolně přibližovat ke 100%. V praxi by šlo bez problémů přesáhnout např. účinnosti 99%, což překračuje efektivitu vlastní síťových protokolů.)

Myšlenka algoritmu je velmi jednoduchá. Čísla lze reprezentovat s pomocí zbytků po dělení, tak jak o tom hovoří Čínská zbytková věta. Pro prvočísla p1,p2,p3... má každé číslo menší než jejich součin P=p1*p2*... svou unikátní kombinaci zbytků po dělení těmito prvočísly. S pomocí zbytkových tříd však nebudu kódovat čísla menší než P, ale budu kódovat jen informaci o zbytku po dělení těchto čísel dalším prvočíslem x, které je řádově menší než P. Při tomto kódování zbytků po dělení x se stane použití libovolné neprázdné podmnožina p1,p2,p3..., kdy součin prvků podmnožiny je menší než podíl P/x, redundantní.

Jinými slovy mám informaci o zbytcích po dělení několika prvočísly a najdu nejmenší číslo y, které má právě tyto zbytky. Uvedené zbytky po dělení kódují zbytek po dělení y prvočíslem x. Tento zbytek představuje část zakódované zprávy. Jednotlivé soubory kódují posloupnost zbytků po dělení jedním prvočíslem.

Formálnější vyjádření myšlenky s náznakem důkazu její korektnosti jsem rychle napsal v LaTeXu. Výsledné pdf nabízím ke stažení na svých stránkách zde.

       

Komentáře

[JS]

To jste objevil neco, co uz existuje.

[František Bártík]

To jsem neznal. Máte pravdu je to v podstatě to samé. Použití struktury zbytkových tříd je IMHO jedna z prvních věcí, která člověka napadne.

Možné by byly i další poměrně zřejmé přístupy. (Například považovat zprávu za označení bodu v n-dimenzionálním prostoru a navrhnout množinu m+n vektorů, kdy libovolná n-tice těchto vektorů je lineárně nezávislá. Zprávu pak kódovat jako lineární kombinaci těchto n+m vektorů.)

[Filip Jirsák]

Přístupů je možné navymýšlet si spoustu, podstatné je ale to, zda to současná technika dokáže spočítat v rozumném čase, a pak umět dokázat, že použitý matematický postup i konkrétní algoritmus je skutečně bezpečný. Naivních šifrovacích algoritmů, které lze snadno rozluštit, existují spousty.

[František Bártík]

>>Naivních šifrovacích algoritmů, které lze snadno rozluštit, existují spousty.

Příspěvek se netýká šifrování! Stačí dokázat korektnost postupu vzhledem k zadání, což bude obvykle triviální.

[Filip Jirsák]

Čeho se tedy příspěvek týká? Co je zadáním? Redundantní uložení dat? Pak je ale zase vhodné dokázat, že způsob uložení je efektivní (tedy že neexistuje jiný způsob uložení se stejnou redundancí, který zabírá méně místa). Pokud je zadáním „provést nějaké náhodné operace s daty“, pak bude korektní skoro jakýkoli postup…

[František Bártík]

Příspěvek se týká kódování; detaily jsou myslím zřejmé po přečtení. Přečtěte si příspěvek znovu.

>>vhodné dokázat, že způsob uložení je efektivní

Je to zbytečné. Podle zadání pro každé parametry (n souborů s délkou d) volbou m souborů s délkou d dokážu zakódovat každou zprávu o délce m*d. Informace o délce m*d samozřejmě nelze zakódovat volbou souborů s celkovou délkou menší než m*d.

[Filip Jirsák]

Co si představujete pod pojmem „kódování“? Pokud způsob uložení nějakých dat, pak se u toho obyčejně sleduje, zda je to uložení efektivní. Samozřejmě můžete použít kódování, které slovo „hrad“ zakóduje do 100 MB, ale uložit to v UTF-8 jako 4 bajty je efektivnější.

[František Bártík]

Nebudu tu vysvětlovat základní pojmy a poznatky informatiky. Čím se v článku zabývám je naprosto jasné protože:

1. zadání je v článku popsané,
2. zadání je naprosto evidentní z popsaného řešení,
3. hned v první komentáři je odkaz na Wikipedii, kde je opět popsána podstata problému a její řešení.

[Filip Jirsák]

Zadání v článku je toto:

Potřebuji zakódovat jedno CD, což je 700MB.

Na vstupu předpokládám obraz CD jako soubor na disku nebo jako čitelné CD v mechanice, které lze na obraz na disku jednoduše převést. Takže máte CD zakódované jako 700 MB, zadání je splněno. Vy ale dál kolem toho CD děláte nějaké rituální tanečky, které jsou vzhledem k tomu zadání zbytečné, jenom to celé prodlužují a nafukují.

Vysvětlovat tu základní pojmy a poznatky z informatiky nemusíte, úplně bude stačit, když si je zkusíte vysvětlit sám pro sebe. Zatím to totiž vypadá, že nevíte, co je to kódování nebo co je zadání.

[František Bártík]

Prosím, již tento příspěvek nekomentujte. Evidentně Vám sdělení příspěvku uniká.

[kotyz]

neni sam. u me to taky zustava nepochopeno.

[František Bártík]

Potom ta žádost o nekomentování platí samozřejmě i pro Vás :)

Příspěvek by měli komentovat jen lidé, kteří jej pochopí a mají co říct (viz například velmi kvalitní první komentář od JS).

[Filip Jirsák]

My jsme ten příspěvek ovšem pochopili, to vy jste jej nepochopil (i to se autorům stává). JS vám jen napsal, že ten váš postup má nějaké jméno – asi by bylo zbytečné psát vám to několikrát. JS se ale nezabýval tím, že vůbec není jasné, čeho chcete dosáhnout (a není ani jasné, zda to víte vy sám). Neboli chybí otázka „Potřebuji získat … , jak to mám udělat?“, na kterou by se dalo odpověď „použijte postup Františka Bártíka“.

[kralyk z abclinuxu]

My jsme ten příspěvek ovšem pochopili, to vy jste jej nepochopil (i to se autorům stává).

LOL!
Pane Jirsák, účelem příspěvku evidentně není kódovat data co nejefektivněji. Kdyby to tak bylo, byl by použit jiný algoritmus. Čili prosím nevyčítejte příspěvku, že nedosáhl cíle, který si ani nevytyčil...

[Filip Jirsák]

Už jsme se dozvěděli, co všechno autor s tím CD nechce dělat. Zvláštní je, že ještě nikdo nenapsal, co s ním udělat chce.

[kralyk z abclinuxu]

Proč by to taky psal. Možná to nenapsal schválně. Vždyť je to zřejmé...

[Filip Jirsák]

Sice je to zřejmé, ale zase je to takový nesmysl, že se tomu nechce věřit. Pořád čekám, že v tom někdo taky objeví něco nezřejmého a smysluplnějšího, než nafukování objemu uložených dat bez jakékoli přidané hodnoty.

[kralyk z abclinuxu]

To není jen tak nějaké prosté nafukování objemu, to je nafukování objemu, které má určité speciální vlastnosti. Efektivita ukládání není jediné kritérium kódovacího algoritmu. Je jich víc a redundance je jedním z nich...

[Filip Jirsák]

I v takovém případě lze porovnávat efektivitu. Jednoduše porovnáváte různé způsoby kódování se stejnou redundancí dat. Na to jsem se ptal zde, ale z odpovědí Františka Bártíka se nezdá, že by efektivní uložení dat s redundancí bylo jeho cílem. Takže jste asi další, kdo smysl celé té operace nepochopil.

[kolemjdoucí]

Vždyť v poznámce kurzivou v textu máte jasně napsáno, že redundace se dá libovolně snižovat volbou velkých parametrů algoritmu. Na vstupu jsou jako parametr nějaké soubory, algoritmus zpracuje zprávu a jako výstup je soubor téměř stejně dlouhý jako zpráva. Vaše komentáře jsou mimo mísu.

[Filip Jirsák]

Podstatné je ale to, jak je při nějaké redundanci to kódování efektivní. Snad se shodneme na tom, že když uložím 700 MB do dvou souborů, v obou případech je redundance taková, že při ztrátě 10 % dat dokážu původní soubor obnovit, a v jednom případě bude mít ten soubor 1 GB a ve druhém 20 GB, je ten první způsob uložení efektivnější.

[kralyk z abclinuxu]

Podstatné je ale to, jak je při nějaké redundanci to kódování efektivní.

Pro koho to je podstatné? Pro tebe? Tak napiš zápisek, ve kterém budeš efektivitu různých těhle algoritmů řešit. Tady to je off-topic.

[Filip Jirsák]

Podstatné pro každého. Vymýšlet další neefektivní způsoby kódování je k ničemu. Nebo nás teď bude autor obšťastňovat každý den zápiskem, že si můžete 700MB CD uložit do 1GB souboru tak, že na konec přidáte 300 MB náhodných dat, další den že je přidáte na začátek, pak doprostřed…

[kralyk z abclinuxu]

Aby byl klid: Ano, tento způsob je k ničemu, už jsi nám to řekl, berem to, a teď můžeš jít někam jinam...

[JS]

Ja souhlasim s Frantiskem Bartikem, ze je jasne, co se chce (tedy alespon z hlediska computer science, z hlediska prava uz je to diskutabilni). Viz prave clanek na Wikipedii (secret sharing).

[Filip Jirsák]

Nemohl by to tedy konečně někdo napsat? Nechce se efektivní kódování (ani na výsledný prostor, ani na čas kódování, ani na prostor potřebný ke kódování), nechce se ani data skrýt (šifrování). Pořád mi to tedy připadá, že účelem je jen samoúčelné nafouknutí dat, což se dá mnohem snáz dosáhnout i s použitím cat a /dev/random.

[kotyz]

ja jenom rikam ze by me to zajimalo, ale vubec tomu nerozumim. neslo by to vysvetlit vic pro idioty?

[michich]

K té otázce autorského práva by tě mohlo zajímat toto: What Colour are your bits?

[kralyk z abclinuxu]

Díky za link, geniální, výstižné.

[pedro]

Divate se na to "autorske" pravo prilis technicky. Podstatou problemu, na ktery rada lidi nevedomky narazi, je, ze autorske pravo ani tak nechrani prava autoru, jako hlavne chrani prava korporaci, ktere s takovymi tzv. autorskymi dily nasledne obchoduji. Proste nazev zakona je v rozporu s jeho obsahem. Je to asi tak podobne, jako kdyby zakon o rodine chranil prava syrotcincu, jesli a domacich pecovatelu.

Vemte si nam blizke tema SW. Pro zjednoduseni vezmeme firmu A, zamestnance B a program C. Takze firma A zamestnava B, ktery vytvori C. Firma A si tedy kupuje praci B (podle zakoniku prace), cimz ziskava C, coz jiz ale vzapeti neni prace, ale "autorske dilo". Docela zvlastni premena pravni podstaty. Dokud s dilem nakladal B (nepochybne autor), tak to byla prace, jakmile s tim zacne nakladat C, tak uz je to autorske dilo, ktere poziva mnohem prisnejsi pravni ochrany a ma uplne jiny pravni status. Dost divne, nemyslite?

Ja jenom cekam na to, az zacnou podobnou formu ochrany vyzadovat kadernictvi, pekarny a dalsi "obycejna" odvetvi. On by se jim totiz i jejich byznis delal o hodne snaz, kdyby za nim stala (nami placena) statni masinerie vymahajici "autorske pravo".

[JS]

Navic je otazka, zda tomu rikat "pravo", kdyz ho lze prevadet mezi lidmi a obchodovat s nim. Skutecnych prav (treba pravo shromazdovaci nebo na svobodu slova) se nelze vzdat.

[Dusan]

Pekne si to vystihol.

[kotyz]

a k cemu se to da prakticky pouzit? jaky to ma vyhody proti tomu co se bezne pouziva v soucasnosti?

[Grunt]

Odporuje to autorskému právu?

IMHO? Ne. Protože jsem nepochopil jak to s autorským právem vůbec souvisí.

[Filip Jirsák]

Ten titulek tam autorovi zřejmě zůstal z minula, o autorském právu není v zápisku ani ň.

[Semo]

Pred cca 10 rokmi bol spraveny na MFF UK studentsky hromadny projekt p2p redundantneho sifrovaneho zalohovania na internete. Kazdy ma na disku vyhradeny priestor, ktory poskytuje "komunite". Svoju zalohu strcite programu, ktory k nej spocita dalsie data navyse na cca 1.25 povodnej velkosti, rozdeli na 10 casti, ktore zasifruje a rozposle do sveta = na 10 dalsich "komunitnych" pocitacov, ktore si ju ulozia. Pri ziskani lubovolnych 8 z tychto 10 casti a znalosti kluca sa daju zrekonstruovat povodne data. K tomu si pridaj vyhladavanie v komunite podla hashu, nejaku uctovaciu politiku, ze mozes "do sveta" ulozit iba 80% velkosti tebou poskytnuteho priestoru a mas slusne geograficky nezavisle zalohovanie. Vdaka sifrovaniu nikto netusi, co vlastne drzi na disku a ani po analyze gumovou hadicou to nebude vediet.

[Michal Fecko]

Toto ma zaujalo... nejake SVNko, CVS, release alebo aspoń link by nebol?

[Semo]

Nasiel som stranku povodnych autorov http://www.occamslab.com/petricek/papers/eternity/

Cele to bolo postavena na onion-routed sieti. Zle som si pamatal ze ulozit mozes len tolko co zdielas, mali vymysleny uctovaci protokol pre platby, takze beries prachy za to, ze poskytujes disk (a vdaka sikovnej kryptografii si nemozes vymyslat, ze je u teba ulozene vela apritom skoro nic) a par dalsich zaujimavych veci. Krasny napad (aj ked ideu a algoritmy mali od veduceho projektu (Tonda Benes, kapacita v ceskej kryptografii), ale nenormalne obrovsky na studentsky projekt, kde hlavnym vielom ma byt obhajenie a nie "giant leap for mankind". Takze implementacia tusim nebola nic extra. Ja som asi o 2-3 roky pozdejsie bol clenom teamu, ktory robil znova a poriadne reimplementaciu nepredvidatelneho a maskovaneho OS prenositelneho onion-routingu (takze iba spodnej vrstvy pre buduce sluzby). Ci sa pozdejsie vypisali a reimplementovali aj dalsie projekty, ktore mali reimplementovat povodny projekt vo vyssej kvalite, to uz neviem.

[Semo]

Tu je este nieco ku Eternity service. Zda sa, ze nie vsetko co som napisal do vyssich prispevkov je uplne presne, ale su to uz roky. http://www.freehaven.net/anonbib/cache/strong-eternity.pdf

[xm]

Nedělá něco podobného náhodou starý dobrý Freenet?

[Semo]

Podla strucne preleteneho "About" nie. Eternity service je primarne ulozisko sukromnych veci a nie zdielanie.

Ta reimplementacia spodnej prenosovej vrstvy, co sme pisali mala celkom pekne vlastnosti. Server o sebe (nejak) zverejni pristupove info (ekv. URL). Az na to, ze zverejni vnutornu polovicu cibule (!povedomie o onion-routingu nutne!), takze tymto na seba nepraskne fyzicke umiestnenie. Klient, ktory chce komunikovat so serverom, obali tuto serverovsku polocibulu dalsimi vrstvami, takze ani ak je server honeypot a v skutocnosti je vstupny uzol (najvrchejsia vrstva serverovej polocibule) napichnuta, tak sa nezisti fyzicke umiestnenie klienta (pretoze pakety od neho najprv poskakali po svete, nez prisli).

Dalsou vecou bolo, ze v kazdej vrstve nie je zaznamenana IP jedineho stroja (ako nasledujuci hop), ale 3. Ktorykolvek preposielaci uzol uprostred cibuloveho routovania si nahodne zvoli jeden nasledujucich 3 moznych hopov a posle to na neho. Pre kazdy paket si voli nahodne znova. Priklad: nech cibula (serverova polocibula s 2 vrstvami obalena klientom zvolenymi dalsimi 2 vrstvami) ma 4 vrstvy A,B,C,D, tak potom jej vnutro vyzera {(A1,A2,A3), (B1,B2,B3), (C1,C2,C3), (D1,D2,D3)}. Vrstva B (a vdaka hierarchickosti cibule spolu s nou aj C a D) je zasifrovana verejnym klucom uzlu A, takze iba A vie zistit B1,B2,B3. Podobne verej. klucom uzlu B je zasifrovana vrstva C. A pakety mozu chodit cestami A2,B1,C1,D3 alebo A1,B3,C1,D3 alebo 3^4-2 zvysnymi moznymi; kazdy paket vlastnou cestou, poskladaju sa az na serveri. Cim sa znemozni sledovanie "hot-wire" aj pre niekoho, kto moze sledovat podstatnu cast siete.

Najma spolu s fiktivnym trafikom - pokial by bol datovy prietok cez uzol B maly, tak by sa dali vystopovat uzly A1,A2,A3 a C1,C2,C3, sledovanim tych by sa dalo prist ku dalsim informaciam. Takze pri prietoku mensom nez nejakom rozumnom sa posielaju nahodne data na dalsie uzly v sieti. Ak je trafic dostatocne, tak nic nahodne netreba pridavat. V podstate to okupuje vyhradene pasmo stale, ale vdaka tomu je velmi tazko stopovatelny trafic.

Dalsia moznost ako stopovat pakety je podla datoveho obsahu parovat prichadzajuci a odchadzajuci pakt na uzle. Takze data sa musia pri kazdom hope presifrovat. V cibuli je pri kazdej vrstve aj kluc, ktorym uzol data pri prechode cez neho presifruje. To znamena, ze data na zaciatku boli 4 zasifrovane a cestou sa odsifrovavaju. Dalej si to uz nepamatam uplne presne, takze nejaka chybicka sa mozno vloudi. Problem je, ze vnutorna polka (v skutocnosti to nemusi byt polka, je na uvazeni servera aku hrubu cibulu o sebe verejne vystavi) je prippravena serverom vratane presifrovacih klucov. Takze data v sutocnosti su na zaciatku zasifrovane iba polovicny pocet krat a cestou sa odsifrovavaju, v polovicke su vlastne uplne odsifrovane a dalej vlastne "odsfirovavanim" zase utajuju viac a viac. Pri pouziti sifry, kde sa sifruje aj desifruje rovnakym algoritmom a sukromny a verejny kluc su vlastne zamenitelne (RSA by tak malo fungovat, nie?) to funguje.

Server ma povedomie o vsetkych cibuliach, ktore o sebe vystavil a pamata si k nim presifrovacie kluce, ktore su v nich. Ked mu pridu data s pouzitim jednej z nich, tak vie, ktorymi a kolkymi klucmi musi data odsifrovat aby dostal plain data (v skutocnosti mu pridu data az prilis odsifrovane a on ich musi niekolkokrat zasifrovat, ale pri spominanych podmienkach na sifru to nevadi). V strede trasy vlstne jehen hop putuju plain data, co nie je zdrave, ale to sa da lahko vyriesit az beznym sifrovacim sposobom na datach (napr. GPG zasifrovana sprava sa tymto divokym sposobom nestopovatelne posle serveru).

Cele je to trocha narocne na CPU (ked sme to testovali, tak 10MB/s trafic spotreboval tak cca Pentium3 600) a sietove pasmo, ktore je vytazene vzdy, ale hlavnym ucelom nie je tahat HD ripy, ale skor pouzitie pre WikiLeaks alebo ine politicky horuce pripady, kde je nevystopovatelny ako prispevatel, tak umiestnenie servera a ani citatel a to ani vtedy, ked je vlada schopna trasovat podstatnu cast siete. Samozrejme musi byt aspon nejake mnozstvo beziacich uzlov po svete. Na 3 uzloch paradu neurobite.

[xm]

Hezké. A rozhodně zajímavé. Ale pořád moc nevidím výhody oproti zaběhlým sítím jako je Freenet. Nebo pokud chceme onion/garlic routing, tak ještě lépe I2P (či Tor hidden services) a nad ním postavit nějaké takové decentralizované úložiště, to by na tom bylo s nevystopovatelností naprosto stejně (ne-li lépe). Zkrátka nějak nevidím důvod proč znovuvynalézat kolo.

Jediný problém je s (relativní) pomalostí těchto sítí. Ale to je prostě daň za anonymitu. Pokud by se tohle nějak dalo vyřešit, pak bych klidně byl i pro úplně nový projekt

Ale to je stejně irelevantní akademická debata, pokud k Eternity nepublikují zdrojový kód pod svobodnou licencí. Aneb "Show me the code!"

[Zdenek]

Pomalost anonymnich siti se vyresi jednoduse. Az lidi nebudou mit jinou moznost, tyto site zaziji renesanci a tim vzroste velmi vyrazne jejich prenosova kapacita.

[kapo]

Neni neco podobneho nodezilla (http://www.nodezilla.net/) ?

[Semo]

Bavime sa o dvoch veciach. Jedna je ta prenosova vrstva, v ktorej som pisal sietovu cast, ale mam slusny prehlad aj o sifrovacom a skladacom zvysku. Ta sa odolnostou na sledovanie hot-wire a stopovanie paketov nepodoba na nic o com som doteraz pocul. Ale je kvoli tomu procesorovo a sietova narocnejsia ako len nejake efektivne on-demand riesenie. Zaroven server netusi nic o umiestneni klienta a naopak klient netusi, kde je server. Ale to mozno bue splnat aj viac projektov.

A druha vec je ta zalohovacia redundantna sluzba, o ktorej mam len matne predstavy a spomienky, pretoze viem, ze nasou ulohou bolo spravit reimplementaciu podmnoziny predchadzajuceho projektu, ale zato dokladne a bezpecne. Je mozne, ze sa to na kadeco podoba, ale nemozem to potvrdit ani vyvratit, pretoze neviem. Len treba brat do uvahy, ze ta 1. implementacia bezala okolo roku 2000-2001.