TomáˇsZach ImplementaceTRNGnaARMCortex-M0 Bakaláˇrskápráce

(1)

prof. Ing. Róbert Lórencz, CSc.

vedoucí katedry doc. RNDr. Ing. Marcel Jiřina, Ph.D.

děkan

ZADÁNÍ BAKALÁŘSKÉ PRÁCE

Název: Implementace TRNG na ARM Cortex-M0

Student: Tomáš Zach

Vedoucí: Ing. Filip Kodýtek Studijní program: Informatika

Studijní obor: Informační technologie Katedra: Katedra počítačových systémů Platnost zadání: Do konce letního semestru 2018/19

Pokyny pro vypracování

Nastudujte problematiku generátorů skutečně náhodných čísel (TRNG) se zaměřením na TRNG vhodné pro mikrokontroléry. Vyberte cílovou platformu, jejíž součástí je procesor s jádrem ARM Cortex-M0.

Implementujte vhodnou variantu TRNG za použití prostředků zvolené platformy. Proveďte vyhodnocení vámi implementovaného řešení a diskutujte své výsledky.

Seznam odborné literatury

Dodá vedoucí práce.

(2)

(3)

Bakal´ aˇrsk´ a pr´ ace

Implementace TRNG na ARM Cortex-M0

Tom´ aˇ s Zach

Katedra poˇc´ıtaˇcových systém˚u Vedouc´ı práce: Ing. Filip Kodýtek

(4)

(5)

Podˇ ekov´ an´ı

Pˇredevˇs´ım dˇekuji svému vedouc´ımu práce Ing. Filipu Kodýtkovi za moˇznost zabývat se zaj´ımavým tématem a téˇz za vstˇr´ıcný pˇr´ıstup a ˇcas, který mi vˇenoval pˇri psan´ı této práce. Dále dˇekuji své rodinˇe za podporu v pr˚ubˇehu

(6)

(7)

Prohl´ aˇ sen´ı

Prohlaˇsuji, ˇze jsem pˇredloˇzenou práci vypracoval(a) samostatnˇe a ˇze jsem uvedl(a) veˇskeré pouˇzité informaˇcn´ı zdroje v souladu s Metodickým pokynem o etické pˇr´ıpravˇe vysokoˇskolských závˇereˇcných prac´ı.

Beru na vˇedom´ı, ˇze se na moji práci vztahuj´ı práva a povinnosti vyplývaj´ıc´ı ze zákona ˇc. 121/2000 Sb., autorského zákona, ve znˇen´ı pozdˇejˇs´ıch pˇredpis˚u.

V souladu s ust.§46 odst. 6 tohoto zákona t´ımto udˇeluji nevýhradn´ı oprávnˇen´ı (licenci) k uˇzit´ı této moj´ı práce, a to vˇcetnˇe vˇsech poˇc´ıtaˇcových program˚u, jeˇz jsou jej´ı souˇcást´ı ˇci pˇr´ılohou, a veˇskeré jejich dokumentace (dále souhrnnˇe jen

”D´ılo“), a to vˇsem osobám, které si pˇrej´ı D´ılo uˇz´ıt. Tyto osoby jsou oprávnˇeny D´ılo uˇz´ıt jakýmkoli zp˚usobem, který nesniˇzuje hodnotu D´ıla, a za jakýmkoli

´

uˇcelem (vˇcetnˇe uˇzit´ı k výdˇeleˇcným úˇcel˚um). Toto oprávnˇen´ı je ˇcasovˇe, teri- toriálnˇe i mnoˇzstevnˇe neomezené. Kaˇzdá osoba, která vyuˇzije výˇse uvedenou licenci, se vˇsak zavazuje udˇelit ke kaˇzdému d´ılu, které vznikne (byt’ jen zˇcásti) na základˇe D´ıla, úpravou D´ıla, spojen´ım D´ıla s jiným d´ılem, zaˇrazen´ım D´ıla do d´ıla souborného ˇci zpracován´ım D´ıla (vˇcetnˇe pˇrekladu), licenci alespoˇn ve výˇse uvedeném rozsahu a zároveˇn zpˇr´ıstupnit zdrojový kód takového d´ıla ale- spoˇn srovnatelným zp˚usobem a ve srovnatelném rozsahu, jako je zpˇr´ıstupnˇen zdrojový kód D´ıla.

(8)

Cesk´ˇ e vysok´e uˇcen´ı technick´e v Praze Fakulta informaˇcn´ıch technologi´ı

c 2018 Tom´aˇs Zach. Vˇsechna pr´ava vyhrazena.

Tato práce vznikla jako ˇskoln´ı d´ılo na ˇCeském vysokém uˇcen´ı technickém v Praze, Fakultˇe informaˇcn´ıch technologi´ı. Práce je chránˇena právn´ımi pˇredpisy a mezinárodn´ımi úmluvami o právu autorském a právech souvisej´ıc´ıch s právem autorským. K jej´ımu uˇzit´ı, s výjimkou bezúplatných zákonných licenc´ı a nad rámec oprávnˇen´ı uvedených v Prohláˇsen´ı na pˇredchoz´ı stranˇe, je nezbytný sou- hlas autora.

Odkaz na tuto pr´aci

Zach, Tomáˇs. Implementace TRNG na ARM Cortex-M0. Bakal´aˇrská práce.

Praha: ˇCeské vysoké uˇcen´ı technické v Praze, Fakulta informaˇcn´ıch technologi´ı, 2018.

(9)

Abstrakt

Tato práce se zabývá generátory skuteˇcnˇe náhodných ˇc´ısel - zkrácenˇe TRNG (True Random Number Generator). Nejdˇr´ıve je provedena literárn´ı reˇserˇse týkaj´ıc´ı se problematiky TRNG se zamˇeˇren´ım na mikrokontroléry. Dále je zde pˇredstavena vlastn´ı implementace TRNG na mikrokontroléru s procesorem ARM-CORTEX-M0. Na závˇer je provedeno vyhodnocen´ı mˇeˇren´ı dané implementace pomoc´ı sady statistických test˚u.

Kl´ıˇcová slova Generátor skuteˇcnˇe náhodných ˇc´ısel, TRNG, mikrokontrolér, ARM-CORTEX-M0, clock jitter, NIST

Abstract

This work deals with true random number generators (TRNG). At first, a literature research concerning TRNG with a focus on microcontrollers is done. Then own implementation of TRNG using microcontroller with ARM- CORTEX-M0 processor is introduced. Finally measurements of the proposed design are evaluated with a set of statistical tests.

Keywords True Random Number Generator, TRNG, microcontroller, ARM- CORTEX-M0, clock jitter, NIST

(10)

(11)

Obsah

Uvod´ 1

1 Generátory náhodných ˇc´ısel 3

1.1 Generátory náhodných ˇc´ısel . . . 3

1.2 Klasifikace generátor˚u náhodných ˇc´ısel . . . 4

1.3 PRNG . . . 4

1.4 TRNG . . . 6

1.5 Praktick´e pouˇzit´ı RNG . . . 9

1.6 Aplikace RNG . . . 9

2 Typy konstrukc´ı TRNG 11 2.1 TERO TRNG . . . 11

2.2 Intel TRNG . . . 12

2.3 Konstrukce Fischer-Drutarovsk´y . . . 13

2.4 TRNG na Atmel AVR . . . 14

3 N´avrh a implementace 17 3.1 Popis implementace . . . 17

3.2 Hardware . . . 18

3.3 Program . . . 19

4 Mˇeˇren´ı 23 4.1 Mˇeˇren´ı 1 . . . 24

4.2 Mˇeˇren´ı 2 . . . 24

4.3 Mˇeˇren´ı 3 . . . 25

4.4 Mˇeˇren´ı 4 . . . 26

4.5 Shrnut´ı . . . 26

5 Statistick´e vyhodnocen´ı 27 5.1 Sada test˚u NIST STS . . . 27

(12)

5.2 Pouˇzit´ı NIST STS . . . 28

5.3 Testovan´a Data . . . 28

5.4 V´ysledky . . . 28

5.5 Shrnut´ı . . . 28

Z´avˇer 31

Literatura 33

A V´ystupy NIST STS 35

B Seznam pouˇzit´ych zkratek 51

C Obsah pˇriloˇzen´eho CD 53

x

(13)

Seznam obr´ azk˚ u

1.1 Klasifikace RNG . . . 4

1.2 Obecn´a struktura PRNG . . . 5

1.3 Fibonacciho LFSR s vnˇejˇs´ı zpˇetnou vazbou . . . 6

1.4 Galo˚uv LFSR s vnitˇrn´ı zpˇetnou vazbou . . . 6

1.5 Obecn´a struktura TRNG . . . 7

2.1 TERO obvod . . . 11

2.2 pr˚ubˇeh sign´al˚u TERO obvodu . . . 12

2.3 stavba TERO TRNG . . . 12

2.4 Blokov´e sch´ema Intel TRNG . . . 13

2.5 Stavba PLL konstrukce TRNG Fischer-Drutarovsk´y . . . 14

2.6 TRNG konstrukce Fischer-Drutarovsk´y . . . 14

2.7 Princip Atmel AVR TRNG . . . 15

3.1 Princip clock jitteru v TRNG . . . 17

3.2 Sch´ema ˇc´ıtaˇce 14 v TRNG . . . 18

3.3 Mikrokontrol´er STM32F030R8T6 . . . 19

3.4 Sch´ema nastaven´ı hodin mikrokontrol´eru . . . 20

4.1 Histogram mˇeˇren´ı 1 . . . 23

(14)

(15)

Seznam tabulek

5.1 Výsledky test˚u NIST STS jednotlivých bit˚u. . . 29 5.2 Výsledky test˚u NIST STS spojených bit˚u. . . 29

(16)

(17)

Uvod ´

Motivace

Chytrá elektronická zaˇr´ızen´ı jsou jiˇz ned´ılnou souˇcást´ı bˇeˇzného ˇzivota. At’

uˇz se jedná o mobil, notebook nebo televizi. Stále v´ıce podobných vynález˚u nab´ız´ı nové moˇznosti pouˇzit´ı, proto jsou vybavena operaˇcn´ım systémem ˇci po- dobným softwarem a umoˇzˇnuj´ı pˇripojen´ı k internetu. To s sebou nese bezpeˇc- nostn´ı rizika. Proto je potˇreba zaˇr´ızen´ı chránit pˇred útoˇcn´ıky. Témˇeˇr kaˇzdý za- bezpeˇcený protokol stoj´ı na základu náhodných ˇc´ısel a generátoru náhodných ˇ

