Kryptologie/RSA-Signatur

Einleitung

Neben der Ver- und Entschlüsselung von Nachrichten, kann der RSA-Algorithmus auch genutzt werden, um Nachrichten zu "signieren". Dies kann man sich wie die handschriftliche Unterschrift auf einem Dokument vorstellen^[1]. Eine solche Signatur verfolgt zwei Sicherheitsziele: Authentizität und Verbindlichkeit^[1].

Bei der RSA-Signatur wird ein privater Schlüssel mittels eines Signaturalgorithmus auf einen Klartext $m$ angewendet und die signierte Nachricht kann mit dem öffentlichen Schlüssel

Authentizität, Verbindlichkeit und Vertraulichkeit
Authentizität
Der Empfänger einer Nachricht kann sich davon überzeugen, dass die erhaltene Nachricht von einem eindeutigen Sender stammt^[2].
Verbindlichkeit
Der Empfänger der Nachricht kann Dritten gegenüber nachweisen, dass die Nachricht von einem bestimmten Sender stammt^[3].
Vertraulichkeit
Höchstens Sender und Empfänger können den Inhalt des Klartextes einer übermittelten Nachricht verstehen^[1].

des Senders mittels eines Verifikationsalgorithmus verifiziert werden und gibt den Klartext $m$ aus. Die signierte Nachricht kann also von Dritten, die die Nachricht abfangen, gelesen werden, da der Verifikationsschlüssel öffentlich ist^[4]. Um Vertraulichkeit zu gewährleisten, muss man daher ein sicheres Verschlüsselungsverfahren, wie das RSA-Verschlüsselungsverfahren, auf die bereits signierte Nachricht angewendet werden^[4].

RSA-Signaturverfahren

Analog zu den drei Algorithmen des RSA-Algorithmus zur Verschlüsselung von Klartexten, besteht das digitales RSA-Signaturverfahren aus diesen drei Algorithmen. Nur die Notation und die Reihenfolge der Algorithmen müssen wir ändern^[4].

RSA-Algorithmus und Erweiterter euklidischer Algorithmus
RSA-Verschlüsselungsalgorithmus
Seien $m,c,e,d\in \mathbb {Z} /N\mathbb {Z}$ und der öffentliche Schlüssel $(e,N)$ und der private Schlüssel $(d,N)$ Schlüsselerzeugungsalgorithmus: identisch^[5] Verschlüsselungsalgorithmus: $c\equiv m^{e}{\bmod {N}}$ Entschlüsselungsalgorithmus: $m\equiv c^{d}{\bmod {N}}$ ^[6]^[4]
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen $a,b\in \mathbb {N}$ angewandt und besteht aus zwei Teilen: Berechnung des $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ (auch als euklidischer Algorithmus bekannt^[7]), Berechnung zweier ganzer Zahlen $s$ und $t$ , welche die Gleichung $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ erfüllen^[8].

Schlüsselerzeugungsalgorithmus,
- Wir wählen $p,q$ prim und bestimme $N=p\cdot q$ und $\varphi (N)$
- Wir wählen ein den Verifikationsexponenten $t$ mit $1<t<\varphi (N)$ mit $ggT(1,\varphi (N))=1$ und erhalten den öffentlichen Verifikationsschlüssel $(t,N)$
- Wir berechnen den privaten Signaturschlüssel $(s,N)$ mit dem Signierexponenten $s$ , indem wir das multiplikative Inverse von $t$ bezüglich $\varphi (N)$ mit dem erweiterten euklidischen Algorithmus berechnen
Signieralgorithmus,
- Wir signieren einen kodierten Klartext $m$ $m$ , indem wir diesen mit dem privaten Signierexponenten $s$ $s$ potenzieren und die signierte Botschaft $s$ $s$ erhalten,
  - $sig\equiv m^{s}{\bmod {N}}$
Verifikationsalgorithmus,
- Die signierte Nachricht können wir mit dem Verifikationsalgorithmus erneut in den Klartext $m$ $m$ umwandeln und die Authentizität und Verbindlichkeit verifizieren
  - $m\equiv sig^{t}{\bmod {N}}$ ^[4]

