%\documentclass[xcolor=dvipsnames]{beamer}
\documentclass[handout]{beamer}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usecolortheme{sidebartab}
%\input{makra-utf8}
\usepackage{listings}
\usetheme{Warsaw}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\newtheorem{veta}{Věta}
%\newtheorem{hyp}{Hypot\'eza}
\newtheorem{reseni}{Řešení}
%\newtheorem{problemx}{Problem}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}
\theoremstyle{example}
\newtheorem{definice}{Definice}
\newtheorem{priklad}{P\v r\'iklad}
\newtheorem*{pozn}{Poznámka}
\newtheorem*{dusl}{Důsledek}
\def\cervena #1{{\color{red} #1}}
\def\cervene #1{{\color{red} #1}}
\def\modra #1{{\color{blue}  #1}}
\def\modre #1{{\color{blue}  #1}}
\xdefinecolor{tmavezelena}{cmyk}{0.7,0,1,0.5}
\def\zelena #1{{\color{tmavezelena}  #1}}
\def\zelene #1{{\color{tmavezelena}  #1}}
\def\c #1{\mathcal {#1}}
\def\s #1{\mathsf {#1}}
%\def\poznamka #1{{\footnotesize Pozn.: #1}\\}
\def\poznamka #1{{\scriptsize Pozn.: #1}\\}
\def\otazka #1{{\scriptsize Kontrolní otázka: #1}\\}
\def\zavorka #1{{\scriptsize [ #1 ]}\\}
\def\sami {{\scriptsize Vyřešte samostatně.}}
\def\ec {{\vec{e_1}}}
\def\ecc {{\vec{e_2}}}
\def\efc {{\vec{f_1}}}
\def\efcc {{\vec{f_2}}}

\def\rovina {{\mathbb R^2}}
\def\vect #1{{\overrightarrow{#1}}}
\def\skalar #1#2{{\langle #1, #2\rangle}}
\def\velikost #1{{\| #1\|}}
\def\sgn #1{{\operatorname{sgn}(#1)}}
\def\norm #1{\|#1\|}

\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\K{\mathbb K}
\def\Z{\mathbb Z}
\def\N{\mathbb N}
\def\C{\mathbb C}

\let\isom\cong
\let\divides\mid
\let\ndivides\nmid
\newcommand{\smalland}{\ \land\ }
\newcommand{\Sage}{\texttt{SAGE}\ }
\let\congr\equiv
\newcommand{\I}{\mathbb{I}}
\def\noqed{\renewcommand{\qedsymbol}{}}
\newcommand{\kron}[2]{(#1/#2)}
\newcommand{\kro}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

%\input definice-slovak.tex

\def\tuzka{\hfill ${\color{orange}\blacktriangleright \blacktriangleright}$}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\title[Aplikace teorie čísel\hspace{15mm} \insertframenumber/\inserttotalframenumber]
{MB141 -- 12. přednáška \\Aplikace teorie čísel}
%\subtitle{}
\author[12. přednáška]{Martin Čadek\\ s využitím přednášek  pro předmět MB104}
\date{Jarní semestr 2022}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{document}
\begin{frame}
\titlepage
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Osnova 12. přednášky}
\begin{itemize}
\item Výpočetní aspekty teorie čísel
\bigskip
\item Kryptografie s veřejným klíčem

\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


\begin{frame}{Základní úlohy výpočetní teorie čísel}

V~mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle  provést jeden či více z~následujících výpočtů:
\begin{enumerate}[<+->]
\item běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech,
\item zbytek mocniny celého čísla $a$ na přirozené číslo $n$ po dělení daným $m$.
\item inverzi celého čísla $a$ modulo $m\in \N$,
\item největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), 
\item rozhodnout o~daném čísle, je-li prvočíslo nebo složené,
\item v~případě složenosti rozložit dané číslo na součin prvočísel.
\end{enumerate}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Základní aritmetické operace}
  
Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škole, kdy umíme \cervene{sčítat} v~\textit{lineárním} čase, \cervene {násobit a dělit se zbytkem} v~\textit{kvadratickém} čase. % \pause 
Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu \textit{rozděl a panuj}) - např. první takový Karatsubův (1960) časové náročnosti $\Theta(n^{\log_23})$ %\pause 
nebo algoritmus Schönhage-Strassenův (1971) časové náročnosti $\Theta(n \log n \log\log n)$. Číslo $n$ zde udává celkový počet cifer vstupujících do výpočtu.
\medskip
%\pause 
Pěkný přehled najdete např. na \url{http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations}
\end{frame}

