Das RSA-Ver­fah­ren

 

Ab­schlie­ßend wird als real be­nutz­tes Ver­fah­ren das RSA-Ver­fah­ren im Rah­men des Ar­beits­blat­tes Das RSA-Ver­fah­ren vor­ge­stellt.

Be­mer­kung: Im Zu­sam­men­hang mit dem RSA-Ver­fah­ren kann auch der Schlüs­sel­aus­tausch nach Dif­fie-Hell­man als ein wei­te­res Bei­spiel für ein asym­me­tri­sches Ver­fah­ren be­han­delt wer­den. Dies ist auch aus his­to­ri­scher Sicht in­ter­es­sant. Wenn dies im Rah­men der RSA-Ein­heit the­ma­ti­siert wer­den soll (was durch­aus sinn­voll ist), so kann hier das Ar­beits­blatt 02_i­ud_a­b_a­sym_R­SA aus der Ein­heit „In­for­ma­ti­ons­ge­sell­schaft und Da­ten­si­cher­heit (iud)“ ver­wen­det wer­den.

Eine Liste ver­füg­ba­rer Prim­zah­len, bei denen noch mit ge­rin­gen Hilf­mit­teln ge­rech­net wer­den kann, fin­det man im In­ter­net, z.B. bei Wal­ter Fendt; eben­so ASCII-Ta­bel­len der Buch­sta­ben und Zah­len.

Um die Kom­ple­xi­tät zu re­du­zie­ren, wird hier in die­sem Un­ter­richts­gang le­dig­lich der Kom­mu­ni­ka­ti­ons­weg A → B be­trach­tet, nicht die bei­der­sei­ti­ge Kom­mu­ni­ka­ti­on. Nach­dem der Un­ter­richts­gang bis hier ver­folgt wurde, kann die Er­wei­te­rung auf eine bei­der­sei­ti­ge Kom­mu­ni­ka­ti­on auf­ge­setzt wer­den.

Tie­fer­ge­hen­de Hin­ter­grund­in­for­ma­tio­nen zu grund­le­gen­den Fra­gen:

Wie si­cher ist RSA?

Um den Al­go­rith­mus an­wen­den zu kön­nen, muss der Be­nut­zer das Pro­dukt $(p-1)\cdot (q-1)$ ken­nen. Der öf­fent­li­che Schlüs­sel in­for­miert aber le­dig­lich über die Zahl $N$ (be­stimmt als $N=p\mathrm{·}q$ ) und nicht über die bei­den er­zeu­gen­den Prim­fak­to­ren $p$ und $q$ selbst. Diese müss­ten eben über Fak­to­ri­sie­rung her­aus­ge­fun­den wer­den, Stich­wort „Ein­weg­funk­ti­on“.

In der Pra­xis setzt man also $N$ aus so gro­ßen Prim­fak­to­ren zu­sam­men, dass die Zer­le­gung selbst mit leis­tungs­fä­hi­gen Com­pu­tern Jahre dau­ern würde (siehe Info in den Ar­beits­blät­tern).

Da das Pro­blem der Fak­to­ri­sie­rung prin­zi­pi­ell ge­löst wer­den kann, be­deu­tet das, dass RSA theo­re­tisch ge­se­hen nicht si­cher ist. Es dau­ert eben nach der­zei­ti­gem Stand der Tech­nik und Ma­the­ma­tik so lange, dass die In­for­ma­ti­on bis zum Zeit­punkt der Lö­sung nicht mehr re­le­vant ist (die­sen ge­ne­rel­len As­pekt von „Si­cher­heit“ lohnt es sich durch­aus, im Un­ter­richt zu the­ma­ti­sie­ren: Auch z.B. Tre­so­re wer­den mit einer Ga­ran­tie ver­kauft, wie lange sie un­be­fug­ten Öff­nungs­ver­su­chen wi­der­ste­hen kön­nen).

In die­ser Hin­sicht ist also RSA so­lan­ge si­cher, bis ein ent­spre­chend schnel­ler Al­go­rith­mus für die Prim­fak­tor­zer­le­gung ge­fun­den ist.

Das RSA-Ver­fah­ren durch­zu­füh­ren ist mit den be­spro­che­nen In­hal­ten nun pro­blem­los mög­lich. Schwie­ri­ger wird es je­doch, wenn man die Frage nach dem grund­le­gen­den ma­the­ma­ti­schen Fun­da­ment des RSA-Ver­fah­rens stellt: Warum funk­tio­niert RSA? Wel­che Zu­sam­men­hän­ge müs­sen dazu be­wie­sen wer­den? Hier­bei stößt man sehr schnell an die Gren­zen des­sen, was in der Schu­le mach­bar ist.

