Quantumcomputers en Cryptografie
Profielwerkstuk
14-12-2016
Arthur Rump
Praedinius Gymnasium

Ook beschikbaar als pdf.

1. Voorwoord

Voor u ligt het verslag van mijn profielwerkstuk over quantumcomputers en cryptografie. De keuze voor dit onderwerp vloeit voort enerzijds uit mijn persoonlijke interesse voor informatica, anderszijds uit het feit dat dit onderwerp een goede combinatie is van de vakken wiskunde en natuurkunde. Het idee van het profielwerkstuk is ook dat de leerling met een onderwerp aan de slag gaat wat hem aanspreekt en daarnaast een raakvlak heeft met twee gevolgde vakken, in mijn geval zijn dat wiskunde D en natuurkunde.

Quantumcomputers komen vaak in het nieuws en worden dan beschreven als mythische machines, die zo snel zijn in hun berekeningen dat de apparaten die nu in gebruik zijn haast een soort speelgoed worden. In bijna elk artikel wordt ook gesproken over de invloed van quantumcomputers op de hedendaagse cryptografie. De NSA zou bijvoorbeeld een grote belangstelling hebben voor quantumcomputers, omdat ze met een werkende quantumcomputer alle versleutelde gegevens ter wereld zouden kunnen lezen. Spoiler: werkende quantumcomputers bestaan en de NSA kan ook alles lezen zonder deze apparaten. Desalniettemin leek het mij interessant om te onderzoeken hoe een quantumcomputer nou echt werkt en waarom deze machines zoveel efficiënter zouden zijn bij het kraken van versleutelde informatie.

Minder relevant, maar ook interessant: de juiste spelling van ‘quantumcomputer’ is enigszins discutabel. De juiste Nederlandse spelling lijkt ‘kwantumcomputer’ te zijn, hier geeft Wikipedia ook duidelijk de voorkeur aan. De rest van het internet is echter meer verdeeld, zo worden bij bijvoorbeeld de NOS en NU.nl beide spellingen door elkaar gebruikt en op de website van het populair wetenschappelijk tijdschrift NewScientist is in de nieuwere artikelen de spelling ‘quantumcomputer’ te lezen. Ik heb in dit verslag gekozen voor de spelling ‘quantumcomputer’, met name omdat ik deze spelling mooier vind.

In dit verslag zal uiteraard een hoop wiskunde voorbij komen, maar ik heb geprobeerd het zo begrijpelijk mogelijk te houden. Voor zowel quantumcomputers als cryptografie is wiskunde nodig die niet onder de middelbareschoolwiskunde, met uitzondering van wiskunde D, valt. Van deze onderwerpen is in hoofdstuk 4 een samenvatting te vinden, als ook verwijzingen naar uitgebreidere uitleg. Ik hoop dat dit verslag hierdoor ook voor mensen die geen wiskunde D (gehad) hebben te begrijpen is.

Ten slotte wil ik nog van de gelegenheid gebruik maken om een aantal mensen te bedanken: Daan Leijen van Microsoft Research voor het maken van Madoko.net, ik moet er niet aan denken om alles zelf in $\mbox{\LaTeX}$ te schrijven; het IBM Quantum team voor het beschikbaar stellen van hun quantumcomputer aan de hele wereld, echt geweldig dat dit mogelijk is; en natuurlijk mijn begeleiders dhr. Septer en mevr. Stadermann, ik heb dan wel weinig gebruik van jullie gemaakt, toch bedankt!

Dan rest mij nu niets anders dan u veel plezier te wensen met het lezen van dit verslag.


- Arthur Rump

2. Samenvatting

Kan een quantumcomputer de hedendaagse cryptografie veel efficiënter kraken dan een normale computer?

De meest gebruikte cryptografie bestaat uit twee algoritmes: RSA en AES. Deze twee verschillen nogal van elkaar. RSA is een asymmetrisch algoritme, wat betekent dat de sleutel die gebruikt wordt om gegevens te versleutelen een andere is dan die gebruikt wordt voor het ontsleutelen. Belangrijk hierbij is dat ook als een van de sleutels bekend is, de andere niet makkelijk af te leiden mag zijn. In RSA is dit gerealiseerd met behulp van het feit dat het makkelijk is om twee priemgetallen te vermenigvuldigen, maar heel moeilijk om die twee priemgetallen te vinden als alleen de vermenigvuldiging bekend is.

AES is een bloksversleuteling en kan alleen blokken van 128 bits versleutelen. Dit gebeurt door meerdere keren een XOR uit te voeren tussen de sleutel en de data, waarbij intussen de bits ook nog systematisch door elkaar gehusseld worden. Wiskundig gezien is AES dus veel simpeler dan RSA, maar een volledige beschrijving kost wel meer tijd.

Quantumcomputers werken met qubits in plaats van gewone bits. Deze qubits kunnen 0, 1, of een superpositie van deze twee zijn. Een superpositie houdt in dat de qubit in een staat tussen 0 en 1 zweeft. Zodra er echter gemeten wordt in welke staat de qubit is, valt deze weer terug naar 0 of 1. Als alle qubits gemeten worden kan een quantumcomputer dus net zoveel informatie bevatten als een normale computer met hetzelfde aantal bits. In de tussenstappen, voor de meting, is er door de superposities wel meer ruimte, waardoor voor sommige problemen speciale quantumalgoritmes ontworpen kunnen worden, waarmee deze problemen efficiënter opgelost kunnen worden dan met een gewone computer.

Een voorbeeld hiervan is het algoritme van Shor voor het vinden van de priemfactoren van een getal. Dit quantumalgoritme is beduidend efficiënter dan het beste algoritme voor dit probleem op een gewone computer. Met dit algoritme is RSA dus veel efficiënter te kraken. Het record voor het algoritme van Shor ligt echter op 21, terwijl bij RSA in de praktijk natuurlijk veel grotere getallen worden gebruikt.

Voor AES is een efficiënter quantumalgoritme minder waarschijnlijk, omdat het maar een vrij simpel algoritme is. In de praktijk wordt de sleutel voor AES vaak versleuteld met RSA, dus als deze gekraakt is, kunnen de met AES versleutelde gegevens gewoon met de sleutel ontsleuteld worden.

3. Inleiding

