Wie groß darf rsa-Klartext sein?

17.05.2016, 13:58

Riberyyy

Wie groß darf rsa-Klartext sein?

Meine Frage:
Wenn man mit dem RSA-Algorithmus einer Klartext verschlüsseln möchte, muss der Klartext teilerfremd zum RSA-Modul N sein, oder? Das heißt, man darf nicht alle Zahlen kleiner N verschlüsseln, sondern nur die kleiner als die Primfaktoren von N, da dann garantiert ist, dass die Zahlen teilerfremd sind.

Meine Ideen:
e×d?1 mod phi(N)
e×d=r×phi(N)+1
ggT(a,m)=1?a^phi(m) ?1 mod m
Klartext=T
Schlüssel=e und d
(T^e )^d?T^(d×e)?T^(r×phi(N)+1)?T^(r×phi(n) )×T verwirrt

T^phi(N) )^r×T?T mod N
Letzer Umformungsschritt erfolgt unter Anwendung des Satzes von Euler. Vorraussetzung dafür, dass (T^phi(N) )^r?1 mod N ist, ist allerdings, dass ggT (T,N)=1 ist.
Quelle der Informationen: https://www.youtube.com/watch?v=LgAj4pGVIqI

17.05.2016, 19:04

URL

Auf diesen Beitrag antworten »

RE: Wie groß darf rsa-Klartext sein?

Zitat:

muss der Klartext teilerfremd zum RSA-Modul N sein, oder?

nein, muss er nicht. Der Klartextraum besteht aus allen natürlichen Zahlen $\begin{eqnarray*} 0\leq m<N \end{eqnarray*}$

17.05.2016, 21:25

echnaton

Auf diesen Beitrag antworten »

Zitat:

Vorraussetzung dafür, dass $\begin{eqnarray*} (T^{\varphi(N)})^r\equiv 1\mod N \end{eqnarray*}$ ist, ist allerdings, dass $\begin{eqnarray*} \text{ggT} (T,N)=1 \end{eqnarray*}$ ist.

Das ist richtig. Deswegen wird eine Fallunterscheidung gemacht. Der Fall $\begin{eqnarray*} T\equiv 0\mod p \end{eqnarray*}$ (oder alternativ $\begin{eqnarray*} \mod q \end{eqnarray*}$ ) muss gesondert untersucht werden.

Dazu schaut man sich $\begin{eqnarray*} T^{r \cdot \varphi(N)+1} \end{eqnarray*}$ bzgl. $\begin{eqnarray*} \mod p \end{eqnarray*}$ und $\begin{eqnarray*} \mod q \end{eqnarray*}$ an. Mit dem Chinesischen Restsatz kennt man dann auch den Modulus bzgl. $\begin{eqnarray*} N \end{eqnarray*}$ .

Wenn $\begin{eqnarray*} T \end{eqnarray*}$ ein Vielfaches von $\begin{eqnarray*} p \end{eqnarray*}$ ist, muss $\begin{eqnarray*} \text{ggT}(T,q)=1 \end{eqnarray*}$ gelten (beachte den Definitionsbereich $\begin{eqnarray*} 0 \le T < pq \end{eqnarray*}$ ), also ist $\begin{eqnarray*} T^{r \cdot \varphi(N)+1} \equiv T \mod q \end{eqnarray*}$ . Aber auch $\begin{eqnarray*} T^{r \cdot \varphi(N)+1} \equiv 0 \equiv T \mod p \end{eqnarray*}$ .

17.05.2016, 21:36

URL

Auf diesen Beitrag antworten »

Ah, das war das eigentliche Problem. Vor den ganzen Fragezeichen habe ich kapituliert.

Neue Frage »

Antworten »

Wie groß darf rsa-Klartext sein?

Verwandte Themen