PCPROG.3

26 Jul 1993 - 22 Apr 1994

Messages - algoritmi

algoritmi.204 debelijencija, -> #177, d.petrovic
!=?> Mogli bi da ovo nastavite kroz mail ili u conf igre. Zar !=?> nemati ni malo milosti i pristojnosti? Milost? Pristojnost? žemu te teške reči? Naime, ovde se raspravlja o tome koji su principi za pravljenje jedne simulacije igranja fudbala. Jednom rečju, pokušavamo da pronađemo _algoritam_ za to. Zar i pisanje igara ne spada pod pisanje programa? I to su takođe algoritmi! Dakle, koliko mi se čini, mi smo pogodili temu, a vi niste ni čitali te poruke... :( Ako nisam u pravu (a jesam :) neka me moderator, ili neki drugi nadležni ispravi.
algoritmi.205 janko, -> #202, kale
>>> CRC32 detektuje SVAKI šum bit, ako je razmak između >>> prvog i poslednjeg šum bita u poruci koju štiti manji od >>> trideset dva bita. Preko toga, nije dizajniran da >>> obavezno detektuje, ali, nekad mu uspe. > > Da mi je tu sveska iz predmeta "Osnove Računarskih > Telekomunikacija", sad bih se ja "setio" garancija koje > daje tridesetdvobitni CRC koji je tada koristio USA DOD > (Department Of Defence). I ja sam pisao po sećanju. I nastavljam, tako mi je lakše, a dovoljno je... > Ovako, po sećanju, mislim da > detektuje sve greške gde je promenjeno do 5 bita i sve > greške gde je promenjen neparan broj bita. Evo, preciznije: ovaj CRC32, koji se naširoko koristi, (mislim da je neki standard, mrzi me da jurim) detektuje sve greške u kojima je prvi bit greške razmaknut od poslednjeg za manje ili jednako 32 bita, što je i logično. Ona priča, da detektuje sve neparne, izgleda da ne stoji, jer polinom na kome se zasniva, za razliku od onih, koje smo radili na predavanjima, nema (x-1) faktor u sebi! Nisam našao knjigu u kojoj su objasnili zašto su standardizovali polinom koji se ne slaže sa tom elementarnom teorijom.
algoritmi.206 dragisha, -> #182, janko
-> U svakom slučaju, četiri milijarde je opet dosta manje od npr. -> 1e64, (sve 10-slovne lozinke, npr.) Eto, i Juniks je koristio -> duplo više bajtova, pa su ga "razvaljivali." Da li su algoritmi u -> Juniksu stvarno toliko loši, da se samo zato lako provaljuju? Nikako da shvatim na šta aplaudiraš kad kažeš 'razvaljivali'?:) Unix algoritam se NE ODMOTAVA, samo postoje dovoljno kvalitetni programi koji metodom uzaludnih pokušaja pogađaju lozinku, tj trude se a ako ti je lozinka dovoljno prosta (čitaj glupa:) onda i uspiju.
algoritmi.207 zormi, -> #206, dragisha
* Unix algoritam se NE ODMOTAVA, samo postoje dovoljno kvalitetni programi * koji metodom uzaludnih pokušaja pogađaju lozinku, tj trude se a ako ti je * lozinka dovoljno prosta (čitaj glupa:) onda i uspiju. BTW, imam programčić koji Novell serveru pošalje username, a onda nekim sistemskim pozivima pokušava da pogodi password za njega. Tim metodom uspeva da isproba reda 10-tak lozinki/sekundi! Počne sa jednoslovnim (A, B, C,...) pa dvoslovnim itd. Gruba procena kaže da može u konačnom vremenu da napipa sve razumne lozinke koje se sastoje samo od 5-6 slova. Zato je moj password duži od 10 slova, ima i "neslova" i počinje sa Z ;)
algoritmi.208 janko, -> #206, dragisha
> Nikako da shvatim na šta aplaudiraš kad kažeš > 'razvaljivali'?:) Da nisu neki razvaljivali, ne bi sad projektanti sakrivali mesto gde je pravi uzorak? To što se šeta okolo džabe, o čemu si pisao, sigurno nije nešto što predstavlja vrh "razbijačke" nauke. Najverovatnije je čist amaterski proizvod, koji je pisao neko ko se time ne bavi profesionalno. Razbijanje je vrlo unosna stvar... ali i skupa -- obično zaposliš nešto bolje od obične Juniks mašine, ili, ne daj bože, pisija. Naravno, ako takvi programi nekome provale šifru, i treba da mu je provale! > Unix algoritam se NE ODMOTAVA, samo postoje dovoljno > kvalitetni programi koji metodom uzaludnih pokušaja > pogađaju lozinku, tj trude se a ako ti je lozinka dovoljno > prosta (čitaj glupa:) onda i uspiju. Dakle, ti programi ne rade u našoj maloj zemlji, jer mi ne koristimo engleski za lozinke (valjda) :) Usput, ako imaš neku PD verziju Juniksa, sa sorsom, baš bi mogao da iščupaš sors tog dela programa, vidiš da se ljudi lome za tim. > -> U svakom slučaju, četiri milijarde je opet dosta manje > od npr. -> 1e64, (sve 10-slovne lozinke, npr.) Eto, i Au greške, ovde sam omašio za neznase nula! :( Sve desetoslovne lozinke su 64 na deseti, tj. jedva nekih 1e18. Eh, to SWAP dugmence (na mnogo je zgodnom mestu :) Što se niko nije bunio?
algoritmi.209 miljko, -> #207, zormi
>­ Počne sa jednoslovnim (A, B, C,...) pa dvoslovnim itd. >­ Gruba procena kaže da može u konačnom vremenu da napipa >­ sve razumne lozinke koje se sastoje samo od 5-6 slova. To mi liči na vremenski nestabilan algoritam za detekciju šifri. Naime u naivnom pristupu detekciji lozinki on poredeći slova svaki put kad naidje na pravo slovo potroši nešto više vremena prelazeći na sledeće, što se može detektovati. Uz malo statistike (više pokušaja pa prosečno vreme i sl.) lozinke se mogu probiti. Ja sam svojevremeno imao programčić na tu temu koji je zaista mogao da detektuje lozinku (u većini slučajeva). Odustao sam kad sam shvatio da se lozinke pamte drugačije. Zanima me kako Novell pamti lozinke, odnosno kako funkcioniše dotični program ?
algoritmi.210 janko, -> #209, miljko
> To mi liči na vremenski nestabilan algoritam za detekciju > šifri. Naime u naivnom pristupu detekciji lozinki on > poredeći slova svaki put kad naidje na pravo slovo potroši > nešto više vremena prelazeći na sledeće, što se može > detektovati. Uz malo statistike (više pokušaja pa prosečno > vreme i sl.) lozinke se mogu probiti. > > Ja sam svojevremeno imao programčić na tu temu koji je > zaista mogao da detektuje lozinku (u većini slučajeva). > Odustao sam kad sam shvatio da se lozinke pamte drugačije. > > Zanima me kako Novell pamti lozinke, odnosno kako > funkcioniše dotični program ? Iskreno se nadam, ne tako kako si opisao. :) Svaki normalan algoritam koji konvertuje lozinku u nešto drugo što pamti, ako radi različito vreme za različite lozinke, to nije u funkciji broja pogođenih slova! Ideja je stvarno lepa, moguće je da postoje uslovi gde se i to može primeniti, ali, ne znam, za sada, gde.
algoritmi.211 dr.grba, -> #207, zormi
>> BTW, imam programčić koji Novell serveru pošalje username, a onda >> nekim sistemskim pozivima pokušava da pogodi password za njega. Tim >> metodom uspeva da isproba reda 10-tak lozinki/sekundi! A šta ako je uključen intruder checking? I blokira stanicu posle npr. petog pokušaja?
algoritmi.212 niklaus, -> #195, janko
(:> Brkaš kontekste. Pričali smo o algoritmu za reprezentaciju (:> pristupnih lozinki sistemu, a ne za proveru "napada šuma." Ne brini se - pažljivo sam čitao sve poruke vezane za metode otkrivanja grešaka (uklučujući i tvoje). Vidiš, napisao sam "metode otrivanja grešaka", a te metode se koriste i u transferu podataka, i u što osetljivijoj enkripciji šifara, i ko zna čega još. "Šum" u slučaju specifične, pogrešno unete šifre, je trenutak kada CRC ne "otkriva" grešku... (:>> Zašto se koristi u popularnom protokolu ZModemu (i svim (:>> manje popu- larnim posle njega)? (:> (:> Zato što tu služi svrsi detekcije šum bitova, uz određena (:> ograničenja koja imaju smisla u datim realnim uslovima. Naravno, ristanu se (kako on kaže) desilo jedared. Meni nijednom, tebi (verovatno) nijednom - mirni smo do starosti... (; (:> CRC32 detektuje SVAKI šum bit, ako je razmak između prvog i (:> poslednjeg šum bita u poruci koju štiti manji od trideset dva (:> bita. Preko toga, nije dizajniran da obavezno detektuje, ali, (:> nekad mu uspe. Nije SVAKI. Znaj da svaka egzaktna i konačna formula za detekciju grešaka imaće barem još jedan ulazni niz, čije rešenje je isto, ili drugim rečima - kada nastupa "previd greške". (:niklaus:)
algoritmi.213 kale, -> #212, niklaus
>> Nije SVAKI. Znaj da svaka egzaktna i konačna formula za detekciju >> grešaka imaće barem još jedan ulazni niz, čije rešenje je isto, ili drugim >> rečima - kada nastupa "previd greške". žini mi se da si prevideo ogradu - "ako je razmak između prvog i poslednjeg šum bita u poruci koju štiti manji od trideset dva bita". CRC jeste konačan (32bita), ali u uslov za sigurno detektovanje greške je da je i greška konačna (<= 32 pogrešna bita).
algoritmi.214 paki, -> #212, niklaus
­> Naravno, ristanu se (kako on kaže) desilo jedared. Meni nijednom, tebi ­> (verovatno) nijednom - mirni smo do starosti... (; Meni 3-4 puta, poslednji put baš danas... :(
algoritmi.215 niklaus, -> #214, paki
(:>­> Naravno, ristanu se (kako on kaže) desilo jedared. Meni (:>­> nijednom, tebi (verovatno) nijednom - mirni smo do starosti... (:> (; (:> (:> Meni 3-4 puta, poslednji put baš danas... :( Mora da postoji objašnjenje. Teoretski je nemoguće toliko "omaški" u tako kratkom periodu, pa još na istom mestu. Moguće je da se SEZAM zeznuo prilikom kopiranja u tvoj PAD (ne znam koja je tačno procedura, tako da je ovo laička pretpostavka). Prvim pogledom na "onu" poruku (SEZAM.5, 11.607), mogu samo da kažem da se slični "efekti" javljaju, kad neki LZW (Lempel-Ziv) algoritam za kompresiju omane. Konkretno,u slučajevima da je jedan karakter u kompresovanom fajlu na silu promenjen, tako da dolazi do promene prilikom dekodiranja iz LZWovog "rečnika". (;ko razume - shvatiće) Inače, baš sam tragao za porukom, koju si citirao kao primer lošeg ponašanja ZModema - ne nađoh je. Koja je u pitanju? (da malo bolje proučim) (:niklaus:)
algoritmi.217 niklaus, -> #214, paki
(:>­> Naravno, ristanu se (kako on kaže) desilo jedared. Meni (:>­> nijednom, tebi (verovatno) nijednom - mirni smo do starosti... (:> (; (:> (:> Meni 3-4 puta, poslednji put baš danas... :( Još nešto da kažem... To što se desilo tebi, ristanu i ko zna još kome u tako kratkom periodu je opšte uzev nemoguće. Jedno od mogućih racionalnih obajšnjenja bi moglo da bude prevaljivanje krivice na SEZAM (koriste li neki disk-kompesor?), i to u trenutku kopiranja u tvoj PAD. Ovo je čista laička hipoteza, jer ne znam kako taj proces zaista funkcioniše. Da ti prenesem moj prvi utisak kad sam video tvoju poruku 11.607 u konfu SEZAM.5 - podseća me na dearhivirani "corrupted" fajl, kompresovan LZW (Lempel-Ziv) algoritmom (ili nekom varijacijom). Malko bombasto zvuči, da objasnim. Do sličnih ponavljanja podstringova u odpakovanom tekst fajlu dolazi u slučaju, kada se "na silu" promeni jedan (ili više) bajt u LZW kompresovanom fajlu. Opet koliko znam, svi disk-kompre- sori koriste upravo LZ? algoritme, jer su run-length (nije potrebno najpre pročitati ceo fajl, radi neke statistike o broju ovog ili onog slovca, već je algoritmu za dekompresiju "sve jasno" dok redno čita fajl). Moguće je da SEZAM ne koristi diks-kompresore, u šta lično verujem jer SEZAM drži do svojih korisnika i sebe. U tom slučaju moguće je da se u SEZAMovom softveru koristi kompresija u nekom trenutku transfera po mreži. Možda je mreža zakazala? Ko zna? Dejanr? U svakom slučaju, ZModem NIJE zakazao (sigurno ne svih 4-5 puta). (:niklaus:)
algoritmi.218 dejanr, -> #217, niklaus
>> Moguće je da SEZAM ne koristi diks-kompresore Sezam radi pod Novell-om 3.11. Kao što je poznato, on ne obuhvata kompresiju diska (za razliku od Novell-a 4.0). Dakle, nema kompresije podataka. >> U tom slučaju moguće je da se u SEZAMovom softveru koristi kompresija >> u nekom trenutku transfera po mreži. Ni u jednom trenutku se ništa ne komprimuje dok ide preko mreže. >> U svakom slučaju, ZModem NIJE zakazao (sigurno ne svih 4-5 puta). Možda nije, možda jeste. Ono što smatram empirijski dokazanim jeste da će, ako neko ostavi poruku tipa "desilo se to i to, i imao sam takav i takav neobjašnjiv problem", sigurno u sledećih 48 sati da još nekoliko korisnika prijavi sličan problem, koji im se u ovom ili onom trenutku desio. Stvar je u tome da se pri radu sa računarom svakome povremeno desi nešto nepredviđeno, što je teško objasniti. Da se locira i potvrdi problem potrebno je obično dosta truda, razmišljanja, talenta za dedukciju i, naročito, iskustva. Jednom davno, dok je Sezam bio "mlađi" i imao malo korisnika, desio nam se sličan problem, četiri korisnika je prijavilo da je imalo problem pri raspakivanju pad-a u periodu od možda deset dana. Svi ti slučajevi su detaljno "isleđeni". Jedan korisnik je u stvari imao pokvaren disk, crkao je neki dan kasnije. Drugi je koristio beta verziju PKUNZIP-a. Treći je greškom uradio DEL PAD*.ZIP pa kasnije UNDELETE, naravno, nije se sve dobro oporavilo. žetvrti slučaj je ostao nerazjašnjen. Jednom, mnogo kasnije, više korisnika je imalo takve probleme. Ispostavilo se da su svi skidali PAD-ove sa noda 15... i najzad je ispalo da je nod 15 u kvaru, na neki čudan način. Eno tog računara i dan danas stoji "rashodovan" u nadi da će ga neko popraviti. Sve u svemu, ZMODEM i njegov 32-bitni CRC je nešto čemu možeš verovati ako mesečno download-uješ nekih 100-tinak datoteka - greške će se desiti možda par puta u životu. Ali, ako se sa jednog sistema download-uje preko 30,000 datoteka ili 2 gigabajta (što je otprilike Sezamova standardna statistika), za očekivati je da se desi određeni broj takvih greški. Može neko koga zanima teorija verovatnoće da proračuna koliko je očekivanje.
algoritmi.219 paki, -> #215, niklaus
­> (:> Meni 3-4 puta, poslednji put baš danas... :( ­> ­> Mora da postoji objašnjenje. Teoretski je nemoguće toliko "omaški" u ­> tako kratkom periodu, pa još na istom mestu. Moguće je da se SEZAM ­> zeznuo Period je godinu dana. ­> Prvim pogledom na "onu" poruku (SEZAM.5, 11.607), mogu samo da kažem ­> da se slični "efekti" javljaju, kad neki LZW (Lempel-Ziv) algoritam za ­> kompresiju omane. Konkretno,u slučajevima da je jedan karakter u ­> kompresovanom Da, sigurno je to (jedan blok se preneo kako nije trebalo, i - gle čuda :). ­> Inače, baš sam tragao za porukom, koju si citirao kao primer lošeg ­> ponašanja ZModema - ne nađoh je. Koja je u pitanju? (da malo bolje ­> proučim) Ne znam na šta misliš? 'Ono' su bili citati iz pokojnog TEXTPADA.
algoritmi.220 drpr, -> #215, niklaus
-> Mora da postoji objašnjenje. Teoretski je nemoguće toliko -> "omaški" u tako kratkom periodu, pa još na istom mestu. -> Moguće je da se SEZAM zeznuo Grešiš teoretski je moguće a praktično teško ostvarljivo. Verovatnoća radi sa beskonačnim brojem pokušaja a u praksi se kaže da je "verovatno" da će se neka veličina raspodeliti na taj i taj način. Elem da završim šaljivo ako si gledao film "Rozenkranc i Gildestern su mrtvi" video si kako jedan od junaka baca novčić oko 180 puta i uvek dobija jednu stranu (mislim da je bila galava) a to se po teoriji teško dešava tj. verovatnoća je š .Znači trebalo je da bude pola pola ali nemora da bude tako i teorija sama svojim imenom kaže "verovatnoća". cope
algoritmi.221 drpr, -> #217, niklaus
-> je opšte uzev nemoguće. Jedno od mogućih racionalnih -> obajšnjenja bi moglo da bude prevaljivanje krivice na SEZAM -> (koriste li neki disk-kompesor?), i to u Opet da se nadovežem i meni se prvi put desilo pre jedno mesec dana. Ponovo sam preneo fajl (nije išao u pad) i sve je bilo ok. cope
algoritmi.222 niklaus, -> #220, drpr
(:> Grešiš teoretski je moguće a praktično teško ostvarljivo. U pravu si! Zapravo bio je to laspup, ili lapsup, kako beše. (; (:niklaus:)
algoritmi.223 dr.grba, -> #220, drpr
>> i taj način. Elem da završim šaljivo ako si gledao film >> "Rozenkranc i Gildestern su mrtvi" video si kako jedan od >> junaka baca novčić oko 180 puta i uvek dobija jednu stranu >> (mislim da je bila galava) a to se po teoriji teško dešava tj. >> verovatnoća je š .Znači trebalo je da bude pola pola ali nemora Pre nekoliko godina, bejasmo srednjoškolci, jedna ekipa đaka je bila angažovana da crticama meri opterećenja nekih raskrsnica u gradu, ne bi li se postavili semafori. Trebalo je u tabelu po satima udarati recku za svaki bicikl, motocikl, putničko ili teretno vozilo... Jedan drugar je za dva sata dežurstva napravio (čini mi se) oko 600 crtica na "biciklovi". Svi ostali su u to vreme imali 30-40 crtica... Kasnije je priznao da se njegov stariji brat, sportski biciklista, navadio sa kolegama iz kluba pa su pičili u krug non stop tom raskrsnicom (((: Toliko o zakonima verovatnoće, raspodelama i Gausovim zvonastim krivama...
algoritmi.224 a.kircanski,
I, na kraju, koji je alogirtam za šifrovanje passwd fajla na unix-u?
algoritmi.225 janko,
Znate li onaj algoritam za dajdžest teksta koji smo pominjali, iz microb poruke xx? Sad ga nešto gledah, i ubeđen sam da je POGREŠAN. Obratite pažnju: > If t is the operation number (from 1 to 80), and M subscript j > represents the jth sub-block of the message (from 0 to 15), and > <<<s represents a left shift of s bits, then the 80 operations > look like the following: > > TEMP = (A <<< 5) + f subscript t(B,C,D) + E + W subscript t + K > subscript t > > E = D > > D = C > > C = (B <<< 30) > > B = A > > A = TEMP > > After all this, A, B, C, D, and E are added to AA, BB, CC, DD, > and EE, respectively, and the algorithm continues with the next > block of data. The final output is the concatenation of A, B, C, > D, and E. Očigledno, komplet A B C D E reči od po 4 bajta daje na kraju onih magičnih 160 bita dajdžesta. Ali... Od tih 160 bita ISTIH 90 su UVEK PRAZNI po gornjim formulama(!) Pogledajte liniju C = (B <<< 30). Šift po definiciji briše bite koji se pomere. Ostaju samo dva upotrebljiva bita u C, trideset ostaju nule. Isto i u D i E, u svim sledećim iteracijama. Zaključak: algoritam, ovakav, kakav je, je za izbegavanje, do daljeg. Ima li neko "na papiru" (u knjizi ili relevantnom članku) ili "u kodu" ovaj isti algoritam, da vidimo kako izgleda ispravna realizacija?
algoritmi.226 ndragan, -> #225, janko
/ Ima li neko "na papiru" (u knjizi ili relevantnom članku) ili / "u kodu" ovaj isti algoritam, da vidimo kako izgleda ispravna Na PDP mašinama si imao RADIX40, skraćeni set znakova, koji je sadržavao A-Z, 0-9. $, blenk i valjda tačku, te nul znak, sve skupa 40 znakova. To čudo je trpalo tri znaka u dva bajta. U tom formatu su u direktorijima pamćena imena fajlova itd. žak i nije išlo po bitovima, nego c1*1600+c2*40+c3 ide do najviše 40**3-1, tj 63999 različitih trojki znakova (u stvari nešto manje, pošto je bilo nekoliko nedozvoljenih kombinacija sa nul znakom). Citirani algoritam (nisam imao živaca ni vremena da implementiram) bi mogao da znači neko slično sečenje suvišnih bitova. Sečenje bi moglo da se ostvari i sužavanjem skupa znakova na recimo neke banke po 32 (velika slova i blenk, mala slova i blenk, cifre i interpunkcija u trećoj banci), sa prefiksnim bajtom pred promenu banke, a dok se nižu znaci iz iste banke moglo bi se trpati po pet bitova u niz, do promene banke. Trebalo bi ipak prvo proračunati koliko se ovakva strategija isplati. If yes, (c).
algoritmi.227 dejanr,
Na zahtev više korisnika, algoritam kojim se rešava jednačina trećeg stepena. Pre svega oznake: ^ je stepenovanje sqrt je kvadratni koren j je imaginarna jedinica. j=sqrt(-1) sh je hiperbolički sinus. sh x = (exp(x)-exp(-x))/2 ash je funkcija inverzna sh. ash x = ln(a+sqrt(x*x-1)); ch je hiperbolički kosinus. ch x = (exp(x)+exp(-x))/2 ach je funkcija inverzna ch. ash x = ln(a+sqrt(x*x-1)); cos je funkcija cos acos je funkcija iverzna cos. Ako u datom jeziku od izverznih funkcija postoji samo atan, može se koristiti acos(x)=arctan(sqrt(1-a*a)/a); abs je apsolutna vrednost pi je broj PI, 3.14159... Jednačina je oblika ax^3+bx^2+cx+d. Pretpostavlja se da je a<>0, jer ako je a=0 to i nije jednačina trećeg stepena. Najpre je treba svesti na oblik: y^3+3py+2q=0. To se radi smenom y=x+b/(3a), u kom slučaju se dobija: 3p=(3ac-b^2)/(3a^2) 2q=(2b^3)/(27a^3) - bc/(3a^2) + d/a Odavde može da se izračuna p i q. Treba izračunati r=+-sqrt(abs(p)). Znak plus se uzima ako je q>=0, a u protivnom je r negativan broj. 1. Ako je p>0 Izračuna se f iz f=ash(q/r^3) Jednačina ima jedan realan koren, y1=-2r*sh(f/3) Jednačina ima dva kompleksna korena, y2=r*sh(f/3)+j*sqrt(3)*r*ch(f/3) i: y3=r*sh(f/3)-j*sqrt(3)*r*ch(f/3) 2. Ako je p<0 2.1 Ako je q^2+p^3>0 Izračuna se f iz f=ach(q/r^3) <-- lako se pokazuje da je q/r^3 nikad po modulu nije manje od 1, dakle ach je definisan Jednačina ima jedan realan koren, y1=-2r*ch(f/3) Jednačina ima dva kompleksna korena, y2=r*ch(f/3)+j*sqrt(3)*r*sh(f/3) i: y3=r*ch(f/3)-j*sqrt(3)*r*sh(f/3) 2.2 Ako je q^2+p^3<=0 Izračuna se f iz f=acos(q/r^3) <-- lako se pokazuje da je q/r^3 uvek po modulu manje od 1, dakle acos je definisan Jednačina ima tri realna korena: y1=-2r*cos(f/3) y2= 2r*cos(pi/3 - f/3) y3= 2r*cos(pi/3 + f/3) 3. Ako je p=0 Jednačina je oblika y^3+2q=0 pa je realno rešenje lako naći kao treći koren iz 2q. Međutim, potrebna su sva tri rešenja: Izračuna se r:=abs(2*q)^(1/3) 3.1 Ako je q<0 y1=r y2=r*cos(2*pi/3)+j*r*sin(2*pi/3); y3=r*cos(2*pi/3)-j*r*sin(2*pi/3); 3.2 Ako je q>0 y1=-r y2=r*cos(pi/3)+j*r*sin(pi/3) y3=r*cos(pi/3)-j*r*sin(pi/3) 3.3 Ako je q=0 Trostruko rešenje y1=y2=y3=0 Pošto su određena tri rešenja transformisane jednačine, rešenja osnovne jednačine su: x1=y1-(b/(3a)) x2=y2-(b/(3a)) x3=y3-(b/(3a)) Srećno :)
algoritmi.228 nboskovic, -> #227, dejanr
*> Na zahtev više korisnika, algoritam kojim se rešava *> jednačina trećeg stepena. Na Sezamu u direktorijumu R:\IBMPC\C ima arhiva u kojoj se nalaze sorsovi za rešavanje mnogih matematičkih problema. Među tim sorsovima ima i rešavanje jednačine do 36-og stepena. Mogu vam reći da program, na mašini koja ima koprocesor, nalaženje 36 nula radi gotovo trenutno :) Treba probati. Do ovog programa sam došao zahvaljujući mjovi dok smo bezuspešno pokušavali da rešimo naveden problem :) Ako ne predstavlja kršenje nekih prava i sl. mogu da pošaljem EXE fajl tog programa. (c) klap nikola
algoritmi.229 dejanr, -> #228, nboskovic
>> Među tim sorsovima ima i rešavanje jednačine do 36-og stepena. Program verovatno koristi neki od numeričkih metoda. Jednačina 5-tog, 6-tog i višeg stepena ne može (u opštem slučaju) da se reši na način na koji smo navikli, tj. da se dobije nešto kao: rešenje je a*b-c^2 gde su a, b i c koeficijenti. Govorili smo o egzaktnom rešavanju (realna i kompleksna rešenja) jednačine trećeg stepena. Međutim, onaj kome treba rešenje u obliku broja (a to je najčešće u praksi i potrebno, dobiješ x=23.128575 i "baš te briga" koja je to funkcija od koeficijenata), zaista će dobro proći sa numeričkom varijantom. Hvala što si nam skrenuo pažnju na program.
algoritmi.230 niklaus, -> #229, dejanr
(:> Program verovatno koristi neki od numeričkih metoda. Da nije onaj sistem za postepeno traženje binoma (oblika (x-a)) delilaca polinoma P(x). Naime zna se da za nula polinoma, koje su realne važi: a=p/q ; gde je a0 (slobodni koeficijent) deljivo sa p an (koeficijent uz xžn) deljivo sa q ...pa se proveri za svaku od kombinacija p/q. Ovde je malo veći pro- blem izvršiti podelu P2(x)=P(x)/(x-a), nakon čega ide GOTO 10. (; Da li nalazi i konjugovano-kompleksna rešenja? (:niklaus:)
algoritmi.231 janko, -> #226, ndragan
> / Ima li neko "na papiru" (u knjizi ili relevantnom > članku) ili / "u kodu" ovaj isti algoritam, da vidimo > kako izgleda ispravna > > Na PDP mašinama si imao RADIX40, skraćeni set znakova, > ... > > Citirani algoritam (nisam imao živaca ni vremena da > implementiram) bi mogao da znači neko slično sečenje > suvišnih bitova. Sečenje bi moglo da Asocijacija ti je loša. Citirani algoritam je parče celog, koji je u microb xxx poruci, ima jaku kriptografsku osnovu itd. Inače, taj članak, čiji je elektronski oblik pomenuta poruka, je izašao u novembarskom Bajtu, sa potpuno istim tekstom, za koji verujem da je pogrešan. Ko ima pristup Biksu, mogao bi da pita samog autora, ako je raspoložen, šta stvarno treba da se nalazi u inkriminisanoj liniji? Ili, da nije izašla ispravka u decembarskom Bajtu? Ili će izaći u januarskom, ne znam kakva im je tehnologija?
algoritmi.232 snemcev,
Jel zna neko kako se iz matičnog broja građanina može "izvući" pol? Datum rođenja su prvih sedam cifara, poslednja je kontrolna, a ono između su pol, mesto rođenja i nekakav uslovno rečeno redni broj. Koja cifra je pol?
algoritmi.233 mirkot, -> #232, snemcev
>> Jel zna neko kako se iz matičnog broja građanina može "izvući" >> pol? 10, 11 i 12 cifra su redni broj za taj dan. Od 0 do 499 su muškići, a od 500 do 999 su devojčice. Mirko
algoritmi.234 vitez.koja, -> #233, mirkot
#=> 10, 11 i 12 cifra su redni broj za taj dan. Od 0 do 499 #=> su muškići, a od 500 do 999 su devojčice. Prvo (pa) muško :))
algoritmi.235 snemcev, -> #233, mirkot
>> 10, 11 i 12 cifra su redni broj za taj dan. Od 0 do 499 su muškići, a >> od 500 do 999 su devojčice. Tnx. Ovo mi je jako trebalo, kopao sam po kojekakvoj dokumentaciji, usput pronašao gomilu stvari za koje nisam ni znao da ih imam, ali ovo nisam našao. Tnx again.
algoritmi.236 dr.grba, -> #235, snemcev
>> usput pronašao gomilu stvari za koje nisam ni znao da ih imam, ali 'Ajd' sad, podeli tu gomilu sa nama (((:
algoritmi.237 salex,
Simpleks algoritam ? Zna li neko za knjigu u kojoj je lepo opisan Simpleks algoritam iz Linearnog programiranja ? Salex
algoritmi.238 afilipovic,
>> Simpleks algoritam iz Linearnog programiranja ? Prilicno je fino i sa teoretske i sa prakticne strane dat u: "Linearno programiranje", Zelimir Vuckovic, " Savremena administracija " Pozdrav, Nenad
algoritmi.239 ppekovic, -> #237, salex
>> Zna li neko za knjigu u kojoj je lepo opisan >> Simpleks algoritam iz Linearnog programiranja ? Algoritmi i programi iz operacionih istraživanja by Slobodan Krčevinac, Jovan Petrić, Milutin župić & Ilija Nikolić u izdanju Naučne knjige iz Beograda. Tamo su dati algoritmi i programi na Fortranu. Ako te mrzi da prekucavaš, pitaću autore da li je source PD (pošto je već objavljen u knjizi) pa ću ga eventualno okačiti ovde ako si zainteresovan? Paya
algoritmi.240 kenza, -> #237, salex
(;> Zna li neko za knjigu u kojoj je lepo opisan (;> Simpleks algoritam iz Linearnog programiranja ? Matematicko Programiranje Autori su V.Vujicic,M.Asic i N.Milicic. Poglavlje 4.2 - Simpleks Metoda (69.strana) p.s. Srecno ;) Trebace ti :)
algoritmi.241 isekulovic,
Ovde je skoro bila rasprava o algoritmu za sifrovanje passworda na bbs-ovima i koliko se sećam nije nadjen zadovoljavajući algoritam. Da li je ovaj možda odgovarajući. Inače ovaj source se nalazi u arhivi DDJ9311.zip, mislim da ima na sezamu, ako nema ima na ffs-u. ivan (* ------------------------------------------------------------------------- *( ** palpak.pas -- Algorithm #13: Palindrome Encryption ** ** --------------------------------------------------------------------------** ** Demonstrates data encryption technique for producing keys or signatures, ** ** Microsoft Calendar files, for example, begin with signature bytes formed ** ** by applying the algorithm to the word Calendar. There is no known ** ** recovery method for restoring text encrypted using this method. ** ** Copyright (c) 1993 by Tom Swan. All rights reserved. ** )* ------------------------------------------------------------------------- *) program PalPak; var S1, S2: String; function Uch(C: Char): Integer; begin if (C in ['a' .. 'z']) then Uch := Ord(C) - 32 else Uch := Ord(C) end; function Lch(C: Char): Integer; begin if (C in ['A' .. 'Z']) then Lch := Ord(C) + 32 else Lch := Ord(C) end; procedure Encrypt(S: String); var I, E, C: Integer; begin I := 1; E := Length(S); while (I <= Length(S)) do begin C := Uch(S[I]) + Lch(S[E]); Write(C, ' '); I := I + 1; E := E - 1 end end; var S: String; begin repeat Write('Enter a string: '); Readln(S); if Length(S) > 0 then begin Write('Encrypted string: '); Encrypt(S); Writeln end until Length(S) = 0; end.
algoritmi.242 janko, -> #241, isekulovic
> Ovde je skoro bila rasprava o algoritmu za sifrovanje > passworda na bbs-ovima i koliko se sećam nije nadjen > zadovoljavajući algoritam. Naprotiv, nađena su dva odlična. Osim toga, pronađeno je da nešto nije u redu u BAJTovom tekstu koji se bavio istom temom. Kad smo već kod toga, ima li neko decembarski i januarski BAJT (ja ih nisam dobio) i da li su objavili neku ispravku pomenutog članka iz novembra? Ako nisu, baš bih voleo da neko kontaktira autora i pita ga za objašnjenje inkriminisanog sleda operacija gde se gubi oko 90 bita potrebnog rezultata... > Da li je ovaj možda > odgovarajući. Inače ovaj source se nalazi u arhivi > DDJ9311.zip, mislim da ima na sezamu, ako nema ima na > ffs-u. Ne zadovoljava elementarnu postavku, da se na osnovu signature ne može (lako) rekonstruisati bilo kakav drugi tekst koji će dati istu signaturu.
algoritmi.243 isekulovic, -> #242, janko
>> Naprotiv, nađena su dva odlična. Osim toga, pronađeno je da nešto Ups, mora da sam prerano prestao da pratim diskusiju. Može li pointer na poruke u kojima su opisani?
algoritmi.244 bulaja,
Koji je algoritam za odredjivanje kontrolnog broja žiro računa?
algoritmi.245 dejanr, -> #244, bulaja
>> Koji je algoritam za odredjivanje kontrolnog broja žiro računa? Pogledaj Bajtove lične prirode u "Računarima" koji u sredu izlaze :) Bio je i ovde na Sezamu, ako se dobro sećam. Sasvim ukratko, račun dopuniš na 18 cifara ubacujući nule pre poslednje grupe. Recimo, ako 60811-620-16, napraviš ga da bude 608116200000000016. Onda ga propustiš kroz sledeću proceduru: function kbroj(ulaz: string): integer; var i, tmp: longint; begin tmp:=0; for i:=length(ulaz) downto 1 do begin if (red[i]>='0') and (red[i]<='9') then tmp:=tmp+(ord(red[i])-ord('0'))*(length(ulaz)-i+2) else begin kbroj:=-1; exit; end; end; tmp:=11-(tmp mod 11); if tmp>=10 then tmp:=0; kbroj:=tmp; end;
algoritmi.246 zolika,
Ne znam da li je sledećoj poruci mesto u ovoj temi, al' ajde... OBAVEŠTAVAM CENJENE KORISNIKE SEZAMA (KOJE TO ZANIMA) DA SAM DANAS, 25. FEBRUARA 1994. GODINE D I P L O M I R A O. Ovo ne kucam zato da bih se hvalisao, već da bih se ZAHVALIO svima onima koji su svakom svojom idejom, makar i najmanjom, uticali na uspeh mog diplomskog rada i koji su mi pružili pomoć kada mi je bila potrebna.
algoritmi.247 .bale., -> #246, zolika
> OBAVEŠTAVAM CENJENE KORISNIKE SEZAMA (KOJE TO ZANIMA) DA SAM DANAS, > 25. FEBRUARA 1994. GODINE > D I P L O M I R A O. Bravo, majstore! :) Je l' proradio BBS? ;-)
algoritmi.248 janko, -> #246, zolika
> OBAVEŠTAVAM CENJENE KORISNIKE SEZAMA (KOJE TO ZANIMA) DA > SAM DANAS, 25. FEBRUARA 1994. GODINE > D I P L O M I R A O. :) žestitam. Za one koji ne prate (nepostojeću) rubriku lične vesti u konferenciji MALI OGLASI: I ja diplomirah, jedan dan ranije. Na ETF BGD, smer računarska tehnika i informatika. :)
algoritmi.249 dr.grba, -> #246, zolika
>> D I P L O M I R A O. Moje čestitke. Nadam se da ćeš naći adekvatno plaćen posao.
algoritmi.250 dr.grba, -> #248, janko
>> I ja diplomirah, jedan dan ranije. žestitke i iste želje i tebi.
algoritmi.251 asterix, -> #249, dr.grba
>>> D I P L O M I R A O. > > Moje čestitke. Nadam se da ćeš naći adekvatno plaćen posao. ^^^^^^^^^^^^ Đirlo maneken ? ... To je dobro plaćen posao. ;)
algoritmi.252 zolika, -> #247, .bale.
>> Bravo, majstore! :) Je l' proradio BBS? ;-) Na komercijalnim osnovama još nije (a čini mi se da i neće), ali je na odbrani diplomskog radio baš kao što treba!!! :-)))))
algoritmi.253 dr.grba, -> #251, asterix
>> > Moje čestitke. Nadam se da ćeš naći adekvatno plaćen posao. >> Đirlo maneken ? ... To je dobro plaćen posao. Šali nikad kraja. Ali bio sam krajnje ozbiljan u onome što sam napisao.
algoritmi.254 vitez.koja, -> #252, zolika
#=> Na komercijalnim osnovama još nije (a čini mi se da i neće), ali #=> je na odbrani diplomskog radio baš kao što treba!!! :-))))) A za onaj multitasking šta si uradio? (nije tajna?) sk
algoritmi.255 zolika, -> #253, dr.grba
>>>> Đirlo maneken ? ... To je dobro plaćen posao. >> >> Šali nikad kraja. Ali bio sam krajnje ozbiljan u onome što sam napisao. To sam i mislio. Što se džirlo-manekena tiče... možda, ako me baš pritisne besparica :-)))) Uostalom, asterix baš voli da se šali.
algoritmi.256 dr.grba, -> #255, zolika
>> To sam i mislio. Što se džirlo-manekena tiče... možda, ako me baš >> pritisne besparica :-)))) Uostalom, asterix baš voli da se šali. BTW, jeste li čuli šta Isak Džirlo radi po Sloveniji? Osim što ga voze u autu vrednom 120.000 USD, prodaje prezervative umočene u med (:
algoritmi.257 markom, -> #256, dr.grba
*** u autu vrednom 120.000 USD, prodaje prezervative umočene u *** med (: Uhhhhhh, i to neko kupuje, pfhuy :( Marko
algoritmi.259 maksa, -> #258, dcolak
>> Treba mi program u C-u (rutina, funkcija) za generisanje >> Random (slučajnih) brojeva. Računari 88 (Januar 93), strana 77, Bajtovi Godine, slika 8.
algoritmi.260 markom,
Kahm, molio bih poštovani Sezamov auditorijum za malo pažnje i pomoći O:) ------------------------------------------------------------------------- Potrebna mi je rutina, najbolje bi bilo u C-u. Naime, imam jedan string u ko- jem pored normalnog teksta ima i ansi sekvenci, a one tu nisu poželjne ;). Da li ima dobre duše da mi kaže gde to ima (pošto mi se čini da sam tako nešto negde video) ili da pošalje gotovu funkciju. Prilično mi je hitno, pa ako ne ume i zna, nek podeli radost sa mnom :) Unapred zahvalan, Ja :))
algoritmi.261 drakce, -> #260, markom
│ Potrebna mi je rutina, najbolje bi bilo u C-u. Naime, imam jedan string u │ kojem pored normalnog teksta ima i ansi sekvenci, a one tu nisu poželjne ;). └───────── Imam source programa u Pascal-u, koji radi sličnu stvar: > CLRESC is a simple filter to remove ANSI escape sequences from a file. > It also removes all graphic characters, replacing them by spaces to > maintain alignment of the non-graphic characters. It is useful in > cleaning up logs of sessions on bulletin boards which use escape > sequences for screen graphics and screen clearing. clresc2.arj
algoritmi.262 markom, -> #261, drakce
*** Imam source programa u Pascal-u, koji radi sličnu stvar: Ma nema veze, preradiće se to :))) Tnx :)
algoritmi.263 vitez.koja, -> #261, drakce
(odgovor preko odgovora, iz opravdanih razloga) #=>│ Potrebna mi je rutina, najbolje bi bilo u C-u. Naime, #=>│ imam jedan string u kojem pored normalnog teksta ima i #=>│ ansi sekvenci, a one tu nisu poželjne ;). Ako pretpostavimo da ispisuješ string slovo po slovo, potrebno je uraditi sledeće: kada naiđeš na ANSI escape sekvencu ESC[ preskoči sve do prvog slova, *I* to slovo; ANSI komanda ima oblik ESC[<op1>,<op2>,...,<opn><K>, gde su <op> brojne vrednosti a <K> karakter koji označava komandu. Znači, if(*text==0x5B && *(text-1)==0x1B) while(!isalpha(*p++)); Ja koristim sledeće: void host::ansiputs (char *str) { char *p; p=str; while(*p) { if(*p==0x1B && *(p+1)==0x5B) if(!ansi) skipansi(&p); putch(*p++); } } inline void host::skipansi (char **p) { (*p)+=2; while(!isalpha(**p)) (*p)++; (*p)++; } ... pri čemu je ansi neka (globalna) promenljiva koja određuje da li su ansi sekvence dozvoljene.
algoritmi.264 mbole,
Da li ima neko generatore slučajnih brojeva koji se uklapaju u određenu raspodelu? Neophodna mi je gama raspodela, a neću se ljutiti ni za ostale. Poželjno u Paskalu.
algoritmi.265 mirche, -> #262, markom
> Ma nema veze, preradiće se to :))) Tnx :) BTNJ, Jel' treba nekom program tp2tc (com ili exe -ne sećam se) koji prevodi pascal source u c source. (osećam da je neka glupost al' kome treba daću mu da ispita.)
algoritmi.266 sbrk, -> #265, mirche
>> BTNJ, Jel' treba nekom program tp2tc (com ili exe -ne sećam se) koji >> prevodi pascal source u c source. Koja verzija? Ako te ne mrzi, pošalji parče READ.ME fajla, ono sa zaglavljem itd...
algoritmi.267 kale, -> #264, mbole
>> Da li ima neko generatore slučajnih brojeva koji se uklapaju u određenu >> raspodelu? Taj problem se u opštem slučaju deli na 2. Prvo izabereš neki sa linearnom raspodelom pa nad njime generisanim brojevima primeniš odgovarajuću inverznu funkciju. Recimo da želiš raspodelu F(x)=x**2. Imaš niz x1, x2, x3,... koji ima linearnu raspodelu. Niz y(i)=sqrt(x(i)) ima traženu raspodelu. Pozdrav!
algoritmi.268 dejanr, -> #267, kale
>> Recimo da želiš raspodelu F(x)=x**2. Imaš niz x1, x2, x3,... koji ima >> linearnu raspodelu. Niz y(i)=sqrt(x(i)) ima traženu raspodelu. Da, to je standardni postupak. Jedino je muka što za mnoge raspodele nije lako (ili nije moguće) odrediti inverznu funkciju od F(x)... recimo mislim da se za generator slučajnih brojeva koji radi po normalnoj raspodeli koristi generator sa uniformnom raspodelom (rnd) pa se onda broj "propusti" kroz neki polinom koji je *približan* inverznoj funkciji.
algoritmi.269 tica, -> #265, mirche
oo_ BTNJ, Jel' treba nekom program tp2tc (com ili exe -ne sećam oo_ se) koji Treba meni (ali nisam bas optimista da ce da proradi).
algoritmi.270 janko, -> #268, dejanr
> lako (ili nije moguće) odrediti inverznu funkciju od > F(x)... recimo mislim da se za generator slučajnih brojeva > koji radi po normalnoj raspodeli koristi generator sa > uniformnom raspodelom (rnd) pa se onda broj "propusti" > kroz neki polinom koji je *približan* inverznoj funkciji. Ako se sećam, ima još jedan prost način, ali ne znam koliko je efikasan -- svaka raspodela teži normalnoj, ako se sabiraju uzorci, ili "lepe" i tako nekako. Slabiji programeri i kada ne žele dobiju normalnu raspodelu, zbog ovog efekta.
algoritmi.271 ndragan, -> #265, mirche
/ BTNJ, Ej, šta ti je ovo BTNJ?
algoritmi.272 markom, -> #271, ndragan
*** Ej, šta ti je ovo BTNJ? Koliko sam ja shvatio BTW, ali po juski ćirilici :)
algoritmi.273 dr.grba, -> #271, ndragan
>> Ej, šta ti je ovo BTNJ? Verovatno bdž the njadž (:
algoritmi.274 robert,
>> Ej, šta ti je ovo BTNJ? BTNJ = BTW samo ćirilicom koja je prevedena na latinicu ;)). Isto kao NJINDONJS = WINDOWS :).
algoritmi.275 mirche, -> #271, ndragan
> Ej, šta ti je ovo BTNJ? Znaju ćiriličari. ;) (To je onaj kodni raspored za ćirilicu koji umesto W ima ćirilično Nj umesto Q - Lj i umesto X - Dž, pa je razumljivo od BTW došlo do BTNJ zarad razbijanja monotonije. ;)) UBR po naški je ekvivalent BTW-u. Kad smo već tu evo još jednog: NBTZ - Ne bilo ti zapoveđeno... :)
algoritmi.277 janko, -> #271, ndragan
> Ej, šta ti je ovo BTNJ? A ti kao ne znaš? NJ je ono slovo na tastaturi levo od E. :)) Pa baci pogled na američke tastature... Njhat džou see is njhat džou get = NJDčSINJG Podždrav.
algoritmi.278 mmitrovic, -> #275, mirche
Ů█▀█Ţ Kad smo već tu evo još jednog: NBTZ - Ne bilo ti zapoveđeno... :) Ili umesto ASAP (As Soon As Posibile) može ŠJPM (Što Je Pre Moguće). ;) _mmix_
algoritmi.279 mmitrovic, -> #277, janko
Ů█▀█Ţ Njhat džou see is njhat džou get = NJDčSINJG Fali jedno Dč. _mmix_
algoritmi.280 ndragan, -> #275, mirche
/> Ej, šta ti je ovo BTNJ? / Znaju ćiriličari. ;) Vrlo dobar, 4+, sedi. Za 5 da otplivaš uzvodno i da nađeš ko je to izmislio ;)
algoritmi.281 mirche, -> #280, ndragan
> izmislio ;) Izmislio? Misliš, UPOTREBIO? Pa i nije bila potrebna neka velika mudrost da se dođe do ovoga. Pri 'preslušavanju' fajla 'himna.bre' upalila mi se ćirilica i, kao i verovatno svi ostali koji su to videli, razvuk'o usta u :) videvši NjindoNjs. Mirche
algoritmi.282 spantic, -> #281, mirche
> 'preslušavanju' fajla 'himna.bre' upalila mi se ćirilica i, kao i verovatno Kad smo već kod toga. Ima li iko "Bože pravde" kao wav?
algoritmi.283 sbrk, -> #282, spantic
>> Kad smo već kod toga. Ima li iko "Bože pravde" kao wav? Ja koliko znam ta melodija postoji na Amigi za SoundTracker. Ako ovo čita neki Amigista, neka se javi.
algoritmi.284 magician, -> #283, sbrk
­=> Ja koliko znam ta melodija postoji na Amigi za SoundTracker. Ako ovo ­=> čita neki Amigista, neka se javi. Imam ja kao "mod".
algoritmi.285 ndragan, -> #281, mirche
/ Izmislio? Misliš, UPOTREBIO? Izmislio, pa upotrebio. / Pa i nije bila potrebna neka velika mudrost da se dođe do ovoga. Pri Nije, samo trenutak nadahnuća. Inače, takav slučaj kao što se tebi desio meni se nije mogao desiti, jer već više od godinu dana ne koristim juski ćirilicu - prešao sam na b.015; drugo, već više od tri godine nemam pendžere na disku.
algoritmi.286 mmitrovic, -> #284, magician
Ů█▀█Ţ Imam ja kao "mod". Pa podeli ga s' nama. _mmix_
algoritmi.287 magician, -> #286, mmitrovic
­=> Pa podeli ga s' nama. Pa, da ga podelim... bogpravd.zip
algoritmi.288 dejanr,
========== security/encryption #770, from ssatchell, 540 chars, Wed Mar 9 00:19:58 1994 Comment to 767. Comment(s). ---------- One of the forgotten facts of DES is that the theory behind the selection of the S-boxes is still classified information. Based on some public comments I've seen over the past few weeks, I've come to suspect that Skipjack uses the same basic scheme as DES uses, only with a longer key and more cycles. People have implemented DES without understanding the theory behind it. I suspect that if we had more information, it would be *easy* to write a version of Skipjack without the law-enforcement field or (shudder) user-definable keys... ========== security/encryption #771, from jrubin, 1508 chars, Wed Mar 9 02:13:39 1994 Comment to 770. ---------- >>DES Sboxes When DES came out, I did a lot of analysis of the Sboxes. As others have reported, they have some peculiar properties: 1) S box 3 does not contain independant permutations. Call the 4 permutations A B C D Then C = A followed by wire crossing D = B followed by the same wire crossing. The result is that toggling one of the input bits leaves the parity of 2 separate pairs of outputs unchanged. 2) In one other case, the S box, which is supposed to be a non-linear function from 6 input bits to 4 output bits, can be expressed in terms of linear operations a smaller non-linear part. I don't remember the details, but it was something like 4 bits -> 3 bits. I never developed a way to exhaustively check for this phenomena. 3) All of the S boxes have linear relations connecting input and output bits which hold EXCEPT FOR A SMALL NUMBER OF STATES. Typically, there are 3 exceptional states. This may be true of randomly constructed S boxes and may not be significant. These facts are suspicious, but by themselves don't seem to lead to a way to crack DES. It might be interesting to examine the problem from the NSA's point of view. You have a cipher like DES, but with different details. How do you choose S boxes that will introduce a subtle weakness? I suspect the "peculiarities" above are artifacts of an attempt to weaken DES. There must be few suitable S boxes, if they had to be as blatant as to choose S3 the way they did.
algoritmi.289 dejanr,
Uz ovu poruku je interesantan prilog Thomasa C. Jonesa pod naslovom "Cipher-Chain-Cipher Mode of Operation for Improving the Security of Block Ciphers". Reč je o, koliko je autoru poznato, originalnoj ideji za unapređenje postojećih kriptografskih algoritama. ========== security/long.messages #246, from peace, 21634 chars, Thu Mar 17 22:56:39 1994 ---------- Fellow cryptorians: The following is a draft of a paper that describes a mode of operation that I personally feel is useful for bulk data encryption for PEM, RIPEM, EDI, PGP and any other secure email application. In particular, submode CC1 is proposed for these applications. I would welcome any suggestions that would help in evaluating this method in those venues. peace at acm.org - - - - - - - - - - - - - - - - - - - - - - Cipher-Chain-Cipher Mode of Operation for Improving the Security of Block Ciphers by Thomas C. Jones 1 ABSTRACT As a way to extend the usefulness of encryption with the DES and prevent several of the more common attacks on the DES, a new mode of operation is defined that can be used with any block cipher, including DES. This mode of operation performs a cipher operation both before and after a chaining operation and so could be called cipher-chain-cipher (CCC) mode of operation. It is characterized by never performing any operation with the plaintext data except immediately after one cipher operation and immediately prior to another, so that cipher operations separate the plaintext and ciphertext in both directions. Thus the common known-text attack and chosen-text attack are avoided and, for some implementations, only two DES operations are required per plaintext block. sifre.zip
algoritmi.290 dgrbic,
Jel neko može da me posavetuje kako da uradim neko jednostavno (i brzo) šifrovanje, a koje se ipak teže provaljuje od nekog xorovanja ili slično? Xorovanje se mnogo lako provali ako znaš početak šifrovanog fajla (npr. MZ za .exe fajlove itd...)