Pereikite tiesiai prie užduočių

Kas yra “Cipher”?

Ar kada nors norėjote parašyti slaptą žinutę draugui, kad kiti jos nesuprastų? Tada jums reikia Cipher, arba šifro lietuviškai! Šifras – tai tiesiog metodas, paverčiantis įprastą tekstą į „kodą“ keičiant simbolius (dažniausiai raides) kitais simboliais. Rezultatas atrodo kaip nesąmonė tiems, kurie nežino, kaip veikia kodas. Esminis dalykas yra tas, kad tik tie, kurie žino raktą (taisyklę, kaip keisti raides), gali vėl padaryti kodą suprantamą. Kitaip tariant: šifrai leidžia siųsti slaptas žinutes, nesvarbu, ar tai vaikystės žaidimas su slaptomis kalbomis, ar tikri šnipai, siunčiantys užšifruotas žinutes. 😄

Yra daug rūšių šifrai – kai kurie naudoja skaičius, kai kurie – simbolius, o šiuolaikinė duomenų kriptografija naudoja labai sudėtingus algoritmus. Šie sudėtingi algoritmai reikalauja labai sudėtingos matematikos, todėl pirmiausia galime pažiūrėti į kelis paprastesnius algoritmus!

Monoalfabetiniai Šifrai

Leiskime pirmiausia pažiūrėti į vienus iš paprasčiausių (ir seniausių) kodavimo metodų, egzistuojančių: monoalfabetinius šifrus.

Monoalfabetinis gali skambėti kaip sudėtingas žodis, bet galime jį padalyti: mono reiškia „vienas“, o alfabetinis – apie alfabetą.

Taigi, monoalfabetiniai šifrai yra kodai, kuriuose visam pranešimui naudojamas vienas „šifravimo alfabetas“. Tai reiškia, kad kiekviena originalaus teksto raidė visada keičiama ta pačia raide per visą užšifruotą pranešimą.

Pavyzdžiui, jei nuspręsite, kad A turi būti pakeista X, tada visos A raidės tekste bus pakeistos į X.

Cæzario šifras

Klasikinis monoalfabetinio šifro pavyzdys yra Cezario šifras (pavadintas Julijaus Cezario garbei). Tai iš esmės taisyklė, pagal kurią visos raidės stumiami tam tikru skaičiumi pozicijų pirmyn abėcėlėje. Teigiama, kad pats Cezaris savo slaptose žinutėse naudojo 3 raidžių poslinkį. Tai veikia taip: A virsta D, B virsta E, C virsta F ir taip toliau per abėcėlę. (Praėjus Z, pradedama nuo A iš naujo.) Žinutė ABC, taigi, taptų DEF, jei naudotume Cezario metodą.

Kaip veikia Cezario šifras praktikoje:

• Pasirinkite raktą: Nuspręskite slaptą skaičių (pavyzdžiui, 3), nurodantį, kiek pozicijų perkelsite kiekvieną raidę.
• Pakeiskite kiekvieną raidę: Kiekvienai raidei pradinėje žinutėje raskite raidę, esančią tiek pozicijų toliau abėcėlėje (raktui 3, A taps D, B taps E ir t.t. – nepamirškite sugrįžti prie A po Z, jei reikia). Galite įtraukti ir Æ, Ø ir Å, tačiau tai bus šiek tiek sudėtingiau.
• Užšifruota žinutė: Pakeiskite raides ir parašykite naują žinutę su „perstumtomis“ raidėmis. Vips – turite neskaitytiną, slaptą tekstą, kurį suprasti gali tik tie, kurie žino raktą!
• Norėdami iššifruoti (t. y. paversti jį atgal į skaitomą tekstą), tiesiog atlikite atvirkštį poslinkį. Jei žinote raktą (pvz., 3), skaityti žinutę yra taip pat lengva, perkeliant raides 3 pozicijas atgal abėcėlėje.

Vienažodės šifrai yra puikus būdas išmokti šifravimo principą. Jie paprasti ir parodo, kaip galime naudoti paprastą taisyklę (raktą) paversti suprantamą tekstą į paslaptingą ir nesuprantamą – ir atgal. Taigi, kitą kartą, kai norėsite nusiųsti draugui slaptą žinutę, galite naudoti Cezario šifrą! Galbūt galite sukurti savo Cezario slaptos abėcėlės variantą? 🔐✨

