Kryptoanalys.sagews

Kryptering 1

Kryptoanalys

load('../kryptering.sage')

*** Pythonbibliotek för kryptering, version 2017 ***

Vi läser in en fil som innehåller det första stycket ur boken Mästaren och Margarita av Michail Bulgakov.

load('Bulgakov.sage')
print Bulgakov

isolnedgångenenvarmvårdaguppenbaradesigtvåherrarvidbiskopdammarnadenenevaromkrungfyrtioårgammalhanvarifördengråsommarkostymhanvarlitentillväxtenvämåendeochmörkhårigochflintskallighankramadesinkorrektahattihandenochhansvälrakadeansiktepryddesavsvartahornbågadeglasögoniövernaturligstorlekdenandrevarenbredaxladrödlockigungmanhansrutigakepsvartillbakaskjuteninackenochhangickkläddirutigsportskjortavitasäckigabyxorochsvartagymnastikskor

Med funktionen replace kan man ersätta alla förekomster av en delsträng med en annan. Om vi t.ex. vill ersätta alla a med ö skriver vi följande.

ny_Bulgakov = Bulgakov.replace(u'a', u'Ö')
print ny_Bulgakov

isolnedgångenenvÖrmvårdÖguppenbÖrÖdesigtvåherrÖrvidbiskopdÖmmÖrnÖdenenevÖromkrungfyrtioårgÖmmÖlhÖnvÖrifördengråsommÖrkostymhÖnvÖrlitentillväxtenvämåendeochmörkhårigochflintskÖllighÖnkrÖmÖdesinkorrektÖhÖttihÖndenochhÖnsvälrÖkÖdeÖnsiktepryddesÖvsvÖrtÖhornbågÖdeglÖsögoniövernÖturligstorlekdenÖndrevÖrenbredÖxlÖdrödlockigungmÖnhÖnsrutigÖkepsvÖrtillbÖkÖskjuteninÖckenochhÖngickkläddirutigsportskjortÖvitÖsäckigÖbyxorochsvÖrtÖgymnÖstikskor

Vi kan utnyttja att gemener och versaler är olika tecken i en textsträng i Python.

Frekvensanalys

Frekvensanalys av monogram erhålls med funktionen monogramanalys. Resultatet kan presenteras antingen grafiskt med ett diagram, i tabellform eller som en lista. Alterantivet 'diagram' är förvalt. Funktionen kan hantera valfritt alfabet.

monogramanalys(Bulgakov)

Samma analys fast i tabellform:

monogramanalys(Bulgakov, typ = 'tabell')

a : 51 b : 6 c : 9 d : 21 e : 30 f : 3 g : 20 h : 16 i : 26 j : 2 k : 22 l : 17 m : 14 n : 36 o : 20 p : 6 q : 0 r : 40 s : 22 t : 23 u : 7 v : 17 x : 3 y : 5 z : 0 å : 8 ä : 5 ö : 5

Vi kan även få resultatet som en lista, där det till varje bokstav hör dess frekvens.

monogramanalys(Bulgakov, typ = 'lista')

{u'\xf6': 5, u'\xe5': 8, u'\xe4': 5, u'a': 51, u'c': 9, u'b': 6, u'e': 30, u'd': 21, u'g': 20, u'f': 3, u'i': 26, u'h': 16, u'k': 22, u'j': 2, u'm': 14, u'l': 17, u'o': 20, u'n': 36, u'q': 0, u'p': 6, u's': 22, u'r': 40, u'u': 7, u't': 23, u'v': 17, u'y': 5, u'x': 3, u'z': 0}

Frekvensanalys av bigram och trigram görs med funktionerna bigramanalys och trigramanalys. Dessa funktioner returnerar de $n$ mest frekventa bi- respektive trigrammen, där $n = 25$ är förvalt värde.

bigramanalys(Bulgakov, 10)

en : 14 ar : 12 an : 10 de : 10 ig : 8 va : 8 ha : 8 or : 7 ti : 7 oc : 6

Tips: Med funktionen count räknar man antal förekomster av en delsträng i en textsträng.

Råstyrkeattack på förskjutningskrypto

Antag att kryptogrammet zaiqnlz har erhållits med ett förskjutningskyrpto. Eftersom antal nycklar är få kan vi testa samtliga.

kryptogram = u'zaiqnlz'
for k in [1..27] :
    mkt = affint_krypto(kryptogram, 1, -k)  # möjlig klartext
    print 'k =', repr(k).rjust(2), ':', mkt