Bemerkung: Es gelten die identischen Anforderungen an den Klartext und die signierte Botschaft, wie beim RSA-Verschlüsselungsverfahren. Im Gegensatz zur RSA-Verschlüsselung signieren (bzw. "verschlüsseln") wir bei der RSA-Signatur der Klartext mit dem privaten, statt dem öffentlichen Schlüssel. Mit dem dem öffentlichen Schlüssel verifizierten(bzw. "entschlüsseln") wir eine signierte Nachricht^[4].

Authentizität und Verbindlichkeit garantiert das Verfahren, da der Empfänger nach der Verifikation über das Nachrichten-Signatur-Paar $(m,sig)$ verfügt. Dieses Nachrichten-Signatur-Paar $(m,sig)$ besitzt zwei wichtige Eigenschaften:

Der Klartext $m$ muss von einem bestimmten Sender stammen, da nur dieser Sender über den Signierexponenten $s$ verfügt, der $sig\equiv m^{s}{\bmod {N}}$ generiert und nur dessen Verifikationsschlüssel die signierte Nachricht verifiziert. Das Verfahren ist authentisch.
Der Empfänger kann Dritten gegenüber beweisen, dass sich die signierte Nachricht $sig$ mit dem öffentlichen Verifikationsschlüssel des bestimmten Senders verifizieren lässt. Das Verfahren ist verbindlich^[3].

Korrektheit der RSA-Signatur

Die vertauschte Verwendung der Schlüssel im Vergleich von RSA-Signatur- und RSA-Verschlüsselungsverfahren spielt wegen $(m^{e})^{d}\equiv m^{e\cdot d}\equiv (m^{d})^{e}\equiv m{\bmod {N}}$ nach Beweis der Korrektheit des RSA-Verschlüsselungsverfahrens keine Rolle für den Beweis der Korrektheit des RSA-Verschlüsselungsverfahrens und kann somit auf die Korrektheit des RSA-Signaturverfahrens angewandt werden. Der folgende Beweis unterscheidet sich also nur durch die Notation vom Beweis der Korrektheit des RSA-Verschlüsselungsverfahrens.

