% !TeX spellcheck = hu_HU
%%% Ez az uj piros téma, Van pár overfill hiba. 2009.11.03.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Normál üzemmód, vetítéshez
\documentclass[compress,ucs]{beamer}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{pgfpages}
\pgfpagesuselayout{resize to}[a4paper,landscape,border shrink=5mm]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Szövegfájl típusú nyomtatáshoz
%\documentclass{article}
%\usepackage{beamerarticle,amssymb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>
{
  \usetheme{CambridgeUS}
  \setbeamertemplate{navigation symbols}{}
  \setbeamertemplate{footline}[frame number]
  \setbeamercovered{transparent}
}
\usecolortheme{orchid}
% color themes: albatross, beaver, beetle, **crane, default, dolphin, dov, fly,
% lily, **orchid, rose, seagull, seahorse, sidebartab, structure, whale,
% wolverine
\usefonttheme{serif}
% font themes: default, professionalfonts, serif, structurebold,
% structureitalicserif, structuresmallcapsserif
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{t1enc}
\usepackage{pifont}
\usepackage{txfonts}
\usepackage{mathtools}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[utf8x]{inputenc}

\usepackage[magyar]{babel}
\usepackage{array}
\frenchspacing

\usepackage{color, colortbl}
\usepackage{tikz}
\usetikzlibrary{intersections}
\usetikzlibrary{calc}
\usetikzlibrary{shadows}
\usetikzlibrary{mindmap}
\usetikzlibrary{arrows,decorations.pathreplacing,shapes.misc}
\usepackage{qrcode}
\usepackage{wasysym}
\usepackage{marvosym}

\graphicspath{{pics/}}

\newcommand{\megjegyzes}{\structure{Megjegyzés.} }
\newcommand{\megj}{\structure{Megj.} }
\newcommand{\bizonyitas}{\structure{Bizonyítás.} }
\newcommand{\biz}{\structure{Biz.} }
\newcommand{\megoldas}{\structure{Megoldás.} }
\newcommand{\id}{\mathrm{id}}
\newcommand{\tg}{\mathrm{tg}}
\newcommand{\ctg}{\mathrm{ctg}}

\newcommand{\bm}[1]{\boldsymbol{#1}}
\newcommand\encircle[1]{\raisebox{.2pt}{\textcircled{\raisebox{-.4pt} {\scriptsize$#1$}}}}

\title{Kód alapú posztkvantum kriptográfia}
\subtitle{tudománynépszerűsítő előadás}
\author{Nagy~Gábor~Péter}
\institute[SZTE Bolyai Intézet]{Szegedi Tudományegyetem\\ Bolyai Intézet}
\date[2022]{2022. május 9.}

\subject{Matematika}

\AtBeginSection[]
{
    \begin{frame}
        \frametitle{Tagolás}
        \tableofcontents[currentsection]
    \end{frame}
}

\begin{document}

\setlength{\abovedisplayskip}{6pt plus 3pt minus 6pt}
\setlength{\belowdisplayskip}{6pt plus 3pt minus 6pt}
\setlength{\abovedisplayshortskip}{0pt plus 3pt}
\setlength{\belowdisplayshortskip}{0pt plus 3pt}

%\includeonlyframes{current}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}
  \frametitle{Tagolás}
  \tableofcontents
  % Die Option [pausesections] könnte nützlich sein.
\end{frame}

\section{Bonyolultságelmélet}

\subsection{Számításos feladatok}

\begin{frame}
\frametitle{Mi a probléma?}
Az alábbiakban a \textit{számítás} fogalmát általánosan értelmezzük.
\begin{block}{A Feladat}
Adott egy \structure{számítási} feladat, aminek egy \alert{$X$ inputhoz} egy \alert{$Y$ outputot} kell hozzárendelnie. 
\begin{itemize}
\item A feladat matematikai értelemben világosan van meghatározva. 
\item Az input és az output állhatnak több részből.
\item Az input és az output véges méretűek. 
\end{itemize}
\end{block}
\pause
\structure{Példák:}
\begin{itemize}
\item Két egész szám szorzata.
\item Hamilton-kör keresése.
\item Lineáris egyenletrendszer megoldása.
\item Prímtényezős felbontás.
\item Két egész szám legnagyobb közös osztója. 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Mi a megoldás?}
\begin{itemize}
\item Az ilyen típusú feladatokra a \structure{megoldás} általában \alert{egy eljárást, egy algoritmust} jelent. 
\item Az \textbf{algoritmus} fogalmának precíz meghatározása a 20. század elején vált szükségessé.
\end{itemize}
\begin{columns}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=4cm]{Alan_Turing} \\
Alan Turing \\ brit matematikus \\ 1912-1954
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=4cm]{Neumann_Janos} \\
Neumann János \\ magyar-amerikai matematikus \\ 1905-1957 
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Számító gépek}
\begin{itemize}
\item \structure{Alan Turing} 1936-ban publikálta a \textit{Computable numbers} c. dolgozatát.
\item Ebben egy elméleti modell alkotott egy \alert{univerzális gépre,} amit my \textit{Turing-gépnek hívunk.}
\item Ennek segítségével lehet definiálni az \textbf{algoritmus,} a \textbf{kiszámíthatóság,} és a \textbf{bonyolultság} fogalmát.
\item A gép a gyakorlatban is megvalósítható, de érdemi matematikai számításokra csak korlátozottan alkalmas. 
\item Sok ötletet alkalmaztak a brit \textit{Blechley Park} kódtörői a német titkosítási eljárások feltöréséhez. \vspace{5mm} \pause
\item A \structure{Neumann János} által 1945-ben javasolt számítógép-architektúra a mai napig meghatározó.
\item Ez a \textbf{CPU,} a \textbf{memória,} és az \textbf{input/output eszközök} elhelyezkedését és kapcsolatait írja le a \textit{digitális} számítógépben.
\end{itemize}
\end{frame}

\subsection{Algoritmus bonyolultsága}

\begin{frame}
\frametitle{Függvény nagyságrendje}
\begin{block}{Függvény nagyságrendje}
Azt mondjuk, hogy a két \alert{$f,g:\mathbb{R}\to \mathbb{R}$} függvény \alert{azonos nagyságrendű,} ha léteznek \structure{$A,B\in \mathbb{R}$} konstansok úgy, hogy 
\[Ag(x) \leq f(x)\leq Bg(x) \qquad\text{ és }\qquad Af(x) \leq g(x) \leq Bf(x)\]
teljesül minden $x\in \mathbb{R}$ esetén.
\end{block}
\structure{Jelölés:} $f\approx g$. 

\begin{exampleblock}{Példák (majdnem...)}
\begin{align}
f(x)&=\frac{x(x-1)}{2} & g(x)&=100x^2-1 \\
f(x)&=\log_2(x) & g(x)&=\log_{10}(x+1) \\
f(x)&=2^x & g(x)&=2^{x+3} - x^{100}
\end{align}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Algoritmus bonyolultsága}
\begin{block}{Algoritmus bonyolultsága \textit{(time complexity)}}
\begin{itemize}
\item Tekintsünk egy $\mathbf{F}$ \structure{számítási feladatot.}
\item Legyen $\mathcal{A}$ az $\mathbf{F}$ egy \structure{megoldási algoritmusa. }
\end{itemize}
Azt mondjuk, hogy az $\mathcal{A}$ algoritmus \alert{bonyolultsága $f(n)$,} ha 
\begin{itemize}
\item az \textit{általános} $n$ méretű input esetén 
\item az $\mathcal{A}$ végrehajtása \alert{nagyságrendileg $f(n)$ lépésben} történik. 
\end{itemize}
\end{block}
\pause
\begin{exampleblock}{Példa: Egész számok szorzása}
\begin{itemize}
\item A megoldási algoritmus az alsó tagozatban tanult ``szorzás papíron''.
\item Az input mérete a tényezők számjegyinek a száma. 
\item Az input általános, ha a számok nem speciális alakúak, pl. egyik sem 10-hatvány.
\item Az algoritmus bonyolultsága $n^2$. 
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Könnyű vagy nehéz?}
\begin{block}{Polinomiális, exponenciális bonyolultság}
Legyen $\mathcal{A}$ az $\mathbf{F}$ feladat egy megoldási algoritmusa.
\begin{itemize}
\item Azt mondjuk, hogy az $\mathcal{A}$ \alert{polinomiális,} ha bonyolultsága \alert{$n^\alpha$} ($\alpha>0$).
\item Azt mondjuk, hogy az $\mathcal{A}$ \alert{exponenciális,} ha bonyolultsága \alert{$\beta^n$} ($\beta>1$).
\end{itemize}
\end{block}
\begin{itemize}
\item Az $\mathbf{F}$ feladatot \textbf{könnyűnek} nevezzük, ha \structure{ismert hozzá polinomiális} megoldó algoritmus. 
\item Az $\mathbf{F}$ feladatot \textbf{nehéznek} nevezzük, ha \structure{ismert hozzá exponenciális} megoldó algoritmus, de \structure{nem ismert polinomiális.} 
\end{itemize}
\pause
\begin{exampleblock}{Példa: Faktorizáció és legnagyobb közös osztó}
\begin{itemize}
\item Az egész számok prímtényezős felbontása \textbf{nehéz.}
\item A legnagyobb közös osztó kiszámítása \textbf{könnyű,} mert az \textit{euklideszi algoritmus} polinomiális (lineáris) bonyolultságú megoldási algoritmus.  
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{A faktorizáció kvantum-könnyű}
\begin{itemize}
\item Kvantumkomputerek a Turing-Neumann modelltől eltérő elven működnek.
\item A kvantumalgoritmusok bonyolultságát a kvantum-biteken \textit{(qubit)} végzett műveletek számával adjuk meg. 
\item \structure{Peter Shor} 1994-ben polinomiális megoldó (kvantum)algoritmust adott a prímtényezős felbontásra. 
\end{itemize}
\begin{columns}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3cm]{Peter_Shor_2017}\\
Peter Shor (MIT) 2017-ben
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=3cm]{IBM_quantum_computer_2021}\\
IBM 100-qubit kvantumszámítógépe 2021-ben
\end{center}
\end{column}
\end{columns}
\end{frame}