c´ısel.

C´ıle pr´ ace

C´ılem reˇserˇsn´ı ˇcásti této práce je seznámen´ı se s problematikou generátor˚u náhodných ˇc´ısel a jejich klasifikac´ı s d˚urazem na TRNG vhodné pro mikro- kontroléry. Dále pak prozkoumán´ı existuj´ıc´ıch typ˚u konstrukc´ı TRNG.

Praktická ˇcást této práce se vˇenuje návrhu a konkrétn´ı implementaci TRNG na mikrokontroléru s procesorem ARM Cortex-M0. Proveden´ı mˇeˇren´ı a sta- tistickému vyhodnocen´ı dané implementace.

(18)

(19)

Kapitola 1

Gener´ atory n´ ahodn´ ych ˇ c´ısel

Tato kapitola se vˇenuje pˇredstaven´ı pojmu generátory náhodných ˇc´ısel, jejich klasifikaci.

1.1 Gener´ atory n´ ahodn´ ych ˇ c´ısel

Problematika náhodných generátor˚u RNG (Random Number Generator) je velmi diskutované a stále aktuáln´ı téma. Náhodná ˇc´ısla maj´ı ˇsiroké vyuˇzit´ı ve statistice, simulac´ıch, poˇc´ıtaˇcových hrách a dalˇs´ıch oblastech [1].

Náhodná ˇc´ısla jsou ned´ılnou souˇcást´ı modern´ı kryptografie. Pouˇz´ıvaj´ı se hlavnˇe k vytváˇren´ı kl´ıˇc˚u v ˇsifrovac´ıch algoritmech jako RSA, Diffie-Hellman nebo AES. Nacházej´ı vyuˇzit´ı pˇri generován´ı vyplˇnuj´ıc´ıch bit˚u, které slouˇz´ı k rozˇs´ıˇren´ı krátkých zpráv na pevný poˇcet bit˚u bez naruˇsen´ı pouˇzité ˇsifry.

Z tohoto d˚uvodu jsou RNG souˇc´ast´ı mnoha produkt˚u v oblasti IT bezpeˇcnosti a kladou se na nˇe striktn´ı poˇzadavky.

Generátor náhodných bit˚u je zaˇr´ızen´ı nebo algoritmus, jehoˇz výstupem je posloupnost statisticky nezávislých a objektivn´ıch binárn´ıch ˇc´ıslic. Ten m˚uˇze být pouˇzit ke generován´ı náhodných ˇc´ısel [2].

Pˇredevˇs´ım mus´ı vytváˇret data pouˇzitelná pro kryptografické aplikace. Po- kud generovaná data nejsou opravdu náhodná a jistou formou se daj´ı pˇred- pov´ıdat, útoˇcn´ık m˚uˇze snadno uhodnout kl´ıˇc ˇsifry z omezeného poˇctu moˇz- nost´ı. Nen´ı vylouˇceno, ˇze se útoˇcn´ık pokus´ı aktivnˇe napadnout RNG, aby urˇcil, nebo dokonce manipuloval s generovanými daty. Proto by RNG mˇel poskyto- vat schopnost odolat tˇemto druh˚um útok˚u. Dalˇs´ım uvaˇzovaným poˇzadavkem je rychlost produkce dat pro nˇekteré ˇcasovˇe nároˇcné aplikace. ˇSpatnˇe navrˇzený RNG m˚uˇze oslabit bezpeˇcnost celého systému.

V roce 2010 doˇslo k prolomen´ı bezpeˇcnosti Sony Playstation 3. Konzole ovˇeˇrovala svoje soubory pomoc´ı podpisu. Jeho vytvoˇren´ı vyˇzadovalo n´ahodn´e ˇ

c´ıslo. Chybou gener´atoru se pro kaˇzd´y podpis pouˇz´ıvala konstantn´ı hodnota.

Utoˇ´ cn´ıci tuto slabinu odhalili a d´ıky tomu mohli podepisovat vlastn´ı soubory.

(20)

1. Generátory náhodných ˇc´ısel

Obr´azek 1.1: Klasifikace RNG¹

Coˇz jim umoˇznilo nahrát do konzole zmˇenˇený operaˇcn´ı systém a pouˇstˇet ne- legáln´ı software.

1.2 Klasifikace gener´ ator˚ u n´ ahodn´ ych ˇ c´ısel

I kdyˇz existuj´ı r˚uzná hlediska klasifikace RNG, podle schématu 1.1 rozdˇelu- jeme RNG do dvou skupin. Prvn´ı skupina zahrnuje pseudonáhodné generátory ˇc´ısel PRNG (Pseudo Random Number Generator) nazývané nˇekterými autory deterministické RNG. Na vstup dostanou poˇcáteˇcn´ı hodnotu tzv. seed a z n´ı algoritmicky generuj´ı pseudonáhodná ˇc´ısla.

Druhou skupinu tvoˇr´ı generátory opravdu náhodných ˇc´ısel TRNG (True Random Number Generator), které se rozliˇsuj´ı na fyzické a nefyzické. Zdrojem náhodnosti fyzických TRNG jsou jevy elektrických obvod˚u. Napˇr. ˇsum ze Ze- nerovy diody, teplotn´ı ˇsum v polovodiˇc´ıch, volnˇe beˇz´ıc´ı oscilátory apod. Nebo fyzikáln´ı jevy jako záˇren´ı pˇri radioaktivn´ım rozpadu, ˇci jiné kvantové procesy.

Nefyzické TRNG vyuˇz´ıvaj´ı náhodné události jako vyhledávac´ı ˇcas pevného disku, obsah pamˇeti RAM, interakce uˇzivatele.

1.3 PRNG

Metody produkuj´ıc´ı náhodná ˇc´ısla pomoc´ı deterministického algoritmu nazý- váme pseudonáhodnými generátory ˇc´ısel [1]. Deterministický nazýváme algoritmus, který pro stejné vstupy má stejný pr˚ubˇeh. Jinými slovy vstup jeho bˇeh jednoznaˇcnˇe urˇc´ı. Obrázek 1.2 ilustruje strukturu PRNG. Na zaˇcátku PRNG pˇrijme na vstupu ˇretˇezec bit˚u nazývaný seed, kter´y urˇc´ı prvn´ı vnitˇrn´ı stav generátoru s₀ a jeho bˇeh. Funkce Ψ na základˇe vnitˇrn´ıho stavu vypoˇcte náhodnou hodnotu r_n. Potom se z aktuáln´ıho vnitˇrn´ıho stavu s_n vypoˇcte nový

1Pˇrevzato z [3]

4

(21)

1.3. PRNG

Obr´azek 1.2: Obecn´a struktura PRNG²

vnitˇrn´ı stav s_n+1 pomoc´ı funkce φ a celý cyklus se opakuje. Aˇckoliv algoritmicky generovaná ˇc´ısla nem˚uˇzou být opravdu náhodná a s urˇcitou periodou se opakuj´ı, má tato skupina generátor˚u i své výhody. Mohou být mnohem rych- lejˇs´ı a jejich výsledky jsou opakovatelné. Napˇr´ıklad m˚uˇzeme provést stejnou simulaci kdyˇz známe seed.

1.3.1 Kryptograficky bezpeˇcn´e PRNG

Zaj´ımavou podskupinou jsoukryptograficky bezpeˇcn´ePRNG - CSPRNG (Cryp- tographically Secure Pseudo-random Number Generator). Pro nˇe plat´ı, ˇze splˇnuj´ı n´asleduj´ıc´ı vlastnosti:

• Mus´ı proj´ıt statistick´ymi testy n´ahodnosti.

• Next-bit test: Pokud známe prvn´ıchkbit˚u náhodné sekvence, neexistuje algoritmus, který v polynomiáln´ım ˇcase pˇredpov´ı (k+1) bit s pravdˇepo- dobnost´ı vˇetˇs´ı neˇz 1/2.

• Odhalen´ı stavu: V pˇr´ıpadˇe ˇze je odhalen vnitˇrn´ı stav, nen´ı moˇzn´e zpˇetnˇe zrekonstruovat generovanou sekvenci do tohoto okamˇziku.

• Odolnost proti zpˇetné rekonstrukci: Pokud generátor pˇri bˇehu vyuˇz´ıvá dalˇs´ı zdroj entropie, znalost aktuáln´ıho vnitˇrn´ıho stavu nestaˇc´ı k pˇredpo- vˇezen´ı vnitˇrn´ıch stav˚u v dalˇs´ıch iterac´ıch.

1.3.2 Z´astupci PRNG

V této podsekci uvád´ıme pro úplnost nˇekteré typy PRNG.

2Pˇrevzato z [3]

(22)

1 13 11

14 16

Obr´azek 1.3: Fibonacciho LFSR s vnˇejˇs´ı zpˇetnou vazbou³

1 11

14 13 16

Obrázek 1.4: Galo˚uv LFSR s vnitˇrn´ı zpˇetnou vazbou⁴ Lineárn´ı kongruenˇcn´ı generátor

Lineárn´ı kongruenˇcn´ı generátor LCG je jedn´ım z nejznámˇejˇs´ıch a ˇsiroce pouˇz´ı- vaných PRNG zvlaˇstˇe v simulaˇcn´ıch aplikac´ıch. Definuje se pomoc´ı reku- rentn´ıho pˇredpisu:

X_n+1 = (aX_n+c) mod m

Kde X je posloupnost pseudonáhodných ˇc´ısel a X₀ je poˇcáteˇcn´ıseed. Kva- lita generátoru závis´ı na volbˇe násobku a, inkrementu c a modulu m, coˇz jsou parametry LCG. Pro kryptografii se nehod´ı, pokud známe nˇekolik hodnot X_i, m˚uˇzeme postupnˇe odvodit jeho parametry jak popisuje [4].

Posuvn´y registr s line´arn´ı zpˇetnou vazbou

Tento typ se pouˇz´ıvá ke generován´ı sekvence binárn´ıch bit˚u. Vstupn´ı bit je výsledek lineárn´ı funkce dvou nebo v´ıce bit˚u. D´ıky snadné hardwarové implementaci se hodnˇe pouˇz´ıvá. Opˇet nen´ı vhodný pro kryptografii, hodnoty m˚uˇzeme pˇredpov´ıdat pomoc´ı Berlekamp-Massey algoritmu [5].

