Shifra e Cezarit: një mini-laborator

Nga variablat te mesazhet sekrete

Në punëtorinë origjinale, pjesëmarrësve u tregua një sfidë në HackerRank që quhej "password cracker", thyerja e fjalëkalimeve, para se të vizatohej qoftë edhe një vijë e vetme me Turtle. Batuta ishte ta linin rehat për momentin. Në fund të këtij mësimi do të kesh ndërtuar anën tjetër të asaj historie: një program të vogël që fsheh një mesazh që të mos lexohet me një shikim, dhe pastaj e zbulon sërish.

Për këtë na duhet një ide që e ke hasur tashmë. Një varg (string) është thjesht tekst i ruajtur në një variabël, si message = "Happy birthday!" nga mësimi i parë. Ajo që nuk e thamë atëherë është se një varg është në të vërtetë një sekuencë karakteresh, një shkronjë pas tjetrës, dhe Python të lejon t'i përshkosh një nga një, pikërisht siç një cikël for përshkon një varg numrash.

Kthimi i një teksti të lexueshëm në tekst të përzier me qëllim, që vetëm dikush me sekretin ta rikthejë, quhet enkriptim. Shifra e Cezarit është truku më i vjetër në këtë fushë, që mban emrin e Jul Cezarit, i cili e përdorte për të mbrojtur urdhrat e tij ushtarakë.

Ideja e shifrës së Cezarit

Rregulli është thuajse tepër i thjeshtë. Zgjidh një numër, të quajtur zhvendosje. Pastaj çoje çdo shkronjë përpara në alfabet me atë numër hapash.

Me një zhvendosje prej 3, A bëhet D, B bëhet E, C bëhet F, e kështu me radhë. Fjala HELLO kthehet në KHOOR. Për ta lexuar sërish, e zhvendos çdo shkronjë po aq hapa mbrapsht.

Ka vetëm një gjë për t'u kujdesur. Kur del jashtë fundit të alfabetit, kthehesh në fillim. Me një zhvendosje prej 3, X bëhet A, Y bëhet B, Z bëhet C. Alfabeti sillet si një rreth, jo si një vijë e drejtë.

Ky kthim rrethor është i gjithë problemi kur e shkruajmë në kod. Gjithçka tjetër është një cikël mbi karakteret.

E ndërtojmë shkronjë për shkronjë

Një zakon i mirë nga mësimi i funksioneve është të zgjidhësh më parë problemin më të vogël. Këtu problemi më i vogël është: zhvendos një karakter të vetëm. Sapo të funksionojë një shkronjë, një cikël e mbaron pjesën tjetër.

Python na jep dy ndihmës për këtë. ord("A") kthen numrin që kompjuteri përdor për një karakter (65 për A të madhe), dhe chr(65) e kthen atë numër sërish në karakter. Kështu mund të bëjmë veprime aritmetike me shkronjat duke i kthyer në numra, duke i zhvendosur, dhe duke i kthyer prapa.

def shift_character(ch, shift):
    if "A" <= ch <= "Z":
        base = ord("A")
    elif "a" <= ch <= "z":
        base = ord("a")
    else:
        return ch
    return chr((ord(ch) - base + shift) % 26 + base)

Lexoje ngadalë. Dy krahasimet kontrollojnë nëse ch është një nga 26 shkronjat e mëdha të alfabetit anglez ose një nga 26 të voglat. base është numri i shkronjës së parë, A për të mëdhatë ose a për të voglat, që ord(ch) - base të na japë një pozicion të pastër nga 0 deri në 25 në vend të një kodi të papërpunuar. I shtojmë zhvendosjen, marrim mbetjen pas pjesëtimit me 26 me % 26 (ky është kthimi rrethor), pastaj i shtojmë base prapa për t'u kthyer te shkronjat e vërteta. Çdo gjë tjetër, një hapësirë, një numër, ose një shkronjë jashtë atyre 26 si ë dhe ç, kthehet e paprekur, pikërisht si te fusha e lojës në fund të këtij mësimi.

Tani cikli. Enkriptimi i një mesazhi të tërë do të thotë thjesht të nisësh me një varg bosh, të zhvendosësh çdo karakter me radhë dhe t'ia shtosh në fund.

