Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Kódfejtés

  [1]    [2]  

Szeretnél hozzászólni? Jelentkezz be.
[15] V. Dávid2004-09-13 16:14:21

Én máshogy álltam neki a feladatnak.

Először is, minden nyelvnek megvannak a gyakori szavai (pl. az angolnak a "the"). A magyarban is vannak ilyenek, pl. "az", "és", "mert", és még sorolhatnám. De ha ezek a szavak ilyen gyakran előfordulnak, akkor majdnem biztos, hogy a kezdőbetűjük egyforma sorszámú karakteren is lesz modulo n. (n a kulcs jegyeinek a száma)

Ha a kulcshoz képesti eltolásuk ugyanaz, akkor viszont az egymásnak megfelelő betűik ugyanazzal a számmal lesznek kódolva, vagyis ezen szavak kódja azonos.

Tehát írtam egy programot, ami 2, 3, 4 .. 10 betűs ismétlődéseket keresett a szövegben, és kiírta az ismétlődesek közötti eltolást is. Az eltolások legnagyobb közös osztója 8 volt, tehát az a sejtésem alakult ki, hogy a kód ennyi jegyből áll.

Innen nem tudtam folytatni a feltörést, mert nem volt magyar betűgyakorisági táblázatom (kellett volna csinálni:). De ha lett volna, akkor a 8-cal azonos maradékot adó betűket a legkisebb négyzetek módszerével törtem volna fel. Azaz a kódszöveg egyes betűinek gyakoriságát kifejeztem volna százalékban, és a kevés elcsűsztatási lehetőségre összeadtam volna az így kapott gyakoriságok és a magyar nyelv gyakoriságai különbségének négyzetét, ezen összegek közül a legkisebbhez tartozó lehetőség majdnem biztosan jó.

[14] Kós Géza2004-09-13 11:42:08

Kedves Gábor és Káli gúla,

Gratulálok. (Először ijesztő volt a nagy csönd. :-))

Az eloszlások összehasonlítását leírhatnád részletesebben, hadd tanuljunk belőle.

Előzmény: [12] Fehér Gábor, 2004-09-11 20:40:34
[13] Fehér Gábor2004-09-11 23:47:23

Itt a program ha véletlenül valakit érdekel: index.html

[12] Fehér Gábor2004-09-11 20:40:34

Sziasztok!

A 3. feladat megoldása; elnézést az ékezetes betűkért )-: és, hogy nem szedem szavakra HOLVOLTHOLNEMVOLTAZÓPERENCIÁSTENGERENISTÚLATÖRPÉKORSZÁGÁB ANOTTISATÖRPEKIRÁLYUDVARÁBANÉLTEGYSZEREGYIRIGYTÖRPEENNEKA ZIRIGYTÖRPÉNEKNAGYONTETSZETTEKASZÍNESKÖVEKÖSSZEISGY?JTÖTT BEL?LÜKRENGETEGETNAPHOSSZATRAKOSGATTA?KETSBÁRTÖMÉRDEKSZÍN ESKÖVEVOLTMEGNEMENGEDTEVOLNASENKINEKSEMHOGYFÉLTETTKINCSEI HEZAKÁREGYUJJALISHOZZÁÉRJENTÖRTÉNTEGYSZERHOGYEGYMERLINNEV ?VÁNDORMATEMATIKUSVET?DÖTTAKIRÁLYIUDVARBASZÖRNYENNAGYTUDO MÁNYÁVALMÉGAKIRÁLYTISÁMULATBAEJTETTEMEGISKÉRTE?TAKIRÁLYMA RADJONMÉGAZORSZÁGÁBANÉSTANÍTSATÖRPEALATTVALÓITAMATEMATIKA TUDOMÁNYÁRAIGENTMONDOTTMERLINASZÍVESMARASZTALÁSRAÉSTÜSTÉN TMEGISKEZDTEATANÍTÁSTATÖRPÉKNEKNAGYONTETSZETTEKMERLINÓRÁI OTTTOLONGTAKATUDÓSEL?ADÁSAINMINDEGYSZÁLIGKIVÉVEAZIRIGYTÖR PÉTAKIFOLYTONCSAKASZÍNESKÖVEITRAKOSGATTAEGYSZERAZTÁNÉSZRE VETTEHOGYTÁRSAINEMJÖNNEKHOZZÁTÖBBETÉSNEMKÉRLELIKMINTAZEL? TTAMIKORMÉGMINDENKIAZ?SZÍNESKÖVEIVELSZERETETTVOLNAJÁTSZAN IPERSZEHIÁBARÁJÖTTHOGYATÖBBIEKMOSTANÁBANMINDMERLINTHALLGA TJÁKFURDALNIKEZDTEAKIVÁNCSISÁGUGYANMILEHETOLYANNAGYONÉRDE KESAZOKONAZEL?ADÁSOKONELHATÁROZTAHOGYMÁRPEDIG?UTÁNAJÁRENN EKÍGYISTÖRTÉNTEGYSZÉPNAPONBESURRANTAZIRIGYTÖRPEISATEREMBE AHOLMERLINAZEL?ADÁSOKATTARTOTTAHÁTLÁTJAÁMHOGYAKATEDRÁNMER LINEL?TTEGYCSODÁLATOSANSZÉPRAGYOGÓKRISTÁLYHEVERPADSZOMSZÉ DJÁTÓLMEGTUDTAHOGYAGYÖNYÖR?KRISTÁLYABÖLCSESSÉGKÖVEAMIT?LM ERLINSOHAEGYPERCRESEMVÁLIKMEGÉSMÁSOKISCSAKEL?ADÁSAIKÖZBEN LÁTHATJÁKOLYANCSODÁLATOSVOLTAKRISTÁLYHOGYAZIRIGYTÖRPEALIG TUDTAASZEMÉTLEVENNIRÓLAÉSNEMISFIGYELTMERLINEL?ADÁSÁRA