Quantumcomputers en cryptografie. Twee begrippen die misschien niet iedreen kent, maar zeker een ervan is ontzettend belangrijk in onze maatschappij: cryptografie. Cryptografie houd zich bezig met het versleutelen van gegevens, opdat onbevoegde personen geen toegang hebben tot deze gegevens. Men staat er niet vaak bij stil, maar een groot deel van het internetverkeer is versleuteld, ieder WhatsApp-berichtje is versleuteld, evenals de meeste gegevens op een moderne smartphone. De tekst wordt als het ware omgezet in een geheimtaal voordat deze verstuurd wordt en alleen de bedoelde ontvanger is in staat de originele tekst weer uit de geheimtaal tevoorschijn te halen, althans, dat is de bedoeling. Door de eeuwen heen zijn er verscheidene cryptografische systeem in gebruik genomen en vervolgens weer afgeschaft, omdat buitenstaanders toch in staat waren om de gegevens te lezen. Dit brengt ons bij het tweede begrip: de quantumcomputer.

Het begrip quantumcomputer is misschien wel beter bekend, het komt regelmatig langs in het nieuws, maar wat het precies inhoudt is voor de meeste mensen een raadsel. In de meeste artikelen over quantumcomputers wordt ook gesproken over de mogelijkheid dat deze apparaten in staat zouden zijn om de cryptografie van vandaag te kraken en met een beetje geluk wordt er ook nog gespeculeerd over de grote impact op ons dagelijks leven die dat zou hebben. Dit leidt tot de hoofdvraag van dit onderzoek: kan een quantumcomputer de hedendaagse cryptografie veel efficiënter kraken dan een normale computer? Een moderne computer kan namelijk ook de hedendaagse cryptografie kraken, maar dat kost erg veel tijd, denk aan duizenden jaren.

Om deze vraag te beantwoorden moeten we weten hoe de meest gebruikte cryptografie werkt en hoe een quantumcomputer werkt. Deze vragen worden respectievelijk beantwoord in hoofdstuk 5 en hoofdstuk 6. In 6.7 kijken we nog naar het algoritme van Shor, dat de sleutel zou kunnen zijn voor het kraken van de basis van de hedendaagse cryptografie. Uiteindelijk kunnen we in hoofdstuk 7 een conclusie trekken.

4. Voorbereidende wiskunde

Bij het rekenen met quantumcomputers en cryptografie komt wiskunde kijken die misschien niet algemeen bekend verondersteld kan worden. Om ervoor te zorgen dat er later geen al te grote onduidelijkheden ontstaan, worden hier een aantal wiskundige concepten kort uitelegd.

4.1. Hexadecimale notatie

Gewone computers rekenen met bits, die een waarde 0 of 1 kunnen hebben. Omdat er dus weinig informatie in één bit kan worden opgeslagen, worden ze vaak samengevoegd in groepjes van acht: een byte. Een byte is te noteren als een serie van acht binaire cijfers: 00101010. Dit neemt echter veel ruimte in, dus wordt vaak een verkorte versie van twee hexadecimale cijfers, waarbij elk cijfer vier bits representeerd, zoals weergegeven in tabel 1. 00101010 is dus ook te schrijven als 2A.

Bits Hex Bits Hex Bits Hex Bits Hex
0000 0 0100 4 1000 8 1100 c
0001 1 0101 5 1001 9 1101 d
0010 2 0110 6 1010 a 1110 e
0011 3 0111 7 1011 b 1111 f

Tabel 1. Hexadecimale notatie

4.2. Vectoren

In een quantumcomputer is het vaak handig om de qubits als vectoren voor te stellen, maar om dat te doen is het handig om te weten wat vectoren inhouden. Een uitgebreide uitleg over dit onderwerp is bijvoorbeeld te vinden in [1], maar voor de volledigheid volgt hier een korte samenvatting.

Een vector is, simpel gezegd, een lijnstuk met een bepaalde richting, dat in een tweedimensionaal vlak gedefinieerd wordt door het verschil in de x- en y-richting tussen het begin en het eind van het lijnstuk. De vector in figuur 1 heeft bijvoorbeeld een verschil van $3-0=3$ in de x-richting en een verschil van $2-0=2$ in de y-richting, dus geven we deze vector aan met de volgende notatie: $\begin{bmatrix} 3 \\ 2 \end{bmatrix}$.

\begin{pspicture}(4,3)
  \psgrid[subgriddiv=0,gridcolor=gray](4,3)
  \psline{->}(0,0)(3,2)
\end{pspicture}

Figuur 1. De vector $\big[\begin{smallmatrix} 3 \\ 2 \end{smallmatrix}\big]$

4.2.1. Vectoren optellen

Een vector heeft geen vaste beginplaats, waardoor vectoren makkelijk opgeteld kunnen worden: door de ene vector met zijn beginpunt aan het eindpunt van de andere te ‘plakken’, is makkelijk te zien waar het resultaat uitkomt, zoals in figuur 2.

\begin{pspicture}(6,7)
  \psgrid[subgriddiv=0,gridcolor=gray](6,7)
  \psline{->}(0,0)(3,2)
  \psline{->}(3,2)(5,6)
  \psline[linestyle=dashed]{->}(0,0)(5,6)
\end{pspicture}

Figuur 2. $\big[\begin{smallmatrix} 3 \\ 2 \end{smallmatrix}\big] + \big[\begin{smallmatrix} 2 \\ 4 \end{smallmatrix}\big] = \big[\begin{smallmatrix} 5 \\ 6 \end{smallmatrix}\big]$

Voor het optellen van vectoren geldt dan de volgende regel:

(1)
\[\begin{bmatrix} a \\ b \end{bmatrix}
+
\begin{bmatrix} c \\ d \end{bmatrix}
=
\begin{bmatrix} a + c \\ b + d \end{bmatrix}
\]

4.2.2. Vectoren vermenigvuldigen met een getal

  \begin{pspicture}(0,-0.5)(2,2)
    \psgrid[subgriddiv=0,gridcolor=gray](2,2)
    \psline{->}(0,0)(1,1)
  \end{pspicture}
(a) Origineel
  \begin{pspicture}(0,-0.5)(2,2)
    \psgrid[subgriddiv=0,gridcolor=gray](2,2)
    \psline{->}(0,0)(2,2)
  \end{pspicture}