Hier als An­re­gung ei­ni­ge grund­le­gen­den Sätze und der Be­weis zur Kor­rekt­heit von RSA:

Grund­le­gen­de Sätze

1. Die Euler'sche $\phi$ -Funk­ti­on

   Ist $n$ eine na­tür­li­che Zahl, so gibt $\phi (n)$ die An­zahl der zu $n$ teiler­frem­den Zah­len an, die nicht grö­ßer als $n$ sind. Damit ist ins­be­son­de­re klar: Ist $p$ eine Prim­zahl, so ist $p$ teiler­fremd zu den Zah­len $1$ bis $p-1$. Daher gilt für Prim­zah­len $p: \phi (p)=p\mathrm{–}1$. Für teiler­frem­de Zah­len $m$ und $n$ gilt: $\phi (n)\cdot \phi (m)=\phi (n\cdot m)$. Daher gilt für Prim­zah­len $p$ und $q$: $\phi (p\cdot q)=\phi (p)\cdot \phi (q)=(p\mathrm{–}1)\cdot (q\mathrm{–}1)$. Be­wei­se zur Euler'schen $\phi$-Funk­ti­on sind sehr lang­wie­rig und in die­sem Zu­sam­men­hang nicht wei­ter­füh­rend. Des­halb sei hier für In­ter­es­sier­te auf die gän­gi­ge Fach­li­te­ra­tur ver­wie­sen.

2. Der Satz von Fer­mat-Euler und der klei­ne Satz des Fer­mat

   Satz von Fer­mat-Euler: Für $a,m\in \mathrm{\mathbb{N}}$ gilt: $\text{ggT}(a,m)=1\Rightarrow a^{\phi (m)}\equiv 1\text{ mod }m$

   Einen Spe­zi­al­fall davon stellt der klei­ne Fer­mat'sche Satz dar:

   Ist $p$ eine Prim­zahl und $a\in \mathrm{\mathbb{N}}$, gilt: $\text{ggT}(a,p)=1\Rightarrow a^{p-1}\equiv 1\text{ mod }p$.

   Bem.: Satz von Fer­mat-Euler für $m=p$, da $\phi (q)=(p\mathrm{–}1)$

   Der Be­weis des Sat­zes von Fer­mat-Euler geht über das in Klas­se 10 Mög­li­che hin­aus. Eine mög­li­che kom­bi­na­to­ri­sche Va­ri­an­te (als „Ket­ten­bas­teln“) kann evtl. für sehr in­ter­es­sier­te SuS the­ma­ti­siert wer­den. Diese und ei­ni­ge wei­te­re Be­weis­mög­lich­kei­ten fin­det man unter https://​de.​wi­ki­books.​org/​wiki/​Bew​eisa​rchi​v:_​Zah​lent​heor​ie:_​Ele­men­ta­re_​Zah​lent​heor​ie:_​Klei­ner_​Satz_​von_​Fer­mat

Der Be­weis: Warum funk­tio­niert RSA?

Die Be­wei­se zur theo­re­ti­schen Be­grün­dung der Kor­rekt­heit des RSA-Ver­fah­rens sind eben­falls oft auf­wän­dig und ma­the­ma­tisch in der Schu­le nicht durch­führ­bar. Hier je­doch eine mög­li­che Skiz­ze, die man (unter Aus­las­sung der Be­wei­se zur Euler'schen Funk­ti­on) schritt­wei­se nach­voll­zie­hen kann:

Die Bot­schaft B wird zum Ge­heim­text S ver­schlüs­selt durch Be­rech­nung von $B^e\text{ mod }N(=S)$. Die Ent­schlüs­se­lung wird vor­ge­nom­men durch $S^d\text{ mod }N(=B)$. Also gilt: $$S^d\text{ mod }N={(B^e\text{ mod }N)}^d\text{ mod }N=B^{ed}\text{ mod }N.$$

Dabei war $d$ das (mo­du­la­re) mul­ti­pli­ka­ti­ve In­ver­se zu $e$ be­züg­lich $\text{mod }(p\mathrm{–}1)\cdot (q\mathrm{–}1)$ und es gilt: $$(e\cdot d)\text{ mod }\phi (N)=1(\iff (e\cdot d)\text{ mod }\phi (p\cdot q)=(e\cdot d)\text{ mod }(p-1)\cdot (q-1)=1).$$

Mit $N=p\mathrm{·}q$ und $\phi (p\mathrm{·}q)=(p-1)\mathrm{·}(q-1)$ gilt die die Be­zie­hung: $$e\mathrm{·}d=k\mathrm{·}\phi (N)+1=k\mathrm{·}\phi (p\mathrm{·}q)+1=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1$$ und somit: $$e\mathrm{·}d\text{ mod }\phi (N)=(k\mathrm{·}(p-1)\mathrm{·}(q-1)+1)\text{ mod }\phi (N).$$

Wir er­in­nern uns: Der ent­schlüs­sel­te Ge­heim­text war: $$S^d\text{ mod }N={(B^e)}^d=B^{ed}\text{ mod }N.$$

Wenn RSA funk­tio­nie­ren soll, muss also gel­ten: $$B^{ed}\text{ mod }N=B.$$ Mit der obi­gen Be­zie­hung: $$e\mathrm{·}d=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1$$ muss also gel­ten: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }N=B.$$