Egyébként abból az ötletből kiindulva fejtettem meg, hogy ha n hosszú a kulcs akkor az n-el azonos maradékot adó sorszámú betüket ugyanazzal 0 és 9 közötti számmal kell eltolni, hogy dekódoljuk a szöveget. Így viszont már lehet vizsgálni a betük gyakoriságát ezekre az azonos maradékot adó halmazokra. (Kezdő kódfejtőknek: minden nyelvre jellemző, hogy egy hosszabb szövegben mennyi a különböző betük előfordulásának az aránya, pl. magyarban az E a leggyakoribb, 9-10Tehát írtam egy olyan programot, ami 1től 60ig minden kulcshosszra megnézi az összes ilyen halmaz betű-gyakoriság statisztikáját. Tehát pl. 5 hosszú kulcshosszra veszi az összes 5k-adik betűt, dekódolja 0-tól 9-ig minden számmal őket, és kiválasztja, hogy melyik számmal kaptuk a magyar nyelvhez leginkább "hasonló" betű-eloszlású halmazt. (Ez a szám lesz a feltételezett kulcs első számjegye.) A "hasonlóság" kiértékelésére volt egy primitív algoritmusom, ami egy számot dobott ki értékelésként. Ezután a program veszi az 5k+1, 5k+2, 5k+3, 5k+4 -edik betűsorozatok értékeléseit is, és az 5 hosszú kulcsszavaknál ezen értékelések átlaga kerül feljegyzésre. Így minél nagyobb ez az átlag egy kulcshosszhoz, annál valószínűbb, hogy olyan hosszú lesz a keresett kulcs. (A 8-as hossz nekem a 4. legmagasabb átlagpontszámot érte el.) És lehet, hogy mázlim volt, de a 8-as kulcshosszhoz tartozó feltételezett értékek pont kiadták a helyes kulcsot. (69314718)

Remélem sikerült érthetően leírnom, kicsit átfésülöm a forráskódot és kiteszem netre azt is. :)

[11] Káli gúla2004-09-11 11:19:12

... számlálás tulajdonképpen egy kölcsönösen egyértelmű megfeleltetés objektumok és egy számosság elemei között.

Előzmény: [10] Kós Géza, 2004-09-09 11:15:37
[10] Kós Géza2004-09-09 11:15:37

Ha jól emlékszem, Verne 800 mérföld az Amazonason c. könyvében szerepel egy titkosírással írt szöveg, amit sokáig nem tudnak megfejteni, pedig pontosan ismerik a titkosító algoritmust is, csak a kulcs hiányzik. Pedig a titkosírás nagyon gyorsan feltörhető...

Először is állapodjunk meg az ábécében: az ábécé most 32 betűből áll, szerepel benne mind a 9 ékezetes magyar betű, de nem szerepel a Q, a W és az X:

AÁBCDEÉFGHIÍJKLMNOÓÖŐPRSTUÚÜŰVYZ

Egy betűt úgy kódolunk, hogy az ábécét egy bizonyos kulcsértékkel elforgatjuk. Ha például a kulcsérték a 3, akkor A helyett C-t, Á helyett D-t, Z helyett B-t írunk.

Az írásjeleket és szóközöket nem kódoljuk és nem írjuk le.

A kulcsértékek periodikusan ismétlődnek, az első periódus a titkosírás kulcsa. (A Verne-regényben 6-jegyű volt a kulcs, most nem feltétlenül annyi.)

Például, ha a kulcs 346, és az "Indul a görög" szöveget akarjuk titkosítani, akkor a kódolt betűk: I+3=K, N+4=Ő, D+6=I, U+3=Ű, L+4=Ó, A+6=É, G+3=Í, Ö+4=S, R+6=Ű, Ö+3=R és G+4=J. A végeredmény tehát: KŐIŰÓÉÍSŰRJ.

