Path: Kryptering / 1 / Symmetriska_kryptosystem.sagews

Views: ³⁷¹⁵

Kryptering 1

Symmetriska kryptosystem

load('../kryptering.sage')

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

Vi deklarerar en klartext till de exempel nedan som illusterar olika funktioner.

klartext = u'dettaärenkortklartext'

Affint krypto

Om t.ex. nyckeln är $(a, b) = (9, 20)$ får vi nedanstående kryptogram.

kryptogram = affint_krypto(klartext, 9, 20)
print kryptogram

tayyucfaåägfyähufyaxy

Vi kan givetvis direkt ange en klartext och använda ett annat alfabet.

print affint_krypto(u'rollingstones', 11, 4, Aeng)

jcvvorsufcrwu

Om $a = 1$ , så representerar funktionen även förskjutningskrypton.

Samma funktion används även vid dekryptering, fast med dekrypteringsnyckeln som indata. Om $(a, b)$ är krypteringsnyckeln, så är $(c, d) = (a^{-1}, -a^{-1} b)$

a, b = 9, 20
c = power_mod(a, -1, 28)  # multiplikativ invers till a = 9
d = (-c * b) % 28
c, d

(25, 4)

Vi kan nu dekryptera kryptogrammet.

print affint_krypto(kryptogram, c, d)

dettaärenkortklartext

Vigenèrekrypto

Om t.ex. nyckelordet är hemligt så får vi följande resultat.

kryptogram = Vigenerekrypto(klartext, u'hemligt')
print kryptogram

kidcieilrxåååbsebcmak

För att bestämma motsvarande dekrypteringsnyckel kan vi först konvertera nyckelordet till en lista av heltal, därefter bestämma motsvarande additiva invers modulo $m$ till respektive heltal och sedan konvertera tillbaka till en textsträng.

nyckel = u'hemligt'
k = text_till_heltal(nyckel)
k

[7, 4, 12, 11, 8, 6, 19]

k = [-x % 28 for x in k]  # bestäm additiv invers för svenska alfabetet
k

[21, 24, 16, 17, 20, 22, 9]

d_nyckel = heltal_till_text(k)  # dekrypteringsnyckeln
print d_nyckel

vzqruxj

Kryptering-s och dekrypteringsfunktionen är densamma. Det som skiljer är att vi använder olika nycklar.

print Vigenerekrypto(kryptogram, d_nyckel)  # dekryptering

dettaärenkortklartext

Autokey

Detta krypto är en variant av Vigenèrkrypto. Nyckeln till detta krypto ska vara en bokstav, som används för att kryptera första bokstave i klartexten. Därefter används föregående bokstav i klartexten som nyckel.

kryptogram = Autokey(klartext, 'h')
print kryptogram

khyktäpvryzdibvlriyän

Med parametern metod styr man om man vill kryptera eller dekryptera. Förvalt värde är 'kryptera'.

print Autokey(kryptogram, 'h', metod = 'dekryptera')

dettaärenkortklartext

Vernamchiffer

Detta kryptosystem är egentligen inget annat än en variant av Vigenèrekryptot, fast med lika lång nyckel som klartexten. För att slumpmässigt välja en nyckel kan vi med pseudoslumptalsgenerator välja bokstäver ur aktuellt alfabet.

print Asve[randint(0, len(Asve) - 1)]

ä

Genom att upperpa denna procedur så många gånger som antalet bokstäver i klartexten får vi en lista av slumpmässigt valda bokstäver. Denna lista sätter vi samma ntill en textsträng med funktionen join.

nyckel = ''.join([Asve[randint(0, len(Asve) - 1)] for i in range(len(klartext))])
print nyckel

lzcbxalzeöiåvcskzbqkp

Vi kan nu kryptera klartexten med Vernamchiffret.

kryptogram = Vernamchiffer(klartext, nyckel)
print kryptogram

oavuxäaarjxommbknuueg

Dekryptering är enkelt eftersom krypteringsfunktionen bestämmer dekrypteringsnyckeln.

print Vernamchiffer(kryptogram, nyckel, metod = 'dekryptera')

dettaärenkortklartext

Vi kan koda klartexten binärt, t.ex. med åtta bitars ASCII. Först konverterar vi varje tecken i textsträngen till ett heltal i basen 10.

M = map(ord, u'Detta är hemligt!')
M

[68, 101, 116, 116, 97, 32, 228, 114, 32, 104, 101, 109, 108, 105, 103, 116, 33]