V této práci se PRNG jiˇz v´ıce nezabýváme a zv´ıdavého ˇctenáˇre odkazujeme na pˇr´ısluˇsnou literaturu.

1.4 TRNG

Jak zmiˇnuje [7], TRNG je zaˇr´ızen´ı, které vyuˇz´ıvá fyzikáln´ı procesy ke ge- nerován´ı náhodné posloupnosti bit˚u. Obrázek 1.5 zobrazuje stavbu TRNG.

Základem je zdroj ˇsumu vznikaj´ıc´ı v elektrických obvodech ( napˇr. nestabilita napˇet´ı na polovodiˇcových souˇcástkách ), nebo zp˚usobený fyzikáln´ımi jevy (napˇr. radioaktivn´ı rozpad). Zdroj ˇsumu vytváˇr´ı v ˇcase nepˇretrˇzité analogové signály, které jsou v jisté fázi opakovanˇe pˇrevádˇeny do digitáln´ıch binárn´ıch

3Pˇrevzato z [6]

4Pˇrevzato z [6]

6

(23)

1.4. TRNG

Obr´azek 1.5: Obecn´a struktura TRNG⁵

hodnot. Ve schématu se nazývaj´ıdas random numbers. Tato ˇc´ısla m˚uˇzou být následnˇe algoritmicky zpracována na vnitˇrn´ı náhodná ˇc´ısla, aby se sn´ıˇzily jejich potenciáln´ı slabiny. Zpracován´ı m˚uˇze prob´ıhat bez pamˇeti, ale to záleˇz´ı na konkrétn´ım pˇr´ıpadˇe. Nav´ıc silný zdroj ˇsumu nutnˇe nevyˇzaduje následné zpra- cován´ı. Nakonec pˇri vnˇejˇs´ım poˇzadavku jsou intern´ı náhodná ˇc´ısla pˇredána na výstup.

1.4.1 Stavebn´ı bloky TRNG

Aˇckoliv existuje mnoho typ˚u TRNG, nejpopulárnˇejˇs´ı a nejuˇziteˇcnˇejˇs´ı se bˇeˇznˇe skládaj´ı z následuj´ıc´ıch tˇr´ı komponent:

Zdroj entropie

Cetn´ˇ e konstrukce TRNG jak bylo ˇreˇceno v literatuˇre sb´ıraj´ı náhodnost z fy- zikáln´ıch proces˚u jako teplotn´ı nebo výstˇrelový ˇsum v obvodech, jitter, nestabilita signálu v obvodech, Brown˚uv pohyb, atmosférický ˇsum, nebo dokonce radioaktivn´ı rozpad. Zdroj entropie je pravdˇepodobnˇe nejd˚uleˇzitˇejˇs´ı z komponent, protoˇze urˇcuje výslednou entropii. Na druhou stranu je jasné ˇze zdroje jako atmosférický ˇsum a radioaktivn´ı rozpad jsou poˇzitelné pro omezené aplikace nebo online distribuované sluˇzby [8]. Nav´ıc nˇekteré zdroje maj´ı sklony, které by mˇely být eliminovány v kroc´ıch sbˇeru nebo následném zpracován´ı. Kvanti- fikace celkové entropie a jejich statistických vlastnost´ı je dalˇs´ı úkol konstrukce.

Jiným problémem jsou dlouhodobé efekty, které mohou zp˚usobit selhán´ı zdroje entropie. Existuj´ı aktivn´ı monitorovac´ı techniky detekuj´ıc´ı totáln´ı selhán´ı.

Nicm´enˇe jemn´e chyby se tˇeˇzko v praxi detekuj´ı.

Technika sbˇeru

Zdroj entropie zaznamenáváme pouˇzit´ım techniky sbˇeru, která v ideáln´ım pˇr´ıpadˇe nenaruˇs´ı fyzikáln´ı proces a sesb´ırá nejvyˇsˇs´ı moˇznou entropii. Mnoho konstrukc´ı realizuje tento krok. Vzhledem k tomu, ˇze neexistuje jiný zp˚usob

5Pˇrevzato z [3]

(24)

analýzy výstupu TRNG neˇz statistickými testy a jednoduchými testy oprav- dové náhodnosti (Tot a restart testy), mechanismus sbˇeru by mˇel m´ıt pˇresné zd˚uvodnˇen´ı. Jednoduˇse ˇreˇceno, Tot testy kontroluj´ı celkové selhán´ı zdroje entropie RNG obvykle zp˚usobeného vlivem stárnut´ı materiálu nebo extrém- n´ım kol´ısán´ım v provozn´ıch podm´ınkách. Restart testy ovˇeˇruj´ı generován´ı náhodnosti restartován´ım RNG za témˇeˇr stejných provozn´ıch podm´ınek.

Následné zpracován´ı

Aˇckoliv tato souˇcást nen´ı vyˇzadována ve vˇsech pˇr´ıpadech, dobrá konstrukce pˇrikazuje pouˇz´ıt postprocessing. C´ılem je zvýˇsit robustnost konstrukce TRNG pouˇzit´ım následného zpracován´ı výstupn´ıch bit˚u. Postprocessing se vyuˇz´ıvá ke skryt´ı nebo eliminaci výkyv˚u anebo závislost´ı ve zdroji entropie nebo mechanismu sbˇeru. Druhý c´ıl, který z´ıskal na d˚uleˇzitosti kv˚uli aktivn´ım útok˚um na selhán´ı systému a útok˚um postrann´ımi kanály, je poskytnout odolnost proti zmˇenám prostˇred´ı a proti manipulaci útoˇcn´ıky. Postprocessing m˚uˇze realizovat jednoduchý von Neumann˚uv korektor nebo komplikovanˇejˇs´ı extrakˇcn´ı funkce nebo jednosmˇerná haˇsovac´ı funkce jako SHA-1. I kdyˇz jednosmˇerná haˇsovac´ı funkce jako SHA-1 nebo MD5 poskytuje bezpeˇcnost pˇri pouˇzit´ı v následném zpracován´ı, komplikuj´ı analýzu rozdˇelen´ı výstupu.

1.4.2 Poˇzadavky TRNG

T´ım pádem existuje velké mnoˇzstv´ı konstrukc´ı TRNG. Jednotlivé typy se zna- telnˇe liˇs´ı podle zdroj˚u entropie nebo pouˇzité techniky sbˇeru. Kaˇzdá konstrukce má své silné a slabé stránky. Nˇekteré z tˇechto vlastnost´ı se týkaj´ı výkonu a jiné bezpeˇcnosti a robustnosti. Nˇekteré poˇzadavky na TRNG shrnuje [7].

• Z praktického hlediska je nezbytné vyrábˇet TRNG pomoc´ı bˇeˇzného kˇrem´ıkového procesu. Nav´ıc je vysoce ˇzádouc´ı implementovat TRNG pouˇzit´ım ˇcistˇe digitáln´ı techniky. To dovoluje snadnˇejˇs´ı integraci s di- gitáln´ımi mikroprocesory a moˇznost implementovat TRNG na populár- n´ıch konfigurovatelných platformách ( napˇr. FPGA a CPLD ).

• Kompaktn´ı a efektivn´ı konstrukce s vysokou propustnost´ı dané prosto- rem a vyuˇzitou energi´ı. Vyvarovat se pouˇzit´ı zesilovaˇc˚u a jiných analo- gových souˇcástek pokud je to moˇzné. Analogové souˇcástky maj´ı tendenci spotˇrebovat v´ıce energie a zt´ıˇzit analýzu. Poznamenejme, ˇze protoˇze za- kazujeme analogové komponenty, mus´ıme vzorkovat zmˇeny v ˇcase jinak neˇz pomoc´ı úrovnˇe napˇet´ı. V pˇr´ıpadˇe striktn´ıho dodrˇzen´ı tohoto kritéria bychom nemˇeli pouˇz´ıvat komplikovaná schémata následného zpracován´ı (napˇr. SHA-1), nebo je alespoˇn implementovat v softwaru.

• Je ˇzádouc´ı m´ıt matematické zd˚uvodnˇen´ı mechanismu sbˇeru entropie a vˇsechny pˇredpoklady empiricky ovˇeˇrit. Návrh by mˇel být dostateˇcnˇe 8

(25)

1.5. Praktické pouˇzit´ı RNG jednoduchý, aby umoˇznil pˇresnou analýzu. K ovˇeˇren´ı výstupu TRNG se pouˇz´ıvaj´ı testovac´ı sady jako DIEHARD [9] nebo NIST [10].

1.4.3 Techniky následného zpracován´ı TRNG

V praxi existuj´ı r˚uzné moˇznosti následného zpracován´ı. Zde prezentujeme ty nejobvyklejˇs´ı, jak je uvedeno v [7].

• Kryptografick´e haˇsovac´ı funkce:

pravdˇepodobnˇe nejpopulárnˇejˇs´ı technikou je pouˇz´ıt kryptograficky sil- nou haˇsovac´ı funkci (SHA-1) na výstup TRNG. Napˇr´ıklad Intel RNG pouˇz´ıvá SHA-1. Z hlediska výkonu se implementován´ı plnohodnotné haˇsovac´ı funkce v TRNG jev´ı jako pˇrehnané. Avˇsak pokud je vhodnˇe implementovaná má d˚uleˇzitý pˇr´ınos z hlediska bezpeˇcnosti - pokud selˇze zdroj náhodnosti tak TRNG ”pouze” degraduje na PRNG.

• Von Neumann˚uv korektor:

jde o jednu z nejstarˇs´ıch a nejznámˇejˇs´ıch technik. Pouˇz´ıvá se k potlaˇcen´ı lokáln´ıch výkyv˚u náhodných hodnot. Pˇrij´ımá na vstupu dva bity a pokud jsou stejné (oba 0 nebo 1) odstran´ı je z posloupnosti náhodných bit˚u, pokud jsou odliˇsné, pouˇzije se jeden z bit˚u - napˇr´ıklad prvn´ı. Rych- lost výstupu je pak zpomalena pˇribliˇznˇe o jednu ˇctvrtinu. Jeho velkou výhodou je snadná implementace.

1.5 Praktick´ e pouˇ zit´ı RNG

CSPRNG

• generov´an´ı kl´ıˇc˚u asymetrick´e kryptografie

• generov´an´ı hodnot na jedno pouˇzit´ı tzv.nonce (number used once)

• solen´ı v digit´aln´ıch podpisech

