Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Frage zu RSA-Verschlüsselung
46 views
Skip to first unread message
Gottfried Helms
Jul 25, 2012, 5:52:36 PM7/25/12
to
Wir hatten k�rzlich eine Diskussion �ber RSA-Verschl�sselung.
Viel mehr, als da� die Schwierigkeit des Code-Knackens
darin besteht, die Faktoren eines Primzahl-Produkts g=p*q,
wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
von 10^50 oder 10^100 oder so, zu finden, wei� ich gar nicht.
Nach meinem (zugegebenerma�en primitiven) Verst�ndnis besteht
die (theoretische) Schwierigkeit
a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
Zahlen
b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
finden, die p*q = g definieren.
Die aktuelle softwarem��ige Implementierung von RSA scheint mir
nun solche Primzahlen kennen zu m�ssen.
Mein Anteil der Diskussion ging nun dahin, da� wenn die Primzahlen p
und q in praxi lediglich aus bekannten Listen stammen (die viel
weniger Eintr�ge enthalten als Primzahlen in dem interessierenden
Bereich vorhanden sind) ist Problem b) nat�rlich viel leichter
zu l�sen, wenn dem "Angreifer" solche Listen bekannt sind, da er
dann g simpel durch trial-und-error mit der Abarbeitung der
Liste faktorisieren kann,
Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
mi�verstanden?
fragt -
Gottfried
Viel mehr, als da� die Schwierigkeit des Code-Knackens
darin besteht, die Faktoren eines Primzahl-Produkts g=p*q,
wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
von 10^50 oder 10^100 oder so, zu finden, wei� ich gar nicht.
Nach meinem (zugegebenerma�en primitiven) Verst�ndnis besteht
die (theoretische) Schwierigkeit
a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
Zahlen
b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
finden, die p*q = g definieren.
Die aktuelle softwarem��ige Implementierung von RSA scheint mir
nun solche Primzahlen kennen zu m�ssen.
Mein Anteil der Diskussion ging nun dahin, da� wenn die Primzahlen p
und q in praxi lediglich aus bekannten Listen stammen (die viel
weniger Eintr�ge enthalten als Primzahlen in dem interessierenden
Bereich vorhanden sind) ist Problem b) nat�rlich viel leichter
zu l�sen, wenn dem "Angreifer" solche Listen bekannt sind, da er
dann g simpel durch trial-und-error mit der Abarbeitung der
Liste faktorisieren kann,
Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
mi�verstanden?
fragt -
Gottfried
Robert Figura
Jul 25, 2012, 8:35:13 PM7/25/12
to
Gottfried Helms <he...@uni-kassel.de> schrieb:
> Wir hatten kürzlich eine Diskussion über RSA-Verschlüsselung.
[...]
> Nach meinem (zugegebenermaßen primitiven) Verständnis besteht
> nun solche Primzahlen kennen zu müssen.
>
> Mein Anteil der Diskussion ging nun dahin, daß wenn die Primzahlen p
Primzahlen heuristisch, etwa mit hilfe des kleinen Fermat, generiert.
So weit ich weiß ist das genug (bzw das Risiko ist skalierbar).
http://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_.C3.B6ffentlichen_und_privaten_Schl.C3.BCssels
> weniger Einträge enthalten als Primzahlen in dem interessierenden
> Bereich vorhanden sind) ist Problem b) natürlich viel leichter
> zu lösen, wenn dem "Angreifer" solche Listen bekannt sind, da er
Grüße
- Robert Figura
--
/* mandlsig.c 0.42 (c) by Robert Figura */
I=1702;float O,o,i;main(l){for(;I--;putchar("oO .,\nt>neo.ckgel-t\
agidif@<ra urig FrtbeRo"[I%74?I>837&874>I?I^833:l%5:5]))for(O=o=l=
0;O*O+o*o<(16^l++);o=2*O*o+I/74/11.-1,O=i)i=O*O-o*o+I%74*.04-2.2;}
> Wir hatten kürzlich eine Diskussion über RSA-Verschlüsselung.
[...]
> Nach meinem (zugegebenermaßen primitiven) Verständnis besteht
> die (theoretische) Schwierigkeit
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
>
> Die aktuelle softwaremäßige Implementierung von RSA scheint mir
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
>
> nun solche Primzahlen kennen zu müssen.
>
> Mein Anteil der Diskussion ging nun dahin, daß wenn die Primzahlen p
> und q in praxi lediglich aus bekannten Listen stammen (die viel
Wenn ich mich recht erinnere werden in der RSA Implementation diese
Primzahlen heuristisch, etwa mit hilfe des kleinen Fermat, generiert.
So weit ich weiß ist das genug (bzw das Risiko ist skalierbar).
http://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_.C3.B6ffentlichen_und_privaten_Schl.C3.BCssels
> weniger Einträge enthalten als Primzahlen in dem interessierenden
> Bereich vorhanden sind) ist Problem b) natürlich viel leichter
> zu lösen, wenn dem "Angreifer" solche Listen bekannt sind, da er
> dann g simpel durch trial-und-error mit der Abarbeitung der
> Liste faktorisieren kann,
>
> Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
> mißverstanden?
> Liste faktorisieren kann,
>
> Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
Grüße
- Robert Figura
--
/* mandlsig.c 0.42 (c) by Robert Figura */
I=1702;float O,o,i;main(l){for(;I--;putchar("oO .,\nt>neo.ckgel-t\
agidif@<ra urig FrtbeRo"[I%74?I>837&874>I?I^833:l%5:5]))for(O=o=l=
0;O*O+o*o<(16^l++);o=2*O*o+I/74/11.-1,O=i)i=O*O-o*o+I%74*.04-2.2;}
Christian Gollwitzer
Jul 26, 2012, 2:49:24 AM7/26/12
to
Am 25.07.12 23:52, schrieb Gottfried Helms:
>
> Nach meinem (zugegebenermaßen primitiven) Verständnis besteht
paar Zahlen finden, die mit großer Wahrscheinlichkeit prim sind. Das
macht sogar Wolframalpha in Sekundenbruchteilen:
http://www.wolframalpha.com/input/?i=nextprime%281e50%29
Anschließend kann man mit dem AKS-Test die Primalität sogar beweisen, um
sicher zu gehen. AKS ist zwar aufwendiger, als ein paar mal
a^(n-1) mod n =? 1
zu berechnen, jedoch liefert es als nachgeschobenes Verfahren einen
Beweis. Dass umgekehrt die Faktorisierung viel schwieriger ist, liegt
daran, dass es eben nochmal exponentiell (in der Anzahl der Stellen)
aufwendig, alle möglichen Faktoren durchzugehen, während die
Primzahltests polynomiell in der Anzahl der Stellen zu haben sind. Man
muss lediglich darauf achten, dass p-q ebenfalls keine kleine Zahl ist,
sonst kann man mit dem Fermatschen Faktorisierungsalgorithmus das
Produkt zerlegen. Bei den üblichen Schlüssellängen reicht es aber
durchaus, p in der Nähe von 2*q zu suchen.
Christian
> Wir hatten kürzlich eine Diskussion über RSA-Verschlüsselung.
> Viel mehr, als daß die Schwierigkeit des Code-Knackens
> darin besteht, die Faktoren eines Primzahl-Produkts g=p*q,
> wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
> von 10^50 oder 10^100 oder so, zu finden, weiß ich gar nicht.
> wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
>
> Nach meinem (zugegebenermaßen primitiven) Verständnis besteht
> die (theoretische) Schwierigkeit
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
Wie Robert schon schrieb, kann man leicht mit dem kleinen Fermat ein
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
paar Zahlen finden, die mit großer Wahrscheinlichkeit prim sind. Das
macht sogar Wolframalpha in Sekundenbruchteilen:
http://www.wolframalpha.com/input/?i=nextprime%281e50%29
Anschließend kann man mit dem AKS-Test die Primalität sogar beweisen, um
sicher zu gehen. AKS ist zwar aufwendiger, als ein paar mal
a^(n-1) mod n =? 1
zu berechnen, jedoch liefert es als nachgeschobenes Verfahren einen
Beweis. Dass umgekehrt die Faktorisierung viel schwieriger ist, liegt
daran, dass es eben nochmal exponentiell (in der Anzahl der Stellen)
aufwendig, alle möglichen Faktoren durchzugehen, während die
Primzahltests polynomiell in der Anzahl der Stellen zu haben sind. Man
muss lediglich darauf achten, dass p-q ebenfalls keine kleine Zahl ist,
sonst kann man mit dem Fermatschen Faktorisierungsalgorithmus das
Produkt zerlegen. Bei den üblichen Schlüssellängen reicht es aber
durchaus, p in der Nähe von 2*q zu suchen.
Christian
Gottfried Helms
Jul 26, 2012, 4:34:54 AM7/26/12
to
Hallo Robert, Christian -
ich habe den Kern der Angelegenheit offensichtlich
noch nicht ganz verstanden. Ich schließe mal an Christians Antwort an:
Am 26.07.2012 08:49 schrieb Christian Gollwitzer:
> Am 25.07.12 23:52, schrieb Gottfried Helms:
>
das Softwareprogramm jedesmal eine neue Primzahl *sucht*, wenn ein
Schlüssel erzeugt wird (womöglich basierend auf einem Zufallszahlengenerator,
der eine zufällige Startkonfiguration für die Fermat-test-Suche einstellt) -
oder greift die Software auf vorkonfigurierte Primzahllisten zurück?
Bzw.: kann ein ANgreifer, der dieselbe Software hat, dieselbe
Startkonfiguration reproduzieren (z.B. so ähnlich wie das beim Pseudo-Random-
Generator in C oder Delphi möglich ist) ?
Gottfried
ich habe den Kern der Angelegenheit offensichtlich
noch nicht ganz verstanden. Ich schließe mal an Christians Antwort an:
Am 26.07.2012 08:49 schrieb Christian Gollwitzer:
> Am 25.07.12 23:52, schrieb Gottfried Helms:
>
> Wie Robert schon schrieb, kann man leicht mit dem kleinen Fermat ein
> paar Zahlen finden, die mit großer Wahrscheinlichkeit prim sind. Das
> macht sogar Wolframalpha in Sekundenbruchteilen:
>
> http://www.wolframalpha.com/input/?i=nextprime%281e50%29
>
> Anschließend kann man mit dem AKS-Test die Primalität sogar beweisen, um
> sicher zu gehen. AKS ist zwar aufwendiger, als ein paar mal
>
> a^(n-1) mod n =? 1
>
> zu berechnen, jedoch liefert es als nachgeschobenes Verfahren einen
> Beweis.
Ist es so, daß bei der praktischen Anwendung der Verschlüsselung
> paar Zahlen finden, die mit großer Wahrscheinlichkeit prim sind. Das
> macht sogar Wolframalpha in Sekundenbruchteilen:
>
> http://www.wolframalpha.com/input/?i=nextprime%281e50%29
>
> Anschließend kann man mit dem AKS-Test die Primalität sogar beweisen, um
> sicher zu gehen. AKS ist zwar aufwendiger, als ein paar mal
>
> a^(n-1) mod n =? 1
>
> zu berechnen, jedoch liefert es als nachgeschobenes Verfahren einen
> Beweis.
das Softwareprogramm jedesmal eine neue Primzahl *sucht*, wenn ein
Schlüssel erzeugt wird (womöglich basierend auf einem Zufallszahlengenerator,
der eine zufällige Startkonfiguration für die Fermat-test-Suche einstellt) -
oder greift die Software auf vorkonfigurierte Primzahllisten zurück?
Bzw.: kann ein ANgreifer, der dieselbe Software hat, dieselbe
Startkonfiguration reproduzieren (z.B. so ähnlich wie das beim Pseudo-Random-
Generator in C oder Delphi möglich ist) ?
Gottfried
Johannes Bauer
Jul 26, 2012, 5:47:44 AM7/26/12
to
On 26.07.2012 10:34, Gottfried Helms wrote:
> Ist es so, daß bei der praktischen Anwendung der Verschlüsselung
> das Softwareprogramm jedesmal eine neue Primzahl *sucht*, wenn ein
> Schlüssel erzeugt wird (womöglich basierend auf einem Zufallszahlengenerator,
> der eine zufällige Startkonfiguration für die Fermat-test-Suche einstellt) -
> oder greift die Software auf vorkonfigurierte Primzahllisten zurück?
Ja. Es werden Zufallszahlen erzeugt und die getestet (z.B. mittels
> Ist es so, daß bei der praktischen Anwendung der Verschlüsselung
> das Softwareprogramm jedesmal eine neue Primzahl *sucht*, wenn ein
> Schlüssel erzeugt wird (womöglich basierend auf einem Zufallszahlengenerator,
> der eine zufällige Startkonfiguration für die Fermat-test-Suche einstellt) -
> oder greift die Software auf vorkonfigurierte Primzahllisten zurück?
Miller-Rabin-Test), ob sie prim sind. Wenn ja, gut. Ansonsten suche weiter.
> Bzw.: kann ein ANgreifer, der dieselbe Software hat, dieselbe
> Startkonfiguration reproduzieren (z.B. so ähnlich wie das beim Pseudo-Random-
> Generator in C oder Delphi möglich ist) ?
aber genug Entropie, was der Grund dafür ist, dass du während dem
Generationsvorgang die Maus hin und herwackeln sollst und auf der
Tastatur wild herumtippen.
Gruß,
Johannes
--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1...@speranza.aioe.org>
Jan Fricke
Jul 26, 2012, 6:16:42 AM7/26/12
to
On 07/25/2012 11:52 PM, Gottfried Helms wrote:
> Mein Anteil der Diskussion ging nun dahin, daß wenn die Primzahlen p
Dein Einwand ist wichtig und richtig; ich bin neulich mal auf einen
Artikel über Fallen bei RSA-Implementation gestoßen:
http://cage.ugent.be/~klein/RSA-Fallen.pdf
Da werden solche Probleme behandelt.
Viele Grüße Jan
> Mein Anteil der Diskussion ging nun dahin, daß wenn die Primzahlen p
> und q in praxi lediglich aus bekannten Listen stammen (die viel
> weniger Einträge enthalten als Primzahlen in dem interessierenden
> Bereich vorhanden sind) ist Problem b) natürlich viel leichter
> zu lösen, wenn dem "Angreifer" solche Listen bekannt sind, da er
> Bereich vorhanden sind) ist Problem b) natürlich viel leichter
> dann g simpel durch trial-und-error mit der Abarbeitung der
> Liste faktorisieren kann,
>
> Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
> mißverstanden?
> Liste faktorisieren kann,
>
> Kann man das Argument aufrecht erhalten? Oder habe ich da etwas
Dein Einwand ist wichtig und richtig; ich bin neulich mal auf einen
Artikel über Fallen bei RSA-Implementation gestoßen:
http://cage.ugent.be/~klein/RSA-Fallen.pdf
Da werden solche Probleme behandelt.
Viele Grüße Jan
Gottfried Helms
Jul 26, 2012, 7:39:31 AM7/26/12
to
Am 26.07.2012 12:16 schrieb Jan Fricke:
> Dein Einwand ist wichtig und richtig; ich bin neulich mal auf einen
> Artikel �ber Fallen bei RSA-Implementation gesto�en:
> Dein Einwand ist wichtig und richtig; ich bin neulich mal auf einen
> Viele Gr��e Jan
>
Jan - vielen Dank. Interessanter Aufsatz!
Gottfried
Vogel
Jul 27, 2012, 10:07:27 AM7/27/12
to
Gottfried Helms <he...@uni-kassel.de> schrieb in news:a7b852F534U1
@mid.dfncis.de:
> Wir hatten k�rzlich eine Diskussion �ber RSA-Verschl�sselung.
> Viel mehr, als da� die Schwierigkeit des Code-Knackens
>
> Nach meinem (zugegebenerma�en primitiven) Verst�ndnis besteht
> nun solche Primzahlen kennen zu m�ssen.
>
Nicht notwendig.
>
> Mein Anteil der Diskussion ging nun dahin, da� wenn die Primzahlen p
> Bereich vorhanden sind) ist Problem b) nat�rlich viel leichter
> zu l�sen, wenn dem "Angreifer" solche Listen bekannt sind, da er
generieren.
>
@mid.dfncis.de:
> Wir hatten k�rzlich eine Diskussion �ber RSA-Verschl�sselung.
> Viel mehr, als da� die Schwierigkeit des Code-Knackens
> darin besteht, die Faktoren eines Primzahl-Produkts g=p*q,
> wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
> von 10^50 oder 10^100 oder so, zu finden, wei� ich gar nicht.
> wobei p und q vielstellige Primzahlen sind, z.B. aus dem Bereich
>
> Nach meinem (zugegebenerma�en primitiven) Verst�ndnis besteht
> die (theoretische) Schwierigkeit
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
>
> Die aktuelle softwarem��ige Implementierung von RSA scheint mir
> a) in der Anzahl der Primzahlen in einem Bereich der x-stelligen
> Zahlen
> b) in dem Problem in solch einem Bereich zwei Primfaktoren p*q zu
> finden, die p*q = g definieren.
>
> nun solche Primzahlen kennen zu m�ssen.
>
Nicht notwendig.
>
> Mein Anteil der Diskussion ging nun dahin, da� wenn die Primzahlen p
> und q in praxi lediglich aus bekannten Listen stammen (die viel
> weniger Eintr�ge enthalten als Primzahlen in dem interessierenden
> Bereich vorhanden sind) ist Problem b) nat�rlich viel leichter
> zu l�sen, wenn dem "Angreifer" solche Listen bekannt sind, da er
> dann g simpel durch trial-und-error mit der Abarbeitung der
> Liste faktorisieren kann,
>
Dazu braucht es keine Listen. Man grosse Primzahlen aus kleineren
> Liste faktorisieren kann,
>
generieren.
>
Christopher Creutzig
Aug 31, 2012, 2:53:06 PM8/31/12
to
On 7/26/12 10:34 AM, Gottfried Helms wrote:
> Ist es so, da� bei der praktischen Anwendung der Verschl�sselung
> der eine zuf�llige Startkonfiguration f�r die Fermat-test-Suche einstellt) -
> oder greift die Software auf vorkonfigurierte Primzahllisten zur�ck?
Ersteres. Zumindest im Prinzip, in der Praxis scheint es manchmal
erstaunlich viele Kollisionen zu geben �
http://eprint.iacr.org/2012/064
http://arstechnica.com/business/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security/
> Bzw.: kann ein ANgreifer, der dieselbe Software hat, dieselbe
> Startkonfiguration reproduzieren (z.B. so �hnlich wie das beim Pseudo-Random-
> Generator in C oder Delphi m�glich ist) ?
Bei einer vern�nftigen Implementation nicht, nein.
--
Auf Wunsch kann ich auch unwiderlegbare Beweise f�r diese These erfinden.
(Wolfram Heinrich)
> Ist es so, da� bei der praktischen Anwendung der Verschl�sselung
> das Softwareprogramm jedesmal eine neue Primzahl *sucht*, wenn ein
> Schl�ssel erzeugt wird (wom�glich basierend auf einem Zufallszahlengenerator,
> der eine zuf�llige Startkonfiguration f�r die Fermat-test-Suche einstellt) -
> oder greift die Software auf vorkonfigurierte Primzahllisten zur�ck?
Ersteres. Zumindest im Prinzip, in der Praxis scheint es manchmal
erstaunlich viele Kollisionen zu geben �
http://eprint.iacr.org/2012/064
http://arstechnica.com/business/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security/
> Bzw.: kann ein ANgreifer, der dieselbe Software hat, dieselbe
> Generator in C oder Delphi m�glich ist) ?
Bei einer vern�nftigen Implementation nicht, nein.
--
Auf Wunsch kann ich auch unwiderlegbare Beweise f�r diese These erfinden.
(Wolfram Heinrich)
0 new messages