Därefter bestämmer vi den binära representationen av varje heltal med exakt åtta bitar vardera.

M = map(lambda x : ZZ(x).digits(base = 2, padto =8), M)
M  # notera att M är en lista av listor

[[0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 0, 1, 1, 0], [1, 0, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 0, 0]]

Härnäst plattar vi ut listan.

M = flatten(M)
M

[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0]

För att använda Vernamchiffer måste vi också konvertera listan till en textsträng, som sedan funktionen internt konverterar tillbaka till en lista av bitar. Med andra ord som att gå över ån efter vatten. Eftersom Vernamchiffret är så enkelt kan vi kryptera på egen hand. Vi behöver en nyckel av rätt längd.

K = [randint(0, 1) for i in range(len(M))]
K

[1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0]

Vid kryptering adderar vi klartexten i position $i$ med nyckeln i samma position.

C = []
for i in range(len(M)) :
    C.append((M[i] + K[i]) % 2)
C

[1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0]

Alternativ lösning 1: Vektoraddition över $\mathbb{Z}_2$ .

vector(Zmod(2), M) + vector(Zmod(2), K)

(1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0)

Alternativ lösning 2: Funktionalprogrammering.

[(m + k) % 2 for (m, k) in zip(M, K)]

[1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0]

Kryptogrammet som en textsträng:

print ''.join(map(str, C))

1011110111111100111101001010110101101011011111101101010011010001110111000100011011011001101100001010001111101100101011101010000110111010

Dekryptering fås här genom att addera nyckeln en gång till.

M = []
for i in range(len(C)) :
    M.append((C[i] + K[i]) % 2)
M

[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0]

För att koda tillbaka till läsbar text måste vi först dela upp listan i dellistor med åtta bitar vardera.

M = [M[i:i+8] for i in range(0, len(M), 8)]
M

[[0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 0, 1, 1, 0], [1, 0, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 0, 0]]

Varje dellista ska vi sedan konverterar till en heltal i baseb 10.

M = map(lambda x : ZZ(x, base = 2), M)
M

[68, 101, 116, 116, 97, 32, 228, 114, 32, 104, 101, 109, 108, 105, 103, 116, 33]

Till sist kan vi koda varje heltal till motsvarande bokstav och sätta samman dem till en textsträng.

print ''.join(map(unichr, M))

Detta är hemligt!

Enigma

I kryptering.sage är Enigma I, d.v.s. den version som tyska armén och flygvapnet använde under andra världskriget. Konfigurationen av kopplingstavlan specificeras som en lista av par $(x, y)$ . Det finns fem rotorer att välja mellan, vilka betecknas I, II, III, IV och V. Vilka tre rotorer och i vilken ordning deklareras med en lista. Startpositionen för de tre rotorerna anges med en textsträng av längd. Här används versaler för klartext, kryptogram och nycklar.

Exempel på hur krypteringsnyckeln till Enigma kan se ut:

k = [('A', 'K'), ('B', 'T'),('E', 'Q'), ('G', 'L')]
r = ['II', 'IV', 'I']
s = 'LYA'

Kryptering av en klartext:

m = 'THISISASECRET'
c = Enigma(m, k, r, s)
print c

HWGZXRRQJOZLX

Med samma nyckel dekrypterar man ett kryptogram.

print Enigma(c, k, r, s)

THISISASECRET

Hillkrypto

Låt $$ M

\begin{pmatrix} 3 & 7 & 17 & 11 \\ 21 & 2 & 5 & 24 \\ 6 & 22 & 13 & 19 \\ 10 & 5 & 27 & 1 \end{pmatrix}

$$ vara en krypteringsnyckel, d.v.s. blocklängden är $4$ . Vi deklarerar matrisen i Sage över mängden $\mathbb{Z}_{28}$ så att alla beräkningar sker modulo $28$ per automatik.

M = matrix(Zmod(28), [[ 3,  7, 17, 11],
                      [21,  2,  5, 24],
                      [ 6, 22, 13, 19],
                      [10,  5, 27, 1]])

Låt oss kontrollera att denna matris är lämpligt som krypteringsnyckel.

M.is_invertible()

True

Förvald krypteringsfunktion i Hillkrypto är $E(x) = Mx$ . Funktionen lägger automatiskt till utfyllnadstecken om så behövs och som standard används x.

kryptogram = Hillkrypto(klartext, M)
print kryptogram