Užduotys

Užduotis 1.1 – Cezario Šifro Užšifravimas

Dabar iš tikrųjų parašysime šiek tiek kodo! Pradėsime paprastai, įgyvendindami užšifravimą. Remiantis teorija, tai turėtų būti gana paprasta.

Įgyvendinkite užšifravimą Cezario šifru naudodami funkciją, kuri priima tekstą ir skaičių, kuris yra „raktas“, t. y. kiek reikėtų pasukti alfabetą.

def caesar_cipher(text, shift):
    result = ""
    for char in text:
        if char.isalpha():
        # sužinokite pradinį tašką pagal didžiąsias ir mažąsias raides
        start = ord('A') if char.isupper() else ord('a')
        # Sudėtingas poslinkio skaičiavimas
        result += chr((ord(char) - start + shift) % 26 + start)
    else:
        result += char
    return result

Užduotis 1.2 – Cezario šifro atkodavimas

Atkodavimas – tai tiesiog atlikti atvirkštinį skaičiavimą nei užšifravimas. Vietoj sudėjimo, atimkite poslinkį.

def caesar_decrypt(text, shift):
    return caesar_cipher(text, 26 - shift)

def caesar_decrypt(text, shift):
    return caesar_cipher(text, 26 - shift)

Kiti Monoalfabetiniai Šifrai/Ciphers (pvz. Atbash)

Yra ir kitų monoalfabetinių šifrų! Vienas iš paprasčiausių vadinamas “Atbash” šifru.

Kaip veikia Atbash?

Tai labai paprasta, vietoj sukimosi raidės atvaizduojamos į atvirkštą alfabetą. Šioje lentelėje parodytas atvaizdavimas:

Užduotis 1.3 – Atbash šifravimas ir dešifravimas

Tai, kas patogu Atbash, yra tai, kadangi šifravimas yra 1 prie 1 transformacija, jis tiesiogiai veikia atvirkščiai. Kitaip tariant, jei sukūrėte šifravimą, automatiškai sukūrėte ir dešifravimą.

Kaip tai galima padaryti praktiškai?

Galite atimti raidę iš Z, arba sukurti „Lookup“ lentelę. Tai reiškia lentelę arba žodyną, kuriame yra visos raidės nuo a iki z ir į ką jas reikėtų pakeisti. Tai gali būti geras sprendimas, jei norite sukurti kitokio tipo šifravimą.

letters = {
    'a': 'z'
    'b': 'y'
    'c': 'x'
    'd': 'w'
    # ... pridėkite likusias raides žemyn
}

Naudodami šią lentelę, galite pereiti per raidę po raidę, tada išgauti reikšmę kiekvienai raidei iš paieškos lentelės ir ją išvesti. Ką turite padaryti didžiosioms ir mažosioms raidėms?

Dalis 2 – Monoalfabetinių Šifru Kriptoanalizė

Šioje dalyje turite pabandyti sukurti algoritmą, kad „įsilaužtumėte“ Cezario šifrą, t. y. paimkite užšifruotą tekstą, o tada išgaukite originalų tekstą nežinant rakto.

Tai galima padaryti apytiksliai rankiniu būdu arba galite pabandyti naudoti paprastą „kriptoanalizę“. Tai konceptas, kurį mes išsamiau nagrinėsime vėliau, bet dabar mes tiesiog pažiūrėsime į vieną iš paprasčiausių būdų: dažnio analizę (frequency analysis). Daugiau apie šį konceptą galite skaityti čia: Dažnio analizė arba čia Vikipedija – dažnio analizė.

Šį metodą galima naudoti ne tik Cezario šifrui, jį galima naudoti ir sudėtingesniems algoritmams, tačiau Cezario šifras yra toks paprastas, kad dažnio analizė yra triviali.

In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.

Frequency analysis is based on the fact that, in any given stretch of written language, certain letters and combinations of letters occur with varying frequencies. Moreover, there is a characteristic distribution of letters that is roughly the same for almost all samples of that language. For instance, given a section of English language, E, T, A and O are the most common, while Z, Q, X and J are rare. Likewise, TH, ER, ON, and AN are the most common pairs of letters termed bigrams or digraphs), and SS, EE, TT, and FF are the most common repeats. The nonsense phrase ETAOIN SHRDLU represents the 12 most frequent letters in typical English language text.