Beweis Korrektheit der RSA-Signatur
Voraussetzung Seien $p,q$ prim, $N=p\cdot q$ $m\in \mathbb {Z} /N\mathbb {Z}$ , $s\in (\mathbb {Z} /\varphi (N)\mathbb {Z} ,\odot )$ und $s\cdot t\equiv 1{\bmod {\varphi (N)}}$ Zu zeigen RSA-Algorithmus entschlüsselt korrekt, d.h. für alle $m\in \mathbb {Z} /N\mathbb {Z}$ gilt $sig^{t}\equiv (m^{s})^{t}\equiv m^{s\cdot t}\equiv (m^{t})^{s}\equiv m{\bmod {N}}$ Beweis Laut Voraussetzung gilt: $s\cdot t\equiv 1{\bmod {\varphi (N)}}$ $\Leftrightarrow s\cdot t\equiv 1{\bmod {\varphi (p\cdot q)}}$ , nach Voraussetzung $N=p\cdot q$ $\Leftrightarrow s\cdot t\equiv 1{\bmod {\varphi (p)\cdot \varphi (q)}}$ , wegen der Multiplikativität der $\varphi$ -Funktion $\Leftrightarrow s\cdot t\equiv 1{\bmod {(p-1)\cdot (q-1)}}$ , wegen Satz 2 Eigenschaft der $\varphi$ -Funktion bei Primzahlen $\Leftrightarrow s\cdot t=1+k\cdot (p-1)\cdot (q-1)\quad ()$ mit $k\in \mathbb {Z}$ und wegen der Definition der Kongruenz und Teilbarkeit. Wir unterscheiden zunächst zwei Fälle: $ggT(m,N)=1$ und $ggT(m,N)\neq 1$ . Fall 1:* Sei $ggT(m,N)=1$ : $(m^{s})^{t}{\bmod {N}}$ $\Leftrightarrow m^{st}{\bmod {N}}$ $\Leftrightarrow m^{1+\varphi (N)}{\bmod {N}}$ , nach $()$ mit $\varphi (N)=(p-1)\cdot (q-1)$ $\Leftrightarrow m\cdot m^{\varphi (N)}{\bmod {N}}$ $\Leftrightarrow m\cdot 1{\bmod {N}}$ , da nach dem Satz von Euler* gilt $m^{\varphi (N)}\equiv 1{\bmod {N}}$ $\Leftrightarrow m{\bmod {N}}$ . Wir müssen nun also nur noch den zweitem Fall betrachten. Fall 2: Sei $ggT(m,N)\neq 1$ . Wegen $N=p\cdot q$ gilt dann also entweder $ggT(m,N)=p$ oder $ggT(m,N)=q$ . Hier ist der Satz von Euler nicht anwendbar, wegen $ggT(m,N)\neq 1$ . Wenn wir jedoch trotzdem zeigen, dass $(m^{s})^{t}\equiv m{\bmod {p}}$ und $(m^{s})^{t}\equiv m{\bmod {q}}$ , dann können wir (wegen $ggT(p,q)=1$ ) den chinesischen Restsatz anwenden und erhalten: $(m^{s})^{t}\equiv m{\bmod {(}}p\cdot q)$ $\Leftrightarrow (m^{s})^{t}\equiv m{\bmod {N}}$ , wegen $N=p\cdot q$ . Wir zeigen dies nun für den Fall $ggT(m,N)=p$ , dass gilt: $(m^{s})^{t}\equiv m{\bmod {p}}$ und $(m^{s})^{t}\equiv m{\bmod {q}}$ . Sei $ggT(m,N)=p$ . Es gilt dann nach Definition der größten gemeinsamen Teilers $p\mid m$ bzw. nach Definition der Teilbarkeit $m=k\cdot p$ mit $k>0$ . Wir zeigen zunächst $(m^{s})^{t}\equiv m{\bmod {p}}$ für $ggT(m,N)=p$ Dann gilt nach Definition der Kongruenz aber auch $m\equiv 0{\bmod {p}}$ . Nun betrachten wir $(m^{s})^{t}{\bmod {p}}$ . $(m^{s})^{t}{\bmod {p}}$ $\Leftrightarrow ((k\cdot p)^{s})^{t}{\bmod {p}}$ $\Leftrightarrow 0{\bmod {p}}$ , da $((k\cdot p)^{s})^{t}$ ein Vielfaches von $p$ ist. Also gilt $(m^{s})^{t}\equiv 0{\bmod {p}}$ und insgesamt $m\equiv (m^{s})^{t}\equiv 0{\bmod {p}}$ . Nun bleibt noch zu zeigen, dass $(m^{s})^{t}\equiv m{\bmod {q}}$ für $ggT(m,N)=p$ . Da $ggT(m,q)=1$ , kann man den Satz von Euler anwenden. $(m^{s})^{t}{\bmod {q}}$ $\Leftrightarrow m^{st}{\bmod {q}}$ $\Leftrightarrow m^{st-1}\cdot m{\bmod {q}}$ $\Leftrightarrow m^{k\cdot (p-1)\cdot (q-1)}\cdot m{\bmod {q}}$ , nach $()$ : $s\cdot t-1=k\cdot (p-1)\cdot (q-1)$ (in umgestellter Form) $\Leftrightarrow m^{(q-1)\cdot k\cdot (p-1)}\cdot m{\bmod {q}}$ $\Leftrightarrow (m^{(q-1)})^{k\cdot (p-1)}\cdot m{\bmod {q}}$ $\Leftrightarrow (m^{\varphi (q)})^{k\cdot (p-1)}\cdot m{\bmod {q}}$ $\Leftrightarrow 1^{k\cdot (p-1)}\cdot m{\bmod {q}}$ , nach dem Satz von Euler* $\Leftrightarrow m{\bmod {q}}$ . Also gilt für $ggT(m,N)=p$ : $(m^{s})^{t}\equiv m{\bmod {q}}$ . Nun können wir den chinesischen Restsatz anwenden: $(m^{s})^{t}\equiv m{\bmod {(}}p\cdot q)$ $\Leftrightarrow (m^{s})^{t}\equiv m{\bmod {N}}$ , wegen $N=p\cdot q$ . Wir haben also nun gezeigt, dass das RSA-Verschlüsseungsverfahren für $ggT(m,N)=p$ korrekt ist. Dies können wir für $ggT(m,N)=q$ analog zeigen, indem wir in der Notation $p$ und $q$ vertauschen. Sie können dies freiwillig eigenständig durchführen. Damit haben wir die Korrektheit des RSA-Verschlüsseungsverfahrens für alle Fälle, nämlich $ggT(m,N)=1$ und $ggT(m,N)\neq 1$ , gezeigt■^[9]^[5]

