RSA-titkosítás: 3. lépés

2000 évvel ezelőtt Euklidész bebizonyította, hogy minden számnak pontosan egy prímtényezős felbontása van, amit tekinthetünk egy titkos kulcsnak. Az is tény, hogy a prímtényezőkre bontás alapvetően egy bonyolult probléma. Határozzuk meg, mit tekintünk „könnyűnek” illetve „nehéznek”. Vezessük be az „időbonyolultság” függvényét! Mindannyian tudunk számokat szorozni, és vannak trükkjeink, amivel fel tudjuk gyorsítani a számítást. Ha szorzáshoz készítünk egy számítógépes programot, az az embernél sokkal gyorsabb lesz. Ez a grafikon megmutatja, hogy mennyi idő kell a számítógépnek két szám összeszorzásához. Természetesen ahogy a számok mérete nő, úgy nő a számításhoz szükséges idő is. Figyeld meg, hogy a számítási idő jóval egy másodperc alatt marad még egész nagy számok esetében is. Erre azt mondjuk, hogy azt „könnyű” végrehajtani. Hasonlítsuk ezt a prímtényezős felbontáshoz! Ha meg kell találnod az 589 prímtényezőit, ez érezhetően nehezebb feladat. Függetlenül az alkalmazott stratégiától, próbálgatásra van szükség, amíg meg nem találod azt a számot, ami egyenletesen osztja el az 589-et. Egy kis küzdelem után eljutsz oda, hogy a prímtényezős felbontás 19-szer 31. Ha a feladat 437 231 prím osztóinak megtalálása, valószínűleg feladod, és számítógépet hívsz segítségül. Ez kis számok esetében működik, de ha olyan gépet keresünk, ami egyre nagyobb számok faktorizációjára képes, exponenciális a növekedés. A számítások elvégzéséhez szükséges idő gyorsan növekszik a szükséges lépések számának növekedésével. Ahogy nőnek a számok, a számítógépnek percekre, majd órákra, végül száz, vagy több ezer évre van szüksége nagy számok faktorizációjához. Erre azt mondjuk, hogy ez egy „nehéz” probléma a megoldáshoz szükséges idő növekedési üteme miatt. Ezért Cocs a faktorizációra alapozta a csapóajtó kialakítását. Első lépésként Alíz generál egy több, mint 150 számjegyből álló prímszámot: legyen ez „p1”. Azután vesz egy másik, körülbelül ugyanolyan hosszú prímet, nevezzük „p2”-nek. Ezután ezt a két prímszámot összeszorozza, így megkapja az N összetett számot, ami több, mint 300 számjegyből áll. Ez a szorzás egy másodpercnél rövidebb idő alatt megvan; akár egy web böngészőben is elvégezhető. Ezután az N felbontását, p1-et és p2-t elrejti. Ha bárkinek odaadja N-et, az évekig futtathatja a számítógépen, amíg megkapja a megoldást. Második lépésként Cocksnak találnia kellett egy függvényt, ami az N prímtényezős felbontásától függ. Ehhez visszanyúlt Leonhard Euler svájci matematikus 1760-as munkájához.