Feladat: Íme egy titkosított szöveg, amit a fenti módszerrel kódoltunk. Fejtsük meg!

MÚOYPPUOSSÖÉÖDÓRYHBÖUJSKRJKBÜZÉTLLUÉŐOTAASCUSVRLÖÚUTCGHHGHÖÓŰ

ZÍZÉÁRSUJLÓŰIOZVÍYGŰIEÁŐKMAÍOÁTCJSKLFKSLMZAUZTÉHSOKÖHBÍÚOHÉYŰ

URISÉPRHÍZPSUKYABÉŰZÉPÉABJŐJTPUÉGLSYTFÍÖÚHBCKAUÁÜCHPPRÁRUÉŐMÉ

AÍOGUŐFROSAÚADZSGÖÚÚHDZUGÚRGUÜHBYYŰÓFÚÍÉPVGLOHYLÜCLAÓÓZNKLUGN

HSHKIÁGYPPOGVLÖLLSÉPVLÓIPMZMJSÜÉŰZLÓRJÚÉLNÉFÉRDSHMZÁÓPCMLYIUE

GDFÚÖÉTYŰUUISUKLFÚAHVIULFGHBRÉYŐÖÖOHDVEFUFÓÚRÁAÍTCULŐÚZCLÜPGÚ

UAÉRKSEPZÓZKAÁÚHÁZEŰUOBJOTÉOÁUVÍÓSFUÁBÁFMSJOCLLVBRDÁKTERÚRÉÁE

ÁHÖUKYÁGNHMÍZÖMUUHÜUGÖÖUBÓENGŰHFKPSNLLHBÓÚYAHLIEÁŐKTAÉULUÜFUÜ

ŰYGÁÓFUACHOÖLZÁSÉÁGNDZÍPÉÁŰEPRBTDIUÁLMÉTYTŐOGTUAPLUMLSÁZEŐAÉÜ

RÁYÉABUDPBZŰHHTŰBTAJUÜNHMÍZÖLBEŰJÁAÉULUEYUGYŰURIŐOKÖUCHBTOAÍÁ

ÚAHZUKÖTGSÓOOÚŰIKÓŰZUUŐÚÖHŰFLGYBFÖÜJMŰÉKDTDOOSNUFÉJETFFSKHOOY

LCLCALVÍNDÁRSUKUGÖÖIÓÓEUURJÚÁOFTFOUGTOÚYKNÁUÁOTTNÉÁÜÁHMZZELUÁ

CZBTJABSHDÉAYLJÓJEUHŰACÍŐJNŐUUÖÉONÓFEIÜŐÉHÉAJAÖÉÖŐFYŐLOÍORÍTY

HBÉÓÜUAÉTKLPVNLLTKOGJOPNHBPÜÉJTÍANŐÁJÍEÍSÚAHVÉAÍÁÜYPPOGÓIÜTCF

OÓÜLUTCJIÓFÍCSEÖŐAYÓŐHBFUÜGÍKÉORÓZYHÖBÉFOSNUFNHVMÓRÁJÁÓPHGYPD

LÍASJÉSÖÍOJAJYLCLLDBTHAKTEMÚNDHÖNLPÉOÍÁŐMBFOTÉOÁÓŐKSJÍRGTDÉÓP

SUCAHPPGIIÚÓOTOKŐÓCUEVÓFYHJÓJENHŰYGELMPÁYIÖÁNGSKRUGLMMZÓVÁRSŰ

KOAÍOÁTCKRTÉYŐOÉJTÁŰZCOŰFAÓŰÖÍZŰÚSVÍÖÚÁŰJSKPÍGÁKTMSÍZOÍŐFAKŐV

CEEYÓPÉÁÜÁÚZÓAYHJBŰPBAÓHDNKTHÉÉRCUHÍSHRTGSÓOOKŐVÜUHMZÍVÚFBÓFU

UVHÖTCKRYÉOÁÓJULYNAÜBÓEIKCLURDÍTFSTÚAIÍKHYÜONHMUÁIÁCIPMZGLFRO

BÚSDÖZKTŰGMÉÉÍRMFYÉZVMÍLSDÉGPÖÜPÓRÉYŐÖÖTPNÁKLFTÉÚISKVLÓYEPÍPP

LÍFÜRBZSRKTFYÁPÍSSÁGGTGNRRAÉJORFÁJÁŰÖBPSSÁÁŐITUIIOÁŰTTESSÜÁOV

ÍZYIOZKTHÉÉGKSLMZAUZTÉDPÍNYBFUDFTFÍTHUÓJYKRUKSRPÁLVUGNLYGÓLFG

MŰRÉYŐÖÖÉÓÜÁJFADSD

