%% Omia määrityksiä:

\newcommand{\R}{{\mathbb R}}

\def\A{{\it Alice}}
\def\B{{\it Bob}}
\def\E{{\it Eve}}
\def\SYT{{\sc SYT}}
\def\MIT{{\sc mit}}
\def\maple{{\sc Maple}}
\def\Maple{{\sc Maple}}
\def\m{{\sc Maple}}
\def\maplea{{\sc Maple}a}
\def\matl{{\sc Matlab}}
\def\matlab{{\sc Matlab}}
\def\Matlab{{\sc Matlab}}
\def\mlb{{\sc Matlab}}
\def\mma{{\sc Mathematica}}
\def\oct{{\sc Octave}}
\def\octave{{\sc Octave}}
\def\scilab{{\sc Scilab}}
\def\emacs{{\sc Emacs}}
\def\notepad{{\sc Notepad}}
\def\wordpad {{\sc Wordpad}}
\def\RSA {{\sc rsa}}
\def\rsa {{\sc rsa}}
\def\syt {\text{syt}}
\def\esm {\textbf{Esim:}}
\def\Mod{\text{mod}}
\def\bv{\begin{verbatim}}
\def\ev{\end{verbatim}}
 
\renewcommand{\proofname}{Tod}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\newtheorem{lause}{Lause}
\newtheorem{seur}[lause]{Seuraus}
\newtheorem{lemma}[lause]{Lemma}
\newtheorem{algo}[lause]{Algoritmi}

