RSA Standard - Revision history

Ckrause: /* Quellen */

2007-07-24T12:55:42Z

Quellen

← Older revision		Revision as of 12:55, 24 July 2007
Line 121:		Line 121:
	== Quellen ==		== Quellen ==

	[http://sar.informatik.hu-berlin.de/teaching/2007-s%20Security%20Engineering%20(SE)/readings/pkcs-1v2-12.pdf PKCS#1 v2.1 RSA Cryptography Standard]		*[http://sar.informatik.hu-berlin.de/teaching/2007-s%20Security%20Engineering%20(SE)/readings/pkcs-1v2-12.pdf PKCS#1 v2.1 RSA Cryptography Standard]
		⚫	*[http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]

			*Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie. Von RSA zu Zero-Knowledge, 2006
⚫	[http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]
			*Spektrum der Wissenschaft, Extras-Ausgabe: Kryptographie, 2001

Ckrause: /* Schlüsselerzeugung */

2007-07-24T12:40:41Z

Schlüsselerzeugung

← Older revision		Revision as of 12:40, 24 July 2007
Line 16:		Line 16:

	== Schlüsselerzeugung ==		== Schlüsselerzeugung ==
	Als ~~Asymmetrisches~~ Verfahren nutzt RSA ein Schlüsselpaar, bestehend aus einem öffentlich zugänglichen Schlüssel und dem dazu gehörigen geheimen privaten Schlüssel. Üblicherweise erzeugt ein Pseudo-Zufallsgenerator mindestens 2 sehr große Primzahlen, mit deren Hilfe dann die Schlüssel berechnet werden.		Als asymmetrisches Verfahren nutzt RSA ein Schlüsselpaar, bestehend aus einem öffentlich zugänglichen Schlüssel und dem dazu gehörigen geheimen privaten Schlüssel. Üblicherweise erzeugt ein Pseudo-Zufallsgenerator mindestens 2 sehr große Primzahlen, mit deren Hilfe dann die Schlüssel berechnet werden.

	Der öffentliche Schlüssel besteht aus 2 Komponenten:		Der öffentliche Schlüssel besteht aus 2 Komponenten:

	n RSA modulus, mit n ~~element von~~ N+		*n   RSA modulus, mit <math>n \in N^+ </math>
	e RSA öffentlicher Exponent, mit e ~~element von~~ N+		*e   RSA öffentlicher Exponent, mit <math> e \in N^+ </math>

	n ist das Produkt von u verschiedenen ~~geheim gehaltenen~~ [Primzahlen] ri, so das gilt:		n ist das Produkt von u verschiedenen geheimen [http://de.wikipedia.org/wiki/Primzahl Primzahlen] r<sub>i</sub>, so das gilt:

	n=~~Prod(ri)~~, ri =1,2..u für u>=2		<math> n=\prod_i^u r_i,\ r_i=1,2 \cdots u</math> für <math>u \ge 2 </math>

	e ist eine ganze Zahl im Bereich 3<=e<=n-1 und es muss gelten:		e ist eine ganze Zahl im Bereich <math>3 \le e \le n-1</math> und es muss gelten:

	[http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler ggT](e,lambda(n))=1 mit lambda(n)=[http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler kgv](r1-1,..,ru-1)		[http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler ggT]<math>(e,\lambda(n))=1\ mit\ \lambda(n)=</math>[http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler kgv]<math>(r_1-1,\cdots,r_u-1)</math>


Line 39:		Line 39:
	Die Erste besteht wieder aus 2 Komponenten:		Die Erste besteht wieder aus 2 Komponenten:

	n RSA modulus, mit n ~~element von~~ N+		*n   RSA modulus, mit <math>n \in N^+ </math>
	d RSA privater Exponent, mit d ~~element von~~ N+		*d   RSA privater Exponent, mit <math> d \in N^+ </math>

	Der private Exponent d wird aus den zuvor gewählten geheimen Primzahlen berechnet, so das gilt:		Der private Exponent d wird aus den zuvor gewählten geheimen Primzahlen berechnet, so das gilt:

	e*d ~~mod~~ lambda(n)=1		<math> e*d\ \bmod\ \lambda(n)=1</math>

	Die zweite Darstellung verwendet ein Quintuple (p,q,dP,dQ,qInv) sowie eine Sequenz aus Triplets (ri,di,ti) i=3..u für jede weitere Primzahl. Weiterhin soll gelten:		Die zweite Darstellung verwendet ein Quintuple <math>(p,q,dP,dQ,qInv)\ </math> sowie eine Sequenz aus Triplets <math>(r_i,d_i,t_i) i=3\dots u </math> für jede weitere Primzahl. Weiterhin soll gelten:

	edP ~~mod~~ (p-1)=1 edi ~~mod~~ (ri-1)=1		<math> edP\ \bmod\ (p-1)=1,\ ed_i\ \bmod\ (r_i-1)=1 </math>
	edQ mod (q-1)=1 Riti mod ri =1 mit Ri=r1r2ri-1
	q*dInv mod p=1

			<math> edQ\ \bmod\ (q-1)=1,\ R_it_i\ \bmod\ r_i=1\ mit\ R_i=r_1r_2\cdots*r_{i-1} </math>
	Mit Hilfe des [http://de.wikipedia.org/wiki/Chinesischer_Restsatz Chinesischen Restsatzes] kann die Berechnung bei 3 oder mehr Primfaktoren optimiert werden.

			<math> q*qInv\ \bmod\ p=1</math>

	== Signieren & Verifizierung ==		== Signieren & Verifizierung ==

Ckrause: /* Signieren & Verifizierung */

2007-07-24T12:01:54Z

Signieren & Verifizierung

← Older revision		Revision as of 12:01, 24 July 2007
Line 55:		Line 55:

	== Signieren & Verifizierung ==		== Signieren & Verifizierung ==
	Beim Signieren mit RSA nutzt der Absender seinen eigenen privaten RSA-Schlüssel K, um aus der Nachricht m eine Signatur s zu erzeugen. Zuerst wird die Nachricht m dabei in ein String aus ganzen Zahlen umgewandelt. Bei Signaturen wird meist noch zusätzlich ein Hashwert über die gesamte Nachricht gebildet, da eine Rekonstruktion der Nachricht nicht erforderlich ist. Es soll nur die Authentizität der Nachricht sicher gestellt sein.		Beim Signieren mit RSA nutzt der Absender seinen eigenen privaten RSA-Schlüssel ''K'', um aus der Nachricht ''m'' eine Signatur ''s'' zu erzeugen. Zuerst wird die Nachricht m dabei in ein String aus ganzen Zahlen umgewandelt. Bei Signaturen wird meist noch zusätzlich ein Hashwert über die gesamte Nachricht gebildet, da eine Rekonstruktion der Nachricht nicht erforderlich ist. Es soll nur die Authentizität der Nachricht sicher gestellt sein.
	Für die Nachricht m muss in jedem Fall die Eigenschaft 0<=m<=n-1 erfüllt sein, sonst wäre eine Dechiffrierung mit dem öffentlichen Schlüssel nicht möglich.		Für die Nachricht ''m'' muss in jedem Fall die Eigenschaft <math>0\le m \le n-1</math> erfüllt sein, sonst wäre eine Dechiffrierung mit dem öffentlichen Schlüssel nicht möglich.

	Bei nur 2 Primfaktoren und dem Schlüssel K=(n,d) gilt:		Bei nur 2 Primfaktoren und dem Schlüssel <math>K\ =(n,d)</math> gilt:

	s=m^d ~~mod~~ n		<math>s = m^d\ \bmod n</math>

	Für beliebig viele Primfaktoren und K = (p,q,dP,dQ,qInv)(ri,di,ti) i=3..u kann folgender Algorithmus verwendet werden:		Für beliebig viele Primfaktoren und <math>K=(p, q, dP, dQ, qInv),(r_i, d_i, t_i)\ mit\ i=3\cdots u</math> kann folgender Algorithmus verwendet werden:

	# s1=m^dP mod p und s2=m^dQ mod q
			# <math> s_1=m^dP\ \bmod p\ und\ s_2=m^dQ\ \bmod q </math>
	# Wenn u>2, si=m^di mod ri
			# <math> Wenn\ u>2, s_i=m^{d_i}\ \bmod r_i </math>
	# h=(s1-s2)*qInv mod p
			# <math> h=(s_1-s_2)*qInv\ \bmod p </math>
	# s=s2+q*h
			# <math> s=s_2+q*h\ </math>
	# Wenn u>2, R=r1 und for i=3..u do		# <math> Wenn\ u>2, R=r_1\ und\ for\ i=3 \cdots u\ do </math>
	R=R*ri-1
			##<math> R=R*r_{i-1}\ </math>
	h=(si-s)ti mod ri
			##<math> h=(s_i-s)t_i\ \bmod r_i </math>
	s=s+R*h
			##<math> s=s+R*h\ </math>

		⚫	Für die Verifizierung der Signatur nutzt der Empfänger den öffentlichen Schlüssel des Absenders <math>K\ =(n,e)</math>. Es wird einfach die Umkehroperation auf die Signatur s ausgeführt, um die Nachricht m wieder herzustellen.

			<math> m = s^e\ \bmod n</math>

⚫	Für die Verifizierung der Signatur nutzt der Empfänger den öffentlichen Schlüssel des Absenders K= (n,e). Es wird einfach die Umkehroperation auf die Signatur s ausgeführt, um die Nachricht m wieder herzustellen.

	m = s^e mod n

	Zur Veranschaulichung ist hier nochmal der ganze Ablauf für 2 Primfaktoren p und q dargestellt.		Zur Veranschaulichung ist hier nochmal der ganze Ablauf für 2 Primfaktoren p und q dargestellt.

Ckrause: /* Sicherheit von RSA */

2007-07-24T11:01:43Z

Sicherheit von RSA

← Older revision		Revision as of 11:01, 24 July 2007
Line 109:		Line 109:

	Die Sicherheit von RSA basiert auf 2 mathematischen Problemen. Zum einen ist das die Faktorisierung, also das zerlegen sehr großer Zahlen in ihre Primfaktoren. Zum anderen		Die Sicherheit von RSA basiert auf 2 mathematischen Problemen. Zum einen ist das die Faktorisierung, also das zerlegen sehr großer Zahlen in ihre Primfaktoren. Zum anderen
	besteht das Problem, die e^th Wurzel modulo n zu finden. Bis jetzt ist kein Algorithmus bekannt, der diese Probleme in polynomialer Zeit lösen könnte.		besteht das Problem, die e<sup>th</sup> Wurzel modulo n zu finden. Bis jetzt ist kein Algorithmus bekannt, der diese Probleme in polynomialer Zeit lösen könnte.
	2005 gelang es, eine 663bit große Zahl in ihre Primfaktoren zu zerlegen. Hierfür war jedoch ein erheblicher Aufwand und Zeit nötig, der in keiner Relation zu den gängigen Zeiten steht, die ein bestimmter RSA-Schlüssel gültig ist. Auch wenn die Entwicklung immer schnellerer Rechner abzusehen ist, dürfte die Faktorisierung auch weiterhin ein Problem sein. Nicht zuletzt besteht immer die Möglichkeit, die Schlüssellängen weiter zu erhöhen, so das eine Lösung für den Dauer der geplanten Verwendung eines bestimmten Schlüssels auszuschließen ist.		2005 gelang es, eine 663bit große Zahl in ihre Primfaktoren zu zerlegen. Hierfür war jedoch ein erheblicher Aufwand und Zeit nötig, der in keiner Relation zu den gängigen Zeiten steht, die ein bestimmter RSA-Schlüssel gültig ist. Auch wenn die Entwicklung immer schnellerer Rechner abzusehen ist, dürfte die Faktorisierung auch weiterhin ein Problem sein. Nicht zuletzt besteht immer die Möglichkeit, die Schlüssellängen weiter zu erhöhen, so das eine Lösung für den Dauer der geplanten Verwendung eines bestimmten Schlüssels auszuschließen ist.
	Was neue Algorithmen oder technische Entwicklungen (z.b. Quantencomputing) betrifft, bestehen hier mittel- und langfristig gewisse Risiken.		Was neue Algorithmen oder technische Entwicklungen (z.b. Quantencomputing) betrifft, bestehen hier mittel- und langfristig gewisse Risiken.

Ckrause: /* Allgemein */

2007-07-24T10:59:36Z

Allgemein

← Older revision		Revision as of 10:59, 24 July 2007
Line 1:		Line 1:
	== Allgemein ==		== Allgemein ==

	Der RSA-Standard gehört zur Gruppe der [http://de.wikipedia.org/wiki/Asymmetrisches_Kryptosystem asymmetrischen Kryptographie-Verfahren], d.h. es gibt 2 ~~[[#~~Schlüssel]]		Der RSA-Standard gehört zur Gruppe der [http://de.wikipedia.org/wiki/Asymmetrisches_Kryptosystem asymmetrischen Kryptographie-Verfahren], d.h. es gibt 2 Schlüssel
	um einen Datensatz zu verschlüsseln bzw. einen chiffrierten Text zu entschlüsseln.		um einen Datensatz zu verschlüsseln bzw. einen chiffrierten Text zu entschlüsseln.
	Man unterscheidet hierbei den ~~[[#~~öffentlichen Schüssel]] und den ~~[[#~~privaten Schlüssel]].		Man unterscheidet hierbei den öffentlichen Schüssel und den privaten Schlüssel.
	Die Schlüssel sind mathematisch so konstruiert, das sie jeweils die Umkehroperation des anderen darstellen.		Die Schlüssel sind mathematisch so konstruiert, das sie jeweils die Umkehroperation des anderen darstellen.
	Aus diesem Grund eignet sich das RSA-Verfahren sowohl für das Verschlüsseln von Daten als auch das [http://de.wikipedia.org/wiki/Digitale_Signatur digitale Signieren].		Aus diesem Grund eignet sich das RSA-Verfahren sowohl für das Verschlüsseln von Daten als auch das [http://de.wikipedia.org/wiki/Digitale_Signatur digitale Signieren].
	RSA ist ein deterministisches Verfahren, d.h. gleiche Eingaben erzeugen stets gleiche Ausgaben. Aufgrund dieser Eigenschaft,		RSA ist ein deterministisches Verfahren, d.h. gleiche Eingaben erzeugen stets gleiche Ausgaben. Aufgrund dieser Eigenschaft,
	zusammen mit Problemen bei sehr kurzen Nachrichten oder kleinen Exponenten, wird RSA in der Praxis durch weitere		zusammen mit Problemen bei sehr kurzen Nachrichten oder kleinen Exponenten, wird RSA in der Praxis durch weitere
	~~[[#~~Schemata]] ergänzt.		Schemata ergänzt.

	== Geschichte ==		== Geschichte ==

Ckrause: /* Schemata für Signaturen */

2007-07-24T10:58:00Z

Schemata für Signaturen

← Older revision		Revision as of 10:58, 24 July 2007
Line 82:		Line 82:
	== Schemata für Signaturen==		== Schemata für Signaturen==

	Durch die Einfachheit der grundlegenden mathematischen Operation ist RSA allein nur bedingt anwendbar. Zu klein gewählte Exponenten oder Nachrichtenlängen könnten die Modulo-Operation negieren. Die e^th Wurzel zu berechnen würde in dem Fall schon eine Lösung bedeuten. Auch ist das rein deterministische Verhalten ein möglicher Angriffspunkt. In der Praxis wird RSA deshalb mit weiteren Algorithmen, sgn. Signaturenschemata kombiniert.		Durch die Einfachheit der grundlegenden mathematischen Operation ist RSA allein nur bedingt anwendbar. Zu klein gewählte Exponenten oder Nachrichtenlängen könnten die Modulo-Operation negieren. Die e<sup>th</sup> Wurzel zu berechnen würde in dem Fall schon eine Lösung bedeuten. Auch ist das rein deterministische Verhalten ein möglicher Angriffspunkt. In der Praxis wird RSA deshalb mit weiteren Algorithmen, sgn. Signaturenschemata kombiniert.
	Diese erzeugen mit Hilfe von z.B. Hashfunktionen und Zufallselementen aus den Nachrichten Zeichenketten passender Größe, welche dann mit RSA signiert werden können.		Diese erzeugen mit Hilfe von z.B. Hashfunktionen und Zufallselementen aus den Nachrichten Zeichenketten passender Größe, welche dann mit RSA signiert werden können.

	Ein rein deterministischen Ansatz stellt das EMSA-PKCS1-v1_5 Schema dar. Er eignet sich für sehr große Nachrichten, je nach gewählter Hashfunktion z.B. SHA-1: 2^64-1 bits.		Ein rein deterministischen Ansatz stellt das ''EMSA-PKCS1-v1_5 Schema'' dar. Er eignet sich für sehr große Nachrichten, je nach gewählter Hashfunktion z.B. SHA-1: 2<sup>64</sup>-1 bits.
	Die Signatur wird nicht direkt aus der zu signierenden Nachricht M erzeugt. Es wird erst eine Encoded Message EM generiert (siehe Abbildung), welcher die ursprüngliche Nachricht nur noch als Hashwert enthält.		Die Signatur wird nicht direkt aus der zu signierenden Nachricht M erzeugt. Es wird erst eine Encoded Message EM generiert (siehe Abbildung), welcher die ursprüngliche Nachricht nur noch als Hashwert enthält.

	<bild>
			[[Image:EMSA-PKCS1-v1_5.jpg\|EMSA-PKCS Schema]]
⚫	DER steht für ~~Distinguished~~ ~~Encoding~~ ~~Rules~~, ein je nach Implementierung festgelegtes Informationsset, welches die verwendete Hashfunktion und andere Informationen enthält.

		⚫	'''DER''' steht für '''D'''istinguished '''E'''ncoding '''R'''ules, ein je nach Implementierung festgelegtes Informationsset, welches die verwendete Hashfunktion und andere Informationen enthält.
	Um die Nachricht verifizieren zu können, wird neben dem obligatorischen öffentlichen Schlüssel auch die Nachricht selbst benötigt, da hier keine Nachrichtenrekonstruktion möglich ist.		Um die Nachricht verifizieren zu können, wird neben dem obligatorischen öffentlichen Schlüssel auch die Nachricht selbst benötigt, da hier keine Nachrichtenrekonstruktion möglich ist.
	Zuerst wird aus der Signatur die EM berechnet. Mit Hilfe der bekannten Nachricht M und der bekannten Hashfunktion wird eine neuer Encoded Message EM´ erzeugt und anschließend mit EM verglichen. Bei gültiger Signatur sollten beide gleich sein.		Zuerst wird aus der Signatur die EM berechnet. Mit Hilfe der bekannten Nachricht M und der bekannten Hashfunktion wird eine neuer Encoded Message EM´ erzeugt und anschließend mit EM verglichen. Bei gültiger Signatur sollten beide gleich sein.


⚫	Das EMSA_PSS Schema nutzt eine Zufallskomponente bei der Erstellung der EM für zusätzliche Sicherheit. Erst wird wieder ein Hashwert aus der Nachricht M erzeugt. Kombiniert mit einem Zufallswert (salt) wird ein zweites Mal ein Hashwert H berechnet, welcher dann den

		⚫	Das ''EMSA_PSS Schema'' nutzt eine Zufallskomponente bei der Erstellung der EM für zusätzliche Sicherheit. Erst wird wieder ein Hashwert aus der Nachricht M erzeugt. Kombiniert mit einem Zufallswert (salt) wird ein zweites Mal ein Hashwert H berechnet, welcher dann den
	ersten Teil des EM bildet. Der Zufallswert selbst wird mit Hilfe einer sgn. Mask Generation Function MGF und dem zweiten Hashwert H		ersten Teil des EM bildet. Der Zufallswert selbst wird mit Hilfe einer sgn. Mask Generation Function MGF und dem zweiten Hashwert H
	verschlüsselt.(Abbildung)		verschlüsselt.(Abbildung)

	<Bild>
			[[Image:EMSA-PSS Encoding.jpg\| EMSA-PSS Encoding]]

	Bei der Verifikation wird zuerst mit Hilfe der rekonstruierten EM der Zufallswert (salt) zurück gerechnet. Anschließend wird wie beim Signieren ein Hashwert H´ berechnet und mit H verglichen. Auch hier ist für die Verifikation die unverschlüsselte Nachricht nötig.		Bei der Verifikation wird zuerst mit Hilfe der rekonstruierten EM der Zufallswert (salt) zurück gerechnet. Anschließend wird wie beim Signieren ein Hashwert H´ berechnet und mit H verglichen. Auch hier ist für die Verifikation die unverschlüsselte Nachricht nötig.

			[[Image:EMSA-PSS Verify.jpg\| EMSA-PSS Verify]]

	== Sicherheit von RSA ==		== Sicherheit von RSA ==

Ckrause: /* Signieren & Verifizierung */

2007-07-24T10:45:37Z

Signieren & Verifizierung

← Older revision		Revision as of 10:45, 24 July 2007
Line 77:		Line 77:

	Zur Veranschaulichung ist hier nochmal der ganze Ablauf für 2 Primfaktoren p und q dargestellt.		Zur Veranschaulichung ist hier nochmal der ganze Ablauf für 2 Primfaktoren p und q dargestellt.
	<Bild>

			[[Image:RSA Example Komplett.jpg\| RSA Signaturerzeugung & Verfifizierung, Beispiel]]

	== Schemata für Signaturen==		== Schemata für Signaturen==

Ckrause: /* Quellen */

2007-07-24T10:29:57Z

Quellen

← Older revision		Revision as of 10:29, 24 July 2007
Line 112:		Line 112:
	== Quellen ==		== Quellen ==

	[~~ftp~~://~~ftp~~.~~rsasecurity~~.~~com~~/~~pub~~/~~pkcs/pkcs~~-1/pkcs-1v2-1.pdf PKCS#1 v2.1 RSA Cryptography Standard]		[http://sar.informatik.hu-berlin.de/teaching/2007-s%20Security%20Engineering%20(SE)/readings/pkcs-1v2-12.pdf PKCS#1 v2.1 RSA Cryptography Standard]

	[http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]		[http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]

Ckrause: /* Quellen */

2007-07-24T10:29:15Z

Quellen

← Older revision		Revision as of 10:29, 24 July 2007
Line 112:		Line 112:
	== Quellen ==		== Quellen ==

	[~~http://~~ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf PKCS#1 v2.1 RSA Cryptography Standard]		[ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf PKCS#1 v2.1 RSA Cryptography Standard]

	[~~http://~~http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]		[http://en.wikipedia.org/wiki/RSA Wikipedia:RSA ]

Ckrause: /* Sicherheit von RSA */

2007-07-24T10:28:59Z

Sicherheit von RSA

← Older revision		Revision as of 10:28, 24 July 2007
Line 108:		Line 108:

	Allerdings haben diverse Angriffe in der Vergangenheit gezeigt, das eine Dechiffrierung auch ohne Wissen der Primfaktoren möglich ist.		Allerdings haben diverse Angriffe in der Vergangenheit gezeigt, das eine Dechiffrierung auch ohne Wissen der Primfaktoren möglich ist.
	RSA zeigt eine gewisse Verwundbarkeit gegenüber [~~http://~~http://en.wikipedia.org/wiki/Chosen-ciphertext_attack Chosen ciphertext attacks]. Dabei werden gefälschte chiffrierte Nachrichten generiert . Durch Analyse der entschlüsselten Fälschungen wird versucht, Informationen über den verwendeten Schlüssel zu gewinnen.		RSA zeigt eine gewisse Verwundbarkeit gegenüber [http://en.wikipedia.org/wiki/Chosen-ciphertext_attack Chosen ciphertext attacks]. Dabei werden gefälschte chiffrierte Nachrichten generiert . Durch Analyse der entschlüsselten Fälschungen wird versucht, Informationen über den verwendeten Schlüssel zu gewinnen.

	== Quellen ==		== Quellen ==