Select Git revision
main.tex 14.85 KiB
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Rapport de mathématique
% Document LaTeX
% Version 1.0 (22.09.22)
%
% Ceci est un rapport sur un TP de mathématique, ou nous devions
% cracker une clefs RSA que nous avions intercepté.
% Par : Adrian Spycher, Flavio Moronne, Jad Tayan
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%----------------------------------------------------------------------------------------
% PAQUETS ET AUTRES CONFIGURATIONS DU DOCUMENTS
%----------------------------------------------------------------------------------------
% --- document ---
\documentclass[11pt]{report} % Style du document et taille de la font
\usepackage[T1]{fontenc} % Définit font encoding
\usepackage[utf8]{inputenc} % Définit character encoding
\usepackage[french]{babel} % Définit la langue du document
\usepackage{hyperref} % Ajoute des liens hyperref aux tables
\usepackage[ % Change les dimensions du document
margin=1.1in,
tmargin=1.25in,
bmargin=1.25in]{geometry}
% --- texte ---
\usepackage[document]{ragged2e} % Gère l'allignement du texte
\usepackage{setspace} % Gère les interlignes
\usepackage{afterpage} % Gère les sauts de page
\usepackage{pifont} % Ajoute des fonts (cmark, xmark)
\usepackage{titlesec} % Format les titres et sections
\usepackage[titles]{tocloft} % Format les toc / lof / lot
\usepackage{fancyhdr} % Format les header et footer
\usepackage{textgreek} % Ajoute l'alphabet grec
\usepackage{enumitem} % Ajoute des fonctionalitées au enum
% --- graphique ---
\usepackage{graphicx} % Gérer les images
\usepackage{subcaption} % Permet de gérer des sous-images
\usepackage{xcolor} % Ajoute une palette de couleur
\usepackage{booktabs} % Améliorer le rendu des tables
\usepackage{hhline} % Gère les bordures des tableaux
\usepackage{colortbl} % Ajoute les couleurs pour les tableaux
\usepackage{xfrac} % Fait de plus beau tableau
\usepackage{multirow} % Pour faire du multirow
\usepackage{multicol} % Pour faire du multicol
% --- diagramme ---
\usepackage{algorithm} % Pour créer des algorithm
\usepackage{algpseudocode} % Pour créer des pseudocode
% --- math ---
\usepackage{amsmath, amssymb, amsthm} % Utilise les fonctionalitées mathématique
\usepackage{mathdots} % Rends conforme les math et la font
\usepackage{bm} % Ajouts des signes mathématique en bold
\usepackage{listofitems} % Implémente les listes
%----------------------------------------------------------------------------------------
% INFORMATIONS DU DOCUMENT ET COMMANDE
%----------------------------------------------------------------------------------------
% --- Variables ---
\def \mytitle{Rapport travail pratique RSA}
\def \myauthor{Adrian \textsc{Spycher}, Flavio \textsc{Morrone} \& Jad \textsc{Tayan}}
\def \myuniversity{\href{https://www.hesge.ch/hepia/}{HEPIA}}
\def \mydepartment{\href{https://www.hesge.ch/hepia/bachelor/informatique-et-systemes-communication}{Informatique et systemes communication}} \def \myteacher{Niklaus \textsc{Eggenberg}}
\def \mymodule{Sciences en ISC}
\def \mycourse{Mathématiques appliquées à l'ingénierie}
\def \mycoursecode{ISC\_122}
% --- Format des sections et paramètres ---
% spécifié le repertoire des images
\graphicspath{ {./figures/} }
% header & footer
\pagestyle{fancy}
\lhead{}
\rhead{\textsc{\leftmark}}
\setlength{\parindent}{0mm} % no indent paragraph
% interligne
\onehalfspacing
% pour ajouter des points au toc/tof/tot
\renewcommand{\cftchapdotsep}{\cftdotsep}
% chapter design
\titleformat{\chapter}[display]
{\Large \bfseries}
{\chaptername \space \thechapter}
{5mm} {}
\titlespacing*{\chapter}{0mm}{7mm}{10mm}
% création des notes
\theoremstyle{remark}
\newtheorem*{remark}{Notes}
% change default symbole pour les listes
% \setlist[itemize]{label=\textbullet}
% --- Fonctions ---
% an empty page
\newcommand\myemptypage{
\null
\thispagestyle{empty}
\addtocounter{page}{-1}
\newpage
}
% espacement entre les lignes/colonnes d'un tableau
\newcommand{\rowsep}[1]{\renewcommand{\arraystretch}{#1}} % 1.3, def : 1
\newcommand{\colsep}[1]{\setlength{\tabcolsep}{#1}} % def : 6pt
% tableau header
\newcommand{\thead}[1]{\multicolumn{1}{c}{\bfseries #1}}
% prog sign eq et not eq
\newcommand{\myprogeq}{=\!=}
\newcommand{\myprogneq}{\neq} %? (=\!\!\!\neq\!\!\!=) faire plus long ?
\newcommand{\myprogand}{\text{\footnotesize \&\&}}
\newcommand{\myprogor}{\text{\footnotesize ||}}
\newcommand{\myprogmod}{\text{\textsf{\footnotesize \%}}}
\newcommand{\myprogpp}{+\!\joinrel\!+}
\newcommand{\myprogmm}{-\!\joinrel\!-}
% algorithme indent
\algdef{SE}[SUBALG]{Indent}{EndIndent}{}{\algorithmicend\ }%
\algtext*{Indent}
\algtext*{EndIndent}
\begin{document}
\pagenumbering{roman}
%----------------------------------------------------------------------------------------
% PAGE DE TITRE
%----------------------------------------------------------------------------------------
\begin{titlepage}
\begin{center}
\vspace*{1cm}
{ \huge \textbf{\mytitle}}
\vspace{0.5cm}
\myauthor
\vfill
\includegraphics[width=0.75\textwidth]{cryptography.jpg}
\vfill
\myuniversity \\
\mydepartment \\
\myteacher \\
\mymodule \\
\mycoursecode $\ -$ \mycourse \\
\today
\end{center}
\end{titlepage}
\newpage
\pagenumbering{arabic} % Commencer la numérotation numérique des pages (1,2,3...)
%----------------------------------------------------------------------------------------
% LISTES DES PAGES CONTENU/FIGURES/TABLES
%----------------------------------------------------------------------------------------
\tableofcontents
\addcontentsline{toc}{chapter}{Table des matières}
\newpage
\renewcommand{\listfigurename}{Liste des figures} % Sinon : "Table de figures"
\listoffigures
\addcontentsline{toc}{chapter}{Liste des figures}
\newpage
%----------------------------------------------------------------------------------------
% INTRODUCTION
%----------------------------------------------------------------------------------------
\chapter{Introduction}
\label{cha:Introduction}
% Ecrivez une brève introduction sur le contexte du TP. Soyez créatifs pour mentionner les
% fondements théoriques du cours sans pour autant copier les slides !
\newpage
%----------------------------------------------------------------------------------------
% MÉTHODOLOGIE
%----------------------------------------------------------------------------------------
\chapter{Méthodologie}
\label{cha:Méthodologie}
% --- Section 2.1 : Description du problème ---
\section{Description du problème}
\label{sec:Description du problème}
% Briève description du problème
% --- Section 2.2 : Méthode de résolution ---
\section{Méthode de résolution}
\label{sec:Méthode de résolution}
% Rappelez-vous que vous devez convaincre vos supérieurs que votre méthode est la bonne,
% mais que, comme tout bon supérieur qui se doit, il ne comprendra pas les détails, mais
% aimera entendre le nom de vos informateurs et vos sources!
% Pensez à TOUJOURS justifier vos propos. Vos supérieurs sont très à cheval là-dessus. Evitez les « on
% sait que », « on montre que », les relatifs vagues du genre « très long » ou « trop long » ou encore
% les conclusions sans fondement du type « A est plus complexe que B ». Posez-vous toujours la
% question « pourquoi est-ce le cas » et, si la réponse n'est pas triviale, expliquez (parfois, 3 mots
% suffisent !).
% TODO : add bibliogrpahy
Pour pouvoir cracker cette clefs RSA, nous avons utilisé la méthode de la factorisation de Fermat.
C'est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel, autrement dit, il va nous aider à retrouver $p$ et $q$ qui composent $n$.
Dans ca factorisation, Fermat nous dit que tout entier naturel impair $n$ se décompose en la différence de deux carrés qui peuvent être ensuite factorisé, on obtient :
\[
n = a^2 - b^2 = (a + b)(a - b) = p \cdot q
\]
Dans notre cas, on assicie la valeur de $p$ à $a + b$ et la valeur de $q$ à $a - b$.
Si $p$ et $q$ sont tout deux différents de 1, alors ce sont des facteurs non triviaux de $n$.
Autrement, on se retrouverait avec $n = n \cdot 1$, qui signifirait que $n$ est premier.
Algébriquement, on voit que :
\[
b^2 = a^2 - n
\]
Sachant que $a$ et $b$ sont deux nombre entier, on cherche une valeur de $a$ qui vérifie bien que $b^2$ ait une racine entière.
Le point de départ de $a$ serra $\ \sqrt[]{n} \ $ arrondis au supérieur, car en-dessous, $b^2$ serait inférieur ou égale à 0, ce qui est impossible.
\newpage % prettier
L'algorithme que nous avons fait se présente alors sous cette forme :
\begin{figure*}[!h]
\centering
\begin{subfigure}{.5\linewidth}
\begin{algorithmic}
\setstretch{1.3}
\Procedure{Fermat factorization}{$n$}
\State $a \gets $ ceil($\ \sqrt[]{n} \ $)
\State $\text{b2} \gets a^2 - n$
\While {b2 is not square}
\State $a \gets a + 1$
\State $\text{b2} \gets a^2 - n$
\EndWhile
\State $b \gets \sqrt[]{\text{b2}}$
\State \Return $a, b$
\EndProcedure
\end{algorithmic}
\end{subfigure}
\end{figure*}
% TODO : add bibliogrpahy
Pour savoir si $b^2$ avait une racine entière, nous avons utilisé une méthode que nous avons retrouver sur \textit{StackOverflow} qui est basé sur l'algorithme Babyloniens aussi appelé l'algorithme de Héron.
Cette algorithme cherche la racine en calculant, à chaque itération, la moyenne arithmétique de $b^2$, en partant de la moitier de $b$.
Si une valeurs testé est répété, c'est que la racine n'est pas entière.
Après avoir récupérer $p$ et $q$, nous pouvons retrouver la clef privée $d$, notamment en calculant la valeur de $\phi$ :
\[
\phi = (p - 1) \cdot (q - 1)
\]\[
d = \text{l'inverse modulaire de } \phi \text{ de } e
\]
On peut maintenant alors décodé le message en clair $M$ en utilisant l'exponentiation rapide de sur le message chiffré $\mu$.
\[
M \equiv_n \: \mu^d
\]
Et c'est comme ça que nous avons déchiffré le message.
% --- Section 2.3 : Application ---
\section{Application}
\label{sec:Application}
% Sans pour autant fournir votre code ni une documentation de ce dernier (le boss n'est pas
% programmeur !), décrivez votre approche dans les grandes lignes. Privilégiez le « Pourquoi cela
% fonctionne » plutôt que le « comment l'avons-nous codé ». Mentionnez également les éventuelles
% astuces d'implémentation non triviales ou les bugs rencontrés, qui assureront aux prochains agents
% de ne pas reproduire les mêmes erreurs !
\subsubsection{Le problème du C}
Pour implémenter ces algorithmes, nous avions d'abord choisis de le faire en C.
Car le C étant compile et très proche de la machine, il est extrêmement rapide par rapport au Python qui était proposé.
Malheureusement, après avoir implémenter la factorisation de Fermat, nous avons remarqué que le C n'était pas capable de gérer des nombres supérieurs à 64 bits.
Nous avons essayer d'utilisé les \textit{uint128} pour pallier se problème, mais ce n'était pas suffisant.
En plus de ne pas être pris en charge par des fonctions triviales comme \textit{printf} ou \textit{sqrt}, une force mystérieuse agissait sur lui de façons à ce qu'il fasse des erreurs de calcule.
Nous avons alors décidé de traduire notre code C en Python de façon à ne plus avoir ces problèmes.
\begin{remark}
Nous avons appris que le standard C 23, qui sort en 2023, prendra beaucoup plus en charge le \textit{uint128}.
\end{remark}
\subsubsection{L'optimisation}
En Python, nous n'avons pas eu de problème, tout à été simple à implémenter.
Ce qui nous a demandé le plus de réfléxion était l'optimisation du code, afin d'attendre le moins longtemps pour cracker la clef RSA.
Nous avons remarqué assez vite qu'un problème se trouvait dans la condition de sortie de la boucle \textit{while} de la factorisation de Fermat.
En effet, nous pensions que trouver une racine entière à l'aide de l'algorithme de Héron était la façon la plus rapide de calculer notre résultat.Car pour nous, la fonction \textit{sqrt} de Python était très lente comparé à l'algorithme de Héron, mais en réalité non.
Nous avons alors choisis de changer la condition en utilisant directement :
\begin{figure*}[!h]
\centering
\begin{subfigure}{.5\linewidth}
\begin{algorithmic}
\setstretch{1.3}
\While {$(a + sqrt(\text{b2}))(a - sqrt(\text{b2})) \myprogneq n$}
\State \dots
\EndWhile
\end{algorithmic}
\end{subfigure}
\end{figure*}
Après avoir changer cette ligne, notre code à été nettement plus rapide, avec une résolution de plus ou moins 45 minutes.
\begin{remark}
La factorisation de Fermat fonctionne très rapidement si $p$ et $q$ sont proche, ce qui n'était forcément pas notre cas.
Sur une autre clef, nous avons pris 5 minutes.
\end{remark}
\newpage
%----------------------------------------------------------------------------------------
% RÉSULTATS
%----------------------------------------------------------------------------------------
\chapter{Résultats}
\label{cha:Résultats}
% N'oubliez pas de présenter votre résultat final et convainquez vos dirigeants de votre performance
% hors normes. Expliquez pourquoi vous avez réussi à craquer un code que la théorie dit devoir
% prendre des milliards d'années, et comment votre propre gouvernement devrait s'y prendre pour
% protéger ses messages !
\newpage
%----------------------------------------------------------------------------------------
% CONCLUSION
%----------------------------------------------------------------------------------------
\chapter{Conclusion}
\label{cha:Conclusion}
% faire une brève conclusion
\newpage
%----------------------------------------------------------------------------------------
% BIBLIOGRAPHIE
%----------------------------------------------------------------------------------------
\chapter*{Bibliographie}
\addcontentsline{toc}{chapter}{Bibliographie}
% \bibliographystyle{plain}
% \bibliography{bibliography.bib}
\newpage
%----------------------------------------------------------------------------------------
\end{document}