Frage zu RSA + Bonus-Beweis zu etwas anderem

18/04/2009 - 12:28 von Markus Wichmann | Report spam
Hi all,

ich habe da mal eine Frage zur mathematischen Seite von RSA: Und zwar
ist mir aufgefallen, dass doch gleiche Eingaben bei gleichem Schlüssel
auch den gleichen verschlüsselten Text hervorrufen.

Bsp.: Sei (N, e) ein öffentlicher RSA-Schlüssel so, dass E(8) = 15. Dann
ist E(8) immer 15, egal was vorher kam oder danach kommen wird. (Dabei
ist E die Verschlüsselungsfunktion.)

Damit kann doch RSA gebrochen werden, indem man es einfach einer
Hàufigkeitsanalyse unterzieht. In der Hinsicht ist es also nicht
sicherer, als eine einfache Substitution.

Meine Frage: Wieso wird RSA dann noch als sicher angesehen? Oder wird in
gàngigen Verfahren etwas gemacht, was ich nicht wissen konnte, weil das
in den öffentlich zugànglichen Dokumentationen fehlt? Oder habe ich
irgendwo anders was übersehen?

Bonus-Beweis: (Eine Sache, die mir mal so einfiel, vielleicht hilft es
jemandem.)

Behauptung: salopp: 0,999... = 1


\ -i
formal: > (9 ⋅ 10 ) = 1
/
i = 1

Beweis: Eine axiomatische Forderung für die reelen und auch die
rationalen Zahlen ist ihre Dichtheit. D.h. für jede zwei verschiedenen
reelen oder rationalen Zahlen làsst sich eine finden, die dazwischen
passt:

∀ a, b ∊ R : a < b → ∃ c ∊ R: a < c < b

Es ist wohl einleuchtend, dass man das auch umdrehen kann: Damit zwei
reelle Zahlen verschieden sind, muss eine dritte reelle Zahl dazwischen
passen.

Nun, genau so eine reelle Zahl existiert hier nicht. Kann sie auch
nicht: Es passt einfach nix zwischen eine unendliche Folge von Neunen,
die hinter einem "0," stehen, und die 1. Es gibt nichts dazwischen.

OK, das Ende leckt ein bisschen... hat jemand eine Idee, das zu beenden?

Tschö,
Markus

P.S.: Verwendete Unicode-Zeichen (für die, die es nicht lesen können):

U+221E ∞ INFINITY SIGN
U+22C5 ⋅ MULTIPLICATION DOT
U+2200 ∀ FOR-ALL OPERATOR
U+220A ∊ SMALL ELEMENT-OF OPERATOR
U+2192 → SINGLE RIGHT-POINTING ARROW
U+2203 ∃ THERE-IS OPERATOR
GUI - ein Hintergrundbild und zwölf XTerms

vim -c "exec \"norm iwHFG#NABGURE#IVZ#UNPXRE\"|%s/#/ /g|norm g??g~~"
 

Lesen sie die antworten

#1 Sebastian Biallas
18/04/2009 - 16:26 | Warnen spam
Markus Wichmann wrote:
Hi all,

ich habe da mal eine Frage zur mathematischen Seite von RSA: Und zwar
ist mir aufgefallen, dass doch gleiche Eingaben bei gleichem Schlüssel
auch den gleichen verschlüsselten Text hervorrufen.



Das ist sehr fein beobachtet :)

Das führt beispielweise auch dazu, dass man sehr kurze Texte oder
Serienbriefe, bei denen sich nur ein kleiner Teil àndert (beispielweise
eine PIN) einfach durch Raten brechen könnte.

Da diese Problematik aber làngst erkannt ist, deshalb fügt man vor der
Verschlüsselung immer noch ausreichend Zufallszahlen am Ende der
Nachricht hinzu. Oder man verschlüsselt gleich nur einen zufàllig
gewàhlten AES Key.

Gruß,
Sebastian

Ähnliche fragen