%\begin{frame}
%\frametitle{}
%\end{frame}
%
%\begin{frame}
%\frametitle{}
%\end{frame}

%\begin{frame}
%\frametitle{}
%\end{frame}

\section{Kriptográfia}

\subsection{Elméleti alapelvek}

\begin{frame}
\frametitle{Titkosírások tudományos alapja}
\textbf{A történeti háttér:}
\begin{itemize}
\item A titkosírások modern módszerei a \alert{19. század elejétől} terjedtek el.
\item Ezeket a mai napig elsősorban \alert{katonai} vagy \alert{üzleti célokra} használják.
\item Ekkortól próbálják a titkosítási technikákat \alert{tudományos alapokra} helyezni
\end{itemize}
\textbf{A KRIPTOANALÍZIS tudományos módszerei:}
\begin{itemize}
\item \structure{Hagyományos:} Nyelvészet, matematikai statisztika
\item \structure{Modern:} Absztrakt algebra, bonyolultságelmélet, számítástudomány, elliptikus görbék, pszeudo-véletlen sorozatok, kvantumalgoritmusok
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A kriptorendszer alapfogalmai: Rejtjelezés}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=center] (A1) at (0,0) {NYÍLT SZÖVEG\\ (plain text)};
\node[rectangle,fill=red!25,anchor=center] (B1) at (5,0) {REALENIGMASTORY};
\onslide<2->\node[drop shadow,rounded rectangle, draw, fill=green!60,align=center,inner sep=2mm,anchor=center] (A4) at (-3.7,-2) {kulcs\\ (key)};
\node[drop shadow,rectangle, draw, fill=blue!20,align=center,inner sep=2mm,anchor=center] (A2) at (0,-2) {REJTJELEZŐ ELJÁRÁS \\ (encryption)};
\onslide<3-> \draw [->,thick] (A1) to (A2);
\draw [->,thick] (A4) to (A2);
\node[rectangle,fill=red!25,align=center,anchor=center] (B2) at (5,-2) {Ceasar-rejtjel\\kulcs=7};
\onslide<4->\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=center] (A3) at (0,-4) {REJTJELEZETT SZÖVEG\\ (cipher text)};
\draw [->,thick] (A2) to (A3);
\node[rectangle,fill=red!25,anchor=center] (B1) at (5,-4) {YLHSLUPNTHZAVYF};
\end{tikzpicture}
\end{center}
\begin{block}<5->{A kriptorendszer \textbf{kulcsterének} fogalma}
A kriptorendszer olyan \alert{kulcsainak halmaza,} amik lényegesen különböző rejtjelezett szövegeket eredményeznek. 
\end{block}
\end{frame}

