Asymmetriska_kryptosystem.sagews

Kryptering 1

Asymmetriska kryptosystem

load('../kryptering.sage')

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

Kodning och indelning i block

Låt oss studera ett exempel där vi kodar en klartext enligt reglerna i kursen.

m = text_till_heltal(u'stormvarning')
m

[18, 19, 14, 17, 12, 21, 0, 17, 13, 8, 13, 6]

Efter att vi kodat varje bokstav till motsvarande heltal adderar vi $1$ till varje heltal.

m = [x + 1 for x in m]
m

[19, 20, 15, 18, 13, 22, 1, 18, 14, 9, 14, 7]

För att sätta samman heltalen i listan till block av säg längd $3$, där varje heltal bettraktas som ett tvåsiffrigt heltal skriver vi följande.

heltal_till_block(m, 3)

[192015, 181322, 11814, 91407]

Eftersom textsträngen stormvarning består av $12$ bokstäver behövs inga utfyllnadstecken. Med istället blocklängden $5$ läggs det autormatiskt till tre stycken x i slutet av sista blocket.

heltal_till_block(m, 5)

[1920151813, 2201181409, 1407232323]

Vi kan med parametern t välja ett annat utfyllnadstecken.

b = heltal_till_block(m, 5, t = 15)
b

[1920151813, 2201181409, 1407151515]

Med funktionen block_till_heltal splittrar vi blocken tillbaka till en lista av heltal.

t = block_till_heltal(b, 5)
t

[19, 20, 15, 18, 13, 22, 1, 18, 14, 9, 14, 7, 15, 15, 15]

Vid konvertering från heltal till motsvarande bokstav subtraherar vi först $1$.

[x - 1 for x in t]

[18, 19, 14, 17, 12, 21, 0, 17, 13, 8, 13, 6, 14, 14, 14]

print heltal_till_text([x - 1 for x in t])

stormvarningooo

Vi kan även koda enligt ASCII.

m = u'Vem är du?'
m = map(ord, m)
m

[86, 101, 109, 32, 228, 114, 32, 100, 117, 63]

Eftersom varje tecken kodas med ett element ur $\mathbb{Z}_{256}$ så ska vi betrakta varje heltal i listan som ett tresiffrigt heltal. Med ett tredje argument till text_till_block styr vi antal siffror i varje heltal. Med blocklängden $4$ får vi följande.

heltal_till_block(m, 4, 3, 88)

[86101109032, 228114032100, 117063088088]

Med t = 88 använder vi X som utfyllnadstecken. Att konverterar från block till tecken då vi utgår ASCII sker på liknande sätt som ovan.

b = [72101109108105, 103116033033090]

Först splittrar vi blocken till en lista av heltal. Eftersom blocken består av $14$ respektive $15$ siffror och varje varje heltal ska betraktas som ett tresiffrigt tal, så är blocklängen $5$.

m = block_till_heltal(b, 5, 3)
m

[72, 101, 109, 108, 105, 103, 116, 33, 33, 90]

Med funktionen chr konverterar man ett heltal till motsvarande tecken enligt ASCII.

t = map(chr, m)
t

['H', 'e', 'm', 'l', 'i', 'g', 't', '!', '!', 'Z']

Sammsättning av textsträngar fås med join.

print ''.join(t)

Hemligt!!Z

Här har troligtvis ett Z använts som utfyllnadstecken.

Ett mer realistiskt exempel

En textsträng över flera rader omges av tre tumtecken. Prefixet u markerar att textsrängen ska kodas enligt Unicode. Man kan även konvertera varje tecken till åtta bitar, d.v.s. texten bildar en följd av ettor och nollor. Delar vi upp dem i block om t.ex. 1024 bitar motsvarar det heltal i mängden $\{0, 1, \ldots, 2^{1024}-1\}$.

klartext = u"""Lägesrapport från Östberlin
Jag har infiltrerat utrikersdepartementet och
kommer inom kort installera en dold mikrofon
i utrikersministerna kontor. Men jag minns inte
vem jag är. Kan du vara snäll ock skicka mig
min personakt. Vidare har jag hittat flera
konstiga tecken på mitt tangentbord, som t.ex.

               @ $ + & ) - ?

Kan någon förklara för mig vad de betyder?

Hälsningar Jason Bourne"""

m = text_till_bitblock(klartext)
m       # skriv ut listan av block
len(m)  # antal block

[80331722605094088462724523336920716688986834467279426761060728705536288027007976736678776296640149188737353049362784662589794264429100945336944608246353408309019739689260809135330007274936231901061544590424146335834405618776800367633260036010526579498420889083776742505042768967156142824782413718604881585228, 75166430018035719785820446170616209739049368360906662370545051526090548038504225505393289929063039382402449166856542965401389051383922818232312184692527447041889902752282561704276081162582054001171395787880600281673289422726993396022457377221935731985827916061901519008636605739672537118006908994911914782067, 77533831892915995508147654213433711060445818670943204405169258451011494310419618399209828950569315199026847779442978815888778106777456291204889559439158424608384932378765983313153083844545333409146238658540093391671919901978110410117085080212186495664612942941983794616517126229284457395364829189117368823407, 134825501727537943008942733738028196199] 4