(b) Na vermenigvuldiging met 2

Figuur 3. Voor en na een vermenigvuldiging met 2

Bij het vermenigvuldigen van een vector met een getal $a$ blijft de richting van de vector gelijk en wordt de lengte $a$ keer zo groot, wat hetzelfde inhoudt als het $a$ keer zo groot worden van de afstand in de x-richting en het $a$ keer zo groot worden in de y-richting, zoals te zien is in figuur 3. Voor het vermenigvuldigen van een vector geldt dus:

(2)
\[a \begin{bmatrix} x \\ y \end{bmatrix}
=
\begin{bmatrix} ax \\ ay \end{bmatrix}
\]

4.2.3. Lineaire transformaties en matrices

  \begin{pspicture}(-1.2,-0.2)(2.2,5.2)
    \psgrid[subgriddiv=0,gridcolor=gray](-1.2,-0.2)(2.2,5.2)
    
    \psline[linestyle=dashed]{->}(0,0)(0,1)
    \psline[linestyle=dashed]{->}(0,0)(1,0)
    \psline{->}(0,0)(2,2)
  \end{pspicture}
(a) Origineel
  \begin{pspicture}(-1.2,-0.2)(2.2,5.2)
    \psgrid[subgriddiv=0,gridcolor=gray](-1.2,-0.2)(2.2,5.2)
    
    \psline[linestyle=dashed]{->}(0,0)(-1,2)
    \psline[linestyle=dashed]{->}(0,0)(1,0.5)
    \psline{->}(0,0)(0,5)
  \end{pspicture}
(b) Na transformatie

Figuur 4. Voor en na een transformatie

Een tweedimensionale lineaire transformatie is het beste voor te stellen als een vervorming van het gehele vlak waarbij het nulpunt niet verplaatst en de rasterlijnen parallel en gelijkmatig verdeeld blijven1. Zo'n transformatie is te beschrijven door bij te houden waar de basisvectoren $\big[\begin{smallmatrix} 0 \\ 1 \end{smallmatrix}\big]$ en $\big[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\big]$ na de transformatie terechtkomen. In figuur 4a is een vector $\big[\begin{smallmatrix} 2 \\ 2 \end{smallmatrix}\big]$ te zien, samen met de basisvectoren, die gestreept zijn weergegeven. In figuur 4b is een transformatie van deze vector weergegeven, die nu uitkomt als $\big[\begin{smallmatrix} 0 \\ 5 \end{smallmatrix}\big]$. De transformaties van de basisvectoren zijn ook weergegeven: $\big[\begin{smallmatrix} -1 \\ 2 \end{smallmatrix}\big]$ en $\big[\begin{smallmatrix} 1 \\ 0,5 \end{smallmatrix}\big]$. Deze vier getallen zijn genoeg om te beschrijven hoe deze transformatie eruit ziet voor elke vector. Elke vector is namelijk te schrijven als een combinatie van de twee basisvectoren:

(3)
\[\begin{bmatrix} x \\ y \end{bmatrix}
=
x \begin{bmatrix} 1 \\ 0 \end{bmatrix}
+
y \begin{bmatrix} 0 \\ 1 \end{bmatrix}
\]

Hierdoor kan ook voor elke vector berekend worden wat die na de transformatie is, als de nieuwe basisvectoren gegeven zijn:

(4)
\[\begin{bmatrix} x' \\ y' \end{bmatrix}
=
x \begin{bmatrix} -1 \\ 2 \end{bmatrix}
+
y \begin{bmatrix} 1 \\ 0,5 \end{bmatrix}
\]

Om een transformatie te beschrijven, worden deze nieuwe basisvectoren samen in een matrix geplaatst:

\[\begin{bmatrix}
  -1 & 1   \\
  2  & 0,5
\end{bmatrix}
\]

Om een transformatie, gegeven als een matrix, op een vector uit te voeren, geldt dan de volgende regel:

(5)
\[\begin{bmatrix} a & b \\ c & d \end{bmatrix}
\begin{bmatrix} x \\ y \end{bmatrix}
=
x \begin{bmatrix} a \\ c \end{bmatrix}
+
y \begin{bmatrix} b \\ d \end{bmatrix}
= 
\begin{bmatrix} xa + yb \\ xc + yd \end{bmatrix}
\]

4.2.4. Inproduct

Het inproduct van twee vectoren is als volgt te berkenen:

(6)
\[\begin{bmatrix} a \\ b \end{bmatrix} \cdot \begin{bmatrix} c \\ d \end{bmatrix} = 
\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} c \\ d \end{bmatrix} =
ac + bd
\]

Merk op dat de eerste vector in de tussenstap wordt geschreven als een 2×1 matrix, waarna deze transformatie wordt toegepast. Zie [Sanderson [1]; tiende video] voor meer uitleg over waarom dit zo werkt.

4.3. Modulo

  \begin{pspicture}(-4.5,-1)(4.5,1)
    \psaxes{<->}(0,0)(-4,0)(4,0)
    \rput(4.5,0){$\infty$}
    \rput(-4.5,0){$-\infty$}    
  \end{pspicture}
(a) Een normale getallenlijn
  \begin{pspicture}(-3,-3)(3,3)
    \pscircle(0,0){2}
    
    \psline(0,1.85)(0,2.15)
    \rput(0,2.4){0}
    
    \psline(1.308,1.308)(1.520,1.520)
    \rput(1.814,1.814){1}
    
    \psline(1.85,0)(2.15,0)
    \rput(2.4,0){2}
    
    \psline(1.308,-1.308)(1.520,-1.520)
    \rput(1.814,-1.814){3}
    
    \psline(0,-1.85)(0,-2.15)
    \rput(0,-2.4){4}
    
    \psline(-1.308,-1.308)(-1.520,-1.520)
    \rput(-1.814,-1.814){5}
    
    \psline(-1.85,0)(-2.15,0)
    \rput(-2.4,0){6}
    
    \psline(-1.308,1.308)(-1.520,1.520)
    \rput(-1.814,1.814){7}
  \end{pspicture}
(b) Getallenlijn $\bmod 8$

Figuur 5. Een voorstelling van modulo