• jednor´azov´e ˇsifry (one-time pad)

1.6 Aplikace RNG

V této kapitole zmiˇnujeme nˇekteré konkrétn´ı aplikace RNG.

• CSPRNG na linuxu dostupn´y jako/dev/randoma /dev/urandom

• CSPRNG implementovaný v OpenSSL pouˇz´ıvaný ke generován´ı kl´ıˇc˚u asymetrické kryptografie (napˇr. RSA SSH kl´ıˇce)

(26)

• TrusZone RNG - skládá se ze dvou ˇcást´ı - hardwarového TRNG, který generuje seed pro softwarový PRNG

• TL200 - hardwarov´y TRNG s USB rozhran´ım, vestavˇen´y posprocessing (napˇr. SHA-512)

10

(27)

Kapitola 2

Typy konstrukc´ı TRNG

V této sekci se zabýváme pˇrehledem nejznámˇejˇs´ıch konstrukc´ı TRNG.

2.1 TERO TRNG

Hlavn´ı souˇcást´ı tohoto typu TRNG je elektronický obvod TERO (Transient Effect Ring Oscilator), který doˇcasnˇe osciluje. Skládá se ze sudého poˇctu inver- tor˚u a páru hradel, který restartuje doˇcasné oscilace (napˇr. dvˇe hradla NAND nebo XOR). Typické schéma TERO obvodu zobrazuje 2.1. Skládá se ze dvou hradel NAND a dvou vˇetv´ı s invertory. TERO obvod m˚uˇzeme chápat jako RS klopný obvod se dvˇema vstupy stejného napˇet´ı V_ctr a dvˇema rozd´ılnými výstupy V_out1 a V_out2.

Pˇri nábˇeˇzné hranˇe vstupu V_ctr, výstupy V_out1 a V_out2 zaˇcnou oscilovat.

Oscilace maj´ı v pr˚umˇeru konstantn´ı frekvenci, ale jejich stˇr´ıda se ˇcasem mˇen´ı.

Stˇr´ıda je pomˇer ˇcas˚u obdéln´ıkového signálu v jednotlivých úrovn´ıch. Stˇr´ıda se mˇen´ı monotónnˇe a po urˇcitém poˇctu oscilac´ı dosáhne pomˇeru 0%, nebo 100%.

V této chv´ıli výstupy V_out1 a V_out2 pˇrestanou oscilovat a ustál´ı se ve dvou navzájem opaˇcných logických hodnotách. Obrázek 2.2 ukazuje pr˚ubˇeh signál˚u vstupu V_ctr a výstupu V_out1 namˇeˇrený osciloskopem. Jak vid´ıme, po nábˇeˇzné hranˇe ˇr´ıd´ıc´ıho signálu V_ctrzaˇcne výstup V_out1 oscilovat.

6Pˇrevzato z [11]

. . .

V

_ctr

V

_out2

V

_out1

. . .

Obr´azek 2.1: TERO Obvod⁶

(28)

2. Typy konstrukc´ı TRNG

V

_out1

V

_ctr

Obr´azek 2.2: pr˚ubˇeh sign´al˚u TERO obvodu⁷

cnt[0]

Counter of rising edges

clk reset

cnt[7:0]

8 _Random

bit output Request of

a random bit

. . . . . .

Obr´azek 2.3: stavba TERO TRNG⁸

Tˇri pˇribl´ıˇzené pohledy ukazuj´ı zmˇenu stˇr´ıdy v ˇcase, která postupnˇe klesá, aˇz se signál V_out1ustál´ı v hodnotˇe logická 0.

Poˇcet oscilac´ı pˇredt´ım, neˇz se výstup stabilizuje se vˇzdy liˇs´ı, protoˇze ho ovlivˇnuje elektrický ˇsum, který naruˇsuje normáln´ı chován´ı tranzistor˚u TERO obvodu.

Strukturu tohoto typu TRNG zobrazuje 2.4. Jiˇz zm´ınˇený TERO obvod je napojen na ˇc´ıtaˇc, který poˇc´ıtá nábˇeˇzné hrany doˇcasných oscilac´ı. Náhodná binárn´ı posloupnost obvykle vzniká spojen´ım nejniˇzˇs´ıch bit˚u ˇc´ıtaˇce.

2.2 Intel TRNG

Tento typ je popsán v [12]. Vzorkuje teplotn´ı ˇsum zes´ılen´ım napˇet´ı namˇeˇre- ném na nevybuzených rezistorech. Nav´ıc k velké náhodné ˇcásti jsou tato

7Pˇrevzato z [11]

8Pˇrevzato z [11]

12

(29)

2.3. Konstrukce Fischer-Drutarovsk´y

Noise Amplifier Johnson Thermal

Noise Source (Resistor)

Digital Corrector Super Latch

FIFO

Voltage Controlled

Oscillator

High- Speed Oscillator

Control/

Status Reg.

Bus

Obrázek 2.4: Blokové schéma Intel TRNG⁹

mˇeˇren´ı ovlivnˇena pseudonáhodnými vlastnostmi prostˇred´ı jako elektromagne- tické záˇren´ı, teplota a kol´ısán´ı zdroje napájen´ı. Odeˇcten´ım signál˚u namˇeˇrených na dvou sousedn´ıch rezistorech Intel RNG znatelnˇe sn´ıˇz´ı párové souˇcásti.

Dále se vyuˇz´ıvá dvou volnˇe bˇeˇz´ıc´ıch oscilátor˚u. Jeden je rychlý a druhý mnohem pomalejˇs´ı. Teplotn´ı ˇsum se pouˇz´ıvá k modulován´ı frekvence poma- lejˇs´ıho hodinového signálu. Ten je pouˇzit k aktivován´ı mˇeˇren´ı rychlejˇs´ıch hodin. Odchylky tˇechto dvou hodin poskytuj´ı zdroj náhodných binárn´ıch ˇc´ıslic.

2.3 Konstrukce Fischer-Drutarovsk´ y

Tento TRNG je zaloˇzen na analogovém Phase-Locked Loop (PLL). Návrh byl implementován v Altera Field Programmable Logic Device (FPLD). Kon- strukce je unikátn´ı v tom, ˇze ˇslo o prvn´ı TRNG, který byl c´ılen na FPGA. Jak zobrazuje 2.5 vzorkuje se jitter hodinového signálu generovaného PLL pomoc´ı zpoˇzdˇených kaskádových vzorkovaˇc˚u, sestavených dle schématu na obrázku 2.6.

Kl´ıˇcovou myˇslenkou je pouˇz´ıt v´ıce vzorkovaˇc˚u, aby bylo moˇzné vzorkovat pˇrechodovou zónu, která je ovlivnˇená jitterem, který podle [13] prob´ıhá v ˇrádu des´ıtek pikosekund. Vzorky zaznamenané v pravidelných intervalech jsou zkombinovány dohromady pomoc´ı funkce XOR. Výsledkem je vzorek z oblasti kˇrivky signálu, která má potˇrebnou náhodnost. Tento návrh je zaj´ı- mavý, protoˇze osvˇetluje potˇrebu stavˇet TRNG na rekonfigurovatelných plat- formách.

9Pˇrevzato z [12]

10Pˇrevzato z [7]

11Pˇrevzato z [7]

(30)

2. Typy konstrukc´ı TRNG

phase comparator voltage controlled oscillator

F_INm/ (n*k)

F_IN 1/n VCO 1/k

1/m Clock Shift

Circuitry 1/v F_INm/ (n*v)

Obrázek 2.5: Stavba PLL pouˇzité jako zdroje entropie konstrukce TRNG Fischer-Drutarovský¹⁰

f_clk

..

. Q

Q

PLL D

D

D T T

T

.

1/k

Obr´azek 2.6: TRNG konstrukce Fischer-Drutarovsk´y¹¹

2.4 TRNG na Atmel AVR

Následuj´ıc´ı konstrukce je popsána v [14]. I kdyˇz 8 bitové mikrokontroléry série AVR nemaj´ı pˇr´ımo urˇcený hardware ke generován´ı náhodných ˇc´ısel, ukázalo se, ˇze je moˇzné pouˇz´ıt jako zdroj entropie vestavˇený oscilátor bez dalˇs´ıch souˇcástek nebo úprav. Vyuˇz´ıvá se faktu, ˇze mikrokontrolér Atmega 169 na desce AVR Butterfly m˚uˇze pˇristupovat k nˇekolika oscilátor˚um. Základn´ı kon- figurace pouˇz´ıvá ˇcipový RC oscilátor jako systémové hodiny. M˚uˇze vyuˇz´ıvat i jiný oscilátor s externˇe pˇripojeným krystalem jako generátorem pulz˚u pro jednotku ˇcasovaˇc / ˇc´ıtaˇc 2.

Tyto oscilátory nejsou nikdy ideálnˇe stabiln´ı. Jejich frekvence ovlivˇnuje mnoho fyzikáln´ıch vliv˚u jako napájec´ı napˇet´ı, provozn´ı teplota ˇci pˇrirozené vlastnosti jitteru. Dopady tˇechto vliv˚u jsou znatelnˇe odliˇsné pro kaˇzdý os- cilátor. Krystalový oscilátor je mnohem v´ıce stabiln´ı v ˇsiroké ˇskále provozn´ıch podm´ınek. Zat´ımco RC oscilátor vykazuje patrné odchylky i kdyˇz je kalibro- vaný. I kdyˇz je mikrokontrolér ve stabiln´ım prostˇred´ı a napájen stabilizovaným zdrojem napˇet´ı, RC oscilátor vykazuje jednoduˇse mˇeˇritelný jitter.

Princip fungován´ı je na obrázku 2.7. Zdrojem entropie je jitter RC os- cilátoru. Krystalový oscilátor byl pouˇzit k periodickému ˇcasován´ı (1 sekunda), a za tu dobu se namˇeˇril poˇcet pulz˚u RC oscilátoru. V ideáln´ım svˇetˇe by byl vˇzdy stejný, avˇsak reálnˇe byly pozorovány odchylky aˇz 2¹² pulz˚u mezi 14

(31)

2.4. TRNG na Atmel AVR

Obrázek 2.7: Princip Atmel AVR TRNG¹² následnými mˇeˇren´ımi.

Ke generován´ı náhodných bit˚u se pouˇz´ıvá následuj´ıc´ı metoda. ˇC´ıtaˇc / ˇ