Beispiel

Wir wollen den Klartext HALLO WELT. signieren.

Berechnung des privaten Signierschlüssels $(47,143)$
Sei $t=23$ und $\varphi (N)=120$ . Berechnung $\operatorname {ggT} (23,120)$ $120=5\cdot 23+5$ $23=4\cdot 5+3$ $5=1\cdot 3+2$ $3=1\cdot 2+1$ $2=2\cdot 1+0$ Es gilt $\operatorname {ggT} (23,120)=1$ . Berechnung der Faktoren $s$ und $k$ mit $\operatorname {ggT} (23,120)=s\cdot 23+k\cdot 120$ $3=1\cdot 2+1$ $\Leftrightarrow 1=3-1\cdot 2$ $\Leftrightarrow 1=3-1\cdot (5-1\cdot 3)$ , da $5=1\cdot 3+2\Leftrightarrow 5-1\cdot 3=2$ $\Leftrightarrow 1=2\cdot 3-5$ $\Leftrightarrow 1=2\cdot (23-4\cdot 5)-5$ , da $23=4\cdot 5+3\Leftrightarrow 23-4\cdot 5=3$ $\Leftrightarrow 1=2\cdot 23-9\cdot 5$ , da $-8\cdot 5-5=-9\cdot 5$ $\Leftrightarrow 1=2\cdot 23-9\cdot (120-5\cdot 23)$ , da $120=5\cdot 23+5\Leftrightarrow 120-4\cdot 23=5$ $\Leftrightarrow 1=2\cdot 23-9\cdot 120+45\cdot 23$ $\Leftrightarrow 1=47\cdot 23-9\cdot 120$ $\Rightarrow s=47$ und $k=-9$ Der private Signierschlüssel ist $(s,N)=(47,143)$

Wir übernehmen die Kodierung des Klartextes aus dem Beispiel zur Verschlüsselung mit dem RSA-Verschlüsselungsverfahren.

Sei also $m=m_{1}-m_{2}-\dots -m_{11}=72-65-76-76-7-90-87-69-76-84-46$ ^[10].

Schlüsselerzeugungsalgorithmus
- Der Schlüsselerzeugungsalgorithmus wurde bereits im Beispiel zur Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens besprochen und wir übernehmen die dort gewählten und Primzahlen und erhalten:
  - $p=11$ und $q=13$
  - $N=p\cdot q=143$
  - $\varphi (143)=120$
  - $t=23$ mit dem öffentlichen Verifikationsschlüssel $(23,143)$
  - $s=47$ mit dem privaten Signierschlüssel $(47,143)$ ^[10]