[9] aPi2004-09-08 18:48:55

Sziasztok!

A 2. Feladat megfejtése: "Időközben a hackereknek volt idejük hogy a"

Segített, hogy épp itt ért véget a szöveg...

Előzmény: [1] V. Dávid, 2004-09-03 10:36:20
[8] V. Dávid2004-09-04 13:17:27

Helyesbítés: Csak az ne írja be, aki már ismeri máshonnan.

Előzmény: [6] V. Dávid, 2004-09-04 09:24:00
[7] V. Dávid2004-09-04 09:24:58

:-) Van ötleted a 2-es feladatra?

Előzmény: [4] WebMonster, 2004-09-04 00:12:02
[6] V. Dávid2004-09-04 09:24:00

Kedves Sirpi!

Ha jól tudom, akkor a Verne-regényben nincs leírva, hogyan lehet feltörni a Vigenére-kódot. Szóval ha még nem ismered a módszert, akkor gondolkozz rajta. Csak az nem írja be a megoldást, aki már ismeri máshonnan.

Előzmény: [5] Sirpi, 2004-09-04 09:14:28
[5] Sirpi2004-09-04 09:14:28

Szia Dávid!

Nem tudtam, hogy Caesar-kódnak hívják, de mivel azt írtad, hogy egyszerű, eltolással próbálkoztam. Amúgy Vigenére-siffréról már 14 éves korom előtt hallottam, ugyanis Vernének a 800 mérföld az Amazonason című regényében pont egy ilyen van, és a bandavezér neve (asszem Ortega) az eltolás alapja. A Sándor Mátyásban pedig (szintén Verne) egy elforgatós siffrírtábla szerepel.

Előzmény: [3] V. Dávid, 2004-09-03 20:40:34
[4] WebMonster2004-09-04 00:12:02

Végre van egy ilyen topic is; már rég foglalkozom kódfejtéssel, mivel mindig is érdekelt. Remélem ezzel sokan vagyunk így ;)

[3] V. Dávid2004-09-03 20:40:34

Gratulálok! Egyszerű Caesar-kód. A hibák természetesen csak véletlenül kerültek bele. De nehéz az ilyesmit pontosan beírni. Na és van ötleted a 2. Feladatra?

(Megjegyzés azoknak, akik még nem tudják: A Caesar-kód lényege, hogy minden betűt eltolunk egy bizonyos számmal. Pl. a=z, b=a ... z=y, ha eggyel toljuk el.)

Elméleti kérdés: 3. Feladat: A következő kódot Vigenére-siffrének hívják. A szöveget periodikusan kódoljuk Caesar-kóddal. Ez azt jelenti, hogy először is választunk egy kulcsszót. Ez legyen például LÁB. A szöveg első karakterét L szerint kódoljuk, azaz olyan Caesar-kóddal, amiben l->a. A második betűt Á, a harmadikat B szerint kódoljuk. Innentől kezdve ezt folytatjuk, azaz a negyedik betűt megint L szerint kódoljuk. (Lehet akár 10 betűs kódot is választani.) Ez ellenáll az egyszerű betűstatisztikai elemzésnek, egy kicsit több kell a feltöréséhez. Sokáig feltörhetetlennek tartották. Találj olyan általános módszert, amivel a Vigenére-siffre könnyen feltörhető.

(Ha valaki már ismeri a módszert, akkor ne írja be.)

Előzmény: [2] Sirpi, 2004-09-03 14:50:01
[2] Sirpi2004-09-03 14:50:01

Az 1. feladatra:

Szerintem van 1-2 hiba a szövegben, de nekem ez jött ki:

A regisztrációs adatbázisban megnevezett útvonalak mappaként jelennek meg, az illető ikonra duplán kattintva érhetjük el őket.

Ezek alapján szerintem a javított kód:

Ű ozbdóüöovxejó űyűöwvüdówűi hzbizszüzöö pösíiűgűf hűmműfaiö ézgziizf hzb, űü dggzöl dfíioű yőmgvi fűöödiösű aoczöéqf zg lfzö

(vagyis a 2. szóba kell egy ü, a negyedikben van egy felesleges k, az 5-et két szóra kell vágni, és a 13.-ba is kell egy q betű)

Előzmény: [1] V. Dávid, 2004-09-03 10:36:20
[1] V. Dávid2004-09-03 10:36:20

Kezdjük egy könnyű feladattal:

1. Feladat: Ű ozbdóöovxejó űyűöwvüdówűi hzbizszüzköö pösíiűgűfhűmműffaiö ézgziizf hzb, űü dggzöl dfíioű yőmgvi fűöödiösű aoczöéf zg lfzö

És egy nehezebb:

2. Feladat: Ibcntkdekeihőnekdokarvegöheojyzaklüa

  [1]    [2]