casovaˇc 1 poˇc´ıtá pulzy systémového RC oscilátoru a bˇeˇz´ı na 2 MHz. ˇC´ıtaˇc 2 vyuˇz´ıvá krystalový oscilátor (32,768 kHz) a odpov´ıdaj´ıc´ı nastaven´ı pˇreddˇeliˇcky generuje pˇreruˇsen´ı kaˇzdou 1 sekundu. V obsluze pˇreruˇsen´ı se pˇreˇcte hodnota ˇ

c´ıtaˇce / ˇcasovaˇce 1 a ˇc´ıtaˇc je vynulován. Pak jsou z 16 bitové hodnoty extra- hovány bity 1 aˇz 8 a pˇredány na výstup jako ˇcást generované posloupnosti náhodných bit˚u.

12Pˇrevzato z [14]

(32)

(33)

Kapitola 3

N´ avrh a implementace

V této kapitole popisujeme návrh a implementaci vlastn´ıho TRNG na mikro- kontroléru.

3.1 Popis implementace

Pˇri navrhován´ı TRNG vycház´ıme z [15]. Na rozd´ıl od citovaného návrhu pouˇz´ıváme 32 bitový mikrokontrolér STM32F030R8T6 [16] se stejným procesorem tj. ARM-CORTEX-M0. Zdrojem náhodnosti je nestabilita hodinového signálu tzv. clock jitter. Princip zobrazuje sch´ema 3.1. Generátor pouˇz´ıvá dva nezávislé oscilátory. Jedn´ım z nich je vysokorychlostn´ı intern´ı oscilátor HSI (High Speed Internal) kmitaj´ıc´ı na frekvenci 48 MHz a druhý je po- malejˇs´ı extern´ı krystalový oscilátor LSE (Low Speed External) s frekvenc´ı 32,768 KHz, který nahrazuje vnitˇrn´ı 40 KHz LSI (Low Speed Internal) krys- tal v p˚uvodn´ım návrhu. Po pˇredem urˇceném poˇctu pulz˚u LSE zmˇeˇr´ıme poˇcet period uplynulých na HSI oscilátoru. V ideáln´ım pˇr´ıpadˇe bude hodnota vˇzdy konstantn´ı, ale v realitˇe zp˚usob´ı ˇsum odchylky, které se daj´ı pouˇz´ıt pˇri gene- rován´ı náhodných ˇc´ısel. Tyto hodnoty maj´ı gaussovské rozdˇelen´ı.

13Pˇrevzato z [15]

Clock jitter Expected period LSI

oscillator HSI oscillator

Gaussian distribution Period time Probability

Obr´azek 3.1: Princip clock jitteru v TRNG¹³

(34)

3. N´avrh a implementace

Frequency Divider *

/1,2 … 128 Prescaler

/1,2,4,8 PLLCLK

HSI HSI48 HSI14 HSE SYSCLK LSI LSE

MCO pin GPIO pin

HSE/32 RTCCLK TI1_RMP MCO

Edge

detector Capture

register Autoreload

counter

Interrupt or DMA request Timer 14 capture mode

Internal Clock

Obr´azek 3.2: Sch´ema ˇc´ıtaˇce 14 v TRNG. *Naˇsemu modelu chyb´ı dˇeliˇcka frekvence MCO pinu.¹⁴

C´ıtaˇˇ c 14 (Timer 14) v zachytávac´ım módu pouˇz´ıváme k mˇeˇren´ı period HSI. Nastaven´ı je znázornˇeno na obrázku 3.2. Oscilátor LSE je pˇres prvn´ı multiplexor vyveden na MCO (microcontroller clock output) pin, který se pouˇz´ıvá jako zdroj pulz˚u vstupuj´ıc´ı do detektoru hran (Edge detector). Ten je nastaven, aby reagoval na kaˇzdou nábˇeˇznou hranu. Dále pomoc´ı pˇreddˇeliˇcky (Prescaler) m˚uˇzeme zvolit poˇcet pulz˚u (1, 2, 4, 8) potˇrebných k aktivován´ı záchytného (capture) registru. Pˇri takové události se aktuáln´ı hodnota ˇc´ıtaˇce napojeného na HSI zaznamená v capture registru a pˇr´ıpadnˇe se vyvolá odpov´ıdaj´ıc´ı pˇreruˇsen´ı.

3.2 Hardware

Pouˇz´ıváme mikrokontrolér STMF030R8T6 [16] s 32bitovým procesorem ARM- Cortex-M0 s nastavitelným kmitoˇctem v rozsahu 8 - 48 MHz viz. obrázek 3.3.

Uˇzivatel m´a k dispozici:

• zelenou LED diodu s oznaˇcen´ım LD2, kterou m˚uˇze programovˇe ovl´adat

• modr´e tlaˇc´ıtko B1, na jehoˇz stisk m˚uˇze program reagovat

• ˇcern´e tlaˇc´ıtko B2, jenˇz slouˇz´ı k resetu mikrokontrol´eru

Pˇr´ıpravek je napájen mikro USB konektorem, který zároveˇn slouˇz´ı k pˇripojen´ı kontroléru k poˇc´ıtaˇci. T´ımto zp˚usobem se do mikrokontroléru nahrávaj´ı pro- gramy a prob´ıhá komunikace s poˇc´ıtaˇcem pˇres sériovou linku.

Deska je osazena tˇremi oscilátory. Dva z nich jsou integráln´ı souˇcást´ı pro- cesoru (HSI, LSI) a tˇret´ı je extern´ı krystalový oscilátor (LSE). Deska nab´ız´ı moˇznost dodateˇcné instalace HSE (High Speed External) oscilátoru.

Mikrokontrol´er je vybaven flash pamˇet´ı 64KB, kter´a slouˇz´ı k uloˇzen´ı programu.

14Pˇrevzato z [15]

18

(35)

3.3. Program

Obr´azek 3.3: Mikrokontrol´er STM32F030R8T6

3.3 Program

Program pro mikrokontrolér je vyvinut v jazyku C. K vývoji pouˇz´ıváme oficiáln´ı vývojové prostˇred´ı ARM Keil, bˇeˇz´ıc´ı na Windows. Jeho úkolem je zdrojový kód v jazyku C pˇreloˇzit do spustitelné binárn´ı podoby, bˇeˇz´ıc´ı na pro- cesoru ARM a také pomoc´ı sériové linky program nahrát do mikrokontroléru.

ARM Keil nab´ız´ı obvyklý standard pro vývojáˇrskou práci jako je krokován´ı programu, breakpointy, ˇci zobrazován´ı hodnot promˇenných.

F´aze bˇehu programu v mikrokontrol´eru:

• nastaven´ı hodin (oscil´ator˚u)

• nastaven´ı s´eriov´e linky

• nastaven´ı ˇc´ıtaˇce 14

• nastaven´ı pˇreruˇsen´ı

• ˇcek´an´ı na znak ”s”

• odesl´an´ı hodnoty do poˇc´ıtaˇce

Po nahrán´ı programu do mikrokontroléru pomoc´ı stisknut´ı tlaˇc´ıtka reset dojde k jeho spuˇstˇen´ı. Po spuˇstˇen´ı programu v mikrokontroléru dojde k inici- alizaci ˇr´ıd´ıc´ıch registr˚u. Nejd˚uleˇzitˇejˇs´ım krokem této fáze je správné nastaven´ı hodin celého systému.

(36)

3. N´avrh a implementace

Obrázek 3.4: Schéma nastaven´ı hodin mikrokontroléru

Zdrojem hodinového signálu je vnitˇrn´ı HSI RC oscilátor. Signál je pˇres dˇeliˇcku pˇriveden do PLL (Phase Locked Loop), kde je jeho poloviˇcn´ı frekvence (4 MHz) vynásobena 12. Multiplexor je nastaven tak, ˇze jako zdroj systémových hodin (SYSCLK) vybere výstup z PLL s frekvenc´ı 48 MHz.

SYSCLK se pouˇz´ıvá dále jako hodinový signál sbˇernice, hodiny periferi´ı a ˇc´ıta- ˇc˚u, vˇcetnˇe ˇc´ıtaˇce 14.

Dalˇs´ım krokem je nastaven´ı parametr˚u sériové linky, která slouˇz´ı k pˇrenosu namˇeˇrených hodnot z mikrokontroléru do poˇc´ıtaˇce. Pouˇz´ıváme 115,2 kbit/s.

Následnˇe je inicializován ˇc´ıtaˇc 14 v záchytném reˇzimu - jak bylo popsáno výˇse - a nastaveno pˇreruˇsen´ı. Pˇreruˇsen´ı je vyvoláno pˇri události zachycen´ı hodnoty ˇc´ıtaˇce v ”capture registru”. V obsluze pˇreruˇsen´ı dojde k pˇreˇcten´ı hodnoty z ”capture registru”, vynulován´ı ˇc´ıtaˇce 14 a uloˇzen´ı hodnoty do kruhové fronty.

Nyn´ı program na sériové lince oˇcekává znak ”s”, ˇc´ımˇz dojde ke spuˇstˇen´ı ˇc´ıtaˇce a záchytného registru. Program vstoup´ı do hlavn´ı smyˇcky - ve chv´ıli kdy kruhová fronta obsahuje namˇeˇrenou hodnotu, odeˇsle se pˇres sériovou linku do poˇc´ıtaˇce.