\begin{frame}{Největší společný dělitel a modulární inverze}

  Jak už jsme ukazovali dříve, výpočet výpočet \cervene{inverze modulo $m$}, tj. řešení kongruence $a\cdot
x\equiv1\pmod m$ s~neznámou $x$ lze snadno (díky Bezoutově větě) převést na
výpočet největšího společného dělitele čísel $a$ a $m$ a na hledání
koeficientů $k,l$ do Bezoutovy rovnosti $k\cdot a+l\cdot m=1$ (nalezené $k$
je pak onou hledanou inverzí $a$ modulo $m$).

%\pause

%\centerline{\resizebox{7cm}{!}{\includegraphics{xgcd}}
%}


%\bigskip
%\begin{lstlisting}[frame=single]
%function extended_gcd(a, m)
%    if m == 0
%        return (1, 0)
%    else
%        (q, r) := divide (a, m)
%        (k, l) := extended_gcd(m, r)
%        return (l, k - q * l)
%\end{lstlisting}
%
\medskip
Podrobná analýza %(viz např. \texttt{[Knuth] nebo [Wiki]}) 
ukazuje, že tento algoritmus je \cervene{kvadratické} časové složitosti.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}[fragile]{Modulární umocňování}  

V kryptografii s veřejným klíčem budeme budeme potřebovat  \cervene{umocňování modulo $m$}. To se také využívá při ověřování, zda je dané číslo prvočíslo nebo číslo složené.
Jedním z~efektivních algoritmů je tzv. \cervene{modulární umocňování zprava doleva}:

%\pause

\bigskip
\begin{lstlisting}[frame=single]
function modular_pow(base, exponent, modul)
    result := 1
    while exponent > 0
      if (exponent mod 2 == 1):
        result := (result * base) mod modul
      exponent := exponent >> 1
      base = (base * base) mod modul
    return result
\end{lstlisting}

Symbol $>>$ ve třetím řádku zdola znamená, že od exponentu zapsaného v dvojkové soustavě odebereme poslední cifru $1$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Idea algoritmu}
Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání $2^{64}\pmod{1000}$
\begin{itemize}[<+->]
\item není třeba nejprve počítat $2^{64}$ a poté jej vydělit se zbytkem číslem 1000, ale lépe je postupně násobit \uv{dvojky} a kdykoliv je výsledek větší než 1000, provést redukci modulo 1000,
\item ale zejména, že není třeba provádět takové množství násobení (v~tomto případě 63 naivních násobení je možné nahradit pouze šesti umocněními na druhou, neboť $$2^{64}=(((((2^2)^2)^2)^2)^2)^2.$$
\end{itemize}
\end{frame}


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame} {Ukázka průběhu algoritmu}
    Vypočtěme $2^{560} \pmod{561}$. Protože $560=(1000110000)_2$, dostaneme uvedeným algoritmem 
    \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      exponent&base&result&exp's last digit\\
\hline
560&2&1&0\\
280&4&1&0\\
140&16&1&0\\
70&256&1&0\\
35&460&1&1\\
17&103&460&1\\
8&511&256&0\\
4&256&256&0\\
2&460&256&0\\
1&103&256&1\\
0&511&1&0\\
\hline    \end{tabular}
  \end{center}

%\pause
A~tedy $2^{560}\equiv1\pmod{561}.$
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Efektivita modulárního umocňování}

V~průběhu algoritmu se pro každou binární číslici exponentu provede umocnění základu na druhou modulo $m$ 
(což je operace proveditelná v~nejhůře kvadratickém čase), a pro každou \uv{jedničku} v~binárním zápisu navíc provede jedno násobení.  Celkově jsme
tedy schopni provést  modulární umocňování nejhůře v~\textbf{kubickém} čase.

\bigskip
Další úlohy výpočetní teorie čísel jsou \cervene{testování prvočíselnosti} a \cervene{rozklad složených čísel na prvočísla}. Tato témata jsou  na samostatnou přednášku, nebudeme se jimi zde~zabývat. Více lze najít v učebnici Drsná matematika v~odstavcích 10.38-47.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Kryptografie s veřejným klíčem}
  