Signieralgorithmus
- Wir setzen den Signierexponenten $s=47$ und das RSA-Modul $N=143$ des privaten Schlüssels $(s,N)=(47,143)$ in den Signieralgorithmus $sig\equiv m^{s}{\bmod {N}}$ ein und erhalten $sig\equiv m^{47}{\bmod {1}}43$ .
- Nun wird jeder Block des Klartextes einzeln mit dem Signieralgorithmus $sig\equiv m^{47}{\bmod {1}}43$ $sig\equiv m^{47}{\bmod {1}}43$ signiert und man erhält
  - $sig_{1}\equiv 72^{47}\equiv 41{\bmod {1}}43$ , $sig_{2}\equiv 65^{47}\equiv 65{\bmod {1}}43$ , $sig_{3}\equiv 76^{47}\equiv 32{\bmod {1}}43$ , $\dots$ und $sig_{11}\equiv 46^{47}\equiv 106{\bmod {1}}43$
  - Man erhält die signierten Blöcke $41,65,32,32,28,51,120,75,32,50,106$ und den signierten Text $sig=41-65-32-32-28-51-120-75-32-50-106=416532322851120753250106$ .
Verifikationsalgorithmus
- Will nun der Empfänger der signierten Nachricht diese verifizieren, so wendet er unseren öffentlichen Verifikationsschlüssel $(23,143)$ auf den Verifikationsalgorithmus $m\equiv sig^{t}{\bmod {N}}$ an und erhält $m\equiv sig^{23}{\bmod {1}}43$ .
- Nun kann jeder signierte Block der signierten Nachricht einzeln verifiziert werden:
  - $m_{1}\equiv 72\equiv 41^{23}{\bmod {1}}43$ , $m_{2}\equiv 65\equiv 65^{23}{\bmod {1}}43$ , $m_{3}\equiv 76\equiv 32^{23}{\bmod {1}}43$ , $\dots$ und $m_{11}\equiv 46\equiv 106^{23}{\bmod {1}}43$
  - Man erhält die verifizierten Blöcke $72,65,76,76,7,90,87,69,76,84,46$ $72,65,76,76,7,90,87,69,76,84,46$ und somit den verifizierten und matheuatisierten Klartext $m=72-65-76-76-7-90-87-69-76-84-46=726576767908769768446$ $m=72-65-76-76-7-90-87-69-76-84-46=726576767908769768446$ .
    - Der Klartext kann nun durch die Dekodierung in seine ursprüngliche Form umgewandelt werden

Lernaufgabe

Aufgabe

Berechnen Sie Signatur und Verifikation der Elemente aus dem Beispiel zu hybriden Verschlüsselungsverfahren mit der RSA-Signatur.

$m_{1}=7$
$m_{2}=PUALYULA$

Wählen Sie entweder den privaten Schlüssel $(s,N)=(453,901)$ und den öffentlichen Schlüssel $(t,N)=(461,901)$ oder erzeugen Sie Ihre eigenen Schlüssel.

Benutzen Sie für $m_{2}$ die Zeichenkodierung $f_{CV}$ aus dem Beispiel zum Caesar-Verschlüsselungsverfahren (siehe Tabelle 1):

Tabelle 1: Zuordnung der Zeichenkodierung $f_{CV}$
Klartext (Definitionsmenge)	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Zugeordnete Zahl (Zielmenge)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Schlüsselerzeugung für

(s,N)=(453,901)

und

(t,N)=(461,901)

Schlüsselerzeugung für $s=453,t=461,N=901$

Wir wählen $p=53$ und $q=17$ .

Berechnung von $N=p\cdot q$ :

$N=53\cdot 17=901$ .

Berechnung von $\varphi (N)=(p-1)\cdot (q-1)$ :

$\varphi (N)=52\cdot 16=832$

Wahl des öffentlichen Schlüssels:

Wir wählen $t=461$ , da $ggT(461,832)=1$ und erhalten den öffentlichen Schlüssel $(461,901)$ .

Berechnung des privaten Schlüssels:

Wir berechnen das multiplikative Inverse $s$ zu $t$ mit dem erweiterten euklidischen Algorithmus:

Gleichung 1: $832=1\cdot 461+371$

Gleichung 2: $461=1\cdot 371+90$

Gleichung 3: $371=4\cdot 90+11$

Gleichung 4: $90=8\cdot 11+2$

Gleichung 5: $11=5\cdot 2+1$

Gleichung 6: $2=2\cdot 1+0$

Nun können wir die Gleichungen nutzen, um $s$ zu berechnen:

