KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

I. 262. A classical way of encrypting texts is the method of letter substitution, in which certain letters of the alphabet are systematically replaced by different ones. However, this encryption scheme (also called substitution cipher) was relatively easy to decipher -- even before the advent of computers -- using statistical methods by comparing the frequencies of different letters in the encrypted text and in the given language.

The file titkos.txt contains the encrypted text, encoded by using a letter substitution scheme. Before the encryption however the original text (in Hungarian) was preprocessed as follows:

[--] the diacritical marks were removed from vowels;

[--] each space was replaced by a letter q;

[--] all punctuation marks and indentation were removed;

[--] each letter was capitalized.

After these steps, the fixed substitution scheme was applied: each letter was replaced by another one.

You can find the beginning of the encrypted text below.

Your program i262 should decrypt the encoded text.

The first command line argument to your program is the name of the file containing the encrypted text. The second argument is the name of a file containing a long sample text in Hungarian. By using this second file, you should determine the relative occurrences of the letters (that is, their frequency distribution) in a typical Hungarian text. Sample texts of this type are found in the Hungarian Electronic Library for example. The third command line argument to your program is the name of the output file containing the decoded (or partially decoded) original text.

Your program should display the frequency distribution of the letters of the first two files. (Higher frequencies should come first.) The first 100-200 characters of the encrypted text should also be displayed, in which one should be able to perform some letter substitutions: the already substituted letters can be displayed as lowercase letters. It is not required to replace all the uppercase characters, additional corrections of the text may be performed afterwards.

You should submit the following in a compressed file (i262.zip, i262.rar):

[--] the decrypted text (megfejtes.txt),

[--] the source code of your program (i262.pas, i262.cpp, ...),

[--] a short documentation of your program (i262.txt, i262.pdf, ...) containing how to use your program, a brief description of your solution and specifying which developer environment to use for compiling the source code.

(10 points)

Deadline expired on 11 April 2011.


Google Translation (Sorry, the solution is published in Hungarian only.)

Mintamegoldásként Szabó Attila (Pécs, Leőwey Klára Gimnázium, 10. osztály) tanuló munkáját közöljük: i262.pas

Megfejtés

karinthy frigyes zold barackok egy nagy barackfan tavasszal mikor melegen es baratsagosan kezdett sutni a nap kinyitottak szemuket a picike zold barackok es...

Forrás: http://www.mek.iif.hu/porta/szint/human/szepirod/magyar/karinthy/barack.hun

Ékezetekkel és írásjelekkel és tagolva:

Karinthy Frigyes:

ZÖLD BARACKOK

Egy nagy barackfán tavasszal, mikor melegen és barátságosan kezdett sütni a nap, kinyitották szemüket a picike, zöld barackok, és kiváncsian körülnéztek.

- De jó meleg van - mondta az egyik barack, akit Gábor baracknak hívtak. - Mitől van olyan jó meleg? ...

A program leírásának részlete:

Magyar nyelvű mintaszövegnek Jókai: Az arany ember című regényének szövegét használtam.

A statisztika elkészítésében a titkos szövegben az 'U' betű, a mintában a szóköz volt messze a leggyakoribb, ebből következően az 'U' betű a szóközt helyettesíti.

A titkos szövegben több 'B' betű jelent meg: a magyarban a leggyakoribb egybetűs szó az 'a' névelő, így a 'B' betű megfelelője az 'a'.

Több helyen látható 'aY' szó, aminek megfelelő magyar szavak közül a leggyakoribb az 'az', tehát az 'Y' megfelelője a 'z'.

A gyakorisági elemzés szerint a titkos szövegben 'J' és a mintaszövegben 'e' gyakorisága közel azonos, így azokat megfeleltethetjük egymásnak.

Több helyen látható az 'eF' szó, aminek leggyakoribb megfelelője a magyar nyelvben az 'es' ('és') szó, tehát 'F' megfelelője az 's'.

A szövegben gyakran látható a 'PS' együttes, ami valamely kettős betű megfelelője lehet. Az 'ePS' szó gyakori előfordulásából sejthető, hogy 'PS' a 'gy' megfelelője, azaz 'P'='g' és 'S'='y'.

A 7. sorban látható a 'NVyaO' szó, amiből látható, hogy 'Vy' is egy kettős betű, azaz 'V' 'l', 'n' vagy 't' megfelelője.

Látható, hogy 'V' gyakorisága legközelebb 'l'-éhez áll, ezért 'V'='l'-et feltételezzük. Az 1. sor végénél látható a 'EaZaAsagNsaO' szó, amelynek végén a '-sag' feltehetően főnévképző, amihez toldalékként az '-os' és '-an' képzők illenek: ebből sejthető, hogy 'N'='o' és 'O'='n'; ezt a gyakorisági elemzés is alátámasztja.

A 7. sorban látható a 'Molenyesen' szó, amely minden bizonnyal a 'folenyesen' szónak felel meg: 'M'='f'.

Az 5. sorban látható 'aAAol a nagy saZgaAol' kifejezésben meglátható a '-tol' rag, amiből 'A'='t'.

A 7. sorban látható 'az Qs egy' kifejezésben a második szó sejthetően 'is', tehát 'Q'='i'.

A szöveg második szava 'fZigyes', aminek egyedüli értelmezése 'frigyes': 'Z'='r'. Ebből a névből sejthető, hogy a szöveg első szava 'karinthy', amit a szöveg meglevő karakterei megerősítenek: ebből 'T'='k' és 'H'='h'. A szöveg 7. szava 'EaraCkfan', amiből sejthető, hogy 'EaraCk' valamilyen gyümölcs neve: ez a 'barack', tehát 'E'='b' és 'C'='c'. A szöveg első sora ezután könnyen elolvasható, a hiányzó karakterek: 'I'='d', 'L'='v', 'G'='m'. A szövegből hiányzó maradék karakterek: 'X'='u', 'R'='p', 'W'='j'. Eddig a 'D' és 'I' karakterek megfejtését nem találtuk meg, ezeknek a magyar 'w' és 'x' betűk felelhetnek meg. Ezek a karakterek nincsenek a szöveg kiírt részében.

A megfejtés kimentése után a szöveg közepe táján a 'Dilde oszkar' szöveg található, ami nyilván 'wilde oszkar'-nak olvasható, tehát 'D'='w', és így 'I'='x'. A teljes szöveget megfejtettük. A gyakoriságok is közelítőleg megfelelnek a magyar mintaszöveg eloszlásának.

Ha a megfejtés során egy karakter megfeleltetését eltévesztjük, azt könnyen javítani lehet.


Statistics on problem I. 262.
7 students sent a solution.
10 points:Barta 111 János, Leitereg András, Szabó 928 Attila.
5 points:1 student.
4 points:1 student.
3 points:2 students.


  • Problems in Information Technology of KöMaL, March 2011

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley