Bitit, tavut ja binäärioperaatiot¶

Tämä osio on idealtaan samanlainen kuin sitä edeltävä Python-tutoriaali. Osiossa esitellään mitä ovat bitit, tavut ja millaisia ovat binäärioperaatiot.

Voit hyödyntää tätä kurssin sivua myöhemmin kun tarkastelet heksadesimaalilukuja tai bittijonoja.

Tietokone käsittelee kaiken informaation bitteinä:

Sekä salattu että salaamaton tietokoneen informaatio koostuu biteistä.
Avaimet, joita salaimissa käytetään, ovat myös bittejä.
Kryptografinen salain, jota käytämme tietokoneissa, koostuu biteistä.

Bittejä ei käytetä tällä kurssilla syvällisesti, mutta tässä luvussa annetut pohjatiedot auttavat ymmärtämään, mitä bitit ovat ja miten niitä voidaan ilmaista heksadesimaalilukuina, sanoina ja numeroarvoina. Syynä bittien esittelyyn kurssin yhteydessä on se, että salattua informaatiota ei useimmiten voi esittää muuten kuin bitteinä 0 tai 1, tai heksadesimaalisena arvoina 0x0, 0x1, … 0x9 ja 0xA … 0xF.

Bitit, tavut ja sanat¶

Bitit¶

Bitit ovat ykkösiä tai nollia. Matematiikan keinoin bitit on kuvattavissa seuraavasti:

\[\textrm{bit} \in \{0,1\}\]

Kun bitit muodostavat bittijonoja, on bittien järjestyksellä väliä. Käytämme yksinkertaisuuden vuoksi seuraavaa notaatiota:

Bittijonon vasemmanpuoleisin bitti on eniten merkitsevä bitti eli most significant bit. \(\underline{\textbf{0}}1101001\) .
Bittijonon oikeanpuoleisin bitti on vähiten merkitsevä bitti eli least significant bit. \(0110100 \underline{\textbf{1}}\) .

Alla on taulukko, jossa esitellään, miten kymmenjärjestelmän lukuja nollasta 255:een kuvataan bittijonoina.

DEC	b’7 (MSB)	b’6	b’5	b’4	b’3	b’2	b’1	b’0 (LSB)
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	1
2	0	0	0	0	0	0	1	0
3	0	0	0	0	0	0	1	1
4	0	0	0	0	0	1	0	0
255	1	1	1	1	1	1	1	1
2-pow	\(2^7\)	\(2^6\)	\(2^5\)	\(2^4\)	\(2^3\)	\(2^2\)	\(2^1\)	\(2^0\)

Kukin bitti toimii kertoimena tietylle kakkosen potenssille.

Käytämme materiaalissa yhtenäistettyä merkintätapaa, jossa bitit tunnistaa merkkijonon alussa olevasta 0b-tunnisteessa. Tämä on myös Pythonissa käytetty bittien merkintätapa. Esimerkiksi bitti nolla merkitään 0b0 ja bitti yksi merkitään 0b1. Samoin jos esitämme useampia bittejä, merkkijono alkaa bittitunnisteella jota seuraa kaikki esitettävät bitit, esimerkiksi 0b01101100.

Seuraavassa esimerkissä esitellään miten bittijono 0b00010111 voidaan muuttaa kokonaisluvuksi:

\(0\cdot2^7 + 0\cdot2^6 + 0\cdot2^5 + 1\cdot2^4 + 0\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0\) eli:

\(0+0+0+16+0+4+2+1 = 23\)

Samalla tavalla voimme lähteä liikkeelle kymmenjärjestelmän luvusta 23 ja laskea ne kakkosen potenssit, jotka yhteen laskettuna tuottavat luvun 23. Kukin tarvittava kakkosen potenssi tuottaa bittijonoon 1:n sen merkitsevän bitin kohdalle, joka vastaa kyseistä kakkosen potenssia (ks. taulukon alin rivi). Muihin kohtiin bittijonossa tulee 0.

\(23 = 16 + 4 + 2 + 1 = 2^4 + 2^2 + 2^1 +2^0 = 10111_2\) eli luku 23 on binäärisenä 0b00010111.

Heksadesimaalinumerot¶

Alla oleva taulukko näyttää miten neljän bitin kuvio voidaan esittää heksadesimaalilukuna (HEX) ja kymmenjärjestelmän kokonaislukuina (DEC). Bitit ovat järjestyksessä merkitsevimmästä (MSB) bitistä vähiten merkitsevimpään (LSB) bittiin. Heksadesimaalilukuja merkitään etuliitteellä 0x. Heksa-luvut saavat arvoja nollasta 9:ään ja sen jälkeen vielä A:sta F:ään. Alla oleva taulukko näyttää miten luvut nollasta 15:een ilmaistaan bitteinä, heksadesimaalina ja normaaleina kymmenjärjestelmän numeroina.

b’3	b’2	b’1	b’0	HEX	DEC
0	0	0	0	0x0	0
0	0	0	1	0x1	1
0	0	1	0	0x2	2
0	0	1	1	0x3	3
0	1	0	0	0x4	4
0	1	0	1	0x5	5
0	1	1	0	0x6	6
0	1	1	1	0x7	7
1	0	0	0	0x8	8
1	0	0	1	0x9	9
1	0	1	0	0xA	10
1	0	1	1	0xB	11
1	1	0	0	0xC	12
1	1	0	1	0xD	13
1	1	1	0	0xE	14
1	1	1	1	0xF	15

Katsotaan taulukkoa:

Taulukon oikeasta laidasta voidaan katsoa kymmenjärjestelmän numero 9, jonka heksadesimaaliarvo on 0x9 ja vastaavasti se on bitteinä 0b1001.
Jos katsomme kymmenjärjestelmän lukua 11, se onkin heksadesimaalilla ilmaistuna 0xB ja binäärisenä 0b1011.

Heksadesimaalista voidaan siis siirtyä bittijonoon tai päinvastoin. Digitaalinen informaatio usein esitetään heksadesimaalisena koska digitaalisella datalla ei ole esimerkiksi vastaavuutta aakkoskirjaimissa.

Asiayhteydestä riippuen, voimme valita miten tieto esitetään. Esimerkiksi voimme merkitä jonkun arvon bittijonona 0b10100001, heksadesimaalisena 0xA1 tai desimaali lukuarvona 161. Näissä kaikissa on kyse samasta informaatiosta eri esitystavoilla.

Tietokoneen tavu eli 8 bittiä¶

Kahdeksan bittiä muodostaa tavun (engl. byte). Esimerkiksi kahdeksan bittiä 0b00010111 muodostavat yhden 8-bittisen tavun. Tavun bitit voidaan ilmaista joko yksittäisinä bitteinä, heksadesimaalinumeroina tai kymmenjärjestelmän lukuna.

Bitteinä: 0b00010111
Heksana: 0x17
Kymmenjärjestelmän luku: 23

Tarvitsemme yhden 8-bittisen tavun kuvaamiseen kaksi heksadesimaalinumeroa, koska heksadesimaalinumerot muodostetaan neljästä bitistä.

Digitaalinen sana¶

Yhdistelemällä tavuja saamme digitaalisia sanoja kuten esimerkiksi 0xABCD. Tästä heksadesimaaliluvusta voidaan tuottaa bittijono purkamalla neljän bitin heksadesimaaliarvot biteiksi järjestyksessä.

HEXa	A	B	C	D
Bitit	1010	1011	1100	1101

Tavujen järjestys digitaalisessa sanassa ja mahdollisesti jopa bittien MSB - LSB järjestys voi vaihdella riippuen tietokoneen prosessorin tai käytetyn datan muodon protokollasta. Jos esimerkiksi tallennat digitaalisen sanan 0xABCD tietokoneen muistiin, voi sana olla muistista luettaessa järjestyksessä 0xD 0xC 0xB 0xA tai 0xA 0xB 0xC 0xD.

Binäärioperaatiot¶

Tietokone käsittelee dataa bittitasolla. Näin ollen myös siis kryptografian menetelmät toteutetaan bittitasolla. Bittitason operaatioita ovat binääriset AND, OR, NOT ja XOR -operaatiot.

Tällä luennolla esitellään vain XOR. Voit hakea verkosta tietoa miten muut binäärioperaatiot toimivat esimerkiksi hakusanalla AND-portti.

