[list=1][*]p, q Primfaktoren im CAS festlegen[/*][*]e auswählen → Slider grün → phi, e teilerfremd) -[color=#0000ff] public key[/color] [br][/*][*]Extended Euklid einstellen → n[sub]d[/sub] Slider grün → Iterationstiefe OK bei ExtGDC([color=#ff0000]0[/color]) - [color=#0000ff]private key[/color][br][/*][*]Alternative Berechnung d: Suchtiefe [color=#0000ff]k[/color] n[sub]d[/sub] (ggf. erhöhen von [color=#0000ff]k[/color] [sub](10)[/sub], wenn kein d gefunden wird)[/*][*]Im CAS stößt man nicht so schnell an ein Zahlenlimit (10000 Stellen siehe Bild unten). Den ExtGCD zur Berechnung der Modulo-Inversen (zu e) hab ich trotzdem in der AlgebraView versteckt - er benötigt 3 Arrays und würde die Übersichtlichkeit im CAS stören. [br][/*][*]Berechnung ExtGCD in einer Matrix, weicht jedoch von dem bekannten a,b,q,r,x,y Muster ab.[i][br]Iextgcd=[/i][size=85][i]IterationList({ Element(X, 2), Element(X, 1)-floor(Element(X, 1)/Element(X, 2)) Element(X, 2) , Element(X, 5), Element(X, 6), Element(X, 3)-floor(Element(X, 1)/Element(X, 2))*Element(X, 5), Element(X, 4)-floor(Element(X, 1)/Element(X, 2))*Element(X, 6) } ,X, {{a,b,1,0,0,1}}, nn)[br][/i][size=100]Mit nn Iterationstiefe angeben - Ergebnis in letzter Zeile Spalte 1,3,4! (siehe Aufgabe 2)[/size][/size][/*][/list] [br][size=150]Binäre Exponentiation[/size][br][br]EXTMOD(a,b,m) → a[sup]b[/sup] mod m [b]"große" Exponenten modulo n[/b] [b]"schnell"[/b] berechnen - [color=#0000ff]CAS function[/color][br][br][i]Beispiel[/i]:[br][br][math]\large 31^{99}\, mod\, 101[/math][br][br][i]wandel des Exponenten in eine [/i][b][i]Binärzahl [/i][br][/b][br][math]99_{(10)}=1100011_{(2)}[/math][br][br][math]\large \begin{array}{rr} 31^{2^0}= 31^{1} = 31 \equiv \textcolor{red}{31} \; mod\; 101&1\\[br]31^{2^1} = \textcolor{red}{31}^2 = 961\equiv \, \textcolor{red}{52}\; mod\; 101&1\\[br]31^{2^2} = 31^4=\textcolor{red}{52}^2=2704\equiv \textcolor{red}{78}\; mod\; 101&0\\[br]31^{2^3} = 31^8=\textcolor{red}{78}^2= 6084\equiv \textcolor{red}{24}\; mod\; 101&0\\[br]31^{2^4} =31^{16}=\textcolor{red}{24}^2=576\equiv \textcolor{red}{71}\; mod\; 101&0\\[br]31^{2^5} = 31^{32}=\textcolor{red}{71}^2=5041\equiv \textcolor{red}{92}\; mod\; 101&1\\[br]31^{2^6} = 31^{64}=\textcolor{red}{92}^2= 8464\equiv \textcolor{red}{81}\; mod\; 101&1\\\end{array}[br][/math][br][br][i]Alle Stellen-Werte an der die Binärzahl 1 steht miteinander multiplizieren. [/i][br][i] [b]Binärzahl die Länge 7[/b]. Führen auf insgesamt [b]"nur" 7 Zwischenrechnungen[/b] [/i](Rekursion)[br][math] 31^{99}\, mod\, 101 \to 31^{1100011_{2}}\, mod\, 101 \to b_i=b_{i-1}^2\, mod\, 101 \to \prod_{bit=1}^{11001_2} b_{i}\, mod\, 101 \to b_i \, = \, \left(\begin{array}{rr}6&81\\5&92\\4&71\\3&24\\2&78\\1&52\\0&31\\\end{array}\right) [/math][br][math]31\cdot 52\cdot 92\cdot 81 = 12012624 \equiv 88\; mod\; 101 \to[/math] [i]Mod(Mod([b]81 92[/b],101) Mod([b]52 31[/b],101),101)[/i])[br][br][math]31 \cdot 88 \equiv 1\; mod\; 101[/math][sub]modinv if mod prim[/sub] [br][br]Trick: einen öffentlichen Schlüssel e wählen mit möglichst wenigen 1 Bits![br][i]Beispiel App . mögliche Schlüssel e=31 (11111[sub]2[/sub]) oder e=37 (100101[sub]2[/sub])[/i][br]

e encrypt - d decrypt - N msg[br][br][math]\large \left(N^{e}\right)^{d}=N [/math][br][math]\large[br]e d \equiv 1 \quad(\bmod \varphi(n))[br][/math][br][br]Es gibt also ein [math] k \in \mathbb{Z} [/math] mit:[br][br][math]\large[br]e d=1+k \varphi(n)=1+k(p-1)(q-1)=1+k^{\prime}(p-1)[br][/math][br][br]Fall 1: [math]\large p \nmid N . \ln \mathbb{Z}_{p} [/math] gilt [math] N^{p-1}=1 [/math] (Fermat) und:[br][br][math]\large[br]N^{e d}=N^{1+k^{\prime}(p-1)}=N \cdot\left(N^{p-1}\right)^{k^{\prime}}=N \cdot 1^{k^{\prime}}=N[br][/math][br][br]Fall 2: [math]\large p \mid N [/math], also [math] N=0 [/math] in [math]\large \mathbb{Z}_{p} [/math] und damit natürlich auch [math]\large N^{e d}=N [/math].[br][br]Wir haben somit [math] p \mid N^{e d}-N [/math] und ebenso [math] q \mid N^{e d}-N [/math].[br][br]Da [math] p [/math] und [math] q [/math] teilerfremd sind, folgt [math] p q \mid N^{e d}-N [/math].[br][br]entnommen [url=https://www.youtube.com/watch?v=mDRMzBlI3U4]E.Weitz Das RSA-Kryptosystem[math]\nearrow[/math][/url][br]