De beste voorstelling van modulo rekenen is waarschijnlijk om de normale getallenlijn (figuur 5a) voor te stellen als een cirkel, zoals in figuur 5b. Bij het tellen op deze ‘getallencirkel’ kom je na 7 weer uit bij 0, waardoor bijvoorbeeld geldt $5 + 4 \bmod 8 = 1$. Op de modulo 8 cirkel beginnend bij 5 is namelijk te zien dat vier stappen verder uitkomt bij 1. Dit betekent ook dat $a \bmod b$ te berekenen is als de rest die overblijft bij het delen van $a$ door $b$.

4.4. Exclusieve disjunctie

De exclusieve disjunctie wordt vaak afgekort als XOR, naar de Engelse term exclusive or en in vergelijkingen weergegeven met $\oplus$. In de logica geldt dat $a \oplus b$ waar is, als $a$ of $b$ waar is, maar niet allebei, zoals te zien in tabel 2.

$a$ $b$ $a \oplus b$
onwaar onwaar onwaar
waar onwaar waar
onwaar waar waar
waar waar onwaar

Tabel 2. Waarheidstabel voor de exclusieve disjunctie

Voor bits geldt 0 als onwaar en 1 als waar, dus $1 \oplus 0 = 1$, $0 \oplus 0 = 0$ en $1 \oplus 1 = 0$. Daarom geldt bij het rekenen met bits $a \oplus b = a + b \bmod 2$.

4.5. Complexe getallen

Normaal gesproken wordt er alleen gerekend met reëele getallen: al deze getallen kunnen we voorstellen op een lijn, en deze getallen worden verzameld in $\mathbb{R}$. In de verzameling van reëele getallen is $\sqrt{-1}$, of de wortel van elk ander negatief getal, niet mogelijk, omdat er op de getallenlijn geen getal is dat met zichzelf vermenigvuldigd een negatief getal oplevert. Bij complexe getallen is een negatieve wortel wel mogelijk, waarvoor het getal $i$ gebruikt wordt:

(7)
\[i = \sqrt{-1}
\]

Alle complexe getallen ($\mathbb{C}$) zijn voor te stellen in de volgende vorm:

(8)
\[z = a + bi \in \mathbb{C} \qquad \text{met } a,b \in \mathbb{R}
\]

Van het complexe getal $z$ is de complex geconjugeerde $z^*$ gedefinieerd:

(9)
\[z^* = a - bi
\]

Dit is slechts een zeer beknopte weergave van complexe getallen, een uitgebreide uitleg is bijvoorbeeld te vinden in [2].

5. Hoe werkt de meest gebruikte cryptografie?

Cryptografie komt voor in vele verschillende soorten en maten, maar waarschijnlijk de bekendste vorm van encryptie wordt door bijna elke internetgebruiker dagelijks gebruikt en is te herkennen aan het groene slotje in de browser: HTTPS.

https


Figuur 6. Een versleutelde verbinding met www.rijksoverheid.nl

HTTPS is op zichzelf eigenlijk geen cryptografisch systeem, maar een protocol voor het gebruik van encryptie bij internetverbindingen. In de TLS specificatie [3], het protocol waar HTTPS gebruik van maakt, is dan wel vrijheid gegeven om uit verschillende cryptografische systemen te kunnen kiezen, maar standaard wordt er gebruik gemaakt van RSA en AES en in de praktijk wordt van de verdere vrijheid slechts weinig gebruik gemaakt. In figuur 6 is te zien dat bijvoorbeeld ook www.rijksoverheid.nl gebruik maakt van deze systemen, die hierna besproken worden.

5.1. Hoe werkt AES?

De Advanced Encryption Standard [4] is één van de meest gebruikte blokversleutelingen en is gebaseerd op het Rijndael algoritme [5], dat ontworpen is door de Belgische Joan Daemen en Vincent Rijmen. In tegenstelling tot Rijndael is AES alleen gespecificeerd voor een invoer van 128 bits, er kunnen dus alleen blokken van 128 enen en nullen mee versleuteld worden. Voor de sleutel zijn er drie lengtes mogelijk, namelijk 128, 192 of 256 bits. Bij een langere sleutel wordt de versleuteling meerdere malen herhaald, zoals te zien in tabel 3.

Sleutel lengte Invoer lengte Aantal rondes
$Nk$ $Nb$ $Nr$
AES-128 128 128 10
AES-192 192 128 12
AES-256 256 128 14

Tabel 3. Verschillende sleutellengtes voor AES

Om handig aan te duiden met welke sleutellengte AES gebruikt wordt, spreekt men meestal van AES-128, AES-192 of AES-256 bij respectievelijke sleutellengtes van 128, 192 of 256 bits.

De eerste stap van het AES algoritme is de uitbreiding van de sleutel. Vervolgens wordt er met AddRoundKey() een exclusieve disjunctie uitgevoerd met de eerste 128 bits van de uitgebreide sleutel en de invoer, waarna er in $Nr - 1$ rondes, achtereenvolgens de functies SubBytes(), ShiftRows(), MixColumns() en weer AddRoundKey(), deze laatste steeds met de volgende 128 bits van de uitgebreide sleutel. Als laatste worden nog een keer SubBytes(), ShiftRows() en AddRoundKey() uitgevoerd. Dit is schematisch weergegeven in figuur 7, de verschillende onderdelen worden hierna besproken.

\[\begin{aligned}
&\text{Uitbreiding van de sleutel}\\
\\
&\text{AddRoundKey()}\\
\\
&\left.\begin{aligned}
      &\text{SubBytes()}\\
      &\text{ShiftRows()}\\
      &\text{MixColumns()}\\
      &\text{AddRoundKey()}\\
      \end{aligned}
\right\}
\quad (Nr - 1) \times\\
\\
&\text{SubBytes()}\\
&\text{ShiftRows()}\\
&\text{AddRoundKey()}
\end{aligned}
\]

Figuur 7. Schematische weergave van het AES algoritme

5.1.1. Uitbreiding van de sleutel

De sleuteluitbreiding genereert een sleutel van $Nb(Nr + 1)$ bits: voor elke ronde zijn er 128 bits ($Nb$) nodig om de invoer mee te versleutelen, naast een initiële 128 bits, die nog voor de eerste ronde gebruikt worden bij de initiële versleuteling. De uitbreiding van een sleutel met 128 bits levert dus $128 \times (10 + 1) = 1408$ bits en gaat als volgt: eerst wordt de sleutel opgedeeld in 4 blokken van 4 bytes, die worden opgeslagen in rij $w$. In het volgende voorbeeld wordt gebruik gemaakt van de sleutel 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c.