XOR, eXclusive OR (\(\mathrm{symboli}\ \oplus\))¶

Ehdoton TAI (XOR) -operaatiota käytetään kryptografiassa. XOR operaatiossa vertaillaan kahta bittiä.

Biteittäinen XOR tuottaa ’1’ jos vain toinen verrattavista biteistä on ’1’.

Jos bitit ovat samat, eli esimerkiksi ensimmäinen vertailtava bitti on 0 ja toinen vertailtava bitti on myös 0, tuottaa XOR -operaatio tulokseksi arvon 0. Sama tulos tulee jos kummankin vertailtavan bitin arvo on 1.
Jos taas vertailtavilla biteillä on eri arvo, eli esimerkiksi ensimmäisen vertailtavan bitin arvo on 0 ja toisen vertailtavan bitti arvo olisi 1, tuottaa XOR -operaatio tulokseksi arvon 1.

Binäärioperaatioita kuvataan totuustaululla. Totuustaulussa on esitelty toiminnan kannalta oleelliset bitit sekä operaation tulos.

XOR-operaation totuustaulu on seuraava:

b_1	b_2	XOR
0	0	0
0	1	1
1	0	1
1	1	0

Totuustaulusta nähdään sama kuin aiemmin tekstissä kuvattiin, mutta paljon tiiviimmin. Totuustaulussa kuvataan minkä tuloksen XOR-portti antaa vertailtavien bittien b_1 ja b_2 arvojen mukaisesti. Jos vertailtavien bittien arvot ovat erisuuret, palauttaa XOR-funktio arvon 1. Muutoin XOR-funktio palauttaa arvon 0.

Alla on esimerkki miten toimii biteittäinen XOR-operaatio kahden tavun V ja U tapauksessa. Muuttujalle V annetaan arvo 0xC9 ja U:n arvoksi asetetaan 0x78. XOR-funktio laskee biteittäin tuloksen, joka on 0xB1.

V = b’11001001 (0xC9)
U = b’01111000 (0x78)
\(\oplus\) b’10110001 (0xB1):

Seuraava taulukko näyttää biteittäin tapahtuvan XOR-operaation.

Muuttuja	b’7	b’6	b’5	b’4	b’3	b’2	b’1	b’0
V	1	1	0	0	1	0	0	1
U	0	1	1	1	1	0	0	0
V \(\oplus\) U	1	0	1	1	0	0	0	1

Pythonissa XOR-operaattori on ^. Alla oleva esimerkki näyttää, miten XOR operaattoria voi käyttää koodissa muuttujilla V ja U.

Inactive

from numpy import binary_repr

# Luodaan muuttujat V ja U bittijonoina
V = 0b11001001
U = 0b01111000

# Tulostetaan muuttujien V ja U arvot bitteinä, heksadesimaalilukuna sekä desimaalilukuna (kymmenjärjestelmä)
print("Binäärinen  V:", bin(V))
print("HEXa        V:", hex(V))
print("Desimaali   V:", V)
print("Binäärinen  U: 0b"+binary_repr(U, 8))
print("HEXa        U:", hex(U))
print("Desimaali   U:", int(U))

# XOR laskenta tapahtuu biteittäin
print("Lasketaan V xor U")
print("Binääri V             ", bin(V))
print("Binääri U              0b"+binary_repr(U, 8))
print("XOR: Binääri    V ^ U  0b"+binary_repr(V ^ U, 8))
print("XOR: HEXa       V ^ U ", hex(V ^ U))
print("XOR: Desimaali  V ^ U ", int(V ^ U))

Voit palata tähän osioon myöhemmin, jos haluat kerrata mitä bitit ja heksadesimaaliluvut tarkoittivatkaan.

Lopuksi¶

Ensimmäinen opetusmoduuli on sisältänyt vielä varsin vähän kryptografiaa. Olemme pohjustaneet kurssia esittelemällä oppimisympäristöä, Python-ohjelmointikieltä ja biteillä operointia tehdäksemme varsinaisesta kryptografian opiskelusta helpompaa. Tämän moduulin sisältöä kannattaa käydä välillä vilkaisemassa, jos Python-esimerkit tuntuvat haastavilta.

Seuraava opetusmoduuli käsittelee kryptografian käsitteitä.