In some ciphers, such properties of the natural language plaintext are preserved in the ciphertext, and these patterns have the potential to be exploited in a ciphertext-only attack.

xcrgneipcpanhxhugtfjtcrnpcpanhxhxhiwthijsnduiwtugtfjtcrnduatiitghdgvgdjehduatiitghxcprxewtgitmiiwtbtiwdsxhjhtsphpcpxsidqgtpzxcvraphhxrparxewtghugtfjtcrnpcpanhxhxhqphtsdciwtupriiwpixcpcnvxktchigtirwdulgxiitcapcvjpvtrtgipxcatiitghpcsrdbqxcpixdchduatiitghdrrjglxiwkpgnxcvugtfjtcrxthbdgtdktgiwtgtxhprwpgpritgxhixrsxhigxqjixdcduatiitghiwpixhgdjvwaniwthpbtudgpabdhipaahpbeathduiwpiapcvjpvtudgxchipcrtvxktcphtrixdcdutcvaxhwapcvjpvttippcsdpgtiwtbdhirdbbdclwxatofmpcsypgtgpgtaxztlxhtiwtgdcpcspcpgtiwtbdhirdbbdcepxghduatiitghitgbtsqxvgpbhdgsxvgpewhpcshhttiipcsuupgtiwtbdhirdbbdcgtetpihiwtcdchtchtewgphttipdxchwgsajgtegthtcihiwtbdhiugtfjtciatiitghxcinexrpatcvaxhwapcvjpvtitmixchdbtrxewtghhjrwegdetgixthduiwtcpijgpaapcvjpvteapxcitmipgtegthtgktsxciwtrxewtgitmipcsiwthtepiitgchwpktiwteditcixpaidqttmeadxitsxcprxewtgitmidcanpiiprz

Užduotis 2.1 – Dažnumo lentelės sukūrimas

Pytone faile sukurkite angliškų raidžių dažnumo lentelę. Galite pabandyti rasti ją patys, bet jei nenorite to daryti, suprantame!

Jei tikrai norite rasti ją patys, galite elgtis kaip Užduotyje 2.2, bet su labai dideliu tekstu.

english_letter_frequency = {
    'E': 12.70, 
    'T': 9.06, 
    'A': 8.17, 
    'O': 7.51, 
    'I': 6.97, 
    'N': 6.75, 
    'S': 6.33, 
    'H': 6.09, 
    'R': 5.99, 
    'D': 4.25, 
    'L': 4.03, 
    'C': 2.78, 
    'U': 2.76, 
    'M': 2.41, 
    'W': 2.36, 
    'F': 2.23, 
    'G': 2.02, 
    'Y': 1.97, 
    'P': 1.93, 
    'B': 1.29, 
    'V': 0.98, 
    'K': 0.77, 
    'J': 0.15, 
    'X': 0.15, 
    'Q': 0.10, 
    'Z': 0.07
}

Užduotis 2.2 – Skaičiuoti raidžių dažnumą tekste

Dabar sukursime algoritmą, kuris ras raidžių dažnumą duotame tekste.

Užduotis 2.3 – Teksto dažnumo palyginimas su tikruoju dažnumu

Kai jau nustatėte visų teksto raidžių dažnumą, galite sukurti funkciją, kuri ras „atstumą“. Hæ? Ką tai reiškia?!

Galite įsivaizduoti, kad, pavyzdžiui, raidės E dažnumas tekste bus skaičius. Galite rasti „atstumą“ nuo tikrojo dažnumo, kuris yra 12.70. Pavyzdžiui: dažnumas yra 9.63, koks yra atstumas? Atstumas bus absoliuti reikšmė (neigiami skaičiai tampa teigiamais) tarp šių dviejų reikšmių: \(12.70 - 9.63 = 3.07\).

Sukurkite funkciją, kuri pereitų per kiekvieną raidę ir rastų atstumą. Tada sudėkite visus atstumus į bendrą „atstumą“.

Užduotis 2.4 – „Įsilaužti“ į Cezario šifrą

Dabar pagaliau surinkime viską, ką padarėme iki šiol! Dabar mes „įsilaušime“ į Cezario šifrą.

Sukurkite programą, kuri „įsilaužtų“ į Cezario šifrą! Be vartotojo įvesties, turėtumėte galėti įvesti užšifruotą tekstą ir gauti iššifruotą tekstą be rakto.