V poˇc´ıtaˇci jsou hodnoty naˇc´ıtány pomocným programem (napsaným v ja- zyce C#) a ukládány do binárn´ıho souboru (2 byte unsigned integer).

Prvotn´ı implementace programu pro mikrokontrolér vyuˇz´ıvala API sofwa- rové vrstvy HAL (Hardware Abstraction Layer) [17]. Jej´ı výhodou je snadnˇejˇs´ı práce s programován´ım mikrokontroléru. Nab´ız´ı pomocné struktury a funkce.

V naˇsem konkrétn´ım pˇr´ıpadˇe se ukázalo, ˇze vrstva nav´ıc zp˚usobuje zpoˇzdˇen´ı po pˇreˇcten´ı generované hodnoty. D˚usledkem je zkreslen´ı generovaných hodnot.

Pˇri nastaven´ı pˇreddˇeliˇcky na 1 by se hodnoty mˇely pohybovat okolo teore- tické hodnoty 1464 dané pomˇerem frekvenc´ı HSI a LSE oscilátor˚u. S pouˇzit´ım HAL výsledky mˇeˇren´ı dosahovaly intervalu okolo hodnoty 1370, tedy hod- 20

(37)

3.3. Program noty mnohem niˇzˇs´ı. Proto jsme pˇrepracovali implementaci bez pouˇzit´ı zm´ınˇené vrstvy, nyn´ı pracujeme pˇr´ımo s ˇr´ıd´ıc´ımi registry a t´ım jsme dosáhli mnohem pˇresnˇejˇs´ıch výsledných hodnot okolo 1430.

(38)

(39)

Kapitola 4

Mˇ eˇ ren´ı

Pˇred zahájen´ım mˇeˇren´ı propoj´ıme pˇr´ıpravek s poˇc´ıtaˇcem, nahrajeme program do mikrokontroléru a stiskneme tlaˇc´ıtko reset. Spust´ıme pomocnou mˇeˇr´ıc´ı aplikaci v poˇc´ıtaˇci, zadáme konfiguraci a potvrd´ıme jméno výstupn´ıho souboru.

T´ım dojde k odeslán´ı startovn´ıho znaku ”s” z poˇc´ıtaˇce do pˇr´ıpravku, který zaˇcne generovat náhodné hodnoty. Ty jsou v poˇc´ıtaˇci ukládány do binárn´ıho souboru.

Pro následné statistické vyhodnocen´ı necháváme vygenerovat 800 milión˚u hodnot, coˇz odpov´ıdá zhruba 40 hodinám bˇehu programu a objemu 1,4 GB dat. Celkem jsme provedli 4 série mˇeˇren´ı s r˚uzným nastaven´ım pˇreddˇeliˇcky (1, 2, 4, 8 pulz˚u na zachycen´ı hodnoty).

0 2x10⁷ 4x10⁷ 6x10⁷ 8x10⁷ 1x10⁸

1405 1410 1415 1420 1425 1430 1435 1440 1445

Četnost

Hodnoty

Histogram rozdělení hodnot - měření 1

Obr´azek 4.1: Histogram mˇeˇren´ı 1

(40)

4. Mˇeˇren´ı

0 1x10⁷ 2x10⁷ 3x10⁷ 4x10⁷ 5x10⁷ 6x10⁷ 7x10⁷

2870 2875 2880 2885 2890 2895 2900 2905 2910 2915 2920 2925

Četnost

Hodnoty

4.1 Mˇ eˇ ren´ı 1

Histogram mˇeˇren´ı je na obr´azku 4.1.

• Nastaven´ı pˇreddˇeliˇcky: 1 (zachycen´ı hodnoty na kaˇzd´y pulz od LSE)

• Rozsah hodnot: 1405 - 1446

• Pr˚umˇer: 1424.962

• Rozptyl: 10.98

4.2 Mˇ eˇ ren´ı 2

• Nastaven´ı pˇreddˇeliˇcky: 2 (zachycen´ı hodnoty kaˇzd´e 2 pulzy od LSE)

• Pr˚umˇer: 2894.762

• Rozptyl: 19.786

24

(41)

4.3. Mˇeˇren´ı 3

0 1x10⁷ 2x10⁷ 3x10⁷ 4x10⁷ 5x10⁷ 6x10⁷ 7x10⁷ 8x10⁷

5810 5820 5830 5840 5850 5860 5870

Četnost

Hodnoty

0 1x10⁷ 2x10⁷ 3x10⁷ 4x10⁷ 5x10⁷ 6x10⁷

11690 11700 11710 11720 11730 11740 11750 11760 11770

Četnost

Hodnoty

4.3 Mˇ eˇ ren´ı 3

• Nastaven´ı pˇreddˇeliˇcky: 4 (zachycen´ı hodnoty kaˇzd´e 4 pulzy od LSE)

• Pr˚umˇer: 5837.125

• Rozptyl: 18.0768

(42)

4. Mˇeˇren´ı

4.3.1 Anal´yza v´ysledk˚u mˇeˇren´ı 3

Histogram ˇcetnost´ı hodnot mˇeˇren´ı 3 vykazuje niˇzˇs´ı hodnotu rozptylu oproti pˇredpokladu pro dané nastaven´ı pˇreddˇeliˇcky. Rozptyl by mˇel lineárnˇe r˚ust v rámci jednotlivých mˇeˇren´ı. Proto jsme provedli dalˇs´ı analýzu s c´ılem objasnit tuto anomálii. Vygenerovali jsme 800 histogram˚u vˇzdy po milionu hodnot a z nich vytvoˇrili video animaci. Histogramy i animaci pˇrikládáme na CD.

Vygenerované histogramy pˇribliˇznˇe odpov´ıdaj´ı celkovému histogramu. Hod- noty rozptylu nevykazuj´ı ˇzádné vˇetˇs´ı odchylky. ˇReˇsen´ım by bylo mˇeˇren´ı s da- ným nastaven´ım pˇreddˇeliˇcky zopakovat popˇr. s jiným fyzickým zaˇr´ızen´ım.

4.4 Mˇ eˇ ren´ı 4

• Nastaven´ı pˇreddˇeliˇcky: 8 (zachycen´ı hodnoty kaˇzd´ych 8 pulz˚u od LSE)

• Pr˚umˇer: 11718.327

• Rozptyl: 48.153

4.4.1 Anal´yza v´ysledk˚u mˇeˇren´ı 4

Na histogramu ˇcetnost´ı hodnot mˇeˇren´ı 4 je v pravé ˇcásti grafu patrná odchylka od ideáln´ı gaussovské kˇrivky (kolem hodnoty 11730). Proto jsme provedli dalˇs´ı analýzu s c´ılem objasnit tuto anomálii. Vygenerovali jsme 800 histogram˚u vˇzdy po milionu hodnot a z nich vytvoˇrili video animaci. Histogramy i animaci pˇrikládáme na CD.

Jak je z graf˚u patrné, k vychýlen´ı celé kˇrivky smˇerem doprava k vyˇsˇs´ım hodnotám doˇslo celkem 3x okolo 300., 527. a 670. mˇeˇreného milionu hodnot.

Aby doˇslo k pozorovanému jevu, muselo by bud’ doj´ıt ke zrychlen´ı vnitˇrn´ıho oscilátoru (HSI), anebo ke zpomalen´ı vnˇejˇs´ıho krystalového oscilátoru (LSE).

Vzhledem k tomu, ˇze neˇslo o vychýlen´ı trvalé, coˇz by mohlo být zp˚usobeno napˇr´ıklad zahˇrát´ım ˇcipu, ale o tˇri výchylky bˇehem 40 hodinového mˇeˇren´ı, docház´ıme k závˇeru, ˇze muselo j´ıt o nˇejaký vnˇejˇs´ı vliv. Pravdˇepodobnou pˇr´ıˇcinou se nám jev´ı nestabilita zdroje napájen´ı nebo zmˇeny okoln´ı teploty.

4.5 Shrnut´ı

Vˇsechna zm´ınˇená mˇeˇren´ı maj´ı oˇcekávané gaussovské rozdˇelen´ı charakteristické proclock jitter, jak je zm´ınˇeno v kapitole výˇse. Dále si vˇsimnˇeme závislosti nastaven´ı pˇreddˇeliˇcky a rozptylu. Pˇri vetˇs´ım poˇctu pulz˚u na zachycenou hodnotu se nestabilita signálu hodin akumuluje, coˇz má za následek i vyˇsˇs´ı hodnotu rozptylu.

26

(43)

Kapitola 5

Statistick´ e vyhodnocen´ı

Statistick´e vyhodnocen´ı prov´ad´ıme pomoc´ı sady test˚u v aplikaci NIST STS (Statistical Test Suite).

Z namˇeˇrených dat prostˇrednictv´ım pomocné aplikace vygenerujeme bit- stream - bitový proud sestávaj´ıc´ı napˇr´ıklad pouze z 1. nejniˇzˇs´ıho bitu kaˇzdé namˇeˇrené hodnoty. Takto z´ıskaný bitový proud dále vyhodnot´ıme pomoc´ı sady test˚u STS.

5.1 Sada test˚ u NIST STS

NIST test suite se skládá z 15 test˚u, které slouˇz´ı k testován´ı náhodnosti binárn´ıch sekvenc´ı, produkovaných hardwarovými nebo softwarovými TRNG nebo PRNG. Testy se zamˇeˇruj´ı na odhalen´ı poruˇsen´ı náhodnosti, která se m˚uˇze v testované vstupn´ı sekvenci objevit.

Pˇr´ıklady nˇekter´ych test˚u:

• Frequency (Monobit) Test - tento test se zamˇeˇruje na zjiˇstˇen´ı mnoˇzstv´ı nul a jedniˇcek ve vstupn´ı sekvenci. ´Uˇcelem testu je zjistit zda nul a jedni- ˇ

cek je pˇribliˇznˇe stejn´e mnoˇzstv´ı - t.j. polovina

• Non-overlapping Template Matching Test - tento test se zamˇeˇruje na vyhodnocen´ı poˇctu výskyt˚u urˇcité posloupnosti bit˚u. Úˇcelem tohoto testu je detekovat generátory, které produkuj´ı mnoho výskyt˚u daného ne-periodického vzoru.

• Linear Complexity Test - tento test se zamˇeˇruje na délku registru s lineár- n´ı zpˇetnou vazbou. Úˇcelem testu je rozhodnout zda je sekvence do- stateˇcnˇe komplexn´ı, aby ji bylo moˇzné povaˇzovat za náhodnou. Náhodné sekvence charakterizuje delˇs´ı LFSR (viz. výˇse)

(44)

5. Statistick´e vyhodnocen´ı

5.2 Pouˇ zit´ı NIST STS

STS spust´ıme s parametrem, který udává délku testované sekvence v bitech.

Dále zadáme vstupn´ı soubor se zpracovávanými daty a kterou sadu test˚u chceme spustit. Následnˇe zadáme poˇcet sekvenc´ı ke zpracován´ı. Dále se zadává typ vstupn´ıho souboru - t.j. zda jde o binárn´ı ˇci ASCII vstup. Po exekuci test˚u je vygenerován výstupn´ı soubor (pˇr´ıklad je v pˇr´ıloze). Poˇcet ˇrádk˚u odpov´ıdá poˇctu provedených test˚u, dále výstup obsahuje pro kaˇzdý test hodnotu p- value, která udává do jaké m´ıry se testovaná sekvence podobá normáln´ımu rozdˇelen´ı ˇci rozdˇelen´ıχ² a název testu.

5.3 Testovan´ a Data

V rámci kaˇzdého mˇeˇren´ı jsme testovali nejménˇe významné bity na pozic´ıch 0-3. Délka testované sekvence byla 1 milión a poˇcet tˇechto sekvenc´ı 800, coˇz odpov´ıdá 800 milión˚um namˇeˇrených hodnot. Na základˇe výsledk˚u jednotlivých bit˚u jsme dále provedli vyhodnocen´ı dat z´ıskaných spojen´ım bit˚u 0-1 a 0-1-2.

5.4 V´ ysledky

V pˇr´ıloze jsou výstupy test˚u mˇeˇren´ı 1 pro bit 0 - vˇsechny testy úspˇeˇsnˇe proˇsly, bit1 - jeden test selhal a bit 2 - vetˇsina test˚u selhala. Výsledky statistických test˚u shrnuj´ı tabulky 5.1 a 5.2. ˇRádek reprezentuje jedno mˇeˇren´ı charakteri- zované nastaven´ım pˇreddˇeliˇcky. Ve sloupc´ıch jsou testované bity. Na výsledky lze nahl´ıˇzet ze dvou pohled˚u. Zaprvé zkoumat rozd´ıly v rámci jednotlivých bit˚u a zadruhé analyzovat výsledky s r˚uzným nastaven´ım pˇreddˇeliˇcky.

Testy prokázaly pˇredpokládanou tendenci klesaj´ıc´ı kvality náhodnosti s rostouc´ı pozic´ı bitu. Výsledky s bity 0 nebo 1 vycházej´ı nejlépe. Podobnˇe dobˇre vycház´ı i spojen´ı bit˚u 0-1. V obou tˇechto pˇr´ıpadech bud’ proˇsly vˇsechny testy

´

uspˇeˇsnˇe anebo neproˇsly pouze jednotky test˚u. U bit˚u 2, 3 a rovnˇeˇz u spojen´ı bit˚u 0-2 doˇslo k selh´an´ı vˇetˇsiny test˚u.

M˚uˇzeme konstatovat, ˇze spojen´ım bitu 0 a 1 se výsledky statistických test˚u zlepˇsily. Nebot’ s nastaven´ım pˇreddˇeliˇcky na 1, 2 a 8 proˇsly úspˇeˇsnˇe vˇsechny testy na rozd´ıl od výsledk˚u bitu 0 nebo 1, kde alespoˇn pˇri dvou nastaven´ıch pˇreddˇeliˇcky neproˇsel nˇejaký test. Také lze ˇr´ıci, ˇze i pro bity 2 nebo 3 lze ve výsledc´ıch, s rostouc´ım ˇc´ıslem pˇreddˇeliˇcky, pozorovat zlepˇsuj´ıc´ı se trend - tedy zvyˇsuj´ıc´ı se poˇcet úspˇeˇsných test˚u.

5.5 Shrnut´ı

Výsledky indikuj´ı, ˇze se daný návrh dá pouˇz´ıt jako TRNG. Abychom si mohli být jist´ı je tˇreba provést podrobnˇejˇs´ı vyhodnocen´ı, pouˇzitá sada test˚u slouˇz´ı k vyhodnocen´ı PRNG, ale lze ji vyuˇz´ıt pro základn´ı vyhodnocován´ı TRNG.

28

(45)

5.5. Shrnut´ı pˇreddˇeliˇcka bit 0 bit 1 bit 2 bit 3

1 ok ok* x x

2 ok ok x x

4 ok* ok** x x

8 ok* ok* x x

* ... neproˇsel jeden ze statistick´ych test˚u

** ... neproˇsly dva ze statistick´ych test˚u x ... vˇetˇsina statistick´ych test˚u selhala

Tabulka 5.1: V´ysledky test˚u NIST STS jednotliv´ych bit˚u.

pˇreddˇeliˇcka bit 0-1 bit 0-2

1 ok x

2 ok x

4 ok* x

8 ok x

* ... neproˇsel jeden ze statistick´ych test˚u x ... vˇetˇsina statistick´ych test˚u selhala

Tabulka 5.2: V´ysledky test˚u NIST STS spojen´ych bit˚u.

Pro reálné nasazen´ı TRNG se jev´ı jako nejvhodnˇejˇs´ı pouˇzit´ı sekvence tvoˇrené bitem 0 nebo 1 popˇr´ıpadˇe sekvence spojených bit˚u 0 a 1. Jestliˇze chceme dosáhnout co nejvˇetˇs´ı výtˇeˇznosti tak je pˇri daných výsledc´ıch vhodné pouˇz´ıt nastaven´ı pˇreddˇeliˇcky na 1 a vyb´ırat spojené bity 0 a 1.

(46)

(47)

Z´ avˇ er

C´ılem reˇserˇsn´ı ˇcásti této práce bylo seznámit se s problematikou generátor˚u náhodných ˇc´ısel a jejich klasifikac´ı. Dále prozkoumat existuj´ıc´ıˇreˇsen´ı generáto- r˚u skuteˇcnˇe náhodných ˇc´ısel s d˚urazem na konstrukce vhodné pro mikrokon- troléry. V praktické ˇcásti jsme se zabývali implementac´ı vlastn´ıho TRNG na mikrokontroléru. Provedli jsme mˇeˇren´ı a statistické vyhodnocen´ı jeho výstup˚u.

V rámci práce jsme splnili vˇsechny poˇzadavky. Provedli jsme literárn´ı reˇserˇsi, podaˇrilo se nám úspˇeˇsnˇe implementovat generátor náhodných ˇc´ısel na mikrokontroléru STM32F030R8T6 s procesorem ARM Cortex-M0. V kapitole 4 jsme provedli 4 mˇeˇren´ı s r˚uzným nastaven´ım pˇreddˇeliˇcky a následnˇe v kapitole 5 jsme provedli jejich statistické vyhodnocen´ı. Na základˇe výsledk˚u NIST STS se jev´ı implementovaný návrh RNG jako vhodný pro pouˇzit´ı jako TRNG.

Nejlepˇs´ıch výsledk˚u jsme dosáhli pˇri nastaven´ı pˇreddˇeliˇcky na 1 a výbˇeru bit˚u 0 a 1.

V pr´aci by se dalo pokraˇcovat n´asledovnˇe:

• Prov´est opakovan´e mˇeˇren´ı s nastaven´ım pˇreddˇeliˇcky 4 a 8.

• Provést rozsáhlejˇs´ı mˇeˇren´ı za r˚uzných provozn´ıch podm´ınek, napˇr. rozd´ıl- né teploty, zdroje napájen´ı.

• Spustit implementaci TRNG na v´ıce fyzických mikrokontrolérech stej- ného typu a porovnat statistické výsledky jednotlivých zaˇr´ızen´ı.

• Provést mˇeˇren´ı s pouˇzit´ım LSI oscilátoru (intern´ı RC oscilátor) a výsledky porovnat.

(48)

(49)

Literatura

[1] Herrero-Collantes, M.; Garcia-Escartin, J. C.: Quantum Random Num- ber Generators, ˇr´ıjen 2016, [cit. 2018-04-25]. Dostupn´e z: https://

arxiv.org/pdf/1604.03304.pdf

[2] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A.:Handbook of Applied Cryptography. CRC Press, Boca Raton, 1997, [cit. 2018-04-27].

[3] Schindler, W.: Random Number generators for cryptographic applicati- ons. Cryptographic Engineering, Springer-Verlag, 2009, ISBN 978-0-387- 71816-3.

[4] Boyar, J.: Inferring Sequences Produced by Pseudo-Random Num- ber Generators. Journal of the Association for Computing Machinery, Vol. 36, No. 1, leden 1989, [cit. 2018-04-29]. Dostupn´e z: http://

asterix.cs.gsu.edu/crypto/p129-boyar.pdf

[5] Massey, J. L.:Shift-Register Synthesis and BCH Decoding, leden 1969: s.

122–127.

[6] Hlaváˇc, J.; Kodýtek, F.: Random Number Generators. Pˇrednáˇska z pˇredmˇetu Hardwarová bezpeˇcnost. ˇCeské vysoké uˇcen´ı technické v Praze, Fakulta informaˇcn´ıch technologi´ı, 2017.

[7] Sunar, B.: True Random Number Generators for Cryptography. Cryp- tographic Engineering, Springer-Verlag, 2009, ISBN 978-0-387-71816-3, 55-73 s.

[8] Random.org:True Random Number Service. Dostupn´e z:www.random.org [9] Marsaglia, G.:The Marsaglia Random Number CDROM, with The Die- hard Battery of Tests of Randomness. [online] Florida State University, 1995, [cit. 2018-05-06]. Dostupn´e z:www.stat.fsu.edu/pub/diehard/

(50)

Literatura

[10] Rukhin A. et al: A Statistical Test Suite for Random and Pseudoran- dom Number Generators for Cryptographic Applications. National Insti- tute of Standards and Technology, NIST Special Publication 800-22rev1a, Duben 2010, [cit. 2018-05-06]. Dostupn´e z: https://nvlpubs.nist.gov/

nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf

[11] Haddad, P.; Fischer, V.; Bernard, F.; aj.: A Physical Approach for Sto- chastic Modeling of TERO-based TRNG, ˇcerven 2015, [cit. 2018-04-30].

Dostupn´e z:https://eprint.iacr.org/2015/593.pdf

[12] Jun, B.; Kocher, P.: The IntelR Random Number Generator. Technical report, Cyptography Research Inc., San Francisco, 1999.

[13] Fischer, V.; Drutarovsk´y, M.: True Random Number Generator Embed- ded in Reconfigurable Hardware. In Proceedings of the 4th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2002). Redwood Shores (USA), Springer-Verlag, srpen 2002, ISBN 3-540- 00409-2, 415-430 s.