\newtheorem{maarit}{M\"a\"aritelm\"a}


\newtheorem{esim}{Esimerkki} 
\newtheorem{huom}{Huomautus}
\newtheorem{teht}{Teht\"av\"a}

\includegraphics*{nauhakone.eps}
\artikkeli{Lukuteoriaa ja salakirjoitusta, osa 2}

\kirjoittanut{\textbf{\emph{Heikki Apiola}}\\
Matematiikan laitos, Teknillinen korkeakoulu}
 
\vspace{0.2cm}

%Hyperlinkkejä voi yksinkertaisesti tehdä komennolla \url{www.abc.de}
%Pitkän url:n voi jakaa kahdelle riville esim. näin:
%\href{www.abc.de/fgh/ijk}{\texttt{www.abc.de/}}
%\linebreak
%\href{www.abc.de/fgh/ijk}{\texttt{fgh/ijk/}}


 
\begin{multicols}{2}

\date{\today}

\subsection*{Virittelyksi}

Kirjoitus on jatkoa numerossa $3/2007$ olleelle esiosalle 
%\verb_solmu.math.helsinki.fi/2007/3/apiola.pdf_,
%\url{solmu.math.helsinki.fi/2007/3/apiola.pdf},
\href{http://solmu.math.helsinki.fi/2007/3/apiola.pdf}
{\texttt{(solmu.math.helsinki.fi/2007/3/apiola.pdf)}},
jossa esitellään 
lukuteoreettisia perustyökaluja tämän varsinaisesti salakirjoitukseen pureutuvan osan 2 tarpeisiin. Viittaan ykkösosaan roomalaisella I:llä.\\
Käytän myös joissakin kohdissa vektori- ja matriisitermejä. \emph{Vektori} tarkoittaa
yksinkertaisesti lukujonoa, lukujen järjestettyä listaa. Matriisi on lukutaulukko, jossa on samanpituisia vektoreita allekkain. Voit palauttaa vektorin 
aiempiin vektorimielikuviisi vaikkapa Solmun numerossa 1/2007 olleen 
kirjoituksen \href{http://solmu.math.helsinki.fi/2007/1/apiola.pdf}
{\texttt{(solmu.math.helsinki.fi/2007/1/apiola.pdf)}} alkua silmäilemällä.




%\verb_solmu.math.helsinki.fi/2007/1/apiola.pdf_.

\subsection*{Kryptologia - salaustiede}


Tiedon salaamisen/turvaamisen tarvetta on esiintynyt ihmiskunnan historiassa 
vuosituhansien ajan. 
Vanhimmat löydökset ovat n. $4500$ vuoden takaa Egyptin vanhasta kuningaskunnasta.


%The earliest known use of cryptography is found in non-standard hieroglyphs 
%carved into monuments from Egypt's Old Kingdom (ca 4500+ years ago)
%    historia.txt

Nimitykset \emph{kryptologia} ja \emph{kryptografia} on johdettu kreikankielen sanasta
\emph{krypt\'os}, salattu, salainen. %%%   \'o  \`o 
%\emph{gr\'afo}, kirjoitus ja \emph{legein}, lukeminen.
\textit{Kryptologia} näyttää vakiintuneen yleistermiksi, joka 
sisältää osinaan \emph{kryptografian} eli salaamisteknisten menetelmien
suunnittelutieteen ja \emph{kryptoanalyysin}, jonka piiriin kuuluvat 
menetelmien luotettavuuden analysoiminen, heikkouksien paljastaminen, 
salakoodien murtaminen jne. Niin sankarit, konnat kuin viileän objektiiviset 
menetelmien tutkijat ja testaajat työskentelevät 
\emph{kryptoanalyytikon} velvoittavan nimikkeen alla.

%Tämä käsittää menetelmien vahvuuksien
%ja heikkouksien analyysin ja testauksen. Analyytikot siis yrittävät työkseen 
%murtaa salakoodeja, toisaalta erilaiset vakoojat tai tietojärjestelmiin 
%tunkeutujat tekevät samaa työtä samoilla välineillä,
%ja varmaan mielellään kutsuvat itseään koodinmurtajan sijasta 
%kryptoanalyytikoiksi.

Lähihistorian dramaattisimpiin tapahtumiin kuuluvat liittoutuneiden 
onnistuneet saksalaisten  
\emph{Enigma}-salakirjoituskoneen sanomien murtamiset (kts. [Wiki]). 
%\verb+ http://en.wikipedia.org/wiki/Enigma_machine+
Tämä pohjautui puolalaisen matemaatikon Marian Rejewskin vuonna $1932$ 
tekemiin keksintöihin. Hän onnistui algebrallista tekniikkaa käyttäen 
pääsemään Enigma-salauksen jäljille. Hänen ryhmänsä luovutti tuloksensa  
vuonna $1939$
ranskalaisille ja englantilaisille kryptoanalyytikoille. 
Brittien Saksan merivoimiin kohdistuvaa kryptoanalyyttista toimintaa johti
matemaatikko ja teoreettisen tietojenkäsittelytieteen isä, \emph{Alan Turing}, jonka ryhmä onnistui joulukuussa $1940$ murtamaan saksalaisten Enigma-koodin.
Joissakin lähteissä esiintyy arvioita, joiden mukaan pelkästään tämän 
onnistumisen ansiosta toinen maailmansota lyheni useilla vuosilla. 

Pieni englantilainen paikkakunta, jonne sodanaikainen kryptoanalyyttinen toiminta keskittyi, on nimeltään \emph{Bletchley Park}.
Siellä toimii nykyisin museo: 
\href{http://www.bletchleypark.org.uk/}
{\texttt{www.bletchleypark.org.uk/}}.
Sattumoisin \emph{Turingin} elämästä kerrotaan musiikin keinoin 
Ooppera Skaalan esityksissä
maaliskuusta 2008 alkaen.
%\href{http://www.oopperaskaala.fi/}{\texttt{www.oopperaskaala.fi/}}.

Kryptologian historia tarjoaa monta muutakin jännitysseikkailua. Niihin liittyviä 
lukuelämyksiä voi etsiä ehkä parhaiten alan klassikosta [CodeB].
Hiiren napsauttamisen päässä olevaa historiatietoa on tutussa lähteessä [Wiki].
%\verb=http://en.wikipedia.org/wiki/=\\
%\verb=History_of_cryptography=\\
%\verb=#World_War_II_cryptography= (tässä erit. 2. maailmansotaa).\\



Toisen maailmansodan jälkeisiin aikoihin saakka salakirjoitusmenetelmät 
perustuivat viestin 
kirjaimien jonkinlaiseen uudelleen järjestämiseen tai sekoittamiseen.
Tietotekniikan kehittymisen myötä mekaaniset laitteet voitiin korvata 
tietokoneohjelmilla.

Alan vallankumouksellinen käännekohta ajoittuu $1970-$luvun lopulle. 
Vuonna 1976 Stanfordin yliopiston tutkijat \emph{Withfield Diffie} ja \emph{Martin Hellman} esittivät julkaisussaan [DH] ns. \emph{julkisen avaimen menetelmän}.
\\
Ensimmäisen konkreettisen esimerkin toimivasta julkisen avaimen salausjärjestelmästä
esittivät \MIT:n tutkijat 
\emph{R. Rivest, A. Shamir, L. Adelmann} [RSA]. Heidän sukunimiensä 
alkukirjainten mukaan sai nimensä \RSA-salausmenetelmä. 

Kannattaa myös mainita, 
että alalla
on suomalaisia, kansainvälisesti arvostettuja tutkijoita, kuten akateemikko, 
emeritusprofessori
\emph{Arto Salomaa} tutkimusryhmineen ja professori \emph{Kaisa Nyberg}, 
jonka kirjoitus
[KN] on kattava, monipuolinen ja ajantasainen katsaus kryptologiaan. %Kirjoituksessani esiintyy joitakin kutakuinkin suoria lainauksia tästä.
%Kiinnostavaa on todeta, että kirjoitus [Salomaa] kuvaa 
%yleistajuisesti 
%\RSA-menetelmän ja visioi hyvin osuvasti sen tulevaisuuden merkitystä 
%ja mahdollisuuksia jo niin varhain kuin vuonna $1981$. 
\emph{Salomaan} julkaisut ja monografiat, joista viitteenä [AS], ovat 
runsaasti referoituja, alan kansainvälistä huippua edustavia
klassikoita.

$1900$-luvun puolestavälistä lähtien salausmenetelmät ovat alkaneet käyttää 
enenevässä määrin matematiikkaa, erityisesti 
abstraktia algebraa ja lukuteoriaa, kombinatoriikkaa, todennäköisyyslaskentaa ja tilastotiedettä,
 algoritmien vaativuusanalyysiä, jne.

Tietokoneiden prosessoritehon jatkuva kasvaminen antaa "ilmaiseksi"\/  
kryptoanalyytikoille raakaan voimaan perustuvia työkaluja salakoodien murtamiseen. Tämä pitää kryptografia-joukot vireinä ja pakottaa suunnittelemaan entistä 
nerokkaampia ja mielikuvituksellisempia menetelmiä. Kvanttitietokonelaskennan 
mahdollisuuksiin on jo alettu varautua, kts. [Wiki] ja \emph{Mikko Möttönen}:
Kvantti-informaatio -- tämän vuosisadan vallankumous !?, Arkhimedes 1/2008.

%Perustutkimukselle 
%tyypilliseen tapaan vielä ei voida sanoa, tuleeko tästä joskus todellisuutta vai ei.


%, ja tutkimustyötä tehdään 
%kryptograafisten ongelmien ja kvanttifysiikan välisen vuorovaikutuksen alalla 
%(kts. [Wiki]).


%\emph{Kaisa Nybergin} kirjoituksessa [KN] mainitaan, että yksityiskohtaiset


%Kryptologian historian eräs klassikko on [CodeB]. 



%** Joku sana Salomaan Arkhimedes-kirjoitukseta **


%Kattava ja monipuolinen suomenkielinen katsaus koko alan nykytilaan on [KN. 

Salaustieteen ja -tekniikan käytön painopiste on siirtynyt puolustusvoimiin 
ja tiedusteluun liittyvästä käytöstä selkeästi jokaisen kansalaisen arkipäivään
kuuluvaksi asiaksi. 
%Toki tiedustelukäytön tarpeet ovat nekin edelleen kasvaneet.
Kaikki luottamuksellisten tietojen välittäminen Internetissä, sähköposti,
sähköinen kaupankäynti, pankkitoiminta, tietojärjestelmien salasanat, 
matkapuhelinliikenne, sähköinen allekirjoitus, äänestys,
sirukortit  
%(joka nykyään näkyy olevan keskustelun kohteena) 
jne. ovat täysin salaamistekniikasta riippuvaisia.


%Lukuteoria yhdessä kehittyvän tietotekniikan kanssa on luonut mahdollisuudet 
%aivan uudenlaisiin salausmenetelmiin. Teoreettisen tietojenkäsittelytieteen 
%kehittämä
%algoritmien vaativuusanalyysi on eräs merkittävä uusi alue,
%jota tarvitaan lukuteorian lisäksi. Myös
%todennäköisyyslaskennan ja tilastotieteen menetelmillä on tärkeä merkitys, ja 
%kuka tietää millä muulla tulevaisuudessa.

%Kyse ei siis ole pelkästään tietokoneiden prosessoritehojen kasvamisesta. Voidaan tavallaan sanoa päinvastoin, että salausmenetelmien kehittäjät joutuvat kaiken
%aikaa parantamaan menetelmiään ja keksimään uusia, koska jatkuva tietokoneresurssien
%kasvaminen tehostaa "ilmaiseksi"\/ kryptoanalyytikoiden työkaluja. 



Kirjoitukseni tarkoituksena ei ole antaa kattavaa katsausta alaan muuten kuin tarjoilemalla kiinnostuneille lisäviitteitä eri suuntiin. Varsinainen päämäärä on avata   
alkeista lähtien yksityiskohtainen matemaattisten päättelyiden ketju näyttääkseni,
miten \RSA-menetelmä toimii ja valaista sitä 
esimerkein. Tätä varten joudun vielä jonkinverran täydentämään kirjoituksen 
osassa 1 kehiteltyä lukuteorian välineistöä. 
%joitakin lukuteorian välineitä 
%työkalupakkiimme,

%Itse salakirjoitusosuuden aloitan esittelemällä johdatukseksi joitakin 
%yksinkertaisia klassisia salausmenetelmiä. 

%Miksi juuri minä kirjoitan, vaikka en ole alan (edes lukuteorian) tutkija enk harrastaja?
%Solmulle tuli ehdotus \RSA-menetelmän esittelystä joskus viime kesän kynnyksellä 
%\emph{Markku Halmetojalta},joka on yhtenä kirjoittajana lukion lukuteoriaa käsittelevässä kirjassa [I. Lukio1]. 
%Kysyimme Solmun toimituksen kesken mm. \emph{professori Kaisa Nybergiltä} ja \emph{akateemikko Arto Salomaalta}
%asiaa, mutta kummallakaan, tutkimusryhmät mukaanlukien ei ymmärrettävistä syistä ollut tähän aikaa.
%Niinpä päätin rohkeasti itse ryhtyä selvittelemään asioita nollatilasta lähtien. Prosessi on ollut
%mielenkiintoinen, siihen on uponnut runsaasti aikaa, kukaties jään itse koukkuun. 
%Toivottavasti mielenkiinto välittyy eteenpäin lukijakuntaan. 

Parhaassa tapauksessa kirjoitus voisi inspiroida
jotakuta matematiikan opettajaa kehittamään aineksia lukion erikoiskurssille 
tai matematiikkakerholle (jos sellaisia jossain on).





%\hrule

%Tuleeko tämä loppuun vai tähän?  ehkä TÄMÄTÄHÄNTÄÄTÄHÄNHÄHHÄHHÄÄ\\
%tai ehkä sittenkin LOPPUUUUUUUN

%Maineikas matemaatikko \emph{G.H. Hardy} kirjoitti kirjassaan 
%\emph{A Mathematician's Apology} vuonna $1940:$
%\begin{quote}
%... both Gauss and lesser mathematicians may be justified in rejoicing that there
%is one science [number theory] at any rate, whose very remoteness from ordinary
%human activities should keep it gentle and clean. 
%\end{quote}


%Vaan kuinkas kävikään!


%\hrule





 












\subsubsection*{Kertaustietoisku mod-laskennasta}


Modulaariaritmetiikka on keskeisessä osassa, joten kerrataan vielä:

%$a \equiv b\, \Mod\, n$
$a \equiv b\ \pmod n$
tarkoittaa, että on olemassa kokonaisluku $k$ siten, että $a=b + k\, n.$
Toisin sanoen, $n \mid (a-b)$ eli $a-b$ on jaollinen $n:$llä.\\
Kun puhutaan luvusta $b \pmod n$, tarkoitetaan yleensä pienintä 
ei-negatiivista muotoa $b\pm k\, n$ olevaa lukua, toisin sanoen jakojäännöstä jakolaskussa
$b/n.$ Näin toimivat myös alla olevissa esimerkeissä käytettävät \mlb- ja
 \maple-ohjelmistojen \texttt{mod}- funktiot: \matl:ssa \texttt{mod(b,n)} ja
\maple:ssa \texttt{b mod n}.



%Vektorit ja matriisit

%Lähteitä: John Keegan: Sodan tiedustelu. Ajatus kirjat 2007. 479 s.

%Kts. 
%\begin{verbatim}
%Kryptausmenetelmia.txt
%ideointia.txt
%tkkideointia.txt     
%Chinese.tex
%enigma.txt
%apiolakehittelee.tex
%\end{verbatim}

%http://www.mlb.co.jp/linux/science/genigma/enigma-referat/node6.html#SECTION00061000000000000000
%http://www.mlb.co.jp/linux/science/genigma/enigma-referat/node6.html
%http://en.wikipedia.org/wiki/Enigma_machine#Mathematical_description

%Kuten sanottu,
%viittaan kirjoituksen 1-osaan roomalaisella $I:$llä, lauseiden numerointi
%on muotoa \\ \textbf{Lause $I.5$}, tai pelkästään "SYTlause" , johon tässä 
%viitattaisiin.

%\begin{verbatim}
%Muutama sana Jukka Pihkon jutusta.

%Kertausta:
%- Vektorit ja matriisit.
%- modulaariaritmetiikka
%- Muutama tärkeä käsite: jakoyhtälö, SYTlause,...
%\end{verbatim}


%Then, in 1977, a revolution occured: the theoretical idea of public-key cryptography - proposed by Diffie and Hellman in 1976 (in a nutshell they asked for an encryption method of such a nature that even if one knew how the message had been encrypted, one could not decrypt the intercepted message in a reasonable time: many years) - became a reality within one year, with the work of Rivest, Shamir and Adelman.

%Kiintoisaa on lukea prof. Arto Salomaan artikkeli Arkhimedes-lehdestä vuodelta
%1981.   ...
%Todettakoon, että Arto Salomaa on alan merkittävä kansanvälinen uranuurtaja ja
%hänen kirjansa ... kuuluu alan klassikoihin, jota edelleen referoidaan runsaasti.
%Salomaa kirjoittaa vuonna 1981: "On vaikea sanoa, missä laajuudessa '
%epäsymmetriset kryptosysteemit ovat jo käytössä. Kokeiluluontoista käyttöä
%on ainakin useissa Amerikan yliopistoissa. Toisaalta systeemejä ei toistaiseki
%ole vielä lainaakn kaupallisesti saatavissa, mikä tietenkin ratkaisevasti rajoittaa niiden laaajempaa käyttöä.

%------------------------------

%Prime Number Hide-and-seek : How the RSA cipher works
%The idea of a trapdoor function
%-------


%Jos tunnetaan funktio, voidaanko määrittää helposti käänteisfunktio?
%Teoreettisesti kyllä. If we throw in the tiny constraint that you have to
%finish before the heat-death of the universe, the answer subtly changes.

%1975: W. Diffie, M. Hellman, R. Merkle realized that a trapdoor function
%could be the basis for an entirely new kind of cipher - one
%in which the decoding method could remain secret even when the encoding method
%was public knowledge.

%Diffie-Hellman 1976: The idea of a week trapdoor function, 1977 RSA, MIT 
%technical memo.  


\subsection*{Symmetrisistä sa\-la\-kir\-joi\-tus\-me\-ne\-tel\-mistä}

Monet lukijoista lienevät joskus nuoruudessaan kokeilleet
jotain tapaa välittää viestiä salatussa muodossa sekoittamalla sopivasti
viestin kirjaimia. Kenties yksinkertaisin menetelmä on korvata sanan
kukin kirjain aakkosissa seuraavalla kirjaimella. Tätä menetelmää käytettiin
myös kuuluisassa, vuonna 1968 valmistuneessa elokuvassa 
''2001: A Space Odyssey'' (A.C. Clarke, S. Kubrick), 
jossa vallankaappausta avaruusaluksen 
miehistöltä yrittänyt tietokone oli nimeltään \texttt{HAL 9000}. 
Toki tässä nimessä oli kyse vain pienestä pikantista kuriositeetista, joka aukeni
osalle katsojia.

%''2001: A Space Odyssey,'' Arthur C. Clarke's science fiction classic that was brought to the screen by Mr. Clarke and Stanley Kubrick, the HAL 9000
%Kts. Osmo Pekosen webbiartikkeli!

Vakaviin sotilaallisiin tarkoituksiin menetelmää lienee käyttänyt
ensimmäisenä 
\emph{Julius Caesar}. Hän on tiettävästi
soveltanut kolmen kirjaimen siirtoa eteenpäin viestin salaamiseen ja 
vastaavasti saman määrän siirtoja taaksepäin salakoodin avaamiseen. 
Tämän tyyppisiä menetelmiä, jossa kirjainta siirretään aakkosissa määrätty
määrä, kutsutaankin yleisesti Caesarin menetelmiksi.

\subsubsection*{Esimerkki Caesarin menetelmästä}

Suoritin itse esimerkin \matl-ohjelmaa hyödyntäen, mutta en paneudu ohjelman syntaksiin.
Otan vain joitakin \matl-näytteitä ja sanontoja, jotka ovat itsensä selittäviä.

 
Muodostetaan merkkivektorit \\
\verb_ >> AAKKOSET='ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ '_
\verb_ >> viesti='SAMMONRYÖSTÖ'_

Muutetaan viestin kirjaimet numeeriseksi vektoriksi laskemalla kunkin kirjaimen
sijainti \texttt{AAKKOSET}-vektorissa. Siis esim. $A=0, B=1,\ldots,Z = 26,\ldots $
Saadaan:

\verb_    18 0 12 12 14 13 17 24 28 18 19 28 _

Alkuperäisessä \emph{Caesarin menetelmässä} lisäämme jokaiseen vektorin komponenttiin luvun $3$.
%Laitoin tahallani sanan, jossa on aakkosten loppupään kirjaimia. 
Lienee aika selvää,
että Ö, jota vastaa numero $28$, siirretään syklisesti aakkosten alkupäähän ja siitä 
tulee siis B (koska valitsimme aakkosvektorimme viimeiseksi merkiksi välilyönnin).

Tämä syklinen siirto tarkoittaa, että redusoimme tuloksen modulo $N=30$, koska 
aakkosvektorin pituus on $30$. (Voidaan ajatella aakkosvektori kierretyksi ympyrän muotoon, jonka 
kehällä liikutaan.) Toisin sanoen lasku numeroilla on $(28 + 3)\, (\Mod\, 30) =1 $.

Yleisesti
salausfunktiomme on siis 
$(x+3) \pmod N$, missä $x$ on viestin numeerisen esitysvektorin
komponentti (viestin kirjainmerkkiä vastaava numero), ja $N$ on 
aakkosvektorin pituus. 
\matl-istuntomme jatkuisi näin, kun ajatellaan, että edellä oleva
viestin numeerinen esitysvektori on muuttujassa \texttt{nviesti}.
%\begin{verbatim}

\verb_>> nsalaviesti=mod(nviesti+3,30)_\\
   21 3 15 15 17 16 20 27 1 21 22 1
\verb_>> AAKKOSET(nsalaviesti+1)_\\
\verb_   VDPPRQUÄBVWB       salaviesti kirjaimilla_\\
%\end{verbatim}

\textbf{Salaviestin avaus}

Viestin vastaanottajalla on tieto menetelmästä ja avainluvusta $3$. Sehän voisi yhtä 
hyvin olla jotain muutakin. Viestin avaaminen tapahtuu salausfunktion käänteisfunktiolla, joka on mitä ilmeisimmin\\  $f^{-1}(y) = (y-3)\, \Mod\ \ N.$
\begin{verbatim}
>> avattu=mod(nsalaviesti-3,N)
     18 0 12 12 14 13 17 24 28 18 19 28
>> AAKKOSET(avattu+1)
SAMMONRYÖSTÖ  
\end{verbatim}
Salaviestin avaus tuotti alkuperäisen viestin, joten hyvin kävi.

Niille, joita kiinnostaa \matl-syntaksi mainitsen, että \texttt{AAKKOSET(avattu+1)}-komento tarkoittaa \texttt{AAKKOSET}-merkkivektorin indeksointia numeerisella vektorilla, jonka komponentteihin pitää lisätä $1$, koska \matl:ssa vektorin indeksointi aloitetaan luvusta $1$, kun taas jakojäännöksillä laskenta vaatii indeksin alkamaan $0$:sta.
Sama ilmiö on tietysti lausekkeessa \texttt{AAKKOSET(nsalaviesti+1)}.

Yleisesti menetelmä voitaisiin esittää tähän tapaan: %(vaihdan pieneen $n-$kirjaimeen):
\\
Merkitään $Z_n = \lbrace 0,\ldots,n-1\rbrace.$ Salausfunktio\\ 
$S_e:Z_n \to Z_n; S_e(x)=(x+e)\pmod n$, missä $e$:tä voidaan kutsua 
\emph{salausavaimeksi} ja funktiota $S_e$ salausfunktioksi, joskus itse funktiota  kutsutaan myös 
salausavaimeksi.
\\
Salakoodi saadaan avatuksi salausfunktion $S_e$ käänteisfunktiolla
$S_e^{-1}(y) = (y-e)\pmod  n .$ 

%Tässä tapauksessa siis $f_e^{-1} = f_d,$ missä $d=-e.$



Menetelmä on \emph{symmetrinen} siinä mielessä, että kun salaus(avain)funktio 
tunnetaan, niin salakoodin avaamisen suorittava käänteisfunktio voidaan 
välittömästi määrittää.

%Hienosti ilmaisten voitaisiin puhua \emph{kryptosysteemistä}, jossa menetelmänä on (yleistetty) 
%\emph{Caesarin menetelmä}. Salausavain on luku $e$, salausfunktio on $f_e$.
%Salauksen purkuavain on $d=-e$ ja vastaava funktio on yllä oleva $f_e^{-1}=f_d$.

%Menetelmä on \emph{symmetrinen} siinä mielessä, että kun salausavain tunnetaan,
%niin purkuavain saadaan siitä heti johdetuksi.


%*************** Tämä siirretään ****
%Viittaamme salausavaimeen kirjaimilla $e,E$, englanninkielisen sanan 
%"Encrypt"\/ alkukirjaimen mukaan. Vastaavasti kirjaimet $d,D$ tulevat 
%sanasta "Decrypt", joka siis tarkoittaa salakoodin avaamista, "dekryptausta".
%
%Numeeriseksi koodattua viestiä merkitään usein kirjaimella $m$, "message"\/ ja 
%vastaavasti salakirjoitettua $c$:llä, viitaten sanaan "ciphertext".
%
%***********************************************************************


%Salausavainta merkitään usein symbolilla $K_e$ ja salakoodin purkuavainta 
%$K_d$:llä. $K$ viittaa sanaan "key", $e$ sanaan "encrypt"\/ ja $d$ sanaan 
%"decrypt". On hyödyksi sisäistää kirjaimien $e,E$ ja $d,D$ merkitys. Käytän 
%niitä johdonmukaisesti viittaamaan "kryptaukseen"\/ eli salaukseen ja 
%vastaavasti "dekryptaukseen"\/ eli salakoodin avaamiseen tai purkamiseen.




\subsubsection*{Kehittyneempiä symmetrisiä menetelmiä}

\emph{Caesarin} menetelmä yleisessäkin muodossaan on luonnollisesti hyvin 
haavoittuva.

Erilaisten mahdollisuuksien (salausavaimien) määrää 
voidaan huikeasti lisätä ottamalla salausfunktioksi jokin muu tapa
sekoittaa kirjaimia. Jos otetaan mielivaltainen aakkosten "permutaatio",
eli uusi järjestys, niin kaikkien mahdollisten
salausavainten lukumäärä on $N!$, missä $N$ on edelleen aakkosvektorin pituus.
Yllä olevassa tapauksessa $N=30,$ jolloin saadaan kaikkiaan
$30!$ mahdollisuutta. Kyseessä on luku, jossa on $33$ numeroa, joten raakaan
voimaan perustuva kaikkien eri mahdollisuuksien läpikäyminen ei onnistu.

%Salausfunktio voidaan esittää kaksirivisenä matriisina, jossa $1.$ rivinä
%ovat aakkoset ja toisessa aakkoset halutussa uudessa järjestyksessä.
%Matriisi voidaan esittää merkkimuodossa tai tietysti yhtä hyvin numeroina.
%Käänteisfunktio saadaan yksinkertaisesti vaihtamalla matriisin rivit 
%keskenään.

Huolimatta avainten lähes äärettömästä määrästä, tämäkin menetelmä on monin
tavoin haavoittuvainen. Kun on tiedossa kieli, jolla viestintä tapahtuu,
voidaan kirjainten esiintymäfrekvenssien perusteella päästä oikeista
kirjaimista selville. Esimerkiksi Suomen kielessä kirjain $A$ on yleisin,
joten (pitkässä) salakirjoitetussa viestissä suurimman esiintymäfrekvenssin
omaava kirjain on todennäköisesti $A$. Ja niin edelleen.
Frekvenssianalyysin käytöstä salausavaimen selvittämiseksi on hyviä 
esimerkkejä ja opastettuja harjoitustehtäviä mm. 
kirjassa [Kob] luvussa III.
%Lisäksi avainten lähettäminen ja vaihtaminen on raskas ja riskialtis operaatio.

Frekvenssianalyysin vaikeuttamiseksi viesti voidaan myös koodata jakamalla 
se ensin osiin, lohkoihin, jotka numeroidaan. Jos vaikka käytettäisiin 
$2$:n pituisia lohkoja, niin kunkin komponentin numerot olisivat
välillä $0,\ldots, N^2-1 = 899$,
ja kyseessä olisi 2-kirjaimisten tavujen tunnistaminen. 
Kasvattamalla lohkon kokoa, sanokaamme suuremmaksi kuin $4$, 
frekvenssianalyysiin perustuva tunnistus 
vaikeutuu olennaisesti.


\emph{Caesarin menetelmää} on kehitetty ottamalla mukaan avainsana, joka 
määrää kirjaimien muuntumisen.
% Lyhyesti ilmaistuna avainsana laajennetaan 
%peräkkäin liittämällä niin, että siitä tulee viestin pituinen, koodataan 
%viesti ja laajennettu avainsana numeerisiksi vektoreiksi ja lasketaan 
%vektorit komponenteittain yhteen $\pmod N$. Tällaisia menetelmiä kutsutaan 
%\emph{Vign\`ere}'n menetelmiksi. 
Jos 
otetaan 
avaimeksi satunnainen merkkijono, joka on lähetettävän viestin pituinen,
niin lasketaan yhteen viestivektorin ja avainvektorin numeeriset 
esityksvektorit komponenteittain $\pmod N$.
%numeeriseksi vektoriksi muunnettu viesti ja avainvektori.
Yllättävää kyllä, tämä menetelmä, englanninkieliseltä nimeltään 
"one time pad", on ainoa tunnettu informaatioteorian mielessä 
luotettavaksi todistettu salausmenetelmä.
Käytännössä se on kuitenkin monin tavoin hankala ja epäluotettava,
avain on yhtä pitkä kuin viesti, 
avainvektorit ovat periaatteessa kertakäyttöisiä, ja avainten
vaihto on työläs ja riskialtis operaatio



%Tämän sai karvaasti kokea mm. Japanin laivasto, joka \emph{Pearl Harbourin}
%menestyksen huumassa viivytti avaimien vaihtoa. Hawaiilla olevien amerikkalaisten koodinmurtajien ansiosta japanilaisten laivasto tuli pahankerran yllätetyksi
%... Menetelmä ei ollut juuri tämä, mutta kertomus käy avaintenvaihto-opetuksesta.


%Avain on
%yhtä pitkä kuin viesti, ja avaimia on vaihdettava tiuhaan.
%jonka englanninkielinen nimi on "one time pad"\/.
%Itse asiassa näin saadaan menetelmä
%Kirjaimet (tai niitä vastaavat numerot) lasketaan yhteen merkki merkiltä
%(\Mod\, N).
%Menetelmä on luotettava, mutta käytännössä hankala. Avain on
%Menetelmän keksijänä pidetään ... *** 
%Toisaalta tämänkaltaisia menetelmiä kutsutaan myös \emph{Vigneret'n}
%menetelmiksi. Tällöin käytetään usein lyhyempiä avaimia samaan tapaan 
%kuin yllä, ja viestit ovat siten helpommin murrettavissa.
%** Vigneret-aksentit **


%Alussa mainittu saksalaisten kehittämä Enigma on mekaanis-elektroninen laite, jossa
%eri kiekkojen ja kytkentäjohtojen avulla asetetaan viestin eri osiin sovellettavia
%permutaatioita. Lyhyt matemaattinen kuvaus siitä on viitteessä:\\
%\verb=http://en.wikipedia.org/wiki/=\\
%\verb=Enigma_machine#Mathematical_description=


%\begin{center}
%\includegraphics[width=4cm]{Enigma.ps} \\
%Enigma ...(lähde Wikipedia)
%\end{center}

Vaikka salausmenetelmien "avantgarde"\/ on epäsymmetristen menetelmien 
puolella, symmetrisiä menetelmiä kehitellään myös edelleen.
Kohta esiteltävät epäsymmetriset menetelmät, joihin edellä mainittu  
\RSA\/ kuuluu, ovat pitkien viestien 
käsittelyssä raskaita. Siksi joudutaan usein käyttämään yhdistelmää,
jossa esimerkiksi lähetetään symmetrisen
menetelmän avain salattuna epäsymmetrisellä menetelmällä ja symmetrisellä
salattu (pitkä) viesti.


%\subsection*{Lisää matematiikkaa peliin}



\subsection*{Lukuteorian täydennystä}

Osassa I käsiteltiin kokonaislukujen jaollisuusasiota ja modulaariaritmetiikkaa.
%Eukleideen algoritmia ja Fermat'n pientä lausetta.
Kannattaa kaivaa aktiivimuistiin nuo asiat, ainakin määritelmät ja lauseiden
 johtopäätökset. Tärkeimpiä: Jakoyhtälö (Lause I.1), SYT-lause (I.5), 
Eukleideen algoritmi, Fermat'n pieni lause (Lause I.13).
Perusasioita lukuteoriasta löytyy myös \emph{Jukka Pihkon} Solmun verkkolehteen kirjoittamasta "lukuteorian helmiä"\/-artikkelista [JP].
Tarvitsemme osassa I esitetyn lisäksi vielä lukuteoreettisen 
jälkiruoka-annoksen.

\textbf{Eukleideen algoritmin laajennus}

Palautetaan mieleen lause $I.8$, joka sanoo, että $\syt(a,b)= \syt(b,r),$
kun $a$ esitetään jakoyhtälön (lause $I.1$) ilmaisemassa muodossa:
$a=b\, q + r,\ \ 0 \leq r < b.$
Tämä edustaa askelta, joka riittävän monta kertaa toistettuna johtaa
$\syt(a,b):$n arvoon. Menettelyä kutsutaan \emph{Eukleideen 
algoritmiksi}. 

Edelleen muistellaan erityisellä lämmöllä 
"SYTlausetta"\/$I.5$. Sehän paljastaa, että $\syt(a,b):$lle saadaan 
esitys muodossa
$x\,a + y\,b,$ missä $x$ ja $y$ ovat kokonaislukukertoimia. 
%(Ne, jotka ovat harrastaneet lineaarialgebraa, mieltävät esityksen
% mielellään $a$:n ja $b$:n kokonaislukukertoimisena 
%\emph{lineaarikombinaationa}.)

Tähän mennessä olemme osanneet nautiskella pelkästään siitä tiedosta,
että tuollaiset luvut $x$ ja $y$ ovat olemassa, menettelyä niiden 
määrittämiseksi emme ole esittäneet. Nyt on sen aika! 


Katsotaanpa esimerkin valossa:

\begin{esim}
Määrättävä $\syt(171,30).$ \\
$171=5\cdot 30 + 21.$ \\ 
\emph{Euklalgo}:  $\syt(171,30)=\syt(30,21).$\\
Jakoyhtälö: $30 = 1\cdot 21 + 9.$ \\
\emph{Euklalgo}: $\syt(30,21) = \syt(21,9).$ \\ 
Jakoyhtälö: $21 = 2 \cdot 9 + 3.$\\
\emph{Euklalgo}: $\syt(21,9)= \syt(9,3)=3$. \\
(Seuraava jakoyhtälö: $9=3\cdot 3 + 0$ johtaisi jakojäännökseen $r=0$,
joka on algoritmin lopetusehto.)\\
Siis $\syt(171,30)= 3.$
\end{esim}
Tähän saakka kerrattiin vanhaa.
Johtaaksemme tavoitellun esityksen, käytämme luvuille kirjainsymoleja asian
selkeyttämiseksi.
Merkitään $a=171, b=30$, ja syntyvät jakojäännökset olkoot 
$r_1, r_2, r_3,\ldots .$
Tässä $r_1=21, r_2=9, r_3=3, r_4=0.$ \\
Päämääränä on siis lausua viimeinen nollasta poikkeava jakojäännös (tässä $r_3)$ muodossa $r_3 = x\, a + y\,b. $
Kirjoitetaan yllä olevat jakoyhtälöt näitä merkintöjä käyttäen:
$$
\begin{cases}
a = 5 \cdot b + r_1 \\
b =  r_1 + r_2 \\
r_1 = 2\cdot r_2 + r_3 . \\
\end{cases}
$$
Kun tämä puretaan alhaalta ylöspäin, saadaan haluttu esitys. Tarkemmin sanottuna:
 
%\begin{enumerate}
%\item
1. Ratkaistaan alimmasta yhtälöstä $r_3\ \ $ $r_1$:n ja $r_2$:n avulla.\\
%\item
2. Sijoitetaan tähän $r_3$:n lausekkeeseen $r_2$ ratkaistuna toiseksi alimmaisesta
yhtälöstä $r_1$:n ja $b$:n avulla.\\
%\item
3. Sijoitetaan näin saatuun $r_3$:n lausekkeeseen $r_1$ yhtälöstä $1$ lausuttuna $a$:n ja $b$:n avulla. 
%\end{enumerate}
%Tällöinhän $r_3 = \syt(a,b)$ tulee lausutuksi halutussa muodossa.
Tämä strategia konkretisoituu esimerkkimme tilanteessa näin:

%\begin{enumerate}
%\item
$r_3  = r_1 - 2\cdot r_2 .$\\
%\item
$r_2 = b - r_1$ sij. (3):een $ \implies 
r_3=r_1 - 2\cdot b + 2\cdot r_1 = 3\cdot \underbrace{r_1}_{a - 5\cdot b} - 2\cdot b $   

Sieventämällä:
$\ \ \syt(a,b)= r_3= 3\cdot a - 17 \cdot b. $


%\end{enumerate}

%\end{esim}



Menettely on nimeltään
\emph{Laajennettu Eukleideen algoritmi}.
\\
Huomautan, että kirjoituksessa [JP] on 
toinen vastaavanlainen esimerkki laskettuna auki.
Samaisessa
kirjoituksessa [JP] ss. 6--7 esiintyy myös hauska konstruktiivinen 
todistus \SYT-lauseelle. Todistus etenee
 \emph{Eukleideen algoritmin tahdissa}, toisin kuin se, jonka esitin osassa I.
Vastaavanlaisia esimerkkejä on myös kirjoissa [I. Lukio1]
 ja [I. Lukio2] aihepiireissä \emph{Eukleideen algoritmi}
 ja  \emph{Diophantoksen yhtälöt}.

\textbf{Ohjelma laajennettuun Eukleideen algoritmiin}.

Nämä esimerkit huolella läpikäytyään lukija varmasti vakuuttuu siitä, että
tällainen tehtävä voidaan aina ratkaista, ja osaa pyydettäessä  
ratkaisun suorittaa. 
En muotoile lausetta matemaattiseksi algoritmiksi tai lauseeksi,
vaan kirjoitan sen suoraan tietokoneohjelmaksi, jollaisena se tietysti 
käytännön sovelluksissa esiintyy.

Kirjoituksen osassa I esitin rekursiivisen ohjelman Eukleideen algoritmille.
Siitä sopivasti laajentamalla saadaan ällistyttävän yksinkertainen
koodi laajennetulle. Koodi noudattaa \maple-kielen syntaksia, mutta 
voidaan muokata helposti mille tahansa rekursion sallivalle kielelle.
\begin{verbatim}
EEukleides:=proc(a,b) 
if b=0 then [a,1,0] 
else L:=EEukleides(b,mod(a,b)); 
     d:=L[1]; x:=L[2]; y:=L[3]; 
     L:=[d,y,x - iquo(a,b)*y] #iquo:osamäärä 
end if 
end proc
\end{verbatim}
Tämä rekursiivinen (itseään kutsuva) ohjelma laskee siis luvun $d=\syt(a,b)$
ja kertoimet $x$ ja $y$ siten, että $d=a\,x + b\,y$  (vrt. SYTlause).\\
Edellä oleva esimerkki laskettaisiin näin:
%\begin{verbatim}
\\
\verb_ > tulos := EEukleides(171, 30); _\\
\verb_ > d := tulos[1]: x := tulos[2]: y := tulos[3]:_\\
\verb_ > d,x,y;_\\
\verb_        3, 3, -17_\\
%\end{verbatim}
Saatiin kuin saatiinkin sama kuin käsin laskemalla!
\\
Algoritmi on kirjoitettu sovittamalla [I. Algo]-kirjassa annettu 
"pseudokielinen"\/ ohjelma \maple-syntaksin mukaiseksi. 
%Laajennetun \emph{Eukleideen algoritmin} yleinen todistus
%jää sekä tästä poistamassani, että \emph{Pihkon} kirjoituksessa esimerkin varaan.
Elegantti tapa laajennetun \emph{Eukleideen algoritmin} yleiselle 
matemaattiselle todistukselle on yllä olevan 
ohjelman oikeaksi todistaminen, joka onkin yllättävän lyhyt ja ytimekäs
([I. Algo] Ch. 33. s. 812.

%*** Kuinka monta kertaa sanottu****

Kuten sanottu, käytän esimerkeissäni symbolilaskentaohjelmaa \maple. 
%Se sopii kryptologiatarkoituksiin, koska siinä voidaan
%laskea periaatteessa mielivaltaisen suurilla kokonaisluvuilla.
Esimerkkien lukeminen ei edellytä lainkaan ohjelman tuntemista. Selitän tarvitsemani
komennot, joita on vain muutama. Ohjelman ottaminen mukaan on sikäli mielekästä,
että voidaan esittää asiat ihan oikean kokoisilla luvuilla. Se myös antaa konkretiaa
teoreettisesti kuvailtaville algoritmeille, ja osoittaa, että hyvä symbolilaskentaohjelma on hyödyllinen kryptologiatyökalu.% etenkin opetuskäytössä.
% vaikkei toki tehokkuudessa pärjää 
%huippuunsa viilatulle käännettävälle ohjelmalle. Käyttömukavuudessa sensijaan se on 
%ylivertainen.
 Sekä \maple:n että \mma:n käyttäjäryhmissä on suuri määrä kryptologian 
esimerkkityöarkkeja.
(\href{http://www.maplesoft.com/applications/}
{\texttt{http://www.maplesoft.com/applications/}} 
$\to$ \texttt{mathematics} $\to$ \texttt{Cryptography} ($23$ kpl.) ja \href{http://www.wolfram.com/}
{\texttt{http://www.wolfram.com/}})
 \\
Toisaalta kannattaa mainita vapaasti saatava ohjelma \emph{Maxima},
jolla kiinnostuneet voivat kokeilla vastaavien asioiden toteuttamista, ellei 
\maple- tai \mma-ohjelma ole käytettävissä. Viimemainituista painotan 
enemmän edellistä siksi, että se on itselleni tutumpi.
%Palaan vielä kirjoituksen lopussa ohjelmistoasioihin.


Huomautan vielä, että \maple:ssa on si\-sään\-ra\-ken\-net\-tu\-na laajennettu 
\emph{Eukleideen algoritmi} nimellä \texttt{igcdex}. 
Nimi koostuu osista: \texttt{i} - integer, \texttt{gcd} = 
\emph{greatest common divisor} = 
\texttt{syt} ja \texttt{ex} - \emph{extended}
Komento \texttt{d:=igcdex(a,b,'x','y')} 
palauttaa tuloksen \texttt{d=syt(a,b)} ja lisäksi muuttujissa 
$x$ ja $y$ kertoimet, joilla $d=a\,x + b\,y.$
\\
Edellinen esimerkki laskettaisiin näin:\\
%\begin{verbatim}
\verb_> d:=igcdex(171,30,'x','y'):_\\
\verb_> d,x,y;_\\
\verb_            3, 3, -17_\\
%\end{verbatim}
%*** sanottu 2 kertaa ***
Jatkossa käytämme valmista \texttt{igcdex}-funktiota esimerkeissämme edellä
esitetyn \texttt{EEukleides}-funktion sijasta.



%Edellä olleet \matl-esimerkit puolustanevat paikkaansa mm. siksi, että
%\matl:n vahva ja kätevä vektori-matriisikieli mahdollistaa helppoja tapoja
% tehdä tarvittavia muunnoksia, kuten merkkivektorin muuntamisen numeeriseksi 
%ja kääntäen. Toki nämä sujuvat \maple:lla tai \mma:lla myös. Näiden suhteen
%otan käyttöön valmiit, \Maple:n käyttäjäkunnan arkistoista löytyneet funktiot. 
%*** Tästä siirrä taulukko ****

%Mainitsen nyt joitakin nimityskäytäntöjä ja komentoja,
%joita esimerkeissämme tarvitaan.
%\\
%Alkukirjain $i$ viittaa sanaan ``integer'', kokonaisluku.

%\begin{tabular}{ll}
%\texttt{ifactor} &   Tekijöihin jako\\
%\texttt{igcd(a,b)} & gcd = syt\\
%\texttt{igcdex(a,b,'x','y')} &  gcd extended = Laajennettu \\ 
%            &   Eukleideen algoritmi\\
%\texttt{a mod b} & Jakojäännös laskussa $a/b$
%\end{tabular}

%Äsken esitelty \texttt{EEukleides} tekee saman (varmaankin vähemmän
%optimoidusti) kuin \maple:en kuuluva perusfunktio \texttt{igcdex}.


\textbf{Yhtälön $a\,x \equiv 1  \pmod n$ ratkaiseminen}

Kyseessähän on mahdollisimman yksinkertainen ns. \emph{Diophantoksen yhtälö},
jota käsiteltiin osassa I.
Lauseen I.12 mukaan yhtälöllä on aina yksikäsitteinen ratkaisu $\pmod n$,
mikäli $\syt(a,n)=1$. Ratkaisu saadaan \emph{laajennetulla Eukleideen 
algoritmilla} laskemalla luvut $x$ ja  $y$
 siten, että $a\,x + n\,y = 1.$ Kiinnostava on vain luku $x$. Kun se tunnetaan,
niin \\ $a\,x = 1 - n\,y \equiv \, 1 \pmod n.$

Yllä olevalla \maple-funktiolla ratkaisu saadaan siis näin:\\
\verb_ > igcdex(a,n,'x','y'):_\\
Kuten sanottu, olemme kiinnostuneita vain $x$:stä, $d$:n tiedämme $1$:ksi, $y$ voidaan heittää
romukoppaan.
Jos halutaan minimaalinen $x$, ts. redusoida $\pmod n,$ niin ei muuta kuin
\verb_x:=x mod n :_
%Ratkaisu $x$ on $a$:n \emph{käänteisalkio} $\pmod n$, ja sille käytetään 
%merkintää $x = a^{-1}\,\pmod n.$

%\end{enumerate}

%\end{esim}


\subsubsection*{Kiinalainen jäännöslause}


Aiheeseen liittyy monta tarinaa erityisesti kiinalaisen (ja kreikkalaisen) 
matematiikan historiasta.
%Sellainenkin väite esiintyy, että kreikkalaiset olisivat keksineet sen
%ennen kiinalaisia. No, mene tiedä.
Löytöjä voi tehdä \emph{Googlella} hakusanalla \emph{Chinese remainder theorem}. 
%Buddalaismunkki I-Hsing lienee tuntenut. Esiintyy varmuudella Ch'in Chiu-shaon
%Shu-shu Chiuchang (Mathematical Treatise in 9 sections) v. 1247.
Eräs tarinoista on [I. Algo]-kirjassa:\\
\textit{Noin vuonna $100$ ajanlaskumme alkuhetken jälkeen
 kiinalainen matemaatikko \emph{Sun-Tsu} ratkaisi seuraavan ongelman:\\
Määritä kokonaisluvut $x$, jotka antavat jakojäännökset $2,3,2$ jaettaessa
luvuilla $3,5,7$. Ratkaisuiksi hän sai luvut $x=23 + k\cdot 105.$
}

Huomattakoon, että jakajat $n_1=3, n_2=5, n_3=7$ ovat pareittain yhteistekijättömät
ja $3\cdot 5\cdot 7 = 105$, mutta miksi näin, ja  mistä tulee $23$ ? 
Nykykielellä siis ratkaisu: $x\equiv 23 \pmod n,$
missä $n=n_1\cdot n_2\cdot n_3$.

Miten hän ratkaisuunsa päätyi, ja osasiko yleistää?
Nykylukijalla on helppoa, sovelletaan kiinalaista jäännöslausetta,
jota 
tässä ei kuitenkaan esitetä.
Mainittakoon kuitenkin, että lauseen muotoili ja todisti yleisessa muodossaan -- kukas muu 
kuin \emph{Euler} v. $1734$.

%Around A.D. 100 the Chinese mathematician solved the problem
%of finding those integers x that leave remainders 2,3,2 when divided
%by 3,5,7 respectively. One sol is x=23, all sols are of the form 
%23 + k 105.   (3*5*7=105)

\RSA-algoritmin todistuksessa tarvittava kiinalaisen jäännöslauseen seuraus
on 
siinä määrin erikoistapaus itse lauseesta, että sen suora todistus on miltei 
itsestäänselvyys. Kiinalaista jännöslausetta voidaan kyllä käyttää mm. \RSA-menetelmän 
tehokkaampaan toteutukseen ja myös \rsa-menetelmän 
murtamisyrityksiin, joten sen esittäminen olisi hyvinkin perusteltua tässä yhteydessä. 
Katson kuitenkin kirjoitukselleni olevan hyväksi keventää 
työkalupakkia, kun se on mahdollista.

%\RSA-todistusta tutkiessani huomasin, että
%menetelmän perustelussa ei tarkkaan ottaen tarvita 
%kiinalaista 
%jäännöslausetta koko voimassaan, vaikka kirjallisuudessa usein asia
%näin esitetään [Co-Lei-Riv].
%Kirjoitukseni minimalistisiin tarkoitusperiin sopii hyvin, että
%jätetään kaikki ylimääräinen painolasti pois, olipa se sinänsä kuinka 
%kiintoisaa tahansa. 

%Siitä syystä nimeän tarvitsemani yksinkertaistetun 
%muunnelman "kiinalaiseksi selviöksi".

%Kiinalaista jännöslausetta voidaan kyllä käyttää \RSA-menetelmän 
%tehokkaampaan implementointiin. (Jossain lähteessä mainittiin n.
%nelinkertainen nopeutus salakoodin avaamisessa.)
%Viitteessä Kts. DI management ... mainitaan n. nelinkertainen tehostuminen
%salakoodin avauksessa.

%*** Jossain sopivassa: e-encrypt, d-decrypt  ****

Kutsun tarvitsemaamme seurausta 
"kiinalaiseksi selviöksi".

\begin{lause}[Kiinalainen selviö]\label{kiinalainen}

Olkoon\\ 
$n=n_1\,n_2\,\cdots n_k,$ missä $\syt(n_i,n_j)=1,$ kun $i\neq j.$\\
Olkoon $a$ mielivaltainen kokonaisluku. Nyt
\\
$x \equiv a \pmod n \iff x \equiv a \pmod {n_i}, i=1,\ldots,k.$
\end{lause}


\begin{proof}
(1) Olkoon $x \equiv a \pmod n$. 
Jatko jääköön lukijalle harjoitustehtäväksi.

% \\
%$x-a = j\,n = j\,n_1\,n_2,\cdots n_k$
%jollain $j$, joten jokainen $n_i$ on tekijänä $(x-a):$ssa ja siten 
%$x \equiv a (\Mod\, n_i), i=1,\ldots,k.$

(2) Olkoon $x \equiv a (\Mod\, n_i), i=1,\ldots,k.$
Tällöin jokainen $n_i$ on tekijänä $(x-a):$ssa. Koska 
$\syt(n_i,n_j)=1,$ kun $i\neq j$,
niin myös tulo $n=n_1\,n_2\cdots n_k$ on tekijänä $(x-a)$:ssa, eli
$x \equiv a (\Mod\, n)$. Tämä viimeinen päätelmä jätetään taas lukijalle
harjoitustehtäväksi (miltei valmiiksi ohjeistettuna).
\end{proof}

\begin{teht} 
Olkoon $\syt(n_1,n_2)=1$ ja olkoon $n_1 \mid a$ ja $n_2 \mid a$.
Osoita, että $n_1\,n_2 \mid a.$
\end{teht}
\textbf{Vihje} Taas kerran päästään liikkeelle SYTlauseen I.5 avulla:
$1 = n_1\,x + n_2\,y.$ Kerro puolittain $a$:lla, niin alat olla perillä.

On selvää, että tämä yleistyy useampaan tekijään (formaalisti induktiolla, jota esitellään
mm.  kirjoituksessa [JP]) 
. Toisaalta tarvitsemme "kiinalaista selviötä"\, vain tapauksessa 
$n=n_1\,n_2.$

\textbf{Modulaaripotenssilaskenta}

Tässä on kaksi näkökulmaa, 1) laskentakaava "potenssi potenssiin"\/ ja 
2) tehokas potenssiinkorotusmenetelmä.

\textbf{1. Potenssi potenssiin}. Silloinhan eksponentit kerrotaan. Päteekö sääntö myös $\pmod$-laskennassa? Mitä on siis
$(a^k \Mod\, n)^j $ ? % No katsotaan:
\\
 $a^k \Mod\, n = a^k + i\,n$ jollain $i$.
\\
Siis $(a^k \Mod\, n)^j = (a^k + i\,n)^j = a^{k\,j} + $ termejä, joissa 
jokaisessa on $i\,n$ tekijänä. (Joko binomikaavalla tai suoraan tulosta 
$(a^k + i\,n)(a^k + i\,n)\cdots (a^k + i\,n)$, jossa kaikkiin muihin 
termeihin paitsi siihen, jossa jokaisesta binomista otetaan ensimmäinen, tulee tekijäksi
$(i\,n)$:n potenssi.) Eli saadaan muotoa $a^{k\,j} + K\,n$ oleva lauseke, missä
$K$ on jokin kokonaisluku. Siis    
$$(a^k \Mod\, n)^j \equiv a^{k\,j}\pmod n,$$

ja potenssi potenssiin sääntö toimii kauneimmalla mahdollisella tavalla.

\textbf{Modulaarinen potenssiinkorotus}

Usein näissä yhteyksissä tulee vastaan tehtävä \\ $a^b \pmod n,$ missä esiintyvät luvut saattavat olla hyvin suuria. Jos vaikka $a$ on luokkaa $10^4$ ja $b$ luokkaa
$10^5$, mikä on huimasti alakanttiin tyypillistä \RSA-salausta ajatellen, 
niin
$a^b$ on luokkaa $10^{400000}$. Tämänkokoisilla luvuilla laskenta alkaa 
olla epätoivoista mille tahansa laskentamyllylle, puhumattakaan ihan normaalista tapauksesta, kuten esimerkissämme, jossa
$a$ tai $b$ voi olla luokkaa $10^{100}$.

%jo numeroita olla enemmän kuin maailmankaikkeudessa atomeja. 

Operaatioon on olemassa tehokas ratkaisu, nimeltään "toistettu neliöön korottaminen"\/ tai "neliöön korotus ja kerolasku". Algoritmi kuvataan [I. Algo]-kirjassa ss. 829 ja [Kob] ss. 23 -- 24:
Pääperiaate on, että kerätään tuloa, jossa edellisellä kierroksella saatu 
tulos korotetaan neliöön ja lisäksi kerrotaan sopivalla luvulla, mikäli 
$n$:n binääriesityksessä on ao. kohdalla $1$.
Kunkin operaation jälkeen redusoidaan modulo $n$, jolloin suurin laskennassa esiintyvä
luku on kaiken aikaa $\leq n^2$. (Oletetaan, että $a < n$.) 
Jätän tilan säästämiseksi kuvauksen ylimalkaiseksi, yksityiskohdat on annettu 
mm. yllä mainituissa viitteissä.
%[Co-Lei-Riv] ss. 829 ja [Kob] ss. 23 -- 24.



%Nämä operaatiot sujuvat bittitasolla
%suorastaan viuhuen ja niinpä laskenta tältä osin voidaan tehdä varsin tehokkaasti.
%Yksityiskohtaisempaan algoritmin selvittämiseen ei tila anna myöten.

\Maple-ohjelmassa algoritmi on suoraan sisää\-nra\-ken\-net\-tu\-na komentona:
\verb_ > c:=a&^b mod n:_
Jos tätä verrataan komentoon
\verb_c:=(a^b) mod n_, jota en suosittele, niin ero saattaa olla huikea, 
sanoisinko ääretön,  
ja ensin kannattaa varmistaa, että ohjelman \texttt{STOP}-nappula toimii.


\subsubsection*{Algoritmien vaativuus}

Laskennallisten algoritmien suhteen on tärkeää arvioida niiden vaatimaa 
laskenta-aikaa (ja tilaa) suhteessa syötteenä olevien lukujen kokoon.
Tällaisia arvioita esiintyy kaikissa numeerisen analyysin kirjoissa, 
alan systemaattisen
tutkimuksen katsotaan kuuluvan teoreettisen tietojenkäsittelytieteen piiriin.
Tässä kirjoituksessa esiintyviin lukuteoreettisiin algoritmeihin paneutuvaa
vaativuusanalyysia käsitellään kirjassa [Kob] huolellisesti ja perusteellisesti. Myös toinen peruskirjamme [I. Algo] sisältää runsaasti vastaavaa 
analyysia. Tähän kirjoitukseen en voi enää mahduttaa uutta asiaa enempää, joten joudun tyytymään tämän tärkeän komponentin osalta kirjallisuusviitteisiin. Mainitsen vain esimerkin ja ulkonäön vuoksi, missä muodossa näitä 
arvioita annetaan. \emph{Eukleideen algoritmin} suoritusaika on 
$O(\log^3 a),$ kun etsitään $\syt(a,b),\ \ a > b.$
Lyhyesti tämä "iso-O"\/-notaatio tarkoittaa suluissa olevaan lausekkeeseen 
verrannollisuutta, eli arvioon kuuluu tarkemmin määräämätön vakiokerroin.
%Lukion (vanhasta) oppikirjastakin löysin asiaan liittyviä alkeita: [LukioNA]
\\
Aikaperspektiivin kannalta mainitsen, että 
viime marraskuuta voidaan pitää numeerisen analyysin ja 
laskennallisten numeeristen algoritmien tutkimuksen $60$-
vuotisjuhlakuukautena, sillä marraskuussa vuonna $1947$ 
ilmestyi \emph{von Neumann}'n ja 
\emph{Goldstine}'n uraauurtava julkaisu aiheesta.


%Nyt on työkalupakkimme hyvin varustettu:


\subsection*{Epäsymmetriset me\-ne\-tel\-mät, jul\-ki\-nen sa\-la\-kirjoitus}


Kaikki vuoteen $1976$ mennessä käytetyt kryptosysteemit lasketaan klassisiin
menetelmiin kuuluviksi. Niille on ominaista, että salausavaimesta $S_e$ voidaan 
kohtuullisella laskentatyöllä johtaa purkuavain $S_d$. Siksi niitä kutsutaan
myös symmetrisiksi menetelmiksi, kuten edellä oli puhe. Käytän tulevaa ennakoiden
kirjaimia $e$ ja $d$, jotka liittyvät sanoihin "encrypt" (salata) ja "decrypt"\/ 
avata salaua, dekryptata.

%Jo $1800-$luvun loppuolelta lähtien on ymmärretty, että itse salausmenetelmän
%salassa pysymiseen ei voi luottaa,
%"the enemy knows the system", oli hollantilaisen \emph{Kerkhoffin} (1835-1903)
%lentävä lause.  *** tarkista ***
%Kaikki salaustoiminta piti rakentaa avaimien salassa pysymisen varaan.

%Ainoastaan avaimet olivat tarkoin varjeltavia salaisuuksia, ja niitä jouduttiin
%vaihtamaan usein.

%Klassiset kryptosysteemit ovat symmetrisiä siinä mielessä, että
%sekä salaamiseen että salakoodin avaamiseen käytettävä avain saadaan 
%helposti johdetuksi salausavaimesta.
%Miten olis: Kirjoitusavain/lukuavain?

Nykyisin, kun sähköinen luottamuksellisen tiedon välitystarve on räjähdysmäisesti kasvanut sotilas- ja diplomaattialueen ulkopuolelle, on suoranainen välttämättömyys suunnitella yhtenäinen salaustekniikka, jotta laajojen järjestelmien 
yhteesopivuus olisi mahdollinen.
Niinpä tarve yleiseen käyttöön sopivan julkisen salakirjoitusjärjestelmän
kehittämiseen 
nousi 1970-luvulla voimakkaasti esiin.






%** Avainten lkm ehkä jossain  : $ (n(n-1)/2)$.

%************** siirrettävä ********************

%Nykyisten kryptosysteemien suunnittelijoiden on otettava huomioon, että
%koodin murtajilla on vahva matemaattisten menetelmien osaaminen,
%supertietokoneen laskentakapasiteetti, täydellinen tieto käytettävistä
%salausmenetelmistä. Vain avaimet puuttuvat. 
%Heille on oletettava olevan mahdollista paitsi kaapata lähetettyjä viestejä,
%myös lähettää itse selväsanaisia viestejä ja kaapata vastaavat salaviestit.
%Näin heillä on käytössään suuri määrä $(m,c)-$pareja, missä $m$ on selväkielinen viesti ja $c$ on vastaava salakielinen. 
%%Avaimia on siksi vaihdettava tiuhaan tahtiin.
%
%************** siirrettävä *********************

%** kuva.m ***


%Diffie ja Hellman (1976) tekivät vallankumouksellisen ehdotuksen ...
%public key cryptography.

%Toteutus RSA 1978.

\subsubsection*{Julkisen salakirjoituksen periaate}

Jokaisella tiedonvaihtoon osallistuvalla osapuolella on kaksi avainta,
julkinen ja salainen. Kryptologian esityksissä on tullut yleiseksi tavaksi 
kutsua kahta kommunikoivaa osapuolta nimillä \emph{Alice} ja \emph{Bob}.

Käytetään edellä olevien $e$- ja $d$- symbolien ohella myös kirjaimia $P$ -- "Public"
ja $S$ -- "Secret"\/ viittaamaan kyseisiin avainfunktioihin. 
\emph{Alice}:lla on siten julkinen avain $P_A$ ja salainen 
avain $S_A$ ja \emph{Bob:}lla vastaavasti $P_B$ ja $S_B.$

Kommunikaatiota \emph{Alice:}n ja \emph{Bob:}n välillä esittää kuva, jossa 
on mukana ilkeä \emph{Eve}, joka sieppaa linjalta salakirjoitettuja viestejä,
minkä ehtii. %\emph{Eve} voi myös ...



\begin{center}
\includegraphics[height=4cm, width=8cm]{AliceBob.eps} \\
%\includegraphics[height=4.5cm, width=8cm]{AliceBob.eps} \\
%\textsc{Kuva 1.} Alice ja Bob
\end{center}


Kaikilla kommunikoivilla osapuolilla on käytössään kaikkien muiden julkinen 
avain,
periaatteessa ne voitaisiin vaikka julkaista webbisivulla.
Lisäksi jokaisella osapuolella $X$ on oma henkilökohtainen salainen avain $S_X$, jota kukaan muu maailmassa ei tiedä.

Voimme ymmärtää tässä kuvailussa avaimen funktioksi, joka muuntaa viestin numeerisen esityksen selväkielisestä salakieliseksi tai päinvastoin.
Joka tapauksessa funktiot $P_X$ ja $S_X$ ovat toistensa käänteisfunktioita.
Niinpä, kun \B\/ salakirjoittaa viestin $m$ käyttäen \A:n julkista avainta 
$P_A$, hän tuottaa luvun $c=P_A(m).$ \A:lla ja vain \A:lla on salainen avain
$S_A$, joka on \A:n julkisen avaimen $P_A$ käänteisfunktio.
Siis \A\/ avaa \B:n lähettämän viestin laskulla $S_A(c).$

Mikä tässä on uutta ja ihmeellistä? Kaikki osapuolet tuntevat avaimen $P_A$,
mutta tämä funktiopa onkin tehty sellaiseksi, että sen käänteisfunktiota 
on äärimmäisen vaikea laskea. Tässä on ero symmetrisiin menetelmiin nähden.
\emph{Diffie ja Hellmann} käyttivät termiä "trapdoor function", jolle 
[KN]:ssä 
käytetään suomennosta "salaovifunktio". Kehitin itse kevytmielisesti
suomennoksen "loukkuluukkufunktio".\/
Luukusta on helppo astua sisään huomatakseen joutuneensa loukkuun.
Takaisin ulos päästäkseen on avattava systeemilukko, jossa on miljoonia 
mahdollisuuksia.  Matemaattisemmin ilmaistuna, on löydettävä 
laskennallisesti kohtuullinen tehtävä,
jonka käänteistehtävä on laskennallisesti kohtuuton, kuten
$1000$ vuotta vaativa laskenta-aika
nopeimmalla supertietokoneella ja parhaalla laskenta-algoritmilla.

\RSA-algoritmissa tuo laskennallisesti kohtuullinen tehtävä on kahden 
hyvin suuren alkuluvun $p$ ja $q$ kertominen: $n=p\, q$. 
Kun luvut valitaan riittävän suuriksi (luokkaa $150$ numeroa), niin
käänteinen tehtävä, luvun $n$ tekijöihin jako on laskennallisesti kohtuuton.
Käsitteiden "kohtuullinen"\/ ja "kohtuuton"\/ kvantifioiminen edellyttää
algoritmien laskennallisen vaativuuden arvioita, mihin
liittyvää "yleissivistystä"\/ annettiin edellä lyhyesti.

On tietysti myös muistettava, että tietokoneiden prosessoritehojan kasvun 
ja aivan uusien laskentainnovaatioiden 
takia \emph{loukkuluukku} vuonna $2008$ ei välttämättä olekaan 
sitä enää vuonna $2018$.

Mutta jatkakaamme \RSA-menetelmän kuvailun tiellä. 
%Näiden pohdintojen saattelemana 
%olemme valmiit uppoutumaan \RSA-algoritmin syövereihin.
%Kun puhutaan \emph{avaimesta}, tarkoitetaan sellaista lukua, lukuparia ym. parametria, joka määrää funktion $P$ tai $S$, jolla salataan tai avataan salaus. 
%Käytämme kirjaimia $e$ ja $d$ viittaamaan sanoihin "encrypt"\/ (salaus) 
%ja "decrypt"\/ (salauksen purku, dekryptaus). Siis $e$:n avulla määritetään
%salausfunktio, eli julkinen avainfunktio $P$ ja $d$:n avulla salakoodin avausfunktio, eli salainen avainfunktio $S$.  
%Toisaalta 
%avaimeksi voidaan kutsua myös itse funktiota, kuten $P_A$, $S_A$ edellä.
%Muistellaan, että \emph{Caesarin menetelmän} yhteydessä puhuttiin avaimesta $e$ ja sen 
%määräämästä funktiosta $f_e(m)= m+e \pmod n$.
%jota siis tarpeen tullen myös voidaan 
%kutsua avaimeksi.
%Seuraavassa palaamme merkintöihin $e$ -- encrypt ja $d$ -- decrypt.
%*** Onko oikea paikka ?? Ei ole, siirrä ... ***
\\
Edellä symmetrisistä menetelmistä puhuttaessa koodattiin viestit kirjain tai 
tavu kerallaan numeroksi ja muunnettiin
niitä sopivasti sekoittamalla. Lukuteoria ja tietotekniikka antavat 
mahdollisuuden käsitellä viestejä suurina kokonaislukuina. Viestin numerokoodi käsitetään numeerisen vektorin sijasta yhdeksi suureksi kokonaisluvuksi, jolle
tehdään sopiva matemaattinen muunnos $P$. Vastaanottaja avaa sen käytössään
olevalla käänteismuunnoksella, eli salaisella avaimella $S$. 
%(S -- salainen, secret, d -- decrypt). 
Jos viesti on kovin pitkä, se jaetaan lohkoihin, joiden pituudet voivat olla 
vaikka $100 - 200$ merkkiä. Ts. viesti voidaan esittää numeerisena vektorina,
jonka komponentit ovat (tarvittaessa) suuria kokonaislukuja.

%Huolta on kannettava siitä, että käänteisfunktio $S_d$ ei joudu 
%"nuuskijan \E"\/ käsiin,
%sekä siitä, että sen saaminen selville käyttämällä parhaita matemaattisia 
%työkaluja ja niiden varaan rakennettuja algoritmeja sekä 
% (super)laskentavoimaa, ei onnistu järkevässä ajassa. 

%*************** siirron loppu ************************


Seuraavaksi esitettävän algoritmin kuvauksessa ajatellaan, että selväkielisen
viestin numeerinen vastine edustaa koko viestiä tai yhtä  
viestivektorin komponenttia. Tälle käytetään merkintää $m$, niinkuin 
"message". Salakirjoitetulle muunnokselle käytetään nimeä $c$, niinkuin
"ciphertext", yleisesti siis $c=P(m)$ ja $m=S(c)$, koska $P$ ja $S$ ovat 
toistensa käänteisfunktioita.

Miten nuo $P$ ja $S$ rakennetaan \rsa-menetelmässä? Nyt olemme valmiit 
sen kertomaan ja perustelemaan.

\vfill\eject


\begin{algo}[\RSA]\label{RSA}
.
\begin{enumerate}
\item
Muodostetaan kaksi samaa suuruusluokkaa olevaa suurta alkulukua $p$ ja $q$.

\item
Lasketaan $n=p\, q$ ja $\phi = (p-1)(q-1)$. 
\footnote{Kirjain $\phi$ viittaa ns. \emph{Eulerin} $\phi$-funktioon, emme kuitenkaan tarvitse siihen liittyvää \emph{Eulerin lausetta}, vaan pärjäämme 
Fermat'n pikkulauseella.}
\item
Valitaan luku $e$, $1 < e < \phi$ siten, että\\ $\syt(e,\phi)=1.$
(Luvun $e$ ei tarvitse olla kauhean suuri.)
% joskus käytetään jopa valintaa $e=3$, mikäli $3 \nmid \phi$)


\item
Lasketaan \emph{laajennetulla Eukleideen algoritmilla} luku $d$ siten, 
että $e\,d \equiv 1  \pmod \phi.$

\item
$A:$n \textbf{julkinen avain} on $(e,n)$ ja $A:$n \textbf{salainen avain} 
on $(d,n)$.

\item
Olkoon $m$ viestin numeerinen esitys, $0 \leq m \leq n$.\\
\textbf{Muodostetaan salainen viesti} $c=m^e (\Mod \, n)$ ja lähetetään $A:$lle.

\item
$A$ {\bf avaa salaisen viestin} $c$ omalla salaisella avaimellaan $d$
kaavalla $a=c^d \pmod n$. Ja todellakin $a = m$, kuten seuraavaksi
osoitetaan.
\end{enumerate}
\end{algo}

%Ennenkuin lähdemme todistamaan algoritmia oikeaksi, lisäämme lukuteorian
%työkalupakkiimme vielä pari työkalua.



\textbf{\RSA-algoritmin oikeaksi todistaminen}
\begin{proof}


Salainen viesti $c=m^e \pmod n$, missä $m$ on alkuperäinen viesti,
$e$ salauseksponentti, $n=p\,q$, $p$ ja $q$ ovat alkulukuja.
Avattu viesti $a=c^d \pmod n$ missä $d$ on avauseksponentti ja toteuttaa yhtälön
$$e\,d \equiv 1 \pmod \phi, \ \ \phi=(p-1)(q-1).$$

Pitää siis todistaa, että avattu viesti on sama, mistä lähdettiin, eli $a=m.$

No katsotaan: $c^d = (m^e\, \pmod n)^d \equiv  m^{e\, d} \pmod n$
potenssipotenssiin-säännön mukaan.

Nyt $e\,d = 1 + j\,\phi=1+ j\,(p-1)(q-1)$ jollain $j$, joten

$m^{e\,d} = m\, m^{j(p-1)(q-1)}$. Järkevä oletus on, että $m < p$ ja $m < q$,
jolloin varmasti $\syt(m,p)=\syt(m,q)=1.$ 

Niinpä \textbf{Fermat'n pikkulauseen}
mukaan \\ 
$m^{p-1}\equiv 1 \pmod p$ ja $m^{q-1}\equiv 1 \pmod q $, joten 
\smallskip
\qquad $ m^{j(p-1)(q-1)}={(m^{p-1})}^{j(q-1)}\equiv 1 \pmod p$. \\ 
Vaihtamalla 
$p$:n  
ja $q$:n järjestys, saadaan \\ 
\medskip
 \qquad $ m^{j(p-1)(q-1)}\equiv 1 \pmod q$.
\\
\textbf{Kiinalaisen selviön} mukaan\\  
%\vspace 1 mm
%\smallskip
\qquad $ m^{j(p-1)(q-1)}\equiv 1 \pmod n$.


Siis $a=c^d \equiv m\, m^{e\,d} \pmod  n \equiv m \pmod n$

Jos luovumme yllä olevasta "järkevästä oletuksesta", niin esim. $p \mid m,$
jolloin $m^{e\,d}\equiv m \pmod p$, koskapa $p$ on molemmissa yhtälön
puolissa tekijänä. Tässä tapauksessa ei tarvita Fermat'n apua, mutta
tilanne on syytä turvallisuussyistä kuitenkin sulkea pois.
Joka tapauksessa väite pätee yleisesti, tehtiinpä yllä järkevä tai
vähemmän järkevä oletus.
\end{proof}

%\begin{huom}
%Vaikka menetelmä on \emph{epäsymmetrinen}, siihen sisältyy 
%seuraavanlainen symmetria avainten suhteen:\\
%$B$ voi salata viestin myös omalla salaisella avaimellaan $d_B,$
%lähettää sen $A:$lle, ja $A$ voi avata sen $B:$n julkisella avaimella $e_B$ 
%Laskuhan on $d$:n ja $e$:n suhteen täysin symmetrinen.
%\end{huom}

%* Mieti vielä, ilmaistaan mieluummin käänteisfunktio-ominaisuutena **

%Tämä on matemaattisesti totta, mutta onko siinä mitään järkeä? 
%Viestinhän voi avata jokainen $B$:n julkisella avaimella. 
%Mutta onpa sittenkin,
%sillä sähköinen allekirjoitus tehdään näinpäin. Tästä lisää jäljempänä.



\subsubsection*{Esimerkki}



%Käytössäni on \maple:n käyttäjäarkistosta hakemani 
%funktiot \texttt{to\_number} ja \texttt{from\_number},
%joilla muunnetaan viesti numeroksi ja kääntäen, annetun 
%aakkosvektorin suhteen.

%Kuten sanottu, käytän symbolilaskentaohjelmaa \maple\/ kuvaamani 
%menetelmän
%vaiheiden konkretisoimiseen ja laskentaesimerkkiinn. %Syynä on ennen kaikkea
%se, että nyt tarvitaan ohjelmaa, joka osaa käsitellä periaatteessa 
%mielivaltaisen suuria (koneen muistikapasiteetin rajoissa 
%kokonaislukuja tarkasti.

Esitykseni on mukaelma viitteen [Cos] tyylistä. 
Otan "mustina laatikoina"\/ siinä annetut 
funktiot \texttt{to\_number} ja \texttt{from\_number}, jotka
muuttavat merkkijonon eli tekstivektorin numeroksi ja vastaavasti takaisin merkkijonoksi annetun aakkosvektorin 
suhteen vastaavaan tapaan kuin edellä olleet \matl-funktiot. Erona on, että 
nyt emme muuta tekstivektoria numeerikseksi vektoriksi, vaan yhdeksi kokonaisluvuksi. Kaiken muun avaan komento komennolta lukijan silmien eteen.

Esimerkin avaimet ovat lähes turvallista kokoa, olisivat olleet vielä hiukan 
yli $10$ 
vuotta sitten. Jäljempänä pohditaan tarkemmin.

Jos muutamme valitun aakkosvektorin suhteen sanan \texttt{SOLMU} numeeriseksi 
saamme: 

\begin{verbatim}
> aakkoset:="ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ "
> to_number("SOLMU");
                 1915121321
\end{verbatim}
Nähdään, että kirjaimia vastaavat numerot on pantu peräkkäin tyyliin:
$A=01, B=02,\ldots, S=19, \ldots U=21$

Toinen, kenties luonnollisempi tapa olisi esittää viesti $N-$järjestelmän
lukuna ja muuntaa se $10-$järjestelmään, missä $N$ on aakkosvektorin pituus. Tällöin samainen \texttt{SOLMU}
muuntuisi luvuksi\\
$21+13\cdot30+12\cdot30^2+15\cdot30^3+19\cdot30^4 = 15806211.$

Koska yllä mainittu \texttt{to\_number}-funktio 
tekee edellisellä tavalla, noudatan sitä.     

%Nämä on kirjoittanut \emph{John B. Cosgrave, Mathematics Department, 
%St. Patricks College, Drumcondra, Dublin 9, Ireland}




%\begin{verbatim}
%aakkoset:="ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ ";
%v:=to_number("AI AI AI KASTUTAAN SIILIÄITI JUOKSEE");
%1093201093201093211 ... 093210211511190505
%\end{verbatim}
%$01\leftrightarrow A$ (luvun etunolla putoaa pois)\\
%$09\leftrightarrow I \ldots 19\leftrightarrow S 05 
%\leftrightarrow E $ 

%\begin{verbatim}
%from_number(v);
%             "AI AI AI KASTUTAAN SIILI?ITI JUOKSEE"





Alla esiintyvät \maple-komennot ovat suurelta osin itsensä selittäviä.
Mainitsen ja kertaan tässä joitakin nimityksiä ja sellaisia komentoja,
joiden merkitys voi olla epäselvä tai unohtunut.\\
Alkukirjain $i$ viittaa sanaan ``integer'', kokonaisluku.

\begin{tabular}{ll}
\texttt{ifactor} &   Tekijöihin jako\\
\texttt{igcd(a,b)} & gcd = syt\\
\texttt{igcdex(a,b,'x','y')} &  gcd extended = Laajennettu \\ 
            &   Eukleideen algoritmi\\
\texttt{a mod b} & Jakojäännös laskussa $a/b$
\end{tabular}






%Alkukirjain $i$ viittaa sanaan ``integer'', kokonaisluku.
%\begin{verbatim}
%ifactor   - Kokonaisluvun tekijöihin jako
%igcd(a,b) - gcd (greatest common divisor)=syt
%igcdex(a,b,'x','y')  -  gcd extended = 
%              Laajennettu Eukleideen algoritmi
%\end{verbatim}

Muistutan vielä, että 
komento \texttt{d:=igcdex(a,b,'x','y')} 
palauttaa tuloksen \texttt{d=syt(a,b)} ja lisäksi muuttujissa 
$x$ ja $y$ kertoimet, joilla $d=a\,x + b\,y.$




%\texttt{}

\textbf{Ja nyt se alkaa!}

Alice valitsee kaksi suurta alkulukua ja laskee niiden tulon:
\begin{verbatim}
> pA := nextprime(10^60 + 1234567*rand()^5);
1198076816021558356980152413678621
5524827311143774029092192981559
> qA := nextprime(10^65 + 8765439999*rand()^5);
24557694884338801620018108793784400
77015568602607435050878572990629
> nA:=pA*qA: 
> length(nA);
131
\end{verbatim}
Luvussa $n_A$ on $131$ numeroa.
Kokeillaan tekijöihinjakoa.
%\begin{verbatim}
\\
\verb_> ifactor(nA);   _\\
\verb_Warning,  computation interrupted_\\
%\end{verbatim}
Painettiin \texttt{STOP}-nappulaa. Ei näytä siltä, että kannattaisi ryhtyä 
odottelemaan.\\
%\maple\/ ei "numeronmurskauksessa"\/ yllä parhaiden käännettyjen ohjelmien 
%tasolle.
Kokeillaan tekijöihinjakoa, kun $p_A$ kerrotaan jollain umpimähkään valitulla
pienehköllä luvulla.
\begin{verbatim}
> ifactor(pA*465734);
(2) (337) (691) (119807681602155835698015241
36786215524827311143774029092192981559)
\end{verbatim}
Onnistuu muotoa $p_A\,k$ olevalle luvulle hetkessä, 
kun kerroin $k$ on miljoonan luokkaa,
mutta jos
vähän kasvatetaan, alkaa kestää tuskaisen kauan.

Seuraavaksi Alice laskee $\phi_A$:n, jota varten siis täytyy tuntea 
 $n_A$:n tekijät $p_A$ ja $q_A$. 
%\begin{verbatim}
\\
\verb_> phiA := (pA - 1)*(qA - 1):_
%\end{verbatim}

 Alice valitsee salauseksponentin ("encryption exponent") .
%\begin{verbatim}
\\
\verb_ > eA := nextprime(10^5 + rand()); _\\
\verb_               624044487349_ \\
%\end{verbatim}
Todetaan, että $\syt(e_A,\phi_A)=1$.  Tämä toteutuu hyvin suurella 
todennäköisyydellä (miksi?), mutta se on kuitenkin erikseen tarkistettava.
%\begin{verbatim}
\\
\verb_ > igcd(eA, phiA); _\\
\verb_                   1 _
%\end{verbatim}
\\
Alice laskee nyt laajennetulla Eukleideen algoritmilla oman salaisen avaimensa eksponentin $d_A$.
%\begin{verbatim}
\\
\verb_> igcdex(eA, phiA, 'xA', 'yA'):_\\
\verb_> dA := xA mod phiA;  _ \\
\verb_1368483131199786650215235652 ... _\\
\verb_> length(dA);_\\
\verb_                  131_\\
%\end{verbatim}
Salaisessa eksponentissa $d_A$ on $131$ numeroa.
Tarkistetaan, vaikka tiedetään, että  $e_A\,d_A \equiv 1 \pmod {\phi_A}$
%\begin{verbatim}
\\
\verb_> eA*dA mod phiA;_\\
\verb_                   1_\\
%\end{verbatim}
Alicen julkinen avain on $(e_A,n_A)$ ja salainen avain on $(d_A,n_A)$.
Edellä esitellyn puhetavan mukaisesti voidaan myös sanoa, että $A$:n julkinen
avain on parametrien $(e_A, n_A)$ määräämä funktio 
\\$P_A(m)= m^{e_A} \pmod {n_A}$ ja salainen avain vastaavasti
funktio $S_A(c)=c^{d_A} \pmod {n_A}.$
\\
Bob tekee vastaavat asiat tykönään:
%\begin{verbatim}
\\
\verb_> pB := nextprime(10^60 + 23453218*rand()^5):_\\
\verb_> qB := nextprime(10^65 + 12456800*rand()^5):_\\
\verb_> nB:=pB*qB: phiB:=(pB-1)*(qB-1):_\\
\verb_> eB := nextprime(10^4 + 3*rand());_\\
\verb_                2336493690667_\\
\verb_> igcd(eB, phiB);_\\
\verb_                        1_\\
\verb_> igcdex(eB, phiB, 'xB', 'yB'):_\\
\verb_> dB := xB mod phiB: _\\
\verb_> length(dB);_\\
\verb_                      131_\\
%\end{verbatim}
Bob'n julkinen avain on $(e_B,n_B)$ ja salainen avain $(d_B,n_B)$, ja 
ne määräävät samalla tavoin julkisen ja salaisen avainfunktion $P_B$ 
ja $S_B.$
Huomaa, että kummankin salainen avain pysyy
kunkin omana tietona. Sitä ei kukaan missään vaiheessa lähetä kenellekään.

\B\/ salaa numeroksi koodatun viestin $m$ käyttäen Alicen julkista avainta,
ts. hän suorittaa laskun \\$c=P_A(m)= m^{e_A} \pmod {n_A}$, ja 
%$(n_A,e_A)$, ja
lähettää salaviestin $c$ Alicelle, kas näin:
%\B\/ muodostaa selväkielisen viestin $m$, muuntaa sen kokonaisluvuksi
%\begin{verbatim}
\\
\verb&> m := to_number(`TAVATAAN HIEKKALAATIKOLLA`);& \\
\verb_ 200122012001011432080905111101120101200911151_\\
\verb_ 21201_\\
\verb_> c:=m&^eA mod nA:  # modulaarinen potenssi    _\\
\medskip
%\end{verbatim}
%Hän salaa viestin käyttäen \A:n julkista salauseksponenttia $e_A$
%\begin{verbatim}
%\end{verbatim}
%Muista: Mapleen on ohjelmoitu "square and multiply"\/-algoritmi laskettaessa 
%potenssi $\pmod n$. Jos laskettaisiin ensin
%potenssi $m^{e_A}$, saataisiin aivan hillitön luku 
%(tässä tapauksessa 600-numeroinen), ja laskenta tukehduttaisi koneen.
%\begin{verbatim}
%length(m)*length(eA);
%                              600
%\end{verbatim}
%** edellä oleva on jo sanottu ***
\A\/ avaa viestin omalla salaisella avaimellaan:\\$a=S_A(c)=c^{d_A} \pmod {n_A}.$
Edellä oikeaksi todistetun algoritmin mukaan pätee: $a = m.$
%\begin{verbatim}
\\
\verb_> a:=c&^dA mod nA;_\\
\verb_ 200122012001011432080905111101120101200911151_\\
\verb_ 21201_\\
\verb=from_number(a);=\\
\verb_           "TAVATAAN HIEKKALAATIKOLLA"_\\
%\end{verbatim}
%Ja toden totta näin se on, ja he rientävät hiekkalaatikolle.
%\begin{center}
%--- Happy end ---
%\end{center}


\subsection*{Sähköinen allekirjoitus}


%Mistä \A\/ voi varmasti tietää, että viestin lähettäjä oli oikea \B ?
%Onhan \A:n julkinen avain kaikkien tiedossa. 
%Varmistaakseen tämän sekä sen, että \B\/ saa luotettavan tiedon siitä,
%että vastausviestin lähettäjä on \A\/, samalla varmistaen viestin sisällön 
%aitouden,
\A\/ vastaa ja  varustaa viestinsä digitaalisella allekirjoituksella, jotta
\B\/ varmasti tietää, että vastaaja on \A\/ ja viesti on tarkalleen se, 
jonka \A\/ on lähettänyt.

Viesti voisi olla\\ 
\texttt{v:="OLEN ALIISA JA TULEN KANSSASI"}.
 Olkoon $m$ tämän viestin numeerinen esitys.
\A\/ muodostaa allekirjoituksen $s = S_A(m)$, toisin sanoen hän 
koodaa   
viestinsä omalla \textbf{salaisella avaimellaan}, ja lähettää \B:lle 
viestin, jonka perään liittää tuon koodin, eli luvun $s$.  \B\/ vastaanottaa
 sanoman vektorina $[v,s]$, lukee selväkielisen viestin $v$, jonka perusteella
tietää käyttää \A:n julkista avainta allekirjoituksen tarkistamiseen.
\B\/ suorittaa laskun $P_A(s).$ Jos tuloksena on $m$, on \A:n identiteetti 
ja viestin sisältö varmennettu.

\textbf{Sama laskettuna auki}

Määritellään \maple:ssa edellä käyttettyjen avaimien avulla \A:n 
julkinen ja salainen avainfunktio $P_A$ ja $S_A$
\\
\verb_> PA:=m->m&^eA mod nA:  SA:=s->s&^dA mod nA:_\\
\verb_> v:="OLEN ALIISA JA TULEN KANSSASI";_\\
\verb&> m:=to_number(v);&\\
\verb_   15120514270112090919012710012720211205142_\\
\verb_   71101141919011909_\\
\A:n digitaalinen allekirjoitus \\
\verb& > s:=SA(m);  (130 numeroa):&\\
\verb_9327163344329493987807141048894710565396353.._\\
%\verb_3376189423128347070998935883530407764078809_\\
%\verb_50872830277923609117368156344016286519342350_\\
\A\/ lähettää viestin:\\
\verb_> Bobille:=[v,s];_\\
\verb_["OLEN ALIISA JA TULEN KANSSASI", 9327163...]_\\
\B\/ muuntaa saamansa vektorin 1. komponentin numeeriseksi ja tarkistaa
viestivektorin 2. komponentin avulla viestin allekirjoitetun sisällön.
\verb&> m:=to_number(Bobille[1]);&\\
\verb_  1512051427011209091901271001272021120514.._\\
\verb&> t:=PA(Bobille[2]);&\\
\verb_  1512051427011209091901271001272021120514.._\\
\verb_ > m - t_\\
\verb_                  0_\\
Kaikki hyvin!


Tähän voidaan tietysti vielä lisätä allekirjoitetun viestin salaus mukaan 
tarvittaessa. Edellinen vastaisi (avointa) allekirjoituksella varmennettua 
paperia 
ja jälkimmäinen kuoreen sinetöityä allekirjoitettua paperia.
\\
Tyypillisiä tilanteita ovat vaikkapa pankkisovellukset. Saman 
allekirjoituksen voi haluta tarkistaa useampikin taho. Sehän käy, koska julkinen avain on kaikilla käytössään ja salainen vain asianomaisella 
allekirjoittajalla. Tyypillinen esimerkki voisi olla \B:n 
\A:lle lähettämä sähköinen shekki, jonka allekirjoituksen \A\/ tarkistaisi, lähettäisi 
edelleen pankkiin, jossa se niinikään voitaisiin tarkistaa \B:n julkista 
avainta käyttäen ja suorittaa asianmukainen rahojen siirto.





\subsubsection*{\rsa:n turvallisuus}



\rsa:n turvallisuus perustuu suuren luvun tekijöihinjakotehtävän vaativuuteen. 
Jos modulin $n$ tekijöihin jako onnistuu,
niin avaimet saadaan käden käänteessä noudattaen yleisen algoritmin kuvausta 
tai sitä seurannutta esimerkkiä. Entä kääntäen, pitääkö paikkansa, että jos 
suuren luvun tekijöihin jako on vaikeaa, niin \rsa:n murtaminen on vaikeaa?
Ongelmaa on tutkittu tiiviisti \rsa:n julkistamisesta lähtien, asiaa ei ole 
pystytty todistamaan, mutta mitään 
muuta tapaa menetelmän murtamiseen ei myöskään ole löydetty.
Lainaan [I. Algo]-kirjaa s. 835: Jos valitaan satunnaisesti kaksi 
$100$-numeroista alkulukua, niin niiden avulla voidaan muodostaa avain,
joka on "murtamaton"\/ nykyteknologialla (v. 1998).
%Tämän mukaan toimimme esimerkissämme  turvallisen suurilla luvuilla (ainakin 
%10 vuotta sitten).

Kuitenkin on erinäisiä seikkoja, jotka täytyy ottaa huomioon, sillä
koodinmurtajien työkalupakissa on taatusti ainakin modulaariaritmetiikan
peruslauseet, Fermat'n pikku lause, Eukleideen algoritmi, Kiinalainen 
jäännöslause ja parhaat laskenta-algoritmit.
Lisäksi raakaa laskentavoimaa on oletettava olevan suurimman 
supertietokoneen verran ja tehokkaasti hajauttaen paljon enemmänkin.

%Mainitsen joitakin yksinkertaisia huomioonotettavia seikkoja. 
[HandB] käsittelee aihetta laajasti esittäen ainakin $8$ erilaista 
hyökkäysmahdollisuutta ja niiden torjuntalääkkeet. 
Monissa muissa lähteissä, kuten
[Nyberg], [Wiki] ja aivan erityisesti [Sti] (s. 225) on 
lisää kryptoanalyyttisiä konnankoukkuja ja niiden 
vastalääkkeitä. 


Pari yksinkertaisinta seikkaa mainitakseni, 
%\textbf{Alkulukujen $p$ ja $q$ valinta}\\ 
on selvää, että alkulukujen $p$ ja $q$ on molempien oltava niin suuria, ettei 
pienistä luvuista lähtevä alkulukujen laskenta ja tekijätarkistus onnistu 
kohtuuajassa. Toisaalta ne eivät saa olla niin lähellä toisiaan, että 
voitaisiin tekijän etsintä aloittaa $\sqrt n$:n läheltä.
\\
Pieni salauseksponentti $e$ on salaamisen kannalta tehokas, mutta ongelmallinen, jos viesti (tai viestin osa) $m$ on 
niin pieni,
että $m < n^{1/e}$. Tällöinhän salaviesti $c = m^e \pmod n= m^e$
(mieti!). Murtaja \E\/ muodostaa luvun $c^{1/e}$, ja lukee $m$:ää kuin avointa
kirjaa. Tämä voidaan estää lisäämällä viestiin riittävästi "suolaa"\/, eli ylimääräistä puppua.


%olla suuria, nykyprosessoritehoja ajatellan turvallinen koko
%tulolle \\$n=p\, q$ on ehkä luokkaa $200$ numeroa, mutta tämä 
%luku kasvaa jatkuvasti ajan mukana. 
%Kumpikaan ei saa olla niin pieni, että parhailla alkulukujen määrittämismenetelmillä päästäisiin kohtuuajassa käymään läpi alkuluvut alusta alkaen ja kokeilemaan kutakin vuorollaan, olisiko se tulossa $n$ tekijänä. 
%\\
%Niiden tulee siis olla samaa suuruusluokkaa, mutta toisaalta ne eivät saa olla liian lähellä toisiaan. Muutenhan voitaisiin
%aloittaa tekijän etsintä luvun $\sqrt{n}$ lähistöltä.
%(Voidaan olettaa, että koodinmurtajat jauhavat jatkuvasti tällaisia ja muita vastaavia testejä siltä varalta, että joku olisi tehnyt huolimattoman valinnan.)

%%\textbf{Salauseksponentin $e$ valinta}

%Periaatteessa salauseksponentti $e$ voitaisiin valita pieneksi (vaikka $e=3)$,
% sehän määrää vain julkisen avaimen. 
%Pieni $e$ on ongelmallinen, jos viesti (tai viestin osa) $m$ on niin pieni,
%että $m < n^{1/e}$. Tällöinhän salaviesti $c = m^e \pmod n= m^e$
%(mieti!). Murtaja \E\/ muodostaa luvun $c^{1/e}$ ja lukee $m$:ää kuin avointa
%kirjaa. Lyhyt viesti voisi olla vaikkapa \texttt{PIN}-koodi. Salakirjoittaja
%voi lisätä viestiinsä ylimääräistä puppua, jotta päästään tästä pälkähästä.
%Puhutaan viestin "suolaamisesta".

%Kryptologinen toiminta on kahden joukkueen välistä kovasti kilpailuja ja pelaamista suosivia. 
%Panoksina ovat aikojen saatossa olleet ihmishenget sotatantereilla.
%Kryptologian kilpailuasetelmassa ovat nykyisin joukkueiden 
%pelivälineinä niin vuosituhansien takaiset matemaattiset menetelmät 
%kuin uudet modernit abstraktit ideat yhdessä verkottuneen tietokonemaailman 
%tarjoamien laskentaresurssien ja  kanssa. 

Kryptologia on aina ollut kahden joukkueen välistä kilpajuoksua. Rauhanomaiseen 
kilpailutoimintaan liittyy \texttt{RSA129}-projekti, joka lähti liikkeelle, kun 
\rsa:n keksijät Rivest, Shamir ja Adleman esittivät vuonna 1977 Scientific American-lehdessä 
$129$-numeroisen kahden alkuluvun tulon haasteeksi tiedeyhteisölle tekijöiden löytämistä varten.
He arvioivat tekijöihin jakoon kuluvan aikaa n. $20 000$ vuotta silloisilla menetelmillä 
ja tekniikalla. Hollantilainen lukuteoreetikko \emph{Arjen Lenstra} organisoi 
maailmanlaajuisen laskentaverkoston\\
\href{http://www.math.okstate.edu/~wrightd/numthry/}
{\texttt{http://www.math.okstate.edu/$\sim$wrightd/numthry/}}
\linebreak
\href{rsa129.html}{\texttt{rsa129.html}}
\\
Lenstran ryhmä käytti 1980-luvulla kehitettyä uutta lukuteoreettista menetelmää ja kykeni
purkamaan algoritmin rinnakkaislaskentaa hyödyntävään muotoon. Huhtikuussa 1994 
tekijöihin jako onnistui, ja \rsa:lla salattu viesti saatiin auki. Viestin 
sisältö oli: "The magic words are squeamish ossifrage."

Kilpajuoksu ei päättynyt tähän. [Wiki]:ssä mainitaan luku \texttt{RSA-200}, joka 
jaettiin tekijöihin vuonna $2005$. 
%Sehän tekee meidän esimerkkimme \A:n ja \B:n olon jo hiukan epävarmaksi. 
Kirjassa [Sti] (v. 2006) s. 175 mainitaan. että nykyiset 
tekijöihinjakoalgoritmit löytävät $512$:n pituisen binääriluvun tekijät.
Luvun pituus kymmenjärjestelmässä  
saadaan kertomalla $\log_{10} 2$:lla (eikö vain), joten se on n.  
$150$ numeroa. Turvalliseksi luvun $n=p\, q$ suuruudeksi 
\emph{Stinton} vakuuttaa nykytietämyksellä 
$1024$ bittiä, siis n. $300$ numeroa $10$-järjestelmässä. 

Ajantasaista
tietoa voi hakea  [Wiki]:sta sanoilla  "RSA Factoring challenge"\/, joka kertoo, että 
tämä kilpailumuoto lopetettiin vuonna 2007, koska 
"nykyteollisuudella on aiempaa huomattavasti kehittyneempi 
ymmärrys yleisistä kryptoanalyyttisistä periaatteista"\/.
%The RSA challenges ended in 2007.[1] According to RSA "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active."[2]

%Tämä ei merkitse, että \rsa-olisi murrettu. Luonnollisesti tällaiseen yritykseen ryhtyminen yhden sanoman vuoksi 
%on lievästi sanoen epäkäytännöllistä. \rsa:ssa avaimia on helppo muuttaa (kuten esimerkissämme nähtiin), 
%ja ennen kaikkea avaimien pituutta kasvattaa. Tuollaisilla projekteilla 
%näytetään, miten suuriin lukuihin täytyy varautua menemään, jotta salaukseen voidaan luottaa.
%Tietysti tällaisissa projekteissa on mukana myös urheiluhenkeä samaan tapaan kuin vaikkapa $\pi$:n desimaalien laskennassa.










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Tähän liittyy hieman hienompaakin työkalua vaativa murto, mikäli lähetetään
%sama viesti samaa eksponenttia käyttäen useille vastaanottajille (vaikka 
%olisikin eri $n$). Nyt oikea Kiinalainen jäännöslause antaa helpon tavan
%koodin murtamiseen. Kts. tarkemmin [HandB] CH 8 s. 288.\\
%Nämä edustakoot esimerkkejä huomioon otettavista seikoista.
%[HandB] sisältää kahdeksan eri tyyppistä hyökkäysmahdollisuutta.

%Tämä havainnollistaa sitä matemaattista peliä, jota osapuolet käyvät
%keskenään toisen yrittäessä suojella salaisuutta ja toisen sitä murtaessa.

%Murtokoplaa kutsutaan hienosti kryptoanalyytikoiksi (anteeksi hyvät rehelliset
%analyytikot!). Menetelmien kehittäjien ja analyytikoiden/murtokoplan välinen
%kilpajuoksu on omiaan viemään kehitystä eteenpäin, vaikka helpompiakin
%tapoja (rehellinen, rauhantahtoinen ihmiskunta, helppoa!) 
%päästä tiedonvältyspäämääriin olisi periaatteesa olemasa.
%Nykymeno pitää ainakin matemaatikot mukavasti leivän syrjässä kiinni.






\subsection*{Tulevaisuuden näkymiä}


%Tietokoneiden prosessorien tehon kasvua arvioidaan ns. \emph{Mooren lailla},
%jonka mukaan laskentaresurssin hinta puolittuu n. $1 \frac{1}{2}$ vuodessa. Tämän 
%kehityksen mukaisesti voidaan arvioida, miten paljon avaimien pituutta tulee 
%lisätä, jotta salausmenetelmä olisi turvallinen.
%Vielä tärkeämpää, joskin vaikeampaa on ottaa huomioon uu laskentaparadigmat, kuten 
%edellä esiintynyt rinnakkaislaskenta ja aiemmin mainittu kvanttilaskenta ym.

Edellä nähtiin, että arviot avainten turvalliseen kokoon liittyvistä vaatimuksista tahtovat 
jäädä jälkeen siitä, minkä tänään oletetaan riittävän pitkälle tulevaisuuteen.
Tästä syystä ei voida pysähtyä lepäämään \rsa-laakereilla, vaan on välttämätöntä 
kehittää uusia "loukkuluukkuideoita".

%On myös selvää, että \rsa\/ ei ole tieteen viimeinen sana julkisen 
%salakirjoituksen menetelmien alalla. Monia muitakin tunnettuja 
%laskennallisesti 
%vaativia ongelmia voidaan valita "loukkuluukuiksi".

Kryptologiset menetelmät ovat laajentuneet abstraktia algebraa,
algebrallista geometriaa, elliptisiä käyriä, ym. kehittyneitä  moderneja matemaattisia teorioita käyttämään. 
Lisäksi determinististen menetelmien ohella on ryhdytty kehittämään myös 
todennäköisyyslaskentaan pohjautuvia satunnaisuuteen perustuvia menetelmiä.
%Uusien "loukkuluukkujen" kehittely ja analyysi jatkuu

%Kryptologian näkökulmasta katsottuna suuresti arvostetun matemaatikon \emph{Hardyn} vuonna 1940 kirjassaan [Hardy] antamat tulevaisuuden ennustukset
%koskien lukuteorian soveltamista (kuin myös suhteellisuusteoriaa) eivät olisi voineet
%pahemmin mennä pieleen.  

Kryptologiassa yhdistyvät kiehtovalla tavalla vuosituhansien aikana kehittyneet lukuteorian 
menetelmät uusien abstraktien matemaattisten teorioiden tarjoamiin mahdollisuuksiin.
Tärkeänä komponenttina on tietotekniikka teoreettisena työvälineenä, tehokkaan laskentavälineistön mahdollistajana,
ja tietysti syyn ja motiivin antajana koko toiminnalle tietoverkkojen, matkapuhelimien, sirukorttien maailmassa.



\subsubsection*{Viitteet}

%R: Rivest\\
%H: Halmetoja \\
%N: Norssi\\
%K: Kaisa

\begin{tehtratk}

\item[[I. Algo]] Cormen, Leiserson, Rivest: Kts. Osa 1
%\emph{Introduction to Algorithms}, The MIT Press, McGraw-Hill, 1998.

\item[[DH]]
W. Diffie, M. Hellman. New directions in cryptography, 
IEEE Transactions on Information Theory IT-22 (1976), 644-654.

\item[[HandB]] A. Menezes, P. van Oorschot, S. Vanstone.
Handbook of applied cryptography:
\href{http://www.cacr.math.uwaterloo.ca/hac/}
 {\texttt{http://www.cacr.math.uwaterloo.ca/hac/}}.   


\item[[CodeB]]
D. Kahn, The Codebreakers, Macmillan 1967, kirjasta on
uudempi painos.

\item[[Crt]]
Bernhard Esslinger.
Cryptography and Mathematics,
\href{http://www.cryptool.com/}
{\texttt{http://www.cryptool.com/}} .
Vapaan lähdekoodin ohjelmapaketti ja opetusteksti.

\item[[InCode]]
Sarah Flannery, David Flannery.
In Code: A Mathematical Journey. \\
Lukuteorian ja kryptologian periaatteiden yleistajuinen esitys 
nerokkaan irlantilaisen koulutytön ja isän kirjoittamana.
\href{http://www.amazon.com/}{\texttt{http://www.amazon.com/}}
[Hakusana In Code]
(Ehkä tästä joku koulutyttö tai poika voisi innostua vaikka 
kirjoittamaan kirja-arvion.)



\item[[Cos]]
John B. Cosgrave.
Bill Clinton, Bertie Ahern, and digital signatures
(A Maple-based introduction to public-key cryptography)
\href{http://staff.spd.dcu.ie/johnbcos/}
{\texttt{http://staff.spd.dcu.ie/johnbcos/}}
\linebreak
\href{Maple_public_other.htm}{\texttt{Maple\_public\_other.htm}}




\item[[Ke-Te]]
Veikko Keränen, Jouko Teeriaho. Salausmenetelmät, Rovaniemen AMK 2006: 
\href{http://ta.ramk.fi/~jouko.teeriaho/}
{\texttt{http://ta.ramk.fi/$\sim$jouko.teeriaho/}}
\linebreak
\href{krypto2006/krypto.htm}{\texttt{krypto2006/krypto.htm}}. 
%{\texttt{http://ta.ramk.fi/}$\sim$\texttt{jouko.teeriaho/krypto2006/krypto.htm}}\\
Kurssimateriaali, käyttää hyväkseen \mma-ohjelmaa.

%\href{www.abc.de/fgh/ijk}{\texttt{www.abc.de/}}
%\linebreak
%\href{www.abc.de/fgh/ijk}{\texttt{fgh/ijk/}}



\item[[Skk]]
Simo Kivelä.
\rsa-menetelmän \mma-toteutus.\\
\href{http://matta.hut.fi/matta2/mma/rsa.pdf}
{\texttt{http://matta.hut.fi/matta2/mma/rsa.pdf}}


\item[[Kob]] N. Koblitz. A Course in Number Theory and Cryptography, Springer 1994.
 
\item[[KN]] Kaisa Nyberg. Kryptologia -- tiedon turvaamisen tiede, Tietojenkäsittelytiede \textbf{26} 
kesäkuu 2007 ss. 31--52.


\item[[JP]] Jukka Pihko, Lukuteorian helmiä,
\href{http://solmu.math.helsinki.fi/2008/1/pihko.pdf}
{\texttt{solmu.math.helsinki.fi/2008/1/pihko.pdf}}


\item[[\rsa]]
R. Rivest, A. Shamir, L. Adelman. A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120-126. Luettavissa tästä:
\href{http://theory.lcs.mit.edu/~rivest/rsapaper.pdf}
{\texttt{theory.lcs.mit.edu/$\sim$rivest/rsapaper.pdf}}

\item[[AS]] Arto Salomaa. Public-Key Cryptography, Springer-Verlag, Berlin 1990.

\item[[Sti]]
D. R. Stinson.
Cryptography, Theory and Practice,
Chapman \& Hall/CRC Press, Boca Raton-London-New York,
Third Edition, 2006 \\
Kurssikirjaviitteenä Kaisa Nybergin (TKK) ja Keijo Ruohosen (TTY) opetussivuilla. (Kirjassa 353 viitettä.)


\item[[Wiki]] \href{http://en.wikipedia.org/wiki/}
{\texttt{http://en.wikipedia.org/wiki/}}
\\
Hakusanoja: \emph{Cryptography, History of cryptography, World\_War\_II\_cryptography, Enigma machine, Quantum Cryptography, RSA, RSA Factoring challenge, }


%\emph{}

\end{tehtratk}









\end{multicols}
%\end{document}