fktfqälööaqxådmoxtxndpåb

Alternativt kan vi använda krypteringsfunktionen $E(x) = xM$ . Vi får förstås inte samma resultat som ovan.

print Hillkrypto(klartext, M, typ = 'H')

jlcgspgjpätrobtbkoxfpfdu

Dekrypteringsnyckeln är matrisinversen av till $M$ .

M_inv = M.inverse()
M_inv

[21  4 20 21]
[ 8  8 19  3]
[27  1 14  1]
[ 1  5 27  1]

Samma funktion används vid dekryptering.

print Hillkrypto(kryptogram, M_inv)

dettaärenkortklartextxxx

Notera att all aritmetik sker i $\mathbb{Z}_{28}$ . Om vi gör om matrisen $M$ så att Sage uppfattar den som en matris med element ur $\mathbb{Z}$ och därefter bestämmer dess invers, så får vi ett helt annat resultat.

matrix(ZZ, M).inverse()

[-12061/110503   3560/110503   2176/110503   5887/110503]
[ -8812/110503  -1980/110503   7481/110503   2313/110503]
[  5725/110503  -1021/110503  -2114/110503   1695/110503]
[ 10095/110503   1867/110503  -2087/110503  -5697/110503]

Data Encryption Standard

För att kunna kryptera en klartext med DES måste vi först konvertera det till en bitsträng som vi dela upp i block om 64 bitar.

# med tre citationstecken tillåts radbrytning i en textsträng
klartext = u'''Hej!
Fienden planerar ett illdåd nästa torsdag strax
efter förmiddagsfikat.
Hemliga hälsningar
Spion X-092'''
m = text_till_block64(klartext)

Antal block:

len(m)

14

Visa det första blocket:

m[0]

[0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0]

Vi behöver bestämma en nyckel.

K = [randint(0, 1) for i in range(64)]
print ''.join(map(str, K))

1010001100001000101011000111101110001001000110110100001110010111

För att kryptera flera block använder vi ECB_DES som krypterar varje block med samma nyckel oberoende av varandra, d.v.s. Electronic Codebook. Funktionen genererar de rundnycklar som behövs. Internt anropas funktionen DES.

c = ECB_DES(m, K)

Vi skriver ut kryptogrammet som bitsträngar.

for b in block64_till_text(c, typ = 'bin') :
    print b

1100100110110001100101010010010111100011110101111110100100011100
0010101111100110111110000010011010111111011100001100011110100110
0001101100011100000000111101000011000010111101111110111000101101
0011111111110000101000111010111111100110110100001000101111100011
1001001101110100110011001100100100001010111110100111011101011101
1011101011000111010010110011011110000100001100110001011010111110
0100011011100100110110111010101001100010100001110101101100010000
1010111110011101001100110001110010001101010110001000001100001110
1101010001100101011110001010110001110101000110101100101001101111
1100000101100111101100101010011111000110100010110111011000110110
1011000011010100000111100110111111111101010111110110000000100101
0001110101010111101111111010001010011010010010101111110010110111
1000100100011011010011011100001101100100000110110011110011101001
0001000011010001010100010001000110111100110011110100010011001011

Vi kan också konvertera varje block till hexadecimal representation.

for b in block64_till_text(c, typ = 'hex') :
    print b

938DA9A4C7EB9738
D4671F64FD0EE365
D838C00B43EF77B4
FC0FC5F5670BD1C7
C92E3393505FEEBA
5DE3D2EC21CC687D
6227DB5546E1DA08
F5B9CC38B11AC170
2BA61E35AE5853F6
83E64DE563D16E6C
0D2B78F6BFFA06A4
B8EAFD4559523FED
91D8B2C326D83C97
088B8A883DF322D3

Det går också bra att konverterar kryptogrammet till vanlig text. Fast det är mer intressant vid dekryptering.

print block64_till_text(c)

+xö¿ú¤¸êýEYR?íØ²Ã&Ø<=ó"ÓÑÇÉ.3P_îº]ãÒì!Ìh}b'ÛUFáõ¹Ì8±Áp+¦5®XSöæMåcÑnl

Dekryptering fås med samma funktionen.

m = ECB_DES(c, K, metod = 'dekryptering')
print block64_till_text(m)

Hej!
Fienden planerar ett illdåd nästa torsdag strax
efter förmiddagsfikat.
Hemliga hälsningar
Spion X-092      