k = 1 : yöhpmky k = 2 : xägoljx k = 3 : våfnkiv k = 4 : uzemjhu k = 5 : tydligt k = 6 : sxckhfs k = 7 : rvbjger k = 8 : quaifdq k = 9 : ptöhecp k = 10 : osägdbo k = 11 : nråfcan k = 12 : mqzeböm k = 13 : lpydaäl k = 14 : koxcöåk k = 15 : jnvbäzj k = 16 : imuaåyi k = 17 : hltözxh k = 18 : gksäyvg k = 19 : fjråxuf k = 20 : eiqzvte k = 21 : dhpyusd k = 22 : cgoxtrc k = 23 : bfnvsqb k = 24 : aemurpa k = 25 : ödltqoö k = 26 : äckspnä k = 27 : åbjromå

Vi ser att för $k = 5$ ger kryptering med $-k$ en läsbar klartext.

Känd klartext-attack på affint krypto

Antag att vi vet att klartexten yl ger kryptogrammet jr med ett affint krypto. Vad är nyckeln? Först kodar vi klartext och kryptogram till heltal.

text_till_heltal(u'yljr')

[23, 11, 9, 17]

Vi söker $a$ och $b$ i krypteringsfunktionen $E(x) = ax + b$. Enligt förutsättningarna är $$E(23) \equiv 11 \pmod{28} \quad\text{och}\quad E(11) \equiv 17 \pmod{28},$$ vilket är ekvivalent med $$23a + b \equiv 11 \pmod{28} \quad\text{och}\quad 11a + b \equiv 17 \pmod{28}.$$ Båda kongruenserna ska vara uppfyllda samtidigt, d.v.s. vi ska betrakta dem som ett kongruenssystem på formen ParseError: KaTeX parse error: Unknown column alignment: @ at position 36: … \begin{array}{@̲{}l@{}} … Med funktionen solve_mod kan vi finna alla icke-kongruenta lösningar.

a, b = var('a b')
solve_mod([23 * a + b == 9, 11 * a + b == 17], 28)

[(4, 1), (25, 22), (11, 8), (18, 15)]

Nyckeln $(a, b)$ kan alltså vara någon av $(4, 1)$, $(11, 8)$, $(18, 15)$ eller $(25, 22)$. Vi testar en av dem:

print affint_krypto(u'yl', 4, 1)

jr

De tre andra lösningarna ger exakt samma kryptogram. Vi har fyra alternativ och vi behöver därför veta mer för att kunna utesluta tre av dem.

Attack på Vigenèrekryptot

För att bestämma samtliga positioner av en delsträng i en textsträng kan man använda funktionen BabbageKasiski. På vilka positioner finns var i textsträngvariabeln Bulgakov?

BabbageKasiski(Bulgakov, 'var')

[15, 71, 98, 126, 244, 295, 338, 416]

Vi räknar antal överensstämmelser då vi förskjuter en textsträng $s$ steg med funktionen Friedman. Antal överensstämmelser då Bulgakov förskjuts $4$ steg:

Friedman(Bulgakov, 4)

20

Med funktionen splittra_text delar man upp en textsträng i $n$ delsträngar, där den $i$:te delsträngen är de tecken vars position i den ursprungliga textsträngen är $kn + i$, där $k$ är ett icke-negativt heltal. Plocka ut var sjunde bokstav Bulgakov:

delstr = splittra_text(Bulgakov, 7)
for i in range(7) :
    print u'Delsträng', i, ':', delstr[i]

Delsträng 0 : ignreehipnertmvdosvnxåhrllksetnsakdangnasderdkauplknccipoaacat Delsträng 1 : såvdnseddavuimaemtattemiilrikiovdterblitteverintsljahkrorsbhgi Delsträng 2 : onaabirbadanoarnmyrienögnianthcäeeståaöuonadöghivbuchkurtäysyk Delsträng 3 : lgrgagrimergåligamllndrotgmkaahlapaagsvrraraduagaatkalttacxvms Delsträng 4 : nemurtasmnofrhfrrhilvekcshaohnhrnrvhaöellnexlnnarkeenäisvkoank Delsträng 5 : envpavrkaemygaöåkatväohhkadradaasysodgriednlogsktanngdgkiirrao Delsträng 6 : deåpdåvornkranrsoneämcåfanertenkidvreongkrbacmreisioidsjtgotsr

Du kan läsa texten ''kolumn för kolumn''. Med monogramanalys kan man analyserar respektive delsträng.

Differentiell kryptoanalys

UNDER KONSTRUKTION