Dva hlavní úkoly pro \uv{public-key cryptography} jsou zajistit
\begin{itemize}
\item šifrování, kdy zprávu \cervene{zašifrovanou veřejným klíčem} není schopen rozšifrovat nikdo kromě držitele soukromého klíče,
\item podepisování, kdy integrita zprávy \cervene{podepsané soukromým klíčem} odesílatele může být ověřena kýmkoliv s přístupem k veřejnému klíči odesílatele.
\end{itemize}

%\pause
Nejčastěji používané systémy:
\begin{itemize}[<+->]
\item RSA (šifrování) a odvozený systém pro podepisování zpráv
\item Digital signature algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA)
\item Rabinův kryptosystém (a podepisování)
\item Diffie-Hellmanův protokol na výměnu klíčů (DH)
\item ElGamal kryptosystém (a podepisování)
\item Kryptografie eliptických křivek (ECC)

\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{RSA}
  \textit{Rivest, Shamir, Adleman} (1977); \textit {Cocks}(1973)

\begin{itemize}[<+->]
\item Jsou dva typy  klíčů -- veřejný a soukromý. 
\item Generování klíčů: zvolí se dvě velká prvočísla $p,q$, vypočte se $n=pq$, $\varphi(n)=(p-1)(q-1)$. Přitom pouze $n$ je veřejné, $\varphi(n)$ nelze snadno spočítat.
\item \cervene{Veřejný klíč} je číslo $e$ s vlastností $(e,\varphi(n))=1$
\item  \cervene{Soukromý klíč} je číslo $d$ s vlastností $e\cdot d\equiv1\pmod {\varphi(n)}$. Ze znalosti $\varphi(n)$ ho spočítáme např. pomocí Eukleidova algoritmu.
\item Zpráva je číslo $M \pmod n$.  Zašifrujeme ji jako  

$C\equiv M^e\pmod n$.
\item Dešifrování šifry $C$ spočívá ve výpočtu: $C^d\pmod n$.
\item Na základě Eulerovy věty totiž $\pmod n$ dostaneme $C^d\equiv (M^e)^d\equiv M^{ed}
\equiv M^{k\varphi(n)+1}\equiv {\left(M^{\varphi(n)}\right)}^{k}\cdot M\equiv M$.
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Rabinův kryptosystém}
  
Dalším veřejným kryptosystémem je \textbf{Rabinův kryptosystém}, který si uvedeme ve zjednodušené verzi:
\begin{itemize}[<+->]
\item Každý účastník $A$ potřebuje dvojici klíčů -- veřejný $V_A$ a soukromý $S_A$.
\item Generování klíčů: $A$ zvolí dvě podobně velká prvočísla \\ $p,q\equiv3\pmod4$, vypočte $n=pq$.

\item $V_A=n$, $S_A=(p,q)$ - dvojice prvočísel, nikoliv jejich největší společný dělitel, který je 1. 
\item Zašifrování numerického \textit{kódu} zprávy $M$: \\  $C\equiv M^2\pmod n$.
\item Dešifrování šifry $C$: vypočtou se (čtyři) odmocniny z~$C$ modulo $n$ a snadno se otestuje, která z~nich byla původní zprávou.  
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Výpočet druhé odmocniny}
 Výpočet druhé odmocniny z~$C$ modulo $n=pq$, \\ kde $p\equiv q\equiv3\pmod4$
 probíhá takto:
    \begin{itemize}[<+->]
    \item vypočti $r=C^{(p+1)/4}\pmod p$ a $s=C^{(q+1)/4}\pmod q$
    \item vypočti $a,b$ tak, že $ap+bq=1$
    \item polož $x=(aps+bqr) \pmod n$,  $y=(aps-bqr) \pmod n$
    \item druhými odmocninami z~$C$ modulo $n$  jsou $\pm x$, $\pm y$.   
    \end{itemize}
    \medskip
  \zelene{Zdůvodnění:} Z Čínské zbytkové věty vyplývá, že $z^2\equiv C\pmod{pq}$, právě když   
  současně platí  $z^2\equiv C\pmod{p}$ a  $z^2\equiv C\pmod{q}$. Lze ukázat, že pro každé liché prvočíslo platí, že kvadratická kongruence  $z^2\equiv C\pmod{p}$ má řešení právě když