$w_0$ 2b7e1516
$w_1$ 28aed2a6
$w_2$ abf71588
$w_3$ 09cf4f3c

In vergelijking (10) wordt beschreven hoe de rest van de rij eruit gevormd wordt.

(10)
\[w_i = w_{i-1} \oplus w_{i-4} \qquad \text{als } i > 3 \land i \bmod 4 \neq 0
\]

Als $i$ wel deelbaar is door 4, wordt er nog een serie andere wijzigingen doorgevoerd:

  1. RotWord(): deze functie krijgt als invoer een rij van vier bytes $[a_0,a_1,a_2,a_3]$ en geeft als uitvoer $[a_1,a_2,a_3,a_0]$. De eerste byte wordt dus weggehaald en achteraan teruggeplakt.
  2. SubWord(): alle bytes worden vervangen door de bijbehorende waarde in de S-box, zie tabel 4. De byte {10} bijvoorbeeld wordt zo vervangen door {ca}.
  3. $\text{temp} \oplus [2^{\frac{i}{4} - 1}, 00, 00, 00]$, waarin temp de waarde is die bij de vorige stap is verkregen. Bij bijvoorbeeld $i = 8$: $[50, 38, 6b, e5] \oplus [02, 00, 00, 00] = [52, 38, 6b, e5]$.
  4. $w_i = \text{temp} \oplus w_{i-4}$, waarin temp wederom de waarde verkregen uit de vorige stap is.
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Tabel 4. Vervangingswaarden voor bytes in SubBytes()

In het kort wordt er dus steeds de exclusieve disjunctie genomen van de voorgaande waarde en de waarde vier plaatsen eerder, elke vierde keer wordt de voorgaande waarde eerst nog een beetje veranderd, om een patroon in de uitgebreide sleutel te voorkomen. Het resultaat van deze stappen is te zien in tabel 5 voor $4 \leq i \leq 8$. Een volledige uitwerking is te vinden in Appendix A van [4].

$i$ $w_{i-1}$ (1) (2) (3) $w_{i-4}$ (4)
4 09cf4f3c cf4f3c09 8a84eb01 8b84eb01 2b7e1516 a0fafe17
5 a0fafe17 28aed2a6 88542cb1
6 88542cb1 abf71588 23a33939
7 23a33939 09cf4f3c 2a6c7605
8 2a6c7605 6c76052a 50386be5 52386be5 a0fafe17 f2c295f2

Tabel 5. Voorbeeld van het sleuteluitbreidingsalgoritme voor AES-128

5.1.2. Versleutelen

Bij het versleutelen wordt de invoer opgeslagen in de variabele $s$, ook wel de state genoemd, die we kunnen voorstellen als een raster van vier bij vier met in elk hokje een byte, zoals te zien in figuur 8.

invoer bytes
$in_{0}$ $in_{4}$ $in_{8}$ $in_{12}$
$in_{1}$ $in_{5}$ $in_{9}$ $in_{13}$
$in_{2}$ $in_{6}$ $in_{10}$ $in_{14}$
$in_{3}$ $in_{7}$ $in_{11}$ $in_{15}$

$\rightarrow$

state
$s_{0,0}$ $s_{0,1}$ $s_{0,2}$ $s_{0,3}$
$s_{1,0}$ $s_{1,1}$ $s_{1,2}$ $s_{1,3}$
$s_{2,0}$ $s_{2,1}$ $s_{2,2}$ $s_{2,3}$
$s_{3,0}$ $s_{3,1}$ $s_{3,2}$ $s_{3,3}$

Figuur 8. Invoer en state
AddRoundKey()
(11)
\[[s_{0,c}', s_{1,c}', s_{2,c}', s_{3,c}'] = [s_{0,c}, s_{1,c}, s_{2,c}, s_{3,c}] \oplus [w_{4r + c}] \qquad \text{voor } 0 \leq c < 4
\]

In vergelijking (11) wordt weergegeven hoe de AddRoundKey() functie werkt. In deze vergelijking is $w$ de rij met de uitgebreide sleutel, zoals beschreven in 5.1.1 en $r$ de ronde waarin de functie wordt aangeroepen. Bij de eerste aanroep, die immers buiten de herhaling valt, geldt $r = 0$; bij de laatste, ook buiten de herhaling, geldt $r = Nr$. AddRoundKey() neemt dus steeds de exclusieve disjunctie van de huidige staat en de volgende 128 bits in de uitgebreide sleutel.

SubBytes()

Deze SubBytes() functie is vergelijkbaar met de functie SubWord() beschreven in 5.1.1 en vervangt elke byte door de bijbhorende byte in de S-box, zie tabel 4.

ShiftRows()

De ShiftRows() functie zorgt voor een verschuiving in de rijen van $s$. De eerste rij blijft hetzelfde, bij de tweede rij wordt de eerste byte naar achteren verplaatst, bij de derde rij worden de eerste twee bytes naar achteren verplaatst en bij de vierde rij worden de eerste drie bytes naar achteren verplaatst. Dit is weergegeven in figuur 9.

$s$
$s_{0,0}$ $s_{0,1}$ $s_{0,2}$ $s_{0,3}$
$s_{1,0}$ $s_{1,1}$ $s_{1,2}$ $s_{1,3}$
$s_{2,0}$ $s_{2,1}$ $s_{2,2}$ $s_{2,3}$
$s_{3,0}$ $s_{3,1}$ $s_{3,2}$ $s_{3,3}$

shiftrows

$s'$
$s_{0,0}$ $s_{0,1}$ $s_{0,2}$ $s_{0,3}$
$s_{1,1}$ $s_{1,2}$ $s_{1,3}$ $s_{1,0}$
$s_{2,2}$ $s_{2,3}$ $s_{2,0}$ $s_{2,1}$
$s_{3,3}$ $s_{3,0}$ $s_{3,1}$ $s_{3,2}$

Figuur 9. ShiftRows()
MixColumns()