\begin{frame}
\frametitle{A kriptorendszer alapfogalmai: Visszafejtés}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=center] (A1) at (0,0) {REJTJELEZETT SZÖVEG\\ (cipher text)};
\node[rectangle,fill=red!25,anchor=center] (B1) at (5,0) {GQJYHMQJDUFWP};
\onslide<2->\node[drop shadow,rounded rectangle, draw, fill=green!60,align=center,inner sep=2mm,anchor=center] (A4) at (-3.7,-2) {kulcs\\ (key)};
\node[drop shadow,rectangle, draw, fill=blue!20,align=center,inner sep=2mm,anchor=center] (A2) at (0,-2) {VISSZAFEJTŐ ELJÁRÁS \\ (decryption)};
\onslide<3-> \draw [->,thick] (A1) to (A2);
\draw [->,thick] (A4) to (A2);
\node[rectangle,fill=red!25,align=center,anchor=center] (B2) at (5,-2) {Ceasar-rejtjel\\kulcs=-5};
\onslide<4->\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=center] (A3) at (0,-4) {NYÍLT SZÖVEG\\ (plain text)};
\draw [->,thick] (A2) to (A3);
\node[rectangle,fill=red!25,anchor=center] (B1) at (5,-4) {BLETCHLEYPARK};
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}
\frametitle{A Ceasar-féle titkosírás rendszer}
\begin{itemize}
\item Tegyük fel, hogy a \alert{26 betűs angol ábécét} használjuk.
\item Kulcsként válasszunk egy számot \alert{$1$ és $25$ között.} 
\item Ebben a példában legyen a kulcs a \alert{$7$-es.} 
\item A nyílt szöveg minden betűjét helyettesítsük azzal a betűvel, ami az \alert{ábécében 7-el utána} van: \structure{A $\mapsto$ H, B $\mapsto$ I,} stb.
\end{itemize}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 1&2&3&4&5&6&7&8&9&10&$\cdots$&24&25&26\\
\hline \rowcolor{yellow!40} A&B&C&D&E&F&G&H&I&J&$\cdots$&X&Y&Z \\ 
\hline \onslide<2->H&\onslide<2-> I&\onslide<2-> J&\onslide<2-> K&\onslide<2-> L&\onslide<2-> M&\onslide<2-> N&\onslide<2-> O&\onslide<2-> P&\onslide<2-> Q&\onslide<2-> $\cdots$&\onslide<2-> E&\onslide<2-> F&\onslide<2-> G \\
\hline 
\end{tabular}
%\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%\hline 1&2&3&4&5&6&7&8&9&10&$\cdots$&33&34&35\\
%\hline \rowcolor{yellow!40} A&Á&B&C&D&E&É&F&G&H&$\cdots$&X&Y&Z \\ 
%\hline \onslide<2->F&\onslide<2-> G&\onslide<2-> H&\onslide<2-> I&\onslide<2-> Í&\onslide<2-> J&\onslide<2-> K&\onslide<2-> L&\onslide<2-> M&\onslide<2-> N&\onslide<2-> $\cdots$&\onslide<2-> D&\onslide<2-> E&\onslide<2-> É \\
%\hline 
%\end{tabular}
\end{center}
\begin{alertblock}{Sebezhetőségek}
\begin{itemize}
\item A kulcstér csak\alert{ $25$ elemű.}
\item Ha ismerjük \alert{egyetlen betű megfejtését,} akkor ismerjük a kulcsot. 
\end{itemize}
\end{alertblock}
\end{frame}