Zu­sam­men­fas­send die zu be­wei­sen­de zen­tra­le Aus­sa­ge (Kor­rekt­heit von RSA):

Es seien $p,q$ ver­schie­de­ne Prim­zah­len und $B\in \mathrm{\mathbb{N}}\text{ mit }B<p\mathrm{·}q.$ Dann gilt für jede Zahl $k\in \mathrm{\mathbb{N}}:B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }pq=B.$

Be­weis¹: Zu­nächst ge­trennt nach den Prim­zah­len $p$ und $q$ (1), (2), dann Zu­sam­men­füh­rung (3):

1. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B$
2. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }q=B$
3. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }pq=B$

Zu:

1. Mit den ele­men­ta­re Po­tenz­re­gel $a^{n+m}=a^n\cdot a^m$ und ${\left(a^m\right)}^n=a^{mn}$ folgt:$$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}=B\mathrm{·}{B}^{k\mathrm{·}(p-1)\mathrm{·}(q-1)}=B\mathrm{·}{\left(B^{(p-1)}\right)}^{k(q-1)}.$$

   Mit den Re­geln für mo­du­la­res Po­ten­zie­ren, dem klei­nen Fer­mat'schen Satz $\text{ggT}(p,B)=1\Rightarrow B^{p-1}\equiv 1\text{ mod }p$ sowie $\text{ggT}(p,B)=1$ , da $p$ Prim­zahl und ist, folgt: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B\mathrm{·}{\left(B^{p-1}\right)}^{k\mathrm{·}(q-1)}\text{ mod }p=B\mathrm{·}{\left(B^{p-1}\text{ mod }p\right)}^{k\mathrm{·}(q-1)}\text{ mod }p$$ $$=B\mathrm{·}{(1\text{ mod }p)}^{k\mathrm{·}(q-1)}\text{ mod }p=B\mathrm{·}{1}^{k\mathrm{·}(q-1)}\text{ mod }p=B\text{ mod }p.$$

   Zu­sam­men­fas­send: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B\text{ mod }p.$$

2. Für $q$ ana­log, le­dig­lich mit an­de­rer Sor­tie­rung im Ex­po­nen­ten.

   Zu­sam­men­fas­send: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }q=B\text{ mod }q.$$

3. $N=pq$: Hier­zu füh­ren wir der Über­sicht­lich­keit hal­ber ein $h:=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1.$

   In den bei­den in (1) und (2) er­hal­te­nen Glei­chun­gen $B^h\text{ mod }p=B\text{ mod }p$ und $B^h\text{ mod }q=B\text{ mod }q$ brin­gen wir je­weils $B$ auf die an­de­re Seite und er­hal­ten: $$B^h\text{ mod }p\mathrm{–}B\text{ mod }p=0$$ und $$B^h\text{ mod }q\mathrm{–}B\text{ mod }q=0.$$

   Mit An­wen­dung der Regel über mo­du­la­re Ad­di­ti­on folgt: $$(B^h-B)\text{ mod }p=0$$ und $$(B^h-B)\text{ mod }q=0.$$ So­wohl $p$ als auch $q$ tei­len also $B^h-B.$

   $p$ und $q$ sind je­doch ver­schie­de­ne Prim­zah­len, also muss $(p\mathrm{·}q)$ die Zahl $B^h-B$ tei­len.

   Mit den Re­chen­re­gel für mo­du­la­res Ad­die­ren und gilt damit: $$(B^h\mathrm{–}B)\text{ mod }(p\mathrm{·}q)=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)\mathrm{–}B\text{ mod }(p\mathrm{·}q)=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)\mathrm{–}B=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)=B\mathrm{■}$$

Die ein­zel­nen Schrit­te sind so mit den im Ver­lauf des Un­ter­richts be­wie­se­nen Ge­set­zen be­grün­det nach­voll­zieh­bar. Al­ler­dings bleibt der Be­weis auf­wän­dig.

 

¹ An­ge­lehnt an http://​www.​ma­the­ma­tik-​netz.​de/​pdf/​RSA.​pdf.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][244 KB]

Un­ter­richts­ver­lauf: Her­un­ter­la­den [pdf][615 KB]

 

Wei­ter zu Ko­pier­vor­la­gen