[14] Hlaváˇc, J.; Hadáˇcek, M.; Lórencz, R.: True Random Number Generation on an Atmel AVR Microcontroller. Proceedings of 2nd International Con- ference on Computer Engineering and Technology – ICCET 2010, vol. 2, 2010, ISBN 978-1-4244-6347-3, 493-495 s.

[15] Laban, M.; Drutarovsk´y, M.: Low Cost ARM Cortex-M0 based TRNG for IOT Applications, 2014, ISSN 1335-8243.

[16] STMicroelectronics: STMF030x8 Datasheet. [cit. 2018-05-06]. Dostupn´e z: http://www.st.com/resource/en/datasheet/stm32f030r8.pdf [17] STMicroelectronics:Description of STM32F0 HAL and low layer drivers.

[online], [cit. 2018-05-09]. Dostupn´e z: www.st.com/resource/en/user_

manual/dm00122015.pdf

34

(51)

Pˇ r´ ıloha A

V´ ystupy NIST STS

Na následuj´ıc´ıch stránkách pˇrikládáme výstupy statistických test˚u NIST pro mˇeˇren´ı 1.

Mˇeˇren´ı 1 - bit 0

Vˇsechny testy ´uspˇeˇsnˇe proˇsly.

--- RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES ---

generator is <Onyx-INT1aa_bit-0>