def encrypt(text, shift):
    result = ""
    for c in text:
        result = result + shift_character(c, shift)
    return result

Le ta provojmë me diçka nga vendi ynë.

print(encrypt("See you Saturday", 3))
# -> Vhh brx Vdwxugdb

print(encrypt("MEET AT 11", 3))
# -> PHHW DW 11

Vëre që hapësira dhe shifrat 11 kaluan të paprekura, pikërisht siç premtoi ndihmësi ynë.

Deshifrimi: zhvendos nga ana tjetër

Nëse enkriptimi i çon shkronjat përpara, deshifrimi thjesht i çon mbrapsht. Pjesa e bukur është se nuk na duhet asnjë kod i ri. Zhvendosja mbrapsht me 3 është e njëjta gjë me zhvendosjen përpara me minus 3, dhe % 26 në ndihmësin tonë i trajton numrat negativë saktë.

def decrypt(text, shift):
    return encrypt(text, -shift)

Kështu udhëtimi i plotë, vajtje-ardhje, duket kështu:

secret = encrypt("Takohemi te sheshi", 3)
print(secret)
# -> Wdnrkhpl wh vkhvkl

print(decrypt(secret, 3))
# -> Takohemi te sheshi

Mesazhi doli i përzier dhe u kthye i plotë.

Ja edhe e keqja e sinqertë, dhe arsyeja pse ky është një laborator dhe jo siguri e vërtetë. Ka vetëm 25 zhvendosje të dobishme. Një kompjuter i provon të gjitha brenda një çasti dhe e lexon mesazhin pa iu treguar kurrë numri. Prandaj shifra e Cezarit është një lodër, ndërsa enkriptimi që mbron aplikacionin e bankës mbështetet te çelësa aq të mëdhenj sa provimi i të gjithëve do të zgjaste më shumë se mosha e universit.

Këtu tregon edhe fija përshkuese përpara. Ajo sfida e parë "password cracker" kishte të bënte me një makinë që merr me mend sekrete duke provuar mundësi. Në mësimin e mëparshëm takove PassGAN, ku një IA moderne mëson të marrë me mend fjalëkalime ashtu si i shkruajnë vërtet njerëzit. Shifra e Cezarit është vështrimi yt i parë e miqësor te ajo garë mes fshehjes së një sekreti dhe zbulimit të tij.

Para se të vazhdosh, provoje drejtpërdrejt më poshtë: shkruaj një mesazh, tërhiq zhvendosjen, dhe shihe si përzihet e kthehet i plotë, pastaj jepi makinës të 25 zhvendosjet njëherësh dhe shih sa shpejt bie një sekret i Cezarit.

Provo veten

Punoji këto me fjalët e tua para se të vazhdosh.

1. Me një zhvendosje prej 1, në ç'shkronjë kthehet Z dhe cili rresht i shift_character e bën këtë të mundur?
2. E shkruam decrypt në një rresht të vetëm që thërret encrypt. Me fjalë të thjeshta, pse zhvendosja mbrapsht me 3 është e njëjta gjë me zhvendosjen përpara me minus 3?
3. Nëse një shok të dërgon një mesazh të enkriptuar me Cezarin por harron të të thotë zhvendosjen, a do të mund ta lexoje prapëseprapë? Shpjego çfarë do të provoje, dhe çfarë të tregon kjo për sa e sigurt është vërtet kjo shifër.

Përgjigjet

1. Z bëhet A. Punën e bën rreshti return chr((ord(ch) - base + shift) % 26 + base): Z është pozicioni 25, plus 1 bën 26, dhe % 26 e kthen atë sërish në 0, që është A.
2. Të ecësh 3 hapa mbrapsht në një rreth me 26 shkronja të çon te e njëjta shkronjë si të ecësh 23 hapa përpara, dhe % 26 i Python-it e kthen -3 në 23 për ne, kështu që një funksion i vetëm mbulon të dy drejtimet.
3. Po. Ka vetëm 25 zhvendosje të dobishme, ndaj i provon një nga një dhe ndalon kur teksti lexohet si fjalë (fusha e lojës bën pikërisht këtë). Një sekret që bie me 25 hamendje nuk është aspak i sigurt.