{ "cells": [ { "cell_type": "markdown", "id": "legislative-architecture", "metadata": {}, "source": [ "# Az RSA algoritmus\n", "Az RSA-t 1977-ben publikálta Ronald Rivest, Adi Shamir és Leonard Adleman és családi neveik kezdőbetűiből lett az RSA betűszó. Algoritmusuk elemi számelméleti ötleten alapszik.\n", "\n", "Legyenek $p$ és $q$ különböző prímszámok, azaz olyan természetes számok, amelyeknek 1-en és önmagukon kívül nincs más osztójuk. Az ókori görög matematikus Eukleidész Elemek című könyvében szerepel annak bizonyítása, hogy végtelen sok prímszám létezik. A XIX. sz. vége óta azt is tudjuk, hogy a prímszámok elég gyakoriak. Annak a valószínűsége ugyanis, hogy egy véletlenszerűen kiválasztott $x$-nél kisebb szám prímszám legyen $1/\\ln x.$ Léteznek hatékony eljárások, amelyekkel gyorsan eldönthető, hogy egy szám prímszám-e. (Például 2002-ben Manindra Agrawal, Neeraj Kayal és Nitin Saxena indiai informatikusok publikáltak egy polinom idejű determinisztikus prímszámtesztet, amelynek hatékonysága azonban ma még nem vetekedik néhány klasszikus, megismert prímteszttel.)\n", "\n", "Nagy prímszámokat tehát könnyű találni, de ha két ilyet összeszorzunk, akkor csak a szorzatot ismerve nagyon nehéz a tényezőket megtalálni. Ezt a faktorizáció problémájának nevezik, ami tudásunk szerint egy nagyon nehéz algoritmikus probléma.\n", "\n", "Legyenek $p$ és $q$ különböző prímszámok és $n=qp.$ Ekkor az $n$-nél kisebb, $n$-hez relatív prím természetes számok száma $\\varphi(n) = (p-1)(q-1).$ Ezt az értéket $p$ és $q$ ismeretében könnyű kiszámítani. A $\\varphi$ függvényt Euler függvénynek nevezzük. Legyen most $e$ egy olyan $\\varphi(n)$-hez relatív prím természetes szám, amelyik kisebb $\\varphi(n)$-nél. Akkor pontosan egy olyan $1\\leq d<\\varphi(n)$ természetes szám létezik, amelyre $ed \\pmod{\\varphi(n)} = 1.$ Itt és a továbbiakban $a \\mod m$ jelenti az $a$ természetes szám maradékát $m$-mel osztva. Ezek után a nyilvános kulcs az $e,n$ számpáros, a titkos kulcs pedig a $d$ szám. A kulcsok meghatározása után a $p$ és $q$ értékét is titokban kell tartani vagy ezeket a számokat meg kell semmisíteni.\n", "\n", "A kódolás során az üzenetet először számok sorozatává alakítjuk olyan módon, hogy a számok mindegyike kisebb legyen, mint $n.$ Ez könnyen megtehető, hiszen az üzenetet a számítógépben bináris alakban tároljuk és most ezt a bináris sorozatot, mint egy kettes számrendszerben megadott szám számjegyeit értelmezzük. Ezután az egyes $m$ számokat az\n", "\n", "$$M \\equiv m^e \\pmod{n}$$\n", "\n", "képlettel kódoljuk előállítva a rejtjelezett $M$ üzenetet. A kódoláshoz csak a nyilvános kulcsot, az $e,n$ számpárt kell ismerni! A titkos $M$ üzenetet az\n", "\n", "$$m \\equiv M^d \\pmod{n}$$\n", "\n", "képlet alapján lehet dekódolni. A visszafejtéshez tehát a titkos $d$ kulcs ismerete kell!\n", "\n", "A kódolás és dekódolás során is moduláris hatványozást kell végezni, amelyik az „intelligens” hatványozó algoritmussal elfogadható gyorsasággal elvégezhető. Az elemi számelméletből jól ismert Euler-Fermat tételből következik, hogy a dekódolás után tényleg az eredeti üzenetdarabot kapjuk vissza." ] }, { "cell_type": "code", "execution_count": 1, "id": "floral-prime", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5021, 2111)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = next_prime(5012)\n", "q = next_prime(2105)\n", "p,q" ] }, { "cell_type": "code", "execution_count": 2, "id": "after-reporter", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10599331" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n=p*q\n", "n" ] }, { "cell_type": "code", "execution_count": 3, "id": "olive-influence", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10592200" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "phi = (p - 1)*(q - 1); phi" ] }, { "cell_type": "code", "execution_count": 4, "id": "silent-style", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10274509" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "e = ZZ.random_element(phi)\n", "while gcd(e, phi) != 1:\n", " e = ZZ.random_element(phi)\n", "e" ] }, { "cell_type": "code", "execution_count": 5, "id": "cordless-observer", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9556989" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d=mod(1/e,phi)\n", "Integers()(d)" ] }, { "cell_type": "code", "execution_count": 6, "id": "restricted-seattle", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "941736102496657601220878515855693" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "uzenet='Ma szerda van.'\n", "s = IntegerRing()([ord(k) for k in uzenet],base=256)\n", "s" ] }, { "cell_type": "code", "execution_count": 7, "id": "incoming-hands", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "77" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ord('M')" ] }, { "cell_type": "code", "execution_count": 8, "id": "sufficient-solid", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'d'" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chr(100)" ] }, { "cell_type": "code", "execution_count": 9, "id": "applicable-debut", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[248778, 4243364, 4335398, 1636980, 74613]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "SL=s.digits(base=n)\n", "SL" ] }, { "cell_type": "code", "execution_count": 10, "id": "expired-latin", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[9580974, 8025203, 7892885, 5901611, 690683]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kod=[power_mod(t, e, n) for t in SL]\n", "kod" ] }, { "cell_type": "code", "execution_count": 11, "id": "thorough-commitment", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[248778, 4243364, 4335398, 1636980, 74613]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dekod=[power_mod(t, Integers()(d), n) for t in kod]\n", "dekod" ] }, { "cell_type": "code", "execution_count": 12, "id": "rapid-bruce", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "941736102496657601220878515855693" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dekod1=IntegerRing()(dekod,base=n)\n", "dekod1" ] }, { "cell_type": "code", "execution_count": 13, "id": "assigned-leave", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['M', 'a', ' ', 's', 'z', 'e', 'r', 'd', 'a', ' ', 'v', 'a', 'n', '.']\n" ] }, { "data": { "text/plain": [ "'Ma szerda van.'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "v=[chr(t) for t in dekod1.digits(base=256)]\n", "print(v)\n", "''.join(v)" ] }, { "cell_type": "markdown", "id": "raising-moment", "metadata": {}, "source": [ "# Pell-egyenletek\n", "Legyen $d$ egy egész, amely nem teljes négyzet. Ekkor az $$x^2-dy^2=\\pm 1$$ diofantikus egyenletet Pell-egyenletnek nevezzük. Az egyenlet megoldásai szoros összefüggésben állnak a $\\sqrt{d}$ valós szám lánctört alakjával, pontosabban az abból származó úgynevezett konvergensekkel. Például, ha $d=2$, akkor $\\sqrt{d}$ első néhány konvergense a következő:\n", "$$1, \\frac{3}{2}, \\frac{7}{5}, \\frac{17}{12}, \\frac{41}{29}, \\frac{99}{70}, \\frac{239}{169}, \\frac{577}{408}.$$\n", "Amennyiben $x,y$ egy egész megoldás, akkor $x$ egy ilyen konvergens számlálója, $y$ pedig a nevezője. A fenti konvergensek esetében a következő értékeket kapjuk:\n", "$$-1,1,-1,1,-1,1,-1,1,$$\n", "tehát például \n", "$$3^2-2\\cdot 2^2=1$$\n", "és \n", "$$7^2-2\\cdot 5^2=-1.$$\n", "\n", "Az alábbi Sage kód adott pozitív, nem teljes négyzet $d$ érték esetén megkeresi a legkisebb $x,y$ megoldását az $$x^2-dy^2=1$$ Pell-egyenletnek. A táblázatban láthatóak adott $n$ értékhez tartozó konvergensek számlálói: $r_n$ és nevezői: $s_n$. Például $d=2013$ esetében azt látjuk, hogy a legkisebb megoldás: $$(x,y)=(152409599,3396960).$$" ] }, { "cell_type": "code", "execution_count": 1, "id": "brazilian-membrane", "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "22541de28f41496e930ccec5ffdf9f9d", "version_major": 2, "version_minor": 0 }, "text/plain": [ "Interactive function with 1 widget\n", " d: IntSlider(value=73, description='d', max=219, min=-73)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "@interact\n", "def _(d=('d',73)):\n", " k=0\n", " a,b=continued_fraction_list(sqrt(d), partial_convergents=True,nterms=k+1)\n", " while b[k][0]^2-d*b[k][1]^2!=1:\n", " k=k+1\n", " a,b=continued_fraction_list(sqrt(d), partial_convergents=True,nterms=k+1)\n", " OT=table([(x,b[x][0],b[x][1],b[x][0]^2-d*b[x][1]^2) for x in [0..k]], header_row = [\"$n$\", \"$r_n$\",\"$s_n$\",\"$r_n^2-ds_n^2$\"])\n", " pretty_print(OT)\n", " pretty_print(html(r'
'))\n", " pretty_print(html(r'Pell-egyenlet: $x^2-%s\\cdot y^2=1$'%latex(d)))\n", " pretty_print(html(r'
'))\n", " pretty_print(html(r'Egy megoldás: $(x,y)=%s$'%latex((b[k][0],b[k][1]))))" ] }, { "cell_type": "markdown", "id": "operational-newport", "metadata": {}, "source": [ "# Feladatok\n", "- RSA titkosítás: $(n,e)=(28011001,1234567).$ A titkosítva elküldendő szöveg: \"Kovetkezo heten lesz a ZH\",\n", "adjuk meg a kódolt üzenetet!\n", "- RSA titkosítás: $(p,q,d)=(333337, 555557, 181574449529),$ a következő kódolt üzenetet kapjuk:\n", "$[126626463509, 33108301030, 55567890018, 8975427251, 18545968187].$ Mi a dekódolt üzenet?\n", "- Lánctörtek segítségével határozzuk meg két különböző egész megoldását az $x^2-19y^2=1$ Pell-egyenletnek.\n", "- Lánctörtek segítségével határozzuk meg két különböző $(x_1,y_1),(x_2,y_2)\\in\\mathbb{N}^2$ megoldását az $x^2-37y^2=1$ Pell-egyenletnek, amelyekre $x_1,x_2$ prímszámok!\n", "- Egy utcában keresünk egy házat a következő információk alapján: az utcában legalább 200 és legfeljebb 500 ház áll, melyek számozása 1-től kezdődik és egyesével növekszik; továbbá az utca elejétől a keresett házig vett házszámok összege megegyezik a keresett háztól az utca végéig vett házszámok összegével." ] }, { "cell_type": "code", "execution_count": null, "id": "civic-photography", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.6", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.11" } }, "nbformat": 4, "nbformat_minor": 5 }