De MixColumns() functie is een matrix transformatie die werkt op de kolommen van $s$, zoals weergegeven in vergelijking (12).

(12)
\[\begin{bmatrix}
  s_{0,c}' \\
  s_{1,c}' \\
  s_{2,c}' \\
  s_{3,c}'
\end{bmatrix}
=
\begin{bmatrix}
  02 & 03 & 01 & 01 \\
  01 & 02 & 03 & 01 \\
  01 & 01 & 02 & 03 \\
  03 & 01 & 01 & 02
\end{bmatrix}
\begin{bmatrix}
  s_{0,c} \\
  s_{1,c} \\
  s_{2,c} \\
  s_{3,c}
\end{bmatrix}
\qquad \text{voor } 0 \leq c < 4
\]

5.1.3. Ontsleutelen

Het ontsleutelen van een met AES versleutelde tekst is gemakkelijk te doen door het algoritme simpelweg in omgekeerde volgorde uit te voeren, waarbij gebruik gemaakt wordt van een prettige eigenschap van de exclusieve disjunctie, die wordt weergegeven in vergelijking (13).

(13)
\[(a \oplus b) \oplus b = a
\]

Hierdoor kunnen we de cijfertekst als het ware opnieuw versleutelen, om de originele tekst terug te krijgen. Om dit een beetje te verduidelijken, is in tabel 6 een voorbeeld gegeven.

tekst 00101010
sleutel 11011000
versleuteld 11110010
versleuteld 00101010

Tabel 6. Opnieuw versleutelen levert de originele tekst op

Omdat voor het versleutelen en ontsleutelen van de data dezelfde sleutel gebruikt wordt, is AES een symmetrisch algoritme.

5.2. Hoe werkt RSA?

RSA is, in tegenstelling tot AES, een asymmetrisch algoritme: voor het versleutelen wordt namelijk een andere sleutel gebruikt als voor het ontsleutelen. Het RSA algoritme, zo genoemd naar de drie bedenkers Rivest, Shamir en Adleman, is gepubliceerd in 1977 [6] en wordt nog altijd gebruikt. Vergeleken met AES is RSA een langzaam algoritme, maar door de asymmetrische sleutels is het veel handiger in gebruik: er hoeft namelijk geen geheime sleutel tussen twee partijen gecommuniceerd te worden, wat het zwakke punt is bij AES. Om een beveiligde verbinding tot stand te brengen is een bij beide partijen bekende sleutel nodig en om de sleutel te communiceren is een beveiligde verbinding nodig. In de praktijk worden de twee daarom vaak gecombineerd: de sleutel voor AES wordt met RSA versleuteld en naar de andere partij verstuurd; de data zelf wordt met AES versleuteld.

5.2.1. Asymmetrische cryptografie

Het idee voor asymmetrische cryptografie werd in 1976 geopperd door Diffie en Hellman in [7], maar zij gaven geen details over hoe dit gerealiseerd kon worden. Wel gaven zij de vier criteria waar asymmetrische cryptografie aan moet voldoen:

  1. Het onstsleutelen van een versleuteld getal, levert datzelfde getal: $D(E(M)) = M$, waarin $M$ de tekst, $E$ de encryptiefunctie en $D$ de decryptiefunctie is.
  2. Zowel $E$ als $D$ zijn makkelijk te berekenen.
  3. Bij het publiceren van $E$ wordt er geen makkelijke manier gegeven om $D$ te berekenen.
  4. Als $M$ eerst wordt ontcijferd en vervolgens vercijferd, is het resultaat $M$: $E(D(M)) = M$.

Er moeten dus verschillende sleutels zijn voor encryptie en decryptie, die gemakkelijk te maken, maar, indien een van twee bekend is, moeilijk te herleiden zijn.

5.2.2. Encryptie en decryptie functies

De encryptie functie voor RSA is gedefinieerd in vergelijking (14), de decryptie functie in vergelijking (15).

(14)
\[C = E(M) = M^e \bmod n
\]
(15)
\[M = D(C) = C^d \bmod n
\]

In deze vergelijkingen is $M$ het klare getal en $C$ het versleutelde getal. Als encryptiesleutel kan dan $(e,n)$ worden gebruikt, als decryptiesleutel $(d,n)$. Om deze sleutels te berekenen worden twee priemgetallen $p$ en $q$ gekozen. De waarde van $n$ in beide sleutels wordt hiermee gedefinieerd in vergelijking (16).

(16)
\[n = p \cdot q
\]

De waarde van $d$ wordt zo gekozen dat $d$ geen gemeenschappelijke delers met $(p-1)(q-1)$ groter dan 1 heeft, oftewel $ggd(d, (p-1)(q-1)) = 1$. Met $d$ wordt dan $e$ berekend, zoals in vergelijking (17).

(17)
\[e = d^{-1} \bmod (p-1)(q-1)
\]

Deze functies voldoen aan de door Diffie en Hellman gestelde eisen voor assymetrische cryptografie. Om bij een bekende encryptiefunctie de bijbehorende decryptiefunctie te vinden is nodig om de priemfactoren $p$ en $q$ te berekenen, wat zelfs met de beste algoritmes bij grote getallen met een gewone computer al snel miljarden jaren kan duren. Op deze moeilijkheid is de veiligheid van RSA gebaseerd.

5.2.3. Voorbeeld

Als voorbeeld worden $p = 47$, $q =  59$ en $d = 157$ gekozen, vergelijking (16) geeft dan $n = 47 \cdot 59 = 2773$, en $(p - 1)(q - 1) = 46 \cdot 58 = 2668$. De waarde van $e$ kan worden berekend met het algoritme van Euclides:

2668 157
2668 1 0
157 0 1
156 1 -16
1 -1 17

Hieruit volgt dat $e = 157^{-1} \bmod 2668 = 17$. De encryptiesleutel is dus $(17,2773)$, de decryptiesleutel $(157,2773)$. Het invullen van deze waardes in vergelijkingen (14) en (15) geeft dan de volgende encryptie- en decryptiefuncties voor dit voorbeeld:

\[\begin{aligned}
E(M) &= M^{17}  &\bmod 2773 \\
D(C) &= C^{157} &\bmod 2773
\end{aligned}
\]

