\documentclass[11pt]{article}
\makeatletter
\usepackage[ american,greek]{babel}
%\usepackage{textcase}
\usepackage{amsmath,amsfonts}
\usepackage[iso-8859-7]{inputenc}
%\usepackage{kerkis}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\sg}{\selectlanguage{greek}}
\newcommand{\sa}{\selectlanguage{american}}
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}
%\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
%\newtheorem{or}{Ορισμός}
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\newcommand{\bv}{\sa \begin{verbatim}}
\newcommand{\ev}{\end{verbatim} \sg}

\makeatother

\begin{document}                    
%\title{Σύντομος Οδηγός Χρήσης του \textlatin{gp-pari}}
%\author{A.K}
%\maketitle
\selectlanguage{greek}
\section*{Ο αλγόριθμος \textlatin{RSA}.}
Ο αλγόριθμος \textlatin{RSA} ανακαλύφθηκε το 1978 από τους 
\textlatin{Ron Rivest}, \textlatin{Adi Shamir} και \textlatin{Leonard Adlerman}. 

Ξεκινάμε με δύο μεγάλους πρώτους αριθμούς $p,q$. 
Διαλέγουμε $1< e< pq$ τέτοιο ώστε $(e,(p-1)(q-1))=1$. Δηλαδή
ένα αντιστρέψιμο στοιχείο στην πολ/κή ομάδα  $\mathbb{Z}_{(p-1)(q-1)}^*$. 
Υπολογίζουμε τον αντίστροφο του $e \mod (p-1)(q-1)$, 
δηλαδή την λύση της ισοδυναμίας 
\[
ed \equiv 1 \mod (p-1)(q-1)=\phi(pq). 
\]
Η συνάρτηση απόκρυψης είναι $c(t):=t^e \mod pq$, δηλαδή κάθε 
ακέραιος $t$ κρυπτογραφείται στον $c(t)$. 
H συνάρτηση αποκρυπτογράφησης είναι $t^d \mod pq$, δηλαδή προκειμένου να 
αποκρυπτογραφήσουμε το κρυπτογραφημένο μήνυμα υψώνουμε στην $d$. 

To δημόσιο κλειδί είναι το ζευγάρι $\{pq,e\}$. To ιδιωτικό κλειδί είναι o 
αριθμός $d$ το οποίο το κρατάμε μυστικό.

Το δημόσιο κλειδί το δίνουμε σε όλους, που θέλουμε να μας στείλουν ένα μήνυμα 
Μόλις λάβουμε ένα κρυπτογραφημένο μήνυμα το αποκρυπτογραφούμε με χρήση 
το κλειδιού $d$. 

H ουσία του αλγορίθμου είναι ότι ο κακόβουλος παραβιαστής του 
κρυπτογραφημένου μηνύματος θα πρέπει να παραγοντοποιήσει τον 
αριθμό $pq$ κάτι που είναι απελπιστικά χρονοβόρο. 

Στην εργαστηριακή αυτή άσκηση θα πρέπει να γράψετε ένα πρόγραμμα
το οποίο θα χρησιμοποιεί το μέθοδο \textlatin{rsa} προκειμένου 
να κρυπτογραφηθεί ένα μήνυμα 

Χρειαζόμαστε ένα τρόπο να μετατρέπουμε μια φράση κειμένου σε 
μια ακολουθία αριθμών. 
Αυτό στο \textlatin{pari} μπορεί να υλοποιηθεί ως εξής:

Oρίζουμε μία λίστα που να περιέχει χαρακτήρες με την εντολή:
\sa
\begin{verbatim}
{alphabet=[" ","A","B","C","D","E","F","G","H","I","J","K","L","M",
           "N","O","P","Q","R","S","T","U","V","W","X","Y","Z"];
}
\end{verbatim}
\sg
Στα στοιχεία της λίστας έχουμε πρόσβαση ως εξής:
\sa
\begin{verbatim}
alphabet[4]
%2 = "C"
\end{verbatim}
\sg
Δηλαδή η εντολή \textlatin{alphabet[4]} επιστρέφει το τέταρτο 
στοιχείο της λίστας που είναι το \textlatin{"C"}. 

Γράφοντας τις εντολές 
\sa
\begin{verbatim}
{lettertonumber(l,n)=
     for(n=1,27,if(alphabet[n]==l,return(n)));
     error("invalid input.")
}
\end{verbatim}
\sg
Ορίζεται μία νέα εντολή του \textlatin{pari} η 
\textlatin{lettertonumber}. Αυτή είναι η αντίστροφη 
συνάρτηση του \textlatin{alphabet[n]} και επιστρέφει τον 
αριθμό που αντιστοιχεί σε ένα γράμμα. 
Δοκιμάστε να την τεστάρετε δίνοντας 
\sa
\begin{verbatim}
lettertonumber("G")
%4 = 8
\end{verbatim}
\sg
Δηλαδή το γράμμα \textlatin{G} βρίσκετε στην έβδομη θέση 
της λίστας που δημιουργήσαμε προηγουμένως. 
Θεωρήστε το μήνυμα προς κρυπτογράφηση:
\textlatin{EPITHESH AYRIO TO PRWI}. 
Το μήνυμα αυτό θα το αποθηκεύσουμε σε μία μεταβλητή
\sa
\begin{verbatim}
message=["E","P","I","T","H","E","S","H"," ","A",
"Y","R","I","O"," ","T","O"," ","P","R","W","I"]
\end{verbatim}
\sg
Εσείς θα πρέπει να βρείτε δύο μεγάλους πρώτους $p,q$
(H συνάρτηση \textlatin{prime(n)} του \textlatin{pari}, 
η οποία επιστρέφει τον $n$-oστό πρώτο είναι 
χρήσιμη για αυτό τον σκοπό). 
Στην συνέχεια να  υπολογίσετε το δημόσιο και το ιδιωτικό κλειδί.
Τέλος να φτιάξετε μια επαναληπτική διαδικασία 
που να διαβάζει ένα ένα  τα γράμματα που 
έχουν αποθηκευτεί στην λίστα \textlatin{message} 
να τα μετατρέπετε σε αριθμούς κάνοντας χρήση της
υπορουτίνας \textlatin{lettertonumber}, και να 
κρυπτογραφήσετε το μήνυμα αποθηκεύοντας το σε μία λίστα
με όνομα \textlatin{cmessage}. 

Επίσης να υλοποιήσετε την αντίστροφη πορεία 
η οποία θα αποκρυπτογραφεί το μήνυμα διαβάζοντας τα 
στοιχεία της λίστας \textlatin{cmessage} 
θα αποκρυπτογραφεί κάθε αριθμό  και θα επιστρέφει 
το αντίστοιχο γράμμα που αντιστοιχεί σε αυτό τον 
αριθμό. 


Την εργασία μπορείτε να την δουλέψετε σε τριάδες, 
και η ημερομηνία παράδοσης θα είναι η 15/12/2002. 




\end{document}