--- P-VALUE PROPORTION STATISTICAL TEST ---

0.514124 791/800 Frequency 0.749884 790/800 BlockFrequency 0.892399 790/800 CumulativeSums 0.757297 794/800 CumulativeSums 0.446556 797/800 Runs

0.857592 793/800 LongestRun 0.952387 797/800 Rank

0.024981 792/800 FFT

0.275709 792/800 NonOverlappingTemplate 0.257329 791/800 NonOverlappingTemplate 0.504219 796/800 NonOverlappingTemplate 0.694171 795/800 NonOverlappingTemplate 0.477392 792/800 NonOverlappingTemplate 0.644928 792/800 NonOverlappingTemplate 0.582629 795/800 NonOverlappingTemplate 0.322901 794/800 NonOverlappingTemplate 0.562080 795/800 NonOverlappingTemplate

(52)

A. V´ystupy NIST STS

0.717205 792/800 NonOverlappingTemplate 0.524101 789/800 NonOverlappingTemplate 0.453583 784/800 NonOverlappingTemplate 0.914672 795/800 NonOverlappingTemplate 0.482223 791/800 NonOverlappingTemplate 0.670915 793/800 NonOverlappingTemplate 0.951205 792/800 NonOverlappingTemplate 0.969946 797/800 NonOverlappingTemplate 0.293235 788/800 NonOverlappingTemplate 0.375313 791/800 NonOverlappingTemplate 0.230755 791/800 NonOverlappingTemplate 0.340461 794/800 NonOverlappingTemplate 0.865697 794/800 NonOverlappingTemplate 0.582629 789/800 NonOverlappingTemplate 0.739918 792/800 NonOverlappingTemplate 0.941144 793/800 NonOverlappingTemplate 0.881284 789/800 NonOverlappingTemplate 0.921005 789/800 NonOverlappingTemplate 0.499295 794/800 NonOverlappingTemplate 0.273999 791/800 NonOverlappingTemplate 0.330628 791/800 NonOverlappingTemplate 0.714660 797/800 NonOverlappingTemplate 0.960198 791/800 NonOverlappingTemplate 0.587791 788/800 NonOverlappingTemplate 0.150552 789/800 NonOverlappingTemplate 0.704442 791/800 NonOverlappingTemplate 0.242986 793/800 NonOverlappingTemplate 0.083654 787/800 NonOverlappingTemplate 0.524101 794/800 NonOverlappingTemplate 0.539193 790/800 NonOverlappingTemplate 0.354548 792/800 NonOverlappingTemplate 0.379555 793/800 NonOverlappingTemplate 0.618905 788/800 NonOverlappingTemplate 0.709558 792/800 NonOverlappingTemplate 0.678686 792/800 NonOverlappingTemplate 0.899521 793/800 NonOverlappingTemplate 0.759756 790/800 NonOverlappingTemplate 0.247698 794/800 NonOverlappingTemplate 0.204985 790/800 NonOverlappingTemplate 0.362765 794/800 NonOverlappingTemplate 0.057601 793/800 NonOverlappingTemplate 0.119682 790/800 NonOverlappingTemplate 0.489508 793/800 NonOverlappingTemplate 0.151616 794/800 NonOverlappingTemplate 36

(53)

0.221898 790/800 NonOverlappingTemplate 0.531629 797/800 NonOverlappingTemplate 0.448892 784/800 NonOverlappingTemplate 0.403403 798/800 NonOverlappingTemplate 0.719747 791/800 NonOverlappingTemplate 0.320988 792/800 NonOverlappingTemplate 0.747401 791/800 NonOverlappingTemplate 0.961247 789/800 NonOverlappingTemplate 0.031323 789/800 NonOverlappingTemplate 0.696743 792/800 NonOverlappingTemplate 0.676097 794/800 NonOverlappingTemplate 0.811993 793/800 NonOverlappingTemplate 0.344448 790/800 NonOverlappingTemplate 0.309677 794/800 NonOverlappingTemplate 0.373203 792/800 NonOverlappingTemplate 0.825505 792/800 NonOverlappingTemplate 0.781584 793/800 NonOverlappingTemplate 0.300464 784/800 NonOverlappingTemplate 0.250878 794/800 NonOverlappingTemplate 0.696743 790/800 NonOverlappingTemplate 0.696743 786/800 NonOverlappingTemplate 0.304126 792/800 NonOverlappingTemplate 0.016573 793/800 NonOverlappingTemplate 0.701879 792/800 NonOverlappingTemplate 0.762209 785/800 NonOverlappingTemplate 0.881284 792/800 NonOverlappingTemplate 0.749884 793/800 NonOverlappingTemplate 0.556970 791/800 NonOverlappingTemplate 0.631914 796/800 NonOverlappingTemplate 0.798139 793/800 NonOverlappingTemplate 0.701879 792/800 NonOverlappingTemplate 0.932904 792/800 NonOverlappingTemplate 0.869673 793/800 NonOverlappingTemplate 0.214722 794/800 NonOverlappingTemplate 0.699313 793/800 NonOverlappingTemplate 0.973388 799/800 NonOverlappingTemplate 0.090252 792/800 NonOverlappingTemplate 0.988867 790/800 NonOverlappingTemplate 0.769527 790/800 NonOverlappingTemplate 0.964295 790/800 NonOverlappingTemplate 0.244549 793/800 NonOverlappingTemplate 0.877468 791/800 NonOverlappingTemplate 0.304126 794/800 NonOverlappingTemplate 0.401199 796/800 NonOverlappingTemplate

(54)

A. V´ystupy NIST STS

0.932904 791/800 NonOverlappingTemplate 0.516611 794/800 NonOverlappingTemplate 0.840797 791/800 NonOverlappingTemplate 0.482223 794/800 NonOverlappingTemplate 0.233767 794/800 NonOverlappingTemplate 0.135331 792/800 NonOverlappingTemplate 0.531629 793/800 NonOverlappingTemplate 0.987896 796/800 NonOverlappingTemplate 0.951205 794/800 NonOverlappingTemplate 0.734904 792/800 NonOverlappingTemplate 0.143279 796/800 NonOverlappingTemplate 0.629311 794/800 NonOverlappingTemplate 0.626709 789/800 NonOverlappingTemplate 0.394631 791/800 NonOverlappingTemplate 0.895989 794/800 NonOverlappingTemplate 0.300464 792/800 NonOverlappingTemplate 0.529115 795/800 NonOverlappingTemplate 0.639722 789/800 NonOverlappingTemplate 0.244549 791/800 NonOverlappingTemplate 0.428095 796/800 NonOverlappingTemplate 0.356591 791/800 NonOverlappingTemplate 0.724817 785/800 NonOverlappingTemplate 0.521600 794/800 NonOverlappingTemplate 0.315297 793/800 NonOverlappingTemplate 0.694171 794/800 NonOverlappingTemplate 0.088226 794/800 NonOverlappingTemplate 0.340461 791/800 NonOverlappingTemplate 0.021999 795/800 NonOverlappingTemplate 0.946308 787/800 NonOverlappingTemplate 0.164882 795/800 NonOverlappingTemplate 0.534146 788/800 NonOverlappingTemplate 0.642325 787/800 NonOverlappingTemplate 0.127762 794/800 NonOverlappingTemplate 0.514124 790/800 NonOverlappingTemplate 0.836482 788/800 NonOverlappingTemplate 0.153763 788/800 NonOverlappingTemplate 0.514124 793/800 NonOverlappingTemplate 0.311542 792/800 NonOverlappingTemplate 0.410055 794/800 NonOverlappingTemplate 0.598138 793/800 NonOverlappingTemplate 0.897763 793/800 NonOverlappingTemplate 0.786355 797/800 NonOverlappingTemplate 0.802793 791/800 NonOverlappingTemplate 0.467799 788/800 NonOverlappingTemplate 38

(55)

0.840797 793/800 NonOverlappingTemplate 0.430380 793/800 NonOverlappingTemplate 0.159242 793/800 NonOverlappingTemplate 0.595549 789/800 NonOverlappingTemplate 0.727346 791/800 NonOverlappingTemplate 0.871642 789/800 NonOverlappingTemplate 0.639722 786/800 NonOverlappingTemplate 0.061356 794/800 OverlappingTemplate 0.375313 787/800 Universal

0.039137 788/800 ApproximateEntropy 0.093664 502/514 RandomExcursions 0.996265 510/514 RandomExcursions 0.192093 511/514 RandomExcursions 0.192093 510/514 RandomExcursions 0.985481 507/514 RandomExcursions 0.610599 508/514 RandomExcursions 0.238734 504/514 RandomExcursions 0.751633 510/514 RandomExcursions

0.900788 510/514 RandomExcursionsVariant 0.984580 509/514 RandomExcursionsVariant 0.963513 504/514 RandomExcursionsVariant 0.639161 503/514 RandomExcursionsVariant 0.683958 506/514 RandomExcursionsVariant 0.263807 511/514 RandomExcursionsVariant 0.154782 510/514 RandomExcursionsVariant 0.836014 509/514 RandomExcursionsVariant 0.626913 511/514 RandomExcursionsVariant 0.226901 508/514 RandomExcursionsVariant 0.941662 514/514 RandomExcursionsVariant 0.424702 512/514 RandomExcursionsVariant 0.176373 511/514 RandomExcursionsVariant 0.379806 512/514 RandomExcursionsVariant 0.461129 512/514 RandomExcursionsVariant 0.986346 512/514 RandomExcursionsVariant 0.101691 512/514 RandomExcursionsVariant 0.916498 510/514 RandomExcursionsVariant 0.375313 789/800 Serial

0.849289 793/800 Serial

0.742418 798/800 LinearComplexity

- - - -

The minimum pass rate for each statistical test with the exception of the random excursion (variant) test is approximately = 783 for a