$C^{\frac{p-1}{2}}\equiv 1\pmod p$. Tedy při počítání $\pmod p$ dostáváme
$x^2\equiv y^2\equiv (bq)^2r^2\equiv 1^2\cdot C^{\frac{p+1}{2}}\equiv C^{\frac{p-1}{2}}\cdot C\equiv 1\cdot C\equiv C\pmod p$.

Analogický výpočet lze provést $\pmod q$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklad}
  \begin{priklad}
    V~Rabinově kryptosystému Alice zvolila za svůj soukromý klíč $p=23, q=31$, veřejným klíčem je pak $n=pq=713$. Zašifrujte zprávu $M=327$ pro Alici a ukažte, jak bude Alice tuto zprávu dešifrovat.   
  \end{priklad}

%\pause
  $C\equiv 327^2\equiv 692$. Při dešifrování spočítáme
  
  $C^6\equiv (2)^6\equiv 18\pmod {23}$ a $C^8\equiv 10^8\equiv 14\pmod {31}$. 
  Dále $-4\cdot23+3\cdot31=1$. Proto máme 4 kandidáty na zprávu, a to
   $\pm 4\cdot 23\cdot 14\pm 3\cdot 31\cdot 18\pmod{713}$. To jsou  čísla $\pm 38$
   a $\pm 327\pmod {731}$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}	{Princip digitálního podpisu}

%Proces podepisování a ověření podpisu zprávy $M$ probíhá obvykle v následujících krocích.
%
%\pause
Podepisování
  \begin{enumerate}
  \item Vygeneruje se otisk (hash) $H_M$ zprávy pevně stanovené délky (např. 160 nebo 256 bitů).
  \item Podpis zprávy $S_A(H_M)$ je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče $S_A$ podepisujícího.
  \item Zpráva $M$ (případně zašifrovaná veřejným klíčem příjemce) je spolu  s podpisem odeslána.
  \end{enumerate}

\medskip
%\pause
Ověření podpisu
  \begin{enumerate}
  \item K přijaté zprávě $M$ se (po jejím případném dešifrování) vygeneruje otisk $H'_M$
  \item S pomocí veřejného klíče $V_A$ (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy $V_A(S_A(H_M))=H_M$.
  \item Oba otisky se porovnají $H_M=H'_M$?.
  \end{enumerate}
\end{frame}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Výměna klíčů podle Diffie-Hellmana}

\textit{Diffie, Hellman} (1976), \textit{ Williamson} (1974)

Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu
(tj. náhrada jednorázových klíčů, kurýrů s kufříky, \dots).

%\pause

\begin{itemize}[<+->]
\item Dohoda stran na \cervene{prvočísle} $p$ a \cervene{primitivním kořenu} $g$ modulo $p$ (veřejné). (Zopakujme, že $g$ je primitivní kořen modulo prvočíslo $p$, jestliže $g^n\equiv 1 \pmod p$ pouze pro násobky $p-1$.)
\item Alice vybere náhodné číslo $a$ a pošle Bobovi $g^a \pmod p$  
\item Bob vybere náhodné $b$ a pošle Alici $g^b \pmod p$
\item Společným klíčem pro komunikaci je $g^{ab} \pmod p$. 
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}
\frametitle{Kryptosystém ElGamal}
    Z protokolu Diffie--Hellman  na výměnu klíčů je odvozen šifrovací algoritmus ElGamal:
    \begin{itemize}
    \item Alice zvolí prvočíslo $p$ spolu s primitivním kořenem $g$. 
    \item Alice zvolí \textbf{tajný klíč} $a$, spočítá $h=g^a \pmod p$  a  zveřejní \textbf{veřejný klíč} $(p,g,h)$.
    \item Šifrování zprávy $M$: Bob zvolí náhodné $b$ a vypočte $C_1=g^b \pmod p$ a $C_2=M\cdot h^b \pmod p$
     a pošle Alici $(C_1,C_2)$.
    \item Dešifrování zprávy provede Alice tak, že spočítá inverzi $I$ k~$C_1^a=(g^{b})^a=g^{ab}\pmod p$ a vynásobí 
    $C_2\cdot I\equiv M\cdot g^{ab}\cdot I\equiv M\pmod p$.
    \end{itemize}

Příklad najdete ve cvičení. Analogicky jako pro RSA lze odvodit podepisování.
\end{frame}




\end{document}