Het versleutelen van het getal $M = 15$ levert dan $E(15) = 15^{17} \bmod 2773 = 1392$ en ontsleutelen van deze uitkomst levert $D(1392) = 1392^{157} \bmod 2773 = 15$. In de praktijk worden natuurlijk vele malen grotere getallen gebruikt; de priemfactoren van 2773 zijn, met een beetje doorzettingsvermogen, ook met de hand nog wel te berekenen en dus voor een computer een fluitje van een cent.

6. Hoe werkt een quantumcomputer?

Op een zoektocht naar een werkende quantumcomputer zijn er twee partijen die snel boven komen drijven: D-Wave Systems, een in 1999 opgericht Canadees bedrijf, specifiek gericht op quantumcomputers; en IBM, de in 1911 opgerichte computergigant, met name bekend door een van de eerste PC's: de IBM PC. De quantumcomputers van beide bedrijven zijn zeer verschillend: de systemen van D-Wave zijn commercieel verkrijgbaar en worden onder andere gebruikt door Lockheed Martin; IBM's quantumcomputer is slechts een onderzoeksproject. Een ander groot verschil is het aantal qubits dat gebruikt wordt in de computers: D-Wave presenteerde recent een preview van een systeem met 2000 qubits [8], IBM's systeem heeft er 5. Het lijkt er dus op dat D-Wave de standaard moet worden voor een onderzoek naar quantumcomputers; hun systeem werkt immers het best.

Nader onderzoek wijst echter uit dat de claim van D-Wave van de eerste commerciele quantumcomputer niet geheel geaccepteerd wordt: zo laat David DiVincenzo, auteur van een van de meest invloedrijke artikelen over quantumcomputers [9], in een interview [10] weten dat de D-Wave computers weliswaar enkele kenmerkende eigenschappen van een quantumcomputer hebben, maar dat de tijd waarin de qubits zich in superpositie bevinden, slechts enkele nanoseconden, wat hem betreft te kort is om deze systemen ook daadwerkelijk als quantumcomputers te bestempelen. Daarnaast is de hardware van de D-Wave computers speciaal gebouwd om één specifiek probleem op te lossen, dus is het niet mogelijk deze computer te programmeren. De winnaar is dus IBM.

Bijkomend voordeel is dat IBM veel opener is over hun quantumcomputer en deze zelfs op het internet heeft aangesloten, zodat iedereen via de IBM Quantum Experience (https://​quantumexperience.​ng.​bluemix.​net) programma's op deze 5 qubit quantumcomputer kan uitvoeren.

6.1. IBM Quantum Experience

In de IBM Quantum Experience is het mogelijk om met behulp van de ‘Composer’ een programma te schrijven dat kan worden uitgevoerd op de IBM 5Q. De Composer is een grafisch programma, maar achter de schermen wordt zogenaamde QASM gegenereerd, de taal die IBM ontworpen heeft om hun quantumcomputer te kunnen programmeren. Bij de uitleg over de werking van quantumcomputers zullen enkele voorbeelden van programma's in de Quantum Experience gebruikt worden, deze zijn te herkennen aan de term QASM. Hier zullen alleen de grafische weergave van het programma en de resultaten van de laatste uitvoering getoond worden, een link naar het programma in de Quantum Experience is te vinden in appendix A.

6.2. Wat is een quantumcomputer niet?

Voor we verdergaan met een echte uitleg van een quantumcomputer, is het wellicht handig om wat mythes de wereld uit te helpen.

Een veelgehoorde uitleg van een quantumcomputer gaat als volgt: een quantumcomputer gebruikt in plaats van gewone bits, qubits, die op waardes 1, 0, of allebei tegelijk kunnen staan. Hierdoor kunnen heel veel berekeningen parallel worden uitgevoerd, wat het bij bijvoorbeeld het kraken van een versleutelde code veel makkelijker maakt om simpelweg alle opties uit te proberen.

Helaas, zo werkt dat niet. Een qubit kan inderdaad in een zogenaamde superpositie terechtkomen, maar dat deze qubit tegelijkertijd voor meerdere berekeningen gebruikt kan worden is de verkeerde conclusie.

Een antwoord op de vraag “Waarom is een quantumcomputer sneller dan een gewone computer?” wordt wel beantwoord met een uitleg dat het aantal verschillende mogelijke toestanden van het gehele systeem exponentieel toeneemt bij het toenemen van het aantal qubits. Het aantal mogelijkheden wordt hierdoor al snel heel erg groot, zoals bij de beroemde legende van het schaakbord vol graankorrels.

Op zich is dit verhaal correct, een antwoord op de vraag is het echter niet. Bij een gewone computer is dit namelijk niet anders, ook hier neemt het aantal toestanden exponentieel toe, en de gemiddelde computer heeft vele malen meer bits tot zijn beschikking dan zelfs het experimentele D-Wave systeem. Voor een uitleg waarom een quantumcomputer soms wel sneller is, zie paragraaf 6.6.

Nog een misverstand is dat op een quantumcomputer alles sneller gaat, maar dat zal meestal niet het geval zijn. Een quantumcomputer is alleen sneller bij algoritmes die gebruik maken van de quantummogelijkheden van de qubits. Een ouderwets algoritme dat ontworpen is voor normale computers zal waarschijnlijk alleen maar langzamer werken, omdat er rekening gehouden moet worden met de willekeurigheid die nu eenmaal bij quantummechanica hoort.

Een quantumcomputer is dus niet een magische machine die alles veel sneller kan; nu eenmaal niet alle problemen worden makkelijker door er quantummechanica aan toe te voegen.

6.3. Wat is een qubit?

Een normale computer rekent met bits, die een waarde 0 of 1 hebben. Een quantumcomputer werkt op een vergelijkbare manier, maar dan met quantum bits (qubits), die een waarde 0, 1, of een superpositie tussen deze twee hebben. Om dit voor te kunnen stellen, worden qubits aangegeven als een vector: de qubit met waarde 0 krijgt de vector $\big[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\big]$ en die met waarde 1 $\big[\begin{smallmatrix} 0 \\ 1 \end{smallmatrix}\big]$. Deze qubits krijgen ook hun eigen naam in de speciale bra-ket notatie: 0 wordt $|0\rangle$, 1 wordt $|1\rangle$, zie ook figuur 10.

  \begin{pspicture}(-1,-1)(1.5,1.5)
    \psline{->}(0,0)(1,0)
    \psline{->}(0,0)(0,1)
    \rput(-0.6,0.5){$|1\rangle$}
    \rput(0.5,-0.6){$|0\rangle$}
  \end{pspicture}

Figuur 10. Qubits $|0\rangle$ en $|1\rangle$ als vectoren

Behalve deze twee basiswaarden kan een qubit zich ook in superpositie bevinden: ergens tussen beide basiswaarden, met als voorwaarde dat de qubit naar een van de basiswaarden moet kunnen terugvallen, waardoor de lengte altijd gelijk moet zijn, namelijk 1.

In 4.2.3 is beschreven hoe elke vector geschreven kan worden als een combinatie van twee basisvectoren. Zo is ook elke qubit te schrijven als een combinatie van de twee basiswaarden, waarmee een qubit als volgt wordt gedefinieerd:

(18)
\[  |\psi\rangle = \alpha |0\rangle + \beta |1\rangle
  \qquad \text{als } \alpha, \beta \in \mathbb{C} \text{ en } |\alpha|^2 + |\beta|^2 = 1
\]

Het probleem met superpositie is dat het niet gemeten kan worden: zodra de qubit geobserveerd wordt, zal hij terugvallen naar een van de basiswaarden. Door deze routine vaak te herhalen, kan de kans dat de qubit naar $|0\rangle$ of $|1\rangle$ terugvalt worden berekent, waarmee vervolgens de superpositie bepaald kan worden.

gelijkmatige-superpositie
(a) QASM
    \definecolor{qorange}{HTML}{F26D21}
    \begin{bchart}[max=1,step=0.125]
      \bcbar[label=0,color=qorange]{0.512}
      \smallskip
      \bcbar[label=1,color=qorange]{0.488}
    \end{bchart}
(b) Resultaat

QASM 1. Gelijkmatige superpositie (1024 Shots)

In QASM 1 is een qubit met een Hadamard poort in een gelijkmatige superpositie gebracht, die bij het meten terugvalt naar een van de basiswaarden. Aan het resultaat is te zien dat de qubit in ongeveer de helft van de tijd naar 0 terugvalt en de andere helft naar 1, vandaar de naam gelijkmatige superpositie. De vectorvoorstelling van deze superpositie is te zien in figuur 11.

  \begin{pspicture}(-1,-1)(1.5,1.5)
    \psline[linestyle=dashed]{->}(0,0)(1,0)
    \psline[linestyle=dashed]{->}(0,0)(0,1)
    \rput(-0.6,0.5){$|1\rangle$}
    \rput(0.5,-0.6){$|0\rangle$}
    
    \psline{->}(0,0)(0.707,0.707)
  \end{pspicture}
(a)
\[    \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}
\]
(b)