Dessa heltal kan sedan krypteras t.ex. med RSA (se nästa avsnitt). Efter dekryptering konverterar man enkelt tillbaka till klartext:

print bitblock_till_text(m)  # använd print för lättläst utskrift

Lägesrapport från Östberlin Jag har infiltrerat utrikersdepartementet och kommer inom kort installera en dold mikrofon i utrikersministerna kontor. Men jag minns inte vem jag är. Kan du vara snäll ock skicka mig min personakt. Vidare har jag hittat flera konstiga tecken på mitt tangentbord, som t.ex. @ $ + & ) - ? Kan någon förklara för mig vad de betyder? Hälsningar Jason Bourne

RSA

Låt oss skapa nycklarna till ett RSA-krypto.

p = nth_prime(96)
q = nth_prime(143)
n = p * q
e = 775
gcd(e, euler_phi(n))  # kontroll att e är ett okej val

1

Vi söker ett heltal $d$ sådant att $d \equiv e^{-1} \pmod{\phi(n)}$.

d = power_mod(e, -1, euler_phi(n))
d

104359

Den publika nyckeln $(n, e)$:

n, e

(413969, 775)

Den privata nyckeln $(p, q, d)$:

p, q, d

(503, 823, 104359)

Heltalet $n = 413969$ tillåter block av längd $2$ då vi kodar varje tecken enligt ASCII.

klartext = [ord(t) for t in u'Vadå - jag dyster?']
klartext = heltal_till_block(klartext, 2, 3, 88)
klartext

[86097, 100229, 32045, 32106, 97103, 32100, 121115, 116101, 114063]

Kryptering ger följande kryptogram.

kryptogram = RSA(klartext, n, e)
kryptogram

[140843, 326338, 263610, 95472, 28201, 4113, 410478, 62461, 72285]

Dekryptering fås med samma funktion, fast med den privata nyckeln som indata.

RSA(kryptogram, n, d)

[86097, 100229, 32045, 32106, 97103, 32100, 121115, 116101, 114063]

Notera att vi inte kan koda kryptoggrammet tillbaka till tecken enligt ASCII eftersom vi erhållit flera tresiffriga heltal som är större än $255$. Se föregående avsnitt om hur man konvertera tillbaka till en läsbar klartext.

Cayley-Pursers algoritm

UNDER KONSTRUKTION

ElGamals kryptosystem baserat på primitva rötter

Vi börjar med att konstruera nycklarna. Först väljer vi ett primtal.

p = nth_prime(55555)
Zp = Zmod(p)
p

686671

Här betecknar Zp mängden $\mathbb{Z}_p$.

Zp

Ring of integers modulo 686671

Vi behöver en primitiv rot modulo $p$.

h = primitive_root(p)
h

3

Med denna kan vi genererar en mer intressant primitiv rot genom att välja ett heltal $k$ som är relativt prima med $\phi(p) = p - 1$ och därfter bestämma $g \equiv h^k \pmod{p}$.

k = 80251
gcd(k, p - 1)

1

g = power_mod(h, k, p)
g

474194

Den multiplikaitva ordningen av en primitiv rot modulo $p$ är $\phi(p)$.

Zp(g).multiplicative_order() == euler_phi(p)

True

Det är nu dags att välja den privata nyckeln $a$ och bestämma $b \equiv g^a \pmod{p}$.

a = 702313
b = power_mod(g, a, p)
b

189349

Vi använder härnäst den publika nyckeln $(p, g, b)$ för att kryptera samma klartext som i avsnittet om RSA.

klartext = [ord(t) for t in u'Vadå - jag dyster?']
klartext = heltal_till_block(klartext, 2, 3, 88)
kryptogram = ElGamal(klartext, [p, g, b])
kryptogram

[(611440, 643086), (294276, 189136), (486910, 335241), (122517, 221304), (646888, 326368), (60220, 81885), (112822, 118594), (239399, 573766), (155626, 98321)]

Mer lättläst utskrft:

for rt in kryptogram :
    print rt

(611440, 643086) (294276, 189136) (486910, 335241) (122517, 221304) (646888, 326368) (60220, 81885) (112822, 118594) (239399, 573766) (155626, 98321)

Vi kan välja egna slumptal, t.ex. med Lehmers slumptalsgenerator.

k = Lehmer(60051, 7012, 892, p - 2, len(klartext))
ElGamal(klartext, [p, g, b], k)

[(426297, 494625), (379670, 582671), (246321, 82942), (102978, 2915), (488555, 512249), (545466, 27256), (528333, 115900), (532870, 223178), (342277, 169079)]

Vid dekryptering ska vi använda den privata nyckeln istället.

m = ElGamal(kryptogram, [p, g, a], metod = 'dekryptera')
m

[86097, 100229, 32045, 32106, 97103, 32100, 121115, 116101, 114063]

Därefter är det bara att konvertera blocken till en textsträng.

t = block_till_heltal(m, 2, 3)
t = map(unichr, t)
print ''.join(t)

Vadå - jag dyster?

Eftersom klartexten innehåller bokstaven å använder vi unichr istället för chr.