$11=5\cdot 2+1$

$\Leftrightarrow 1=-5\cdot 2+11$

$\Leftrightarrow 1=-5\cdot (90-8\cdot 11)+(371-4\cdot 90)$ , nach Gleichung 3 und 4

$\Leftrightarrow 1=-5\cdot 90+40\cdot 11+371-4\cdot 90$

$\Leftrightarrow 1=-5\cdot (461-371)+40\cdot (371-4\cdot 90)+371-4\cdot (461-371)$ , nach Gleichung 2 und 3

$\Leftrightarrow 1=-5\cdot 461+5\cdot 371+40\cdot 371-160\cdot 90+371-4\cdot 461+4\cdot 371$

$\Leftrightarrow 1=-5\cdot 461+5\cdot 371+40\cdot 371-160\cdot (461-371)+371-4\cdot 461+4\cdot 371$ , nach Gleichung 2

$\Leftrightarrow 1=-5\cdot 461+5\cdot 371+40\cdot 371-160\cdot 461+160\cdot 371+371-4\cdot 461+4\cdot 371$

$\Leftrightarrow 1=-169\cdot 461+210\cdot 371$

$\Leftrightarrow 1=-169\cdot 461+210\cdot (832-461)$ , nach Gleichung 1

$\Leftrightarrow 1=-169\cdot 461+210\cdot 832-210\cdot 461$

$\Leftrightarrow 1=-379\cdot 461+210\cdot 832$

Eigentlich gilt nun $s=-379$ . Wir haben jedoch das Problem, dass wir in unseren Verschlüsselungsalgorithmus der RSA-Signatur nur Standardrepräsentanten einsetzen können. Wir müssen also kleinste positive Zahl der Restklasse $[-379]_{832}$ wählen. Die einfachste Möglichkeit dieses Element zu berechnen ergibt sich aus $-379+832=453$ . Es gilt also $453\in [-379]_{832}$ und wir wählen $s=453$ . Der private Schlüssel ist daher $(453,901)$ .

Lösung

Lösung für $m_{1}=7$

Wir signieren $m=m_{1}=7$ mit dem Verschlüsselungsalgorithmus der RSA-Signatur $sig\equiv m^{s}{\bmod {N}}$ :

$sig\equiv 623\equiv 7^{453}{\bmod {9}}01$

$\Rightarrow sig=623$ .

Nun verifizieren wir die Signatur mit dem öffentlichen Schlüssel $(461,901)$ und dem Entschlüsselungsalgorithmus $m\equiv sig^{t}{\bmod {N}}$ der RSA-Signatur:

$m\equiv 7\equiv 623^{461}{\bmod {9}}01$

$\Rightarrow m=7$ .

Lösung für $m_{2}=PUALYULA$

Bevor wir $m_{2}=PUALYULA$ signieren können, müssen wir den Klartext in ein numerisches Alphabet übertragen.

Wir definieren unsere Definitions- und Zielmenge:

$\Sigma _{L}:=\{A,B,C,...,Z\}$ mit $\mid \Sigma _{L}\mid =26$

$\Sigma _{26}:=\{0,1,...,25\}$

und unseren Zeichenkodierung $f_{CV}$ :

$f_{CV}:\Sigma _{L}\rightarrow \Sigma _{26}$ mit $A\mapsto 0$ , $B\mapsto 1$ , ... $Z\mapsto 25$ (vgl. Tabelle 1).

Analog zum Beispiel der Caesar-Verschlüsselung erhalten wir

$f_{CV}(P)=15,f_{CV}(U)=20,f_{CV}(A)=0,f_{CV}(l)=11,f_{CV}(Y)=24,f_{CV}(U)=20,f_{CV}(L)=11,f_{CV}(A)=0$ .

Insgesamt erhalten wir den Klartext $m=15200112420110$ und signieren diesen mit dem privaten Schlüssel $(s,N)=(453,901)$ und dem Verschlüsselungsalgorithmus $sig\equiv m^{s}{\bmod {N}}$ der RSA-Signatur.