Figuur 11. Gelijkmatige superpositie als vector

Om te controleren dat dit inderdaad een geldige qubit is, kan deze vector geschreven worden in de vorm $\alpha |0\rangle + \beta |1\rangle$, waarbij moet gelden dat $|\alpha|^2 + |\beta|^2 = 1$ (zie vergelijking (18)):

(19)
\[\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}
=
\frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle
\Rightarrow
\left(\frac{1}{\sqrt{2}}\right)^2 + \left(\frac{1}{\sqrt{2}}\right)^2 = 1
\]

6.3.1. Bra-ket notatie

Eerder is vermeld dat de basiswaarden een speciale bra-ket notatie kregen: $|0\rangle$ en $|1\rangle$. Dit zijn de ket-versies van de vectoren. Naast de ket-versie is er, zoals de naam van de notatie doet vermoeden, ook een bra-versie, die als volgt gedefinieerd is:

(20)
\[\langle\cdot| = \left(|\cdot\rangle^*\right)^T
\]

Dit betekent dat de bra de geconjugeerde transpositie van de ket is. Als voorbeeld wordt de vector $|\psi\rangle$ gebruikt:

(21)
\[|\psi\rangle = \begin{bmatrix} a + bi \\ c + di \end{bmatrix}
\]
(22)
\[\langle\psi| = \left(|\psi\rangle^*\right)^T = 
\begin{bmatrix} (a + bi)^* \\ (c + di)^* \end{bmatrix}^T =
\begin{bmatrix} (a - bi) \\ (c - di) \end{bmatrix}^T =
\begin{bmatrix} a - bi & c - di \end{bmatrix}
\]

Het sterretje naast de ket betekent dus dat van alle getallen in de vector de geconjugeerde wordt genomen; de T naast de vector dat deze vector geschreven wordt als een 2×1 matrix.

De bra-ket notatie is vooral handig bij het berekenen van het inproduct:

(23)
\[|a\rangle \cdot |b\rangle = \langle a| |b \rangle = \langle a|b \rangle
\]

Of het berekenen van de lengte van een vector:

(24)
\[\text{lengte(}|a\rangle\text{) } = \sqrt{\langle a|a \rangle}
\]

6.3.2. Kans op een uitkomst

Het is voor elke superpositie mogelijk om te berekenen wat de kans is dat de qubit bij het uitlezen terugvalt naar een bepaalde basiswaarde door te kijken “hoeveel van die basiswaarde in de superpositie zit.” Dit kan berekend worden met het inproduct van de qubit en de basiswaarde:

(25)
\[p_0 = |\langle\psi|0\rangle|^2
\]

Door de notatie voor een qubit uit vergelijking (18) te gebruiken, kan deze kans simpeler uitgedrukt worden:

(26)
\[p_0 = |(\alpha\langle 0| + \beta\langle 1|)|0\rangle|^2 = 
| \alpha \langle 0|0 \rangle + \beta \langle 1|0 \rangle |^2 =
|\alpha \times 1 + \beta \times 0|^2 =
|\alpha|^2
\]

Op dezelfde manier kan de kans dat de qubit naar 1 terugvalt worden berekend:

(27)
\[p_1 = |\langle\psi|1\rangle|^2 = |\beta|^2
\]

Hierdoor wordt ook duidelijk waarom in vergelijking (18) de voorwaarde $|\alpha|^2 + |\beta|^2 = 1$ gesteld wordt: de totale kans dat de qubit naar een van de twee basiswaarden terugvalt moet natuurlijk 1 zijn.

We kunnen nu ook