\begin{frame}
\frametitle{A Ceasar-rendszer ``javításai''}
\textbf{A klasszikus monoalfabetikus rendszer}
\begin{itemize}
\item Az ábécé ciklikus eltolásai helyett a betűk \alert{tetszőleges összecserélése.}
\item A kapott kulcstér mérete angol ábécé esetén
\[\color{blue}{26!=403\,291\,461\,126\,605\,635\,584\,000\,000\approx 4\cdot 10^{26}}\]
\item A ma legjobb szuperszámítógép \alert{kb. 370 év alatt} végez ennyi műveletet.
\item \textbf{Sebezhetőség:} A természetes nyelvekben a \alert{betűk a gyakoriságuk alapján} beazonosíthatók.
\end{itemize}
\textbf{Vigen\`ere-rejtjel: A klasszikus polialfabetikus rendszer}
\begin{itemize}
\item A Ceasar-kulcs értéke \alert{függ a betű helyétől.}
\item \textbf{Sebezhetőség:} Fejlett \textit{statisztikai módszerek,} illetve \textit{ismert szövegrészek.}
\end{itemize}
\begin{exampleblock}{Ajánlott irodalom}
\begin{itemize}
\item Edgar Allan Poe: Az aranybogár (1843)
\item Verne Gyula: Nyolcszáz mérföld az Amazonason (1881)
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{A Kerckhoff-féle alapelvek és a ``katasztrófa-forgatókönyv''}
\begin{block}{\textsc{Auguste Kerckhoffs}, \textit{La Cryptographie Militaire}, 1883}
\begin{enumerate}
\item A rendszernek gyakorlatilag, sőt lehetőleg matematikailag is \textbf{visszafejthetetlennek} kell lennie. A \textbf{rendszer maga nem lehet titkos,} nem jelenthet problémát, ha azt ismeri az ellenség.
\item A \textbf{kulcsnak rövidnek és könnyen továbbíthatónak} kell lenni, írott jegyzetek használata nélkül is. 
\item A rendszer legyen használható a \textbf{Morse-távírós} kommunikációban.
\item A rendszernek \textbf{hordozhatónak} kell lennie, egy személy is tudja üzemelni. 
\end{enumerate}
\end{block}
\begin{block}{A modern ``katasztrófa-forgatókönyv'' feltételezései}
\begin{enumerate}
\item Az ellenfél \alert{teljesen ismeri} a kriptorendszerünket.
\item Az ellenfél el tudja olvasni az \alert{összes rejtjelezett szövegünket.}
\item Az ellenfél ismeri \alert{jelentős mennyiségű} rejtjelezett szövegünkhöz tartozó \alert{nyílt szövegünket.} 
\end{enumerate}
\end{block}
\end{frame}


%\begin{frame}
%\frametitle{}
%\end{frame}


\subsection{Napjaink kriptorendszerei}


\begin{frame}
\frametitle{Szimmetrikus kulcsú kriptográfia}
\begin{block}{SZIMMETRIA}
\alert{Ugyanaz a kulcs} szolgál rejtjelezésre és visszafejtésre.
\end{block}
\begin{itemize}
\item 1976: \textbf{DES} (Data Encryption Standard)
\item 2001: \textbf{AES} (Advanced Encryption Standard)
\item AES demó: \texttt{http://www.formaestudio.com/rijndaelinspector/}
\item \structure{Előny:} Gyorsaság, kicsi memóriaigény, matematikai módszerekkel jól ellenőrizhető biztonság (``keverési'' tulajdonságok)
\item \structure{Hátrány}:\textbf{ A kommunikáló feleknek előre meg kell állapodni a \alert{közös titkos kulcsban}} (\textit{key management})
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Nyilvános (aszimmetrikus) kulcsú kriptográfia} 
\begin{block}{ASSZIMETRIA}
Két \alert{különböző kulcsot} használunk a rejtjelezésre illetve a visszafejtésre: egy \textbf{nyilvános} és egy \textbf{privát} kulcsot
\end{block}
\begin{itemize}
\item \structure{Alice nyílt szövege Bobnak} + \alert{Bob nyilvános kulcsa} = \textbf{rejtjelezett szöveg Bobnak}
\item \structure{rejtjelezett szöveg Bobnak} + \alert{Bob privát kulcsa} = \textbf{Alice nyílt szövege Bobnak}
\item A nyilvános kulcsból a privát kulcs kiszámítása \textbf{elméletben lehetséges,} de a \textbf{gyakorlatban nem}
\item 1978: \textbf{RSA} (\textsc{Ronald Rivest, Adi Shamir} és \textsc{Len Adleman})
\item Az RSA biztonsága azon múlik, hogy tudunk-e \alert{több száz számjegyből} álló számokat \alert{prímtényezőkre} bontani.
\end{itemize}
\end{frame}

%\begin{frame}{Kulcsmenedzsment: A Diffie-Hellman--kulcscsere (1976)}
%\begin{center}
%\only<1>{\includegraphics[width=10cm]{diffie_hellman_1.pdf}}%
%\only<2>{\includegraphics[width=10cm]{diffie_hellman_2.pdf}}%
%\only<3>{\includegraphics[width=10cm]{diffie_hellman_3.pdf}}%
%\only<4>{\includegraphics[width=10cm]{diffie_hellman_4.pdf}}%
%\only<5>{\includegraphics[width=10cm]{diffie_hellman_5.pdf}}%
%\only<6>{\includegraphics[width=10cm]{diffie_hellman_6.pdf}}%
%\only<7>{\includegraphics[width=10cm]{diffie_hellman_7.pdf}}%
%\only<8>{\includegraphics[width=10cm]{diffie_hellman_8.pdf}}%
%\end{center}
%\end{frame}


%\begin{frame}
%\frametitle{}
%\end{frame}


\subsection{A kriptográfia matematikai fogalmai}

%\begin{frame}{Digitális kommunikáció, forráskódolás}
%\begin{center}
%\begin{tikzpicture}
%\node[drop shadow,rounded rectangle, draw, fill=green!40,align=center,inner sep=3mm] (A1) at (0,0) {\textbf{INFORMÁCIÓ}\\szöveg, kép, hang, \ldots};
%\node[drop shadow,rounded rectangle, draw, fill=green!40,align=center,inner sep=5mm] (A3) at (8,0) {\textbf{0-1} SOROZATOK\\bitek, bájtok, \ldots};
%\draw [<->,ultra thick] (A1) to node[align=center,above] {\large\textbf{DIGITALIZÁLÁS}} (A3);
%\end{tikzpicture}
%\end{center}
%\begin{columns}
%\begin{column}{3.5cm}
%\textbf{Neumann János} \\
%(1903-1957) \\
%magyar matematikus
%\end{column}
%\begin{column}{6cm}
%\includegraphics[width=3.6cm]{./neumann_janos} 
%\end{column}
%\end{columns}
%\end{frame}

\begin{frame}
\frametitle{A matematikai kriptográfia alapfogalmai}
\textbf{Az üzenet:}
\begin{itemize}
\item $0/1$ sorozat
\item rögzített hosszúságú $0/1$ sorozat
\item nemnegatív egész szám $0,1,\ldots,2^n-1$
\item nemnegatív egész szám $0,1,\ldots,N-1$ tetszőleges számrendszerben
\end{itemize}
\textbf{Ugyanez mondható el a titkosító kulcsról.}
\medskip

\begin{block}{Jelölés}
\begin{itemize}
\item \alert{$m$} nyílt üzenet \textit{\structure{(plain text message)}}
\item \alert{$k$} titkosító kulcs \textit{\structure{(encryption key)}}
\item \alert{$c$} titkosított üzenet \textit{\structure{(ciphertext)}}
\item $\alert{m,k,c} \in \{0,1,\ldots,N-1\}$, ahol $N$ nagy pozitív egész
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Titkosítás \textit{(encryption)} és visszafejtés \textit{(decryption)}}
\begin{block}{Emlékeztető:}
Az \structure{$\text{ENC}$} titkosító eljárás \textit{(encryption)} egy kulcsból és egy nyílt üzenetből készít egy titkosított üzenetet:
\[\alert{(k,m) \xmapsto{\text{ENC}} c}\]
A \structure{$\text{DEC}$} visszafejtő eljárás \textit{(decryption)} egy kulcsból és egy titkosított üzenetből készíti el a nyílt üzenetet:
\[\alert{(k,c) \xmapsto{\text{DEC}} m}\]
\end{block}
\textbf{Matematikai jelölés:}
\begin{itemize}
\item \alert{$c=\text{ENC}(k,m)=\text{ENC}_k(m)$} 
\item \alert{$m=\text{DEC}(k,c)=\text{DEC}_k(c)$} \structure{függvények}
\item \structure{Művelettel:} $c=k*m$.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Kulcs kereső támadás \textit{(key recovery attack)}}
$c,m$ ismert számok, $*$ ismert művelet, határozzuk meg $x$-et:
\[\alert{c=x*m}\]
\begin{itemize}
\item A kulcstér végessége miatt \textbf{próbálgatással} megoldható
\item Az eljárás biztonságosságának mértékegysége: \textbf{DOLLARDAY}
\item \alert{Szivárgás (flaw):} 1 bit információ a kulcsról \structure{megfelezi a kulcsteret}
\item \structure{Gyakori} kulcscsere
\item A kulcsot \structure{random} választjuk a kulcstérből
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Üzenet kereső támadás \textit{(message recovery attack)}}
$c$ ismert szám, $*$ ismert művelet, határozzuk meg $x,y$-t:
\[\alert{c=x*y}\]
\begin{itemize}
\item Nem reménytelen, különösen ha $k$-nak vagy $m$-nek \textbf{erős a struktúrája}
\item Pl. \structure{$0\leq y\leq 999$} és \alert{$x*y=1000x+y$.} 
\item Másik példa a \structure{monoalfabetikus rendszer} feltörése \textit{gyakoriság-analízissel.} 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A $*$ művelet felépítése}
\begin{itemize}
\item $m,k,c \in \{0,1,\ldots,N-1\}$
\item \structure{modulo $n$} jelentése: egy egész szám $n$-el vett \textbf{osztási maradéka}
\item \textbf{Alapműveletek} modulo $N$:
\begin{align*}
x\oplus y &= x+y \pmod{N} \\
x\ominus y &= x-y \pmod{N} \\
x\otimes y &= x\cdot y \pmod{N} \\
x\oslash y &= x/y \pmod{N} 
\end{align*}
\item \alert{Melyik a kakukktojás??}
\item \structure{Algebrai test:} \textbf{halmaz} ÉS \textbf{négy művelet} ÉS \textbf{számolási szabályok}
\item Pl. $\{0,1\}$, műveletek modulo $2$: $\quad\alert{1\oplus 1 = 0.}$
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{RSA}
\begin{itemize}
\item \textbf{RSA} titkosítás:
\[c=\text{ENC}_k(m)=m^k \pmod{N}.\]
\item \textbf{RSA} visszafejtés: \alert{$k$-dik gyök modulo $N$.}
%\item 
\end{itemize}
\begin{alertblock}{RSA biztonsága}
\begin{itemize}
\item A feladat: adott \structure{$x,k,N$,} keressük \structure{$\sqrt[k]{x}\pmod{N}$.} 
\item \textbf{Könnyű,} ha ismert $N$ prímtényezős felbontása.
\item \textbf{Nehéz} egyébként.
\item \textbf{Kvantum-könnyű!} \textit{(Kvantum-támadás)}
\end{itemize}
\end{alertblock}
\end{frame}

\begin{frame}
\frametitle{Az USA poszt-kvantum felhívása}
\begin{center}
\url{https://csrc.nist.gov/Projects/post-quantum-cryptography}
\end{center}
\begin{exampleblock}{NIST Post-Quantum Challange 2017}
\begin{itemize}
\item NIST = National Institute of Standard and Technology
\item Az USA szabványügyi hivatala
\item Nemzetközi felhívás kvantum-biztos kriptográfiai eljárások javaslatára
\item Első három kör: 2017, 2019, 2021.
\item Eredményhirdetés: 2022.
\end{itemize}
\pause
\end{exampleblock}
Valószínűleg el fogják fogadni:
\begin{itemize}
\item Kód alapú: \textbf{klasszikus McEliece}
\item Rács alapú: \textbf{SABER, CRYSTAL}
\item Izogénia alapú: \textbf{SIKE}
\end{itemize}
\end{frame}

\section{Hibajavító kódok}

\subsection{Alapfogalmak}

\begin{frame}{A hibajavító kódok elméletének megalapozása}
\begin{columns}
\begin{column}{6cm}
\begin{center}
\includegraphics[width=5.5cm]{./Richard_Hamming} 
\\\textbf{Richard Hamming} \\(1915-1998) \\amerikai matematikus
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[width=5cm]{./Claude_Shannon} 
\\\textbf{Claude Shannon} \\ (1916-2001) \\amerikai matematikus
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Hibajavítás zajos kommunikációs csatornán}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=east] (A1) at (0,0) {FELADÓ};
\visible<2->{\node[drop shadow,rectangle, draw, fill=green!20,align=center,inner sep=2mm,anchor=center,above=22mm] (K1) at (A1.north) {KÓDOLÁS};}
\node[drop shadow,rectangle, draw, fill=blue!20,align=center,inner sep=2mm,anchor=center] (A2) at (3.6,3) {ZAJOS\\CSATORNA\\{\LARGE\Lightning\;\Lightning\;\Lightning}};
\visible<3->{\node[drop shadow,rectangle, draw, fill=green!20,align=center,inner sep=2mm,anchor=center,above=22mm] (K2) at (A3.north) {DEKÓDOLÁS};}
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=west] (A3) at (7.2,0) {CÍMZETT};
\draw [->,thick] (A1) -- node[align=center,left] {küldött\\üzenet} node[right,color=blue] {[\textbf{ABC}]} (K1);
\visible<2->{\draw [->,thick] (K1) -- node[align=center,above] {kódolt\\üzenet} node[below,color=blue] {[\textbf{ABC}|DE]} (A2.west);}
\visible<3->{\draw [->,thick] (A2) to node[align=center,above] {megkapott\\üzenet} node[below,color=blue] {[\textbf{A\color{red}{X}\color{blue}{C}}\color{blue}|DE]} (K2);}
\visible<4->{\draw [->,thick] (K2) to node[align=center,left] {kézbesített\\üzenet} node[right,color=blue,font=\bfseries] {[ABC]} (A3);}
\visible<5->{\node[left] at (A3.west) {\resizebox{10mm}{10mm}{\Smiley}};}
\end{tikzpicture}
\end{center}
\end{frame}


\begin{frame}{Példa: Hibajavítás a QR-kódban}
\begin{center}
\begin{tikzpicture}
\draw (0,0) node {\qrcode[height=3.5cm,level=L]{Introduction\ to\ code-based\ post-quantum\ cryptography\ 2022}};
\draw (6,0) node {\qrcode[height=3.5cm,level=H]{Introduction\ to\ code-based\ post-quantum\ cryptography\ 2022}};
\visible<2>{%
\draw (0,0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (0,-0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (6,0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (6,-0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};}
\end{tikzpicture}
\end{center}
\begin{itemize}
\item A QR-kódokban az \alert{$\mathbb{F}_{256}$} véges test felett értelmezett \alert{Reed-Solomon kódokat} használják.
\end{itemize}
\end{frame}

\begin{frame}{Lineáris kódok fő paraméterei}
A továbbiakban $\mathbb{F}_q$ egy $q=p^m$ rendű véges testet jelöl, ahol $p$ prím.
\begin{alertblock}{Definíció: $n$ hosszúságú lineáris kód}
\begin{itemize}
\item A $Q$ \textbf{ábécé} az \alert{$\mathbb{F}_q$} véges test.
\item $C\leq \mathbb{F}_q^n$ egy \alert{lineáris altér.}
\end{itemize}
\end{alertblock}
A főbb paraméterek:
\begin{itemize}
\item \textbf{Hosszúság} $n$
\item \textbf{Dimenzió} $k$
\item \textbf{Információs ráta} $R=k/n$
\item \textbf{Minimum távolság} $d$
%\item \textbf{Dekódolási küszöb} $t$
\end{itemize}
\begin{block}{Singleton-korlát}
$k+d\leq n+1$.
%A \structure{legközelebbi szomszéd} algoritmus dekódolási köszöbe \alert{$t=\lfloor\frac{d-1}{2}\rfloor$.}
\end{block}
\end{frame}

\begin{frame}
\frametitle{A Reed--Solomon-kódok}
\begin{itemize}
\item Legyen \structure{$0\leq k \leq n \leq q$.} Legyenek \structure{$\alpha_1,\ldots,\alpha_n$} az $\mathbb{F}_q$ különböző elemei.
\item \alert{$\mathbf{RS}_k=\{(f(\alpha_1),\ldots,f(\alpha_n) \mid f\in \mathbb{F}_q[X], \deg(f)<k \}$}
\end{itemize}
\begin{block}{Tétel}
\begin{itemize}
\item A Reed--Solomon-kód minimum távolsága \structure{$d=n+1-k$.} 
\item A \textbf{Peterson-algoritmus} ki tud javítani \alert{$\lfloor \frac{n-k}{2}\rfloor=\lfloor \frac{d-1}{2}\rfloor$} hibát.
\end{itemize}
\end{block}
\begin{columns}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=3.5cm]{./Reed_Solomon} 
\\\textbf{Irving S. Reed} (1923-2012) 
\\\textbf{Gustave Solomon} (1930-1996) 
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=3.5cm]{./Wesley_Peterson} 
\\\textbf{W. Wesley Peterson} \\ (1924-2009)
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Random kódok}
Nincs annál \textit{könnyebb,} mint jó paraméterekkel rendelkező bináris lineáris kódokat készíteni:
\begin{columns}
\begin{column}{7cm}
\begin{block}{Zajos csatornakódolási tétel (Shannon 1948)}
Értelmezzük a \alert{bináris entrópiafüggvényt:}
\[H(p)=-p\log_2 p-(1-p)\log_2(1-p).\]
Rögzítsük az \structure{$0<R<1$} rátát. Ekkor:
\begin{itemize}
\item kellően nagy $n$ esetén
\item az \alert{$n$ hosszúságú} és \alert{$R$ rátájú}
\item \textbf{``random''} bináris lineáris kód
\item minimum távolsága legalább 
\[\alert{n\cdot H^{-1}(1-R)}.\]
\end{itemize} 
\end{block}
\end{column}
\begin{column}{4cm}
\begin{tikzpicture}[scale=3.2]
%\[H(p)=-p\log_2 p-(1-p)\log_2(1-p).\]
\draw [help lines,color=gray!50] (0,0) grid [step=0.1] (0.7,1);
\draw[very thick] (0,1) node[left] {$1$} -- (0,0) node[below left] {$0$} -- (0.7,0) node[below] {$0.7$};
%\draw[thick,blue] plot [domain=0.001:1,samples=100] (\x,-{\x*log2(\x)-(1-\x)*log2(1-\x)});
\draw[thick,blue] plot [domain=0.001:0.7,samples=100] (\x,{1+\x*log2(\x)+(1-\x)*log2(1-\x)});
\draw (0.35,0) node[below] {$p$};
\draw (0.7,1) node[above] {$1-H(p)$};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}

\subsection{Dekódolási algoritmusok}

\begin{frame}{A hibajavító kódolás}
\begin{itemize}
\item \textbf{Véges ábécé} $Q=\{0,1,\ldots\}$; általában \alert{bináris:} $Q=\{0,1\}$
\item Egy \textbf{$n$ hosszúságú kód} a \structure{ $C\subseteq Q^n$} halmaz részhalmaza
\end{itemize}
\begin{center}
\tikzstyle{place}=[circle,scale=0.5,draw=blue!50,fill=blue!20,thick]
\begin{tikzpicture}[line cap=round,line join=round,>=latex',scale=0.7]
\draw[rounded corners=10,very thick,drop shadow,fill=yellow!30] (-4.5,-1) rectangle (6,6);
\node at (5.4,5.5) [font=\Large] {$Q^n$};
\node (A0) at (-3.76,3.09) [place] {0};
\node (A1) at (-0.5,-0.51) [place] {1};
\node (A2) at (5.34,2.09) [place] {2};
\node (A3) at (1.12,3.67) [place] {3};
\node (A4) at (0.54,5.49) [place] {4};
\node (A5) at (-1.82,1.03) [place] {5};
\node (A6) at (1.84,1.13) [place] {6};
\node (A7) at (-0.06,2.85) [place] {7};
\node (A8) at (3.44,4.17) [place] {8};
\node (A9) at (-1.5,4.37) [place] {9};
\draw[<->] (A3) -- (A8) node[pos=0.5,above] {$d_H$};
\draw[dotted] (A6) circle (1.5);
\draw[thin] (A6) -- +(-30:1.5) node[pos=0.5,above] {$r$};
\draw[thin] (A6)+(30:1.5) node[right] {$B_r(\bm{x})$};
\end{tikzpicture}
\end{center}
\begin{itemize}
\item<1-> Példa: \textbf{3-szoros ismétlő kód:} \alert{$0\mapsto 0|00, \; 1\mapsto 1|11$.}
\item $Q=\{0,1\}$, $C=\{000,111\} \subseteq \{0,1\}^3$.
\end{itemize}
\end{frame}

\begin{frame}{Legközelebbi szomszéd \textit{(maximum likelihood)} dekódolás}
\begin{center}
\tikzstyle{place}=[circle,scale=0.5,draw=blue!50,fill=blue!20,thick]
\begin{tikzpicture}[line cap=round,line join=round,>=latex',scale=0.8]
\draw[rounded corners=10,very thick,drop shadow,fill=yellow!30] (-4.5,-1) rectangle (6,6);
\node at (5.4,5.5) [font=\Large] {$Q^n$};
\node (A0) at (-3.76,3.09) [place] {0};
\node (A1) at (-0.5,-0.51) [place] {1};
\node (A2) at (5.34,2.09) [place] {2};
\node (A3) at (1.12,3.67) [place] {3};
\node (A4) at (0.54,5.49) [place] {4};
\node (A5) at (-1.82,1.03) [place] {5};
\node (A6) at (1.84,1.13) [place] {6};
\node (A7) at (-0.06,2.85) [place] {7};
\node (A8) at (3.44,4.17) [place] {8};
\node (A9) at (-1.5,4.37) [place] {9};
\visible<2->{\node (R) at (2.3,2) [place,draw=red!80,fill=red!50] {y};
\draw[->,red] (3.8,3.5) node[align=center,right] {megkapott\\$y\not\in C$} -- (R);}
\visible<3>{\foreach \x in {0,...,9} \draw[very thin] (A\x) -- (R);};
\visible<4->{\draw[thick,->] (R) -- (A6);
\node[align=center,below right] at (A6) {legközelebbi kódszó\\$x=y-e$};}
\end{tikzpicture}
\end{center}
\begin{itemize}
\item<1->$\textcolor{blue}{0|00,1|00,0|10,0|01} \mapsto 0|00 \mapsto \mathbf{0}$\\ $\textcolor{blue}{1|10,1|01,0|11,1|11} \mapsto 1|11 \mapsto \mathbf{1}.$ 
\item $\mathrm{Prob}(\text{$k$ hiba}) > \mathrm{Prob}(\text{$k$-nál több hiba})$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A dekódolási feladat}
\begin{exampleblock}{A legközelebbi szomszéd dekódolási feladat}
\textbf{Adott:} a \structure{$C\subseteq Q^n$} kód és az \structure{$\bm{y} \in Q^n$} vektor. \\ \smallskip
\textbf{Keresünk:} olyan \structure{$\bm{x}\in C$} kódszót, amire \alert{$d_H(\bm{x},\bm{y})$ minimális.}
\end{exampleblock}
\begin{exampleblock}{A küszöbértékes dekódolási feladat}
\textbf{Adott:} a \structure{$C\subseteq Q^n$} kód, az \structure{$\bm{y} \in Q^n$} vektor és a \structure{$t$} pozitív egész. \\ \smallskip
\textbf{Keresünk:} olyan \structure{$\bm{x}\in C$} kódszót, amire 
\[\alert{d_H(\bm{x},\bm{y})\leq t.}\]
Ha nincs ilyen, akkor az eredmény legyen \textbf{``NINCS''.}
\end{exampleblock}
\begin{itemize}
\item A \textbf{küszöbértékes dekódolás} lényegesen könnyebb a legközelebbi szomszéd dekódolásnál, ha \structure{$t<d(C)/2$.}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A dekódolási feladat lineáris kódokra}
Legyen $C$ \textbf{lineáris kód} a szokásos paraméterekkel: \structure{$q,n,k,d$.}
\begin{itemize}
\item $C$ megadható egy $\mathbb{F}_q$ feletti \alert{$k\times n$} \textbf{generátormátrixszal.} 
\item A generátormátrix $nk$ elemet tartalmaz, tehát a feladat mérete bitben számolva
\[\alert{(nk+n)\log_2(q).}\]
\item Mivel \structure{$k\leq n$,} a feladat méretének nagyságrendjét tekinthetjük \alert{$n^2$-nek.}
\end{itemize}
\begin{block}{Állítás}
\begin{itemize}
\item A \textbf{kimerítéses keresési eljárás} mindkét dekódolási feladatra \alert{exponenciális bonyolultságú} megoldási algoritmust ad az \structure{$n$ paraméterben.} 
\item \alert{Rögzített $q$} mellett a Reed--Solomon-kódok dekódolása \structure{\textit{könnyű.}}
\item A Petersen-algoritmus bonyolultsága \alert{$n$-ben polinomiális.} 
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{A dekódolás \textit{nehéz} --- még a bináris esetben is}
Random bináris lineáris kódok \textit{használhatatlanok}  a gyakorlatban:
\begin{block}{Tétel (Berlekamp, McEliece, van Tilborg, 1978)}
Bináris lineáris kódok esetén a küszöbértékes dekódolási feladat \textbf{\textit{nagyon nehéz}} (\textit{''NP-teljes''}).
\end{block}
\begin{columns}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./McEliece} 
\\\textbf{Robert McEliece} \\(1942-2019) 
\end{center}
\end{column}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./Berlekamp} 
\\\textbf{Elwyn Berlekamp} \\(1940-2019) 
\end{center}
\end{column}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./vanTilborg} 
\\\textbf{Henk van Tilborg} \\(1947-) 
\end{center}
\end{column}
\end{columns}
\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}






\subsection{Résztest részkódok}

\begin{frame}
\frametitle{Az általánosított Reed--Solomon-kód}
\begin{alertblock}{Definíció: Általánosított Reed--Solomon-kód}
Legye $q$ prímhatvány, $0\leq k\leq n \leq q$. Legyenek \structure{$\alpha_1,\ldots,\alpha_n$} az $\mathbb{F}_q$ különböző elemei, \structure{$v_,\ldots,v_n$ az $\mathbb{F}_q$} nem nulla elemei.
\[\alert{\mathbf{GRS}_k(\bm{\alpha},\bm{v})=\{(v_1f(\alpha_1),\ldots,v_nf(\alpha_n)) \mid f\in\mathbb{F}_q[X],\, \deg(f)<k\}.}\]
\end{alertblock}
\begin{itemize}
\item A \textit{Reed--Solomon} és az \textit{általánosított Reed--Solomon-kódok} paraméterei \alert{megegyeznek.}
\item A \structure{Peterson-dekódolás} az általános esetben is működik.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Lineáris kódok résztest részkódjai}
\begin{alertblock}{Definíció: Résztest részkód}
Legyen \structure{$q=p^m$ prímhatvány} és \structure{$C\leq \mathbb{F}_q^n$} lineáris kód $\mathbb{F}_q$ felett. Legyen
\[\alert{C|_{\mathbb{F}_q}=C\cap \mathbb{F}_p^n.}\]
Ekkor $C|_{\mathbb{F}_q} \leq \mathbb{F}_p^n$ \textit{lineáris kód} $\mathbb{F}_p$ felett.  
\end{alertblock}
\pause
\begin{itemize}
\item A résztest részkód \structure{minimum távolsága} legalább akkora, mint az eredeti kódé.
\item Az eredeti kód \textbf{dekódolási eljárásai alkalmazhatók} a résztest részkód esetén is
\item Küszöbértékes dekódolás esetén a küszöbérték \alert{megőrződik.} 
\item A résztest részkód \structure{dimenziója} 
\[\dim(C|_{\mathbb{F}_q})\geq n-m(n-k).\]
\item Nagy $m$-re pontatlan a becslés, de \textbf{nehéz} sokkal jobbat mondani.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Reed--Solomon-alapú bináris kódok}
\begin{alertblock}{Definíció: Alternáns kód}
Az általánosított Reed--Solomon-kódok résztest részkódjait \alert{alternáns kódoknak} nevezzük.
\end{alertblock}
\begin{itemize}
\item Az alternáns kód konstrukcióval bináris lineáris kódok egy széles osztályát kapjuk.
\item Ezek paraméterei nem különösebben jók.
\item Nagy előnyük, hogy ismert hozzájuk polinomiális dekódolási eljárás.
\item Tehát megfelelő \structure{$t$ küszöbértékkel} a \alert{dekódolásuk \textit{könnyű}.}
\end{itemize}
\pause
Fontos alternáns kód altípusok:
\begin{itemize}
\item \structure{BCH} \textit{(jól skálázható)}
\item \structure{bináris Goppa} \textit{(a várt küszöbérték duplájáig dekódolható)}
\item \structure{Srivastava}
\end{itemize}
\end{frame}

\definecolor{cadmiumgreen}{rgb}{0.0, 0.42, 0.24}
\definecolor{darkpastelgreen}{rgb}{0.01, 0.75, 0.24}

\begin{frame}
\frametitle{Az $n,k,q$ paraméteres kódok tengere}
\begin{center}
\begin{tikzpicture}
\node at (7.9,6.3) {$n$ hosszúságú, $k$ dimenziós lineáris kódok $\mathbb{F}_q$ felett};
\filldraw[fill=blue!40,rounded corners=20] (0,0) rectangle (12,6);
\node at (6,4) [blue,right,font=\huge] {random kódok};
\filldraw[fill=green!40,rounded corners=5] (0.6,0.5) rectangle (1.5,1.3);
\node at (1.5,1.1) [cadmiumgreen,right,font=\Large] {strukturált kódok};
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}
\frametitle{A strukturált kódok szigete}
\begin{center}
\begin{tikzpicture}
\fill[fill=blue!40] (-1,-1) rectangle (6,6);
\filldraw[fill=green!40,rounded corners=10] (-0.3,-0.3) rectangle (5.3,5.3);
\draw[thick] (-0.3,4.5) -- (-2,4) node[left] {strukturált kódok};
% 2-
\visible<2->{\draw[very thick,dashed] (0.2,0.2) rectangle (4.8,4.8);
\draw[thick] (0.2,4) -- (-2,3) node[left] {kódok gyors dekóderrel};}
% 3-
\visible<3->{\filldraw[fill=gray!40,rounded corners=10] (0.8,0.8) rectangle (3,3);
\draw[thick] (0.8,2.5) -- (-2,2) node[left] {alternáns kódok};}
% 4-
\visible<4->{\filldraw[fill=darkpastelgreen,rounded corners=3] (1.1,1.2) rectangle (1.8,2);
\draw[thick] (1.1,1.5) -- (-2,1) node[left] {bináris Goppa kódok};}
\end{tikzpicture}
\end{center}
\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}


\section{Kód alapú kriptográfia}

\subsection{Klasszikus McEliece}

\begin{frame}
\frametitle{A McEliece-féle kriptoséma (1978)}
Tegyük fel, hogy \structure{Alice} egy $k$ bites \alert{$\bm{m}\in \mathbb{F}_2^k$} titkos üzenetet akar \structure{Bobnak} küldeni.

%\textbf{Kulcs generálás}
\begin{exampleblock}{Kulcs generálás}
\begin{enumerate} [<+->]
\item Bob választ egy kellően nagy \structure{$q=2^m$} $2$-hatványt, \structure{$k<n\leq q$} egészt és \structure{$t$ küszöbszámot} úgy, hogy a megfelelő paraméterekkel rendelkező \textbf{alternáns kód} létezik. 
\item Bob választ random \alert{$\alpha_1,\ldots,\alpha_n$} és \alert{$v_1,\ldots,v_n\in \mathbb{F}_q$} elemeket és megkonstruálja a 
\[C=\mathbf{GRS}_k(\bm{\alpha},\bm{v}) \cap \mathbb{F}_2^n\]
bináris alternáns kódot.
\item Bob \structure{képes $t$ hibát javítani} $C$-ben, mert ismeri az \alert{$\alpha_i,v_i$} értékeket. Ezek az értékek alkotják Bob \textbf{privát kulcsát.} 
\item Legyen \structure{$G$} a $C$ egy \textit{generátormátrixa.} Ez Bob \textbf{nyilvános kulcsa,} ezt elküldi Alicenak.
\end{enumerate}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Titkosítás és visszafejtés a McEliece-sémában}
%\textbf{Titkosítás}
\begin{exampleblock}{Titkosítás}
\begin{enumerate} %[<+->]
\item Alice generál egy \textbf{random} \alert{$t$ súlyú} \structure{$n$ hosszú} \alert{$\bm{e}\in\mathbb{F}_2^n$} vektort.
\item Alice kiszámítja az
\[\bm{m}'=\bm{m}G+\bm{e}\]
vektort és elküldi Bobnak.
\end{enumerate}
\end{exampleblock}
%\textbf{Visszafejtés}
\begin{exampleblock}{Visszafejtés}
\begin{enumerate}[<+->]
\item Bob \textit{(polinomiális) dekódolási algoritmusa} meg tudja határozni azt az \textbf{egyetlen} \structure{$\bm{y}\in C$} kódszót, amire
\[d_H(\bm{m'},\bm{y})\leq t.\]
\item Ez pontosan az \alert{$\bm{m}G$} kódszó. 
\item Az
\[\bm{m}G=\bm{y}\]
lineáris egyenletrendszer megoldásával Bob \structure{meghatározza az $\bm{m}$ üzenetet. }
\end{enumerate}
\end{exampleblock}
\end{frame}

\subsection{Kriptoanalízis}

\begin{frame}
\frametitle{A McEliece-séma biztonsági elemzése \textit{(kriptoanalízis)}}
\begin{itemize}
\item \textbf{Privát kulcs:} \alert{$\alpha_1,\ldots,\alpha_n,v_1,\ldots,v_n$.} Ezekből konstruáljuk a \structure{$C$ alternáns kódot.}
\item \textbf{Nyilvános kulcs:} Az alternáns kód \alert{$G$ generátormátrixa.}
\item A séma biztonságos, ha a \structure{nyilvános kulcsból} a \structure{privát kulcs} meghatározása \textbf{nehéz feladat.}
\item Ennél kicsit többet várunk el: $G$ \alert{ne legyen megkülönböztethető} egy hasonló méretű \textbf{random mátrixtól.} 
\item Ekkor a biztonságot garantálja, hogy random mátrix esetén a \structure{dekódolási felada}t \textbf{nehéz} (Berlekamp--McEliece--van Tilborg-tétel).
\item Ehhez az \alert{$n,k,t$} értékeket \textbf{kellően nagyra} kell választani. 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Klasszikus McEliece modern köntösben}
\begin{itemize}
\item McEliece eredeti 1978-as javaslata a \textbf{bináris Goppa kódokra} épül.
\item Ez a \structure{$v_1,\ldots,v_n$} \textit{multiplikátoroknak} egy speciális megválasztását jelenti.
\item Erre az osztályra a mai napig \alert{nem sikerült} a privát kulcs visszafejtése.
\item Az \textbf{eredeti javaslatban} szereplő paraméterek:
\[\alert{n=1014, \quad k=524, \quad t=50.}\]
\item A \textbf{2020-as NIST javaslatban} a legmagasabb 256 bites biztonsági szinthez javasolt paraméterek:
\[\alert{n=6686, \quad k=128, \quad t=13.}\]
\item \textbf{Túl nagy nyilvános kulcs:} \structure{$32$, illetve $836$ kilobyte.} 
\item \textit{Rengeteg ötlet és javaslat a nyilvános kulcs méretének lényeges csökkentésére -- \alert{eddig sikertelenül...}}
\end{itemize}
\end{frame}

\begin{frame}
\begin{center}
\Huge \structure{KÖSZÖNÖM A FIGYELMET!} \hspace{2cm}
\end{center}
\vspace{1cm}
\pause
\Large
\textbf{Érdeklődőknek:}
\begin{itemize} 
\item szakdolgozati témák
\item TDK dolgozati témák
\item NSUCRYPTO verseny felkészítés
\end{itemize}
\end{frame}



\end{document}