Zuvor müssen wir den Klartext jedoch noch in Blöcke kleiner $901$ unterteilen:

$m=15-200-112-420-110$ .

Nun kann der Klartext signiert werden.

$sig_{1}\equiv 155\equiv 15^{453}{\bmod {9}}01$

$sig_{2}\equiv 744\equiv 200^{453}{\bmod {9}}01$

$sig_{3}\equiv 736\equiv 112^{453}{\bmod {9}}01$

$sig_{4}\equiv 275\equiv 420^{453}{\bmod {9}}01$

$sig_{5}\equiv 43\equiv 110^{453}{\bmod {9}}01$

Die einzelnen Blöcke werden nun mit dem öffentlichen Schlüssel $(461,901)$ und dem Entschlüsselungsalgorithmus $m\equiv sig^{t}{\bmod {N}}$ der RSA-Signatur verifiziert:

$m_{1}\equiv 15\equiv 155^{461}{\bmod {9}}01$

$m_{2}\equiv 200\equiv 744^{461}{\bmod {9}}01$

$m_{3}\equiv 112\equiv 736^{461}{\bmod {9}}01$

$m_{4}\equiv 420\equiv 275^{461}{\bmod {9}}01$

$m_{5}\equiv 110\equiv 43^{461}{\bmod {9}}01$

und wir erhalten $m=15200112420110$ .

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
6: RSA-Kryptosystem
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
8: Korrektheit des RSA-Verschlüsselungsverfahrens	9: RSA-Signatur	10: Hybride Verschlüsselungsverfahren

Literatur

↑ ^1,0 ^1,1 ^1,2 Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 644.
↑ Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 645.
↑ ^3,0 ^3,1 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 121.
↑ ^4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. S.122.
↑ ^5,0 ^5,1 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 123.
↑ Seite „RSA-Kryptosystem“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 15. Dezember 2019, 19:39 UTC. URL: https://de.wikipedia.org/w/index.php?title=RSA-Kryptosystem&oldid=194933568 (Abgerufen: 10. Januar 2020, 10:40 UTC; Formulierung verändert)
↑ Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
↑ Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
↑ Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems. (16. Juni 2013). Wikibooks, Die freie Bibliothek. Abgerufen am 10. Januar 2020, 12:20 von https://de.wikibooks.org/w/index.php?title=Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems&oldid=674922. (Formulierung verändert)
↑ ^10,0 ^10,1 Kryptologie/Verschlüsselungsalgorithmus des RSA-Verfahrens. (10. Januar 2020). Wikiversity, . Abgerufen am 16. Januar 2020, 12:08 von https://de.wikiversity.org/w/index.php?title=Kryptologie/Verschl%C3%BCsselungsalgorithmus_des_RSA-Verfahrens&oldid=609331.

[:5-1] 1,0 ^1,1 ^1,2 Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 644.

[2] Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (S. 644–654). S. 645.

[:2-3] 3,0 ^3,1 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 121.

[:0-4] 4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. S.122.

[:3-5] 5,0 ^5,1 Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 123.

[:02-6] Seite „RSA-Kryptosystem“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 15. Dezember 2019, 19:39 UTC. URL: https://de.wikipedia.org/w/index.php?title=RSA-Kryptosystem&oldid=194933568 (Abgerufen: 10. Januar 2020, 10:40 UTC; Formulierung verändert)

[7] Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.

[8] Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.

[9] Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems. (16. Juni 2013). Wikibooks, Die freie Bibliothek. Abgerufen am 10. Januar 2020, 12:20 von https://de.wikibooks.org/w/index.php?title=Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems&oldid=674922. (Formulierung verändert)

[:1-10] 10,0 ^10,1 Kryptologie/Verschlüsselungsalgorithmus des RSA-Verfahrens. (10. Januar 2020). Wikiversity, . Abgerufen am 16. Januar 2020, 12:08 von https://de.wikiversity.org/w/index.php?title=Kryptologie/Verschl%C3%BCsselungsalgorithmus_des_RSA-Verfahrens&oldid=609331.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]